基于改进分配法的多智能体队形形成

陈 梅,梅 乐,陈艳燕

(合肥工业大学 电气与自动化工程学院,安徽 合肥 230009)



基于改进分配法的多智能体队形形成

陈 梅,梅 乐,陈艳燕

(合肥工业大学 电气与自动化工程学院,安徽 合肥 230009)

多机器人是当今研究热点,机器人编队是多机器人的一个重要问题,编队行为在自然界中广泛存在,大雁、鱼群的有秩序的聚集并编队运动启示编队运动具有重要的意义和作用。文章针对多机器人队形问题,提出了一个基于多智能体(multi-agent)结构的优化算法,多智能体的体系结构具有良好的自适应特点,适合运用到多机器人控制中,对于队形形成问题,改进分配算法具有良好的特性。

多智能体;多机器人;队形形成;改进分配算法

0 引 言

关于多智能体队形形成的问题研究,主要需要解决的是各个智能体如何确定自身的队形目标点以及如何快速无碰撞地到达目标点。文献[1]提出对直线队形和圆形队形形成的算法,这一类方法可以归为传统方法,也有学者运用势场法进行问题的求解；文献[2]用相对距离来确定队形并采用分布式的导航函数形成队形；文献[3]通过自主切换控制率形成期望队形;文献[4]研究了未指定队形位置的群体队形聚集方法;文献[5]提出了基于梯度的分散式控制率,这种方法使机器人群体收敛到某种队形。

基于多智能体的机器人系统主要是借鉴多智能体系统的拓扑结构来构建体系结构。体系结构是多机器人系统研究的重要内容,通常将体系结构分为群体和个体体系结构。本文仅根据多个智能体的初始分布情况来选择形成常用编队队形中的某种队形,这样可以避免智能体的移动距离过远,并减少智能体之间的冲突发生情况。对于队形形成中的路径规划,在选择好编队队形后,通过各个联盟体中的通信智能体进行各自的规划,然后分享各自的规划结果后再根据几项指标择优,来完成队形目标点的分配。

1 智能体模型

智能体(agent)可以指一个具有自治能力的、能够自适应的、以认识与模拟人类某种智能行为为目标的硬件、软件或其他实体。作为智能体,应具有自治能力、社交能力、反应能力以及主动性,能够感知周围的环境,自治地运行,并能够影响和改变环境[6]。智能体由3个基本部分组成,如图1所示。

图1 智能体通用模型

智能体都有一个感知器来感知外部环境,能根据环境的状态来改变自己的结构和内部状态,同时通过一个效应器作用于外部环境,改变外部环境的状态[7]。近年来将多智能体系统的理论应用到多机器人系统中去,基本思想都是将每个机器人视为具有智能行为的智能体,从而借鉴多智能体系统理论来研究多机器人系统。本文将沿用这个思想,将两轮差动的智能移动机器人模型视为智能体。

图2 运动模型

由模型可知:

(1)

智能体的旋转半径可以表示为:

(2)

可以看出:当vL=vR时,Rω→∞,智能体沿直线行走;当vL=-vR时,Rω=0,智能体在原地旋转,旋转半径为0;其余情况下,智能体做圆弧运动。

本文智能体的感知器模拟声纳传感器的工作机制来探测周围环境,其分布示意图如图3所示。该传感器仅探测智能体的前进方向及其正负45°范围内的障碍物或智能体,因此设立3个传感器,分别分布在前进方向正前方,以及与正前方相隔±45°的方向,从左到右标号为传感器1～3,探测半径设为700 cm,感知障碍物和智能体,并确定其方位。

图3 智能体传感器分布示意图

2 队形形成及其选择算法

目标位置优化选择算法[9]按照距离进行队形点的优化分配规划:

(1) 计算所有队形点与所有智能体之间的距离,存入距离信息矩阵。

(2) 对每个队形点,将各个智能体与其的距离ρ进行一个排序,将智能体按照最小ρ初步分配队形点。

(3) 在队形点初步分配之后,若出现多个智能体同时竞争一个队形点的情况,比较进行竞争的智能体的状态,将队形点分配给相距队形点距离较远的智能体。

(4) 更新距离信息矩阵,继续队形点的分配,直到完成队形点分配。

