文章快速检索  
  高级检索
时效优先的轮式机器人编队避障策略
吴慧超1, 罗元1, 周前能1, 尹云鹏2     
1. 重庆邮电大学光电工程学院, 重庆 400065;
2. 重庆邮电大学通信与信息工程学院, 重庆 400065
摘要: 针对传统轮式机器人编队避障策略存在耗时长、环境适应度差的问题,提出了一种结合路径规划启发函数和最优队形变换的时效优先避障策略.首先,建立机器人编队队形和各队形变换知识库;其次,根据路径启发函数和最优队形变换得到避障耗时评估值,其最小值对应路径即为时效优先的;最后,基于leader-follower(领航跟随者)拓扑,完成避障任务.对该方法进行仿真分析,并与传统的机器人编队避障方法对比.结果表明,所提方法在避障的效率、灵活性方面都更胜一筹.
关键词: 轮式机器人编队     避障     时效优先     路径启发函数     队形变换     耗时评估值    
Obstacle Avoidance Strategy of Wheeled Robot Formations Based on Time Efficiency
WU Huichao1, LUO Yuan1, ZHOU Qianneng1, YIN Yunpeng2     
1. College of Optoelectronic Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;
2. School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
Abstract: To overcome the high time consumption and poor environmental adaptability encountered during obstacle avoidance by a wheeled robot formation, we propose a strategy that combines a heuristic path planning function and an optimal formation transformation. First, we build a base of common robot formation knowledge and transformation time. Second, the optimal obstacle avoidance path is found according to the minimum time-consuming assessment value and calculated with a heuristic function and optimal formation transformation. Finally, the robot formation can pass through the obstacle areas in the topology of leader-follower. The simulation result shows that the proposed method is more effective and flexible compared with the traditional method.
Key words: wheeled robot formation     obstacle avoidance     time efficiency     heuristic path planning function     formation transformation     time-consuming assessment value    

1 引言

多机器人编队控制在合作搬运、安全救援、探险、农业生产等领域有广泛的应用前景[1-6].而多机器人执行任务的过程中,不可避免地会遇到障碍物.现有文献对机器人编队避障的研究大多着眼于路径最短和静态队形变换[7-10](即从一种队形固定地变换为另一种队形).主要方法有:

(1) 基于最短路径的整体避障.即在遇到障碍物的时候,将机器人编队作为一个整体,保持原有队形,以最短路径避开障碍物.这种方式虽然保持了队形,但灵活性不高,无法通过狭长的过道.如文[11]使用障碍物函数来构造导航函数,从而找到无碰且离目标点最短的一系列空间位置,并在此过程中始终保持原始编队队形.

(2) 局部自主避障,即该机器人编队中的每个个体灵活地避开障碍区,当组员全数通过后,再重组原来的队形[12-13].如文[13]采用改进的人工势能场法对避障算法进行优化,使多智能体编队能有效地通过障碍物区域,并在避障后再次形成编队.这种方式灵活程度高,但是队形拆散后再次重组的耗时长且不适用于需要保持强连通的机器人编队.

(3) 动态队形变换避障,如文[14],根据环境的约束条件,选择最优队形避开障碍物.该方法虽然在队形变化方面耗时少,但仍基于最短路径,因而不能保证整个避障过程时效最优.

针对上述问题并考虑到在实际应用中对机器人编队高效率执行任务的需求 (尤其在工业生产和安全救援等分秒必争的领域),本文在基于领航跟随者方法的基础上提出一种结合路径规划启发函数和最优队形变换的时效优先的机器人编队避障策略,该策略主要应用场景为走廊和过道.

2 传统机器人编队避障策略

当多机器人编队遇到障碍物时,文献中通常的处理办法是将原有编队固定变为柱形[8-9],并基于最短路径通过障碍区,如图 1所示.即使区域1和区域2的可通行宽度变化,机器人编队依然以固定柱形从路径较短的区域2通过.

图 1 传统的机器人编队避障方法 Figure 1 Obstacle avoidance of the robots formation with the traditional method
3 时效优先的机器人编队避障策略 3.1 多机器人编队模型建立 3.1.1 多机器人编队队形

图 2所示,菱形、柱形、双排形等都是常用的多机器人编队队形[15].本文将这些典型的机器人队形存入队形知识库.

