—35— 团队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 计 算 机 工 程Computer Engineering第31卷 第14期Vol.31 № 14 2005年7月July 2005·基金项目论文· 文章编号：1000—3428(2005)14—0035—02文献标识码：A 中图分类号：TP391.411 问题的提出 行进是虚拟环境中CGF(Computer Generated Forces)所具备的基本功能，是CGF完成复杂任务的基础。团队CGF为了提供防御能力和进攻能力，在进行的过程中要保持一定的队形，这就是所谓的编队行进，编队行进问题是一个具有典型性和通用性的团队CGF协调问题，是许多协调问题研究的基础。基于行为的编队控制方法可以分为两类：一是Brooks的行为抑制法[2]，即在每一时刻，编队任务被具体化为某个子行为；二是Arkin的控制变量的矢量累加方法[1]。即在每一个时刻，对3个子行为分别求出控制变量，然后进行矢量累加而得到综合的控制变量。这两类方法各有利弊，Brooks的方法在每一时刻控制变量都有明确意义，但是由于不停地在各个子行为之间进行切换，控制结果不平滑，而完成任务所需要的时间较长；Arkin的方法完成任务速度较快，但是控制意义不明确，而且把每个子行为平等看待，因此各个子行为之间相互干扰，从而影响了整体的控制效果[4]。 团队组织结构是团队协调、协作和协同工作的基础。因此，团队的组织结构在队形保持中起着重要的作用。本文给出一种基于团队组织结构的分层编队控制方法。该方法把整个团队队形分解为一些简单的子队形，分别由不同的成员维护，从而实现对整个队形的控制。 2 基于团队组织模型CTOM的队形保持方法 基于文献[3]中的团队组织模型CTOM，下面给出队形保持的方法。 2.1 准备 定义1 pAgAg⊆×，,xyAg∀∈，若p∈(x，y) （写作xpy），若在CTOM中x的Header是y。p关系不满足自反性、对称性和传递性。其中Ag表示团队中成员的集合。 定义2 团队中任意成员x的Header集合为：Header(x) = {y | xpy，y∈Ag}。 团队中每个成员可以有几个不同的Header成员，表明该成员可以属于几个不同的小组。在任意时刻它只能属于某一个小组。因此不失一般性，我们规定，集合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) = Level(Header(x)) +1 if Header(x) Φ≠Φ⎧⎨⎩； 定义5 (队形图) 一个团队CGF的行进队形定义为G = (1) V为n为顶点的集合，n为团队中成员个数。每个顶点表示团队中的一个CGF成员； (2) 关系p⊆ V×V定义如上，代表连接顶点之间的边，设E表示所有边的集合； (3) C为E上的约束集合，C＝{}eeEc∈，图中的每个边e = (,ijxx)，ec为一个()eφ维的约束向量，()eφ∈ℜ为约束条件个数，kec：ℜ×ℜ→ℜ，k=1,2,L，()eφ，定义了队形在ix和jx之间的所有约束，当满足所有约束时，(,)0keijcxx=对所有k都成立。 基金项目：国家“863”计划基金资助项目(2004AA115130) 作者简介：郑延斌(1964—)，男，博士生、副教授，主研方向：虚拟现实，人工智能；王 辉，硕士生 定稿日期：2004-06-12 E-mail：zhengyb@vrlab.buaa.edu.cn —36—图1 三角形编队 图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φ=，113c={||13|| = 1D}，213c={成员3在成员1前进方向的反方向}；(17)φ=3，117c= {||17||=2||13||}，217c={成员7在成员1前进方向的反方向}，317c={1与3 的连线方向与1与7的连线方向的夹角为0o}；(32)φ=3，132c={||32||=2D}，232c={成员2在成员3的左边}，332c={1与3连线方向与3与2连线方向的夹角为90o}；…。其中||xy||表示成员x的重心位置到成员y的重心位置的距离。1D、2D为数值常量。 定理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个方向，从而确定最终的运动方向。 （1）目标方向 设O为CGF重心位置（当前位置），Goal为目标点的位置，则向目标方向移动的速度方向为连接O与Goal的连线方向，用单位矢量gvuur表示。 （2）保持队形方向 设O为CGF重心（当前位置），M为CGF期望在队形中的位置，则维持队形速度方向为连接O与M的连线方向，用单位矢量mvuur表示。 （3）避障方向 首先考虑静态障碍的情况，动态障碍比较复杂，将在下面介绍。当CGF与障碍物之间的最短距离小于某个阈值时，要产生避障速度，方向为CGF重心点到最短距离点的连线方向的反方向，用单位矢量avuur表示。当大于该阈值时，不产生避障速度。 （4）最终的运动方向 根据这3个速度，就可以求出CGF的最终速度方向。 ggmmaavkvkvkv=++ruuruuruur 其中kg，km，ka为大于或等于0的数。可以通过调节它们的值来改变CGF的运动方向。如图3所示。当CGF的当前位置与Goal的距离小于某个阈值时，此时设km = 0，ka= 0，即此时即到达目标。当没有障碍时，ka= 0。 2.3 动态障碍的规避 在移动过程中，当一个CGF实体与另一个动态实体的距离小于一个固定的阈值时，就要进行动态避障处理。 2.3.1 根据速度方向判断两个动态实体是否将发生碰撞 设CGF重心与动态实体重心的连线方向为lvur，CGF运动方向为cvuur，动态实体的运动方向为mvuur。分为两种情况：情况（1）如图4（a）所示，表示lvur与cvuur之间的夹角，lvur与mvuur之间的夹角都为0，或都非常小时，发生碰撞；（2）图4（b），不满足情况1，设lvur与cvuur之间的夹角为θ，lvur与mvuur之间的夹角为α。则当θαπ+∆<<−∆时，∆为一个角度常量，CGF实体与动态实体将发生碰撞，否则，不发生碰撞，从而不作处理。 (下转第73页) 发送信息调整运动速度和方向行进到达目标图2 社员CGF行为状态Header感知环境开始获得进行的参数来自Header的命令感知环境接收消息1 5 6 78 92 3 4

图4 两个动态实体运动方向示意图qCGF移动实体mvuurcvuurαlvur(A)（B）lvurCGF移动实体cvuurmvuurM向目标方向移动维持队形避障图3 CGF运动方向大小的确定Goal障碍物ggkvuurmmkvuuraakvuurggmmaavkvkvkv=++ruuruuruur —73— 图7 3个算法的收敛特性 4结论 本文描述的遗传算法解决了QoS多播路由的优化问题，交叉操作和变异操作工作在可变长的染色体。交叉操作和变异操作的结合保证了最优解的搜索能力和解的全局收敛性。实验表明，该算法收敛速度快、可靠性高，与文献[7, 8]提到的算法相比，该算法的性能更优。尤其是在网络规模较大，可选路径较多时，该算法搜索速度更快，能大大减小路由计算时间，能满足在实时通信环境、高动态的拓扑结构以及QoS多播路由的网络结构的需求。 参考文献 1李腊元, 李春林. 计算机网络技术. 北京：国防工业出版社, 2001 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~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(上接第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)，则比较两个实体的运动速度，设为xvuur，yvuur。如xvuur>yvuur,则通知对方减速前进，转（10）； (7)若xvuur