动态环境中的无人机路径规划方法

刘 洋 章卫国 李广文 史静平

(西北工业大学 自动化学院，西安 710129)

路径规划是无人机任务规划中最基本的部分.由于无人机路径规划时需要考虑威胁、动态约束等问题，使得规划的复杂性显著增加.为了解决这些问题，文献［1］提出了概率地图法(PRM，Probability Road Maps).概率地图法可以构造自由空间中的连通图，将连续空间的规划问题转化为拓扑空间的规划问题，使路径规划问题的复杂度与环境的复杂程度和规划空间的维数无关，而主要依赖于路径搜索复杂度.

在实际规划环境中不但有静止的障碍物，还有运动的障碍物.因此，路径规划不仅需要考虑与静止障碍物的碰撞，还需要研究如何防止与运动障碍物碰撞的问题.对于动态环境中的路径规划问题已有很多研究.文献［2］通过对环境进行模糊描述，将距离信息转换为相应位置受障碍物影响的程度，表示为模糊信息，解决了动态障碍物的表示问题.文献［3］修改了传统势场函数，通过增大运动障碍物的威胁程度的方法表示动态障碍物的势场，并应用于规划中.文献［4］中通过引入碰撞危险度概念进行路径规划，成功解决了动态障碍物的避碰问题.文献［5］中把动态障碍物都看作匀速运动的障碍物，采用遗传算法研究了动态环境中的规划问题.文献［6］提出了一种基于分层强化学习的路径规划算法，但运行速度较慢.文献［7］采用PRM方法构建路线图，同时将时间离散化，然后按每个时间点对动态的障碍物进行碰撞检测.这些研究都是通过预测某一时刻运动障碍物的运动范围或计算运动障碍物在某一位置出现的概率来解决这一问题的，这就存在一个缺陷，即这些方法都只能表示运动障碍物在某一时刻的情况，而不能表示其所有时刻的情况.由于无人机的飞行是连续的，经过不同位置的时刻是不同的，这样的方法只能保证得到的路径是可行的，不能保证是最优的.要想解决这个问题，就需要表示出运动障碍物在所有时刻的位置.而概率地图法在空间维数增加时，不会显著增加采样点的数量.因此本文通过引入时间轴，将构型空间扩展为构型-时间(CT，Configuration-Time)空间.在CT空间中可以表示运动障碍物在所有时刻的情况，这样就可以得到更优的结果，更好地解决含有动态障碍物环境的路径规划问题.

完成规划环境的表示后就可以搜索可行的路径.在路径生成阶段，本文采用了一种改进的蚁群算法，通过将方向信息作为启发信息引入蚁群算法，使蚂蚁在算法运行开始阶段的搜索更有目的性，提高了算法的收敛速度.

1 规划环境的构建

在实际的规划环境中，不但存在着静止障碍，还存在着一些运动的障碍，它们在规划环境中的位置随时间改变而改变，如何在规划中考虑运动障碍的碰撞检测是一个研究的重点.将算法从静态环境扩展到动态环境的研究已有很多，但是只有有限的几种方法可以很好地处理动态环境的规划问题.概率地图法通过随机采样构建概率地图的方法表示环境信息，可以处理动态环境的规划问题.

为了在构型空间中表示运动障碍，本文在构型空间中引入时间轴，将障碍物所有时刻的位置表示出来，从而把构型空间扩展为CT空间，然后在CT空间中进行碰撞检测并生成地图，可以解决动态障碍的问题.对于一个运动趋势已知的障碍物，在未来任意时刻其位置是已知的，因此可以把这种运动障碍物的所有时刻的位置在CT空间中表示出来.对于运动规律未知的障碍物，当其最大速度已知时，则可以确定其在任意时刻可能的位置范围，若把所有可能的范围都标注为碰撞的，则可以保证规划得到的路径无碰撞.基于这种思想，本文将所有障碍物都在CT空间中表示并采用PRM方法构建环境地图.