图 2 机器人编队队形 Figure 2 Robots formation shape
3.1.2 leader-follower队形控制结构

本文参考文[16],得到如图 3所示的leader-follower拓扑的轮式机器人菱形编队模型.其中R1为领航机器人,R2~R4为跟随机器人,RvR2需要跟随的虚拟机器人,与R1保持的期望距离和角度为 (lφ).

图 3 轮式机器人菱形编队 Figure 3 Rhombus shape of the wheeled robots formation
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条:如图中实线和虚线箭头所示,根据本文避障策略:

图 4 机器人编队避障示意 Figure 4 Obstacle avoidance of the robots formation

(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为队形变换后通过障碍物区域消耗的时间.tcitti分别为机器人i进行队形变换的起止时刻,tsptep分别为其通过障碍物区域的起止时刻.

(3) 计算:

(7)

得到该绕行路径的时间消耗预估值.其中,V为领航机器人在安全的障碍物距离下 (本文设置该距离为大于等于1.5倍的机器人外形尺寸宽度) 的行驶速度;Tfs为通过该区域时所需的队形变换时间,该值由步骤 (2) 的环境适应度函数计算过程得到.

(4) 选择T最小值对应的路径即为时效优先的.

(5) 机器人编队以leader-follower扑结构,以 (4) 中选定的路径通过障碍区并完成最优队形变换.

(6) 进入障碍物检测循环.

避障策略的流程图如图 5所示.

图 5 机器人编队的时效优先避障流程 Figure 5 Software flow char diagram of the obstacle avoidance strategy of the robots formation based on time efficiency
4 实验验证

为验证算法可行性,本文进行了Matlab和ROS (robot operating system) 下的仿真验证,并与传统的基于路径最短的柱形编队避障方法对比.

4.1 Matlab仿真研究

实验1 两种算法的仿真结果分别如图 6图 7所示.图中实心圆标识机器人R1~R4,方框为障碍物,星型标记目标点,数字1、2、3表示3个区域,字母A1B1表示障碍物膨化后的边缘,实线及虚线标记了可能的绕行路径.机器人的初始编队为菱形,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.

图 6 机器人编队以本文方法避障 (实验1) Figure 6 Obstacle avoidance of robots formation with the proposed method (experiment 1)
表 1 两种绕行方向的参数对比 (实验1) Table 1 Contrast of the two path direction′s parameters (experiment 1)
指标绕行方向
A1B1
队形变换次数/次02
队形变换时间/s015.37
启发函数f(Q)9.798.63
耗时参考值/s19.5832.63

而文[8-9]所使用的传统柱形编队避障方案,仿真结果如图 7所示.该方案直接选择路径最短的B1方向绕行且不考虑环境的约束,固定地变换为柱形编队避障.

图 7 机器人编队以柱形避障 (实验1) Figure 7 Obstacle avoidance of robots formation with the cylindrical robots formation (experiment 1)

根据图 6图 7表 2的对比可知,本文的避障策略与传统的避障方式相比,虽然路径略长,但综合考虑了最优队形变换,总体耗时更少,因而效率和灵活性都要更高.

表 2 本文方法与固定柱形避障的方法对比 (实验1) Table 2 Comparison between the proposed method and the method of cylindrical robots formation (experiment 1)
指标方法
本文方法传统方法
队形变换次数/次02
队形变换时间/s015.52
路径长度/m10.488.47
总时间/s24.9636.46

实验2 为了验证本文算法的环境适应性,本实验减小了1区域的可通行距离,其它不变.

图 8为采用本文方法的仿真结果,根据绕行方向的参数对比 (见表 3),机器人编队最终从路径1所示路径绕行.其中,区域1易得0.75<ρ<1,因而机器人将菱形队形微缩后通过障碍区1.

图 8 机器人编队以本文方法避障 (实验2) Figure 8 Obstacle avoidance of robots formation with the proposed method (experiment 2)
表 3 两种绕行方向的参数对比 (实验2) Table 3 Contrast of the two path direction′s parameters (experiment 2)
指标绕行方向
A1B1
队形变换次数/次22
队形变换时间/s12.0015.37
启发函数f(Q)9.798.63
耗时参考值/s31.5832.63

各机器人的位置误差曲线如图 9所示.可以看出,在约3 s、12 s处,机器人队形由于环境变化而相应进行变化,于是X方向、Y方向上的位置误差及角度误差efxefyefθ分别增大,并在约3 s的时间内迅速减小并最终趋近于0.

图 9 实验2中各机器人的位置误差 Figure 9 Robots′ position errors in experiment 2

而传统柱形编队避障方案,仍然会从B1方向以固定的柱形编队绕行避障 (与实验1相同).

实验2的对比结果如表 4所示,再次证明了本文能根据环境约束选择优化的队形变换,以时效最优的绕行路径通过障碍区,从而优于传统避障算法.

表 4 本文方法与固定柱形避障的方法对比 (实验2) Table 4 Comparison between the proposed method and the method of cylindrical robots formation (experiment 2)
指标方法
本文方法传统方法
队形变换次数/次22
队形变换时间/s12.0015.52
路径长度/m10.689.11
总时间/s34.5836.78
4.2 ROS平台上的验证

实验平台为配备Intel双核、2.19 GHz主频、1.96 GB内存的笔记本电脑,并安装Linux (Ubuntu10.4) 操作系统和hydro版本的ROS系统,并采用4台装载sick LMS-200激光传感器 (扫描范围为180°,感应距离8 m) 的Pioneer2-DX机器人模型,如图 10所示.

图 10 装载sick激光传感器的4台Pioneer2-DX Figure 10 Four Pioneer-DXs with sick laser sensors

在ROS系统下搭建与本文4.1节中与实验2相同的实验环境 (不再赘述),并对机器人进行如图 11的速度设置,包括最大速度、避障速度、转弯速度等.

图 11 ROS平台下机器人的速度设置 Figure 11 Robots′ speed setting on ROS

仿真结果如图 12所示.首先,机器人在起点 (2,5) 检测到有障碍物于前方遮挡目标点,于是计算可绕行路径的f(Q),并根据队形变换因子ρ>1,进一步判断若从A1方向绕行,耗时参考值为

(9)
图 12 ROS平台上的验证 Figure 12 Validation on ROS

其中TfsA1TfsA3分别为图 12(a)中区域1、区域3的队形变换耗时.

而若从B1方向绕行,在区域2根据队形变换因子ρρm(取ρm=0.75) 可知需要将队形异构变换,通过计算fenvfit可得最佳变换队形为双排型,而在区域3由于ρ>1,要恢复初始菱形编队.于是耗时参考值为

(10)

其中,TfsB2TfsB3为通过区域2、3所需的队形变换时间.由TB1>TA1,于是选择从A1方向绕行避障.绕行方向的各指标对比如表 5所示.如图 12所示,最终机器人编队按照本文策略选择了时效优先的路径,并在避障的过程中选择时效最优的同构压缩队形通过,离开障碍区后恢复原有编队,与传统方法的耗时对比请见表 6.

表 5 两种绕行方向的参数对比 (ROS平台下实验2) Table 5 Contrast of the two path direction′s parameters (experiment 2 on ROS)
指标绕行方向
A1B1
队形变换次数/次22
队形变换时间/s12.0015.37
启发函数f(Q)9.818.68
耗时参考值/s31.6232.73
表 6 本文方法与固定柱形避障方法对比 (ROS) Table 6 Comparison between the proposed method and the method of cylindrical robots formation (on ROS)
指标方法
本文方法传统方法
队形变换次数/次22
队形变换时间/s17.6021.17
路径长度/m10.8810.15
总时间/s39.9543.67

因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.
http://dx.doi.org/10.13976/j.cnki.xk.2017.0211
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

吴慧超, 罗元, 周前能, 尹云鹏
WU Huichao, LUO Yuan, ZHOU Qianneng, YIN Yunpeng
时效优先的轮式机器人编队避障策略
Obstacle Avoidance Strategy of Wheeled Robot Formations Based on Time Efficiency
信息与控制, 2017, 46(2): 211-217.
Information and Contro, 2017, 46(2): 211-217.
http://dx.doi.org/10.13976/j.cnki.xk.2017.0211

文章历史

收稿/录用/修回: 2016-01-05/2016-04-25/2016-05-24

工作空间