TELKOM NIKA , Vol. 11, No. 4, April 2013, pp. 2264  ~   2 270   ISSN: 2302-4 046           2264      Re cei v ed  De cem ber 2 4 , 2012; Re vi sed  March 3, 201 3; Acce pted  March 10, 20 13   Velocity Perception: Collision Handling Technique for  Agent Avoidance Behavior        Na zree n Abd u llasim 1 , Ahmad Hairul Basori* 2 , Md Sah Hj Salam Abdullah Bade 3  1 Kulli yya h  of Information a nd  Commun i cati o n  T e chnolo g y ,  Internatio na l Islamic Univ ersit y ,  531 00 Gomb a k , Selang or, Mala ysi a   2 UT M VicubeL ab, F a cult y   of Comp uting, Un iversiti  T e knolo g i Mal a ysia Sk uda i, 813 10 Jo hor, Mala ys ia   3 Sekola h Sai n s  dan T e knolo g i ,  Universiti Mal a y s ia  Sa ba h, 8889 9, Kota Kin aba lu, Sab ah, Mala ysi a   *Corres p o ndi n g  author, e-ma i l : ajen dgre a t@ gmail,c o m 1 , uchih a .hoir u l@ g m ail.com* 2,  aba de 08@ ya h oo.com 3      A b st r a ct     Collis io n avo i d ance  beh avi o r is alw a ys ab ou t mai n ta i n in g free col lisi on  bet w een virtua l ob jects. It   is als o   ab out  g ener ating  ev asi on r out in g for  the  ag ents i n  v i rtual  envir on m ent suc h   as i n   crow d si mu lati on.   It consists of three  process e s w h ich are c onstructio n  of  Field of Vis i o n ,  Collis ion  ha n d lin g a nd co lli sion   respo n se. C o n s tructing fie l d  of visio n  is  al w a ys a da unti ng task  and  al w a ys in e n ig ma for the  desi g ne r   beca u se it is subj ected tow a r d s age nt ’ s  perc eptio n w h ic h is  varies to eac h of them. T here  are few  attemp ts   on d e si gni ng fi eld  of visi on  b a sed  on th e a gent ’ s   dyn a m i c  focus tow a rd  its surrou n d i n g . T herefor e, w e   prese n t a top  dow n ap pro a c h  study fro m  c r ow d simula ti o n  mod e li ng u n t il the col lisi o n  han dli ng l e vel  in   order t o  i d e n tify the s u itab le   crow d mod e li n g  for  our  ap pro a ch. H ence,  at  the  end  of th is  pa per w e  w i l l   be  abl e to discuss  the possib l e techn i qu es for constructi n g  a gent ’ s  fie l d of vision  and a n a l y z e its pot entia l i n   crow d simu lati on env iron men t.      Ke y w ords : av oid ance  beh avi o r, collisi on d e tection, crow d simulati on, aut o n o m o u s ag ent      Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion and Ba ck ground     Cro w d  Simul a tion i s  a  complicated  syste m. Th ro ugho ut years, the r e  are  many   developm ent approa che s  i n trodu ce d that is called  crowd mo delin g. They are segre gated by  the   different app roa c h taken  on definin g the virtual environme n t with the cro w d ag e n ts.  Furthe rmo r e, cro w d  simulat i on com p ri se s  of   many  ele m ents an d o n e  of th em i s   crowd  behavio r.  Cro w d  be hav ior i s   a  syste m  that p r ovid es  actio n s to  the auto nom ous ag ents  so that it  ca n  react  to its virtual  environ ment.  It adds  a se nse  of re a lism to the cro w d livelih ood  as if e a ch  o f  the   agent h a s  a  sense of intelli gent that  a b le  them to ma ke de cisi on m a kin g  up on th eir rea c tion th eir  surro undi ngs.  One of th e m o st ba si c cro w d b ehavio rs is Collisi on a v oidan ce. Ge nerally  Colli si on   avoidan ce i s  a me ch ani sm of which t he a gent  w ill  avoid a n y a gent fro m   col liding a nd  avoid   in te r s e c tion   w i th   s t a t ic ob s t ac les .  T h e r e is a  stu d y that di sti n ct  colli sion   avoidan ce  a s  a n   avoidan ce m e ch ani sm be tween  dyna mic obj ect s   and o b sta c le  avoidan ce  as a  avoida nce   mechani sm between dynamic with  stati c  obstacles[1].  However in this paper  we will mai n tai n   colli sion avoi dan ce a s  a g eneral avoida nce b ehavio r for both stati c  and dynami c  obsta cle s .    1.1 Cellular Automata    In orde r to u nderstan d th e archite c t of cro w d  beh avior, it is e s se ntial to unde rstand it s  cro w d  mo del.  The r e  are  m any ap pro a ch es  of cro w d  modelin g a n d  the m o st  co mmon  are  So cial  Force, Cell ul ar Automata  (CA) an d Rule  Based.  CA i s  a commo n model for  cro w d si mulation  in   the early co mputer g a me  developme n t espe cially  fo r a strategy and turn ba sed gam es. CA is  based o n  spa t ial spa c e  def ragm entation  of the virt ual  environ ment.  It is se gment s into  whe r e i t   is call ed as  cells [2]. In order to avoid ag ents in terse c t i ng with ea ch  other, CA can  define the ce ll  to allow on e  agent to  occupy only o n e  cell  at a tim e . Thu s  by a dapting thi s   approa ch,  CA will  guarantee fre e  colli sion/int e rsectio n  bet wee n  age nt  a nd any stati c   obje c t that de fine in occu pi e d   cell s. Althoug h CA i s  sim p l e  co mpa r e fo r many ot h e r  cro w d  mod e li ng, ho wever i t  is not  suitab le   to simulate d ense situatio n sin c e it can not  visuali z e  push or bo dy conta c t between ag ents.     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Velocity Perception: Colli si on Handling  Te chnique for Agent... (N azreen Abdullasim )   2265 1.2 Social Force     Social fo rce  wa s introdu ced by  Helbi ng  that in co rporate  Newt on’s law into  crowd  simulatio n  [3]. It functions  as colli sio n  avoidan ce and  ensu r e s  free  interse c tion  betwe en age nts.  More over,  so cial fo rce a b l e  to  simulate  pu sh   effe ct and body co ntact  b e twe e n   pa rticle s where  CA co uld not  perfo rm. It is a strai ght forward alg o rith m to impleme n t in cro w d  si mulation, thu s  it  can  sim u late  a large  amou nt of cro w d s .  Ho wever, it  i s  difficult to i n tegrate  soci al  force  with  oth e r  behavio r such as  path foll owin g, flee a nd many  oth e r. Fu rtherm o re,  soci al fo rce f ond to ward  sha k in g movement wh en the age nts are  in hi gh den si ty situation or at narro w sp ace s .     1.3 Rule Bas e d     In 1987, Crai g Reynold s  h ad introd uce d  Boid s that simulate flo c king be havior of birds  [4]. The simul a tion is  reali s tic and a b le t o  imitat e flocking b ehavio r to an extent whe r e e a ch b i rd   has thei r o w n  indepe nde nt behavio r. Each individual   can pe rform th ree di stin ctive action s which  are  co hesi on,  sep a ration a nd alig nment.  This  rule  ba sed mo del i s  e x tensible  and  able to  creat e   compl e x be h a vior. Th ro ug hout the  yea r s m any  re se a r ch ers i n tro d u c ed  thei r exp ansi on  of cro w d  simulatio n   su ch a s  Vi Crowd [5] and  Cle a rPath [6 ] wh ich  a r e ba sed   on Crai g Re ynolds’ s  wo rk.  In  1999, Reyno l ds ha d extended hi s wo rk by intr od ucin g Steeri ng Behavio r into his crowd  s i mulation [7]. This   work is   im po rtant   as  far as colli sion avoi dan ce  i s  co nce r n. Colli si on   avoidan ce  was int r od uce d  in  steeri n g  behavio r th at dedi cate s only to pe rform avoid a n c e   maneuve r  action for autonomou s ag e n t. Howeve r,  developing  cro w d  simula tion using ru le  based app ro ach i s  com p li cated  comp a r e to CA and  so ci al force. This is du e to the fact that  desi gning  be havior for thi s  cro w d mo d e l need to  b e  co nci s e a n d  yet comp re hen sive as  o n e   behavio r may  relate to anot her.        2. Cro w d  Simulation De sign Crite r ion    Accordi ng to crowd  sim u lation  design crit eri on (whi ch are  fl exibility,  extensibility,  execution efficiency  and scalability [8]), rule based i s  mo re fulfilli ng in  comparison  with other  cro w d  mod e l . Neverth e le ss,  executio n efficien cy  and  scala b ility are de p endin g  on t h e   compl e xity of the behavio r algorithm. A l though  rule   based is m o re com p licate d  in term of i t s   developm ent, it offer more  flexibility and extensibilit y compa r e to  CA and soci al force. Thu s , rule   based mod e l is more suita b le wh en de si gning  sop h isti cated b ehavi o r.       Table 1. The  Differen c e s  B e twee n Crowd Model s Pertaining To Th e Colli sion Handlin g   Cro w d M odel  Flex ibility     Ex tensibility   Scalability   Ex ecution   CA    Rigid to Space  partitioning  Based on space  expansion   Large  Fast  Social Force    Rigid to  Ne w t on’s La w  No Large   Fast  Rule Based    Continuu m  and  Based on Agent  decision   Yes   M ediu m   M ediu m           De signi ng re alistic  cro w d  behavio r ca n be a com p licated task. As the cro w d si mulatio n   getting mo re  reali s tic, cro w d b ehavio r  obviou s ly will  be mo re  co mplex and  h ence affectin g the   comp utationa l cost for co mputer p r o c essor  a nd m e mory. Ho wever, the sol u tion doe s n o t  necessa ry so lve with mo re  memo ry and  faster  pro c e s sor. It al so  ca n be d one  by simplifying th e   algorith m . Effectivene ss a nd efficien cy are the  fun d a m ental de sig n  obje c tives to be co nsi dered   in a real-time simulation. To maintai n  the inte ractive  rate pe rform ance, the tra de-off bet we en   pre c isi on an d  spee d execu t ion must be  balan ce a c co rding to the a pplication [9].      3. Adap ting Steering  Be hav i or     Steering Beh a vior whi c h  wa s introd uced by  Reynol ds is o ne of the best exa m ples o f   distrib u tive crowd be havior [1]. Distri bution of  cro w d be havior basi c ally co mpri se s of b a si c  steeri ng b e h a vior an d co mbination th ose. A s  fo r  example, flocking  beh avior is comp rise s of  three b a si c b ehaviors  whi c h a r e  coh e si on, se parat io n and  alignm ent. Dist ributi on facto r  in  rule  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 4,  April 2013 :  2264 – 2 270   2266 based  will  al low it to  be  co mbine d  a nd thu s   able  to cre a te  sophi sticate d   and  eme r ge nce   behavio r. Tab l e 2 is the example s  of  Basic a nd Comb ine stee ring b ehavior.       Table 2. Example of Basi c And Combi n ed Steerin g Behavior [1], [7]. [10]  Basic Steering Behavior    Combined Steeri ng  Behavior  -Seek and Flee   -Pursue and  evade  -Wander  -Arri v a l   -Obstacle avoidance  - C ollision avoida nce  -Containment   - W all follow i ng  -Path follo w i ng   -Flo w  field follow i ng  -Cohesion   -Separation   -Alignment   -Cro wd path follo w i ng   -Leade r follow i ng   -Unaligned collisi on  avoidance  -Que uing  - F locking  -Seek and Follo w i ng         In this paper  we  will focus on collision  avoi dance behavior as it i s  rel a ting toward our  resea r ch focu s. Colli sio n  a v oidan ce g e n e rally  pe rform avoidan ce   maneuve r  for the age n ts from  intersecting  or colliding with  ob stacles i n  the vi rtual environm en t. It is  a fundamental behavior  in  cro w d  sim u la tion be cau s e  it’s bee n  with many oth e r com b ination  of ba sic  beh a vior in  ord e r to   cre a t e  mo re  compl e x  beh av ior.  Ho wev e r,  colli sion  a v oidan c e itsel f  is a combi n ation of two b a si c   behavio rs which  are avo i dan ce  wi th  static  ob stacl e  and  avoid a nce with  dy namic ob sta c le.  Acco rdi ng to some  re sea r cher, avoida nce with st atic  obsta c le i s  known as Ob stacle Avoidan ce   and avoid a n c e with dyn a m ic ob stacl e  is kno w n a s  colli sio n  a v oidan ce [1]. Figure 1 i s  a n   example of  combi ned  st eerin g be hav ior in  ope nS teer  C++ lib rary fo r see k  an d flee t hat  inco rpo r ate  collision  avoid ance and o b stacle avoid a n c e [11].          Figure 1: Example of the Structu r e Of Combine d  Steering Be havio r      3.1 Collision Av oidance behav i or description     In order to m a intain the belie vability of crowd  simul a tion, it  is normal that each agent   sho u ld  not in terse c t  with e a ch  othe r a n d  not i n terse c t with  othe r  obje c t a s   wel l . This i s  fo r t he  purp o se to  visuali z e  the  solidity of the   corre s p o n d  ob je c t  in  vir t ual e n v ir on men t. U s u a lly th ere   will be two  types of coll ision avoi da nce; that  re spo n se to st atic ob stacl e s and  dyna mic  obsta cle s . Howeve r, the  mech ani cs  o f  these  two  colli sion avoi dan ce s are the same  whi c h  con s i s t of Constructio n  o f  agent’s pe rce p tion,  coll ision d e tecti on/pre d ictio n , and colli sio n   respon se.     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Veloc i ty  Perception: Collis i on Handling  Tec h nique for A gent... (Nazreen Abdullasim)  2267     Figure 2. Coll ision Avoida n c e Behavio r  Mech ani cs      Con s tru c tion  of agent’ s  pe rceptio n is th e  firs t  p r ocess of  colli sion avoidan ce beh a v ior.  It  is abo ut cre a ting a se nsor-like area to d e tect in terse c ting obje cts so that the agent woul d avoid   from colliding. There are  many ap proaches of  designing  the sensor such  as  using ray-casti n g,  boun ding vol u me te chni qu e, sp atial pa rt ition, and V e locity ob sta c le s te chniq ue  with ea ch  of t he  approa che s  come with the i r colli sion d e t ection alg o rit h m. Collisi o n  detection i s   about collisi o n   testing bet we en the age nts and the o b s tacl es  whi c h  later on will  pro c e ss th e collision  re spo n se   whe r e in colli sion avoid a n c e case is a resp on se  that moving the a g ent aw ay from the obsta cl e.  Ho wever, in this pa per  we  will discu s s a bout  the co nstruction of the  agent’s p e rception.     3.2 Collision Handling  w i th  Agent’s P e rception    The pe rcepti on in colli sion  avoidan ce is the fi eld of vision of the ag ent. It is an area that  rep r e s ent s a sen s o r  to detect ob stacle s. Obstacl e  ca n be the age n t or any object in the virtual  environment.  Moreover there are  set  of rules to be followed  when testing  collision in virt ua l   environ ment  with multi ag e n t. This i s  for  the purpo se  t o  maintain f r e e  colli sio n  an d create p r io ri ty  avoidan ce be tween age nt with  ag ent  a nd  ag ent with  ob stacl e s.  Table  3 is th e colli sio n  te sting  rule s betwee n  obsta cle s  (agent an d oth e r obje c t) a n d  perception.       Table 3. Colli sion Te sting  Rule s  Main O b ject  Collision T e sting  Obj e c t   T e st Validity   Perception Obstacle  True   Obstacle Perception  False  Perception Perception  False  Obstacle Obstacle  True         Colli sion te sting is u s u a lly a seri es  of te st betwe en  each  obje c t’ s edg es  or v e rtice s .  Compl e x obj ects  app are n t ly have more edg es a nd  ve rtice s  thu s   having mo re  testing. Thi s   will  cause m o re processing re sources and will affect t he efficiency of the whol e process. Therefore,  it is imp o rta n t  to sim p lify the obj ect  re pre s entat io n  so th at the t e sting  is le sser an d fa st er.  Gene rally, bo th perceptio n  and ob sta c l e  will be d e fine as  bou n di ng volume o r  basi c  p r imitive   sha pe such a s  sp here and  box. Figure 3  is an  exampl e of agent wit h  field of vision.      4. Velocit y  P e rception for Collision Handling    There a r e m any method s on con s tru c ting  age n t’s  perceptio n.  In openSte er that   simulate p e d e stria n  in st eerin g beh avior, t he perception is ba sed on the  con s tru c tion  of  boun ding vol u me an d ray - ca sting [7][1][11]. There ar e also  wo rks  on con s tru c ting the pe rcep tion  based o n   sp atial pa rtition i ng an d u s in g ro botic   ad aptation  o n  obsta cle avoi dan ce su ch as  reci procal ve locity app ro a c h[12][6]. Ho wever, th ere  is la ck of  resea r ch on  desi gnin g  t h e   perceptio n b a s ed  on  ag ent’ s  dyn a mi c fo cal  point. So   as to  h u man   perceptio n, th e si mulation   o f   agent’ s  dyna mic p e rcepti on will  able  to pro d u c e  more va ria n t rea c tion t o wa rd  colli si on  avoidan ce be havior. Figu re  4 and 5 dem onstrate t he differen c e s  b e twee n fixed perceptio ns  with  dynamic p e rception.     Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 4,  April 2013 :  2264 – 2 270   2268     Figure 3. Agent’s Field of Vision           Figure 4. Coll ision Avoida n c e u s ing Fixe d Perception           Figure 5. Coll ision Avoida n c e u s ing Velo city Perce p tio n       4. Discussio n  and Futu r e  Work     In this pap er we present  additional f eat ure to a u tonomo u s  ag ent that the dynamic  toward ag ent’ s  pe rception   focal p o int m a y re sult  a di fferent re acti on toward  col lision  avoida n c e   behavio r. Thu s  in som e  scenari o  su ch a s  in figure  5, the faster a g e n t may react first sin c e it has  longe r focal p o int relative t o  its velo city. In addition, th e slo w e r  do e s  not h a ve to  respon se  sin c e  its perceptio n  does n o t detect any ob sta c le by hav ing  shorte r focal point hen ce it  does n o t nee d   to go for unnecessary collision  testing. The  dynamic percepti on may  also be extended it   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Velocity Perception: Colli si on Handling  Te chnique for Agent... (N azreen Abdullasim )   2269 possibility by  able to generali ze avoi dance  maneuver behavior since its  collision  detection  gene rali zing  both static a n d  dynamic o b s ta cl es a s  onl y one type of  obsta cle.      In our future  work, we wou l d like to p r op ose  our  co nst r uctio n  of pe rceptio n field i n  crowd   simulation application. We also   woul d like to investigate the ot her possibilities  t hat can affect  human fo cal  point and the r efore be co me  agent’s  a r gu ments to ward  its dynamic p e rception.       Referen ces   [1]  I Millin gton, J  Funge.  Artificial Intelligence fo r Gam e s, Sec o nd Edition . Mor gan K aufma nn  Publis her s   Inc., 2009.  [2]  J Dijkstra, J   Jesurun, H T i mmermans. A  mult i-a g e n t  cellu lar  autom ata mo del  of  pe destria n   movement.  Pedestria n an d Evacuati on Dyn a mics . 200 2; 173– 18 0.  [3]  D He lbi ng,  L  Buzn a, A J oha nsso n, T   W e r ner. Self- O rganiz ed P e destria n Cr o w d D y n a mics:   Ex pe ri me n t s, Si mu l a tio n s , a nd D e si gn  So l u tion s.  T r ansportat i on Sci ence . 2 005; 39( 1): 1–2 4.  [4]  CW Rey nolds. Flocks, herds and schools: A  distributed behavior al  model. 1987; 25–34.   [5]  SR Muss e, D  T halmann. A   Mode l of  Hum an  Cro w d  B e h a vior: Gro u p  In ter-Relati ons hi p a n d  Co llis ion   Detectio n Ana l ysis.  Proc. W o rkshop of Co mputer Ani m at io n and Si mul a ti on of Euro gra phics.  19 97;   39– 51.   [6]  SJ Gu y ,  J Ch hug ani, C Kim ,  N Satish, M Lin, D Man o c ha, P Dub e y .  ClearP a th: hi ghl y p a ra lle l   collis io n av oi d ance  for m u l t i-age nt simu l a tion.  Proceedings of  the 2009 ACM SIGGRAPH  Eurogr aph ics Symp osi u m on  Computer An i m ati o n . Ne w  O r lea n s. Louis i a na. 200 9; 177 – 187.   [7]  C Re yn olds. S t eerin g Beh a vi ors for Autono mous Ch aract e rs.  Game D e velo pers Co nf erenc e.  San  Jose. Cal i forni a . 1999; 7 63– 7 82.   [8]  S Z hou, D Ch en, W  Cai, L  Luo, MYH  Lo w ,  F   T i an, VSH T a y ,  DW S  Ong, BD Ham ilton. Cro w d   mode lin g an d simulati on tech n o lo gies.  ACM T r ans.  Model. Co mp ut.  Simu l . , 2010; 20(4):  1–3 5.  [9] C  Ericson.  R eal-T i m e  Co lli sion  Detecti o n  (T he Mor g a n  Ka ufman n   Series  in  Inte ractive  3- D   T e chno logy) .  Morga n  Kaufm ann. 20 05.   [10]  N Pe lech an o,  JM Allb eck, NI  Bad l er. Vi rt ual  Cro w d s : Meth ods, Sim u lati o n , an d  Contro l,”  Synthes i s   Lectures o n  Co mp uter Graph i cs and Ani m ati o n . 200 8; 3(1): 1–1 76.   [11]  OpenSteer. Av aila bl e: h ttp:// w w w . r e d 3d.com/ c w r/steer/.   [12]  J van de n Be rg, MC Lin, D  Manoch a . Re ciproc al Ve loci t y  Obstacles f o r Rea l -T ime Multi-Ag en t   N a vi ga ti on .  IEEE International Conferenc e  on Robotics And Autom a tion . 200 8; 192 8– 19 35.                                                   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 4,  April 2013 :  2264 – 2 270   2270       Evaluation Warning : The document was created with Spire.PDF for Python.