基于蚁群算法的移动机器人多目标路径规划

蒋 强，易春林，张 伟，高 升

(1. 沈阳理工大学，辽宁 沈阳 110159；2. 中国科学院沈阳自动化研究所，辽宁 沈阳110016)

1 引言

随着信息化与工业化的不断融合，全球正经历第四次工业革命浪潮，以机器人为代表的智能产业迅猛发展，将成为当代科技创新与智能制造的中流砥柱。与传统工业机器人相比，具备自主感知、主动决策和自动执行功能的智能机器人拥有更大的机动性和灵活性，在国防、航空航天、工业生产、智能物流运输、社会服务等领域有着广阔的应用前景。作为智能机器人研究领域的一个重要分支，路径规划技术是智能机器人实现自主导航、完成其它高级任务的前提与基础，其目的是在具有障碍物的环境中，按照一定的评价标准(如路径最短、耗能最小、安全性最高等)，寻找一条从起始点到目标点的无碰撞路径[1]。

虽然单任务机器人可以在某种层面上满足人类对智能制造的渴望，然而迫于成本与空间的限制以及对绿色生产理念的追求，人们更愿意在工业生产中使用多任务机器人。通常多任务可以分成串行多任务和并发多任务，对于串行多任务，机器人可按照任务之间的时序要求或先后关系，从前到后依次逐个执行；而对于并发多任务，则需要优化各个任务的执行顺序，尽可能减少机器人往返于各个任务点之间所需的时间或能源消耗，即需要考虑机器人的多目标路径规划问题。不同于M.Nazarahari等人在文献[2]中对多目标路径的描述，本文将多目标路径规划定义为：在具有障碍的环境中，按照一定的评价指标，寻找一条从初始位置出发并遍历所有目标点的无碰撞路径。显然，多目标路径规划模型能更好的贴近现实，在无人生产、智能物流配送、车间调度等领域有着极大的应用价值。

这些年来在众多学者的潜心钻研下，人们对路径规划的研究已经取得了辉煌的成绩，针对各种路径规划问题提出了大量不同的解决方法。例如栅格地图[3]、几何特征地图、拓扑地图以及混合地图等方法被用于路径规划的地图建模环节中；Dijkstra算法[4]、A*算法[5]、人工势场法[6]以及一些诸如PRM、RRT[7]等基于采样的方法被用于路径规划的路径搜索环节中，此外随着人工智能的发展，一些智能算法也逐渐被应用于路径搜索中，如神经网络算法[8]、遗传算法[9]、蚁群算法[10]、粒子群算法[11]等。然而在这些成果中，几乎没有对本文所定义的多目标路径规划的研究，因此本论文致力于研究多个目标点之间的路径规划问题，期望所研究的内容有助于移动机器人技术的发展与进步。

2 地图建模与路径搜索算法

2.1 地图建模

地图建模是路径规划的重要环节，目的是将移动机器人所处的实际物理环境抽象成便于计算机存储和处理的地图模型，实现现实环境与虚拟地图的相互映射。在前面提及的地图建模方法中，栅格地图具有简单有效、易于实现、便于更新的特点，是目前研究和应用最广泛的方法。通常根据栅格的划分方式，可将其分为确切栅格和不确切栅格，其中确切栅格法编程简单且易于实现，因此本文采用由正方形构成的确切栅格来表示机器人的真实工作场景，如图1所示。

确切栅格是将机器人的工作环境按照一定的精度划分成一系列大小相等的栅格单元，然后根据障碍物的占据情况将栅格分成两种状态：把包含障碍物的栅格标记为障碍栅格(黑色部分)，表示机器人不可通行的区域；把不包含障碍物的栅格标记为自由栅格(白色部分)，表示机器人可以通行的区域。由图1(c)和1(d)可知，栅格单元的大小会直接影响环境的精度：当栅格单元划分较小时，环境信息存储量将增大，不利于进行路径搜索；当划分较大时，无法准确地表示真实环境，甚至会导致可通行的路径信息被覆盖掉。而且在实际情况中，机器人在障碍环境里的移动不能被简单的视为质点的移动，需要考虑机器人自身的形状、尺寸以及运动学与动力学约束对它的影响，甚至有时为了保证机器人在运动过程中的安全性，还需要让机器人与障碍物保持足够的距离。为了简化问题以便于后续工作的开展，本文做出以下合理的假设：

1)仿真中所用的地图是在考虑到机器人最大尺寸及安全距离的情况下建立的，已对地图中的障碍物做膨胀处理，因此在规划路径时可将机器人视为一个质点；

2)机器人所处的环境是静态的；

3)机器人不具备特殊的外形，如长杆形等；

4)机器人以麦克纳姆轮或全向轮为驱动轮，在小范围内具有360°全方位移动的能力，不受规划路线是折线的影响；

