团队CGF行进中的队形控制方法

计 算 机 工 程 第 31 卷 第14期

Vol.31 № 14 Computer Engineering · · 基金项目论文

文章编号：1000—3428(2005)14—0035—02

文献标识码：A

2005年7月

July 2005

中图分类号：TP391.41

团队CGF行进中的队形控制方法

郑延斌1,2，王 辉1

(1. 北京航空航天大学计算机学院，北京 100083；2. 河南师范大学计算机系，新乡 453002)

摘 要：分布式虚拟环境中，团队CGF的行进问题是CGF研究的基本问题，而行进中的队形保持问题又是行进问题研究的重点。在提出的团队组织模型CTOM的基础上，给出了一种团队CGF行进中队形保持方法。 关键词：团队CGF；行进；队形；避障；速度；方向

Formation Control of CGF Team in Advance

ZHENG Yanbin1,2 , WANG Hui1

(1. College of Computer, Beijing University of Aeronautics and Astronautics, Beijing 100083;

2.Dept. of Computer Science, Henan Normal University, Xinxiang 453002)

【Abstract】In distributed virtual environment, the advance of CGF team is the main issue of CGF team researches. The maintaining of teamformation in advance is the key issues of this problems. This paper proposes a method for maintaining CGF team formation. 【Key words】Team CGF; Advance; Formation; Avoiding obstacle; Velocity; Direction

1 问题的提出

行进是虚拟环境中CGF(Computer Generated Forces)所具备的基本功能，是CGF完成复杂任务的基础。团队CGF为了提供防御能力和进攻能力，在进行的过程中要保持一定的队形，这就是所谓的编队行进，编队行进问题是一个具有典型性和通用性的团队CGF协调问题，是许多协调问题研究的基础。基于行为的编队控制方法可以分为两类：一是Brooks的行为抑制法[2]，即在每一时刻，编队任务被具体化为某个子行为；二是Arkin的控制变量的矢量累加方法[1]。即在每一个时刻，对3个子行为分别求出控制变量，然后进行矢量累加而得到综合的控制变量。这两类方法各有利弊，Brooks的方法在每一时刻控制变量都有明确意义，但是由于不停地在各个子行为之间进行切换，控制结果不平滑，而完成任务所需要的时间较长；Arkin的方法完成任务速度较快，但是控制意义不明确，而且把每个子行为平等看待，因此各个子行为之间相互干扰，从而影响了整体的控制效果[4]。

团队组织结构是团队协调、协作和协同工作的基础。因此，团队的组织结构在队形保持中起着重要的作用。本文给出一种基于团队组织结构的分层编队控制方法。该方法把整个团队队形分解为一些简单的子队形，分别由不同的成员维护，从而实现对整个队形的控制。

成员可以属于几个不同的小组。在任意时刻它只能属于某一个小组。因此不失一般性，我们规定，集合Header（x）中的元素个数为0或1，即每个成员最多有一个Header。

定义3 团队中任意成员x的Member集合为Member（x）＝{y|y px，y∈Ag}。

推论1 x，y∈Ag，x≠y，则Member(x)IMember(y) = Φ(空集合)。

定理1 团队CGF组织（成员个数大于1）中不存在这样的成员x，满足Header(x)= Φ且Member(x)= Φ。

定义4 层次Level映射：Ag→ ， 为自然数集。Ag为团队中成员集合。 x∈Ag，

Level(x) =

0; if Header(x) = Φ

if Header(x) ≠Φ Level(Header(x)) +1；

定义5 (队形图) 一个团队CGF的行进队形定义为G

= <V，p，C>

(1) V为n为顶点的集合，n为团队中成员个数。每个顶点表示团队中的一个CGF成员；

(2) 关系p V×V定义如上，代表连接顶点之间的边，设E表示所有边的集合；

(3) C为E上的约束集合，C＝{ce}e∈E，图中的每个边e = (xi,xj)，ce为一个φ(e)维的约束向量，φ(e)∈ 为约束条件个数，ce： × → ，k=1,2,L，φ(e)，定义了队形在

k

2 基于团队组织模型CTOM的队形保持方法

基于文献[3]中的团队组织模型CTOM，下面给出队形保持的方法。 2.1 准备

定义1

k

∈(x，y) （写

，若在CTOM中x的Header是y。p关系不满足作xpy）

p

Ag×Ag， x,y∈Ag，若p

自反性、对称性和传递性。其中Ag表示团队中成员的集合。 定义2 团队中任意成员x的Header集合为：Header(x) = {y | xpy，y∈Ag}。

团队中每个成员可以有几个不同的Header成员，表明该

xi和xj之间的所有约束，当满足所有约束时，

ce(xi,xj)=0对所有k都成立。

基金项目：国家“863”计划基金资助项目(2004AA115130) 作者简介：郑延斌(1964—)，男，博士生、副教授，主研方向：虚拟现实，人工智能；王 辉，硕士生

定稿日期：2004-06-12 E-mail：zhengyb@

—35—

图1所示为团队CGF行进中的三角形编队图形。团队

中的成员编号为1～9。图中的边表示p关系，V={1,2,3,4,5,6,7,8,9}，

