,, [ ] H(t) = min 1 ne (t)r( t H ) + α n α h S h (t), 1 (1) S(t) = min[1( t L )(1 H(t)) + α 1S 1 (t), 1] (2) [ ] F (t) = min F i (t), 1 (3)

Size: px

Start display at page:

Download "1328 34 3..,, [ ] H(t) = min 1 ne (t)r( t H ) + α n α h S h (t), 1 (1) S(t) = min[1( t L )(1 H(t)) + α 1S 1 (t), 1] (2) [ ] F (t) = min F i (t), 1 (3)"

鳗舒
7 years ago
Views:

1 34 10 Vol. 34, No ACTA AUTOMATICA SINICA October, Tu Xiaoyuan John David Funge,,, agent., agent. agent,,,,.,,, TP242.6 Research on Advanced Self-organization Behavior for Artificial Fish School BAN Xiao-Juan 1 NING Shu-Rong 1 TU Xu-Yan 1 Abstract Based on research work of Tu and Funge, the advanced self-organization behaviors of fish school were further researched. An self-organization approach of advanced behavior for artificial fish school was presented based on cognition. In this approach, each artificial fish was regarded as an agent, the selforganization behaviors of artificial fish school were emerged from the interactions among many agents, such as behavior planning of motion, predation and escaping. The biologic characteristics of natural fish school were shown, and the advanced behaviors of natural fish school were simulated. A cognition-based artificial fish school animation system was tested efficaciously using the approach of the advanced self-organization in this paper. Key words Artificial fish school, cognition, advanced selforganization behavior, behavior planning Tu [1], Xiaoyuan s Fish, Xiaoyuan s Fish : + [2], John [3],,,,,, :, ;,,.,,.,,., Reynolds boid [4] Ariel dolan foly. boid floy (agent) Received September 11, 2007; in revised form December 12, 2007 ( ) Supported by National Natural Science Foundation of China ( ) Information School of Engineering, University of Science and Technology Beijing, Beijing DOI: /SP.J , agent.,,,.,,,,, 1 [5].,.,. 1,,.,,,,. Fig. 1 1 Structure plan of artificial fish school animation implementation, : 1) ; 2)., ( ), ( ),,,,, 1. (Animal logic), ;,.,,. 2.,,

self-organization behaviors of fish school were further researched. An self-organization approach of advanced behavior for artificial fish school was presented based on cognition.

2 ,, [ ] H(t) = min 1 ne (t)r( t H ) + α n α h S h (t), 1 (1) S(t) = min[1( t L )(1 H(t)) + α 1S 1 (t), 1] (2) [ ] F (t) = min F i (t), 1 (3) [ ] F i D0 (t) = min d i (t), 1,, t, n e (t),, r(x) = 1 P 0x, P 0 ; t H ; n α, ( n α ); α h S h (t), ; P 1 l(x) = P 1x ; t L ; α 1S 1 (t) ; D 0 = 200 ; F i d i (t) i ; P 0 = , P 1 = :, 2. i (4),.,,,.,,.,..,, 4. : AFishBehModel= < ID, Atb, Listate, AutoBehCon(), IntOptBehCon () > ID: AFish. Atb = (Sex, Age, Mass, Type): AFish, Listate: AFish, H(t) S(t) F (t), (1) (3). AutoBehCon():,, IntOptBehCon ():, (I danger ) (I avoid ) (I mate)., : I danger > I avoid > I mate.,. 1. S(t) α H(t) β, α, β,,.. 2. : w avoid > w repulsive > w attractive > w match.,,..,,, avoid repulsive, repulsive attractive, attractive match.,, : 1.,. 3 (agent-baesd) Fig. 2 2 Frame construction of advanced behavior about individual artificial fish,,,, 1, agent. AFishAgent, AFishBehModel. AFishAgent AFishAgent, 3.1 :

