李 波，易 洁

(重庆理工大学， 重庆 400054)

随着机器人技术的发展及生产实践的需求，单机器人系统已经不能满足人们的实际需求。而与单机器人构成的系统相比，多机器人系统可以通过机器人之间的相互协调合作提高工作效率，提升工作性能，增强容错能力。因此，对多机器人系统的研究已成为目前的研究热点，但同时多机器人系统也使系统复杂程度增加。多机器人系统的算法问题包含了路径规划、碰撞检测、避障策略等，其中最重要的问题是多个机器人如何在互斥的工作区域中工作而不冲突。

对于共享工作空间的多机器人系统的无碰路径规划，需要解决以下两个主要问题：一是对于给定的任务，机器人相对于静态障碍物的无碰路径规划；二是多机器人相互之间的无碰协调运动路径规划[1]。

路径规划是机器人研究中的主要研究内容之一。机器人的路径规划问题，就是在其工作空间中搜索一条从起始状态到目标状态能避开障碍物的最优路径，其一般步骤主要包括环境建模和路径搜索。先根据采集到的环境信息构建路径搜索空间，一般可以简化为二维模型，目前的表示方法可以大致分为3类：栅格表示、几何信息表示和拓扑图表示[2]。栅格表示法是将整个工作环境按照相同的大小划分成若干小方格，即栅格，同时对于每个栅格分别进行说明是否存在障碍物。其特点是：创建与维护较容易，但当栅格数量增大时，内存消耗非常大，且实时处理变困难。几何法是使用更为抽象的几何特征对环境进行描述，这种方法便于位置估计和目标识别，但几何信息的提取需要对感知信息做额外的处理，且需要有大量感知信息的支撑才能得出结果，较麻烦[3]。拓扑图将环境表示为一张拓扑意义中的图，图中的节点对应于环境中的一个特征状态、地点。节点间存在的直接连接路径相当于图中连接节点的弧，它能实现快速的路径规划，而当存在两个很相似的地方时，这种方法很难确定是否为同一个节点。

目前，常见的单个机器人系统的路径搜索避障算法有：A*算法[4]、人工势场法[5]、遗传算法[6]等。这些算法依旧存在许多问题，例如A*算法转折次数多，使得机器人按规划路径行动变得非常困难；人工势场法在狭小的区域当中容易产生抖动；遗传算法还不完善，人工因素对结果有很大的影响。对于多机器人系统的路径规划方法的研究，大部分是从单个机器人系统的路径搜索避障算法扩展而来的，主要可分成三大类：传统方法(人工势场法等)、智能优化算法(遗传算法、强化学习等)和其他方法(动态规划、模糊控制等)。

人工势场法是将机器人系统在工作空间中的运动看作受到了一种虚拟的人工受力场的作用后的运动，障碍物对机器人产生斥力，而目标状态点对之产生引力，引力和斥力由算法产生相应的势，但是和单机器人系统一样，也存在着目标点不可达和易陷入徘徊抖动的问题，以及对于动态环境规划能力不足的问题。文献[7]在原有引力势场和斥力势场的基础上增加了填平势场，并规定只有当机器人处于局部极小点时才启用，解决了目标点不可达和易陷入徘徊抖动的问题，但是对于动态环境规划能力不足的问题并未得到解决。在强化学习算法中，主要是将机器人系统通过马尔科夫建模转换成一个强化学习可以解决的问题，再通过强化学习进行求解，从而得到路径规划，达到避障的目的。其优点主要是：不需要构建精确的环境模型，并且可以一次性将避障、路径规划等问题解决。其缺点是：当处于动态环境中，会不可避免地出现学习策略随状态、动作的维数呈指数增长的现象导致“维数灾难”，同时由于其不存在一个明确的标签，在机器人和环境之间的交互完全是采用试探的方法，导致强化学习的学习速度比较慢。文献[8]提到可以通过分层强化学习来解决“维数灾难”；文献[9]提出一种新的基于ERL算法的非线性动态系统最优控制方法，提高了非线性系统的学习效率。虽然路径得到了优化，但是学习效率并没有得到显著的提升，且算法的复杂性依旧存在。