目标位置优化选择算法能够在一定程度上优化分配,减少队形形成间的冲突,快速地形成队形;但其仅将智能体与目标点的直线距离作为一个衡量标准,忽略了智能体方向角的问题,而通常智能体作为移动式机器人时,是无法以任意的角度进行运动的,因此该算法并不能保证这个优化结果是时间上最优的结果。

2.1 队形形成中的路径规划

队形形成问题中要进行路径规划首先要解决队形选择问题。多智能体的编队通常采用“一”字形、柱形、“人”字形等一些形状对称的队形,如图4所示。

图4 常用编队队形

一个合理的队形对于完成任务的效率有很大的影响,比如为了捕捉猎物,必须选择大圆形或小圆形的队形,又如在比较复杂、障碍物比较多的环境中,采用柱形的队形能更有效地避开障碍物。

2.2 队形选择生成方法

利用智能体群体的分布情况,本文提出一种比较简单的队形选择生成的方法:

(1) 收集所有智能体的信息状态。

(2) 收集好信息之后,记录当前工作正常的智能体数量以及各个智能体的位姿情况。

(3) 将各个智能体横坐标以及纵坐标分别形成向量,计算2个向量的均方差σx与σy,这2个均方差值分别代表了智能体群体在x轴与y轴的分散程度。

(4) 将2个均方差相减得到σΔ,与一个根据仿真所得到的经验临界值σλ进行比较,判断接近于哪个队形。

(5) 队形选择完毕之后,以智能体当前分布的横纵坐标平均值为队形中心,按照一定的队形点距离生成与工作正常的智能体一致数量的队形点目标。队形选择生成流程如图5所示。

图5 队形选择生成流程

2.3 改进分配法

针对静态队形形成,本文的队形选择生成使得队形图的生成更加智能,有利于下一步的目标点分配;相比于目标位置优化选择算法,本文结合其优点,考虑智能体角度方面的影响,提出了改进的目标点优化分配法，即改进分配法。

改进分配法规划过程如下:

(1) 将前面生成的队形点信息、收集到的所有智能体的位姿信息及智能体的数量送入规划控制器,计算所有队形点与所有智能体之间的距离,存入距离信息矩阵。

(2) 对每个队形点,将各个智能体与其的距离ρ进行一个排序,可以得到各个智能体对于每个队形点的远/近情况。

(3) 将队形点进行一个初步分配,每个智能体选出距离ρ最小或者在一定的误差范围内的所有队形点。

(4) 在队形点初步分配之后,通常会出现多个智能体同时竞争一个队形点的情况,这时虽然从个体自私的角度考虑是各自最理想的状态,但整体上看是不能满足每个智能体要求的,因此要从整体上再次进行调整分配,解决分配冲突。

(5) 使用新的距离信息矩阵,重复步骤(2)～步骤(4)的分配过程,直到不再出现有冲突的队形点,再将其余队形点依次按其最优的分配即步骤(2) 、步骤(3)的方法进行配对即可。最后输出队形点的分配信息,并按步骤(3)的方法输出分配信息中最大距离ρ以及相应的角度δe,同时输出总距离以及总角度。流程图如图6所示。

图6 改进分配法的流程

计算智能体当前角度δc与各队形点的期望运动角度δR、相差角度δe最小的队形点,如图7所示。

图7 智能体和目标点

智能体当前位姿为[xcycδc]T,某一队形目标点为[xRyR]T,当智能体与队形点的直线方向角度δR与智能体当前角度δc相差较大时,即使两者之间直线距离比较短,但仍需要先将角度调整到期望运动角度再直行,或者弧线进行运动绕行,这不仅浪费时间,还容易增加智能体之间的碰撞几率。

因此对于只考虑了智能体与队形点直线距离进行分配的目标位置优化选择算法,本文提出的改进分配法同时考虑了智能体与队形目标点的距离以及角度,有利于队形的快速生成。

3 Matlab仿真

选用5个智能体,位姿任意指定,并假设所有智能体工作都正常,没有故障。仿真环境为无障碍(60×40) m2的地区,智能体用小圆球表示,车身半径取0.6 m,车轮半径取0.08 m,智能体的朝向在图中形象地表示出来。最大距离表示为maxLen,最大距离对应的转弯角为maxtheta,单位为弧度,总直线距离为totalLen,总转弯角为totaltheta,单位为弧度,完成时步数为step。对使用改进分配法和不使用改进分配法进行仿真实验,结果如图8所示,其中图8b、图8d、图8f、图8h为使用了改进分配法的仿真结果。图8a、图8b中各个智能体初始位姿矩阵相同,最终输出分别为:

