IAES Inter nat iona l  Journ al  of A r tifici al I nt el li gence  (I J - AI )   Vo l.   8 , No .   2 ,  J un e   201 9 , pp.  95 ~ 106   IS S N: 22 52 - 8938 ,   DOI: 10 .11 591/ijai. v 8 .i 2 .pp 95 - 106          95       Journ al h om e page :  http: // ia es core .c om/o nline/i nd ex .ph p/I J AI   Develop ment of  path pla nn ing algorithm  of  ce ntip ede inspi re d  wheeled  ro b ot  in  presenc e of st atic and mo ving obs tacles us ing  modified   critic al - snakebug  algorit hm       Subir K um ar Da s 1 , Aj oy Ku mar  Dutt a 2 , S ubir Ku mar   Debnat h 3   1 Depa rtment   of C om pute r  Appli ca t ion ,   As ansol Engi ne eri ng  Co l le ge ,   Ind ia     2 ,3 Depa rtment   of   Producti on   Enginee ring ,   Jad avpu r  Univer sit y ,   Ind ia       Art ic le  In f o     ABSTR A CT   Art ic le  history:   Re cei ved   Dec  20, 201 8   Re vised  Ma r   6 ,  2019   Accepte d  Ma y  5,   2019       Path  pla nn ing  f or  a  m ovable  r obot  in  r eal   l ife  situa t ion  h as  bee n  wi d e l y   cul ti v ated  and  b ec om e  rese arc h   int er est  for  la s t  few  de ca d es.   Biom imeti c   robots  have   inc r ea sed  a tt ra ct ion  for  the ir  c apa b ilit y   to  dev el op  v ari ous  kind   of  walki ng  in  orde r  to  navi g a te   in  different   envi ronm ent .   T o  m ee t  thi s  re quire m ent   of  nat ura l  insec t  lo comotion  has  ena ble d  th e  developm ent   of   compos it e  ti n y   r obots.  Alm ost  al l  insec t - sc al e  l eg ged  robots  ta ke  m oti vat ion  from   stiff - bod y   hexa pods;  thoug h,   a  d iffe r ent   dis ti nctive  org ani s m   we  find  in   nat ure   is c en ti pe de,   disti nguis h ed   b y   it s num ero us l egs  and  pli abl e bod y .   Thi s  unique ness  is  a nti ci p ated  to  pre sent  per form ance  bene f it s  to  bu il d  robot  o f   the   said  t y p e  in   te rm s  of   sw ift ness,  stea dine ss ,   toughne ss ,   and  ada pta t ion   abi lit y .   Thi s  p ap er  proposes  a   lo ca l   pat h   pla nn in g  al gor i thm  of  m ult ipl e  r ake  ce nt ipe de  inspire d  robot  na m ely   Modifi ed Crit ical - Snak eB ug   (MCS B)   al gorit hm .   Algo rit hm   tri es  to  avoi d  static  an d  d y nami c  obstacle  both .     The   r esult s d emons tra te t he   c apabili t y   of the   al go rit hm .   Ke yw or d s :   Bi oin sp i red m ob il e  rob ot   Bug al gorithm   Crit ic al  p oin t   Local  path pla nn i ng   Ob sta cl e a void ance   Op e n p oin t   Copyright   ©   201 9   Instit ut e  o f Ad vanc ed   Engi n ee r ing  and  S cienc e .    Al l   rights re serv ed .   Corres pond in g  Aut h or :   Subir  Ku m ar  Das ,   Dep a rtm ent  of   Com pu te r  A pp li cat ion ,   Asansol  En gine er in g  Coll e ge Asan so l,     West Ben gal,  Ind ia .   Em a il s: sub ir krdas@ gm ai l.com       1.   INTROD U CTION     Creat ing   bio lo gical ly   insp ire d  ti ny,  res ponsi ve  it ineran t  rob ots  has  al ways  bee n  gre at   interest   in  researc h  a rea.   Asp i rati on  f or  rob ots  to   trav e l  an d  c on t ro l  obj ect s   fl e xib ly   and  in de pende ntly   in  3D  sit ua ti on ,  reg a rd le ss   of  t he  pr ese nce ,  a bs e nce  or  dire ct ion   of  any   e xter nal  co ntr ol   syst e m   at tract s  resea rchers.   This  insp irat io n  is  he lping  to   de vel op  va rio us  bi om i m et ic   ro bots .  O ne   of  th e  re aso ns   to   beh i nd  this   is  eac h  ki nd   of  bio lo gical   crea ture  ha s  it s  ow n  ou tst a nd i ng  dyna m is m   c apab il it y  to  act   and   tra vel  throu gh   s pecific   ty pe  of  env i ronm ent, inclu ding c riti cal  an d co nf i ne d place . Som e  of  t he biolo gic al  insp irat io ns   are ex c el le nt clim ber s,   so m e  wond e rful  s wim m ers,   and  s om e   can  fly ,  so m e  jum p  ver y  well .  T he  nee d  for  robo ts   to  be   m ob il e  in   stran ge  an d  diff ic ult  en vir on m ents  is  rap id ly   increasing.  This  incr easi ng  dem and   br in gs   f oc us   on  di ff e ren t   kind  of  bio l ogic al ly   insp ired   rob ots.  Wh il e   discussi ng  ab ou t  path  plan ni ng   t he  pr o pe rty   of   e nv i ronm ent  or     the  local it y  w her e  the  r obot   will   wo rk   is  an  i m po rtan t  issue.   If   th e  env ir on m ent  is  sta t ic   then  al l     the  env ir onm e ntal  el e m ents  or   obsta cl es  ar e  sta ti c.  In   case  of   dynam ic   env i ronm ent  t he  el e m ents  m ay   be   sta ti c  or   m a y  be  dy nam ic .  T he  r obot  m ay   and   m ay   no t  know  al l  the  inf or m at ion   ab out  the  env ir onm ent.  In  dynam ic   env ir on m ent ,   path  plan ning  com es  in  two  form   a)  Global   pat h  plan ning  –   w her e  th e  inf orm at ion   about the envir on m ent is k nown  to  r obot b e fore it st arts  mo vi ng  a nd   b)  L ocal p a th p la nning   –   w he re the  r obot   do e sn’t hav e a ny infor m at ion  r egardin g  the  env i ronm ent. Th is i s sen sory  b ased pat h  pla nn i ng   wh e re the  r obot  us es  se nsors  t o  get  in f or m ation   a bout  the  ob sta cl es  to  a void  it  an d  reac h  desti nation.  In   case  of  loc al   path   plan ning  rob ot  acq uires  i nform at ion   ab ou t  l ocali ty   durin g  it s  m ov em ent.  In   unkn own  dy nam ic   env ir onm ent,  Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2252 - 8938   IJ - AI  V ol.  8 ,  No.  2, June   201 9 :   95   –   106   96   nav i gation  al gorithm   of   m ob il e  ro bot  av oidi ng   obsta cl e  can  be  done  us i ng  f uture  pre dicti on   with  t he  he lp  of   pr i or it y  be hav i or   [ 1].  The   sai d  process  us es   sing le   r a ke  r obot.   But  in   cas e  of  bi ologica ll y  insp ire d  r ob ot  li ke  sn a ke  r obot  th e  nav i gatio n  r equ i res  a  diff e ren t  kind  of  lo com otion   te ch niques  a nd   m echan ic s  [ 2].  A   sn a ke   rob ot  sh ould  be   so   desig ne d  and   m od el ed  physi cal ly   as  well   m a the m at icall y  so   that  it  beh ave s   li ke  rea l  sn ake   [3 ] . T he  m otion  p at te r n  of snake li ke  r obot  sh oul d  be  c on t ro ll ed  in s uc h way t hat it  w il l  b e able to  nav i gate on  la nd   as  well   in  water  [4 ] .  T he  m et ho d  t o  co nt ro l  m ov em ent  of   Sn a ke  rob ot  shou l d  be   well   def i ned   [ 5 - 7].  This  kind  of  rob ot  m ay   us e  wh eel s  for  m otion .  Othe r  interest i ng   bio l ogic al ly  insp ir ed  rob ot   is  centi pe de - li ke  m illi   rob ot [8]. T hes e k in ds   of ro bot’s g ai ts a re  now on e  of the  m os t i ntere sti ng  researc h  t op ic s . The n a vi gatio n  a nd  ob sta cl e  a voidi ng  pat h  plan ni ng  te ch nique  of  a  m ob i le   r ob ot  with   m ulti pl e  ra kes  us in g  vi su al   or  oth e r  s ens or s   therefo re  pay  at te ntion   m or e   and  m or e  [9 - 17 ] .  A par t  f r om   sn ake  a nd  centi pede  ot he r  ki nd s   of  stu died  bio m i m et ic  r obots ar e  sc orpio n [18,  19] an d  i nch wo rm  [ 20 ] .    Bug   al gorithm s  are  one  of  the  us e d  s i m ple  local   path  plan ni ng   te chn i qu e .  Crit ic al - Po i ntBu g  al gorithm   [2 1]   belo ngs  t o  bug  al go rithm   race  that  propos es  a  procedu re   to  reach   de sti nation  av oi ding  sta ti c  ob sta cl es.  Howev e r  this  al gorithm   con sid ers  a  po i nt  robo t.  A  de velo pm ent  fr om   t he  sai d  al gori thm   is    Crit ic al - Sn ake Bug   al gorithm   [22].  This  al gorithm   m od ifie s  the  Crit ic a l - Po i ntBug   al gorithm   so   that  the  m od ifie d  ve rsion   ca n  be  use d  for  bi o - i ns pi re d  sna ke  li ke  m ulti ple  rak e  r obot.  The  al gori thm   exists  in  [2 2]  is  us ef ul  f or   sta ti c  ob sta cl e  av oid ance   durin g  pa th  plan ning  f or  bio - ins pire d  m ul ti ple  rak e  r obot  w her e  eac h  ra ke   is  assum ed  to b e  a point.  B ut  obsta cl e  m a y  no t be  al ways stat ic   and   th e  r akes o f   the r ob ot  m ay   hav e  som e  non  neg li gi ble val ue  in  it s d im ension. In  t hose ca ses the al gorith m  ex ist s i n  [22 ]   m ay  n ot work  w el l.  T he pr op os e d  Mod ifie dCriti cal - Sn a keBu g( MC SB)  al gorit hm   her e  is  a   m od ific at ion   a nd   de velo pm e nt  of  al gorith m   pr esent  in  [ 22 ]   f or   m ulti ple  rak e  ce ntipede  i nspired  r obot  to  a vo i d  s ta ti c  as  well   as  dynam ic   ob sta cl e.   T h e   al go r it h m   pro po se d  he re   con side rs  the   rak es  of  rob ot  to  hav e  di m ension   not  as  po int.  T her e fore  durin g  obsta cl e   avo i dan ce  it  w i ll  calc ulate  the  safety  precauti on also   an d  t hus the  ge ner at e d path  is m or e r eal ist ic .         2.   PROP OSE D MET HO D    Im agine  a  bu g  is  m ov ing   to  a certai n  d irect io n  an d  faces w it h  an  obstr uctio n  in  it s  path.   T o  av oid   th e   ob st ru ct io n  the   bug  ci rcu m nav igate s  it   till   t he  m otion   to  t he  or i gin al   pat h  is  no t  furthe r  blo c ked.  The   bug  al gorithm s  fo r  local   path  pla nnin g  a nd   obsta cl e  avo i ding  ar e  insp i red   by  t his  be ha v io r  of   natu ral  bu g.   T hese  are  sens or   de pe nd e nt  pat h  pl ann i ng.  Tw o  m ai n  beh a vio r s  of   these  al go rithm s  are:  1.   m ov ing   to  the  obj ect ive  and  2.  bounda r y  fo ll owin g  of  an  e nc ountere d  ob sta cl e.   Bu g1,  B ug2  wer e   the  pr im ary  al gorithm s  introdu c e d  by  L um el sk y  et   al   [ 21] .  Si nc e  then   a  nu m ber  of  ver si ons  ha ve  bee n  ra ise d  of   bug  al gorithm s  each  with  a   dev el op m ent  than  t he  pre vious  one.  M os tl y  us ed  a nd  note d  in  path  plan ni ng   of   m ob il e  r obot  are  Ta nge ntBu g,   VisBu g,   DistB ug   et c.  Exce pt   these  few   ot her   al gorithm s  are  Re v,   Re v2,  O neBu g,   L eaveBu g,   P oint Bug ,    K - B ug,  Crit ic al - Po i ntBug,  Cr it ic a - Sn akeB ug  et c.  T he  m ai n  ob j ect ives  of  eve ry  bu g  al gorithm s  at tem pt  to   sh ort en  the  path,   sho rten  the  tim e  to  reach  de sti nation,   sim plify  the  al go ri thm   and   m aking   it   m o re  reali s ti c  in  ever y c o nd it io n,   s how n  i n  F i gure  1.           Figure  1.  Tra j e ct or ie s  form ed  by d i ff e ren t  bu g  al go rithm   with r e fer e nce t o l it eratur e [ 20]   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     IS S N:  22 52 - 8938       Develo pm e nt  of  p at h pla nn i ng a lg or it hm  of c entipede  ins pir ed  w heele d  r ob ot ...   ( Subir K umar  Das )   97   The  C riti cal - Sn akeB ug  al go r it h m   [22]  is  de velo ped  keepi ng   i n  m ind   of  m ulti   rak e  r obot.  This   al gorithm   trie s   to  avo i d  sta ti c  ob sta cl e   of  al l  it s  li nk s  wh il e   m ov in g  from   a  so urce  point  to  destinat io n  po i nt.  Using  it s  body   gest ur e  na viga ti ng   th r ough  cl uttered  a nd  r ough  s urr ound ing s   is  m uch   easi er  f or  s nake  li ke  m ul ti   rak e  r obot  than  ot her  robot.  Li ke  ot he r  m os tl y  us ed  bug  al go rithm s   this  al gorithm   al so   us e s  dm in  li ne  to   get  the  m ini m um   distance  f ro m   robo t  to  destinat io n.   T he  dm in  help s   the  r obot  to  reach  destinat i on   by   traversi ng  m inim u m   distance.  The  m ajo r  ad van ta ges  of  Bu g  al gorithm s  ov er  the  oth er  e xisti ng   path  pl ann i ng  and  obsta cl e  avo i ding  al go r it h m   is  it s  sim pl ic it y  and   us e  of  m ini mu m   nu m ber   s ens or s.   T his  pro posed  al gorithm   us es  the  te chn i qu e  of   on e  m or e  al gorithm   na m ely  “Op er at iveCrit ic al Po int  Bu g”,   wh ic h  is  ye t  to  be   publishe d.   T he   al go rithm   c on si ders  dyna m ic   path  plann in g  kee ping  i n  m ind   of   th e  di m ension   of  rob ot .   Th ough it  is no t y et  p ubli sh e d so no t  r e fen ce d i n  li te ratu re r e view.     2.1.   M od i fied cri tical – sn ak e bug a l go ri th m   This  al gorithm   assist s  to  locat e  the  path  and   pass  thr ough  it   fo r  a  bio l og ic al ly   centi pe de  ins pire d  wh eel e d  m o bile  rob ot  in  a  pl ane  fl oor  fill ed  wit h  obsta cl es.  T he  obsta c le s  are  unide nt ifie d  an d  of  sta nd a r d  form ,  di m ension,  a nd  locat io n.   To  reac h  th e  ta rg et   from   current  point  it   cal culat es  an d  determ ines  th e  ne xt  po i nt  to  m ov e  by  getti ng  on   t he  ob sta cl e  loc at ion .   Fig ure   2  shows  an   exa m ple  of   centi pe de  li ke  18  w he el e d  m ob il e  ro bot  [ 23 ]   known  a s  Tam iy a  70 230.   This  al go rith m   helps  to  na vi gate  a  r obot  in  pla nar  of  unknown   locat ion   w hich   is  fill ed  with  s ta ti c  as   well   as   dynam ic  ob sta cl es  of   unde fin ed  but  regular  sh a pe.   Ra nge  sen s or   is  us ed  to  rec ognize  a n  al te ra ti on   in  distanc e  to  recog nise   ob sta cl e  posit ion s .  Fig ure   3  sh ows  t he  sca nn i n g  process   of  a   r ang e   se ns or   i n  it s  fiel d  of  view  (FO V)   t o  detect   obsta cl es  [21].   We   belie ve   pe rh a ps   a n  unboun ded   s pa ce  Q  ⊂  R 2   occu pie d  by  a  set   of   bounde d  sta ti c  and   dynam i c  ob sta cl es  O  =  {O 1 ,O 2 ,  .  .  . , O K }.   The  w hole   en vir on m ent  is  c on si der e d  to  be   in  2D   with  t he  obj ect i ve  of  si m ulati on .  F ur t her   we  c ons ider  a  rob ot  w hich  is   m ade  up   of   a   series  of   w he el ed  r obot.  Th e  first  wh eel e d  rob ot  ra ke  is  furn is he d  with   rang e   sens or   t o  se nse   obsta cl es.  Fi g ure   4  il lustrat es  the  head  of   the  centi ped e  insp ire d  rob ot  in  rectan gula r  sh a pe  with  w heel   a nd  ot her   e quip m ent.  The  othe r  ra kes  c on ta i n  a  com pact,   m ul ti - cor e  pro pelle r  m ic ro co ntr oller   with  ha r dw a re   to  com m un ic at e  betwee n  eac h.   We  pu t  th e  rob ot  an d  the  ob sta cl e  in   2D   plane  a nd  ass um e  a   virtu al   ci rcle  s urrou nd i ng  the   r obot.  E ve ry  par t  of  the   r obot  will   be   c onsidere d  in side  a  virt ual  ci rcle .  T he   head  a nd   oth er  r akes ar e sam e in al m os t a ll   aspect b ut the o nly dif fer e nce  is a sen so r  is at ta ched  w it h  th e h ead   wh ic h  can  sca n  180 0   a rea.  D ur i ng   m ov em e nt  ever y  ra ke  or  sect ion   of   the   robo t  s uppose d  to  go  after  t he   sa m e  coor din at es  of   it s  pr edece ssor.  T he  init ia l  and   final  c oord i nate  with  respec t  to  global  f ram e  of   ref e re nce  is   known   to   r obot .  Pr i or  we   pr oc eed  t o  the   des cripti on  of  al gorithm s,  we   co m po se  so m e  im po rtant  an d  help fu l  assum ption  a nd  def i niti on   f or this alg or it hm   wh ic h  a re alm os t sam e as [ 22 ] .           Fi gure  2.  Ce ntipede  li ke wh e e le d  rob ot w it h re fe ren ce  to [2 3]       Figure  3.  O bs t acl es d et ect ed by ra nge  sens or(R)       Figure  4.  Dis play  o f  robot a nd  ob sta cl es i n 2 D plot       2.1.1.    As sum pt ion     The ro bot i s s uppose d be as  f e w ph ysi cal ly  an d analy ti cal ly conn ect e d  sm al l robo ts     The  al gorithm  u ses  w or ld  c o - ordinate syst e m  as g lob al  fra m e o f refe renc e     All p os it ion co ordinates  (incl ud i ng w it h i nit ia l and   goal )  a r e at first  quad r ant     The vel ocity  a nd ang ular vel ocity  o f  robot i s constant i n  e ver y m ov em ent an d r otati on r especti vely     The  e nviro nm ent is flat  a nd m ai ntains e qu al   al ti tud e eve rywh e re     The  m ob il e r obot m ov es  in  a   two - dim ensional  sp ace a nd ro ta te s w it hout sl ipp in g     Both  the  rob ot  and   dynam ic   ob sta cl es  a re  r un   i n  co ns ta nt  sp ee d  an d  in  st raig ht  li ne.   I f  anyo ne  wa nts  t o  change  directi on it  h a s to  sto p t hen  t urn  t hen  again st art m ov in g      Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2252 - 8938   IJ - AI  V ol.  8 ,  No.  2, June   201 9 :   95   –   106   98   2.1.2.     Imp or t an t   de finitio ns   The  r obot  sca ns   t he  s urr oundin gs   0 0   t o  180 0   by  ra nge  se ns or.   S o  t o  m a ke  a   sca n  of  total   36 0 0   t he   rob ot  has  to  r ot at e  the  head   pa rt  90 0   le ft  an d  righ t  a nd   s ca n  the  env i ronm e nt  again .  O bv i ou sly   it   is  req ui red   i f   the  centi pe de  ge ts  fu ll   of   obst acl e  at   18 0 0   sc an.   We  co ns i de r  on  bo unde d  and   unbo unde d  sp ac e  O  a nd   Q  in  a   read i ng   from   ran ge  sens or  wi thin  a  ti m e  per iod ,  t n   to  t n+1 .  I f  it   no ti ces  a  va riat ion   in  dist an ce  say   Δd  ( wh e re  Δd  value  is  defi ned)  in  range at  any  po sit ion  then  that  posit ion   point  is  regarde d  as  O pen  Po int.   T he  pri m aril y  the r obot f aci ng d irect ly  to  goal  p oin t an d  aft erw a rd  it  b egi ns scann i ng  fo r  op e n  point. S ub goal po i nt is  a  m id   obj ect ive  of  t he  r obot  t o  at ta in  the  fi nal  obj ect ive .  T his  point  is  placed  at   a  par ti cular  differe nc e  from     the  co rr es pond ing   op e n  po i nt  and   perha ps   create s  a  rig ht   ang le   at   ope n  po i nt  to  the  l ine  passi ng   t hroug h    the  se ns or  poin t  of  r obot  a nd  t he  open   point.   Fr om   the  c oor din at e  of  op e n  po i nt  c orrespo nd i ng  s ub  goal   point   is  determ ined.   The  r obot  sel e ct s  on e  po i nt  cal le d  crit ic al   po int,  f or  subse qu e nt  m ov e  from   a  set   of   su b  goa l   po i nts.  T his  po int  is  sel ect ed  on   t he  ba se  of  sm a ll est   distance  from   the  ta rg et   point  an d  s o  f a r  not  co ns i der e d  for  m ov em ent.  The   r obot  at te m pts  to  m ov e  i ts  each  rak e ’s  center  of  vi rtu al   ci rcle  to  c riti cal   po i nt  or  t o  virtu al   ci rcle’s  center  of   it s  pr e deces so r .  The  m idp oi nt  of   the  tw o  e xtrem e  po ints  of   eac h  r obot’s  rak e  is  centre  of   t he   corres pondi ng  virtu al   ci rcle  a nd  the  half  dis ta nce  bet ween  the  tw o  e xtre m e  po ints  of  t he  ra ke  with  a   safety   const ant    is  the  ra diu s .  The   lowest  valu e  of     ca n  be  ob ta ined  f ro m   few   num ber   of   e xp e rim ents.  Fig ure   4  sh ows  the  plo tt ing  a nd  oth e r  r equ i red ge om e tric al  d et a il s.    d  –   Per pendicular   distance  of obs ta cl e fr om  the  sens or   A  –   Locati on  of   r obot  w heel - ‘a xl e’ ( im aginar y l ine)  ce nter   X  –   Dista nce  from  sen s or  t o o pen  po i nt   w  –   Dista nce  betwe en wh eel - ‘a xle ’  ce nter  a nd wheel  cente r   F  –   Dista nce  betwe en  the  r ea r  e nd  and  w heel  ‘a xle’  ce nter    R  –   Dista nce  betwe en  the  wheel   ‘a xle’  ce nter  and  the  rear  e nd  of the  rob ot   C  –   Ce nter of  the  vi rtual circl e   α   –   Op e n p oin t  detect ion  a ng le  b y  the se nsor     -   Safety  constant  for  t he ro bot   r  –   Ra dious  of the  virtu al  ci rcle   β  –   Sensor  d i recti on a ng le  at  ope n p oin t  with  res pect to t he  li ne  p a rall el  to  x - a xis a nd p as sin g t hro ugh (x i ,y i )  befor e  m ov em ent   θ  –   Angle  gen e rate d by β  with  res pect to t he  li ne  p a rall el  to  x - a xis fo r  s ub goa l po i nt coo rd i na te s calc ulati on   –   Angle c reated  on a line  pa rall el  to  x axis  and  p assi ng th rou gh se nsor by a  li ne fr om  sen sor  to op e n p oin t      –   Angle  betwee n l ine joini ng  open po i nt & su bg oal a nd   the  li ne parall el  to x - axis a nd  passi ng th rou gh   op e n p oin t   d k –   Dista nce  of a s ub goal  po i nt fro m  cu r ren t l oc at ion   x s   a nd y s   –   a re  the sig n fact ors  u se d  i n determ inati on   of the   c oor din at es  of open  points   s x   an d  s y   –   are t he  si gn f act ors  us e d  to  d et erm ine the c oor dina te s o f  s ub goa l po i nts     We c onsider ,   T n = {( x 1 ,y 1 ),(x 2 ,y 2 ), ...,( x i ,y i )}   as a set  po i nts  t rav el le d   by t he  robot ’s  n t h  li nk   wh e re  (x i ,y i ) sym bo li ze the  coor din at e  values   t he nth lin k arri ved   OP = { ( (α a ,d a ) , (α b ,d b )),...., (( α k ,d k ) ,( α j ,d j ) ) }  as  a set o f  op e n  points  of obstac l es ide ntifie d   by  the se ns or  wh e re α a nd  d i nd ic at e the  angle s   &  d ist an c e s of  op e n p oint s   res pecti vely  f r om  the r ob ot  and each   ( (α a ,d a ),(α b ,d b )) re pr ese nts tw o o pen points  conn ect e d  to  eac h ob sta cl e,  if  only  one  po i nt i s d et ect ed   then  α a = α b   a nd   d a = d b   SG =  { (a i ,b i ) , … ..,(x j ,y j ) }  as a  s et  o f  sub g oal  po i nts r ec ogniz ed   by   the  r obot   an d  e ver y  (a i ,b i )  sig nifies t he  su b g oal  point  wh ic h  the  ro bot can selec t  for next m ov e   T obs = {(( a i ,b i ) , …(a j , b j ) ), … ..,( (x i ,y i ) ,..,( x j ,y j ) ) } as a set  of  ini ti al l y  identifie d   obstr uction w her e  each   ((a i ,b i ) ,… (a j ,b j ) )  are  th e  set  of  po i nts  of  eac h  ob sta cl e.   S obs = {(( a i ,b i ),…(a j ,b j ) ), … ..,( (x i ,y i ) ,..,( x j ,y j ) ) } as a set  of f i xe d obst acl es where  ev e ry ((a i ,b i ),…(a j ,b j ))   a r e  the set  of   point s   of eac h fixe d ob sta cl e.   TD obs = {( (a i ,b i ) ,…( a j ,b j )) , …..,( (x i ,y i ) ,..,( x j ,y j ) ) } as a set  of  ini ti al ly   m ov in g   obsta cl es whe re  ever y  ((a i ,b i ) ,… (a j ,b j ) )  are  the   set  of  po i nts  of  eac h pro vision al ly  m ov ing   obsta cl e.   D obs = {( (a i ,b i ),…(a j ,b j )) ,… ..,( (x i ,y i ) ,..,( x j ,y j ))}   as a set  of m ov a ble   obsta cl es where  each   (( a i ,b i ) ,… (a j ,b j ) )  are the  s et  of  points  of each  m ov a ble   obsta cl e.   D= {(( x a ,y a ),δ a ) ,… , ( ( x j ,y j ) ,δ j ) } as a set  of s ub  go al   points a nd d ist a nce fr om   ta rg et  of t hat point   wh e re ea ch  set  ( (x a ,y a ) ,δ a )   r epr ese nts t he  s et  o f  sub g oal  po i nt and t heir dist ance  from  t arg et   Her e  d m in   is t he  d ist ance  fro m  the ro bo t t o goal  p oi nt and     i s the  directi on  of the sam e.   P C   is t he p os it ion  w he re th e   r obot  m ay  co ll i de wit h  the  obs ta cl e  and  the  di sta nce  f r om  cu r re nt positi on  of  rob ot to  t he po i nt of c olli sion i s  D C .   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     IS S N:  22 52 - 8938       Develo pm e nt  of  p at h pla nn i ng a lg or it hm  of c entipede  ins pir ed  w heele d  r ob ot ...   ( Subir K umar  Das )   99   2.1.3.    Al go ri t hm   a.   Ma in pro ce dur e   1.   Robot Start   2.   Take i nput  of the  posit ion  c o - ordinates  of s ource  and  destin at ion   3.   Ca lc ulate  the dist ance and  dir ect ion   from  so ur ce  to desti nat ion   d m in   and    resp ect ively   4.   W H ILE  not  D est inati on   5.     Start OBS TAC LE_ DETECT I ON proc ed ur e   in F OV   6.   IF   obsta cl e or  virtu al   obsta cl e in  directi on   7.   Ca lc ulate   the  c oor din at es  of   s ub  goal s  from   OP ,   do n’ t  cal c ulate   sam e  set  from   OP   twic e  an d  save it i n set  S G  a nd D   8.   Ca lc ulate  d ist ance  of each  sub g oal  from  d est inati on  a nd s ave it i n set  D   9.   Sele ct  the c oor din at e  po i nt P   hav i ng the l owest  d ist ance i n D   10.   IF  t he po i nt ex i sts i n  T rav e rse po i nt set T 1   11.   Discar d  the  poi nt   12.   Sele ct  the  nex t  lowest  distance  point P  fro m  D   13.   Fo ll ow ste p 10   14.   ELSE    15.   IF  P  is S AF E _POI NT   16.   Sa ve  t he  c oor di nate in tra ve rs e point set   T 1   17.   Ca lc ulate  an gl e of rotat ion a nd  ro ta te   18.   Ca ll  MOV E  Proced ure to  m ov e at P   19.   IF   obsta cl e d y nam ic   20.   IF   VI RT U AL OBST ACLE   21.   Fo ll ow ste p 7   22.   END I F   23.   END I F   24.   Ca lc ulate  d irec ti on     and   distance  d m in   25.   ENDIF   26.   ENDIF   27.   ELSE    28.   Ca lc ulate  the ne xt point c oor di nate P towa rds the  directi on    29.   IF  P  is S AF E _POI NT   30.     Save  t he  c oor di nate in T 1   31.     Ca ll  MOV E  Proced ure to  m ov e at P   32.     Ca lc ulate  n ew   d m in   33.   END I F   34.   END I F   35.   END  WHILE   36.   Robot St op     b.   Mov e  pro ce dur e   1.   FO R i = n  to  2   2.     Save  t he  la st c oor din at e  of   T i - 1   in tra ver se   po int set  T i   3.   END F OR   4.   FO R i = 1  to  n   5.     Mov e  the ith  li nk to ward t he  l ast  point  of   T i   6.   END F OR   c.   Ob sta cl e _d et ec ti on   proce dure   1.   Scan 0 0   t o 180 0   2.   Id e ntify o bs ta c le s in  F O V   3.   Ca lc ulate  the c oor din at es  of open  points  and  save t ho se  poi nts in  set T obs   4.   IF   no ope n p oin ts   5.     Ro ta te  the  hea d  le ft  90 0   6.     Scan 0 0   t o 180 0   7.     Ca lc ulate  the c oor din at es  of open  points  and  save t ho se  poi nts in  set T obs   8.     Rotat e the  hea d rig ht 90 0   9.     Scan 0 0   t o 180 0   10.     Ca lc ulate  the c oor din at es  of open  points  and  save t ho se  poi nts in  set T obs   11.   END I F   12.   FO R a ny c oor d inate  in  T obs   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2252 - 8938   IJ - AI  V ol.  8 ,  No.  2, June   201 9 :   95   –   106   100   13.     IF  c oor din at e s et  o f  T obs  exists  in  S obs    14.       Discar d  the  coor din at e  from  T obs   15.     ELSE   16.       IF  t her e e xists  any n ea rest  po i nt in S obs   with     sm a ll  ch ang e  in x  or y val ue   17.     The o bs ta cl e m ay  b e  dynam ic   18.     Save  c oor din at e in T D obs   19.     ELSE     20.     IF  t her e e xists  any n ea rest  po i nt in TD obs     with sm al l chan ge  in x  or y  va lue   21.     It is p a rt  of  m ov in g obst acl e   22.     Save  t he po i nts  of T D obs  and T obs  to the ro bo t  reg ist ry a nd all  the  op e n p oin t s of    the  ob sta cl e    in D obs   23.     ELSE   24.     Save  t he po i nts  in  S obs   25.     RETURN  obst acl e   26.     END I F   27.     END I F   28.     END I F     29.   END F OR   30.   IF   obsta cl e d y nam ic   31.     IF   VI RT U AL OBSTCLE     32.     RETURN  v i rtu al  o bst acl e   33.     END I F   34.   END I F     d.   Virtual ob sta cl e  pro ce dure   1.   Ca lc ulate  d irec ti on     a nd s pee d v obs   of the  ob sta cl e from  the points e xists i n rob ot r e gistr y    2.   IF  t he ob sta cl e  directi on    i ntersecti ng ro bo t  directi on    3.     Ca lc ulate  p r ob able posit io n  P C   of colli sio n   4.     Ca lc ulate  p r ob able d ist a nce  D C   f ro m  the ro bo t t o  P C   5.     IF   D C <d m in   6.     Ca lc ulate   the  tim e  R T C1   and  R TC2   the  rob ot  will   ta ke  t o  ar rive  at   P C   an d  cr os s  P C   fu ll y   resp ect ively   7.     Ca lc ulate  the   ti m e O TC   m ov ing   ob sta cl e  will  r eq uires  to  a rr i ve  at  P C   8.     IF  R TC2 >=O TC   and R TC1 <=O TC   9.     Id e ntify t he p oi nt P C   an d al l t he    adj ace nt  points  of the  obstacl e  as    virtu al   O bs ta cl e   10.       Ca lc ulate  the open points  and  save i n OP   11.       RETURN  v i rtu al  o bst acl e   12.     ENDIF   13.     END I F   14.   END I F     e.   Safe _poin t  pro cedure   1.   IF  P  corr esp on ds  t o  a s ub s ub  set  o f  OP   2.     Sele ct  the s ub  set  f r om  O P th at  co r res ponds  to P   3.     IF  it  is  first s ub set   4.     Sele ct  the sec ond su b set  from  p rev io us  set  from     OP   5.     ELSE   6.     Sele ct  the f i rst  su b set   from  n ext set f r om  O P   7.     END   IF   8.     Ca lc ulate  the dist ance S d between  tw o  s ub s et s   9.   ELSE   10.     Sele ct  the tw o po i nts fr om  O P h a ving m inim u m  d ist ance f r om  P   11.     Ca lc ulate  the dist ance S d between  tw o po i nt s   12.   END I F   13.   IF  S d  <  2r   14.       RETURN  saf e   15.   ELSE    16.     RETURN  not  safe   17.   ENDIF   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     IS S N:  22 52 - 8938       Develo pm e nt  of  p at h pla nn i ng a lg or it hm  of c entipede  ins pir ed  w heele d  r ob ot ...   ( Subir K umar  Das )   101   3.   DISCU SSI ON   A ND R ES UL T    The  pri nci ple  m ot ive  of   the  a lgorit hm   is  to  c reate  a  con ti nu ou s p at h  f r om   fixe d  source  to   destinat ion.   Avoidi ng  sta ti c  obsta cl e  can  be  is  discuss e d  in  [ 20 - 21 ] ,   the   Fig ure   1  s how s  the  a vo i dan c e  as  pe r  [20].  Curren t   al gorithm   a tt e m pts  to  avo i d  m ov ing   obsta c le   too .  Als o  thi s  al go rit hm   in  con t rast  of  [ 21 ] ,  j udges  t he  r obot  as  a  series  of   ra kes  hav i ng   dim ension s  not  only   a  po int  an d  ave r ts  colli sion   with  the  obsta cl es  us ing   pr e ve ntati ve  m easur e.  Fi g ure   5  s hows  eac h  pa rt  of  the  r obot  co ns i der i ng   i n  a  vi rtual   ci rcle  avo i d  obsta cl e  an d  th e  op e n  po i nts  an d  it s  relat ed  sub  goal   po i nts   is  sh ow n  in  Fig ure   6  Ca lc ulati ng   s ob   go al   po i nt  us in g  re qu i re d  m et ho dolo gy  is  ref le ct ed  i n  F ig ure   7  All  the   sub  goal s  sit ua te   perpendicu la rly   rev ers e  di recti on   of  the  r el at ed   op e n  points.  T o  a v oi d  the  ob sta cl e  the  r obot   has  to   tur n  t he  ra kes .  T he  tur ning  an gle  and  dis placem ent  of  rob ot’s p os it ion   du e  to  t urn  is  shown i n  Fi g ure   8.             Figure  5.  Whole r obot insi de  t he virtual ci rcle wit h  safety  m easur em ent      Figure  6.  O bs t acl es’  ope n po i nt an d su b g oal point  detect ed by r obot       3.1.   Al go ri thm   study  and  analysis   Let  an   open  po int i s ide ntifie d by se nsor at  a ng le  α.  As  per   [20]   β i = (α +β i - 1 ) %3 60     x i+1,j  = x + d k cos θ(x s )   (1)     y i+1,j  = y+ d k sinθ( y s )   (2)     Her e   ( x, y)   is  th e  locat io n  of  se ns or  a nd  ( x i+1,j ,y i+1,j )  is  the  loc at ion   of  j t h  i de ntifie d,  one  of  su bse que nt   op e n  points  at  ( i+ 1) t h  it erati on  a nd  in  acc ordan ce   to wor ld s  co ordinate  sy stem .  The  op e n  po i nt  ap pea rs   in  t w o  ways.  1.   I f  ea r li er  value  of   α ,   the  sen sor  an gle  α   - 1  sense s   an  obst ru ct io n  an d  2.  S ub se quent  value  of  α ,  the  sens or   an gle  α +1  senses  obstructio n.   Eac h  of  these  two  al s o  ha ve  two  s ub  cases  and   th ose   are:  a)    >  9 0 0   an d  b)    <=  90 0     wh e re  = % 180 °                       So   we  ca n desc ribe    as  foll ows,     = { − 90° , Sx =   1 , Sy =   1           if   > 90°         − 1   not   o bst a c le − 90° , Sx = − 1 , Sy = − 1         if     > 90°       − 1   is   obstacl e       90° − , Sx = 1 , Sy = − 1             if   ≤ 90°     − 1   not   obsta cle 90° − , Sx = − 1 , Sy = 1               if     ≤ 90°   − 1   is   obsta cle                                   (3)     If   ( x i+1,j ,y i+1,j )  is o pe n po i nt P t hen  a s  per   Fig ure   7, c oord i na te  v al ue o f  c onnected  sub  goa l po i nt Q is:      =  +  .     =  +  .  }                   (4)     (Qx,Qy )  will   be  the  ne xt  centre  after  m ov e  of  the  virt ual  ci rcle  that  con ta ins  the  head   par t  of   centi pede  ins pired   rob ot.  I n  a ccorda nce  t o  F ig ure   4,  A   is  th e  wh e el   axel  c entre  a nd   AC  i s  the  dista nce  a m on g  the  virtu al   ci rc le   centre  and   wh eel   axel  ce nt re.  So,  the  val ue  of  ne xt  po si ti on   of  w heel  axel  centre  A  can  be  determ ined  as,   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2252 - 8938   IJ - AI  V ol.  8 ,  No.  2, June   201 9 :   95   –   106   10 2    =  +  .    =  +  .     }     (5)     Now  the  hea d  par t  of   rob ot  w il l  co m pu te   the   require d  an gle   of   ro ta te   to  m ov e  w heel  axel   centre  a nd   then  sta rt  pro gr essi ng  to  ne xt  po sit io n.   T he  rem ai nin g  par t  of  the  robo t  will   fo ll ow  it   pr edecess or   li nk s   coor din at e  loc at ion   for  ne xt  m ov e  as  wr it ten   in  a lgorit hm .   Du ri ng   it s  tur ning  to  av oid   obsta cl es  the  robo t  get s   disp la ce d  from   it s  d m in   li ne,   wh ic h  it   has  to  cov e r  in  nea r  fu t ur e.  Ma xim um   it   turn s  th e   m axi m u m   it   t akes  to   cov e r. Acc ordi ng Fig ure   8,  if   Y  is t he displa ce m ent v al ue  then,     Y = ( F + R ) sin         ( 6)     = sin − 1 ( + ) ⁄                                                       (7)     Her e  ( F+R )  is t he  le ngth  of ea ch rake  and    is t he  m axi m um  p er m issi ble r otati on a ng le   of a r a ke .   Irresp ect ive  of   m ob il it y  or   non - m ob il it y  ever y  obsta cl e  is  sta ti on ary  at   an  exact  point  of  tim e.  I f  the  po sit io n  cha ng es  of   a n  obsta cl e  then  it   is  m ov ing   ot herwise  it   is  sta t i c.  For  m ov ing  ob sta cl e  the  po s sible   po sit io n  in  f utu re  can  be  det erm ined  fr om   i ts  sp eed  an d  di recti on.  Fig ure   9  il lustrate s  ho w  to  a vo i d  dynam ic  ob sta cl e  usi ng   MC SB  al go ri thm   by  p red ic ti ng   the  virtu al   ob sta cl e  locat ion .   T he  sta te d  schem e  al lows   the  rob ot  to  av oid  secur el y  sta ti c  ob sta cl es   sho w n  in   Fi gure  10 .   For  m ob il e  obsta cl es  is  has   fi nd  out  t he  s pee d  of  that o bs ta cl e by  sen sin g  it s  posit ion at  tw o  s epar at e ti m e t n+ 1   an d  t n   w he re  t= t n+1 - t n . Th er e fore,             Figure  7.  O pe n p oin t t o S ub goal p oin t c al cu la ti on     Figure  8.  Tu r nin g an gle a nd d i sp la cem ent d ur ing  t urn             Figure  9.  A voidin g  a m ov in g ob sta cl e  by cal culat ing   virtu al   obsta cl e twice     Figure  10.  A voiding o bs ta cl e i n  L ocal Mi nim a       Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     IS S N:  22 52 - 8938       Develo pm e nt  of  p at h pla nn i ng a lg or it hm  of c entipede  ins pir ed  w heele d  r ob ot ...   ( Subir K umar  Das )   103   v obs = ( O t+1 − O t ) t                                                                                                                                 (9)     wh e re  O t+1 ,O t   are  O bs ta cl e  posit ion s   at   tim e  instant  t n+1   and   t n   a nd  v obs   i s  sp ee d  of   t he  m ob il e  ob sta cl e.  By   so lvi ng   e quat ion   of  r obot’s  directi on  an d  ob sta cl e’ s  dir e ct ion   the  pr ob able  posit ion   of  colli sion  (P C )   can  be   cal culat ed.   Th e  nex t  ta sk   is  to  fin d  out  w he ther  ther e  will   be  a  real  colli sion   or  not  at   P C .  If   there  will   be  a  colli sion   the n  t he  posit io n  an d  it s  su r r ounding   will   be  ide nt ifie d  as  virt ua l  ci rcle.  If   P R (rx n+1 ,ry n+ 1 )   be  c urren t  locat ion   of the   rob ot at t n+1 . T hen,     D C = √ ( Cx − rx n+1 ) 2 + ( Cy − ry n+1 ) 2           (10)     w he re  (Cx,C y)  is the c oor din a te  p osi ti on   of P C . By t he value  of D C   r obot th en dete rm ines,     R TC1 = D C v ⁄                                                                                                                                                         (11)     R TC2 = ( n ∗ 2r + D C ) v ⁄                                                                                                               (12)     O TC = D C v obs ⁄                                                                                                                                                 (13)     The  velocit y  of  r obot  is  v.   R T C1  and   R TC2   are   tim e  of   enteri ng  at   P C   an d  e xiti ng   from   P C   resp ect ively   and  O TC   is  th e   t i m e  the  ob st acl e  will   ta ke  to  ar rive  at   c ol li sion   poi nt.  N   is  num ber   of  li nk s  or  ra kes  of   t he  rob ot  and   r  is  the  rad i us   of  vi rtual  ci rcle.  O TC   li es   tim e  ran ge  R TC1  and   R TC2   m eans  they   will   be  at  P C   i n  the  sam e   tim e  per iod   i n  nea r  f uture.  S o  the  po i nt   will   be  ind ic a te d  as  virt ual  obsta cl e  an d  dis torted  tra j ect ory   will  be  s hap e d  with   safety   m easure .  H ow   t he  r ob ot  will   avo i d  l ocal  m ini m a  pr oble m   is  il lust rated  in  Fig ure   9.   If   the  rob ot  fail s  to  fin d  an  op e n  point  in  dire ct ion   F OV   the  head   will   ro ta te   righ t  a nd   le ft   as  m uch   as  po ssible,   scan  the   area  t ake  op e n  po i nts.  I f  it   sti ll   fails  then  it   has  to   ro ta te   the  w hole   robo t.   The   F ig ure   11  s how s  ho w   to  av oid   a n  obsta cl e  with  saf et y  m easur em e nt.  He re  in   this   fig ur e  it   is  de s cribe d  f or   a  sin gle  li nk.  But  f or  any   lin ks  it  is a pp li cable as al l t he  li nk s  foll ow th e sam e p at h  to  reach  d est in at ion.           Figure  11.  O bst acl e avo i dan c e w it h safet y m easur em ent       3.2.   To ta l  tim e a n d pat h len gt h  c alculat i on   If   v i   an d  i   are  the  s peed  and   a ngular  velocit y  at   it h  it erati on   the n,   ti m e  ta ken  in  m ov ing    and r otati ng [2 0]:     = ∑ ⁄ = 0     = ∑ ⁄ = 0       So  t he  c os t f un ct ion  in  term s o f  tim e fo r  one  li nk s  is:   = ∑ ( ⁄ + ⁄ ) = 0 + ∑  = 0     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2252 - 8938   IJ - AI  V ol.  8 ,  No.  2, June   201 9 :   95   –   106   104   w he re  DOT is  the tim e taken t o  ide ntify m ob il e obstac le  a n d i ts directi on of  progress  and s pee d .   So  t he  total  c ost  in  te rm s o f  ti m e fo r  all  the l ink s  or the  wh ole ro bo t i s:      = ∑ 1     3. 3 .   Simul at io n  resul ts   How  a  rob ot  is  us in g  M od i fiedCrit ic al - Sn a kebu g  al gorith m   to  sta y  away  fr om   sta ti onary  an d  non - sta ti on ary  obst acl e  sh own  i n  the  Fig ure   12.  Ther e  a re  twel ve  sepa rate  sn a p  shots  of  twel ve  sepa rate  m ome nts  in  sa m e  env ir on m ent.  The  gr ay   colo ured ,   rectangula r  s hap e d  ob j ect   is  non - sta ti onar y  ob sta cl e  and  sta tic   ob sta cl es  are  of  gr e en  re ct an gula r.   T he  al go r it h m   is  m od el l ed  us i ng   Pyt ho n  3.5  on   windows  7  platfo rm .   In te l   cor e  i 3 - 2350@ 2.30   G hz  Lapt op   with  2  GB  RAM  is  us e d.   The  re d  ci rcle  at   the  top   a nd   foot  are  the  go al   and  init ia l po ints  re sp ect ively . T he  p at h r obot tr av el le d  is sh own   us in g  Bl ack  li ne .           Fi gure  12.  Sn a ps hots  of tra j ec tory  gen e rated   us in g  m od ifie dc riti cal - sn ake bug al gorithm  on 2D  p la ne       4.   CONCL US I O NS   A ND FUT UR E  WO RK   The  earli er  w orks  is  f ur th er  c on ti nue d  in  this  pap e r.   T he  f or em os t  intenti on   is  to  buil d  a  local   path  plan ning  al gor it h m   on  sim pl e  sens or  base d  f or  bi o - in sp ir ed  ce ntipe de  li ke  m ulti   rak e  rob ot.  T he  al gorithm   m akes  an   ef fort  to  t hink  a bout  the  restrict ion s   of  rob ot’s  dim ension .   T o  c om plete   the  ta sk   us in g  t his  bu g  al gorithm   the   rob ot  re qu ire s  ver y  li tt le   pr ior  i nfor m at i on.  Me asu rin g  t he  safety   pr ecauti on  m akes  th e   al gorithm   m or e  eff ect ive .  T hi s  al go rit hm   helps  to  a vo i d  a   ver y  sm al l  th e  gap   or  to  pa ss  thr ough  sm al l  gap   wh ic h  is bi g  e noug h  t o  pass.  I n  case   le ss  c om plex  env ir on m ent  or  e nv ir onm ent  with f e w  nu m ber s   of o bs ta cl e,   Evaluation Warning : The document was created with Spire.PDF for Python.