在本文中使用改进的栅格法来对环境进行建模，然后再在构建好的环境模型中利用对转折次数多这一缺点进行改进后的A*算法，在不考虑机器人相互碰撞、只考虑静态障碍物的前提下得到单个机器人位形空间的静态无碰运动规划；在给定各机器人任务路径的前提下，使用基于时间的多机器人协调避碰规划算法实现系统间的无冲突连续路径搜索，即先求得多机器人系统的碰撞点集，然后通过计算时间来调节机器人到达碰撞点时是否真正产生碰撞，如果产生则避让。该方法采用解耦法进行研究，同时仿真实验结果：说明该方法能有效并快速得到多机器人系统的路径规划。

1 背景知识

1.1 栅格法

栅格法最先由W.E.Howeden于1986年提出。在进行路径规划时，W.E.Howeden采用栅格表示地图，在处理障碍物的边界时，避免了复杂的计算。当要更精确地表示地图，即栅格粒度越小时，会占用大量的存储空间，并且实时处理会变得困难[10]。

栅格模型使用形状为二维矩形的栅格表示环境，由于栅格法的特性，如何选取单个栅格的大小将直接影响路径规划算法的性能。若栅格选得过小，环境地图的精度高，但处理速度慢；栅格选得过大，决策的速度快，但规划路径可能不精确。

1.2 A*算法

A*算法[11]是一种静态路网中求解最短、路最有效的直接搜索方法，也是许多其他问题的常用启发式算法。

公式表示为：

f(a)=g(a)+h(a)

(1)

其中：f(a)是从初始位形经由位形节点a到目标位形的估计代价；g(a)是在位形空间中从初始位形到位形节点的实际代价，即为到达位形节点a已经消耗了的代价；h(a)是从位形节点a到目标位形的最佳路径的估计代价。

从公式中可以看出：启发函数h(a)的设置将直接影响A*算法的路径规划性能。如果h(a)经常比从a移动到目标的实际代价小(或者相等)，则A*保证能找到一条最短路径。h(a)越小，A*扩展的结点越多，运行就越慢。

如果h(a)精确地等于从a移动到目标的代价，则A*将仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，但仍可以在一些特殊情况下让它们精确地相等。只要提供完美的信息，A*会运行得很完美。

如果h(a)有时比从a移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。

2 基于时间的多机器人协调避碰算法

2.1 单机器人路径规划

第一阶段是在忽略机器人间冲突的前提下，规划出各个机器人与环境的无碰路径。该问题属于机器人运动规划的基本问题，即规划处给定机器人的初始位形到目标位形的无碰路径。

2.1.1 环境建模

本文使用栅格法表示环境，记单个栅格的大小为单个机器人的大小，并且此时将障碍物简化为矩形。当障碍物不满一个栅格时将其扩展为一个栅格，并且不规则形状障碍物进行合并或扩展栅格形成规则形状即矩形(如图1所示)。这样，可以使规划路径准确，且决策速度快。

图1 障碍物的合并与拓展

记单个机器人的大小为s×s，D是机器人系统R在二维平面上的矩形有限运动区域，其内部分布着有限个静态障碍物b0,b1,…，bn。以D的左上角为坐标原点O，横向为X轴，纵向为Y轴，建立一个栅格坐标系，X、Y轴的最大值为Xmax、Ymax，以单个机器人的大小作为一个单位栅格，其中bi(i=1,2,…,n)占一个或多个栅格。记a∈D为任意栅格，A为D中所有a的集合，同时B=(b0,b1,…,bn)⊆A为有静态障碍物的栅格集，则不存在障碍物的空间为C=A-B。

所以序号为i的栅格ai的坐标(xi,yi)可用下列公式确定：

(2)

(3)

现在规划的目的是使机器人由任意起点abegin无碰地到达任意终点aend，begin≠end且abegin,aend∈C。

2.1.2改进的A*算法

A*算法虽然广泛应用于移动机器人的自主路径规划中，但是A*算法给出的规划路径转折点过多，不够平滑。故可以设置，若当前节点在父节点的某一方向，则在f(a)值相同的情况下优先选取当前节点同一方向的下一节点。又由于已知起点abegin和终点aend的坐标，例如在起点右边，即abegin的x值比aend小，则先不计算当前节点左边节点的f(a)值，只比较右边和上下节点的f(a)值。只考虑x值的大小。

