基于改进动态窗口法的机器人路径规划

2023-12-04邹文韩丙辰

北京联合大学学报 2023年6期

邹文韩丙辰

[摘要] 针对传统动态窗口法安全性低、规划范围有限等问题，提出一种联合动态窗口法和A*算法的路径规划方法。该方法首先根据路径前方障碍物种类的不同，在代价地图中投影不同的空间模型；然后在动态窗口法的评价函数中引入距离评价子函数，使机器人能对不同类别的障碍物保持不同的避让距离；最后融合A*算法，提供全局路径指引。对比实验表明，与传统算法相比，改进算法拥有全局规划能力，并且提升了机器人路径规划的安全性。

[关键词]移动机器人；路径规划；安全性；空间模型

[中图分类号]TP 242

[文献标志码]A

[文章编号]1005-0310（2023）06-0067-06

Robot Path Planning Based on Improved Dynamic

Window Approach

ZOU Wen，HAN Bingchen

（1.College of Electronic Engineering， Sichuan Vocational and Technical College， Suining Sichuan 629000， China;

2.Department of Physics， Taiyuan Normal University， Jinzhong Shanxi 030619， China）

Abstract： A path planning method combining dynamic window method and A* algorithm is proposed to address the issues of low security and limited planning scope of traditional dynamic window method. This method first projects different spatial models in the cost map based on the types of obstacles in front of the path， and then introduces a distance term subfunction in the evaluation function of the dynamic window method， allowing the robot to maintain different avoidance distances for non-classified obstacles. Finally， it integrates the A* algorithm to provide global path guidance. Comparative experiments show that compared with traditional algorithms， the improved algorithm has global planning ability and improves the safety of robot path planning.

Keywords： Mobile robot；Path planning；Safety performance；Space model

0 引言

随着机器人技术的飞速发展，越来越多的机器人进入社会生产生活中。路径规划是实现机器人自主导航的重要组成部分，可分为全局静态路径规划和局部动态路径规划。其中，动态规划是指机器人在运动时，依靠自身传感器检测到环境中出现的未知障碍物，使用路径规划算法实现合理、安全地避开障碍物并到达目标位置的过程。

动态窗口法（Dynamic Window Approach， DWA）是常用的机器人局部规划算法，它既能有效避开路径中出现的未知障碍物，又能提升路径的平滑度。传统的DWA算法对所有障碍物的避让距离相同，规划范围有限，容易陷入地图陷阱，无法满足多种场景的局部动态规划需求，因此，移动机器人局部规划算法的改进成为当前的研究热点之一。王永雄等提出自适应动态窗口法，根据障碍物的距离和密度自动调整机器人的最大速度限制，从而获得最佳运行速度组和最优路径。封硕等在动态窗口法评价函数中增加了动态障碍物速度的评价函数，从而避开高速移动的障碍物。张森等通过对人的紧张空间和机器人的运动趋势进行建模，进而优化人在机器人运动过程中的舒适感受。王洪斌等用预瞄偏差角算法追踪动态目标，得到动态障碍物的位置信息及运动趋势，进而提升路径规划效率。宋莉等对Q-Learning（QL）算法进行离散化处理及降低状态空间维度，并在奖惩函数上增加了ε-探索和动作选择算法来选择执行速度组，增强了机器人在复杂情况下的适应能力。邹文等通过增加动态窗口法的运动状态，提高了機器人的灵活性。文献[9]～[11]均将不同程度改进的A*算法与动态窗口法融合，既能做到全局不丢失路径，又能避让运动过程中遇到的未知物体。

1 环境空间模型

机器人在路径规划前，需要根据环境信息建立环境模型地图。机器人根据传感器采集到的信息，将障碍物的种类和空间位置投影在二维地图模型中，并根据代价地图来完成规划和移动。

1.1 环境描述

环境模型地图可分为全局静态地图和局部动态模型地图。全局静态地图用来表示在机器人整个运动环境中相对固定不变的物体，如墙体、家具等。本文将全局环境投影在连续紧凑的二维栅格平面中，构建全局静态环境模型。每个栅格以概率形式表示是否被固定障碍物占据，黑色栅格表示占据状态，白色栅格表示空闲状态，如图1所示。

1.2 障碍物空间模型

