基于双向A_算法的路径规划问题研究_李云龙.pdf

2023.02ELECTRONICS QUALITY基于双向 A*算法的路径规划问题研究李云龙，梁波，薛新华，张平，管乐阳，魏广伟（中国电子科技集团公司第二十八研究所，江苏 南京210000）摘要：针对我军野外无路网条件下机动作业问题，通过网格法将野外环境进行等效，利用路径规划算法规划最短路径。利用传统的A*算法进行路径规划时，由于算法只从单一方向进行探路，收敛速度较慢，尤其是针对区域面积较大、障碍物环境复杂时运算速度会显著地降低。因此，提出了一种经过改进的双向A*算法，其主要思路为利用起点、终点同时进行寻路，当两侧路径的可到达点出现交叉时即完成寻路。根据仿真结果，验证了双向A*算法能够完成最优路径搜索，相较于传统A*算法，能够有效地提高寻路效率，减少搜索时间。关键词：路径规划；A*算法；双向A*算法；仿真；最优路径中国分类号：TP 301.6文献标识码：A文章编号：1003-0107（2023）02-0001-04doi:10.3969/j.issn.1003-0107.2023.02.001Research on Path Planning Based on Bidirectional A*AlgorithmLI Yunlong，LIANG Bo，XUE Xinhua，ZHANG Ping，GUAN Yueyang，WEI Guangwei（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing 210000，China）Abstract：Aiming at the problem of mobile operation of our army in the field without road network，the field environ-ment is equivalent by grid method，and the shortest path is planned by path planning algorithm.When the traditionalA*algorithm is used for path planning，the convergence speed is slow because the algorithm only explores the pathfrom a single direction，especially when the area is large and the obstacle environment is complex，the operationspeed will be significantly reduced.Therefore，an improved bi-directional A*algorithm is presented.Its main idea isto use the starting point and the end point to find the path at the same time.When the reachable points of the paths onboth sides cross，the path finding is completed.According to the simulation results，it is verified that the bidirectionalA*algorithm can complete the optimal path search，which can effectively improve the path finding efficiency and re-duce the search time compared with the traditional A*algorithm.Keywords：path planning；A*algorithm；bidirectional A*algorithm；simulation；optimal path收稿日期：2022-10-08修回日期：2022-12-07作者简介：李云龙（1989），男，河北保定人，中国电子科技集团公司第二十八研究所工程师，硕士，从事作战任务规划技术研究工作。0引言进行跨区域、远距离、野外环境下（无路网等基础设施）机动作业，是未来我军的常态化需求。合理地规划野外行动路线，确保行程路线合理可行，是我军重要的研究课题。路径规划问题是指在有障碍物的环境下，按照一定的评价标准，找出一条从起点到终点的无碰路最优路径的过程。根据路径规划环境是否随时间变化，将路径规划分为动态规划和静态规划。根据路径规划的目标范围，又可分为全局路径规划和局部路径规划1。Computer Science and Technology计算机科学与技术1ELECTRONICSQUALITYELECTRONICS QUALITY目前，常见的路径规划算法主要包括栅格法2、A*算法3、人工势场法4和动态窗口法5等。本文针对我军面向战术环境下野外路径规划问题6，根据不同区域的地质条件，利用栅格法进行地图区域建模。采用启发式搜索思想7，通过采用双向寻路方法对A*算法进行改进，在保证准确度的前提下，大幅地减少了探索路线，提高了算法的计算效率。1数学模型描述选取包含起点和终点的矩形区域（长为a、宽为b），将区域等分成m行n列的网格，每个网格大小形状均相等。按照网格区域是否可通行作为设置障碍物的标准，例如：当网格为沼泽地、河流时，该网格设置为不可通行的障碍物，使用以下矩阵定义网格是否可通行。A=C11C1nCm1Cmn?（1）Aij=1，该网格可通行0，该网格不可通，行（2）为了方便后续计算，假定每个网格均可以进行上下左右4个方向的移动，如图1所示。当网格划分越密时，该近似与实际结果越接近，但同时会造成计算耗时增加。2基于双向A*算法的路径规划2.1 A*算法A*算法是启发式搜索算法的一种，在静态环境中进行路径规划实验时可满足实时性的要求，从而可迅速高效地求解最优路径单向递进式搜索方式的A*算法通过筛选计算每一步所得到的最优节点，逐步形成最优路径。其表达式为：F（n）=G（n）+H（n）（3）式（3）中：G（n）从起点A移动到指定方格n点的移动代价；H（n）从指定的方格n移动到终点B的估算代价；选择曼哈顿距离8计算H（n）值，H（n）值为估算值，比从n移动到目标点B的实际代价小。Open，Close都是存储节点的集合。H（n）=（nx-Bx）2+（ny-By）2姨（4）a）计算步骤1）初始时，将起点A加入Open点集合，Close点集合为空。2）遍历Open点集合中各点，依次计算F（n），选取其中F（n）值最小的点Ni移除Open点集合，放入Close点集合。3）寻找Ni可到达的其他点，不包括障碍物及Close点集合中的点。4）若该点不在Open点集合中，置入Open点集合中，并且把当前方格设置为它的父节点。5）若该点已经在Open点集合中，计算这条路径（即经由Ni到达它那里）的G值，若G值更小，则把它的父亲设置为当前方格。6）重复步骤2）-5）。b）算法停止条件1）当把终点加入到Open点集合中，此时路径已经找到了。路径由终点B延各点的父节点指向起点A。2）当终点未找到且Open点集合是空，此时没有路径。2.2 双向A*算法传统的A*算法当面临较大的规划场景时，往往由于庞大的计算量导致运行时间过长、内存占用严重。双向A*算法即从起点、终点正反两个方向同时进行计算，同时对可能的路线进行探索收敛，大部分情况下能够有效地减少探索点数及搜寻时间。a）计算步骤1）初始时，将起点A加入OpenStart点集合，CloseStart点集合为空。2）遍历OpenStart点集合中各点，依次计算F（n），选取其中F（n）值最小的点Ni移除Open-Start点集合，放入CloseStart点集合。图1每个方格的4种移动方向22023.02ELECTRONICS QUALITY3）寻找Ni可到达的其他点，不包括障碍物及CloseStart点集合中的点。4）若 该 点 不 在OpenStart点 集 合 中，置 入OpenStart点集合中，并且把当前方格设置为它的父节点。5）若该点已经在OpenStart点集合中，计算这条路径（即经由Ni到达它那里）的G值，若G值更小，则把它的父亲设置为当前方格。6）重复步骤2）-5）。7）同步将B点加入OpenEnd点集合，CloseEnd点集合为空，以同样的步骤计算。b）算法停止条件1）当在第3步中，若Ni可到达的点Ni+1点已在OpenEnd（正向查找）或者OpenStart（反向查找）点集合中出现，此时路径即为由Ni、Ni+1延各自父节点指向A、B点的点集合。2）当条件1未达成时且OpenStart和OpenEnd点集合和是空，A、B两点之间没有可达路径。3仿真验证1）软件开发语言：JAVA、JS、Html。2）浏览器：Chrome。3）编译器：Eclipse。试验路径搜索结果如图2-7所示。其中，左侧标记为起点，右侧标记为终点，黑色标记为不可通过点。灰色标记点为参与计算预期代价的节点。黑色标记线为搜寻路径。为了方便对照，每组试验设置相同的起点、终点和不可通过点。起点终点图2试验1-1路径搜索结果图图3试验1-2路径搜索结果图图4试验2-1路径搜索结果图图5试验2-2路径搜索结果图图6试验3-1路径搜索结果图起点终点起点终点起点终点起点终点Computer Science and Technology计算机科学与技术3ELECTRONICSQUALITYELECTRONICS QUALITY详细试验结果对照如表1所示。根据表1中的数据，进行以下分析。a）搜寻时间采用双向A*算法的搜寻时间小于或等于A*算法，平均节约时间35.3%。b）搜寻路径将试验1-1、试验1-2分别与试验2-1、试验2-2进行对比，发现尽管两种算法所得路线不同，但是路线长度一样，均为最小路径。4结论通过上述分析，得到了以下两点结论：a）根据试验中所搜索到的路径长度，双向A*算法与A*算法均能实现最优路径搜索；b）根据试验中搜索路径所用时间，双向A*算法相比于A*算法计算时间有明显的减少，可以有效地提高路径搜索效率。5结束语文中对当前路径规划中常见算法进行了简介，并利用栅格法对存在障碍物条件下的野外路径规划进行了数学建模。同时详细地介绍了A*算法及其改进优化后的双向A*算法的原理，并对其进行了建模仿真。根据仿真结果，最终确定了双向A*算法和A*算法均可搜寻到最短路径，但双向A*算法的搜寻时间明显地缩短。参考文献：1皇甫淑云，唐守锋，童紫原，等.自主移动机器人路径规划方法研究综述J.软件导刊，2018，17（10）：1-5.2魏宁，刘一松.基于栅格模型的移动机器人全局路径规划研究J.微计算机信息，2008（11）：229-231.3周宇杭，王文明，李泽彬，等.基于A星算法的移动机器 人 路 径 规 划 应 用 研 究 J.电 脑 知 识 与 技 术，2020，16（13）：1-3；10.4王迪，李彩虹，郭娜，等.基于人工势场法的移动机器人局部路径规划J.山东理工大学学报（自然科学版），2021，35（1）：21-26；32.5高宇，赵嵩郢.基于动态窗口法的无人艇局部路径规划J.船电技术，2022，42（7）：50-54.6罗钦瀚，李荣宽，邵玮炜，等.面向战术环境的智能路径规划设计J.指挥信息系统与技术，2018，9（6）：49-54.7蒋帅，周永坤，王涛.启发式搜索思想在路径规划中的应用J.指挥信息系统与技术，2021，12（4）：57-63.8谢晖，张达奇，冯李.结合曼哈顿距离的A-star算法在光缆寻址中的应用J.信息通信，2019（1）：34-36.表1试验结果对照表试验序号算法路线长度搜索时间/ms节约时间/%平