重庆理工大学学报(自然科学)

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

分类:重点推荐 发布时间:2019-04-30 16:06 访问量:1109

分享到:



本文引用格式李波,易洁.基于时间的多机器人协调避碰算法研究[J].重庆理工大学学报(自然科学),2019,33(3):91-97.

Citation format:LI Bo, YI Jie.The Time-Based Multi-Robot Coordinated Collision Avoidance Algorithm[J].Journal of Chongqing University of Technology(Natural Science),2019,33(3):91-97.


作者简介李波,男,教授,硕士生导师,主要从事大数据与人工智能研究,E-mail:libo@cqut.edu.cn;易洁,女,硕士研究生,主要从事大数据与机器学习研究。



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

李 波,易 洁

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

 针对现有多机器人协调避碰问题,提出了一种基于时间的多机器人协调避碰规划算法。首先,对机器人系统使用改进的栅格法进行环境建模,将其转化为一个关于机器人动作序列的问题。然后运用解耦法,第1阶段在构建好的模型中利用改进的A*算法规划单个机器人的静态无碰路径;第2阶段通过错开时间修改运动序列的方式实现多机器人之间无冲突的运动,即可达到多机器人协调避碰规划的目的。仿真实验结果表明:所设计的基于时间的多机器人协调避碰规划算法能够有效地实现多机器人的避碰路径规划。

  多机器人系统;路径规划;协调避碰

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

