基于改进A%5E%28＊%29与改进DWA的组合路径规划算法.pdf

计 算 机 与 网 络技术论坛基于改进A*与改进DWA的组合路径规划算法原忠虎，王豪杰（沈阳大学 信息工程学院，辽宁 沈阳110044）摘要：在地面移动机器人路径规划算法中，针对传统A*算法存在的边缘摩擦、边缘碰撞和路径不平滑等问题，采用改进的A*算法，即引入势力场对其进行处理，再采用三阶曲线平滑路径，通过仿真实验验证，改进后的A*算法路径更平滑、路径更短，明显改善了边缘摩擦或碰撞的问题。针对传统的DWA算法容易陷入局部最优的问题，通过引入曲率约束评价函数对算法改进，并且经过仿真实验，改进后的DWA算法明显得到了改善，而且规划的路径更加平滑，也避免出现陷入局部最优解的情况。提出改进A*与改进DWA的组合路径规划算法，实现机器人的自主导航。关键词：移动机器人；路径规划；A*算法；DWA算法；三阶Bezier曲线中图分类号：TP391.4文献标志码：A文章编号：1008-1739（2023）15-67-6YUAN Zhonghu,WANG Haojie(College of Information Engineering,Shenyang University,Shenyang 110044,China)In the path planning algorithm of the ground mobile robot,in order to solve the problems of the edge friction,the edgecollision and the path unsmoothness of the traditional A*algorithm,the improved A*algorithm is adopted,that is,the force field isintroduced to deal with it,and the third order Bezier curve is adopted to smooth the path.The simulation experiment verifies that theimproved A*algorithm has smoother and shorter paths,significantly improving the edge friction or the collision problems.For theproblem that the traditional DWA algorithm is easy to suffer from the local optimal solution,the curvature constraint evaluationfunction is introduced to improve the algorithm.After the simulation experiment,the improved DWA algorithm is obviously improved,and the planned path is smoother,avoiding suffering from the local optimal solution.Finally,the combined path planning algorithmbased on the improved A*and the improved DWA is proposed to realize the autonomous navigation of the robot.mobile robot;path planning;A*algorithm;DWA algorithm;third order Bezier curve收稿日期：2023-04-020引言路径规划是移动机器人领域中的一个重要内容，该技术是指移动机器人按照某一性能指标（如距离、时间等）搜索一条从起始状态到目标状态的最优或次优路径1。Dijkstra提出一种基于广度优先搜索（Breadth First Search,BFS)的Dijkstra路径搜索算法，该算法可以规划出最短路径，但是需要遍历很多节点，搜索时间很长，在实际应用时的效果不理想。Rachmawati等2提出了启发式搜索路径算法的A*算法，该算法是在Dijkstra算法上的改进，使搜索的节点明显减少，效率也显著提高。Fox等3提出了一种灵活性很高的动态窗口法（Dynamic Window Approach,DWA），该算法被广泛应用于机器人局部路径规划。至今，大部分机器人利用该算法在导航中，根据探索的本体速度和加速度的方法寻找到一条最优路径，实现局部避障。67计 算 机 与 网 络技术论坛1传统路径规划算法1.1 A*算法A*算法或许是运动规划中最著名的算法。其中的新要素是：一个新的关键值。由于引入了离开代价函数，A*算法与Dijkstra算法相比，效率更高、访问的状态更少。在图论和人工智能（AI）专业术语中，图结构的状态通常被泛称为节点4。在A*算法中，每一个节点存储三个值，分别称为、和，代价估计计算如下：，（1）式中：与Dijkstra算法中一样，是精确的、已知的、最优的接近代价，是从状态上到目标状态的离开代价估计，是从初始状态经由状态到达目标状态的总路径代价估计（基于计算得到）。在A*算法中，优先级队列根据而不是来排序。这种变化使得算法在搜索到目标之前，总是按照最低总代价估计的顺序来探索路径。A*算法流程如图1所示。图1 A*算法流程1.2 DWA算法DWA作为局部路径规划的算法之一，在机器人自主导航领域得到了广泛应用，该算法对机器人速度进行采样，并且依据采样的速度信息模拟出其运动轨迹，通过评价函数对各分组速度进行打分，选取最高分数的函数用来控制运动5。首先将机器人运动学模型离散化，然后对机器人在速度约束中添加极限速度约束、动力学性能约束和安全距离约束。（1）极限速度约束由于机器人自身的机械结构和性能的限制，应该对采样空间进行限制，设为极限速度约束，则具体可表示为：，（2）式中：min、max表示线速度最值，min、max表示角速度最值。（2）动力学性能约束机器人在移动过程中，电机加速减速时会存在限制，设d对机器人加速度限制，则d具体可表示为：，（3）式中：c、c表示当前线速度和角速度，、表示最大的线加速度和角加速度。（3）安全距离约束为了避免机器人在运动中与障碍物发生碰撞，需要对制动距离要设置限制，设机器人安全距离约束为a，则a具体可以表示为：，（4）式中：min(,)表示轨迹(,)和最近障碍物的距离。令r表示整体速度空间，并且r为以上速度空间的交集，则可以表示为：。（5）在得到以上速度空间约束后，把采样速度限制在一个范围内，则DWA算法的评价函数具体如下：，（6）式中：(,)表示目标方位角函数，该函数是以(,)运动后的轨迹后端，机器人的正方向和目标方向之间的夹角表示为180-，(,)表示运动轨迹后端和障碍物之间的距离，其目的是使机器人可以远离障碍物，(,)表示这一组采样的线速度大小，其目的是使机器人可以尽快运动至目标位置，、分别表示3个评价函数的系数，可以动态调节。2基于三阶Bezier曲线平滑改进A*算法传统的A*算法存在一些问题，比如边缘摩擦、边缘碰撞、路径不平滑等6，针对边缘摩擦和碰撞的问题，引入势力场对其进行处理，即当机器人运动至障碍物临近的地方时，产生斥力惩罚，使得机器人偏离这个地方，避免产生边缘碰撞的情况，待机器人移动至安全范围之后会继续运动。针对路径不平滑这一问题，采用三阶Bezier曲线平滑改进A*算法产生的路径，减.68计 算 机 与 网 络技术论坛少规划的路径长度，增加了机器人运动过程的平滑性。（1）边缘摩擦和碰撞的问题优化首先要确定障碍物的作用范围，通过在图问题上来确定机器人是否与障碍物相交，从而判断机器人在运动过程中是否处于安全状态。因此，采用圆形包围盒算法对障碍物作用范围进行求解。该算法的原理是将物体用圆形包围盒进行覆盖，然后判断2个圆形包装盒之间有无碰撞，从而判断物体之前有无发生碰撞。设圆的坐标为(1,1)，其半径为1，圆的坐标为(2,2)，其半径为2。如果满足式（7），说明和之间圆心的距离小于半径之和，就会发生碰撞；反之则说明没有发生碰撞。(2-1)2+(2-1)2(2-1)2。（7）本文采用占据栅格法进行建模，障碍物占据的最小范围是一个栅格，并且在仿真实验中将机器人同样视为一个栅格，所以障碍物作用范围如图2所示。图2障碍物作用范围示意每一个栅格在坐标系中代表一个单位，障碍物和机器人之间的安全距离应满足：1+21.5（栅格）。（8）因此，1.5个栅格栅格，障碍物没有斥力作用。确定障碍物的作用范围后，引入惩罚机制，在机器人和障碍物二者的坐标中心距离小于障碍物的作用范围时，产生斥力惩罚，可以有效避免机器人发生碰撞的问题。其中，斥力惩罚函数可以表示为：。（9）式中：表示斥力增益，min表示节点至障碍物的距离，表示障碍物作用范围。将斥力惩罚函数与A*算法的目标函数融合之后可以表示为：(,)=(,)+(,)+()。（10）（2）基于三阶Bezier曲线的路径平滑处理Bezier曲线是一种利用数学原理计算曲线路径的方法，已经广泛应用于工业设计和一些制图软件中，其原理是根据4个任意点的位置坐标绘制一条平滑曲线，具体计算如下：，（11）式中：0、1、2、3为三阶Bezier曲线上的4个点，0、3为2个端点，为路径原始数据，1、2为2个控制点，根据式（11）可以计算出0与3之间曲线上的任意点。三阶Bezier曲线如图3所示。图3三阶Bezier曲线将路径平滑问题转化为寻找原始路径中的控制点问题，具体步骤如下：生成原始路径中点集合，如图4所示，其中、表示原始数据，也就是运动路径上的4个点坐标。图4计算中点集合则1、2、3、4的坐标可以通过已知的原始数据的坐标求出，因此中点集合的坐标可以表示为：，（12）式中：、表示第 个路径点坐标。确定中点连接线和分割点，如图5所示，通过相邻路径长度的比值，对中点连接线进行分割，设分割点为点，即/=A B/A B。图5计算分割点B1269计 算 机 与 网 络技术论坛由式（12）可以分别得出点1、2的坐标，为(,)和(,)，因此可以求出点的坐标为：，（13）式中：。对中点连接线进行平移，使得各中点连接线的分割点和原始坐标点重合，如图6所示。图6平移分割点调整中点连接线端点和原始点距离，缩减量为，得到控制点集合，如图7所示。图7确定控制点集合设当前顶点的坐标为(,)，并且通过以上步骤已确定了集合和集合，则点 的坐标可以表示为：，（14）中点线平移偏移量为：。（15）设平移之后的蓝色线段的起点坐标为，终点坐标为，具体可以表示为：最终可以推导出控制点坐标为：。（17）确定三阶Bezier曲线的控制点后，根据式（11）可以得出曲线上的全部点，并画出Bezier曲线。3基于改进DWA算法的局部路径规划考虑到履带机器人在转向时比较不灵活，所以在巡检的整个过程中要保证路径相对平滑，转弯次数要尽量少7，针对这一情况，对DWA算法中的评价函数进行改进，在评价函数中引入曲率，即=/，由此可以得到曲率和角速度为正相关，曲率约束具体表示为：=|-last|，（18）式中：表示在当前时刻轨迹末端的曲率，last表示在上一时刻最优轨迹的曲率。在构建评价函数时，需要将全部因子归一化处理，避免其中的某因素对整个轨迹造成较大的影响，使得最终的评价结果更加准确，具体如下：，（19）式中：为轨迹方向角，为轨迹和障碍物之间的距离，为轨迹的速度，|i-last|为曲率约束值。综上所述，评价函数改进之后具体表示为：，（20）4组合路径规划在实际环境中，不仅有静态障碍物，动态障碍物也是不可忽略的，单独依靠全局路径规划是不行的，往往需要和局部路径规划相结合，最终的效果才最佳。全局路径规划是在已知的静态环境中规划出来的一条路径，如果突然出现动态障碍物时，不能对其进行避障，机器人会与动态障碍物相撞，发生危险。因此，需要局部路径规划应对突然出现的动态障碍物，进而躲避动态障碍物。本文采用基于改进A*算法的全局路径规划和基于改进DWA算法的局部路径规划相组合的方式，实现机器人的导航功能。组合路径规划的具体流程如图8所示。2112。（16）70计 算 机 与 网 络技术论坛图8组合路径规划算法流程具体实现步骤如下：机器人通过传感器采集周围信息，并构建全局环境地图。导入环境地图后，确定机器人当前位置和设定的目标点位置，根据改进A*算法规划一条全局路径。在机器人行进过程中，若没有遇到未知障碍物，则按照全局路径移至目标位置。当机器人遇到未知障碍物时，标记当前障碍物下的全局路径点作子目标点，并通过改进DWA算法进行局部路径规划，实现躲避障碍物。如果没有规划成功，则继续选择子目标点。如果到达子目标点，机器人继续沿着原始全局路径运动。机器人到达目的地，结束规划。5仿真与分析5.1改进A*算法仿真与分析首先，通过仿真比较了A*算法和Dijkstra算法，在相同的环境下，起始点和目标点的位置一致，环境地图为138113的栅格地图，黑色代表障碍物，绿色线为算法规划的路径，蓝色区域表示规划路径过程中遍历的节点，仿真对比结果如图9所示。（a）Dijkstra算法仿真结果（b）A*算法仿真结果图9 Dijkstra算法与A*算法仿真结果比较具体比较结果如表1所示。表1 Dijkstra算法与A*算法实验数据由表1可以看出，A*算法比Dijkstra算法的效果好，路径长度减少了15.29%，遍历的节点数量和计算所需的时间也明显减少。虽然A*算法和Dijkstra算法相比要好一些，但是通过A*算法搜索出的路径转折点比较多，且存在边缘摩擦或碰撞的问题，所以对A*算法进行了改进，A*算法改进前后的比较如图10所示。可以看出，改进后的A*算法得到了明显改善。图10 A*算法与改进A*算法仿真结果比较具体比较如表2所示。表2 A*算法与改进A*算法实验数据5.2改进DWA算法仿真与分析通过Matlab仿真软件比较改进前后的DWA算法，传统DWA算法在一些环境比较复杂或者障碍物相对繁多的情况下，路径规划与避障的效果不太理想。通过对传统算法的改进，71计 算 机 与 网 络技术论坛改进后的DWA算法得到了明显改善，规划的路径更加平滑，并且避免了陷入局部最优解的问题。如图11所示，图中包括2个不同环境的局部路径规划，分别是图11（a）、图11（b）和图11（c）、图11（d）。在局部路径规划仿真中设置的基本参数如表3所示。图11 DWA算法与改进DWA算法比较表3算法仿真基本参数设置6结束语通过传统A*算法搜索出的路径转折点比较多，且存在边缘摩擦或碰撞的问题，改进后的A*算法路径转折点减少，路径更平滑，规划的路径更短，明显改善了边缘摩擦或碰撞的问题。传统的DWA算法在规划中出现“绕路”的状况，规划的路径比较长，改进后的DWA算法规划出的路径未出现“绕路”且更短。传统的DWA陷入局部极值，出现了“死锁”情况，致使无法到达最终的目标点，改进后的DWA可以避免这种情况的发生，并且规划出的轨迹更平滑。最后，将改进A*与改进DWA进行组合，可以实现机器人稳定、平滑的自主导航功能。参考文献1 HUANG Q.Research on Path Planning of Mobile RobotBased on Particle AlgorithmJ.International Core Journal ofEngineering,2021,7:423-431.2 RACHMAWATI D,GUSTIN L.ANALYSIS of DijkstrasAlgorithm and A*Algorithm in Shortest Path ProblemJ.Journal of Physics:Conference Series.2020,1566:012061.3 FOX D,BURGARD W,THRUN S.The Dynamic WindowApproach to Collision AvoidanceJ.IEEE Robotics&Automation Magazine,1997,4(l):23-33.4 MAC T T,COPOT C,TRAN D T,et al.Heuristic Approachesin Robot Path Planning:A SurveyJ.Robotics andAutonomous Systems,2016,86(C):13-28.5 YANG X Z.Slam and Navigation of Indoor Robot Based onROS and LidarJJournal of Physics:Conference Series,2021,1748:022038.6 SUGIANTI N,MARDHIYAH A,FADILAH N R.KomparasiKinerja Algoritma BFS,Dijkstra,Greedy BFS,Dan A*DalamMelakukan PathfindingJ.Jurnal Informatika SunanKalijaga,2020,5(3):194-204.7 CHEH L,SHI C L,Hu H,et al.Research on Navigation andLocation System of Inspection Robot for Urban Utility TunnelC/2020 4th International Conference on Robotics andAutomation Sciences(ICRAS).Wuhan:IEEE,2020:11-14.欢迎订阅2023年下半年计算机与网络期刊刊号:CN 13-1223/TN，邮发代号：18-210。计算机与网络 期刊坚持立足IT业，面向多层次人员，着眼实用和为决策层提供重要技术信息；以信息网络为中心，计算机与通信相结合；新技术、新产品、新应用与市场信息相结合；普及与提高相结合。本刊重点设置“电子商务、业界动态、动漫、硬件世界、软件天地、网事、防火墙、市场透析、技术论坛”等栏目，信息含量丰富，技术性、实用性、可读性完美结合，具有报道及时、周期快、发行量大等鲜明特色，深受广大读者欢迎。联系电话：[phone]投稿：或广告72