ROS学习笔记（6）——路径规划

全局路径规划：

提供Dijkstra和A*算法，默认使用Dijkstra

Dijkstra：广度优先，从近到远遍历所有点计算一遍，直至计算出最优路径

伪代码：

获取起点坐标、目标点坐标，把起点放进openlist

while (openlist不为空列表)

{ 取openlist中路程最小的点为中心点，从openlist剔除，放入closedlist

if (中心点是目标点)

{从目标点开始通过父节点反推，提取出路径，break跳出循环}

else
{遍历相邻的八个点

{if(点已存在closedlist中  or  遇到障碍物 )

{跳过，不计算这个点}

else

{累计路径

if(点已存在openlist中)

if(累计路程<原来记录的路程)

{替换数据}

else {加入openlist}

}

openlist从小到大排序

}

}

A*算法：深度优先，按目标点的方向计算

伪代码：

获取起点坐标、目标点坐标，算出起点的F值(F=0+H)把起点放进openlist

while (openlist不为空列表)

{ 取openlist中F值最小的点为中心点，从openlist剔除，放入closedlist

if (中心点是目标点)

{从目标点开始通过父节点反推，提取出路径，break跳出循环}

else
{遍历相邻的八个点

{if(点已存在closedlist中  or  遇到障碍物 )

{跳过，不计算这个点}

else

{累计实际路程G，估算H，F=G+H

if(点已存在openlist中)

if(实际路程G<原来记录的G)

{替换数据}

else {加入openlist}

}

openlist从小到大排序

}

}

base_global_planner：配置全局规划器名称

global_planner和navfn功能包区别：

navfn默认使用Dijkstra算法，A*算法有BUG

global_planner可以使用两种算法，补充升级

carrot增加解决目标点放置在障碍物中的问题

切换算法：

base global planner: "global_planner/GlobalPlanner”#指定用于move base的规划器插件名称

global_planner/use_dijkstra:false

global planner/use_grid path: true

局部路径规划：

DWA算法：

初始化——小车最大最小速度、加速度，评价函数权重等

循环

{ 判断是否到达目的地

计算当前采样的速度范围（动态窗口）

遍历所有速度v & w，根据模型模拟一段时间的路径

根据评价函数打分（包括评价函数、归一化、权重）

选取最优解——v & w，下发给运动底盘

小车继续移动

局部路径规划之Teb——Timed-Elastic-Band