如图1所示为规划环境，其中障碍物1为运动规律未知的障碍物，其最大运动速度已知，只能给定其运动范围;障碍物2与障碍物3为运动方向已知但速度未知的障碍物，它们沿箭头所指方向运动;障碍物4为运动规律已知的障碍物，其沿箭头所指方向匀速运动;障碍物5为运动轨迹已知，速度未知的障碍物.它们在CT空间中的表示如图2所示.

图1 规划环境

图2 运动障碍物在CT空间中的表示

对于传统概率地图法，首先从构型空间中选取一个点，运用碰撞检测程序检测采样得到的点的位置，若碰撞，则舍弃;若位于自由空间中，则把这个点作为结点加入到路线图中.随后，尝试将新获得的结点与路线图中的结点连接在一起，如此循环直到完成路线图的构建.这种方法可以自然地扩展到CT空间，在CT空间中随机得到的每个采样点都包含两个信息:一个是采样点的位置信息，另一个是采样点的时间信息.这种方法会得到一部分无用的采样点，这些无用的采样点无人机肯定不会经过，可以在构建地图时忽略.例如，在初始点附近但时间坐标值较大的采样点是肯定不会经过的，这就使算法性能有部分浪费.为此，改进了采样点的获得方法，只给定其位置坐标而不给定其时间坐标，在路径生成过程中对于经过的采样点动态地添加时间坐标并进行碰撞检测.时间坐标的值由当前结点的前向结点的时间坐标和两个结点之间的距离确定.时间坐标添加方法如图3所示.图中给出了两条在概率地图基础上得到的出发点cs和目标点c2之间带时间坐标的路径示意图，图中Δt为从cs到c1所需的时间.当无人机从cs出发到达c1点时，c1点的时间坐标由cs点的时间坐标与无人机从cs到c1点所需时间相加得到.

图3 时间坐标的添加方法

2 基于概率地图的蚁群算法

基于概率地图的路径规划的难点在于，当概率地图规模较大的时候，会存在搜索时间过长的问题.因此，构建快速有效的优化搜索算法是合理解决路径规划问题的关键.蚁群算法作为一种智能算法，能够在较短的时间内至少得到一个次优解，可以有效解决这个问题.

传统的蚁群算法［8］在开始阶段由于各个路径段上的信息素是相同的，蚂蚁经过各个路径段的概率是相同的，这样就会使蚂蚁搜索到的路径较差，如果在初始时刻给蚂蚁一定的指引，就能使蚂蚁更早地寻找到较好的路径.文献［9］通过计算目标吸引度引导蚂蚁搜索，但是目标吸引度计算复杂，运算效率较低.文献［10］则是采用了自适应调整的启发函数，实时计算启发函数引导蚂蚁搜索.本文将方向信息作为新的启发信息引入蚁群算法中，使蚂蚁在搜索路径时受到指引，加快蚁群算法的收敛速度，能够以更快的速度得到解.

2.1 改进的状态转移规则

蚁群算法中蚂蚁按照环境中的信息素分布和启发信息进行其状态转移，启发信息由候选的解元素的评价值决定.在路径规划中蚁群算法的状态转移是指蚂蚁由一个采样点经过一条边移动到采样点，构成路径的解元素就是概率地图中的边.蚂蚁k在结点i选择结点j的概率为

式中，τij是边(i，j)上的信息素轨迹强度;ηij为边(i，j)的能见度，反映由结点i转移到结点j的启发程度，这个量在蚁群算法的运行中不变;Φk表示蚂蚁k下一步可以选择的结点.由式(1)可知，转移概率与成正比.α和β为两个参数，分别反映了蚂蚁在运动过程中所积累的信息素和启发信息在蚂蚁选择路径中的相对重要性.