5)栅格地图的精度选择合理，不会因为栅格过大而致使地图中的可通行信息被湮没。

图1 基于栅格法的地图模型

2.2 改进的Dijkstra路径搜索算法

Dijkstra算法是荷兰计算机科学家E.W. Dijkstra于1959年提出的一个适合于所有边的权重均为非负值的最短路径算法。作为图论中一种典型的单源最短路径求解方法，常被用于计算加权图中指定节点到其它所有节点的最短路径，它的主要特点是以起始点为中心按路径递增的顺序逐渐向外层扩展，直至到达目标点为止。由于需要遍历目标距离范围内的所有节点，因而存在搜索效率低的缺点，不适合搜索单个目标；然而与A*算法以及一些智能搜索算法相比，它具有更好的广度优先搜索特性，在同时搜索多个目标对象时具有较好的实效性。

众所周知，在路径规划中A*算法是一种实时性较好的搜索算法，因此这里将A*算法与Dijkstra算法进行比较，以验证两种算法在多目标路径搜索中的时效性，仿真结果如图2所示，其中红色、蓝色曲线分别表示使用Dijkstra、A*算法所规划出的路径，仿真结果表明：①在相同邻域的搜索规则下，Dijkstra算法规划的路径更短；②这两种算法均具有完备性，若环境中存在一条从起点到终点的无碰路径，则该算法一定能找到，若不存在则会报告规划失败[12]。

图2 基于A*和Dijkstra算法的多目标路径搜索

地图序号(栅格尺寸)目标序号目标个数寻路时间(s)经典A*DijkstraMap A110.00210.0039(13×13)1～770.00870.00511～13130.01390.0060Map B110.05340.0828(100×100)1～881.00790.20461～15151.82630.2475

表1 列出了这两种算法在不同情况下所需要的寻路时间，实验数据说明：对单目标的路径规划，A*算法具有较好的时效性，而对多目标的路径规划，Dijkstra算法具有较好的时效性。

现实中机器人的转向角通常是某个范围内的连续取值；而使用栅格地图进行路径搜索时，Dijkstra算法通常被限制在4邻域或8邻域，如图3所示，因而搜索出的路径一般是比较曲折的。为了使规划的路径性能更优，本文针对搜索方向或搜索邻域较少的问题进行了改进，提出了一种16邻域的搜索规则。图4显示了在不同地图中分别使用这三种规则进行路径搜索所获得的规划路线，其中绿色、粉色和蓝色曲线分别对应4、8和16邻域的搜索规则。由仿真结果可知，随着搜索邻域的增多，所规划的路径效果越好。

图3 四、八和十六邻域搜索规则

图4 三种规则下的路径规划结果

由于搜索方向的限制，使用A*或Dijkstra算法所规划的路径一般是由多条线段组成的折线，特别是在地图尺寸较大的情况下，路径存在一定的锯齿效果，如图5所示。从图中的路径曲线可以看出，路径中存在一些不必要的转折点，如P3和P5，删除这些不必要的转折点可以改善路径在长度、平滑度等方面的性能，因此为了进一步提升路径性能，本文提出了一种删除这些冗余转折点的方法。

图5 路径的锯齿效应

删除冗余转折点的实质就是在路径中找出冗余转折点。考虑到生成的路径是一条折线，因而可用一系列由折线的转折点构成的有序集合来表示Path={P0，P1，P2，…，Pn-1，Pn}，对于路径上的转折点Pi，若其前后两个相邻转折点的连线Pi-1Pi+1不经过障碍物，则Pi是冗余转折点；反之，若Pi-1Pi+1经过障碍物，则Pi是必要转折点，删除它将使路径与障碍物发生碰撞，如图6所示。

由上面的描述可知，Pi-1Pi+1是否穿过障碍物是判断Pi是否为冗余转折点的标志，而判断Pi-1Pi+1是否穿过障碍物就是分析Pi-1Pi+1所经过的栅格单元中是否存在障碍栅格。图7描述了栅格地图中Pi-1Pi+1可能经过的栅格单元，其中红色网格表示连线穿过的栅格单元，而成对出现的绿色网格则表示连线经过该网格的一个顶点但不穿过该网格。显然只有当所有红色网格都不是障碍网格且成对的绿色网格中至少有一个不是障碍网格，才能保证Pi-1Pi+1不穿过障碍。

图6 冗余转折点(左)与必要转折点(右)

设点Pi-1和Pi+1的栅格坐标分别为(x1，y1)和(x2，y2)，并记Δx=|x2-x1|，Δy=|y2-y1|，对于Δx≥Δy的情形，以x为自变量来描述经过Pi-1和Pi+1的直线方程

(1)

①若x1=x2时，线段Pi-1Pi+1所经过的栅格单元的坐标集合Sgrid可表示为

(2)