对于共享工作空间的多机器人系统的无碰路径规划,需要解决以下两个主要问题:一是对于给定的任务,机器人相对于静态障碍物的无碰路径规划;二是多机器人相互之间的无碰协调运动路径规划[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×sD是机器人系统R在二维平面上的矩形有限运动区域,其内部分布着有限个静态障碍物b0,b1,…,bn。以D的左上角为坐标原点O,横向为X轴,纵向为Y轴,建立一个栅格坐标系,XY轴的最大值为XmaxYmax,以单个机器人的大小作为一个单位栅格,其中bi(i=1,2,…,n)占一个或多个栅格。记aD为任意栅格,AD中所有a的集合,同时B=(b0,b1,…,bn)?A为有静态障碍物的栅格集,则不存在障碍物的空间为C=A-B

?aA在坐标系中都有确定的坐标(栅格中心点坐标即为该栅格坐标)(x,y)。令S={1,2,3,…,M}为栅格序号集,即对应序号为1,记为对应序号为2,记为对应序号为Xmax/s+1,记为aXmax/s+1。当Xmax不能被s整除时,将余数部分舍弃,即每行最多有mmax=Xmax/s个栅格。

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


(2)


(3)

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

2.1.2 改进的A*算法

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

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

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

相应流程如图2所示。

程序主体:

步骤1 比较abeginaendx值大小,若abeginx值比aend小,则接下来相邻节点不包括当前节点左节点;当abeginx值比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 多机器人系统的碰撞点集

机器人系统R中拥有N个机器人{R1,R2,…,RN},经过上一步骤可得每个机器人从abeginaend在运动区域D中的静态无碰路径点,即机器人Rk的路径点集合为其中Hk代表机器人Rk的路径点集合的尺寸。若两个机器人路径点集合交集不为空,则称这两个机器人路径图元发生碰撞,交集中的路径点即为碰撞点。机器人Rk与其他所有机器人的路径碰撞点组成Rk的静态碰撞点集合Qk,其中Qk?Lk。并且将之与路径点集比较,按照路径点集中节点的顺序对Qk中的节点进行排序,使路径图元遇到第1个碰撞点的下标为0,第2个碰撞点的下标为1,即其中Gk代表机器人Rk的碰撞点集合的尺寸。

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

Given:机器人Rk的路径点集用Qk(即碰撞点集)记录机器人Rk的碰撞点

1. For i:=1 To N-1

2. For j:=i+1 To N

?



5. else

6. Continue

7. Sort (Qk)

8. Q=Q1Q2∪…QN

2.2.2 基于时间的避碰系统

设所有机器人都以匀速运动,记机器人Rk的速度为vk,机器人速度集为V={v1,v2,…,vn},则可知在某一碰撞点多个机器人的抵达时间不一定相等。故可设RkRn基于路径图元发生碰撞,但因抵达时间不一致,即当Rk离开碰撞点时与Rn恰好抵达碰撞点时不一致,就说RkRn不发生碰撞。即Rk先抵达时,Rn(栅格大小为s×s)后抵达则不发生碰撞;Rn先抵达时,Rk后抵达则不发生碰撞。

定义 Rk抵达终点的全路程为Tk=Hk×s,路径点集碰撞点集为则抵达第一个碰撞点前需要经过的路程计算如下:

由于所以则Rk抵达第一个碰撞点所需时间为例如,当N=2时,是机器人R1R2的一个碰撞点,R1在启动后抵达在启动后抵达R1R2同时启动:当时,证明R1R2不会碰撞;当时证明R1R2不会碰撞。此时可将R1R2的碰撞点集中删除。令R1R2错时启动,R1启动tR2才启动,则R2时间是其他与前一情形一致。

若两个机器人不符合上述情况,则在碰撞点发生碰撞,此时需要确定机器人优先级,让其中一个机器人先行,另一机器人在原地等待。当RkRn碰撞时,其中一个机器人的等待时间设为本文机器人优先级的确定以多机器人系统完成特定的任务周期时间最短为优化目标,以碰撞点集Qk的尺寸大小Gk作为衡量代价,因为碰撞点越多(Gk越大),可能需要等待的时间越长,碰撞点少(Gk越小),需要等待的时间就越短。

首先根据Gk的大小确定机器人的优先级序列,即得到一个有序的机器人集:此时机器人不用等待,从机器人开始可能需要等待,只参考与优先级比机器人高的机器人与之碰撞点:


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

伪代码如下:

新碰撞点集记为Jk,集合tk代表机器人Rk(未排序时)抵达终点前所有碰撞点所用的时间,抵达碰撞点的时间记为:

1. 根据机器人R={R1,R2,…,RN}的Gk值排序,得

2. For i:=1 To N


4. For i:=2 To N

5. For j:=1 To i-1



?, x=1,2,3,…,i-1




12. Else


则得到机器人系统R={R1,R2,…,RN}中的每一个机器人相对应的需要等待的碰撞点即可得到机器人相应的无碰序列。

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*算法的耗时对比

首先使用改进的A*算法求得机器人Rk(k=1,2,3)的路径点集合为再使用基于时间的避碰系统得到机器人Rk(k=1,2,3)对应的无碰序列(蓝色、红色、灰色分别代表3个机器人的最终路径)。得到的最终路径序列总耗时如图8所示。实验结果表明:该方法可行,且耗时在接受范围内。


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


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


图8 最终路径序列总耗时

4 结束语

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

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

参考文献:

[1] WU H M,SU M J,GUAN Y S,et al.Collision-free Motion Planning for Multiple Robots Using Dynamic Modification of Operating Sequence[J].ROBOT,2016,38(6):651-658.

[2] WANG W H,CHEN W D,XI Y G.Uncertain In Information Based Map-Building Of Mobile Robots In Absolutely Unknown New Environment[J].ROBOT,2001,23(6):563-568.

[3] ZHANG Y,FU M Y,WANG M L.A method about state-space representation and location estimation by computational geometry[C]//Control & Decision Conference.Shanghai,IEEE,2014:4579-4583.

[4] HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE transactions on Systems Science and Cybernetics,1968,4(2):100-107.

[5] 徐飞.基于改进人工势场法的机器人避障及路径规划研究[J].计算机科学,2016,43(12): 293-296.

[6] 刘国栋,谢宏斌,李春光.动态环境中基于遗传算法的移动机器人路径规划的方法[J].机器人,2003,25(4):327-330.

[7] YU Z Z,YAN J H,ZHAO J,et al.Mobile Robot Path Planning Based On Improved Artificial Potential Field Method[J].Journal of Harbin Institute of Technology,2011,43(1):50-55.

[8] 徐昕,沈栋,高岩青,等.基于马氏决策过程模型的动态系统学习控制:研究前沿与展望[J].自动化学报,2012,38(5):673-687.

[9] 陈学松,刘富春.一类非线性动态系统基于强化学习的最优控制[J].控制与决策,2013,28(12):1889-1893.

[10] 夏梁盛,严卫生.基于栅格法的移动机器人运动规划研究[J].计算机仿真,2012,29(12):229-233.

[11] 曲道奎,杜振军,徐殿国,等.移动机器人路径规划方法研究[J].机器人,2008,30(2):97-101.