在基本蚁群算法中，蚂蚁开始路径搜索时，由于各条路径上的信息素含量是相等的，文献［8］中启发信息选用了路径段长度的倒数，不能很好地引导蚂蚁选择路径，降低了算法的效率.为了在初始时刻对蚂蚁的搜索做出指引，本文对启发信息做了改进，引入了方向信息，使蚂蚁在寻找路径时受到方向信息的影响，提高了算法的效率.改进算法的启发信息函数公式如下:

式中θij为可选结点j与目标结点的连线与初始终止点连线的夹角.可见转移概率不但与成正比，而且还与夹角θ的余弦值成正比.ij夹角θij越小，cosθij值越大，蚂蚁选择结点j的可能性就越大.

2.2 基于约束条件的候选集合策略

在蚁群算法中，构建蚂蚁状态转移的候选集合策略是提高算法性能的一个重要途径.为了能够更好地表达环境信息，构建的概率地图含有的采样点数量往往较多，这就导致无人机路径规划问题规划空间的规模比较大，因此设计一个合适的候选集合策略可以提高算法的运行效率，具有很重要的意义.

在基于蚁群算法的无人机路径规划中，蚂蚁的状态转移候选集合的构造需要考虑环境约束以及无人机的性能约束，有下面几个方面的因素:①概率地图中结点之间的连通关系限制;②无人飞机的最小航线段长度限制，飞机在经过转弯后需要一定的直飞距离来修正转弯造成的航线偏移并调整自己的飞行姿态，这有利于飞机对航线的精确跟踪;③无人飞机的最大转弯角度的限制，这与飞机的机动性能相关;④飞机最大航程限制，这与飞机的载油量相关.在考虑这些限制之后，蚁群算法中蚂蚁可以选择的结点范围大幅减少，有利于算法性能的提升.

2.3 基于排序的信息素更新机制

为了防止蚁群算法过早地收敛，陷入局部最优，在信息素更新时采用了基于排序的更新机制.

基于排序的信息素更新机制的局部信息素更新规则与基本蚁群算法相同，路径段(r，s)上的信息素更新如下所示:

式中，ρ为挥发系数;Δτrs为路径段上信息素的增量.

全局信息素更新中在每次循环完成后，对蚂蚁搜索得到的路径按照长度进行排序，并对排在前m名的蚂蚁进行相应的信息素更新，更新规则如下所示:

式中，Δτij为当前路径段上走过的蚂蚁按照排名得到的信息素更新量的总和;λ为挥发系数.

2.4 基于排序的信息素更新机制

基于排序的蚁群算法步骤如下所示:

初始化

Repeat

For k=1:n//对每一只蚂蚁

Pi={ps};//将蚂蚁置于起始点

Repeat//查找路径

For所有候选路径点

根据式(2)，计算启发信息ηij

根据式(3)进行局部信息素更新

Until到达目标点.

根据式(4)进行全局信息素更新;

Until满足终止条件.

3 仿真实验

基于上述算法设计，本文针对如图1所示的动态规划环境进行仿真实验，规划范围为200×200，障碍物为圆盘形，最大转弯角为60°，构建概率地图的采样点数量为600个.图4为改进蚁群算法得到的路径.图5为无人机沿规划得到的路径飞行时在部分时刻与障碍物的相对位置图.其中菱形为无人机当前时刻的位置，灰色圆盘为障碍物的可能位置.由仿真结果可见，无人机与障碍物是不碰撞的，验证了方法的可行性.

图4 改进蚁群算法得到的路径

图5 无人机在部分时刻与障碍物的相对位置图

为了验证算法的有效性，本文对蚁群算法和改进蚁群算法分别进行了仿真验证.图6为路径长度的迭代曲线对比图，由仿真结果可见，改进蚁群算法可以在算法运行初期得到更好的解，这说明由于引入了方向信息作为启发信息，蚂蚁在算法开始阶段寻找路径时，受到了更好的引导，可以更早地寻找到较短的路径，使算法更快地收敛.

图6 路径长度的迭代曲线对比

