遍历所有点的最短路径matlab_全覆盖路径规划及其在slam无人车适用方案

基本概念&＃xff1a;

CCPP:

Complete Coverage Path Planning

CCPP需解决的关键问题&＃xff1a;

遍历工作区域内除障碍物以外的全部区域

在遍历过程中有效避开所有障碍物

在遍历过程中要尽量避免路径重复,缩短移动距离

CCPP技术指标&＃xff1a;

区域覆盖率

路径重复率

总行程

死区&＃xff1a;

是指它的周边相邻区域,或者是边界,或者是障碍物,或者是已覆盖过的区域

全覆盖路径规划问题本质&＃xff1a;

在栅格地图中,全覆盖路径规划问题就演变为寻找机器人的下一个移动位置,只有准确找出了该位置,才能使机器人自主规划出一条切实可行的无碰撞且重复率低的移动路径。

路径搜索

路径表达&＃xff1a;以环境模型中的结点序列组成或由直线段序列组成

路径平滑&＃xff1a;根据机器人运动学或动力学约束&＃xff0c;形成机器人可跟踪执行的运动轨迹

运动学约束&＃xff1a;路径轨迹的一阶导数应连续

动力学约束&＃xff1a;路径轨迹的二阶导数应连续

CCPP方法分类

1 行为覆盖法&＃xff1a;随机碰撞法

原理&＃xff1a;机器人根据简单的移动行为,尝试性地覆盖工作区域,如果遇到障碍物,则执行对应的转向命令

缺点&＃xff1a;行为全覆盖算法工作效率低,路径规划策略过于简单,面对复杂地形机器人经常无法逃离死区

随机覆盖法&＃xff0c;也称为随机碰撞式导航&＃xff0c;但这并非是指机器人真正与环境中的物体产生碰撞&＃xff0c;也非毫无章法的在地板上随机移动&＃xff0c;随机覆盖法是指机器人根据一定的移动算法&＃xff0c;如三角形、五边形轨迹尝试性的覆盖作业区&＃xff0c;如果遇到障碍&＃xff0c;则执行对应的转向函数。这种方法是一种以时间换空间的低成本策略&＃xff0c;如不计时间可以达到 100%覆盖率。随机覆盖法不用定位、也没有环境地图&＃xff0c;也无法对路径进行规划&＃xff0c;所以其移动路径基本依赖于内置的算法&＃xff0c;算法的优劣也决定了其清扫质量与效率的高低。

2 区域分割法

原理&＃xff1a;为了使机器人能够逃离死区,同时减少算法的计算量,Jin等提出一种基于时空信息的全局导航与局部导航组合的算法。

优点&＃xff1a;

该算法一方面能够通过局部计算代替不必要的全局计算,减少了实时决策时局部最优导航的计算量;

另一方面通过分层的方式使机器人能够逃离死区。

缺点&＃xff1a;

局部与全局的转换过程中,当周围没有未覆盖的区域时,机器人需要扩大邻近区域的面积来寻找未覆盖区域,这将导致覆盖效率的降低,尤其是当未覆盖区域距离机器人较远时

3 神经网络法

原理&＃xff1a;利用神经网络的自学习、并行性等特性,增强机器人的“智能”,提高覆盖效率。受神经网络结构与栅格地图单元类似的启发,加拿大学者 S. X.Yang等提出一种基于生物启发神经网络的移动机器人全覆盖路径规划算法,将需要全覆盖的二维栅格地图单元与生物启发神经网络的神经元一一对应起来,机器人实现全覆盖的实时路径规划是由神经元的活性值和机器人的上一位置产生的。该算法完全根据栅格地图单元的性质 (未搜索单元、已搜索单元还是障碍物),决定神经元的输入,直接计算神经元的活性值,不存在神经网络学习过程

优点&＃xff1a;算法实时性好,同时可以自动避障与逃离死区。

缺点&＃xff1a;但是基于生物启发神经网络的全覆盖算法计算量大,同时此种方法中神经网络模型的衰减率等参数没有最优值,在实现算法时只能通过反复实验确定,参数的设定存在人为不确定因素,从而影响其在线应用