图8c、图8d中各个智能体初始位姿矩阵相同,最终输出分别为:

图8e、图8f中各个智能体初始位姿矩阵相同,最终输出分别为:

图8g、图8h中各个智能体初始位姿矩阵相同,最终输出分别为:

图8 仿真实验结果

4 结 论

从图8可以看出,规划器按照智能体的分布智能选择更易形成的队形方案,形成步数都非常少,在50步左右就完成了队形形成。从输出看出,不使用分配法,增大了运用步数,增长了行走的总距离,而且还容易发生碰撞。另外,对于中小数量的智能体,改进分配法使用的是直接决策方法,对比于决策性算法,具有一定的时间优势。但是对于数量比较多的智能体,分析的内容太多,不具有优势,需要加入优化策略改进。

对比图8a、8c、8e、8g和图8b、8d、8f、8h可以发现,每个队形的分配都很合理,图8b中以最简洁的分配形成“一”字形队形。图8d中左一智能体和左四智能体的分配考虑了转弯角。如果不考虑转弯角,即左一和左四两者分配对调,那么两智能体都将转弯180°左右,整体会更耗时。因此从整体考虑,采用改进分配法更好地实现了队形形成。图8f中的分配右一和左一智能体在规划中出现过冲突,但是以本文的比较参数来看,参数设定是合理的,对于左一智能体而言,2条路径之差大于轮子转动一圈的长度,因此选择当前的分配,这样的分配也避免了2个智能体之间运动过程中的碰撞情况;图8h中可以更明显地看出分配冲突的发生,5个智能体之间相互都有选择的冲突,从最终的输出参数来看,整体的分配比较均匀,能以较快的速度形成队形,证明了该文算法的合理性和有效性。

[1] SUGIHARA K,SUZUKI I.Distributed algorithms for formation of geometric patterns with many mobile robots[J].Journal of Robotic Systems,1996,13(3):127-139.

[2] DE GENNARO M C，JADBABAIE A.Formation control for a cooperative multi-agent system using decentralized navigation functions[C]//Proceedings of the 2006 American Control Conference，Minnesota:IEEE,2006:6.

[3] FIERRO R，DAS A K，VIJIAY KUMAR R，et al.Hybrid control of formations of robots[C]//Proceedings of the 2001 IEEE Internoational Conference on Robotics and Automation Vol 1 IEEE，2001:157-162.

[4] BELTA C，KUMAR V.Abstraction and control for groups of robots[J].IEEE Transactions on Robotics，2004，20(5): 865-875.

[5] HSIEH M A，KUMAR V，CHAIMOWICZ L.Decentralized controllers for shape generation with robotic swarms[J].Robotica，2008，26(5):691-701.

[6] 张进.基于智能体的多机器人协作的仿真系统[D].南京:南京理工大学，2003.

[7] 倪建军.复杂系统多Agent建模与控制的理论及应用[M].北京:电子工业出版社，2011.

[8] 郁伉,肖本贤,李艳红.受非完整性约束的移动机器人路径跟踪算法[J].合肥工业大学学报(自然科学版),2010,33(9):1315-1319.

[9] 李强.基于多智能体系统的机器人队形控制与协作研究[D].无锡:江南大学，2011.

(责任编辑 张 镅)

Formation of multi-agent based on improved distribution algorithm

CHEN Mei,MEI Le,CHEN Yanyan

(School of Electric Engineering and Automation, Hefei University of Technology, Hefei 230009, China)

Multi-robot is the focus of present research. Robot formation is of importance in multi-robot research. Formation exists widely in nature, and the orderly aggregation and formation movement of geese and fish shows the great significance and effect of formation. Aiming at the formation of multi-robot, an improved algorithm based on the multi-agent structure is put forward. The structure of multi-agent has good adaptive characteristic, which is suitable for the multi-robot control. The improved distribution algorithm has good characteristic for formation.

multi-agent; multi-robot; formation; improved distribution algorithm

2015-04-28；

2015-07-08

陈 梅(1963-),女,安徽合肥人,合肥工业大学副教授,硕士生导师.

10.3969/j.issn.1003-5060.2016.10.008

TP273.5

A

1003-5060(2016)10-1336-05