现将机器人模型简化为质点，机器人路径简化为线。

在搜索路径过程中设置：开启列表openSet——寻路过程中的待检索节点列表；关闭列表closeSet——不需要再次检索的节点列表；追溯表comeFrom——存储父子节点关系的列表，用于追溯生成路径。

相应流程如图2所示。

程序主体：

步骤1 比较abegin、aend的x值大小，若abegin的x值比aend小，则接下来相邻节点不包括当前节点左节点；当abegin的x值比aend大，则接下来再也不考虑当前节点的右节点。将起点abegin加入开启列表openset。

图2 改进A*算法流程

步骤2 寻找开启列表openset中f(a)值最小的节点，设为当前点anow；开启列表openset中移出当前点anow；关闭列表closeset中加入当前点anow。

步骤3 对当前点的相邻节点aneighbor，如果它不可通过或者已经在关闭列表中，略过。否则：若它不在开启列表中，加入开启列表中；若在开启列表中，进行g(a)值判定，若此路径G值比之前路径小，则此相邻点的父节点为当前点，同时更新g(a)与f(a)值。反之，则保持原来的节点关系与g(a)、f(a)值。

当目标点aend在开启列表或当前开启列表为空，则转到步骤4；否则，转到步骤2。

步骤4 结束程序。

当目标点aend在开启列表中，此时有路径生成，此时由aend节点开始逐级追溯上一级父节点，直到追溯到开始节点abegin，此时各节点即为路径。

当开启列表为空，此时没有路径。

2.2 多机器人协调避碰

2.2.1 多机器人系统的碰撞点集

该多机器人系统中所有机器人的静态碰撞路径点集合Q=Q1∪Q2∪…QN，算法伪代码如下：

1. Fori:=1 ToN-1

2. Forj:=i+1 ToN

5. else

6. Continue

7. Sort (Qk)

8.Q=Q1∪Q2∪…QN

2.2.2 基于时间的避碰系统

依次计算出机器人到达每一个碰撞点的时间，判定碰撞点是否真会相撞，再将所有要等待的机器人相应列出，最后得到每一个机器人的运行序列。

伪代码如下：

2. Fori:=1 ToN

4. Fori:=2 ToN

5. Forj:=1 Toi-1

12. Else

3 仿真实验

使用Matlab仿真软件，假设在10×10的D区域中，有容积为3的机器人系统R={R1,R2,R3}，令单个机器人大小为1×1，即单个栅格大小也为1×1，3个机器人以相同的速度v匀速前进。分别给定起点abegin和终点aend的坐标，使用A*算法求得机器人R的路径点集合，如图3所示(黑色为障碍点，绿色为起点，黄色为行进路径点)。

图3 使用传统A*算法机器人R的路径点集合

使用改进的A*算法求得机器人R的路径点集合如图4所示(黑色为障碍点，绿色为起点，黄色为行进路径点)。

图4 使用改进A*算法机器人R的路径点集合

可以明显看出：拐点得到了有效的减少，路径更为平滑，同时得到结果的耗时也有些许优化，如图5所示(其中improve_A为改进的A*算法)。

图5 使用改进A*算法和传统A*算法的耗时对比

图6 使用改进的A*算法机器人Rk(k=1,2,3)的路径点集合

图7 机器人Rk(k=1,2,3)相对应的无碰序列

图8 最终路径序列总耗时

4 结束语

本文提出了通过调节机器人到达碰撞点时间的基于栅格环境离线解耦法，能够有效解决在共享区域空间时多机器人系统的无碰运动规划问题。该方法由两阶段实现，第一阶段使用改进的A*算法得到单个机器人的静态无碰运动序列；第二阶段通过调节机器人抵达碰撞节点栅格的时间来实现机器人之前的无碰运动。

但本文算法的计算量较大，对于大型多机器人系统具有一定的局限性。今后研究将从以下几个方面进行改进：① 改进算法提高运算效率；② 为了获得多机器人系统的最优解决方案，增加优化指标，如时间、能耗等。