②若x1≠x2时，线段Pi-1Pi+1所经过的栅格单元的坐标集合Sgrid可表示为

Sgrid=S1∪S2

(3)

图7 Pi-1Pi+1连线经过的栅格单元

(5)

对于W(i)需按以下两种情况来分析，当k≥0时

(6)

当k<0时

(7)

其中，符号[·]表示向下取整；上述公式中除or连接的两个坐标表示成对出现的绿色网格外，其余的坐标均表示红色网格。

而对于Δx<Δy的情形，以y为自变量来描述经过Pi-1和Pi+1的直线方程。同理，在分析Pi-1Pi+1所经栅格单元的坐标集合时，亦可按y1=y2和y1≠y2两种情况来分别讨论。最后，根据所经栅格单元中障碍物的占据情况可以判断Pi-1Pi+1是否穿过障碍物。

图8中的蓝色和红色曲线分别表示优化(删除冗余转折点)前、后的路径，结果表明优化后的路径更平滑也更短。

图8 优化前后的路径效果

3 多目标路径规划算法

通常使用路径长度、平滑度和安全性等三个指标来评价一条路径，由于前面已假设按照安全距离对障碍物进行了膨胀，因此生成的路径一定是安全可靠的。此外，由于机器人停留在任务点执行任务的过程中可能会且有足够的时间做出一些姿态调整，因此不必要求机器人进入某个目标地点或离开该目标点的姿态必须连贯，即无需考虑机器人进入或离开某个目标点时路径的平滑度。

多目标路径规划问题本质上是一个需要大量已知环境信息的全局寻优问题，因而只适合在环境信息已知的全局路径规划中实现，它主要包含路径规划技术和多目标优化技术，两种技术间的融合如图9所示。

在全局路径规划部分，主要包含以下几个环节：①选择路径搜索算法；②搜索并优化起始点及各目标点之间的路径；③计算每条优化后的路径距离。在多目标优化部分，主要是利用由全局路径规划获取的距离信息来搜索一条最短路径。为了详细地介绍多目标路径规划的实现过程，本文将分别从路径规划和多目标优化两个部分来进行描述。在此之前先假设在某个具有障碍物的环境中机器人的起始位置为T0，其期望到达的n个目标点的位置分别为T1，T2，…，Tn。

图9 多目标路径规划框架图

3.1 路径规划

在路径规划部分，需要采用一种有效的全局路径搜索算法搜索出T0，T1，T2，…，Tn中每两点之间的最短无碰撞路径，然后对这些生成的路径进行优化处理。待路径优化完毕，将得到一系列由折线段组成的路径，如图10所示。

图10 点Pi到点Pj的路径示意图

故点Ti到Tj的距离di，j(0≤i，j≤n，i≠j)可由式(8)计算。

(8)

最后可用一个距离矩阵来描述这些距离信息

(9)

从而多目标路径规划问题可以表述为

(10)

其中，R表示{1，2，3，…，n}的全排列，R(i)表示该排列中的第i个元素。

由于dij和dji是相等的，因此为了提高路径规划的效率，在搜索路径时只需要获取距离矩阵中上三角部分的元素对应的路径及距离信息。除此以外，Dijkstra算法适合同时搜索大量目标，当目标个数较少时，为了保证算法的搜索速度，可选择使用A*等算法来进行路径搜索。

3.2 多目标优化

在多目标优化部分，需要采用优化算法在距离矩阵中寻找出一条从起始点出发遍历所有可到达的目标点的最短路径。这是一种典型的TSP问题，它已被证实为具有NPC计算复杂度——随着目标个数的增多，问题的可行解会产生组合爆炸。

当问题规模较大时，为了避免对整个可行解空间进行穷举式的搜索，越来越多的学者热衷于使用遗传算法、蚁群算法、粒子群算法、免疫算法和细菌觅食算法等智能优化算法来求解多目标问题的近似最优解。与早期的分枝定界法、线性规划法、动态规划法等精确算法相比，智能算法无需遍历整个可行解空间，计算效率较高。在上述智能优化算法中，蚁群算法具有分布计算、信息正反馈和启发式搜索等特征，在搜索最短路径方面具有优势[13]，因此本文使用蚁群算法来解决多目标优化问题。

蚁群算法是通过模拟蚁群觅食过程而提出的一种启发式优化算法，蚂蚁在合作觅食的过程中，总能通过各自遗留在所经路线上的信息素来进行信息交流，从而指导整个蚁群在蚁穴与食物找到一条最优路径。受益于这一自然灵感的启迪，M.Dorigo等人于上世纪90年代提出了蚁群算法基本模型[14]，其原理如下：

(11)

息启发式因子，表示信息素的相对重要性，反映了路径上残留的信息素对蚂蚁选择路径的影响程度；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息对蚂蚁选择路径的影响程度。