机器人在运动过程中，除相对固定不变的静态障碍物外，往往还会遇到位置改变的静态障碍物和移动的未知障碍物。本文按照物体自身能否移动将障碍物分为静态障碍物和动态障碍物两种。其中，将自身不会发生移动的物体（如墙体、家具、植物等）定义为静态障碍物，将自身会发生移动的人和动物等定义为动态障碍物，分别赋予其不同的安全范围值。本文基于障碍物的特性和种类建立空间模型，来描述障碍物的安全范围空间和舒适范围空间。

静态障碍物和动态障碍物安全区域的半径大小不同，对于动态障碍物，除安全区域外，本文还在其外添加了一层舒适区域。其中，安全区域表示机器人禁止进入的区域，舒适区域表示机器人可以进入的区域，但进入舒适区域后机器人会减速并优先选择远离障碍物的模拟轨迹。图2（a）为传统方法对障碍物的膨胀模型，图2（b）是本文提出的膨胀模型，图2（b）中左边为动态障碍物，右边为静态障碍物。

1.3 障碍物分类检测

本文使用Yolov3算法来识别机器人在移动过程中遇到的障碍物。机器人首先识别出障碍物，然后对物体进行静态或动态分类，最后将障碍物对应的空间模型投影在代价地图中，并在代价地图中对障碍物进行扩展。机器人使用搭载的摄像头对环境中物体的识别效果如图3所示。

2 改进动态窗口法

2.1 传统动态窗口法

动态窗口法主要通过采样多个速度组（线速度、角速度），并模拟它们在预测时间范围内的轨迹，把机器人与障碍物碰撞的轨迹删掉，最后通过评价函数选取出最优的速度组。

假定在一个最小单位时间间隔内，机器人做匀速直线运动。线速度v和角速度ω反映机器人的运动状态，其运动模型可用式（1）表示：

在速度空间（v，ω）范围内存在无数个速度组，需要根据实际情况对采样速度进行限制。速度组约束如式（2）所示：

因加速度受机器人自身电机的性能约束，在一个时间间隔内，实际能到达的速度组如式（3）所示：

式中：（vc，ωc）代表当前速度组，（va，ωa）代表机器人的最大加速度组，（vb，ωb）代表机器人的最大减速度组。

在采样并模拟的各条轨迹中，除机器人与障碍物发生碰撞的轨迹之外，还有很多可行的模拟轨迹，最后通过评价函数来筛选出最优的模拟轨迹。评价函数如式（4）所示：

式中：G为方位角评价子函数，表示模拟速度组在轨迹末端时的朝向与目标位置航向角之间的角度偏差；G为障碍物评价子函数，表示模拟轨迹与障碍物之间最近的距离；G为速度评价子函数，表示模拟轨迹对应的速度大小；σ为平滑系数，α、β、γ为各个子函数的加权系数。

2.2 扩展评价函数

动态窗口法的评价函数结构清晰，扩展性强。本文在此评价函数的基础上增加了距离评价子函数G，取值范围为[0，1]，其计算方法如式（5）所示：

式中：d代表采样速度组模拟轨迹与障碍物之间的最小距离，取值范围为（r，r）；r表示各类障碍物的禁止区域半径；r表示各类障碍物的舒适区域半径。优化后的评价函数如式（6）所示：

式中，δ为距离评价子函数的加权系数。

改进算法对障碍物空间模型的模拟轨迹示意图如图4所示。

图4中：轨迹①和轨迹②进入安全范围内，所以将其剔除；轨迹③和轨迹④在舒适范围内且在安全范围外，距离评价子函数的得分按式（5）求得，越靠近障碍物中心的模拟轨迹，其得分越低；轨迹⑤和轨迹⑥在舒适范围以外，距离评价子函数的得分均为1。

2.3 融合A*算法

由于动态窗口法仅向前模拟一定时间内的轨迹，所以其规划的路径范围有限，很容易陷入“L”型、“凹”型等陷阱中。如图5中绿色虚线所示，由于DWA算法规划的范围有限，机器人会从①处运动到②处，进入地图陷阱中，而最优路径应该是与图5中红色实线类似的路径。

本文在机器人局部路径规划前融合全局规划算法（A*算法）。首先，将A*算法规划的路径点提取出来，然后将该路径点中多余的转折点删除，留下各阶段的关键点，再将各个关键点作为局部规划的临时目标点，指引机器人到达最终的目标位置。融合A*算法使机器人得到全局路径的指引，从而避免陷入局部路径陷阱中。

3 实验及分析

为了验证本文改进动态窗口法的性能及合理性，在Matlab 2021b下进行仿真实验，并设置了障碍物环境进行导航实验，同时对各实验结果进行分析。

3.1 仿真实验

