RRT*算法是一种基于随机采样的路径规划方法,不仅具有概率完备性,还具有渐进优化能力。假设X=(0,1)^d代表d维构型空间,d \in N,d\geq 2
进一步假设X_{obs}代表障碍物空间,X_{obs}属于X.X_{free}表示自由空间,X_{free}+X_{obs}=X.对于机器人来说,初始构型和x_{init}和目标构型x_{goal}是X_{free}中的元素。由此可以将路径规划问题转化为以下形式
(X_{free},x_{init},x_{goal})
假设函数\sigma:[0,1] \rightarrow R^4 ,\sigma 的全变差可以定义如下:
为了更好的理解算法,有必要实现熟悉三个定义:
定义一
\sigma的全变差TV(\sigma)<\infty,则称函数\sigma为区间[0,1]上的有界变差函数。
->\sigma是连续函数,则可以称\sigma为路径,
->\sigma是路径,且对所有\tau \in [0,1], \sigma(\tau) \in X_{free}.则\sigma 为碰撞路径;
->σ是无碰撞路径, 且\sigma(0)=x_{init}, \sigma(1)=x_{goal},则称\sigma 为可行路径。
由上述定义,路径的总变差可以理解为路径的长度。
定义二
(可行路径规划)给定一个路径规划问题(X_{free},x_{init},x_{goal}),如果可行路径存在,则规划一条可行路径,如果路径不存在,则返回可行路径失败信息。
定义三
规划一条路径问题,(X_{free}, x_{init}, x_{goal}),并定义价值函数c: \sum \rightarrow R \geq0 .\sum 是可行路径。如果最优路径存在,则会规划一条最优路径\sigma*且如果最优路径存在,则返回最优路径规划失败信息。
对于机器人的路径规划,从环境情况感知情况,可以将其分为以下两种:
RRT算法全称是快速扩展随机树,(RRT, Rapidly-exploring Random Trees)是最近十几年得到广泛发展与应用的基于概率采样的运动规划算法。由Steven M.LaValle教授在1998年提出。
RRT算法适合解决多自由度机器人在复杂环境下和动态环境中的路径规划问题。
与其他的随机路径规划方法相比,RRT算法更适用于非完整约束和多自由度的系统中。
RRT 算法具有以下优势:
Ref: 冗余机械臂运动学及避障路径规划研究