摘要∶针对跳点搜索（JPS，jump point search）算法在障碍物位置随机的栅格地图中路径规划时间较长的问题，提出了并行一交替式双向跳点搜索（PA-BJPS，parallel alternate bidirectional jump point search）算法；首先，在起始点与目标点间确定一个中心热点区域；其次，采用改进了预计代价函数的并行式双向跳点搜索算法，分别规划从起始点抵达中心热点区域以及目标点抵达中心热点区域的路径；然后，采用交替式双向跳点搜索算法，规划中心热点区域内部的路径；最后，提出迭代式路径修正方法来改良危险路径，并采用3次B-样条曲线替代拐角来平滑路径；仿真结果表明，并行一交替式双向跳点搜索算法有效地缩短了路径规划时间，同时提高了路径的安全性和平滑性。
路径规划是移动机器人研究领域的关键内容，它是指在障碍物环境下，机器人自主地规划出一条从起始点运行至目标点的无碰撞路径。为解决机器人的路径规划问题，各国科研人员主要提出了以下四类路径规划算法∶
1）基于智能搜索算法，如∶蚁群算法、粒子群算法、快速搜索随机数算法等；
2）基于
人工智能算法，如∶深度学习、Q-Learning算法等；
3）基于几何模型算法，如∶Dijkstra算法、Voronoi图等；
4）基于局部避障算法，如∶人工势场法、动态窗口法等。
在上述的四类路径规划算法中，基于智能搜索算法的路径规划其最大的特点是具有随机性，它首先随机生成初始解或采样点，然后通过迭代的方式来逼近最优解，因此它的解是渐进最优且非唯一的，当地图中的最优路径比较狭窄时，该方法可能会规划出较长的冗余路径。基于人工智能算法的路径规划能够让机器人自主对环境进行学习以实现自主路径规划，其通常只使用在具有大量数据样本的场景中。基于避障算法的路径规划主要适用于移动机器人在局部地图中的避障场景，主要用于提高移动机器人的安全性。基于几何模型的路径规划算法能够实时调节根据最优策略得到的可行解，其在工业、农业、医疗等领域的移动机器人路径规划中均得到广泛应用，极大地提高了生产生活的效率，适用于大规模静态场景下的移动机器人路径规划问题。
基于几何模型的路径规划先需根据已知的环境信息构建地图几何模型，再在几何模型中规划合适的路径。常见的地图模型有3种∶
1）语义地图；
2）栅格地图；
3）拓扑地图。
构建语义地图需要与同步定位与建图技术相结合，其主要应用于识别环境中独立个体，以应对复杂场景及完成更加智能的任务。栅格地图能够反应物体真实的物理尺寸，在实时环境中有助于机器人的定位与导航。拓扑地图是对地理空间的抽象和形式化描述57，其采用节点和连线来表述环境信息，通常关键位置以节点的形式表示，连线表示节点之间是否允许通行。相较于只表示不同节点之间连通关系的拓扑地图而言，栅格地图能够唯一确定地表示机器人、障碍物、可行路径的确切位置信息。与此同时，栅格地图还有具有易于构建和保存的特点，因此各国的工程师和科研人员研究提出了诸多建立在栅格地图基础上的路径规划算法。
A*算法是一种可应用在栅格地图中的启发式路径规划算法，其在搜索过程中具有一定的方向性，具有运行效率较高的特点61。该方法广泛应用于单机器人在全局静态环境中的路径规划。文献【7】通过在估价函数中加入车身轮廓代价和障碍物距离代价对A*算法进行改进；文献【8】参考了人工势场法的引力思想，提升了A*算法的效率。即便如此，在障碍物栅格数量较少的空旷区域，A*算法仍需对栅格进行逐个搜索，这导致了冗余的搜索栅格增多，降低了算法的效率【9】。
针对A*算法在空旷区域搜索效率十分有限的问题，跳点搜索算法（JPS，jump point search）在A*算法的基础上进行了优化。文献【10】的验结果表明，由于跳点搜索算法在扩展过程中裁剪了无用的节点，其路径规划速度高于A*算法。文献【11】提出了一种正六边形栅格跳点搜索算法，并以此解决智能体在障碍物地图中的路径规划问题；文献【12】提出通过“块”操作的方法减少跳点搜索过程中不必要的节点，进一步加快跳点搜索算法的速度。然而，在障碍物位置分布随机的情况下，障碍物个数的增加导致了跳点数量的攀升，跳点搜索算法的路径规划的时间仍大幅度增加。此外，由于跳点搜索算法没有考虑机器人的体积大小，其规划出的路径存在紧贴障碍物、轨迹不平滑问题，给机器人的运行带来安全风险。
在障碍物位置随机的栅格地图中，针对跳点搜索算法路径规划时间大幅度增加的问题，本文提出了并行一交替式双向跳点搜索（PA-BJPS，parallel alternate bidirectional jump point search）算法，其首先在障碍物位置随机的栅格地图里确定一个中心热点区域，在该中心热点区域的外部采用并行运算的方式规划路径，在中心热点区域内部采用交替运算的方式规划路径，有效地缩短了路径规划的时间。针对跳点搜索算法规划的路径存在安全性和平滑性不足的问题，本文提出迭代式路径修正方法来改良危险路径，并采用3次B-样条曲线替代拐角来平滑路径。仿真实验结果表明，本文算法有效地缩短了路径规划的时间，同时兼顾了路径的安全性和平滑性，具有良好的工程应用前景。
1、跳点搜索算法及其不足
跳点搜索算法在保留A*算法框架的同时，优化了A*算法对后续节点扩展的操作。通过对扩展节点的筛选和处理，跳点搜索算法不仅缩短了路径规划的时间，而且减小了节点信息的内存占用量。然而，跳点搜索算法只将移动机器人视为一个质点，因此由跳点搜索算法规划的路径可能会由于移动机器人紧贴障碍物而产生碰撞风险。此外，若采用跳点搜索算法进行双向的路径规划，还可能会造成路径规划时间增长和路径冗余的问题。
1.1 跳点搜索算法
在进行路径规划时，跳点搜索算法对扩展过程中的无用节点进行裁剪，只保留了用于扩展的跳点。当跳点搜索算法扩展至目标点后，即得到一条从起始点到目标点的无障碍路径。
跳点搜索算法进行路径规划时，首要筛选栅格中的强迫邻居（Forced Neighbour）。当栅格节点x的八邻域中有障碍物，且节点x的父节点p经过x到达节点n的代价距离，比父节点p经过任何其他节点到达节点n的代价距离更小，则称n为x的强迫邻居，强迫邻居的筛选规则如式（1）∶
len(<p(x),z,n>)<len(<p(x),...,n>\x)(1)强迫邻居主要包含两种类型，横向强迫邻居如图1（a）所示，在图1（a）中画圈的节点为x的斜向强迫邻居；斜向强迫邻居如图1（b）所示，在图1（b）中画圈的节点为x的横向强迫邻居。
在筛选出强迫邻居的基础上，还需对跳点进行筛选。如果节点x满足下列3个条件之一，则该节点为跳点。
1）节点x是起始点或目标点；
2）节点x至少有一个强迫邻居；
3）在斜向搜索情况下，节点x的水平或垂直方向上有满足1）、2）的节点。
更多详细内容请下载附件查看
已绑定手机
发表于 2022-7-25 14:03