仿真實验分别用A*算法、改进的DWA算法、融合A*的传统DWA算法、融合A*的改进DWA算法，在相同环境下进行。各算法规划出的路径如图6所示，避让距离统计如表1和图7所示。

由图6（a）可知，A*算法规划出的路径转折角度大，离障碍物的距离约为0.5个单位栅格。由图6（b）可知，未融合A*算法的改进DWA算法的规划范围有限，容易陷入局部路径陷阱中，此时路径规划失败。由图6（c）和图6（d）可知，融合A*的DWA算法能到达终点。

对比图6（c）和图6（d），并联合表1和图7可知，融合A*的传统DWA算法与所有障碍物的避让距离均为1个单位栅格，而融合A*的改进DWA算法与动态障碍物的避让距离为1.5个单位栅格，与静态障碍物的避让距离为1个单位栅格。由此可知，传统算法对所有障碍物只能保持相同的安全距离，融合A*算法的改进DWA算法对动态障碍物、静态障碍物能有针对性地选择不同的避让距离。改进算法不仅提升了路径规划的安全性，也扩大了路径规划的范围。

3.2 自主导航实验

为验证本文的改进算法在机器人路径规划中的实用性，本文在如图8所示的环境中进行自主导航实验。本实验用Gmapping算法构建栅格代价地图后，在环境中设置“凹”型陷阱，并添加其他障碍物。机器人自主导航的移动路径如图9所示。

图9表明，机器人能提前规划全局路径，避开“凹”型陷阱，并且其对动态障碍物（人）的避让距离大于静态障碍物，证明了改进算法在实际应用中的可行性。

4 结束语

机器人与障碍物的合理避让距离是路径规划时应考虑的重要安全性因素。针对传统动态窗口法对所有障碍物采取相同避让距离的问题，本文通过构建不同障碍物空间模型和扩展评价函数来改进动态窗口法；针对动态窗口法规划范围有限的问题，本文融合A*算法为机器人提供全局指引。仿真對比实验和自主导航实验表明，融合改进算法能让机器人根据环境中各类物体的运动特性合理规划出不同的安全避让距离，而且不会落入地图陷阱。相比传统算法，改进算法能让机器人的移动过程更安全、更合理。

[参考文献]

[1]SARIFF N， BUNIYAMIN N. An overview of autonomous mobile robot path planning algorithms[C]//4th Student Conference on Research and Development. Piscataway， USA： IEEE，2007： 182-187.

[2]何玉庆，赵忆文，韩建达，等.与人共融——机器人技术发展的新趋势[J].机器人产业，2015（5）：74-80.

[3]王永雄，田永永，李璇，等.穿越稠密障碍物的自适应动态窗口法[J].控制与决策，2019，34（5）：927-936.

[4]封硕，吉现友，程博，等.融合动态障碍物运动信息的路径规划算法[J].计算机工程与应用，2022，58（21）：279-285.

[5]张森，刘景泰.基于多维度服务情景的人的舒适需求建模[J].机器人，2019，41（4）：493-506.

[6]王洪斌，尹鹏衡，郑维，等.基于改进的A*算法与动态窗口法的移动机器人路径规划[J].机器人，2020，42（3）：346-353.

[7]宋莉，李彩虹，王小宇，等.移动机器人局部避障路径规划仿真研究[J].计算机仿真，2018，35（7）：279-284.

[8]邹文，韩丙辰，李鹏飞，等.融合改进A*算法和优化动态窗口法的路径规划[J/OL].计算机集成制造系统.（2022-04-12）[2022-10-11].http：//kns.cnki.net/kcms/detail/11.5946.TP.20220409.1931.002.html.

[9]刘建娟，薛礼啟，张会娟，等.融合改进A*与DWA算法的机器人动态路径规划[J].计算机工程与应用，2021，57（15）：73-81.

[10]槐创锋，郭龙，贾雪艳，等.改进A*算法与动态窗口法的机器人动态路径规划[J].计算机工程与应用，2021，57（8）：244-248.

[11]赵伟，吴子英.双层优化A*算法与动态窗口法的动态路径规划[J].计算机工程与应用，2021，57（22）：295-303.

[12]LIU Y J，ZHAO C S，WEI Y L.A particle PHD filter for dynamic grid map building towards indoor environment[J].Applied Sciences，2021，11（15）：6891.

[13]阮晓钢，张家辉，黄静，等.一种结合内在动机理论的移动机器人环境认知模型[J].控制与决策，2021，36（9）：2211-2217.