4.路径规划式

规划式导航需要建立起环境地图并进行定位。对路径规划的研究已经持续很多年了&＃xff0c;也提出了很多种类的方法。不同的方法有各自的优缺点&＃xff0c;适用范围各不相同&＃xff0c;没有一种路径规划方法能适用于所有的环境信息。其中的人工势场法、栅格法、模板模型法、人工智能法等是路径规划中很典型的方法&＃xff0c;并且受到越来越多的关注。

下面主要来看最常见的两种搜索&＃xff1a;

第一种螺旋式搜索&＃xff1a;

这种方式在无障碍物时看起来效果还不错&＃xff0c;可是一旦有障碍物时&＃xff0c;往往会陷入局部死区&＃xff0c;搜索路径也会大大增加&＃xff0c;所以不采用。

第二种弓字型搜索&＃xff1a;

这种方式在无任何障碍物时就像耕地一样一趟一趟得进行搜索&＃xff0c;当存在障碍物时&＃xff0c;通过设计算法效果如下&＃xff1a;

可以看到存在障碍物时&＃xff0c;也可以合理的安排路径&＃xff0c;故采用这种方式&＃xff0c;在此基础上进行改进来运行适合slam建图的路径规划。

适用于slam无人车的CCPP方案&＃xff1a;

1 思想

首先来看slam无人车与扫地机器人的不同&＃xff1a;

扫地机器人一次智能遍历到它当前位置的那个格子&＃xff0c;而无人车由于其上的摄像头&＃xff0c;因此可以抽象如下&＃xff1a;

车一次所能遍历到的其实就是它的视野&＃xff0c;我们可以通过可信范围的方式认为其遍历到的格子

是一个三角形的范围&＃xff0c;视野前端半径为r个格子&＃xff0c;视野远端h个格子&＃xff0c;这样一次覆盖范围就为&＃xff1a;

由于视野比较宽阔&＃xff0c;所以在走一次的路线上视野覆盖面积其实类似与铲雪一样&＃xff1a;

直行一趟扫过的面积其实是一个宽为2r个格子的矩形&＃xff0c;因此我们没有必要一列一列的去搜索&＃xff0c;在掉头时不用只是向左或向右只走一个格子就进行下一列的搜索&＃xff0c;而是掉头时向左或向右走2r个格子再进行下一列的搜索&＃xff0c;并且由于视野可以延申h和格子&＃xff0c;因此在距离边界h个格子时就可以进行掉头&＃xff1a;

2 方案

1. 从起点&＃xff08;1&＃xff0c;1&＃xff09;开始&＃xff0c;设地图总共大小为&＃xff08;m&＃xff0c;n&＃xff09;.首先行至&＃xff08;r&＃xff0c;0&＃xff09;&＃xff0c;若行进路线上无障碍物&＃xff0c;则下一个目标点设置为这一列的对面&＃xff0c;视野覆盖下扫过的单元格记录到搜索过的列表中。
2. 若碰到障碍物或是搜索过的格子&＃xff08;当前位置距其r个格子&＃xff09;&＃xff0c;则检测这个障碍物的横向长度占几个格子&＃xff0c;手动设置阈值&＃xff0c;若绕过的路程少&＃xff0c;则直接绕过&＃xff0c;把目标点设置为障碍物的背面对应点&＃xff0c;利用A*进行导航&＃xff0c;继续搜索&＃xff0c;若横向长度太长&＃xff0c;则直接掉头。

1. 若障碍物紧靠边界&＃xff0c;通过阈值判断&＃xff0c;若是长的障碍物&＃xff0c;则还是直接掉头&＃xff0c;若是短的&＃xff0c;则直接把接下来的目标点设定为障碍物旁边的一个格子&＃xff1a;

1. 检测周围区域&＃xff0c;若均是障碍物或是搜索过的区域&＃xff0c;则表示无路可走&＃xff0c;也就是陷入死区&＃xff1a;

死区示意图&＃xff1a;

此时利用A*导航至离当前点最近的未搜索区域继续搜索&＃xff1a;

5&＃xff0c;重复进行&＃xff0c;直到搜索所有格子加入列表。