2. 重庆邮电大学通信与信息工程学院, 重庆 400065
2. School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
1 引言
多机器人编队控制在合作搬运、安全救援、探险、农业生产等领域有广泛的应用前景[1-6].而多机器人执行任务的过程中,不可避免地会遇到障碍物.现有文献对机器人编队避障的研究大多着眼于路径最短和静态队形变换[7-10](即从一种队形固定地变换为另一种队形).主要方法有:
(1) 基于最短路径的整体避障.即在遇到障碍物的时候,将机器人编队作为一个整体,保持原有队形,以最短路径避开障碍物.这种方式虽然保持了队形,但灵活性不高,无法通过狭长的过道.如文[11]使用障碍物函数来构造导航函数,从而找到无碰且离目标点最短的一系列空间位置,并在此过程中始终保持原始编队队形.
(2) 局部自主避障,即该机器人编队中的每个个体灵活地避开障碍区,当组员全数通过后,再重组原来的队形[12-13].如文[13]采用改进的人工势能场法对避障算法进行优化,使多智能体编队能有效地通过障碍物区域,并在避障后再次形成编队.这种方式灵活程度高,但是队形拆散后再次重组的耗时长且不适用于需要保持强连通的机器人编队.
(3) 动态队形变换避障,如文[14],根据环境的约束条件,选择最优队形避开障碍物.该方法虽然在队形变化方面耗时少,但仍基于最短路径,因而不能保证整个避障过程时效最优.
针对上述问题并考虑到在实际应用中对机器人编队高效率执行任务的需求 (尤其在工业生产和安全救援等分秒必争的领域),本文在基于领航跟随者方法的基础上提出一种结合路径规划启发函数和最优队形变换的时效优先的机器人编队避障策略,该策略主要应用场景为走廊和过道.
2 传统机器人编队避障策略当多机器人编队遇到障碍物时,文献中通常的处理办法是将原有编队固定变为柱形[8-9],并基于最短路径通过障碍区,如图 1所示.即使区域1和区域2的可通行宽度变化,机器人编队依然以固定柱形从路径较短的区域2通过.
3 时效优先的机器人编队避障策略 3.1 多机器人编队模型建立 3.1.1 多机器人编队队形如图 2所示,菱形、柱形、双排形等都是常用的多机器人编队队形[15].本文将这些典型的机器人队形存入队形知识库.
3.1.2 leader-follower队形控制结构本文参考文[16],得到如图 3所示的leader-follower拓扑的轮式机器人菱形编队模型.其中R1为领航机器人,R2~R4为跟随机器人,Rv是R2需要跟随的虚拟机器人,与R1保持的期望距离和角度为 (l,φ).
3.2 机器人编队避障的耗时评价体系 3.2.1 动态队形变换策略本文使用环境适应度函数来评价机器人的目标队形适应当前环境的程度[17].该值越小,表明该队形变换对环境的适应度越好.其定义如式 (1) 所示:
(1) |
其中,Ifdd为队形失真度,Iecr为能量消耗率,Ifcct为队形变换收敛时间比.
接着,引入队形变换因子ρ,定义为
(2) |
其中,Wmax表示障碍物间的最大可通行宽度,W则表示当前机器人队形的宽度.
3.2.2 路径规划的启发式函数路径规划的启发式函数可评价该路径代价[18]:
(3) |
式中,g(Q) 为领航机器人从当前位置运动到Q点的代价,h(Q) 为领航机器人从Q点运动到目标点的代价.
3.3 时效优先的机器人编队避障策略该策略的主要思想为:先建立常用机器人队形知识库,当检测到障碍物时,先由路径规划的启发函数f(Q) 获得可能的避障路径代价;再通过计算环境适应度函数和队形变换因子选择当前避障的最佳队形,二者结合后根据总耗时估值最小确定一条时效最优的避障路径;最后利用leader-follower[19-20]拓扑结构通过障碍区.在图 4所示的场景中,假设环境的信息可以获得,则菱形机器人编队可能的避障路径有2条:如图中实线和虚线箭头所示,根据本文避障策略:
(1) 计算f(Q) 以评价两条绕行路径的代价.
(2) 计算区域1、2的队形变换因子ρ并预测队形变换时间:
① 若ρ>1,则无需队形变换通过障碍区;
② 若ρm<ρ<1,则需将队形进行同构变换;
③ 若ρ<ρm,则需要进行异构队形变换,结合式 (4)~(6),在队形知识库中反复计算fenvfit,将其最小值对应的异构队形作为目标队形:
(4) |
式 (4) 中,Fc为当前队形的参数矩阵,Ft为目标队形参数矩阵,FΔ=Ft-Fc为队形矩阵的变化量.
(5) |
式 (5) 中,Efs为机器人队形变换的能量消耗;Ep为队形变换完成后,机器人编队完全通过障碍区的能量消耗;ψ为机器人两个驱动轮的转角;ψLci、ψLti分别为机器人i队形变换起点、终点左驱动轮的转角值,同理可得ψRci、ψRti;τL、τR为其左右轮输出力矩,n为编队成员总数.
(6) |
其中,Tfs为机器人队形变换消耗的时间,Tp为队形变换后通过障碍物区域消耗的时间.tci、tti分别为机器人i进行队形变换的起止时刻,tsp、tep分别为其通过障碍物区域的起止时刻.
(3) 计算:
(7) |
得到该绕行路径的时间消耗预估值.其中,V为领航机器人在安全的障碍物距离下 (本文设置该距离为大于等于1.5倍的机器人外形尺寸宽度) 的行驶速度;Tfs为通过该区域时所需的队形变换时间,该值由步骤 (2) 的环境适应度函数计算过程得到.
(4) 选择T最小值对应的路径即为时效优先的.
(5) 机器人编队以leader-follower扑结构,以 (4) 中选定的路径通过障碍区并完成最优队形变换.
(6) 进入障碍物检测循环.
避障策略的流程图如图 5所示.
4 实验验证为验证算法可行性,本文进行了Matlab和ROS (robot operating system) 下的仿真验证,并与传统的基于路径最短的柱形编队避障方法对比.
4.1 Matlab仿真研究实验1 两种算法的仿真结果分别如图 6和图 7所示.图中实心圆标识机器人R1~R4,方框为障碍物,星型标记目标点,数字1、2、3表示3个区域,字母A1、B1表示障碍物膨化后的边缘,实线及虚线标记了可能的绕行路径.机器人的初始编队为菱形,R1~R4的初始坐标分别为:(2,5)、(1.5,5.8)、(1.5,4.2)、(1,5).在理想实验环境下且机器人负载不变,大部分时间为匀速运动,可将机器人的左右输出力矩简化为常数τ,两个驱动轮的转角ψ与路程成正比.速度约束如下:
(8) |
其中,vmax=0.8 m/s,ωmax=0.1 rad/s.
如图 6所示,机器人编队按照本文的避障策略先计算两种绕行方向的耗时估计值如表 1所示,并最终选择耗时估计值小的路径1.
而文[8-9]所使用的传统柱形编队避障方案,仿真结果如图 7所示.该方案直接选择路径最短的B1方向绕行且不考虑环境的约束,固定地变换为柱形编队避障.
根据图 6、图 7、表 2的对比可知,本文的避障策略与传统的避障方式相比,虽然路径略长,但综合考虑了最优队形变换,总体耗时更少,因而效率和灵活性都要更高.
实验2 为了验证本文算法的环境适应性,本实验减小了1区域的可通行距离,其它不变.
图 8为采用本文方法的仿真结果,根据绕行方向的参数对比 (见表 3),机器人编队最终从路径1所示路径绕行.其中,区域1易得0.75<ρ<1,因而机器人将菱形队形微缩后通过障碍区1.
各机器人的位置误差曲线如图 9所示.可以看出,在约3 s、12 s处,机器人队形由于环境变化而相应进行变化,于是X方向、Y方向上的位置误差及角度误差efx、efy、efθ分别增大,并在约3 s的时间内迅速减小并最终趋近于0.
而传统柱形编队避障方案,仍然会从B1方向以固定的柱形编队绕行避障 (与实验1相同).
实验2的对比结果如表 4所示,再次证明了本文能根据环境约束选择优化的队形变换,以时效最优的绕行路径通过障碍区,从而优于传统避障算法.
实验平台为配备Intel双核、2.19 GHz主频、1.96 GB内存的笔记本电脑,并安装Linux (Ubuntu10.4) 操作系统和hydro版本的ROS系统,并采用4台装载sick LMS-200激光传感器 (扫描范围为180°,感应距离8 m) 的Pioneer2-DX机器人模型,如图 10所示.
在ROS系统下搭建与本文4.1节中与实验2相同的实验环境 (不再赘述),并对机器人进行如图 11的速度设置,包括最大速度、避障速度、转弯速度等.
仿真结果如图 12所示.首先,机器人在起点 (2,5) 检测到有障碍物于前方遮挡目标点,于是计算可绕行路径的f(Q),并根据队形变换因子ρ>1,进一步判断若从A1方向绕行,耗时参考值为
(9) |
其中TfsA1、TfsA3分别为图 12(a)中区域1、区域3的队形变换耗时.
而若从B1方向绕行,在区域2根据队形变换因子ρ<ρm(取ρm=0.75) 可知需要将队形异构变换,通过计算fenvfit可得最佳变换队形为双排型,而在区域3由于ρ>1,要恢复初始菱形编队.于是耗时参考值为
(10) |
其中,TfsB2和TfsB3为通过区域2、3所需的队形变换时间.由TB1>TA1,于是选择从A1方向绕行避障.绕行方向的各指标对比如表 5所示.如图 12所示,最终机器人编队按照本文策略选择了时效优先的路径,并在避障的过程中选择时效最优的同构压缩队形通过,离开障碍区后恢复原有编队,与传统方法的耗时对比请见表 6.
因ROS平台下的仿真综合考虑了机器人的几何尺寸、传感器数据采集及速度设置等因素,更接近真实环境,因而再次验证了本文避障策略的可行性.
5 结论本文提出的时效优先的多机器人编队的避障策略,结合路径规划的启发性函数和最优变形变换获得时效优先的避障路径,既克服了传统的机器人编队避障算法只着眼于路径最短而带来的耗时缺陷,又兼顾了机器人编队的最优队形变换,从以上两个方面实现了时效最优的原则,从而可以灵活避障.从仿真结果可以看出,本文提出的机器人编队避障策略,智能化程度更高,耗时更少.当然,本文也存在一定的局限性,如在机器人编队方面,采用了控制简单、应用广泛的leader-follower策略,并没有对可能发生的异常情况进行深入研究;在实际应用方面,由于多机器人编队避障策略涉及的技术领域广且需要考虑诸多实际细节,因而将其在物理上稳定实现仍亟待解决.后续将在这两方面做进一步研究.
[1] | Wang Z Y, Gu D B. Cooperative target tracking control of multiple robots[J]. IEEE Transactions on Industrial Electronics, 2012, 59(8): 3232–3240. DOI:10.1109/TIE.2011.2146211 |
[2] | Mas I, Kitts C. Obstacle avoidance policies for cluster space control of nonholonomic multirobot systems[J]. IEEE/ASME Transactions on Mechatronics, 2012, 17(6): 1068–1079. DOI:10.1109/TMECH.2011.2159988 |
[3] | Franchi A, Freda L, Oriolo G, et al. The sensor-based random graph method for cooperative robot exploration[J]. IEEE/ASME Transactions on Mechatronics, 2009, 14(2): 163–175. DOI:10.1109/TMECH.2009.2013617 |
[4] | Ferruz J, Vega V M, Ollero A, et al. Reconfigurable control architecture for distributed systems in the HERO autonomous helicopter[J]. IEEE Transactions on Industrial Electronics, 2011, 58(12): 5311–5318. DOI:10.1109/TIE.2010.2046003 |
[5] | Zhang H W, Lewis F L, Qu Z H. Lyapunov, adaptive, and optimal design techniques for cooperative systems on directed communication graphs[J]. IEEE Transactions on Industrial Electronics, 2012, 59(7): 3026–3041. DOI:10.1109/TIE.2011.2160140 |
[6] | Yamashita A, Arai T, Ota J, et al. Motion planning of multiple mobile robots for cooperative manipulation and transportation[J]. IEEE Transactions on Robotics and Automation, 2003, 19(2): 223–236. DOI:10.1109/TRA.2003.809592 |
[7] | Heonyoung L, Yeonsik K, Kim J, et al. Formation control of leader following unmanned ground vehicles using nonlinear model predictive control[C]//IEEE/ASME International Conference on Advanced Intelligent Mechatronics. Piscataway, USA:IEEE, 2009:945-950. |
[8] | Chen H Y, Sun D, Yang J, et al. Localization for multirobot formations in indoor environment[J]. IEEE/ASME Transactions on Mechatronics, 2010, 15(4): 561–574. DOI:10.1109/TMECH.2009.2030584 |
[9] | 王小亮, 陈健. 多机器人协同队形变换算法与实现[J]. 计算机仿真, 2013, 30(8): 327–330. Wang X L, Chen J. Algorithm and implement for formation change based on multi robots cooperation[J]. Computer Simulation, 2013, 30(8): 327–330. |
[10] | Panagou D, Kumar V. Cooperative visibility maintenance for leader-follower formations in obstacle environments[J]. IEEE Transactions on Robotics, 2014, 30(4): 831–844. DOI:10.1109/TRO.2014.2304774 |
[11] | 杨甜甜, 苏治宝, 刘进, 等. 多移动机器人编队控制[J]. 计算机仿真, 2011, 28(9): 215–218. Yang T T, Su Z B, Liu J, et al. Formation control and obstacle avoidance for multiple mobile robots[J]. Computer Simulation, 2011, 28(9): 215–218. |
[12] | Johnson E N, Calise A J, Sattigeri R, et al. Approaches to vision-based formation control[C]//43rd IEEE Conference on Decision and Control (CDC). Piscataway, NJ, USA:IEEE, 2004:1643-1648. |
[13] | 代冀阳, 殷林飞, 杨保建, 等. 一种矢量人工势能场的多智能体编队避障算法[J]. 计算机仿真, 2015, 32(3): 388–392. Dai J Y, Yin L F, Yang B J, et al. A multi-agent algorithm of obstacle avoidance based on vectorial artificial potential field[J]. Computer Simulation, 2015, 32(3): 388–392. |
[14] | Ren L M, Wang W D, Du Z J, et al. On a laser rangefinder-based mobile robot obstacle avoidance strategy via local virtual target[J]. Laser in Engineering, 2013, 25(3/4): 205–223. |
[15] | 杨丽, 曹志强, 谭民. 不确定环境下多及机器人的动态编队控制[J]. 机器人, 2010, 32(2): 283–284. Yang L, Cao Z Q, Tan M. Dynamic formation control for multiple robots in uncertain environments[J]. Robot, 2010, 32(2): 283–284. |
[16] | 张瑞雷, 李胜, 陈庆伟. 车式移动机器人动态编队控制方法[J]. 机器人, 2013, 35(6): 651–656. Zhang R L, Li S, Chen Q W. Dynamic formation control for car-like mobile robots[J]. Robot, 2013, 35(6): 651–656. |
[17] | 任立敏, 王伟东, 杜志江, 等. 障碍物环境下多机器人动态优化队形变换[J]. 机器人, 2013, 35(5): 535–543. Ren L M, Wang W D, Du Z J, et al. Dynamic and optimization formation switching for multiple mobile robots in obstacle environments[J]. Robot, 2013, 35(5): 535–543. |
[18] | 洪伟. 移动机器人系统中分布式传感器信息融合方法及路径规划问题的研究[D]. 长春: 吉林大学, 2004. Hong W. Research on distribute multisensory information fusion and path planning in mobile robot system[D]. Changchun:Jilin University, 2004. |
[19] | 高杨, 张华飞. 基于领航跟随法和星系动力学的多机器人编队控制[J]. 厦门大学学报:自然科学版, 2013, 52(1): 14–18. Gao Y, Zhang H F. A multi-robot formation control based on the pilot follow method and galactic dynamics[J]. Journal of Xiamen University:Natural Science, 2013, 52(1): 14–18. |
[20] | Loria A, Dasdemir J, Alvarez J N. Leader-follower formation and tracking control of mobile robots along straight paths[J]. IEEE Transactions on Control Systems Technology, 2015, 24(2): 727–732. |