团队CGF行进中的队形控制方法
更新时间:2023-04-22 20:47:01 阅读量: 实用文档 文档下载
- 团队cg是什么意思的推荐度:
- 相关推荐
计 算 机 工 程 第 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—
正在阅读:
团队CGF行进中的队形控制方法04-22
南安普顿大学与伯明翰大学哪个好10-04
关于加强接地线安全管理的通知文件09-11
VFP简单初级入门教程超好04-10
小学校安工程汇报材料02-07
服务礼仪培训心得3篇12-24
泰康人寿运用平衡计分卡的实践05-10
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 进中
- 队形
- 团队
- 控制
- 方法
- CGF
- S7-200精品培训课件第六讲
- 人教版品德与生活一上《祖国妈妈的生日》PPT课件1
- 构建新型师生关系-余杨志
- 最新人教版七年级数学上册总复习知识点汇总
- 材料力学课件: 压杆的稳定性
- 微型光泽仪 德国BYK
- 顺口溜解电学综合题的示例
- 防水毯人工湖施工说明
- 托福阅读细节题例题解析-智课教育旗下智课教育
- 口诀
- CAD命令及技巧——整理版
- 梦幻西游手游召唤兽技能搭配攻略 宠物PK高级技能大全
- ASTM_D3363铅笔硬度测试
- 基于因子分析法的我国区域人类发展实证研究
- 城里小学普及安全知识演讲比赛主持词
- 我国中小企业员工培训的现状及对策
- 六年级下册英语教学计划
- 1000kV GIS变电所VFTO特性研究
- 【国家自然科学基金】_移动通讯_基金支持热词逐年推荐_【万方软
- 商业网站流量统计分析系统