RRT*算法与优化运动规划：理论局限与新突破
需积分: 10 41 浏览量
更新于2024-07-23
收藏 9MB PDF 举报
增量采样基算法在最优运动规划中的应用已经成为近年来研究的热点，特别是在Rapidly-exploring Random Trees (RRT)系列算法中。RRTs因其在实践中表现出色并具备概率完备性等理论保证而受到广泛关注。然而，对于这类算法所能达到的解决方案质量，直到现在仍未有明确的理论界限。
本文的第一大贡献是理论上的负面结果：它证明了，在满足某些温和的技术假设下，RRT产生的路径成本几乎必然趋向于一个非最优值。这一发现揭示了RRT在追求全局最优解时可能存在的局限性，尽管它在实际问题解决中表现良好。
为了克服这一局限，作者引入了一种新的算法——Rapidly-exploring Random Graph (RRG)，其成本最优路径的收敛性被证明几乎是确定的。相比于RRT，RRG在保持随机性和探索性的同时，更接近于找到全局最优解。
此外，文中还提出了一种结合了RRG优点且保留了RRT结构特点的树形版本算法——RRT*。RRT*算法通过创新的连接RRTs与随机抽样规划算法理论之间的桥梁，能够在保证渐进优化的同时，提供更为精确和高效的路径规划。这意味着RRT*在保持RRT的灵活性和效率的同时，能够向最优解的收敛提供坚实的理论基础。
总结来说，这篇论文对增量采样基算法进行了深入探讨，特别关注了RRT和其变种RRG以及RRT*的性能分析。它不仅指出了RRT的不足，还提出了改进方法，展示了如何通过理论和实践的结合，提高运动规划算法在寻找最优路径上的能力。这对于理解这类算法的工作原理、优化它们的性能以及设计未来更高效规划策略具有重要意义。
4
constants M and n
0
such that f(n) ≥ Mg(n) for all n ≥ n
0
.
The function f(n) is said to be Θ(g(n)), denoted as f(n) ∈
Θ(g(n)), if f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)).
Let X be a subset of R
d
. A (directed) graph G = (V, E) on
X is composed of a vertex set V and an edge set E, such that
V is a finite subset of X, and E is a subset of V × V . The
set of all directed graphs on X is denoted by G
X
. A directed
path on G is a sequence (v
1
, v
2
, . . . , v
n
) of vertices such that
(v
i
, v
i+1
) ∈ E for all 1 ≤ i ≤ n − 1. Given a vertex v ∈ V ,
the sets {u ∈ V |(u, v) ∈ E} and {u ∈ V |(v, u) ∈ E}
are said to be its incoming neighbors and outgoing neighbors,
respectively. A (directed) tree is a directed graph, in which
each vertex but one has a unique incoming neighbor; the vertex
with no incoming neighbor is called the root vertex. Vertices
of a tree are often also called nodes.
B. Problem Formulation
In this section, two variants of the path planning problem
are presented. First, the feasibility problem in path planning
is formalized, then the optimality problem is introduced.
Let X be a bounded connected open subset of R
d
, where
d ∈ N, d ≥ 2. Let X
obs
and X
goal
, called the obstacle region
and the goal region, respectively, be open subsets of X. Let
us denote the obstacle-free space, i.e., X \X
obs
, as X
free
. Let
the initial state, x
init
, be an element of X
free
. In the sequel, a
path in X
free
is said to be a collision-free path. A collision-free
path that starts at x
init
and ends in the goal region is said to
be a feasible path, i.e., a collision-free path σ : [0, s] → X
free
is feasible if and only if σ(0) = x
init
and σ(s) ∈ X
goal
.
The feasibility problem of path planning is to find a feasible
path, if one exists, and report failure otherwise. The problem
can be formalized as follows.
Problem 1 (Feasible planning) Given a bounded connected
open set X ⊂ R
d
, an obstacle space X
obs
⊂ X, an initial
state x
init
∈ X
free
, and a goal region X
goal
⊂ X
free
, find a
path σ : [0, s] → X
free
such that σ(0) = x
init
and σ(s) ∈
X
goal
, if one exists. If no such path exists, then report failure.
Let c : Σ
X
free
→ R
>0
be a function, called the cost
function, which assigns a non-negative cost to all nontrivial
collision-free paths. The optimality problem of path planning
asks for finding a feasible path with minimal cost, formalized
as follows.
Problem 2 (Optimal planning) Given a bounded connected
open set X, an obstacle space X
obs
, an initial state x
init
, and
a goal region X
goal
, find a path σ
∗
: [0, s] → cl(X
free
) such
that (i) σ
∗
(0) = x
init
and σ
∗
(s) ∈ X
goal
, and (ii) c(σ
∗
) =
min
σ∈Σ
cl(X
free
)
c(σ). If no such path exists, then report failure.
III. ALGORITHMS
In this section, two incremental sampling-based motion
planning algorithms, namely the RRT and the RRG algorithms,
are introduced. Before formalizing the algorithms, let us note
the primitive procedures that they rely on.
Sampling: The function Sample : N → X
free
returns
independent identically distributed (i.i.d.) samples from X
free
.
Steering: Given two points x, y ∈ X, the function Steer :
(x, y) 7→ z returns a point z ∈ R
d
such that z is “closer” to y
than x is. Throughout the paper, the point z returned by the
function Steer will be such that z minimizes kz − yk while
at the same time maintaining kz − xk ≤ η, for a prespecified
η > 0,
1
i.e.,
Steer(x, y) = argmin
z∈R
d
,kz−xk≤η
kz − yk.
Nearest Neighbor: Given a graph G = (V, E) ∈ G
X
free
and a point x ∈ X
free
, the function Nearest : (G, x) 7→ v
returns a vertex v ∈ V that is “closest” to x in terms of a
given distance function. In this paper, we will use Euclidean
distance (see, e.g., [18] for alternative choices), i.e.,
Nearest(G = (V, E), x) = argmin
v∈V
kx − vk.
Near Vertices: Given a graph G = (V, E) ∈ G
X
free
, a
point x ∈ X
free
, and a number n ∈ N, the function Near :
(G, x, n) 7→ V
0
returns a set V
0
of vertices such that V
0
⊆ V .
The Near procedure can be thought of as a generalization of
the nearest neighbor procedure in the sense that the former
returns a collection of vertices that are close to x, whereas the
latter returns only one such vertex that is the closest. Just like
the Nearest procedure, there are many ways to define the
Near procedure, each of which leads to different algorithmic
properties. For technical reasons to become clear later, we
define Near(G, x, n) to be the set of all vertices within the
closed ball of radius r
n
centered at x, where
r
n
= min
(
γ
ζ
d
log n
n
1/d
, η
)
,
and γ is a constant. Hence, the volume of this ball is
min{γ
log n
n
, ζ
d
η
d
}.
Collision Test: Given two points x, x
0
∈ X
free
, the Boolean
function ObstacleFree(x, x
0
) returns True iff the line seg-
ment between x and x
0
lies in X
free
, i.e., [x, x
0
] ⊂ X
free
.
Both the RRT and the RRG algorithms are similar to most
other incremental sampling-based planning algorithms (see
Algorithm 1). Initially, the algorithms start with the graph that
includes the initial state as its single vertex and no edges; then,
they incrementally grow a graph on X
free
by sampling a state
x
rand
from X
free
at random and extending the graph towards
x
rand
. In the sequel, every such step of sampling followed
by extensions (Lines 2-5 of Algorithm 1) is called a single
iteration of the incremental sampling-based algorithm.
Hence, the body of both algorithms, given in Algorithm 1, is
the same. However, RRGs and RRTs differ in the choice of the
vertices to be extended. The Extend procedures for the RRT
and the RRG algorithms are provided in Algorithms 2 and 3,
respectively. Informally speaking, the RRT algorithm extends
the nearest vertex towards the sample. The RRG algorithm first
extends the nearest vertex, and if such extension is successful,
it also extends all vertices returned by the Near procedure. In
both cases, all extensions resulting in collision-free trajectories
1
This steering procedure is used widely in the robotics literature, since its
introduction in [29]. Our results also extend to the Rapidly-exploring Random
Dense Trees (see, e.g., [30]), which are slightly modified versions of the RRTs
that do not require tuning any prespecified parameters such as η in this case.
剩余19页未读，继续阅读
270 浏览量
132 浏览量
点击了解资源详情
点击了解资源详情
2025-03-12 上传
2025-03-12 上传
w1234567XH
- 粉丝: 4
我的内容管理
展开
最新资源
- Win7系统下的一键式笔记本显示器关闭解决方案
- 免费替代Visio的流程图软件：DiaPortable
- Polymer 2.0封装的LineUp.js交互式数据可视化库
- Kotlin编写的Linux Shell工具Kash：强大而优雅的命令行体验
- 开源海军贸易模拟《OpenPatrician》重现中世纪北海繁荣
- Oracle 11g 32位客户端安装与链接指南
- 创造js实现的色彩识别小游戏「看你有多色」
- 构建Mortal Kombat Toasty展示组件：Stencil技术揭秘
- 仿驱动之家触屏版手机wap硬件网站模板源码
- babel-plugin-inferno：JSX转InfernoJS vNode插件指南
- 软件开发中编码规范的重要性与命名原则
- 免费进销存软件的两个月试用体验
- 树莓派从A到Z的Linux开发完全指南
- 晚霞天空盒资源下载 - 美丽实用的360度全景贴图
- perfandpubtools：MATLAB性能分析与发布工具集
- WPF圆饼图控件源代码分享：轻量级实现
