基于包围圆的多智能体绕行算法研究

李林钢，冯开平

（广东工业大学 机电工程学院，广东 广州 510006）

基于包围圆的多智能体绕行算法研究

李林钢，冯开平

（广东工业大学 机电工程学院，广东 广州 510006）

探讨了基于包围圆的多智能体碰撞检测和绕行算法.在绕行中避免智能体重叠方面，依据两圆之间位置关系与接近和远离的检测，提出了改进的前向预防碰撞检测方法，提升了数值健壮性.在智能体间的绕行方面，提出了在总体时间复杂度为O（n2）时，对单个智能体和多个智能体的绕行算法，以及对多智能体的提前绕行算法.实验结果表明，在总体接近目标的效果方面，多智能体绕行算法优于单智能体绕行算法，多智能体提前绕行算法优于其不提前绕行算法.

多智能体；包围圆；碰撞检测；绕行算法

目前，游戏中的图像和音效技术都得到了很大的进步，但人工智能方面的理论与应用还有待深入研究［1］.在RTS、RPG等游戏中，常常需要处理多个角色单位间的位置关系，其中的一个典型问题就是，在不发生相互重叠的前提下，多个智能体角色如何一步步行走到同一个目标点.常用的解决方法是，将每个智能体分别设置障碍和可见点进行A*寻路，如Local Repair A*（LRA*）算法［2］，但其容易出现计算量过大、循环依赖和死锁等现象［3］.为了解决计算量过大的问题，并行的方法如利用GPU［4］能起到较好的效果，但需要特定的硬件来提供支持.为了让智能体能够在连续的空间内顺利地到达目标点，且能保证一定的运行效率，同时便于用软件实现，本文从障碍物绕行本身趋向的特性入手，以智能体中具有旋转不变性的包围圆作为研究对象，构建了在单线程整体时间复杂度为O（n2）时，整体位置尽可能地接近目标点的智能体碰撞检测和绕行算法.

1　多智能体之间碰撞检测方法的改进

在模拟智能体群行进的过程中，如果不考虑相互重叠的情况，则容易产生大量智能体单位聚集在一点的现象，这也不符合实际情况，为此，首先要对智能体单位发生的碰撞进行检测.考虑到在实际的应用中，智能体单位的运动包括前后平移和以一定角速度旋转以变换朝向等，而圆作为包围体具有简洁和旋转不变性的特点，因此可以用包围圆替代智能体单位来进行碰撞检测和寻路.

对于2个智能体的包围圆，按圆心距可将二者的位置关系分为外离、外切、相交、内切和内含5种类型.由于智能体的实际形状往往不是精确的圆形，其实际面积通常明显小于包围圆的面积，因此可以将外切和外离两种位置关系视为没有碰到，其余的视为碰到.令圆的半径分别为r1和r2，圆心距为d，对于碰到的情况通常有：

由于计算机往往以浮点数进行计算，智能体单位在移动后出现的误差会导致包围圆之间的互相嵌入，造成死锁现象.为此，尝试考虑一个单位与另一个单位靠近与远离的情况以提升数值健壮性.由于本文提到的算法均为单线程运行，即同一时刻只能移动一个智能体单位，因此只需考虑其中一个智能体的速度方向即可.设这个智能体的速度向量为v1，到另一个智能体的连线向量为d1，则对于靠近的情形有：

由于每个智能体的碰撞检测对象必须是所有的其他物体，不能包括自身，因此，可以将圆心距过近的“两个单位”排除.设要排除的过近圆心距的阈值为dmin（0≤dmin≪min（r1， r2）），结合上述公式，碰撞判别式有：

在多智能体的碰撞检测和移动过程中，为了进一步提高数值健壮性，可以采用前向预防的方法［5］.即检测它们中的某个单位下一时刻的位置是否碰到其他单位，如果没有碰到，则立即移动到这个位置，再检测下一个单位，以此循环.

2　多智能体之间绕行算法的构建

2.1一个智能体对单个智能体的绕行算法

当2个智能体大体上沿同一个方向运动而相对位置却在逐渐靠近时，将导致最终只有个别单位到达目标点，如图1所示.对此，需要考虑一个智能体对单个智能体的绕行方法.如图2和图3所示，令图中的x轴方向向右，y轴方向向上（下同），设某个智能体A到目标点的方向向量为v1（v1x，v1y），前方有另一个智能体B，A圆心到B圆心的连线为d（dx， dy）.则当v1×d垂直于纸面向里，即v1xdy-v1ydx＜0时，A将沿B的左侧绕行；反之当v1×d垂直于纸面向外，即v1xdy-v1ydx＞0时，A将沿B的右侧绕行；当v1xdy-v1ydx=0时，A沿着B的两侧都可以绕行.

