I nte rna t io na l J o urna l o f   Ro bo t ics a nd   Aut o m a t io n ( I J R A)   Vo l.   7 ,   No .   1 Ma r ch   2 0 1 8 ,   p p .   48 ~ 58   I SS N:  2089 - 4 8 5 6 ,   DOI : 1 0 . 1 1 5 9 1 / i j r a . v7 i 1 . pp 48 - 58          48       J o ur na l ho m ep a g e h ttp : //ia e s co r e. co m/jo u r n a ls /in d ex . p h p / I JR A /in d ex   Ex plo ra tion Strat eg ies o Co o rdina ted  M ul ti - Ro bo t   Sy ste m A   Co m pa ra tive  Stu dy       Ay m a E l sh e na w y 1 K ha lil  M o ha m ed 2 H a ny   M .   H a rb 3   1, 2 De p a rtem e n o f   S y ste m s an d   Co m p u ters   En g in e e rin g ,   Al - A z h a Un iv e rsit y , Eg y p t   3 De p a rte m e n o f   In f o r m a ti o n   T e c h n o lo g y ,   M isr  Un iv e rsity , Eg y p t       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Sep   1 1 ,   2 0 1 7   R ev i s ed   Dec   1 2 ,   2 0 1 7   A cc ep ted   J an   2 6 ,   2 0 1 8       En v iro n m e n Ex p lo ra ti o n   is  th e   b a sic   p ro c e ss   th a m o st   o M u lt Ro b o t   S y st e m a p p li c a ti o n d e p e n d   o n   it .   T h e   e x p lo ra ti o n   p r o c e ss   p e rf o r m a n c e   d e p e n d o n   th e   c o o rd in a ti o n   stra teg y   b e t w e e n   th e   ro b o ts  p a rti c ip a t in g   in   th e   tea m .   In   th is   p a p e t h e   c o o rd in a ti o n   o f   M u lt R o b o S y ste m in   th e   e x p lo ra ti o n   p ro c e ss   is  su rv e y e d ,   a n d   t h e   p e rf o rm a n c e   o f   d iff e re n M u l ti   Ro b o S y ste m e x p lo ra ti o n   stra te g ies   is  c o n tras ted   a n d   a n a ly z e d   fo d if fe re n t   e n v iro n m e n ts  a n d   d if fe re n tea m   siz e s.   K ey w o r d :   C en tr alize d   co o r d in atio n   C o o p er ativ m u lti - r o b o t   Dec en tr alize d   co o r d in atio n   Mu lti - r o b o t e x p lo r ati on   Mu lti - r o b o t s y s te m s     Co p y rig h ©   2 0 1 8   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Ay m an   E s h e n a wy ,     Dep ar te m en t o f   S y ste m an d   C o m p u ter   E n g i n ee r in g ,   Al - A z h a Un iv e rsit y ,   Mo s taf E l N a h as   U n i v er s it y   R o ad ,   Nasr   C it y ,   C air o ,   E g y p t .   E m ail: e a y m a n el s h e n a wy @ az h ar . ed u . eg       1.   I NT RO D UCT I O N   A   m u lti - r o b o t s y s te m s   ( M R S)  is   s e t o f   m o b ile  r o b o ts   th a m a y   h a v s i m ilar   o r   d if f er en t   ca p ab ilit ies  w h er th e y   ar co n n ec ted   th r o u g h   w ir eles s   s en s o r   n et w o r k   to   s h ar th s e n s o r y   in f o r m a tio n   w it h   r ec o n f i g u r ab le  s e n s i n g   ca p ab ilit ies  [ 1 ] .   T h ess en tial  g o al  o f   MR is   to   ac h ie v co m p le te  task   i n   s h o r ter   ti m t h an   t h r eq u ir ed   ti m f o r   ac h iev i n g   th s a m ta s k   u s i n g   s in g le  r o b o t,  s in ce   in   MRS   t h tas k   is   p er f o r m ed   s i m u lta n eo u s l y   [ 2 ] .   MRS   h a s   n u m b er   o f   ad v a n tag e s   o v er   s i n g le  r o b o s y s te m   s u c h   as  h ig h er   f au lt - to ler an ce ,   co n s o lid atio n   o f   th o v er lap p ed   in f o r m a tio n   [ 3 ,   4 ] ,   p r o h ib itio n   o f   tas k   ex ec u t io n   b y   o th e r   r o b o ts   [ 5 ] ,   [ 6 ] ,   r ed u ctio n   o f   en er g y   co n s u m p tio n   w h ich   lead i n g   to   lo n g er   co m m u n icatio n   t i m d u r i n g   t h ta s k   ac h iev e m e n t [ 7 ] ,   [ 8 ] .   R ec en t l y   M R h a v b ee n   u s e d   in   s ev er al  ap p licatio n s   t h at  ar d an g er o u s   to   th h u m an   s u ch   as  p o s d is aster   r elief ,   m ilit ar y   ap p licatio n s ,   s ea r c h   an d   r escu e,   s u r v eilla n ce ,   clea n i n g ,   m i n clea r in g   [ 9 ] - [ 1 2 ] ,   etc.   I n   s u c h   ap p licatio n s   r o b o ts   s h o u ld   m ak e   d ec is io n   w h et h e r   to   s ea r ch   n e w   tas k s   o r   est ab lis h   co o p er ativ e   in ter ac tio n s   to   ac h ie v th e ir   in d iv id u al  a n d   co llectiv g o als [ 4 ] ,   [ 1 3 ] ,   [ 1 4 ] .     Mo s o f   M R ap p licatio n s   d e p en d   p r i m ar i l y   o n   t h e x p lo r atio n   o f   th e n v ir o n m en i n   a   m i n i m u m   ti m e,   an d   t h m ap   o f   t h en v i r o n m e n is   g en er ated   to   f o r m   th MR ex p lo r atio n   p r o ce s s .   MRS   ex p lo r atio n   p r o ce s s   en co u n ter s   s e v er al  c h allen g es  t h at  a f f ec its   p r o d u c tio n .   T h ese  ch alle n g es  ar s u ch   as  li m i tatio n s   in   th e n v ir o n m en t   t h at  m a y   f o r ce   r o b o ts   to   m o v e   to g et h er ,   r o b o t in ter f er en ce   w it h   ea ch   o th er   o r   th r ed u n d an c y   d u to   m is s in g   o f   s h ar ed   in f o r m atio n   [ 1 5 ] .     Du r in g   MR ex p lo r atio n   p r o ce s s ,   it  is   n ec e s s ar y   f o r   ea ch   r o b o t o   h av en o u g h   in f o r m a tio n   ab o u th ex p lo r ed   ar ea s   o f   th e n v ir o n m e n t,  s o   t h r o b o ts   ca n   p lan   th e ir   p ath s   a n d   co o r d in ate  th eir   ac tio n s .   A   r o b o t   ca n   in d i v id u al l y   e x p lo r d if f er en ar ea s   o f   th e n v ir o n m e n t ,   b u w it h o u an y   co o r d in atio n   it  m a y   b ex p lo r Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I SS N:  2089 - 4856       E xp lo r a tio n   S tr a teg ies o f Co o r d in a ted   Mu lti - R o b o t S ystem:   A   C o mp a r a tive    ( A yma n   E l sh en a w y )   49   th s a m ar ea   ex p lo r ed   b y   o th e r   r o b o ts ,   b lo ck   o th er   r o b o ts ,   in ter p o s o th er   r o b o ts   s en s o r   r ea d in g s ,   etc.   T h e   ab s en ce   o f   co o r d in atio n   in   MRS   lead s   to   w a s te  o f   e x p lo r atio n   ef f o r a n d   ti m e.   T h er ef o r e,   co o r d in atio n   b et w ee n   r o b o ts   in   MRS   e x p lo r atio n   is   n ec ess ar y   to   i m p r o v t h ex p lo r atio n   e f f icien c y   [ 1 5 ] ,   [ 1 6 ] .   T h co o r d in atio n   is   an   es s e n tial   tas k   o f   t h M R S   ex p lo r atio n   an d   s o   t h s y s te m   p e r f o r m an ce   ( ex ec u tio n   ti m a n d   s y s te m   u tili t y )   is   a f f ec ted   b y   its   q u alit y   [ 1 3 ] - [ 1 6 ] .   C o o r d in atio n   in   MRS   e x p lo r atio n   i s   u s ed   to   co m p lete  t h o v er al l   tas k   as s i g n ed   to   th e   MR t ea m ,   m er g e   th e   o b tain ed   i n f o r m at io n   b y   s e v er al  r o b o ts ,   d ea w ith   li m i ted   co m m u n icat io n ,   ass i g n   tas k s   to   in d iv id u al  r o b o ts ,   s p ec if y   s et  o f   r u les,  in ter ac to   ea ch   i n d iv id u al  r o b o ts ,   an d   o v er co m t h i n ter f er en ce s   b etw ee n   t h r o b o ts   s u ch   th a t h co o r d in atio n   ca n   b e   ac h iev ed   m o r e f f icien tl y   at  g l o b al  lev el  [ 1 6 ] - [ 1 9 ] .   I n   s p ite  o f   lo o f   d e v elo p m e n h a s   b ee n   d o n i n   M R ex p l o r atio n   m an y   c h alle n g in g   is s u es  ar s till   p r esen t.  T h ese  is s u e s   in cl u d co o p er atio n   co n tr o l,   co n cu r r en lo ca liz atio n ,   m ap p i n g ,   co lli s io n   av o id an ce ,   tas k   p lan n i n g ,   co m m u n icatio n   a m o n g   r o b o ts ,   co o r d in atio n ,   n a v ig a tio n   an d   ex p lo r atio n ,   etc .   A s   an   ex a m p le,     Fig u r 1   s h o w s   th at  th r ee   r o b o ts   tr ies  to   ex p lo r th e n v ir o n m e n a n d   n a v i g ate  to   th e ir   g o al  lo ca tio n s .   W h ile   R o b o 3   ca n   n av i g ate  to   its   g o al,   ig n o r i n g   t h r e m ai n i n g   r o b o ts ,   R o b o ts   1   an d   2   n ee d   to   c o o r d in ate  s o   as  n o to   cr o s s   th n ar r o w   d o o r w a y   s i m u lta n eo u s l y   [ 2 0 ] .           Fig u r 1 .   An   ex a m p le  o f   s i m p l n av i g atio n   tas k       Mo s o f   p r ev io u s   s tu d ie s   in   th is   p o in f o cu s   o n   th co o r d in atio n   b et w ee n   i n d iv id u al   r o b o ts   to   d ec r ea s ex p lo r atio n   ti m e,   b u o n l y   f e w   p ap er s   f o cu s   o n   h o w   co llab o r atio n s   b et w ee n   r o b o ts   af f ec th e   ex p lo r atio n   tas k   its el f   [ 1 2 ] ,   [ 2 1 ] ,   [ 2 2 ] .   I n   th i s   p ap er   th c o o r d in atio n   o f   M R e x p lo r atio n   is   s t u d ied   an d   s et  o f   co m m o n   r ec en tl y   u s ed   alg o r ith m s   ar p r esen ted   an d   co m p ar ed   f o r   s et  o f   d if f er e n tea m   s izes  a n d   d if f er en en v i r o n m e n s tr u c tu r es.   T h p ap er   is   o r g an ized   as  it  f o llo w s .   A   r e v ie w   o f   co o r d in atio n   i n   MR is   d i s cu s s ed   i n   s ec tio n   2 ,   w h ile  th e   p r o b lem   o f   ex p lo r in g   a n   u n k n o w n   e n v ir o n m e n i s   d escr ib ed   an d   f o r m u la ted   in   s ec tio n   3 .   T h m u lti - r o b o ex p lo r atio n   alg o r ith m s   ar d i s cu s s ed   in   s ec tio n   4 ,   co m p ar is o n   b et w ee n   th p er f o r m a n ce   o f   co o r d in atio n   s tr ateg ie s   is   s h o w ed   an d   an al y ze d   in   s ec tio n   5 ,   an d   f in a ll y   o u r   w o r k   is   co n clu d ed   w it h   s u g g es tio n   f o r   f u t u r e   w o r k s   is   p r esen ted   in   s ec t io n   6 .       2.   T HE   M RS C O O RDINAT I O N   T ASK S   T ask   co o r d in atio n   in   M R h as   b ee n   d iv id ed   in to   th r ee   ca teg o r ies  ac co r d in g   to   th ar ch itec tu r o f   th e   r o b o ts   team .     2 . 1 .   T he  Dec ent ra lized  Co o rdi na t io n Ar chit ec t ure   I n   th i s   ar ch itect u r th er is   n o   ce n tr al  co n tr o r o b o an d   a ll  th r o b o ts   ar eq u al  w i th   r esp ec to   co n tr o an d   ar e   co m p letel y   au to n o m o u s   i n   t h e   d ec is io n   m a k i n g   p r o ce s s .   I t   is   also   ca lled   d is tr i b u ted   ar ch itect u r in   w h ich   ea c h   r o b o in   t h tea m   is   r esp o n s ib l f o r   cr ea ti n g   its   i n d iv id u al  m ap p in g .   I n d i v id u a l   m ap p in g   i n f o r m atio n   ar ex c h an g ed   b et w ee n   r o b o ts   w h en   t h e y   m ee ea ch   o th er   i n   o r d er   to   b u ild   co m p lete   m ap   m o d el.   T h d ec en tr alize d   co o r d in at io n   r esp o n d s   to   d y n a m ic  e n v ir o n m e n ts   in   s u b o p ti m al  w a y   [ 2 3 ] .   T h d ec en tr alize d   co o r d in atio n   h a s   b ee n   i m p le m en ted   in   v ar io u s   ap p licatio n s   o f   M R e x p lo r atio n   s u c h   as  [ 2 4 ] - [ 3 4 ] .   T h h ier ar ch y   o f   d ec en tr alize d   ap p r o ac h   is   s h o w n   i n   Fi g u r 2 .       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   I J R A Vo l.  7 ,   No .   1 Ma r ch   2 0 1 8 :   48     58   50   2 . 2 .   T he  Cent ra lized   Co o rdi na t io n Ar chit ec t ure   I n   ce n tr alize d   co o r d in atio n   ar c h itect u r e,   th er is   a   ce n tr al   co n tr o l r o b o t ( lead er )   th at  h a s   t h ab ilit y   to   co m m u n icate   w i th   a ll o th er   r o b o ts ,   in   o r d er   to   s h ar t h g lo b al  in f o r m atio n   ab o u t t h e n v ir o n m e n t a n d   r o b o ts .   So   it  is   r e s p o n s ib le  f o r   m ap p in g   b y   co llecti n g   d ata  f r o m   o th er   r o b o ts .   T h is   ar ch itectu r p er f o r m s   w ell  f o r   a   s m al n u m b er   o f   r o b o ts   an d   r u n   f a s ter   t h an   d ec e n tr alize d   c o o r d in atio n ,   b u it  b ec o m e s   i n ef f icie n f o r   lar g e   n u m b er   o f   r o b o ts   d u to   th e   in f o r m atio n   lo s s e s   a n d   h i g h er   co m m u n icatio n   o v er h ea d .   T h is   co m m u n icat io n   o v er h ea d   m a y   lead   to   co m m u n icat io n   f a ilu r a n d   o th er   u n ce r tai n tie s .   T h ce n tr alize d   ar ch itectu r also   p r o d u ce s   h ig h l y   v u l n er ab le  s y s te m   i f   t h ce n tr al  co n tr o r o b o m al f u n ctio n s   an d   th e n t ir team   i s   d i s ab led   u n le s s   t h er is   an   alter n ati v r o b o [ 2 ] ,   [ 3 5 ] .   T h er ar e   lo o f   s tu d ies  b elo n g i n g   to   th ce n tr alize d   ar ch itect u r in   MR ex p lo r a tio n   s u c h   as   [ 3 6 ] - [ 4 0 ] .   T h h ier ar ch y   o f   ce n tr alize d   ap p r o ac h   is   s h o w n   i n     Fig u r e.   3 .           Fig u r 2 .   T h Dec en tr alize d   Ap p r o ac h   Hier ar ch y   Fig u r 3 .   T h C en tr alize d   A p p r o ac h   Hier ar ch y         2 . 3 .   T he  H y brid Co o rdina t io n A rc hite ct ure   T h H y b r id   co o r d in atio n   i s   an   i n ter m ed iate   b et w ee n   th e   ce n tr alize d   ar c h itect u r an d   t h e   d ec en tr alize d   ar ch itect u r [ 3 9 ] .   T h co n tr o p r o ce s s   is   ac h iev ed   u s i n g   o n o r   m o r l o ca ce n tr al  co n tr o r o b o ts .   T h is   s it u atio n   lead s   to   th e   o r g an izatio n   o f   r o b o ts   i n to   clu s ter s   w h er ea c h   cl u s ter   is   r e s p o n s ib le  f o r   p er f o r m in g   s u b - tas k s   i n d iv id u all y   i n   a   ce n tr alize d   m a n n er   [ 4 1 ] - [ 4 4 ] .   T h h y b r id   co o r d in atio n   p r o v id es  m o r r o b u s s o lu tio n s   a n d   ab le  to   in f lu e n ce   t h en tire   tea m s   ac tio n s   t h r o u g h   g lo b al  g o als  a n d   p lan s   [ 1 0 ] ,   [ 2 3 ] ,   [ 3 1 ] ,   [ 4 5 ] ,   [ 4 6 ] .       3.   T HE   M RS E XP L O RA T I O N   OF   U NK NO WN   E NVI RN M E NT S   T h MRS   ca n   b u s ed   to   ex p l o r all  th r eg io n s   o f   a n   e n v ir o n m e n to   g a th er   i n f o r m atio n ,   ac q u ir a   g r ap h ical  r ep r esen ta tio n ,   d etec t a ll th u n k n o w n   p lace   an d   f i n all y   b u ild   t h g lo b al  en v ir o n m en m ap   [ 4 7 ] .   T h e   g lo b al  en v ir o n m e n m ap   ca n   b b u ilt  b y   co llect in g   lo ca m ap s   o f   t h ex p lo r ed   ar ea s   b y   ea c h   r o b o in   t h e   MRS .   T h M R e x p lo r atio n   i s   en d ed   w h e n   t h g lo b al  en v ir o n m e n m ap   i s   p r ese n ted .   T h en v ir o n m en m ap   ca n   b r ep r esen ted   a s   g r ap h s   ( Vo r o n o d iag r a m ,   Vi s ib ilit y   g r ap h ) ,   ce lls   ( o cc u p an c y   g r id s ) ,   p o ly g o n s   o r   tr ee s   ( g r ap h   w it h o u t c y c les)  [ 4 ] ,   [ 2 1 ] ,   [ 1 2 ] ,   [ 4 7 ] .     3 . 1 .   T he  P ro ble m   De s cr iptio n   T h MRS   e x p lo r atio n   p r o b lem   i s   d ef in ed   a s   t h p r o b le m   o f   ex p lo r in g   a n   e n v ir o n m e n t   o cc u p ied   b y   a   s et  o f   o b s tacle s ,   u s i n g   s et  o f   id en tical  m o b ile  r o b o ts .   T h f o u r   m ai n   co m p o n e n ts   t h at  a f f e ct  th p er f o r m a n ce   o f   th i s   p r o ce s s   ar th en v ir o n m en t,  o b s tacle s ,   s et  o f   r o b o ts   an d   th ex p lo r atio n   al g o r ith m .     3 . 1 . 1 .   E nv iro n m e nt   An   en v ir o n m e n is   co n s id er ed   as  f in ite  t w o - d i m e n s io n al  s p ac w it h   en v ir o n m e n tal  b o u n d ar y   a n d   it   ca n   b r ep r esen ted   as  ce ll  b ased   m ap   o r   g r ap h   b ased   m ap .   I n   th C e ll - B ased   m ap ,   th en v ir o n m e n to   b e   ex p lo r ed   ca n   b d iv id ed   in to   s i m ilar   ce ll s .   Du r i n g   t h e x p lo r atio n   p r o ce s s ,   ea ch   ce ll  h a s   s p ec if ic  s tate  f r o m   f o u r   s tate s   [ 4 ] u n e x p lo r ed ,   f r ee ,   w all,   an d   f r o n tier .   T h u n e x p lo r ed   ce ll  h as  n o b ee n   v is i te d   b y   an y   r o b o t,  th e   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I SS N:  2089 - 4856       E xp lo r a tio n   S tr a teg ies o f Co o r d in a ted   Mu lti - R o b o t S ystem:   A   C o mp a r a tive    ( A yma n   E l sh en a w y )   51   f r ee   ce ll  is   o p en   an d   v is ited   b y   at  lea s o n r o b o t.  T h w all  ce ll  is   o cc u p ied   b y   an   o b s tacl w h ile  th f r o n tier   ce ll  is   d etec ted   as  a   f r ee   s p ac an d   i s   n o v is ited   b y   a n y   r o b o an d   it  s ep ar ates  t h f r ee   s p ac r eg io n   a n d   t h e   u n e x p lo r ed   r eg io n .   I n   th e   Gr ap h - b ased   m ap ,   th e n v ir o n m e n t i s   co n s id er ed   as a   g r ap h   co n s i s ti n g   o f   ed g e s   a n d   v er tices.   T h is   g r ap h   is   u n k n o w n   ap r io r w h er n o   ed g es a n d   n o   v er tices a r k n o w n   [ 7 ] ,   [ 2 2 ] .     3 . 1 . 2 .   O bs t a cles   T h en v ir o n m e n to   b e x p l o r ed   is   o cc u p ied   b y   s et  o f   r an d o m l y ,   s tatio n ar y   a n d   d is tr ib u ted   o b s tacle s   w ith   s h ap e s   an d   p o s itio n s   w h ic h   ar eith er   k n o w n   o r   u n k n o w n   [ 3 6 ] .     3 . 1 . 3 .   M o bil Ro bo t s   A   tea m   o f   m o b ile  r o b o ts   p e r f o r m s   t h ex p lo r atio n   tas k .   T h ese  team   r o b o ts   m a y   b in   s i m ila r   s tr u ct u r ( Ho m o g e n eo u s   r o b o ts )   o r   in   d if f er en s tr u ct u r ( h eter o g o n o u s   r o b o ts ) .   T h ese  r o b o ts   ca n   f r ee l y   m o v f r o m   o n ce ll  to   an y   o n o f   its   n ei g h b o r s   d ep en d i n g   o n   s o m lo ca in f o r m a tio n   ab o u th n ei g h b o r   r o b o ts   o r   th n ei g h b o r   ce lls   [ 1 ] ,   [ 2 1 ] .     3 . 1 . 4 .   E x plo ra t io Alg o rit h m s   A t   ev er y   ti m e   s tep ,   t h e x p lo r atio n   al g o r ith m   c h o o s es   o n o f   t h f r o n tier   ce lls   to   b t h n ex tar g et   f o r   r o b o b ased   o n   its   d is tan ce   an d   t h s ize  o f   t h e n v ir o n m e n to   b ex p lo r ed   at  th cu r r en s tep .   E x p lo r atio n   al g o r ith m s   a ls o   u p d ate  th ex is ti n g   m ap   b y   t h e   n e w   i n f o r m atio n   a n d   ass ig n   p ar ticu lar   g o al  to   r o b o ts   u s in g   d ef in ed   co s f u n ct io n .   T h s h o r test   p ath   f r o m   th r o b o ts   to   th g o als  a r th en   f o u n d   [ 5 ] .   Fin all y ,   th e   r o b o ts   ar n a v i g at ed   alo n g   t h p at h s .   s e o f   c o m m o n   e x p lo r atio n   al g o r ith m s   w il b d is c u s s ed   in   d etail  in   s ec tio n   4 .     3 . 2 .     T he  P ro ble m   F o r m ula t i o n   T h MRS   ex p lo r atio n   p r o b le m   is   co n s id er ed   as  r ep etitiv tas k   ass ig n m en ts .   A ea c h   s tep ,   r o b o t                                         is   as s ig n ed   to   g o al                                      w it h   m i n i m u m   ex p lo r atio n   ti m e.   T h r o b o           m u s tr av el                                    d is tan ce   to   r ea ch   th g o al     .   T h ex p lo r atio n   ti m is   ap p r o x im a ted   b y   [ 4 8 ] .   T h f o llo w i n g   f o r m u la  f o r   tr av eli n g   B er li n   r ea ch es  t h d esti n atio n   as  s h o w n   i n   eq u atio n   ( 1 ) .                                                                                        ( 1 )     T h o b j ec tiv is   to   f i n d   s eq u en ce   o f   tr aj ec to r ies           (          |                       )     a m o n g   all   p o s s ib le  tr aj ec to r ies            |                         )     th at  h a v e   m i n i m u m   ex p ec ted   m ea n   ti m o f   th ex p lo r atio n   en v ir o n m e n t   as  s h o w n   i n   eq u atio n   ( 2 ) W h er       an d              ar e   tr a j ec to r ies  o f   th         r o b o t,   T   tim e   n ee d ed   t o   tr av er s R   a n d   th f o r m u la  as  s h o w n   in   eq u a tio n   ( 3 ) .                                |   )   ( 2 )             |   )          )           ( 3 )   W h er       )   is   th p r o b a b ilit y   d en s it y   f u n ctio n   w h e n   p r io r   in f o r m atio n   ab o u o b j ec ts   is   av ail ab le.   T h       )   is   co n s id er ed   to   b th r atio   o f   th ar ea           n e w l y   m ea s u r ed   at  ti m w h en   t h r o b o ts   f o llo w   th tr aj ec to r ies      an d     th ar ea   o f   t h w h o le  e n v i r o n m e n th r o b o ts   o p er ate             ,   w h e n   th p r io r   in f o r m atio n   is   n o av ailab le.   T h f o llo w i n g   f o r m u la  f o r   p r o b ab ilit y   d en s i t y   as  s h o w n   i n   eq u atio n   ( 4 ) .           )                       ( 4 )     T h er ef o r E q u atio n   2   ca n   b r e w r itte n   as   s h o w   i n   eq u atio n   ( 5 ) .                                |   )                                 ( 5 )     Ass u m ptio n s :   i.   E ac h   r o b o in itiall y   h as  n o   in f o r m atio n   ab o u o th er   r o b o ts   an d   th en v ir o n m en e x ce p t   th r elativ e   d is tan ce s   w ith   o t h er   r o b o ts .   ii.   A ll r o b o ts   h a v th s a m g eo m etr ical  s ize s   eq u al  to   s ize  o f   g r id   ce ll.    iii.   E ac h   r o b o t is ab le  to   co m m u n i ca te  w it h   t h en v ir o n m e n w it h   n o   d ela y .     iv .   A ll r o b o ts   ca n   m o v u p w ar d ,   d o w n w ar d ,   lef t w ar d ,   an d   r ig h t w ar d   o n l y .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   I J R A Vo l.  7 ,   No .   1 Ma r ch   2 0 1 8 :   48     58   52   4.   M UL T I - RO B O T   E XP L O R AT I O N   A L G O RI T H M S   Ma n y   e x p lo r atio n   s tr ateg ie s   ex is t,  f o u r   m et h o d s   ar s t u d ied   w ith in   t h p r ese n ted   ex p lo r atio n   f r a m e w o r k ,   an d   th f o llo w in g   p ar ag r ap h   g iv e s   an   o v er v ie w   o f   th e s s tr ate g ies.     4 . 1 .   T he  F ro ntie B a s ed  E x plo ra t io n Alg o rit h m   T h k e y   id ea   b eh in d   f r o n ti er   b ased   ex p lo r atio n   alg o r ith m   is   to   g ai n   n e w   i n f o r m atio n   ab o u a n   en v ir o n m e n a n d   n a v i g ate  to   th b o u n d ar y   b et w ee n   e x p l o r ed   an d   u n e x p lo r ed   ter r ito r ies  at  t h ti m o f   m ap p in g   an d   n a v ig a tio n   [ 4 7 ] ,   [ 4 9 ] .   W h en   r o b o n av ig ates   to   f r o n ti er   ce ll,  it  w il in co r p o r ate  m o r o f   th e   s p ac co v er ed   b y   t h p ath   in to   m ap p ed   ter r ito r y .   I f   t h r o b o d o es  n o i n co r p o r ate  th en tir p ath   at  o n ti m e,   th en   n e w   f r o n tier   w ill  al w a y s   ex i s f u r t h er   alo n g   th p ath .   T h is   f r o n tier   s ep ar ates  th k n o w n   an d   u n k n o w n   ar ea   an d   p r o v id es  n e w   d est in atio n   f o r   ex p lo r atio n .   Nav ig atin g   to   s u cc es s i v f r o n tier   p o in ts   en ab les  t h e   ex p lo r atio n   o f   u n s ee n   ar ea s   ad d in g   t h in f o r m a tio n   to   th m ap ,   s o   th r o b o t   ca n   in cr ea s it s   k n o w led g ab o u t   th en v ir o n m e n t [ 4 9 ] .   Fig u r 4   an d   Fig u r 5   r ep r esen ts   s u m m ar y   o f   t h u s ed   s ea r ch   al g o r ith m   [ 4 7 ] .         W h il e   )   Un e x p lo re d   a re a s ex ist  &            ! n o _ f ro n ti e r _ w it h _ e n o u g h _ si z e   DO                   Re a d   c u rre n se n so r   in f o rm a t io n                   Up d a te t h e   m a p   w it h   th e   o b t a in e d   d a ta                   De term in e   n e w   g o a c a n d id a tes                                   If   No   f ro n ti e f o u n d   O                                                 ! T h e   g o a is  re a c h e d         Re t u rn   to   t h e   c o m m o n   S tati o n                     A ss ig n   th e   g o a ls  to   t h e   ro b o t s                                       If   No   a ss ig n e d   f ro n ti e )                                                 G o   b a c k   to   t h e   b a se .                                         If   (o v e rlap p in g   w it h   a n o t h e ro b o t)                                               T a k e   a   ra n d o m   ste p .                     P la n   p a t h s f o th e   r o b o ts.                   Ch o o se   t h e   b e st f ro n t ier.                    M o v e   th e   ro b o ts  to w a rd s th e   g o a ls.       W h il e   )   Un e x p lo re d   a re a s ex ist  &            ! n o _ f ro n ti e r _ w it h _ e n o u g h _ si z e   Re p e a   F o e a c h   e x p lo re a g e n DO                   I n it ialize   e x p lo re r                   Ex p l o re   e n v iro n m e n f o a   ti m e                     IF   a   re n d e z v o u p o i n is  re a c h e d                               OR a   p a re n is  i n   ra n g e   T HEN                                         S e n d   i n f o rm a ti o n   to   p a re n                       END   END   F o e a c h   re lay   a g e n DO          In it ial ize   re la y          IF   a   re n d e z v o u s p o in is  re a c h e d                                 OR   a   c h il d   is  i n   ra n g e   T HEN                             Re c e iv e   d a ta f ro m   c h il d     a g e n          END          I F   a   re n d e z v o u s p o in is  re a c h e d                               OR a   p a re n is  i n   ra n g e   T HEN                                       S e n d   d a ta t o   p a re n a g e n                 END   END   END      Fig u r 4 .   T h Fro n tier   b ased   e x p lo r atio n   alg o r it h m             Fig u r 5 .   T h R o le  b ased   ex p l o r atio n   alg o r ith m         4 . 2 .   T he  Ro le  B a s ed  E x plo ra t io n Alg o rit h m   T h r o le - b ased   ex p lo r atio n   alg o r ith m   i s   u s ed   to   ad d r ess   th p r o b lem   o f   l i m i ted   co m m u n icatio n   i n   MRS   e x p lo r atio n   f o r   s tatic  e n v ir o n m en ts   [ 1 7 ] ,   [ 2 7 ] ,   [ 5 0 ] .   I is   co n s id er ed   as   co m m u n ic atio n   a n d   p lan n i n g   p r o to co l   th at  en ab les  MR S   t o   co n s tr u ct  g lo b al  m ap   a n d   p lan   th eir   n ex m o v e m e n t s .   R o b o ts   ar m o v ed   to g eth er   in   m o b ile  n et w o r k   an d   s h ar r elev an i n f o r m ati o n   f o r   th tea m   [ 2 1 ] .   T h M R tea m   f o r m s   a   p r ed ef in ed   r ig id   h ier ar ch al  tr e w h ic h   is   m a n u all y   co n s tr u ct ed   b ef o r th r o b o ts   en ter   th en v ir o n m e n t.  E ac h   r o b o m a y   b in   o n o f   t h f o l lo w i n g   t h r ee   s tate s ,   th e   f ir s o n is   th e   B a s s t a t io n   th at   is   t h r o o o f   t h tr ee .   T h s ec o n d   is   t h E x plo re rs ,   w h ic h   e x p lo r th e   en v ir o n m en as   p o s s ib le  a n d   r et u r n   b ac k   to   r en d ez v o u s   p o in ts   at  p r e - ar r an g ed   s ch ed u le.   T h th ir d   is   t h Rela y s   th at  s h ar in f o r m at io n   ab o u th e n v ir o n m en t   b et w ee n   t h eir   ch ild r en   an d   p ar en n o d es  to   en s u r t h at  t h e y   h av t h s a m k n o w led g e   ab o u it.  A   s u m m ar y   o f   th p r o ce d u r is   p r esen ted   in   Fig u r 5   [ 1 7 ] ,   [ 5 0 ] .     4 . 3 .   T he  L ea der  F o llo w er   E x plo r a t io n Alg o rit h m   T h is   alg o r ith m   f o c u s e s   o n l y   o n   th r o le  o f   th tea m   r at h er   th an   t h en v ir o n m e n s tr u c tu r e .   T h r o les  ca n   b c h an g ed   ac co r d in g   to   t h d is ta n ce   to   th e   co r r id o r s   an d   th d etec tio n   r es u lt s .   A   r o b o m a y   b t h e   lead er   if   t h alg o r it h m   r ec o g n ize s   a   f r o n tier   as  co r r id o r ,   an d   th o th er   r o b o ts   w ill  b s et  as  f o llo w er s   o r   r o o m - ex p lo r er s   [ 9 ] .   T h f o llo w er s   co n s id er   t w o   f ac to r s ,   t h f ir s t   o n is   t h Co s t ,   w h ic h   is   th s u m   o f   p ath   co s t           f r o m   r o b o     to   th f r o n tier     ,   an d   r o tatio n   co s w h e n   t h r o b o m a k es  r o tatio n   to   r ea ch   t h tar g et  f r o n tier   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I SS N:  2089 - 4856       E xp lo r a tio n   S tr a teg ies o f Co o r d in a ted   Mu lti - R o b o t S ystem:   A   C o mp a r a tive    ( A yma n   E l sh en a w y )   53   an d   th o th er   is   t h F ro ntie utilit y ,   f o r   th       r o b o t   to   th f r o n tier         )     th er w ill  b e                  )     .   Fo r   th e   f o llo w er s ,   th r e w ar d   is   s h o wn   in   eq u a tio n   ( 6 )   an d   eq u atio n   ( 7 ) .                    )                                                          )                              ) )   ( 6 )                                   )   ( 7 )     W h er e       is   co n s ta n f ac to r   an d           is   th o r ien tatio n   o f   th r o b o ts   to   th tar g et  p o in t s   a n d           [       ] I n   th is   w a y ,   th o p ti m izi n g   d ec is io n   m o d el  o f   tas k   ass i g n m en t c a n   b g iv e n   as  s h o w n   i n   eq u atio n   ( 8 ) .                                         )         ( 8 )     W h er e            ,   is   th e   o p ti m al  d ec i s io n   s o l u tio n   o f   ta s k   a s s i g n m e n [ 9 ] .   T h d etails  o f   t h is   a lg o r it h m   is   g i v en   i n   Fig u r 6   an d   Fig u r 7 .       I np ut A   g r id   m ap   an d   t h las er   d ata  o f   r o b o ts .   O utput : a n   ar r an g e m e n t o f   r o b o ts   f r o n tier s     B u ild   th m ap   w i th   t h f r o n tie r s   an d   th laser   d ata.   E v alu a te  th lab els  m   o f   f r o n ti er         .   C o m p u te  th co s         f o r   ea c h   r o b o t       to   r ea ch   f r o n tier       .   Whil t h er is   an y   f r o n tier       w h ich   is   lab eled   co r r id o r   ( m   =1 )   w it h o u t a   tar g et  r o b o t   Dete r m i n r o b o     f o r   f r o n ti er         w h ich   s atis f y   th r o le  m o d el  b elo w                                        E nd   w hil e   Whil t h er is   an y   r o b o t       lef t w it h o u t a   tar g et  f r o n tier   w h ic h   lab el  m   i s   0   Dete r m i n r o b o t       f o r   f r o n ti er         f o r   th r o le  m o d el  ac co r d in g   to   th o p ti m a l d ec is io n   m o d el              )                                                  )   R ed u ce   o t h er   f r o n tier s   u til itie s   as   th e   laser s   r an g o f   r o b o     ca n   r ea ch .     E nd   w hil e   Ste 1 .   Su b tr ac th s m allest   en tr y   i n   ea c h   r o w   f r o m   all  t h en tr ie s   o f   it s   r o w .   Ste 2 .   S u b tr ac t h s m all est  e n tr y   i n   ea c h   co lu m n s   f r o m   all  t h e n tr ies o f   its   co l u m n .   Ste 3 .   Dr a w   li n es  th r o u g h   r o w s   a n d   co lu m n s   s o   th at  all  t h ze r o s   e n tr ies.   Ste p 4 .   T est f o r   o p tim a lit y                  I f   ze r o   lin n   th e n                        A n   o p ti m a as s ig n m e n o f   ze r o s   i s   p o s s ib le                        E x is t.                  E ls I F z er o   lin n   t h en                        Pr o ce e d   to   Step   5 .   Ste 5 .   Dete r m i n t h s m alle s en tr y   n o co v er ed   b y   a n y   l in e s .                  Su b tr ac th is   en tr y   f r o m   ea c h   u n co v er ed   r o w                  A d d   it to   ea ch   co v er ed   co lu m n .     Ret urn t o   Ste p 3 .     Fig u r 6 .   T h L ea d er   f o llo w er   ex p lo r atio n   alg o r ith m     Fig u r 7 .   T h Hu n g ar ia n   al g o r ith m         4 . 4 .   T he  H un g a ria n Alg o rit h m   T h Hu n g ar ia n   m eth o d   is   an   o p tim izat io n   al g o r ith m   th at  s o lv es  t h r o b o t - tas k   ass i g n m en t.  T h ass i g n m e n ca n   b w r itte n   i n   a   f o r m   o f   t h         m atr ix     ,   w h er th ele m en           r ep r esen ts   th le n g t h   o f   t h e   p ath   f r o m   t h         r o b o p o s itio n   to   th g o al        .   T h Hu n g ar ia n   alg o r ith m   f i n d s   th o p ti m al  a s s i g n m e n f o r   th e   g iv e n   co s m atr i x   C .   T h alg o r ith m   i n it iall y   ass u m es  t h at  th n u m b er   o f   g o als  ar eq u a to   th n u m b er   o f   r o b o ts ,   in   ca s th ey   a r n o eq u al,   an   i m a g i n ar y   g o al s   o r   r o b o ts   ca n   b ad d ed   an d   ass ig n ed   to   a   f ix ed   co s an d   th e y   ar s k ip p ed   d u r in g   th e x p lo r atio n   p r o ce s s .   A   s u m m ar y   o f   th p r o ce d u r is   s h o w n   in   Fig u r 7   [ 4 8 ] .       5.   T H E   S I M UL AT I O R E SU L T S   I n   o r d er   to   c o m p ar th ab o v lis ted   MRS   ex p lo r atio n   alg o r ith m s ,   MRESi m   is   u s ed   as  an   ex p lo r atio n   f r a m e w o r k   [ 4 7 ] ,   [ 5 ] .   T h s im u lato r   ass u m es  p er f ec lo ca lizatio n   an d   n o i s e - f r e s en s o r   d ata  [ 2 7 ] ,   [ 1 7 ] .   A   s et   o f   ex p er i m e n ts   is   p er f o r m ed   o n   t h t h r ee   d i f f er en m ap s   w it h   v ar io u s   s ize s   a n d   s tr u ct u r es  a s   d escr ib ed   in   Fi g .   8 .   I n   th is   s i m u latio n   w h a v ta k en   in   co n s id er atio n   t h co m p lex i t y   o f   t h m ap   as   an   i m p o r tan f ac to r   in   t h ev a lu at io n   o f   t h ese  al g o r ith m s .   T h S i m p le  m ap   in   Fi g u r 8 - a.   d esc r ib es  th ca s o f   a   b ig   r o o m   w i th   f o u r   o b s tacle s   r ep r esen ted   as   b lack   s q u ar es.  T h m ap   in   Fi g u r 8 - b .   r ep r esen ts   a   s l ig h tl y   s tr u ct u r ed   en v ir o n m e n t.  T h m ap   in   Fi g u r 8 - c.   r ep r esen ts   r ea l b u ild in g   w i th   m a n y   s ep ar ated   r o o m s .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   I J R A Vo l.  7 ,   No .   1 Ma r ch   2 0 1 8 :   48     58   54               Fig u r 8 .   ( a)   Sim p le  Ma p ,   ( b )   m o d er ate  Ma p ,   an d   ( c)   co m p l ex   Ma p       E ac h   en v ir o n m en w ill  b m o d eled   as  an   o cc u p an c y   g r id   o f   1 0 0   1 0 0   ce lls .   A ll  t h alg o r ith m s   ar test ed   to   co v er   th w h o le  e n v i r o n m e n b y   tea m   o f   id en t ica MRS .   I n   o r d er   to   g et  n ea r   ac cu r ate  ev al u atio n   r esu lt s ,   th e s ex p er i m en t s   w ill   b i m p le m e n ted   u s i n g   d i f f er e n n u m b er   o f   r o b o ts ,   t w o   r o b o ts   an d   f o u r   r o b o ts .   A ll   th e   s i m u latio n s   ar ex a m i n ed   o n   t h s a m h ar d w ar w i th   co r e - i5   p r o ce s s o r   o n   3 . 8   GHz ,   8   GB   R A M   r u n n i n g   x 8 6   6 4   w in d o w s .   T h to tal  n u m b er   o f   r u n s   ar th u s   ( 4   ex p lo r atio n   alg o r ith m s )   *   ( 3   en v ir o n m e n t   m ap s )   *   ( 2   tea m   s ize  co n f ig u r atio n s )   *   ( a v er ag o f   3   r u n s   f o r   ea ch   ex p er i m e n t)   7 2   r u n s .   Fo r   th e   Si m p le  m ap   e n v ir o n m en t,  t h s i m u latio n   r es u lts   f o r   all  al g o r ith m s   f o r   d i f f er en t   tea m   s izes   ( 2   r o b o ts   an d   4   r o b o ts )   ar s h o w n   i n   Fi g u r 9 .   T h s i m u lati o n   r esu l ts   i n d icate   t h at  t h f o u r   alg o r ith m s   g iv e   ap p r o x im a tel y   t h s a m r esu l t s   ex ce p th lead er   f o llo w er   alg o r ith m   w h ich   h as  s li g h tl y   d if f er e n b eh a v io r .   T h is   d if f er en ce   ca n   b esti m at ed   as  5 f o r   2   r o b o ts   team   s iz an d   f r o n tier   b ased   h as  s m all  d if f er e n ce   th a n   th e   o th er s ,   b u it  is   t h b est  o n as  s h o w n   in   Fig u r 9 - a.   T h lead er   f o llo w er   alg o r ith m   h as  th w o r s b eh a v io r   ( 1 4 . 8 % w o r s t h an   r o le  b ased   f o r   4   r o b o ts ) ,   d u to   i n ef f icie n t d is tr ib u tio n   lo ca lizat io n   o f   t h r o b o ts   at  th s tar s tep   an d   s o m eti m es  th f o llo w er s   d o   t h s a m t h i n g   t h at  th e x p lo r er s   d o .   T h h u n g ar ian   a n d   r o le  b ased   ap p r o ac h es a r th b est t w o   ap p r o ac h es in   ca s o f   2   r o b o ts   as sh o w n   i n   Fi g u r 9 - b.             Fig u r 9 .   T h Sm al l M ap   R es u lts   f o r   ( a)   2   r o b o ts   team   s ize,   ( b )   4   r o b o ts   tea m   s ize       T h s a m e x p er i m e n i s   test e d   f o r   th m o d er ate  m ap   d esc r ib ed   in   Fig u r 8 - b   a n d   th r esu lt s   ar e   p lo tted   as  s h o w n   in   F ig u r 1 0 .   T h r esu lt s   o f   t h is   e x p er i m en i n d icate s   t h at  t h f o u r   ex p lo r atio n   alg o r ith m s   ar v er y   clo s to   ea ch   o th er   w h e n   u s i n g   4   r o b o ts .   T h r o le   b ased   alg o r ith m   y ield s   b etter   r esu lts   f o llo w ed   b y   Hu n g ar ia n   m et h o d   as  s h o w n   in   Fig u r 1 0 . a n d   Fi g u r e   1 0 . b   r esp ec tiv el y .   T h er is   s li g h t l y   d if f er en ce   i n   Fig u r 1 0 . w h er th i s   d if f er e n ce   clea r l y   ap p ea r s   in   t w o   ap p r o ac h es:  th r o le  b ased   an d   t h lead er   f o llo w er   alg o r ith m s .   T h lead er   f o llo wer   w h ich   i s   1 3 . 2 w o r s th a n   th r o le  b ased   f o r   2   r o b o ts   an d   8 . 3 % f o r   4   r o b o ts .       Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I SS N:  2089 - 4856       E xp lo r a tio n   S tr a teg ies o f Co o r d in a ted   Mu lti - R o b o t S ystem:   A   C o mp a r a tive    ( A yma n   E l sh en a w y )   55       Fig u r e   10 .   Mo d er ate  Ma p   E x p lo r atio n   ( a)   u s in g   2   R o b o ts ,   ( b )   u s i n g   4   R o b o ts       Fin all y   t h s a m e   ex p er i m en t   is   test ed   f o r   m o r co m p le x   en v ir o n m e n a s   d escr ib ed   in   Fig u r 8 - an d   th e   s i m u latio n   r es u lt s   ar p lo tted   in   Fi g u r e   1 1 .   T h p er f o r m a n ce   o f   t h e x p lo r atio n   al g o r ith m s   f o r   tea m   o f   2   r o b o ts   is   v er y   clo s to   ea ch   o th er   as  s h o w n   in   F ig u r 1 1   an d   th lead er   f o llo w er   e x p lo r atio n   alg o r ith m   y ield s   t h w o r s p er f o r m a n ce   f o llo w ed   b y   f r o n tier   ap p r o ac h .   T h b est  r esu lts   ar ac h iev e d   b y   t h r o le  b ased   alg o r ith m   f o llo w ed   b y   H u n g a r ian   in   m o d er ate  m ap   a n d   th e   co m p lex   m ap   w h ich   e v e n   o u tp er f o r m s   t h r o le   b ased   alg o r ith m   in   s o m ca s e s .             Fig u r e   11 C o m p lex   Ma p   E x p l o r atio n   ( a)   u s in g   2   R o b o ts ,   ( b )   u s i n g   4   R o b o ts       T h r elatio n   b et w ee n   t h tea m   s ize  a n d   t h m ea n   t i m e   o f   ex p lo r atio n   is   id e n ti f ied   b y   co m p ar in g   t h e   r o b o ts   tr a j ec to r ies  f o r   all  alg o r ith m s   as  s h o w n   i n   Fig u r 1 2 .   T h s i m u latio n   r esu lt s   s h o w   th at  th r o le  b ased   alg o r ith m   h as   les s   e x p lo r atio n   m ea n   ti m co m p ar ed   to   th o t h er   alg o r it h m s   f o r   all  ca s es  o f   t h t h r ee   en v ir o n m e n t s   a n d   tea m   s izes.   Fi g u r 1 2   s h o w s   t h at  t h e x p lo r atio n   ti m e   d ec r ea s es  b y   i n cr ea s i n g   t h tea m   s ize.   Fo r   th e   s a m tea m   s ize,   th e   ex p lo r atio n   ti m i s   d ec r ea s ed   as  t h co m p lex it y   o f   t h e n v ir o n m e n t   is   d ec r ea s ed .   T h is   r esu lts   f r o m   t h f ac t th a t th o b s tac les i n   t h co m p lex   e n v ir o n m e n t l i m its   th d etec ti n g   r a n g e s   o f   ea ch   r o b o t.       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   I J R A Vo l.  7 ,   No .   1 Ma r ch   2 0 1 8 :   48     58   56         ( a)   Si m p le  m ap   ( b )   Mo d er ate  m ap   ( c)   C o m p le x   m ap     Fig u r 1 2 .   E x p lo r atio n   ti m m ea n   v s .   r o b o t te am   s ca le  i n   t h e   Mo d er ate  Ma p .       6.   CO NCLU SI O N   AND  F U T U RE   WO RK S   I n   th i s   p ap er ,   d if f er en co o r d i n ated   MR ex p lo r atio n   al g o r ith m s   ar p r esen ted ,   a n d   its   p e r f o r m an c e   ar an al y ze d   an d   co m p ar ed   f o r   d if f er en t   tea m   s izes  a n d   d if f er e n e n v ir o n m en t s .   R o le   b ased   ex p lo r atio n   alg o r ith m   y ie ld s   b etter   r esu lts   th a n   th o th er   u s ed   a lg o r it h m s   f o llo w ed   b y   Hu n g ar ian .   I n   th f u t u r w ca n   u s e   th e   r o le  b ased   e x p lo r atio n   alg o r it h m   as   t h m ai n   e x p lo r atio n   al g o r ith m   f o r   t h e   d esig n   o f   a   f r a m e w o r k   f o r   task   co o r d in atio n   in   M R S.  Mo r ef f o r ts   to   in cr ea s th n u m b er   o f   s i m u latio n   r u n s   to   en s u r m o r ac cu r ate   s tatis t ical  r esu lts .   T h r o le  b ased   alg o r ith m s   m a y   b i m p le m en ted   in   r ea l - ti m ap p licatio n s .       RE F E R E NC E S   [1 ]   A .   P a l,   R.   T i w a ri  a n d   A .   S h u k la,  Co o rd i n a ted   M u lt i - Ro b o Ex p l o ra ti o n   u n d e Co n n e c ti v it y   Co n stra in ts,   Jo u r n a o f   In f o r m a ti o n   S c ien c e   a n d   En g i n e e rin g ,   V o 2 9 ,   n o   4 ,   Ju 2 0 1 3 ,   p p   7 1 1 - 7 2 7 .   [2 ]   S .   Ch a n d ra   N,  L .   V a c h h a n a n d   A .   S in h a ,   A   De c e n tralize d   A p p ro a c h   f o A u to n o m o u M u lt i - R o b o Ex p l o ra ti o n   a n d   M a p   Bu il d i n g   f o T re e   S tru c tu re s,”  In d ia n   Co n tro Co n f e re n c e   In d ia n   In sti tu te  o f   T e c h n o lo g y   M a d ra s ,   5 - 7   Ja n   2 0 1 5 ,   C h e n n a i,   I n d ia.    [3 ]   K.  Ce sa re ,   R.   S k e e le,  S .   Yo o ,   Y.  Zh a n g   a n d   G .   Ho ll in g e r,   M u lt i - UA V   Ex p lo ra ti o n   w it h   L im it e d   Co m m u n ica ti o n   a n d   Ba tt e ry ,   IEE E   In tern a ti o n a l   Co n f e re n c e   o n   Ro b o t ics   a n d   A u to m a ti o n   (ICRA ),   2 6 - 3 0   M a y   2 0 1 5 ,   S e a tt le,  WA ,   USA .   [4 ]   Y.  W a n g ,   A .   L i a n g   a n d   H.  G u a n ,   F ro n ti e r - b a se d   M u lt i - R o b o M a p   Ex p l o ra ti o n   Us in g   P a rti c le  S w a r m   Op ti m iza ti o n ,   IEE S y m p o siu m   o n   S w a r m   In telli g e n c e   (S IS ),   1 1 - 1 5   A p 2 0 1 1 ,   P a r is,   F ra n c e .   [5 ]   M .   Ra jes h ,   G .   R.   Ja se   a n d   T . S . B.   S u d a rsh a n ,   M u lt i   Ro b o t   Ex p l o ra ti o n   a n d   M a p p i n g   u si n g   F ro n ti e Ce ll   Co n c e p t,   A n n u a IEE I n d ia C o n f e re n c e   (IND ICON ),   1 1 - 1 3   De c   2 0 1 4 ,   P u n e ,   In d ia.     [6 ]   T .   G u n n   a n d   J.  A n d e rso n ,   Eff e c ti v e   T a sk   A ll o c a ti o n   f o Ev o lv in g   M u lt i - Ro b o T e a m s   in   Da n g e ro u En v iro n m e n ts,   IEE E/ W IC/A C M   In ter n a ti o n a Co n f e re n c e o n   W e b   In telli g e n c e   (W I)  a n d   I n telli g e n A g e n T e c h n o lo g y   (I AT ),   V o 1 1 4 ,   1 7 - 2 0   No v   2 0 1 3 ,   A tl a n ta,  G A ,   US A .   [7 ]   S .   C.   Na g a v a ra p u ,   L .   V a c h h a n i   a n d   A .   S in h a ,   M u lt i - R o b o G ra p h   Ex p lo ra ti o n   a n d   M a p   Bu il d in g   w it h   Co ll isio n   Av o id a n c e A   De c e n tralize d   A p p ro a c h ,   S p r in g e r,   S c ien c e + Bu sin e ss   M e d ia Do rd re c h t ,   1 1   N o v   2 0 1 5 .   [8 ]   M .   A n d ries   a n d   F .   Ch a rp il let,   M u lt i - r o b o e x p lo ra ti o n   o f   u n k n o wn   e n v iro n m e n ts  w it h   id e n ti f ica ti o n   o f   e x p lo ra ti o n   c o m p letio n   a n d   p o st - e x p l o ra ti o n   re n d e z v o u u si n g   a n a lg o rit h m s,”  IEE E/ RS In tern a ti o n a Co n f e re n c e   o n   In telli g e n Ro b o ts  a n d   S y ste m s (I ROS),   3 - 7   No v   2 0 1 3 .   T o k y o ,   Ja p a n .   [9 ]   B.   W a n g   a n d   S .   Qi n ,   M u lt i - r o b o E n v iro n m e n Ex p l o ra ti o n   Ba s e d   o n   L a b e M a p s   Bu il d in g   v ia  Re c o g n it io n   o f   F ro n t iers ,   IEE In tern a ti o n a Co n f e re n c e   o n   M u lt ise n s o F u s io n   a n d   In f o rm a ti o n   In teg ra ti o n   f o In telli g e n t   S y st e m s (M F I),   28 - 2 9   S e p   2 0 1 4 ,   Be ij in g ,   Ch i n a .   [1 0 ]   S .   G ra y so n ,   S e a rc h   &   Re s c u e   u sin g   M u lt i - R o b o S y ste m s,”  S c h o o o f   Co m p u ter  S c ien c e   a n d   In f o rm a ti c s,   Un iv e rsit y   Co ll e g e   Du b li n ,   2 0 1 4 .   [1 1 ]     M .   A l - k h a w a ld a h ,   T .   M .   Yo u n e s,  I.   A l - A d w a n ,   M .   Nisira t   a n d   M .   A lsh a m a sin ,   A u to m a t e d   M u lt i - Ro b o t   S e a rc h   f o a   S tatio n a ry   T a r g e t,   In tern a ti o n a Jo u rn a l   o f   Co n tr o S c ien c e   a n d   E n g in e e rin g ,   Vo 4   (1 ),   2 0 1 4 ,   p p .   9 - 15.   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I SS N:  2089 - 4856       E xp lo r a tio n   S tr a teg ies o f Co o r d in a ted   Mu lti - R o b o t S ystem:   A   C o mp a r a tive    ( A yma n   E l sh en a w y )   57   [1 2 ]   R.   Re id ,   A .   Ca n n ,   C.   M e ik lejo h n ,   L .   P o li ,   A .   Bo e in g   a n d   T .   Bra u n l,   Co o p e ra ti v e   M u lt i - Ro b o Na v ig a ti o n ,   Ex p lo ra ti o n ,   M a p p i n g   a n d   Ob jec De tec ti o n   w it h   ROS,   IEE In telli g e n V e h icle S y m p o siu m   (I V ),   2 3 - 2 6   Ju n   2 0 1 3 ,   G o ld   Co a st,  A u stra li a .     [1 3 ]   A .   F a rin e ll ia,  N.  Bo sc o l o c ,   E.   Za n o tt o b   a n d   E.   P a g e ll o b ,   A d v a n c e d   A p p ro a c h e f o M u lt i - Ro b o C o o rd in a ti o n   in   L o g isti c   S c e n a rio s,” El se v ier,  Ro b o ti c s an d   A u to n o m o u s S y ste m s,  V o l   9 0 ,   A p 2 0 1 7 ,   p p   3 4 - 4 4 .   [1 4 ]     N.  P a lm ieri1 ,   X .   S .   Ya n g ,   S .   M a r a n o ,   Co o rd i n a ti o n   T e c h n iq u e s o f   M o b il e   Ro b o ts  w it h   E n e rg y   Co n stra in ts,   IEE E   In tern a ti o n a S y m p o siu m   o n   P e rf o r m a n c e   Ev a lu a ti o n   o f   Co m p u t e a n d   T e l e c o m m u n ica ti o n   S y ste m (S P ECT S ),   24 - 2 7   J u l   2 0 1 6 ,   M o n trea l,   QC,  C a n a d a .     [1 5 ]   L .   W u ,   D.  P u ig   a n d   M .   A .   G a rc i a ,   Ba lan c e d   M u lt i - R o b o Ex p lo r a ti o n   t h ro u g h   a   G lo b a Op ti m iza ti o n   S trate g y ,   Jo u rn a o f   P h y sic a A g e n ts,   Vo l.   4 ,   n o   1 ,   Ja n   2 0 1 0 .   [1 6 ]   R.   G .   Co lare a n d   L .   C h a im o w i c z ,   A   No v e Dista n c e   Co st  A p p ro a c h   f o M u lt i - ro b o t   In teg ra ted   Ex p l o ra ti o n ,   IEE 1 2 t h   L a ti n   A m e ri c a n   Ro b o ti c S y m p o siu m   a n d   3 rd   Bra z il ian   S y m p o siu m   o n   R o b o ti c s,  2 9 - 3 1   Oc t   2 0 1 5 ,   Ub e rlan d ia,  Bra z il .   [1 7 ]   J.  d .   H o o g ,   S .   Ca m e ro n   a n d   A .   Vi ss e r,   Ro le - Ba se d   A u to n o m o u M u lt i - R o b o Ex p lo ra ti o n ,   0 9 .   IE EE   In ter n a ti o n a Co n f e re n c e   o n   F u tu re   Co m p u ti n g ,   S e rv ice   Co m p u tatio n ,   C o g n it iv e ,   A d a p ti v e ,   Co n te n t,   P a tt e rn s ,   1 5 - 2 0   N o v   2 0 0 9 ,   p p   4 8 2 - 4 8 7 ,   A t h e n s,  G re e c e .   [1 8 ]   D.  F o x ,   J.  Ko ,   K.  Ko n o li g e ,   B,   L i m k e tk a i,   D.  S c h u lz  a n d   B.   S tew a rt,   Distrib u ted   M u lt i - r o b o E x p lo ra ti o n   a n d   M a p p i n g ,   IEE T ra n sa c ti o n o n   Ro b o ti c s an d   A u to m a ti o n ,   V o 9 4 ,   Ju 2 0 0 6 ,   p p   1 3 2 5 - 1 3 3 9 .   [1 9 ]   W .   Bu rg a rd ,   M .   M o o rs,  C.   S tac h n iss  a n d   F .   E.   S c h n e id e r,   Co o rd i n a ted   M u l ti - Ro b o Ex p l o ra ti o n ,   IEE E   T ra n sa c ti o n s o n   R o b o ti c s,  V o l.   2 1 ,   Ju n e   2 0 0 5 ,   n o   3 ,   p p   3 7 6   -   3 8 6 .   [2 0 ]   F .   S .   M e lo ,   M .   V e l o so ,   De c e n tr a li z e d   M DP w it h   sp a rse   in tera c ti o n s,”  El se v ier,  B. V ,   A rti f icia In telli g e n c e ,   V o l   1 7 5 ,   2 0 1 1 ,   p p .   1 7 5 7 1 7 8 9 .   [2 1 ]   A .   P a l.   R.   T iw a ri  a n d   A .   S h u k la,  M u lt i - Ro b o Ex p l o ra ti o n   i n   W irele ss   En v iro n m e n ts,   S p rin g e r,   S c ien c e + Bu sin e ss   M e d ia i n   A u to n o m o u s Ro b o ts ,   2 6   A p 2 0 1 2 ,   L L C.   [2 2 ]   T .   A n d re   a n d   C .   Be tt ste tt e r,   C o ll a b o ra ti o n   i n   M u lt i - R o b o Ex p lo ra ti o n T o   M e e o r   n o t o   M e e t?,”  S p rin g e r,   Jo u rn a o f   In telli g e n &   R o b o ti c   S y ste m s ,   V o 8 2 ,   M a y   2 0 1 6   ,   p p   3 2 5 3 3 7 .   [2 3 ]   B.   Du g a rjav   a n d   S .   L e e ,   S c a n   M a tch i n g   Ba se d   M u lt i - r o b o t   M a p   B u il d in g ,   In tern a ti o n a Co n f e re n c e   o n   M e c h a n ica a n d   I n d u strial  E n g in e e rin g   (ICM A IE’ 2 0 1 5 ),   8 - 9   F e b   2 0 1 5 ,   Ku a la L u m p u r,   M a lay sia .     [2 4 ]   X .   Da i 1 ,   L .   Jia n g   a n d   Y.  Z h a o ,   Co o p e ra ti v e   e x p lo ra ti o n   b a se d   o n   s u p e rv iso ry   c o n tro o f   m u lt i - ro b o sy ste m s”   S p rin g e r,   S c ie n c e + Bu sin e ss   M e d i a   in   A u to n o m o u s Ro b o ts ,   1 4   Ja n   2 0 1 6 ,   Ne w   Yo rk .   [2 5 ]   C.   Ch a n g   a n d   C.   T sa i,   Co o p e ra ti v e   Ex p lo r a ti o n   o f   Ne t w o rk e d   M u lt i - Ro b o S y ste m U sin g   M in ima In f o rm a ti o n   En tro p y ,   IEE 1 2 th   In tern a ti o n a Co n f e re n c e   o n   Ne tw o rk in g ,   S e n sin g   a n d   Co n tro l   Ho w a rd   Civ il   S e rv ice   In tern a ti o n a Ho u se ,   9 - 1 1   A p 2 0 1 5 ,   T a ip e i,   T a iw a n .     [2 6 ]   J.  Re n o u x ,   A .   M o u a d d i b   a n d   S .   L e .   G lo a n n e c ,   A   d e c i sio n - th e o re ti c   p lan n in g   a p p r o a c h   f o m u lt i - ro b o e x p lo ra ti o n   a n d   e v e n se a rc h ,   IEE E/ RS In tern a ti o n a Co n f e re n c e   o n   In telli g e n Ro b o ts  a n d   S y ste m s   (IROS),   Co n g re ss   Ce n ter   Ha m b u rg ,   S e p 2 8   -   Oc 2   2 0 1 5 .   Ha m b u rg ,   G e r m a n y .   [2 7 ]   V .   S p iri n   a n d   S .   Ca m e ro n ,   Re n d e z v o u T h ro u g h   Ob sta c les   in   M u lt i - A g e n Ex p lo ra ti o n ,   IE E In tern a ti o n a l   S y m p o siu m   o n   S a f e t y ,   S e c u rit y ,   a n d   Re sc u e   Ro b o ti c s (S S RR),   27 - 3 0   Oc 2 0 1 4 ,   H o k k a id o ,   Ja p a n.   [2 8 ]   L .   M a ti g n o n ,   L .   Je a n p ierre   a n d   A .   M o u a d d i b ,   Distrib u ted   V a lu e   F u n c ti o n f o M u lt i - Ro b o Ex p lo ra ti o n ,   IEE E   In tern a ti o n a C o n f e re n c e   o n   Ro b o ti c s an d   A u to m a ti o n   (ICRA ) , 1 4 - 1 8   M a y   2 0 1 2 ,   S a in t   P a u l,   M N,  U S A .   [2 9 ]   L .   M a ti g n o n ,   L .   Je a n p ierre   a n d   A .   M o u a d d i b ,   Co o rd in a ted   M u lt i - R o b o Ex p lo ra ti o n   Un d e r   Co m m u n ica ti o n   Co n stra in ts  Us in g   De c e n tralize d   M a rk o v   D e c isio n   P r o c e ss e s,”  Tw e n t y - S ix th   AA A I   Co n f e re n c e   o n   A rti f icia l   In telli g e n c e ,   2 0 1 2 .   [3 0 ]   Z.   Ya n ,   N.  Jo u a n d e a u   a n d   A .   A .   Ch e rif ,   M u lt i - ro b o De c e n tralize d   Ex p lo ra ti o n   Us in g   a   T ra d e - b a se d   A p p ro a c h ,   8 th   I n tern a ti o n a C o n f e re n c e   o n   I n f o rm a ti c s in   Co n tro l,   A u to m a ti o n   a n d   Ro b o ti c s (ICINCO),  2 0 1 1 .   [3 1 ]   A .   D.  Ha u m a n n ,   K.  D.  L ist m a n n   a n d   V.  W il lert,   DisCo v e ra g e :   n e w   P a ra d ig m   f o M u lt i - Ro b o Ex p lo ra ti o n   IEE In tern a ti o n a Co n f e re n c e   o n   Ro b o ti c s an d   A u to m a ti o n   (ICRA),  3 - 7   M a y   2 0 1 0 ,   A n c h o ra g e ,   A K,   USA .     [3 2 ]   A .   M a rjo v i,   J.  G .   Nu n e s,  L .   M a rq u e a n d   A .   d e   A lme id a ,   M u lt i - R o b o Ex p l o ra ti o n   a n d   F ire S e a rc h in g ,   IEE E/ RS J   In tern a ti o n a C o n f e re n c e   o n   In tell ig e n Ro b o ts  a n d   S y ste m s,  1 1 - 1 5   Oc 2 0 0 9 ,   S t.   L o u is,   USA .   [3 3 ]   L .   W u ,   M .   A .   G a rc ia,  D.  P u ig   a n d   A . S o le,  V o r o n o i - Ba se d   S p a c e   P a rti ti o n in g   f o Co o r d i n a ted   M u lt i - Ro b o t   Ex p lo ra ti o n ,   Jo u rn a l   o f   P h y sic a Ag e n ts,   V o l .   1 ,   n o .   1 ,   S e p   2 0 0 7 .   [3 4 ]   S .   Om id sh a f iei,   A .   A .   M o h a m m a d i,   C.   A m a to ,   S .   L iu ,   J.  P .   Ho w   a n d   J.  V ian ,   De c e n tralize d   c o n tro o f   m u lt i - ro b o p a rti a ll y   o b se rv a b le M a r k o v   d e c isio n   p r o c e ss e s u sin g   b e li e f   sp a c e   m a c ro - a c ti o n s,” IE EE   In tern a ti o n a Jo u rn a l   o f   Ro b o t ics   Re se a rc h ,   V o l .   3 6 (2 ) ,   2 0 1 7 ,   p p   2 3 1 2 5 8 .   [3 5 ]   Z.   Ya n ,   N.  Jo u a n d e a u   a n d   A .   A .   Ch e ri f ,   A   S u rv e y   a n d   A n a ly sis  o M u lt i - Ro b o C o o r d in a ti o n ,   In tern a ti o n a l   Jo u rn a o f   A d v a n c e d   Ro b o ti c   S y ste m s,  2 3   Oc 2 0 1 3 ,   S a in t - De n is,   F ra n c e .   [3 6 ]   J.  F a ig a n d   M .   Ku li c h ,   On   Be n c h m a r k in g   o f   F ro n ti e r - Ba se d   M u lt i - Ro b o Ex p l o ra ti o n   S trate g ies ,   IEE Eu r o p e a n   Co n f e re n c e   o n   M o b il e   R o b o ts  (E CM R),   2 - 4   S e p   2 0 1 5 ,   L in c o l n ,   U K.    [3 7 ]   S .   Kim ,   S .   Bh a tt a c h a r y a ,   R.   G h r ist  a n d   V .   Ku m a r,   T o p o lo g ica Ex p lo ra ti o n   o f   Un k n o w n   a n d   P a rti a ll y   Kn o w n   En v iro n m e n ts,   IEE E/ RS In tern a ti o n a Co n f e re n c e   o n   In telli g e n Ro b o ts  a n d   S y ste m s   (IROS),   3 - 7   No v   2 0 1 3 .   T o k y o ,   Ja p a n .     [3 8 ]   J.  Bu tzk e   a n d   M .   L ik h a c h e v ,   P l a n n in g   f o M u lt i - Ro b o Ex p lo ra t io n   w it h   M u lt i p le  Ob jec ti v e   Util it y   F u n c ti o n s,”   IEE E/ RS J I n tern a ti o n a C o n f e re n c e   o n   In telli g e n Ro b o ts  a n d   S y st e m s,  2 5 - 3 0   S e p   2 0 1 1 ,   S a n   F ra n c is c o ,   CA ,   USA .     [3 9 ]   J.  Ba n f i·  A .   Q.  L i,   I.   Re k leiti s,  F .   Am i g o n i,   N.  Ba sili c o ,   S trate g ies   f o Co o rd in a ted   M u lt ir o b o E x p lo ra ti o n   w it h   Re c u rre n Co n n e c ti v it y   Co n stra i n ts,   S p rin g e r,   S c ien c e + Bu sin e ss   M e d ia  i n   A u to n o m o u R o b o ts ,   L L C,   2 3   J u n   2 0 1 7 ,   p p   1 - 20.   Evaluation Warning : The document was created with Spire.PDF for Python.