为了验证本文提出的蚁群算法在不同规模的概率地图中的有效性，本文在图1所示环境中对采样点数量为600，800和1 000的情况分别进行了仿真实验，图7为路径长度的迭代曲线对比图.由迭代曲线对比可见，算法在不同采样点数量的情况下都可以在算法开始阶段找到较好的结果，并且算法能够快速地收敛到最终结果.

图7 不同采样点数量条件下的路径长度迭代曲线对比

4 结 束 语

本文针对动态环境中的路径规划问题，提出了一种引入时间轴扩展构型空间的方法.仿真结果表明，这种方法可以解决动态环境中的无人机避障问题.在路径生成阶段，本文提出了一种改进的蚁群算法，通过引入方向信息作为新的启发信息，改进蚁群算法可以更快地收敛到最优解，提高了蚁群算法的运算效率，更好地满足了无人机规划的实时性要求.

References)

［1］ Kavraki L E，Svestka P，Latombe JC，et al.Randomized preprocessing of configuration space for fast path planning［C］//IEEE International Conference on Robotics and Automation.San Diego:IEEE，1994:3020 －3026

［2］曾碧，杨宜民.动态环境下基于蚁群算法的实时路径规划方法［J］.计算机应用研究，2010，27(3):860 －863 Zeng Bi，Yang Yimin.Method of real time path planning based on ant colony algorithm in dynamic environment［J］.Application Research of Computers，2010，27(3):860 －863(in Chinese)

［3］朱毅，张涛，程农，等.动态环境下基于子目标的移动机器人路径规划方法［J］.系统仿真学报，2010，22(增刊1):254－257 Zhu Yi，Zhang Tao，Cheng Nong，et al.Sub-goal based path planning method for mobile robot under dynamic environment［J］.Journal of System Simulation，2010，22(Supplement 1):254 －257(in Chinese)

［4］肖本贤，齐东流，刘海霞，等.动态环境中基于模糊神经网络的AGV路径规划［J］.系统仿真学报，2006，18(9):2401－2404 Xiao Benxian，Qi Dongliu，Liu Haixia，et al.AGV path planning in the dynamic environment based-on fuzzy neural network［J］.Journal of System Simulation，2006，18(9):2401 － 2404(in Chinese)

［5］刘国栋，谢宏斌，李春光.动态环境中基于遗传算法的移动机器人路径规划的方法［J］.机器人，2003，25(7):327－330 Liu Guodong，Xie Hongbin，Li Chunguang.Method of mobile robot path planning in dynamic environment based on genetic algorithm［J］.Robot，2003，25(7):327 －330(in Chinese)

［6］沈晶，顾国昌，刘海波.未知动态环境中基于分层强化学习的移动机器人路径规划［J］.机器人，2006，28(5):544－547 Shen Jing，Gu Guochang，Liu Haibo.Mobile robot path planning based on hierarchical reinforcement learning in unknown dynamic environment［J］.Robot，2006，28(5):544 － 547(in Chinese)

［7］ Van Den Berg J，Overmars M.Kinodynamic motion planning on road maps in dynamic environments［C］//Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems.San Diego:IEEE，2007:4253 －4258

［8］ Colorni A，Dorigo M，Maniezzo V.Distributed optimization by ant colonies［C］//The 1st European Conference on Artificial Life.Paris:Elsevier Publishing，1991:134 －142

［9］张晓勇，吴敏，彭军，等.机器人救援的目标吸引动态路径规划蚁群算法［J］.系统仿真学报，2011，23(9):1854 －1859 Zhang Xiaoyong，Wu Min，Peng Jun，et al.Target attraction based ant colony for dynamic path planning of rescue robot［J］.Journal of System Simulation，2011，23(9):1854 －1859(in Chinese)

［10］柳长安，鄢小虎，刘春阳，等.基于改进蚁群算法的移动机器人动态路径规划方法［J］.电子学报，2011，39(5):1220－1224 Liu Chang’an，Yan Xiaohu，Liu Chunyang，et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm［J］.Acta Electronica Sinica，2011，39(5):1220－1224(in Chinese)