文|大核有料
编辑|大核有料
移动机器人是一种自主移动的机器设备，能够在很多环境中执行任务，如工厂、仓库、医院、办公室等。
路径规划是移动机器人实现导航和避障的关键问题，其目的在于在未知或已知环境内，找到机器人从起点到终点尽可能最短、最安全、最平滑路径，并避开障碍物。
移动机器人在已知所有环境信息的地图中搜寻最优路径称为全局路径规划，常见的全局路径规划算法主要有基于搜索的Dijkstra和A*算法和D*算法、基于概率的快速扩展随机树（rapidly-exploringrandomtree，RRT）算法以及基于智能算法的遗传算法、蚁群算法、粒子群算法等。
在已知部分环境信息或全部未知的情况下搜寻最优路径称为局部路径规划，常见的局部路径规划算法有时间弹性带（timeelasticband，TEB）算法、人工势场法和动态窗口法（dynamicwindowapproach，DWA）等。
动态窗口法根据自身的物理约束和环境约束进行速度采样生成速度窗口，然后利用子评价函数对这些速度组合生成的模拟轨迹进行评价，筛选出最优速度组合作为机器人下一次的运动状态，较其他算法不但全面考虑了机器人的自身约束和环境约束，而且更具实时性。
然而在障碍物密集的复杂环境中，传统的DWA算法由于其固定的权重系数，易出现路径规划不合理或避障失败等问题。
为了能使DWA算法能够更加适应环境信息，并且规划出较优路径，需要对算法进行多方面的改进。
提出了基于带精英策略的非支配排序遗传算法（non-dominatedsortinggeneticalgorithm-II，NSGA-II）的改进DWA算法。
改进算法利用多目标优化的思想，在评价函数的基础上设计了以评价函数和速度函数为目标函数、以权重系数为自变量、权重系数取值为约束条件的多目标优化问题的数学模型，并利用NSGA-II算法对其进行求解，获得权重系数最优组合，实现权重系数的自适应变化。
改进后的算法不仅能识别障碍物密集区域并能确保移动机器人能安全有效地通过障碍物密集区，而且提高了算法的环境适应能力。
«——【·传统算法简述·】——»
传统DWA算法：动态窗口法的基本过程是在一定的约束下在速度空间(v，)中采样多组速度，并模拟移动机器人在这多组速度下运行一定时间的轨迹，然后利用评价函数对这些轨迹进行评价，选取一条最优轨迹并利用最优轨迹对应的速度来驱动移动机器人运动。
移动机器人的完整轨迹是由n个采样间隔的n条小轨迹组成的，假设移动机器人的采样间隔为Δt，则运动模型为
理论上速度空间中存在无穷多组线速度v和角速度ω，但在实际环境下移动机器人可达到的速度会受到本身硬件性能及环境的限制，因此需要根据此对采样速度的范围进行以下约束：
由移动机器人运动学分析可知，机器人自身存在最大速度和最小速度的限制，因此采样的速度被约束在以下范围：
移动机器人电机的功率限制了机器人在一个采样时间内的最大速度和最小速度，由于电机性能影响采样速度应该被约束在以下范围：
为保证移动机器人能安全地避开障碍物，需要机器人在与障碍物发生碰撞之前将速度降至0，因此在最大减速度条件下采样速度应该被约束在以下范围：
综上所述，最终速度采样约束Vr为：
在所有约束条件下采样的速度空间中含有若干条可行的模拟轨迹，因此需要评价函数来对这些可行轨迹进行筛选以得到最优轨迹，实现路径规划。评价函数为
NSGA-II算法：在实际问题中往往具有多个目标需要同时满足，并且这些目标又大多是相互冲突的，这种问题被称为多目标优化问题。
通过多目标优化，可以使多个目标在给定区域内尽可能多地达到最优解，这些最优解通常是由多个Pareto最优解组成的，而这些最优解的集合被称为Pareto前沿。
多目标优化问题的数学模型描述为：
NSGA-II算法的流程图如图1所示。
«——【·改进的DWA算法·】——»
传统DWA算法存在的问题：传统的DWA算法虽然能够在简单障碍物环境中实现实时有效的路径规划，但是由于其评价函数G(v，ω)=σ[α·H(v，ω)+β·D(v，ω)+γ·V(v，ω)]中的权重系数α、β、γ采用固定的组合，在障碍物密集的复杂环境中进行路径规划时就时常会出现路径规划不合理的情况。
下面采用控制变量法用两组对比仿真实验演示传统DWA算法中存在的几种问题。
首先，将权重β和γ值固定，仅调节指向目标点权值α的大小，对比仿真实验结果如图2所示。
当α=0.1时，移动机器人绕过障碍物密集区域，并且在目标点周围绕行没有成功到达目标点。
没有到达目标点的原因是指向目标点的权值较低，方位角评价函数指导性不足。
当α=0.8时，移动机器人前进过程中被障碍物阻挡且无法避开障碍物。无法避开障碍物的原因是指向目标点的权值较高，方位角评价函数指导性过大，导致探索失败。
其次，将权重α和γ值固定，仅调节避障权重β的大小，对比仿真实验结果如图3所示，并将路径长度、运行时间、安全距离的具体实验数据列于图3中。
当β=0.1时，在运行过程中会出现移动机器人距离障碍物较近的情况；当β=0.8时，虽然安全距离提高了，但是运行时间增加了4.817秒，运行效率明显下降。
障碍物密集区域检测：在实际应用中移动机器人可以通过自身携带的雷达等传感器来获取环境信息。
但是通常情况下，由于这些传感器的局限性，只能检测到有限范围，但是传统DWA算法忽略了传感器的这种局限性，因此设计了一个基于移动机器人传感器的视野域来表示传感器的检测范围，使算法更加符合实际环境，使路径规划的更加合理。
视野域如图4所示。
同时在此基础上设计了一个表示视野域内障碍物稠密度的函数如式（8）所示：
设稠密度阈值为1，定义稠密度函数I(n，d)≥1时移动机器人进入障碍物密集区域。当障碍物分布如图4所示时，稠密度函数的值为1.260，所以判断此时移动机器人进入障碍物密集区域。
改进NSGA-II算法：为了避免NSGA-II算法陷入局部最优、且能更好地利用优秀解，提出了一种自适应调整交叉、变异概率的方法来提高算法的性能。用以下公式来更新交叉和变异概率：
这样随着迭代次数的增加，交叉概率会增加而变异概率会降低，这样就保证了算法在前期能够更好地探索搜索空间，并且在后期会更好地利用已知的优秀解。
基于改进NSGA-II的DWA算法：通过引入改进的NSGA-II算法，可以获取DWA算法评价子函数最优的权重系数组合，从而有效地兼顾航向、安全、速度等多方面的需求，并且可以根据环境信息自动调节各个权重值，从而达到既合理又安全的目的。
以DWA算法的评价函数、速度评价函数以及DWA算法中评价函数的具体要求为基础，构建如式（10）所示的目标函数和如式（11）所示的不等式约束。
建立好多目标优化数学模型后，利用改进的NSGA-II算法对该多目标优化问题进行求解，可以得到帕累托最优解集(α*，β*，γ*)以及对应的帕累托前沿(fG*，fV*)，这样就可以获得一组新的轨迹空间，再从优化后的轨迹空间中选择评价函数得分高且速度低的轨迹，最后由移动机器人运动模型获得下一时刻的位置，以此循环直到移动机器人到达目标点。
经此改进，DWA算法就可以通过改进的NSGA-II算法在不同的环境中计算出权重系数的最优组合，提高了算法的自适应能力，改进的DWA算法的伪代码如表1所示：
«——【·仿真验证与分析·】——»
仿真实验中算法参数的设置如表2所示。
为了验证所提出的算法的性能，本节首先针对传统的DWA算法由于固定权重系数易产生的路径规划不合理的问题，在障碍物密集的环境中从脱离局部最优、导向目标点、穿越密集障碍三个方面进行仿真对比测试实验，其次还验证了改进算法的性能与效率。
仿真1：首先验证改进DWA算法脱离局部最优的能力，构建如图5所示的障碍物环境地图。
首先利用传统的DWA算法，设置权重系数组合为α=0.8、β=0.8、γ=0.5，可以得到如图5（a）的结果，发现算法陷入局部最优，移动机器人无法避开障碍物。
同样设置提出的改进DWA算法在非障碍物密集区域的权重系数组合为α=0.8、β=0.8、γ=0.5，可以得到如图5（b）的结果，发现移动机器人可以成功避开障碍物并到达目标点。
两种结果对比可知，传统DWA算法由于固定的权重系数使移动机器人受方位角的影响过大，从而导致无法避开障碍物；
而改进的DWA算法使移动机器人在面对可能会造成阻碍的障碍物时会降低方位角权重α并提升避障权重β，从而顺利避开障碍物，并成功到达目标点，证明了改进算法脱离局部最优的有效性。
然后验证改进DWA算法导向目标点的能力，构建如图6所示的障碍物环境地图。
首先利用传统的DWA算法，设置权重系数组合为α=0.1、β=0.8、γ=0.5，可以得到如图6（a）的结果，发现移动机器人无法成功到达目标点。
同样设置提出的改进DWA算法在非障碍物密集区域的权重系数组合为α=0.1、β=0.8、γ=0.5，可以得到如图6（b）的结果，发现移动机器人可以成功到达目标点。
两种结果对比可知，传统DWA算法的固定权重系数使移动机器人受避障的影响过大而受方位角的影响过小，导致在目标点周围存在障碍物时无法成功到达目标点；
而改进的DWA算法使移动机器人在接近障碍物附近的目标点时会提升方位角权重α并降低避障权重β，从而成功到达目标点，证明了改进算法导向目标点的有效性。
仿真2：为了验证所设计的视野域对算法穿越障碍物密集区域的影响，构建如图7所示的复杂障碍物环境地图。
由图7（a）可见传统DWA算法规划出来的路径会绕过障碍物密集区域，导致路径长度大大增加，降低了路径合理性；
由图7（b）可知，相比传统DWA算法，加入视野域的改进DWA算法能够识别障碍物密集区域并在障碍物密集区域采用改进的DWA算法从而使轨迹可以穿越障碍物密集区域，路径长度缩短了20.7%，算法的性能得到了明显的提升。
仿真3：为了验证改进算法的性能，首先建立如图8所示的环境地图。
传统DWA算法的权重系数组合为α=0.5、β=0.3、γ=0.2时易得到较优的路径，规划出来的路径用蓝色线表示，路径长度为12.099m，安全距离为0.382m。
同样将提出的算法在非障碍物密集区域的权重系数设置为α=0.5、β=0.3、γ=0.2，规划出来的路径用红色线表示，路径长度为11.754m，安全距离为0.377m，可见改进算法在路径长度和安全性上都有有效的优化，而且轨迹平滑性更好。
运行线速度对比图如图9（a）与图9（b）所示，可见传统DWA算法在穿越障碍物密集区（t=50~170s）时的线速度较高而且波动幅度较大，使得安全性降低；
而改进后的DWA算法不仅可以在到达障碍物密集区前高速前进，而且在到达障碍物密集区时能及时降低线速度，并以较低速度穿越此区域，确保移动机器人能够安全高效地在障碍物密集环境中进行路径规划。
«——【·结语·】——»
针对传统DWA算法因固定的权重系数组合无法同时兼顾导航、避障、速度三方面的要求造成的难以适应障碍物密集环境这一问题，提出了基于NSGA-II的DWA算法。
建立了以评价函数、速度函数为目标函数、以权重系数为自变量的多目标优化问题的数学模型，并利用改进的NSGA-II算法进行求解，实现了权重系数的自适应变化。
仿真实验表明了改进DWA算法明显改善了传统DWA算法路径规划不合理的问题，验证了改进DWA算法通过障碍物密集区时的合理性、高效性，对研究路径规划有一定的参考价值。