0x, P 0 ; t H ; n α, ( n α ); α h S h (t), ; P 1 l(x) = P 1x ; t L ; α 1S 1 (t) ; D 0 = 200 ; F i d i (t) i ; P 0 = 0.00067, P 1 = 0.0025. 2 :, 2. i (4),.,,,.,,.,..,, 4.

3 10 : ) AFishAgent, Listate, AutoBehCon(), S(t) H(t) ; w attractive,. 2) 3 R-A, AFishAgent i AFishAgent j r a > r ij > r m,, AFishAgent i AFishAgent j ; AFishAgent i AFishAgent j 0 < r ij < r r,,, AFishAgent i AFishAgent j, ; AFishAgent i AFishAgent j r m r ij r r,, AFishAgent i AFishAgent j,,,. r a > r m > r r. 3) 1) 2),. α k (t) β k (t) γ k (t) t k t 1 v n = v, k x k (t) = x k (t 1) + v n cos α k (t 1) y k (t) = y k (t 1) + v n cos β k (t 1) z k (t) = z k (t 1) + v n cos γ k (t 1),, 3.3,.,., 3, n,, k AFishAgent k X k, V k : (8) X k = (x k1, x k2, x k3 ) T, k = 1, 2,, n (9) V k = (v k1, v k2, v k3 ) T, k = 1, 2,, n (10) 3 R-A 4 Fig. 3 R-A model Fig. 4 Motion type 3.2, [5 9]., :,.,, r,. n AFishAgent AFishAgent 1, AFishAgent 2,, AFishAgent n. 4, t, k ( ) ( ) t 1. t k N k (t) = {j : (x k (t) x j(t)) 2 + (y k (t) y j(t)) 2 + (z k (t) z j(t)) 2 r 2 n} x k (t), y k (t), z k (t), r n 0. n k (t) = N k (t). V = v [cos α, cos β, cos γ], v, α, β, γ k α(t) = β(t) = γ(t) = 1 n k (t 1) 1 n k (t 1) 1 n k (t 1) j N k (t 1) j N k (t 1) j N k (t 1) α j(t 1) (5) β j(t 1) (6) γ j(t 1) (7) AFishAgent k P k = (p k1, p k2, p k3 ) T, pbest. AFishAgent, P g = (p g1, p g2, p g3) T, gbest., AFishAgent k t + 1 X k (t+1) V k (t+1) : V k t+1 = ωv k t + c1r1(p t X k t ) + c2r2(p g X k t ) (11) X k t+1 = X k t + V k t+1 (12) k = 1, 2,, n, ω, c1 c2, r1 r2 [0, 1]. c1 c2 ω, c1 c2 ω. 3.4, :,.. 1),,,,, if (v k (T ) < v d ) then v k (t) = rand V max (13), v k (T ) T FishAgent, rand [0, 1]. v k (t) [V min, V max].

AFishAgent i AFishAgent j,,,. r a > r m > r r. 3) 1) 2),.