图1　相互靠近的一种情况

图2　向左绕行

图3　向右绕行

对于绕行后的速度向量v2有v2⊥d.当向左绕行时，v2∞（-dy,dx）；当向右绕行时，v2∞（dy，-dx）.

2.2一个智能体对多个智能体的绕行算法

如图4所示，智能体A的前方有智能体B和C，当A的绕行方向在B和C之间时，A无法通过.这时，需要对A旁边的多个智能体单位进行共同讨论.

对于等半径的情况，最多能有3个单位在智能体A的前方，如图5所示.而当A前方智能体的单位半径更小时则会有更多.这里仅讨论智能体前方有障碍的情况，如果后方也有障碍，可视为A阻塞.如图6所示，智能体A的绕行方向一般在前方最外侧的两个方向上.令v1为A到目标点的连线，d1、d2和d3为A到其他单位的连线，v2和v3为绕行方向.由于B、C和D均在A的前方，即v1与d1、d2、d3夹角的余弦均大于零，因此v1与它们之间的夹角和叉积在定义域内满足单调性.

对于最外侧的2个障碍单位B和D，上述对应叉积的z轴分量（设z轴方向满足右手系，即垂直纸面向外，下同）达到了前方所有单位中对应量的最大值或最小值.

图4　2个障碍单位的情形

图5　A的前方障碍（实线部分）

图6　对多智能体的绕行方式

为了尽可能地接近目标点，A在最外侧两个智能体B和D之间应选择对应圆心连线d1和d3中与v1夹角绝对值较小的智能体单位进行绕行.令A到这个准备绕行的单位的连线为d*，A到编号为j（0≤j＜n，n为单位总数）的单位的连线为dj，nzj为v1×dj的z分量，则对于绕行方向，当v1×d*=min（nzj）时，向右绕行；当v1×d*=max（nzj）时，向左绕行.

在上述的绕行之后，通常会转为对单个智能体的绕行过程，这时需要保持原先的绕行方向一段时间，因而不能沿用上一节中提到的对单智能体的绕行方法.为此，需要对每个智能体单位额外存储两个数据：被绕行的智能体单位编号p（0≤p＜n，n为单位总数）和绕行方向q（向左为0，向右为1），注意到初始值应当为无效值（如-1）.

当确定了绕行的方向后，如果绕行的障碍多于一个，则从nzj的最值中更新绕行单位的编号p和绕行方向q并按照这个方向绕行；如果绕行的障碍等于一个，则当p为要绕行的障碍时按q的方向绕行，否则将p和q复位（置为无效），并按单智能体的缺省绕行方式绕行；如果绕行的障碍不存在，则将p和q复位.在此之后对新的速度向量进行前面提到的碰撞检测工作，相应的更新状态和绕行的流程如图7所示.

图7　更新状态与绕行的算法流程

2.3一个智能体对多个智能体的提前绕行算法

如果每个智能体仅在碰到另一个智能体后才进行绕行，则其活动空间将受限，为此可以让每个智能体在一定间距下提前绕行［5］.而为避免单位之间的相互碰撞，提前绕行距离的取值可以略大于这个单位的移动速度.

在实际应用中，很多时候只需要智能体单位远离目标点一段距离，即在目标点周围形成一个扇形阵.此时如果各个单位在相等间距下提前绕行，会出现该扇形阵上最内侧分布不紧密的现象，这将影响群体的最终分布结果.为此可以采用分类讨论的办法，即一个单位遇到其最内侧的另一个单位时不提前绕行.对于阵型中的最内侧，设智能体半径为ri，数量为n，要求其距离目标点的距离为R，若能够全部在最内侧排下并成弧形，则其总共占的弧度θ如下：

对于所有圆等半径的情况，令半径为r，则最内侧智能体单位的上限m满足：

为了尽可能地让所有智能体的平均位置为目标点，在一开始，可以让每个智能体单位在除了要绕行的对象是最内侧单位的情况以外，以一个额外的间距进行提前绕行，以减少单位之间的碰撞.当最内侧的单位按式（5）被填满后，再让所有智能体单位进行不提前的绕行，以消除各单位之间的空隙.

3　实验与分析

实验平台为Intel Core i3-2350M 2.30GHz 双核CPU，4GB内存，程序采用HTML5 Canvas和JavaScript编写，在Chrome 45下测试.

