TELKOM NIKA , Vol. 11, No. 5, May 2013, pp. 2545 ~   2552   ISSN: 2302-4 046           2545      Re cei v ed  Jan uary 9, 2013;  Re vised Ma rch 11, 2013; A c cepted Ma rch 22, 2013   Soldiers’ Group Behaviors Simulation Based on  Improved MAPRM      Meng Li* 1 , Jia-hon g Lian g  1 , Shi-lei Li   2   1 Colle ge of Me chan ical En gi n eeri ng an d Aut o matio n , Natio nal U n ivers i t y   of Defence tec hno log y , 4 100 73  Cha ngsh a , P.R. China   2 Departme n t of Information Se curit y , Co ll ege  of Electroni c E ngi neer in g, Na val Univ ersit y  o f  Engine eri ng,  430 00 0, W uha n, P.R. China   *Corres p o ndi n g  author, e-ma i l : {mengsh u q i n 198 4, lin gji aho ng_ nu dt, stoneli}@1 63.com       A b st r a ct   Sold iers ’   gro u p  beh aviors  are  a class  of flo cking  beh avi o r s  in w h ich  a s qua d of so ldi e r s  marc h   forw ard accord ing to  a sp ecifi ed for m ati on  a nd try to ke ep i t  w hen enc oun tering  narrow  c o rridors. It has   a   lea d in g a p p lica t ion i n  d e terri n g  the  be havi o r  and  activiti es o f  a pote n tia lly  h o stile cr ow d a n d bri ngi ng  a  mob   eng ag ed  in  a  riot u nder  cont rol i n  s o cia l  st abl e  ma in te na nce. In th is p a per, w e  focus   on i n vesti gati n g  soldi e r ’ s gr oup  behav iors b a s ed on a n  i m pr oved MAPRM  alg o rith m. F i rstly, w e  use MAPRM alg o rith m to  sa mp le   co n f i g u r a t i o n s   fro m  th e   me d i a l  a x i s  o f  the  simu la ti o n  sp a c e .  Seco n d l y , i n  the   co n s tru c ti on   and  query  phas e o f  MAPRM, clearanc e infor m a t ion of the s p a c e is intro duc e d  to loc a l p l an ner a nd us ed  a s   heur istic infor m ati on to A* a l gorit hm w h ic h  impr oves  the  MAPRM alg o ri thm. T h irdly,  w hen the sol d i e rs   pass through narrow corridors , their formatio n  transiti ons ar e ach i eve d  by  sampli ng th e d e sire d for m ati o n   shap e. T he simu lati on resu lts show  that  our appro a ch is ef fective and fe a s ible.     Ke y w ords :  Cr ow d simulati on , flocking, sold i e rs ’   gro up b e h a vior, MAPRM         Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Cro w d s ,  ubiq u itous in  the  real  wo rld f r o m  group s  of h u man s  to  flocks of i n sect s,  are  vital  feature s  to m odel in  a virtual environm ent. Vari ou s  simulatio n  m odel s an d archite c ture s h a ve   been d e velo ped. Crowd  manag eme n t mean s all meas ures ta ken in the  n o rmal p r o c e s s of  facilitating th e movem ent  and  enjoym ent of pe opl e,  as  well  a s  all me asure s  p r ep are d  t o  be  taken i n  the  emergent p r o c e ss  of peopl e evac uation s . Crowd ma nagem ent ca n be succe ssful  only whe n  viewe d  as  a combinatio n of  manag em en t of all the crowd s , enviro n ment an d their  relationshi p . This is  especi ally necessary for  the cro w d incid ents in  urba n ci rcum stan ce s.   Soldiers’ g r o up beh aviors  are a  cla s s of flocki ng be h a viors i n  whi c h a sq uad  of soldi e rs  march forwa r d according t o  a spe c ified  formation. Its appli c atio n area in clu d e s  the mean s to   influen ce the   behavio r a n d  activities  of  a potentia lly hostile cro w d ,   as well as, the  capability   to   bring  a mob  engag ed in  a riot und er control. So ldiers’ group  i.e. a squa d  of soldie rs is  a   coh e re nt gro up  which n e ver  splits up i n to seve ral  su b-g r ou ps. In  current a pplica t ions, the  qua lity  of coh e rent g r oup  be havio r is i n  ge ne ra l not very  go od, espe cially  few resea r ch ers inve stigat es   the soldie rs’   grou p b ehavi o rs.  The  prim ary rea s on s  are th e n eed s to  com pute  the path s  in  real- time and co ntrol the gro up’s formatio n transitio ns  whe n  the sol d iers’ gro up  passe s thro u gh  nar ro w co rri d o rs.   In respe c t of motion pla nni ng problem f o r g r ou ps of  entity, the most com m on  a ppro a ch  to simulating  group move ment is to use flocki ng.  The co ncept of flocking  was intro d u c e d  by  Reynol ds.  Hi s boi ds m o d e l de scribe d  the beh avio r  of the entitie s in a  gro up  usin g only lo cal  rule s for th e individual  entities [1]. Later, Reynold s  extend ed the tech nique to in clude   autonom ou s  reactive  beh a v ior. But in  Reynold s ’s work, little motio n  pla nning  was  co nsi dere d . In   the rob o tics community, on e of the domi nating te chni que s is the  probabili stic  roa d map a pproa ch   (PRM ). Efficient probabili stic (centralize d ) te chniq u e s  for multiple  e n tities have  b een d e velop e d .   They treat th e differe nt en tities togethe r as  one  l a rg e  rob o tic  syste m . Unfortu nat ely, each  enti t y  has t w o  deg rees  of free do m (a ssumin g  it is defin ed  b y  its po sition  on a flo o r  su rface )   so the  to tal  roboti c  syste m   ha s 2 n   de gree s of fre e dom  whe n  th ere  are  n  ent ities. When   n  gets la rge r  t he  runni ng time  become s  too  large. To  ove r co me th is  problem d e cent ralized te chni que s, like p a th   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2545 – 255 2   2546 coo r din a tion,  have b een   develop ed, e nablin g the  p l annin g  of m o tion for a la rge r  n u mbe r   of  entities. Still though, the s e method s fa il when th e  n u mbe r  of enti t ies grows a nd the re sulti n g   motion is no t coherent [1]. Recently,  Bayazit, Lien and Amato have com b ined the PRM  approa ch wit h  flocki ng techniqu es. The  entities u s e the roa d ma p cre a ted by PRM to guid e  thei r  motion to wa rd the  goal  wh ile they u s e  flocking  to a c t  as  a g r ou p a nd avoi d lo ca l colli sion s. B u t  grou ps still   split u p  e a sil y . Li and  Chou  dev elo p ed a  ne w  a ppro a ch that  allo ws dyna mic  stru cturi ng  of the e n tities such  that the   centra lized  pl annin g  of th e  motion s i s   g r eatly imp r ov ed.  Ho wever, thi s  app roa c h l a cks the abil i ty of  guaran teeing co he rence [1]. So  it can’t be used  dire ctly  in sol d iers’ gro up behavio rs  si mulation.  A. Kamphui s, J.F.  Hel gers  a nd  M. H.  Ove r mars  introdu ce d a new a pproa ch to motion planni ng for  grou ps of en tities in virtual environm e n ts.  They model e d  the grou p a s  a deformab l e sha pe of large e nou gh  area a nd pla nned the mot i on   for this  sha p e  throug h the  environ ment  usin g an  exte nsio n of the  prob abili stic roadma p  met hod   [1, 2].  But A. Kamphuis ig nore d  the cle a ran c e info rmation of the spa c e wh en  generating the   grou p’s t r avel ing path. Alth ough Steven  A. Wilmar th d e velope d MAPRM alg o rith m and u s e d  it to  gene rate  pat hs o n  the  me dial axis of th e free  sp ace, he di dn’t u s e  the cl earan ce to imp r ove  the   local pl anne r  and qu ery ph ase of MAPRM [3].  In respe c t of formation  control p r obl e m   of group s,  currently, the popul ar m ean s of  forming  a target group fo rmation i s  to specify the  d e s ire d  po sition  of ea ch a g e n t at a pa rticular  moment and  then gene rat e  reali s tic tra n sition s bet ween the cu rre n t position an d the target. So  most existin g  work a dopt s the com m on  pro c e ss  of  first sampli ng t he de sired fo rmation  sh ap e ,   followe d by a path plannin g  stage for e a ch  samp l e  points. Sub s eque ntly, agents in the flock  follow  th e co rre sp ondi ng sampl e  point s, while at  the same time  exhibiting flocki ng beh aviors.   Based  on thi s  ide o logy, Anderso n et al . con s ide r ed an  iterative sampling meth od  to  ge nera t e  grou p ani ma tions  with predefine d  formation.  More re cently, Xu et al. propo sed  a shap e   con s trai ned fl ock alg o rithm  to handl e co mplex 2D  an d 3D  sh ape  con s trai ned fl ocks th at mo ve   along p r ed efined path s  [4, 5, 6].  This p ape r focu se s on th e soldi e rs’ group be haviors, whi c h i s  u s ed m a inly for soci al   stable m a inte nan ce an d m ob co ntrol s . Our a pproa ch  is in spired  most he avily by A. Kamphuis’ s   innovational  rese arch i n  th e dom ain  of moti on pl anni ng for group s of  entities  and Steven   A.  Wilma r th’s m o mentou s wo rk on  MAPRM  (a  p r o babil i stic roa d map   plann er with sampli ng  o n   t he  medial axi s  of the free space),  Choon S i ng Ho’ s   work  is also helpf ul to fulfill this paper [4, 7,  8 ,   9].  Our pa per co nsi s ts  of thre e ph ases:  prepr o c e s sing  pha se with MAPRM,  qu e r y  ph ase  con s id erin g the cl earan ce  informatio n of  the sp ac e i n   A* algorithm,  formation tra n sition s ph ase.  In the first p h a se,  milesto n e s  are  ge ne rated  with   MA P R M sampli n g   st rat egy  wh ich ca n  in cr e a se  the sa mpling s  on th e me di al axis of the  corrid or s in th e sp ace. The  node s lie  on  the medial  axis  of the free  space which  potentia lly provides th e soldiers’ g r o u p  a maximu m pa ssa ge.  The  medial  axis facilitates acquirin g process of  the  clearance inform ation  whi c h i s  used in local  planner  of M APRM to im prove the collision-fr ee links. In the  second phase, the MAPRM   algorith m  is  improve d  by con s ide r in g  the clea ran c e info rmatio n of the sp a c e. The  gro up’s  traveling p a th  is ge ne rated  by A* algo rithm with   an i m prove d  he u r istic fun c tion . As the soldi e rs’  grou p  fo rmati on cha nge s according   to the  current   cl eara n ce info rmation, form ation tra n sitio n s  are a c hieve d  in the third ph ase u s in g B-spline curve.       2. Impro v e M A PRM  Algori t hm   2.1. Using   MAPRM   Algorithm to G e nera te  Mileston es  and  Impro v e Loc al Planner   w i th   Cleara n ce In formatio n   MAPRM (A   Proba bilisti c  Roa d map  Pl anne r  with S a mpling  on  the Me dial A x is of the  Free  Spa c e )   use s   a  sam p li ng  strate gy of  gen eratin g  random  mile st one s lie  on  th e me dial  axis  o f   the free  sp ace. It efficiently retra c ts  any  sam p led  co n f iguration, fre e  or  not, onto  the medi al a x is   of the free sp ace  without h a ving to com pute the m edi al axis explici t ly. Sampling and ret r a c ting  in   this way give excellent p e rform a n c e o n  probl ems  of generating  paths  re quiring traversal  of  narro w pa ssa ges [3].  In our  pap er  we  reg a rd th e sp ace a s  a  2D  co nfigura t ion sp ace in  whi c h the  fre e  sp ace   and  ob stacl e s a r e  polygo n a l. For si mpli city, we  co nsi der  only  sets  P  that a r e th e  disjoi nt union  of a finite  nu mber of  clo s e d  polyg on s  (i nclu ding  the i n terio r , po ssi b ly with  hole s ). Fo r  x P , we  define  () P Bx  to b e  the la rge s t closed  disc cente r ed  at  x  that is  a su bset of   P ,  i. e.,  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Soldiers ’  Group Beha vio r s  Sim u lation Base d on Im prove d  MAPRM (Meng Li )  2547  () , ( ) PP Bx B x x , where   , Bx r  den otes the  clo s ed di sc of  ra dius  0 r  cente r e d  at  x  and   2 () t a n , \ P x di s c e x P R  is the  dista n c e to  the  bo u ndary  for  poi nts in sid e   P  a nd 0  for poi nts   outsid e   P  [3]. T he medial axi s   () M AP  of  P  is defined as    ( ) |    w ith   ( ) ( ) PP M AP x P y P B x B y  Ø  (1)     Formul ation  (1) m ean s th a t   () M AP  are the  set of all  point s  x  of  P  w h os e as so c i a t e d   () P Bx  is maximal.  A  point  x P  is cal l ed a  sim p le point  if  x  has a  unique nea rest point  0 x  in P .  Otherwise,  x  is called a  m u ltiple point .  P  is defined to be  P  minus its no n-convex vert ex points.           Figure 1. Medial axis of a clo s ed p o lygo n      The followi ng  facts hold a c cording to referen c e [3]:   1. Let  x P  , Then  x  is in  () M AP  if and only if  x  is a con v ex vertex of  P .  2. Any multiple point of  P  is contai ned in  () M AP . If  () x MA P , then  x  is in the interior of  P  if and only if  x  is a  m u ltiple  point  of  P  [5].   3. For e a ch   x P ,  () P Bx  is conta i ned in  a u n ique m a xim a l disc  () P By , where   () yM A P . Furthe rmo r e if   \\ ( ) x PP M A P  , then  y  is on the  ray  0 x x  . If  x  is a  non -vertex  point of the bound ary, then   y  is on the line throug h  x  no rmal to the bo unda ry at  x .  4. The ma p   \( ) PM A P P   taking  ea ch p o int to  its nea re st  boun dary p o i nt is   contin uou s a nd  () M AP  is a  clo s ed  set. Esp e cially imp o rtant is the f a ct that  () M AP  is  an  deform a tion retract of  P  because  P  can be  contin uou sly  deform ed o n t o  () M AP  without m o ving  any of the points of  () M AP .  Let  C  den otes the co nfigu r ation spa c e i n   2 R  and   BC  the  Co b s t a c l e  be a di sjoi nt  union of a fin i te numbe r of  polygon s, then  \ FC B  is the fre e  sp ace whi c h co nsi s ts of  a finite  numbe r of co nne cted poly gono us comp onent s.  Acco rding to afore m entione d facts,  Proposition  1  is obtain ed  [3].  Proposition  1.  The canoni cal retraction ma p   () FM A F  can be extended  contin uou sly to map  \( ) ( ) CM A B M A F .  On  the ba sis of  Propositio n 1 , we  can i n crea se th e  sampling s  i n   medial  axis o f  all the  corrid ors whi c h h a ve vario u s  clea ran c e s  in the  spa c e. In our p r ep rocessin g ph ase, the MAP R M   algorith m  for sampli ng the  mileston es o n  the medial  axis is given i n   Algorithm 1  [3].     Algorithm 1   MAPRM sa m p ling strategy   Input: N , the number of mile stones to ge ne rate   Output:  N  milestone s on the  medial axis o f   F   1:  repea t   2:  Gene rate a u n iformly ran d o m point  p  in  C .  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2545 – 255 2   2548 3:  Find the nea rest point  q  on  F  to  p .  4:  if   p  is  free  the n   5:  Take th e retraction di re ction  v  to be  qp , and let the start point  s  be  p .  6:  else   7:  Take th e retraction di re ction  v  to be  pq  , and let the start point  s  be  q .  8:  end if   9:  Usi ng bi se ction, move  s  in the dire ction  v  until  q  is not the uniqu e  nearest poi nt of  F  to  s . This  moves   s  onto the medial axis  of  F .  10:  until   N  milesto nes h a ve bee n gene rated.     After the milestone s which are u s ed to  construct a roa d map a r e ge nerate d  by  Algorithm 1 , we can u s e the cle a ra nce informatio n co mputed by  medial axis to  improve the  local pl anne r  of MAPRM. The cle a ra nce of one point  () x MA F  is  0 () t a n , clearanc e x dis c e x x   whi c h is illust rated in Figure 2. A corri dor is defined as:    ()  a n d   , | , ( ) , ( ) , ( ) 0 , w z cor x M A F x z w z w M A F c l e arnc e z cl earn c e w   (2)     in whi c h   is a pred efine d  value of  width. The  cleara n ce info rmation of  w z co r  is  () m i n ( ) | ww zz c l e a r anc e c or c l e a r a nc e x x c or   which is the  minimum s  value of the cle a ran c e s  of all   the points tha t  are in the co rrid o r (Fi g u r e  2).       Medial axis x F B B 0 x z w ( ) w z cl ea ran c e c or Group sold ie r     Figure 2. The  clearan ce inf o rmatio n of a corrid or      After the mile stone s o n  me dial axis a r e  gene rated  an d the cl earan ce info rmatio n of the  corrid ors is  acq u ire d , we  can improve the ex isting local pla n n e r of MAPRM by adding  the   following rule  to it.  If   () w z c l e a r anc e c or   Then  th e  mileston es i n   w z co r  are  delete d . At the sam e  time, we  sup p leme nt the numb e r of  milestone s that are del ete d  usin g  Algor ithm 1 .  In whic h,   is a n  u s e r  d e fined valu e  and  aforem entione d rule  mean s th at if the   clea ran c e of a  co rri do r  is smaller  th an , then the  co rri d o r i s  forbidde n to pa ss. At the same tim e ,  we  sho u ld  su ppleme n t the  numb e r of m ileston es to N . Up to p r e s e n t, the prep ro cessing  pha se  is accom p lished.        Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Soldiers ’  Group Beha vio r s  Sim u lation Base d on Im prove d  MAPRM (Meng Li )  2549 2.2. Impro v e  Quer y  Phase of MAPRM   In this pha se, A* algorit hm is u s e d  to find a pat h betwe en t he sta r t and  the goal  config uratio n, usin g the  ro admap  co nst r ucte d  in th e  prep ro ce ssin g pha se. Sim u ltaneo usly,  we  improve  the  MAPRM al go rithm o n ce a g a in by  ren o va ting the  heu ri stic fu nctio n  o f  A* algo rithm  in   existing MAPRM.   We use  () hz  to d enote th e h e u r istic fun c tion   in existin g  A*   algorith m  a n d   () hz  to  den ote  the improve d  heuri s tic fun c tion.    () () ( ) m a x ( ) , ( ) h z h z clea ra n c e x clea ra n c e z cl ea ra n c e w   (3)     whe r e () m a x ( ) , ( ) c l e a r anc e x c l e a r anc e z c l e a r anc e w  mean s that we  should ta ke i n to   accou n t the  variation  of t he  clea ran c e  inform ati on  of the  co rrid o r  in  the  estim a ted  co st of t h e   path from mil e ston e  z  to the goal  config uration. In thi s  wa y, the bigger i s  the v a riation  of the  clea ran c e  of  a co rri do r, the larger th e  cost of p a ss in g this  co rrid o r to the go al. As the va riati on of  the cle a ran c e  refle c ts the  changi ng d egree of  g r ou p’s  formation  wh en pa ssing t h e co rri do r,  () hz   corresponds  to the  probability to sel e ct t he path through the  co rridor. Obviously,  () hz never  overe s timate s the  cost to  rea c h the  g oal. So  far, usin g improved A* algo rit h m, the gro u p’s  traveling path  can be g ene rated.       3. Formation  Transition o f  the Soldier s ’ Group   In this se ctio n, we p r e s ent  a flexible form ation ha ndli ng by the pro c e ss  of first sampling  the de sire d formatio n sh a pe, followe d  by a pat h pla nning  stage f o r ea ch  sam p le point s on  the  basi s   of jiayixu’s  work [6] .  Subse que ntly, so ldie rs i n  the g r o up  follow th e pa th between t h e   corre s p ondin g  sampl e  poi nts, while at the sam e  time  avoiding collision s  with e a c h othe r.   In ord e r to  d r ive the m o tion of an  enti r e g r ou p in  a more  cohe rent ma nne r  whe n  it  migrate s  fro m  initial formation to desi r ed one, we spe c ify a glo bal path  () Rt (B-s pline c u rv e )   betwe en the  cente r s of the  two formatio ns [6].   Let  1 O  and  2 O  re spectively re prese n t the ce nters of  the i n itial formatio n and th e de sire d  formation. We set  1 O  as the start point,  2 O  as the end poi nt of the B-sp line cu rve. Similarly, we   assume  1 S  and   2 S as the two  corre s p ondin g  sam p le p o ints of one  so ldier in th e g r oup  on the   initial formati on and the d e s ire d  formatio n, as illustrated in Figu re 3 .       1 O 2 O 1 S 2 S () Ot () St () St () R t     Figure 3. The  formation tra n sition of the  grou p       Then the cen t er of the gro up  () Ot  betwe en  the initial and  the desired formatio n ca n  be   comp uted by formulatio n (4 ).    12 () ( 1 ) Ot t O t O   (4)     Similarly, 12 () ( 1 ) St t S t S  . Then the path b e twee n  1 S  and  2 S   can b e  co nstructed a s :   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2545 – 255 2   2550 12 1 2 12 12 ( ) () () () SS S S St R t O t S t OO O O   (5)     One maj o r a d vantage of t h is p a th co ntrol schem e is  that we only  need to p a ra meteri ze  the path on ce for all sa m p le point s [6]. At  the sam e  time, Homi ng beh avior  whi c h is u s e d  to   drive the  sol d ier and  colli sion  avoidance behavior whi c h  i s   used  to avoid collisions  bet ween   soldi e rs are utilized to  steer the soldier.  In this  way, the form ation  trans ition phase of the  group   is accom p lished.      4. Experimental Re sults  and Con c lus i ons  In our  sim u l a tion, we  e m ploy a h u m an a n imati on softwa r e  packa ge  call ed DI -Guy,  whi c h is com m ercially available from Boston Dy n a m i cs In c. we control the be haviors of the  she phe rd an d the flock u s ing SDK by  C++ pro g ra ms. We sup pose the followin g  scena rio to   prove  ou r m odel: a  squa d of  soldi e rs form s a  co here n t g r ou p ,  this g r o up  tactical  targe t  of  marchin g  fro m  the initial p o sition to th e  goal p o si tion   to get on the  army  tru c ks. Figure  4(a) gi ves   the initial  co nfiguratio n of  enviro n ment . Fig. 4( b ) , (c),  (d) give t he snap sh ots of  simulati on  res u lts.          (a)  initial simulati on environment      (b)  sna p shot at t=20 s  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Soldiers ’  Group Beha vio r s  Sim u lation Base d on Im prove d  MAPRM (Meng Li )  2551    (c) sn ap shot  at t=29s         (d)  snap sh ot at t=35s    Figure 4 .  Simulation re sult s of the soldi e rs’ g r o u p       From Fig u re  4, we can  se e that improved  MAPRM a l gorithm ge ne rate a more realisti c  path for soldi e rs’  gro up by  con s ide r ing  the clea ra nce  information  of the spa c e.  And in narro w  corrid ors, the grou p ch ang e s   its formatio n automatical ly.      5. Summar y   In this pa pe r  we h a ve p r e s ented the  sol d iers’ g r ou p b ehaviors by i n trodu ce  an i m prove d   MAPRM alg o rithm. In o u r ap proa ch,  we in co rpo r ated MAP R M algo rithm  with cl eara n ce  informatio n o f  the spa c e  by improve t he lo ca l  pla n ner and  A*  algorith m  in   query  pha se  of  MAPRM. Simultaneo usly, the soldie rs’  g r oup  ca n a d a p t its formatio n acco rdin g to the cl earan ce   informatio n. But, this pap er do esn’t take the inte ra ction bet wee n  the mob a nd the soldie r into   consideration. Further research es will focus on this problem.       Ackn o w l e dg ments   This pa pe r was supp orted  by national  n a tural scie nce foundatio n (6117 0160 ).       Referen ces   [1]    A Kamph u is,  MH Overmars. F i ndin g  path for c oher ent gro u p s usin g cl e a ranc e.  ACM  SIGGRAPH/Eurographics Sym p osium   on Computer Anim ation . 200 4: 193 -202.   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2545 – 255 2   2552 [2]    A Kamph u is,  JF Helg ers, MH Overm a rs . Motion   pla nni ng for  grou ps of  entities.  ACM   SIGGRAPH/Eurographics Sym p osium   on Computer Anim ation . 200 3: 193 -202.   [3]    C Hol l ema n  a nd L Kavr aki. A frame w ork for us in g the  w o rkspac e med i al a x is i n  prm  plan ners.  In  Internatio na l C onfere n ce o n  Rob o tics an d Automatio n . 200 0; 2: 1408- 141 3.  [4]    SH Cho on, H N  Quang, O Ye w - S o o n . Auton o m ous m u lti-a gents i n  fle x i b l e  flock formati on.  MIG2010 ,   LNCS 6 459 . 2 010: 37 5– 38 5.  [5]    F  Aurenh amm e r. Voron o i d i agrams: A su rve y   of a fun dame n tal g e o m etric data st ructure.  ACM   Com p ut. Surv .  199 1; 23: 345 – 405.   [6]    Xu  J, Jin  X, Y u  Y, She n  T ,  Zhou M.  S hap e- constrai ned  flo ck anim a tion. I n : Comp uter  A n i m ati on a n d   Virtual W o rl ds . 200 8; 19: 313 – 330.   [7]    CW Re y n o l ds.  Flocks, herds , and scho o ls:  A distribute d   beh avior a l mo del.  in Co mp ut er  Graphics .  198 7: 25– 34.   [8]    RT  Vaughan,  N Sumpter, J Hen derso n, A F r os t, and S Camero n. Exp e riments i n  au tomatic flock   control. Ro bot and Auto nom.  S y s. 20 00; 31:  09-1 17.   [9]    OB Bay a zit, JM Lien, NM Amato.  Better Group B ehav iors  using  Rul e -Ba s ed Ro ad maps . In Proc. Int.  W kshp. on Alg.  F ound. of Rob .  (W AF R), Nice, F r ance. 2002:  95-11 1.  Evaluation Warning : The document was created with Spire.PDF for Python.