4 自 1330 动化同时它们将会忘记自身的历史最好位置而仅记住种群的最佳位置. 描述为 if (vv k (T ) < v d ) then P k = P g (14) 其中 P k 为 AFishAgent 在空间中所搜索到的最佳食物位置 P g 为整个粒子群迄今为止搜索到的最优位置. 2) 遇敌时的逃逸鱼群在遇到天敌时的逃逸, 通过个体逃逸及过程中相互作用表现群体逃逸行为. 当某个 AFishAgent 发现捕食者时将发送消息给其他的 AFishAgent. 假设 AFishAgent 接收到危险信号, 将分析捕食者的位置方向, 自身的心理生理作出相应逃逸选择. 下面将这个逃逸行为模拟为: 设 AFishAgenti 的质量为 mi ; 某遇险时刻为 t; 速 V min, V max ]; 逃逸时期望达到的速度为度为 v i (t) [V V min, V max ]; 其遇到捕食者需要旋转的角度为 v i 0 (t) [V ei (t); AFishAgent 逃逸期间防止碰撞的排斥作用力为 f ij. 则 Ti 时间内 AFishAgent 运动速度 v i (t) 位置 r i (t) 的变化可用下式表示 mi dvv i (t) v i 0 (t)ei (t) v i (t) X = mi + f ij dt Ti j=i v i (t) = drr i dt (15) 学报 34 卷 2) Call 鱼群移动算法并根据定理 2 设定人工鱼当前状态参数 x, y, z 的优先级别. 3) If 人工鱼 S(t) F (t) then Begin call 高级行为的路径规划算法 call 鱼群觅食算法 End Else begin call 高级行为的路径规划算法 call 鱼群逃逸算法 End 4) Call 高级行为的路径规划算法} 4 鱼群动画系统实现与高级行为测试采用上述自组织算法, 我们对其进行了测试. 下面是各高级行为的部分程序截图. 图 6 8 所示为鱼群感知到静态障碍物 (礁石) 并躲避的过程. 图 6 中, 随着鱼群的游动, 礁石进入鱼群感知范围内, 即被鱼群发现并认定为前方有障碍. 图 7 中, 根据上面提 (16) 同时定义人工鱼逃逸期间避免碰撞的斥力为 f ij = f f nij, 其中 Ai, Bi 为常量; dij = ri rj Ai exp[(rij dij )/Bi ]n 为两条人工鱼之间的距离. n ij = (n1ij, n2ij, n3ij ) = (ri, rj )/dij 为有指向的法向量. 其中遇到捕食者需要旋转的角度为 ei (t)(t 的取值可由 AFishAgenti 的运动速度 v i (t) 与捕食者 Predator 的运动速度 v p (t) 共同决定), 如图 5 所示, 其中虚线为调整后的速度. if v k (t)vv p (t) 1 then ei (t) = 180 v k (t)vv p (t) 0 then ei (t) = 0 µ v i (t)vv p (t) π ei (t) = arccos 2 v i (t) v i (t) elseif else (17) 图6 Fig. 6 鱼群感知到静态障碍物 Static obstacle was percepted (18) (19) 式 (19) 中表示背离 Predator 运动方向, 即 Predator 在 AFishAgenti 左侧, 则 AFishAgenti 向右转, 反之亦然. 图7 Fig. 7 图5 Fig 鱼群躲避静态障碍物 Static obstacle was avoided 运动转角 Angle of rotation 鱼群自组织主体算法整合上述各行为的算法, 基于认知的自组织算法 AFishBeh SelfOrganizing 设计如下: AFishBeh SelfOrganizing (α, β, x, y, z){ 1) 根据定理 1, 判定如下动作: If S(t) α && S(t) β then call 鱼群集群算法 Fig. 8 图 8 避障成功 Static obstacle was avoided successfully

