Choudhury 等。 - 2016 - Regionally accelerated batch informed tree
需积分: 0 158 浏览量
2022-08-04
16:28:51
上传
评论
收藏 2.25MB PDF 举报
Regionally Accelerated Batch Informed Trees (RABIT*): A Framework
to Integrate Local Information into Optimal Path Planning
Sanjiban Choudhury
1
, Jonathan D. Gammell
2
,
Timothy D. Barfoot
2
, Siddhartha S. Srinivasa
1
, and Sebastian Scherer
1
Abstract— Sampling-based optimal planners, such as RRT*,
almost-surely converge asymptotically to the optimal solution,
but have provably slow convergence rates in high dimensions.
This is because their commitment to finding the global optimum
compels them to prioritize exploration of the entire problem
domain even as its size grows exponentially. Optimization
techniques, such as CHOMP, have fast convergence on these
problems but only to local optima. This is because they are
exploitative, prioritizing the immediate improvement of a path
even though this may not find the global optimum of nonconvex
cost functions.
In this paper, we present a hybrid technique that integrates
the benefits of both methods into a single search. A key insight
is that applying local optimization to a subset of edges likely to
improve the solution avoids the prohibitive cost of optimizing
every edge in a global search. This is made possible by Batch
Informed Trees (BIT*), an informed global technique that
orders its search by potential solution quality. In our algorithm,
Regionally Accelerated BIT* (RABIT*), we extend BIT* by
using optimization to exploit local domain information and
find alternative connections for edges in collision and accelerate
the search. This improves search performance in problems
with difficult-to-sample homotopy classes (e.g., narrow passages)
while maintaining almost-sure asymptotic convergence to the
global optimum.
Our experiments on simulated random worlds and real data
from an autonomous helicopter show that on certain difficult
problems, RABIT* converges 1.8 times faster than BIT*.
Qualitatively, in problems with difficult-to-sample homotopy
classes, we show that RABIT* is able to efficiently transform
paths to avoid obstacles.
I. INTRODUCTION
Sampling-based planners are popular for solving the
motion-planning problem in robotics and are effective on
a large range of applications. Algorithms such as Proba-
bilistic Roadmaps (PRM) [1], Rapidly-exploring Random
Trees (RRT) [2], and Expansive Space Trees (EST) [3] are
probabilistically complete. These algorithms find a solution,
if one exists, with probability one as the number of samples
goes to infinity.
Recent research has developed asymptotically optimal
planners, such as
RRT*
[4]. The solutions found by these
algorithms converge asymptotically to the optimum, if one
exists, with probability one as the number of samples goes to
infinity (i.e., almost surely). With informed search techniques,
such as Informed
RRT*
, this convergence can be linear in
1
S. Choudhury, S. S. Srinivasa and S. Scherer are with The Robotics
Institute at Carnegie Mellon University, Pittsburgh, Pennsylvania, USA.
Email: {sanjibac, basti, siddh}@cs.cmu.edu
2
J. D. Gammell and T. D. Barfoot are with the Autonomous Space
Robotics Lab at the University of Toronto, Toronto, Ontario, Canada. Email:
{jon.gammell, tim.barfoot}@utoronto.ca
s = 1.87 s = 1.66
(a) (b)
BIT* RABIT*
Fig. 1. Solutions found by
BIT*
and
RABIT*
after
0.1
seconds of
computation time on a simulated
2
-dimensional world. The world has an
obstacle with a narrow gap that creates three homotopy classes, two of
which flank the obstacle and one that passes through the narrow gap.
BIT*
’s
ability to find a path through the narrow gap depends on the distribution
of the random samples.
RABIT*
judiciously applies a local optimizer to
potential edges (shown in magenta), allowing it to exploit additional problem
information and find paths through difficult-to-sample homotopy classes
(e.g., narrow passages) faster than sampling alone.
the absence of obstacles [5], but generally convergence is
provably poor, especially in high dimensions [6]. This is
because the algorithms prioritize exploring the domain despite
its exponential growth in size with increased state dimension.
Local optimizers, such as Covariant Hamiltonian Optimiza-
tion for Motion Planning (
CHOMP
) [7], instead prioritize
exploiting domain information, such as cost gradients, to
modify and improve a path. This rapidly finds high-quality
solutions in high-dimensional planning problems, but only
provides guarantees on local optimality. This is because
nonconvex cost functions have local optima that can entrap
greedy optimization methods, such as gradient descent. This
makes the relative suitability of local optimizers and global
searches dependent on the specific planning problem [8].
In the field of nonconvex optimization, it is common to
avoid these limitations by combining local optimization with a
global search [9]–[14]. This provides the rapid convergence of
local optimizers (e.g., gradient descent) with the insensitivity
to local optima of a global search (e.g., stochastic search).
In this paper, we use this existing work as motivation for
a framework to integrate local and global planning methods
into a hybrid search. We do so by using Batch Informed
Trees (
BIT*
) [15], a global method that uses heuristics to
search in order of potential solution quality. This provides the
efficiency necessary for a local optimizer to generate potential
edges from domain information (e.g., cost gradients). This
2016 IEEE International Conference on Robotics and Automation (ICRA)
Stockholm, Sweden, May 16-21, 2016
978-1-4673-8026-3/16/$31.00 ©2016 IEEE 4207
评论0
最新资源