Header(1) = Φ，Number(1)={3,7}，Header(3) = {1}，Number(3)={2,4}，Header(7) = {1}，Number(7)={5,6,8,9}，其它成员的下属集合都为空。

E={13,17,32,34,75,76,78,79}；φ(13)=2，c1

13={||13|| = D1}，

c23在成员1

前进方向的反方向}；φ(17)=3，c113={成员17=

{||17||=2||13||}，c2

17={成员7在成员1前进方向的反方向}，

c

3

17={1

与3 的连线方向与1

与7的连线方向的夹角为0o

}；

φ(32)=3，c1

}，c2

32={||32||=D232={成员2在成员3的左边}，

c3={1与3连线方向与3与2连线方向的夹角为90o32}；…。

其中||xy||表示成员x的重心位置到成员y的重心位置的距离。D1、D2为数值常量。

图2 社员CGF行为状态

定理2 满足定义5的任何团队CGF队形可以有其内的子团队通过行或列队形来维持。p

通过关系，把团队CGF中的成员分为两类，为了叙述方便，把团队CGF中满足条件 Member(x) =Φ的成员称为社员CGF，而把Member(x) ≠Φ的成员称为基层CGF。

社员CGF的任务为：（1）通过感知环境来确定自己下一步的速度和方向；（2）向自己的Header成员发送相应的信息；（3）接收消息，来调整运动方向和速度（消息有两类：

一类是有Header发送的任务、

奖励或惩罚信号、速度和方向的调整等；另一类是其它成员发送的用于避障的速度大小的调整信息）。其行为状态如图2所示。

基层CGF的任务为：它首先具备社员CGF的功能，即

上面（1）

、（2）、（3）；对其下属成员的行为进行监控，从而维护它与下属组织的子队形。为了满足团队CGF编队行进的要求，把每个成员的在任意时刻的运动方向分解为下面3个方向之和：(1) 目标方向（Move to Goal）；(2) 维持队形方向(Maintain Formation)；(3) 避障方向（包括躲避静态障碍和动态障碍）(Avoiding obstacle)

2.2 运动方向的确定

CGF成员通过感知环境，确定上面说明的3个方向，从

—36 —

而确定最终的运动方向。

（1）目标方向

设O为CGF重心位置（当前位置），Goal为目标点的位置，则向目标方向移动的速度方向为连接O与矢量uuGoal的连线方向，用单位

vr

g

表示。

（2）保持队形方向

设O为CGF重心（当前位置），M为CGF期望在队形中的位

置，则维持队形速度方向为连接O与M的连线方向，用单位矢量uuvr

m表示。

（3）避障方向

首先考虑静态障碍的情况，动态障碍比较复杂，将在下面介绍。当CGF与障碍物之间的最短距离小于某个阈值时，要产生避障速度，方向为CGF重心点到最短距离点的连线方向的反方向，用单位

矢量uuvr

a表示。当大于该阈值时，不产生避障速度。

（4）最终的运动方向

根据这rv=ku3ur个速度，就可以求出uuruurCGF的最终速度方向。

g

vg

+kmvm

+kava

其中kg，km，ka为大于或等于0的数。可以通过调节它们的值来

改变CGF的运动方向。如图3所示。当CGF的当前位置与Goal的距离小于某个阈值时，此时设km = 0，ka= 0，即此时即到达目标。当没有障碍时，ka= 0。

M

rv=kuuruurkuurv+kv+avakuvuraa

2.3 动态障碍的规避

在移动过程中，当一个CGF实体与另一个动态实体的距离小于一个固定的阈值时，就要进行动态避障处理。 2.3.1 根据速度方向判断两个动态实体是否将发生碰撞 设CGF重心与动态实体重心的连线方向为uvr

l动方向为uvuruur

，CGF运

c，动态实体的运动方向为情况（1）如图4（a）所示，表示uvruurvm。分为两种情况：

uruu

rl与vc之间的夹角，vl与vm之间的夹角都为0，或都非常小时，发生碰撞；（2）图4（b）不满足情况1，设uvruurur与uvu

r，

l与vc之间的夹角为θ，vlm之间的夹角为α。

则当θ+ <α<π 时， 为一个角度常量，CGF实体与动态实体将发生碰撞，否则，不发生碰撞，从而不作处理。

uvruvruvurm

urc

urvCGl

F

(A)

（B）

图4 两个动态实体运动方向示意图

(下转第73页)

Objective Function Values

2李腊元,李春林.动态QoS多播路由协议.电子学报, 2003,31(9):1345 3 Sun Baolin, Yin Xianhong, Li Layuan. Optimizing Fuzzy Controllers for QoS Improvement in DiffServ Networks. In: Proceedings of the 7th Joint Conference on Information Sciences (JCIS 2003), Cary, North Carolina, USA, 2003-09：521-525

4 孙宝林, 李腊元, 陈 华. 基于遗传算法的最短路径路由优化算法. 计算机工程, 2005,31(6):142-144

5 Xiawei Z,Changjia C,Gang Z. A Genetic Algorithm for Multicasting

Routing Problem. International Conference Communication Technology Proceedings, WCC-ICCT 2000, 2000: 1248-1253 6 Zhang Q, Lenug Y W. An Orthogonal Genetic Algorithm for Multimedia Multicast Routing. IEEE Trans Evolutionary Computation, 1999,3: 53-62

7 Munemoto M,Takai Y,Sato Y. A Migration Scheme for the Genetic Adaptive Routing Algorithm. IEEE International Conference on Systems, Man, and Cybernetics, 1998: 2774-2779

8 Inagaki J, Haseyama M, Kitajima H. A Genetic Algorithm for Determining Multiple Routes and Its Applications. Proceedings of IEEE International Symposium on Circuits and Systems, 1999: 137-140

9 王小平, 曹立明. 遗传算法——理论、应用与软件实现. 西安：西安交通大学出版社, 2002

Generations

图7 3个算法的收敛特性

4结论

本文描述的遗传算法解决了QoS多播路由的优化问题，

交叉操作和变异操作工作在可变长的染色体。交叉操作和变异操作的结合保证了最优解的搜索能力和解的全局收敛性。实验表明，该算法收敛速度快、可靠性高，与文献[7, 8]提到的算法相比，该算法的性能更优。尤其是在网络规模较大，可选路径较多时，该算法搜索速度更快，能大大减小路由计算时间，能满足在实时通信环境、高动态的拓扑结构以及QoS多播路由的网络结构的需求。

参考文献

1李腊元, 李春林. 计算机网络技术. 北京：国防工业出版社, 2001

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(上接第36页) 2.3.2 碰撞的处理

当两个动态实体将发生碰撞时，需要改变CGF的运动速度的方向，从而避免碰撞。我们采用下面的算法来处理：

(1)移动实体的所在的组织ID，若与CGF所在的组织不相同，则转（9）；

(2)它们的运动方向发送给各自的Header，得出相应的奖惩信息，并根据这些信息进行调整，若调整后的方向如不满足上述的碰撞条件，则转（10）；

(3)判断它们在组织中的层次。设移动实体为x，CGF实体为y； (4)若Level（x）< Level(y) 说明对方比当前的CGF实体级别高，则CGF实体减速前进，转（10）；

(5)若Level(x) > Lever(y)，则通知对方减速前进，CGF速度不变，转（10）；

(6)若Level(x) = Level(y)，则比较两个实体的运动速度，设为

uruuruuruuur

； vx，v。如vx>v,则通知对方减速前进，转（10）

送奖励信号。当成员收到奖励信号后，保持目前的速度和方

向不变。当成员收到惩罚信号后，根据信号的类型调整k1，k2，k3的值，来改变运动方向。

2.5 团队中成员运动速度的控制

为了能使团队成员更好地保持队形，我们设定团队中的成员开始的运动速度都相等。成员在运动的过程中通过感知环境来调节运动方向，而速度大小的改变有3个渠道：（1）Header成员发送的调整速度的信息（用于调整掉队或冒进）；（2）团队中其它成员发送的改变速度的信息（用于避障）；（3）在碰撞处理中自己确定改变速度大小的决定。

3 结论

该方法的成果运用到我们承担的“十五”计划“863”项目的CGF子系统DveFoce中，得到了比较满意的结果。

给出的队形保持算法。它有以下本文基于CTOM组织模型，

优点：（1）可以处理大型CGF团队；（2）灵活的成员运动

（4）通过子团队的方向的调节；（3）队形的调节能力较强；

Header的调节，可以很好地解决掉队问题和队形的变化问题；（5）成员行进速度的一致性，可以从根本上保证行进队形有较高的保持率。

参考文献

1 Arkin R C. Motor Schema Based Mobile Robot Navigation. International Journal of Robotics Research , 1989, 8(4):92

2 Brooks R A. A Robust Layered Control System for A Mobile Robot. IEEE Journal of Robotics & Automation, 1986, 2（1）: 14-23 3 Zheng Yanbin , Wang Hui. A CGF Team Organizational Model Based on Multi-agents. Simulation Interoperability Workshop(SIW), Orlando,Florida,USA, /siw/03fall, 2003 4 董胜龙，陈卫东. 多移动机器人编队的分布式控制系统. 机器人

Robot,2000, 22(6): 433-438

ruuruu

(7)若vx<v，则CGF减速前进，转（10）；

yuuruur

(8)若vx＝v，则随机确定加速或减速，把结果告诉对方，

y

yy

或者通过协商处理，转（10）；

(9)让对方减速，CGF速度不变； (10)结束

引理1 团队行进中满足队形要求的所有成员运动过程中不会发生碰撞。

定理3 通过上述算法可以有效地解决两个动态实体的碰撞问题。

2.4 上级对下属成员的监控

当CGF确定自己下一步的运动方向和速度后，把这些信息发送给Header，Header根据自己的位置、方向，其所有下属成员的速度、位置、队形参数，计算是否满足队形约束的要求，若满足则向下属成员发送奖励信号。若不满足，则找出偏离队形的成员，给该成员发送惩罚信号；若满足则发

—73—

本文来源：https://www.bwwdw.com/article/h32q.html