如图8所示，I为原始位置，II和III分别为单个智能体对单个和多个智能体障碍时不提前绕行的运行结果，IV为单个智能体对多个智能体提前绕行（提前量为4 px）的运行结果.图中大圆表示智能体单位及其朝向，小圆点为目标点.单位碰撞箱半径为8.5 px，共有15个，起始位置在中上方，以20 px的距离接近右下方的目标.

图8　不同绕行算法下的运行结果

实验过程：先对每个单位执行对单个智能体的绕行算法，待其完全停止后进行对多个智能体的不提前绕行算法，然后待其停止后再执行多智能体的提前绕行算法.在移动的过程中，计时周期为50 ms，智能体单位的速度为每计时周期3 px，角速度为每计时周期20°.智能体在其朝向与速度方向一致时进行移动，其余时刻进行旋转以导正方向.

本文以智能体单位平均位置到目标点的距离来衡量智能体总体到达目标的情况，同时以智能体单位x和y方向标准差σx和σy的平均值衡量单位间的密度，图8相应的数据如表1所示.可以看到，随着算法的不断改进，智能体总体接近目标点的效果得到了明显的提升；在提前绕行算法下，平均密度有一定程度的下降.在实际的游戏战术应用中，对于近战的智能体单位，可以令其平均位置尽可能地接近目标点以保证最大的输出；而对于远程的智能体单位，较小的平均标准差可以使队伍不至于过分深入到敌方阵地，二者需要权衡考虑.

表1　不同绕行算法下，智能体在位置稳定后的结果数据

4　结论

本文探讨了在不发生相互重叠的前提下，包围圆形式的多智能体向同一个目标点行进的相关问题，提出了相应的解决方案：

1）对于重叠的避免，提出了一种前向预防的综合性碰撞检测方法，其中对智能体间相互靠近和远离关系的判断，提升了检测数值的健壮性.

2）对于障碍物的绕行，分别提出了整个群体在时间复杂度为O（n2）时，对单个、多个智能体的绕行算法，以及对多智能体的提前绕行算法，并能够明显地起到总体接近目标的效果，同时保证了计算的实时性.

总之，随着碰撞检测和绕行算法的不断改进，实验能够达到预期效果.对于智能体单位数量过多的情形，则需要考虑更合理的绕行算法，同时需要更好地稳定队伍的阵型来提升最终的效果.

[1] 周小镜.基于改进A*算法的游戏地图寻径的研究[D].重庆：西南大学，2011: 3-10.

[2] SILVER D.Cooperative pathfinding [J].AIIDE,2005 (1): 117-122.

[3] 黄进，黄宗文，凌子燕，等.多智能体寻路系统在计算机游戏上的应用[J].电脑知识与技术，2012,8(13): 3159-3164.

[4] SHOPF J,BARCZAK J,OAT C,et al.March of the Froblins: simulation and rendering massive crowds of intelligent and detailed creatures on GPU [C]//ACM SIGGRAPH 2008 Games.ACM,2008: 52-101.

[5] 王培俊，王文静，陈鹏，等.基于OBB算法和前向预防的快速碰撞检测[J].西南交通大学学报，2011,46(6): 1003-1007.

[责任编辑：熊玉涛]

Research on a Circumambulation Algorithm for Bounding Circles-based Agents

LI Lin-gang,FENG Kai-ping
(School of Electro-mechanical Engineering,Guangdong University of Technology,Guangzhou 510006,China)

This paper discusses collision detection algorithms and circumambulation algorithms for agents based on bounding circles.To avoid overlaps during circumambulating and improve the numerical robustness,we put forward the improved forward collision prevention method based on the position relationship between two circles and the detection of their going nearer to or away from each other.In terms of circumambulation of intelligent agents,we propose algorithms of circumambulating based on single agents and on multiple agents within the total time complexity at O（n2） and the advance detour algorithm for multiple intelligent agents.The experimental results show that in the general effect of going close to the target,the multi agent algorithm is superior to the single agent circumambulation algorithm and the multi agent advance algorithm excels the non-advance circumambulation algorithm.

multi-agents; bounding circles; collision detection; circumambulation algorithms

TP311.1

A

1006-7302（2016）01-0024-05

2015-11-09

广东省自然科学基金博士启动项目（10451009001004484）；国家863计划项目（2013AA031301）；广东省自然科学基金资助项目（2015A030310112）

李林钢（1991—），男，山东郓城人，在读硕士生，研究方向为游戏引擎开发、嵌入式开发；冯开平，教授，硕士生导师，通信作者，研究方向为机器视觉、虚拟现实.