当每只蚂蚁走完一步或完成一次周游后，要对各路径上残留信息素进行更新处理，通常t+1时刻在路径(i，j)上的信息素可按如下规则进行调整

τij(t+1)=(1-ρ)·τij(t)+Δτij(t)

(12)

(13)

(14)

4 仿真及结果分析

为了验证该多目标路径规划算法的有效性，本文将采用一系列尺寸不同、环境各异的地图来进行仿真。整个程序使用Python语言进行编写，计算机配置为：Windows 7操作系统，处理器为E5620，主频2.4GHz，运行内存为8G。

图11 多目标路径规划仿真地图

实验所用的仿真地图如图11所示，其中蓝色栅格(或圆)表示起始节点，绿色栅格(或圆)表示目标节点，为了便于计算所生成路径的距离信息，在这里认为所有地图中栅格单元的边长为1，即地图尺寸为100×100的地图是由100×100个网格单元构成的。与精确算法不同的是，蚁群算法求解的是优化问题的近似最优解，并不能保证每一次仿真结果都是一致的。为了确保实验结果有足够的说服力，本文将对同一地图进行多次(10次)重复仿真，并记录相关实验数据及对应的地图信息至图13中。最后在图12中显示了十次仿真中路径长度最短的实验结果，其中红色线段表示所规划的路线。

从图12中各目标点之间的路径曲线可以看出，该路径搜索算法对最短路径的搜索效果大体上能与可视图法媲美，它所规划的路径大多都是最短的或近似最短的，符合多目标路径规划求解全局最短路径的设计初衷。通过分析仿真结果可以看出：①由对Map_1、Map_2、Map_3以及Map_4的仿真结果可知，该算法对不同复杂度的环境均能做出有效的路径规划，具有较好的环境适应能力；②在Map_1中设定了与起点隔离的四个目标点，由此地图的规划结果可知该算法能够判断出某个目标是否可到达，并在多目标路径规划阶段避开不可到达的目标点；③由表2中出现实际最短距离的次数可知，当目标点个数较少时，蚁群算法能大概率搜索出全局最优解，而随着目标个数的增加，蚁群算法开始陷入局部最优解(见图12中Map_6的仿真结果)，只有很小的概率能找到最优解，因此在以后的研究中将重点对蚁群算法进行优化，以提高算法的优化性能；(4)通过分析图13中Map_4、Map_5和Map_6的仿真数据可以发现，平均误差会随着目标个数的增加而逐渐增大，但整体平均偏差是在一个可接受的范围内，从而说明该算法能有效解决多目标路径规划问题。

图12 多目标路径规划仿真结果

地图基本信息实验数据地图序号地图尺寸目标个数实际最短距离进行10次重复仿真十次仿真中出现的最好结果十次仿真中出现的最坏结果平均搜索距离平均误差出现实际最短距离的次数平均搜索时间(s)蚁群算法相关参数设置Map_1100×100153703703703700%102.292Map_2100×100156706706756710.15%84.077Map_3100×10015503503.6509503.60.12%93.297Map_4200×200116666666666660%107.357Map_5200×200211009101410301022.11.30%414.182Map_6200×200311186120512241213.12.28%323.216Q=1ρ=0.02α=3β=2.5

注：在每一次仿真中，蚂蚁个数k与可到达的目标点个数相同。

5 结论

随着无人生产理念的不断深化以及智能制造技术的不断进步，智能机器人将在我国今后的工业生产、产业结构转型和产品优化升级等方面发挥巨大的作用，本文针对智能机器人在复杂的静态障碍物环境下执行并发多任务的情况，提出了一种基于蚁群算法的多目标路径规划算法，通过仿真结果可验证，在静态环境中该算法能有效解决多目标路径规划问题。与单目标路径规划相比，多目标路径规划更为复杂，存在一些至今尚无高效解决方法的难点，这些问题的突破将有助于多目标路径规划的广泛应用：

1)没有考虑机器人的运动学与动力学特性，只是从决策层面(而非执行层面)进行了路径规划，获得的路径不符合机器人的底层控制要求，不能将该路径用于机器人的轨迹跟踪。因此在未来的研究中应将机器人的底层控制与路径规划算法相结合。

2)大多数关于多目标路径规划的研究都是基于静态环境的，难以适用于复杂且多变的现实环境。相对静态环境下的路径规划，动态环境下的多目标路径规划更加贴近实际应用。

3)在诸如蚁群算法、遗传算法等智能优化算法中，参数的配置对优化结果的好坏有着极大的影响，在解决各种优化问题时往往需要根据实际问题来配置参数，并不存在一组适合解决各种优化问题的万能参数。因而根据当前的优化问题自适应地配置并调节优化算法的相关参数[15]是确保多目标路径规划算法自主适应各类地图环境的关键。