下面将这个逃逸行为模拟为: 设 AFishAgenti 的质量为 mi ; 某遇险时刻为 t; 速 V min, V max ]; 逃逸时期望达到的速度为度为 v i (t) [V V min, V max ]; 其遇到捕食者需要旋转的角度为 v i 0 (t) [V ei (t); AFishAgent

5 10 期班晓娟等: 人工鱼群高级自组织行为研究到的避障规则, 鱼群选择从礁石两侧游过礁石来躲避该静态障碍物. 图 8 中, 躲避静态障碍物成功, 鱼群继续向前游动. 图 9 和图 10 是人工鱼群看见天敌 (鲨鱼) 并逃逸的行为过程. 图 9 中, 随着鲨鱼的接近, 鲨鱼进入鱼群的感知范围, 即被鱼群认知为有生命危险. 图 10 中, 鱼群感知到鲨鱼接近的危险后采取了逃逸行为由于部分程序不能很好地表现集群时各人工鱼方向趋向程度, 我们采用 Matlab 仿真模拟鱼群集群时的方向趋向程度, 见图图9 鱼群逃逸行为 1 Escape of fish school 1 Fig. 9 图 13 Fig. 13 鱼群的初始状态 Initialed state of fish school 图 10 Fig. 10 鱼群逃逸行为 2 Escape of fish school 2 图 11 和图 12 为鱼群的觅食行为. 图 11 为鱼群发现周围的食物, 开始觅食, 其中白色的点表示食物; 图 12 为人工鱼群周围出现鲨鱼, 鱼群成为鲨鱼的觅食对象. 图 14 运行时间 20 s 时鱼群的集群效果 Fig. 14 Collection of fish school at t = 20 s Fig. 11 图 11 鱼群觅食 Searching food of fish school 图 12 Fig. 12 鲨鱼觅食鱼群 Fish school was predating by shark 图 15 运行时间为 100 s 时鱼群的集群效果 Fig. 15 Collection of fish school at t = 100 s

13 鱼群的初始状态 Initialed state of fish school 图 10 Fig. 10 鱼群逃逸行为 2 Escape of fish school 2 图 11 和图 12 为鱼群的觅食行为. 图 11 为鱼群发现周围的食物, 开始觅食, 其中白色的点表示食物; 图 12 为人工鱼群周围出现鲨鱼, 鱼群成为鲨鱼的觅食对象.

6 ,,,,,. agent,,,,. References 1 Tu X Y. Artificial Animals for Computer Animation: Biomechanics, Locomotion, Perception, and Behavior [Ph. D. dissertation], University of Toronto, Ning Shu-Rong, Ban Xiao-Juan, Tu Xu-Yan. Intention produce and behavior control for artificial fish based on harmonic of emotion and intelligence. Acta Automatica Sinica, 2007, 33(8): (,,.., 2007, 33(8): ) 3 John David Funge [Author], Ban Xiao-Juan [Translator]. AI for Games and Animation: A Cognition Modeling Approach. Beijing: Tsinghua University Press, 2004 (John David Funge [ ], [ ]. :. :, 2004) 4 Wang Shuo, Tan Min. Robert Fish. Beijing: Beijing University of Posts and Telecommunications Press, 2006 (,.. :, 2006) 5 Reynolds C W. Description and control of time and dynamics in computer animation. SIGGRAPH 85 Advanced Computer Animation Seminar Notes. New York: ACM, Parrish J K, Viscido S V, Grunbaum D. Self-organized fish schools: an examination of emergent properties. The Biological Bulletin, 2002, 202(3): Kahn K M. Creation of Computer Animation from Story Descriptions [Ph. D. dissertation], MIT Artificial Intelligence Laboratory, Chen J, Pan F, Cai T. Acceleration factor harmonious particle swarm optimizer. International Journal of Automation and Computing, 2006, 3(1): Toner J, Tu Y H. Flocks, herds and schools: a quantitative theory of flocking. Physical Review E, 1998, 58(4): banxj@ies.ustb.edu.cn (BAN Xiao-Juan Ph. D.. Her research interest covers artificial intelligence, computer animation, and artificial life.).. ningngu@yahoo.com.cn (NING Shu-Rong Ph. D.. Her research interest covers artificial intelligence, computer animation, and artificial life. Corresponding author of this paper.). tuxuyan@126.com (TU Xu-Yan Professor. His research interest covers artificial intelligence and artificial life.)

Acta Automatica Sinica, 2007, 33(8): 835 839 (,,.., 2007, 33(8): 835 839) 3 John David Funge [Author], Ban Xiao-Juan [Translator]. AI for Games and Animation: A Cognition Modeling Approach.

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier 36 7 Vol. 36, No. 7 2010 7 ACTA AUTOMATICA SINICA July, 2010 1, 2 1, 2, 3 1, 2,,,,,,, DOI,,, 10.3724/SP.J.1004.2010.00923 Distributed Simulation System Hierarchical Design Model Based on Quotient Space