TELKOM NIKA , Vol.14, No .2, June 20 16 , pp. 655~6 6 4   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v14i1.2989    655      Re cei v ed  No vem ber 8, 20 15; Re vised  Febr uary 8, 2 016; Accepte d  February 2 7 , 2016   Quadrotor Path Planning Based On Modified Fuzzy Cell  Decomposition Algorithm      Is w a nto* 1,2 , O y as Wah y u nggoro 1 , Adha Imam Cah y adi 1   1 Departem ent of Electrical En gin eeri ng a nd Info rmatio n  T e chno log y , U n ive r sitas Gadja h  Mada,  Yog y ak arta, Indon esia   2 Departme n t of Electrical En gi neer ing,  Un iver sitas Muhamm adi ya h Yo g y ak arta,   Yog y ak arta, Indon esia   *Corres p o ndi n g  author, e-ma i l : is w a nto.s3te 13@ma il.u g m.ac.id       A b st r a ct   T he pur pos e o f  this pa per is t o  pres ent a n  a l gor ith m  to  dete r mi ne th e sh ortest path for  qu adroto r   to be abl e to navig ate in an u n know n are a . T he prob le m  in  robot navi gati on is that  a rob o t has inca pab i lity   of findin g  the s hortest path w h ile  movin g  to the go al  p o siti o n  and  avoi di ng  obstacl es. Hen c e, a mo dific a ti on   of severa l a l go rithms  is pr opo sed to  ena bl e the ro bot  to r e a c h the  goa l p o s ition thr o u gh t he sh ortest pat h.   T he alg o rith ms  used ar e fu zzy logic  and c e ll  deco m p o siti on  algor ith m s, in  w h ich the fu zzy algor ith m  w h i c h  is an  artificia l  i n telli ge nce  alg o rith m is  used  for  robot p a th  pla nni ng  an d  cell  deco m posi t ion a l gor ith m  i s   used t o  cre a te  a  map  for the  robot  path,  b u t the  mer ger  of these tw o a l g o ri thms  is still  inc apa ble  of fin d i n g   the shortest pa th. T herefore, this  pa per d e sc ribes a  mo dific a tion of the b o th alg o rith ms b y  addi ng p o ten t ial   field  alg o rith m  that is us ed to  provi de w e i g h t  values  on t h e  ma p i n  or der f o r the  qua drot or to  move  to i t s  goa l pos itio n a nd fin d  the s h ortest path. T h e mod i fica tio n   of the al gorit h m s h a s  sh ow n that qua drotor  is  abl e to av oi d  vario u s o b stac les a nd fi nd t h e shortest  pat h so th at the t i me re quir ed t o  get to  the  g oal  positi on is shor ter.       Ke y w ords : Ce ll Deco mpos itio n, Quadrotor, F u zz y ,  Sh ortest Path, Modifie d   Potentia l F i eld        Copy right  ©  2016 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Quad roto r is  an auton omo u s robot that  moves  by u s i ng four  rotors [1] without requiri ng  an ope rato r but a naviga t ion system t hat is ca pabl e to dire ct it to the goal position in  an   unkno wn are a . Quadrotor is one type of UAV us ed  by SAR tea m  and the military to perform   missi on s su ch as surveilla nce, search  and re scue  v i ctims of disa sters in  the a r ea s. Given the  missi on,  qua droto r  m u st f l y low in  whi c h it  ha s  a  chall enge  to  avoid  seve ral  ob stacl e s.  T o   overcome th e pro b lem,  several re se arche r s h a ve co ndu cted  resea r ch  o n  path pla n n ing   algorith m  that enable s  UAV s  to be able t o  av oid ob sta c le s and mov e  to the goal positio n.  Grap h-se arch  theory has b een u s ed by Filippis  et al., [2] for UAV  path plan ning  in a 3 D   environ ment.  This theo ry is used to   cre a te a  3D  ma p i n  an  un kn own environm en t by dividing  th e   environ ment i n to small  grid s. Th e 3 D  ma p with  g r id s i s  a  co ntour m ap  with  colo rs that  re present   different heig h ts above th e grou nd. Th e algorit hm  use d  for path plannin g  are A* and theta*   applie d to UAV in a 3D environme n t. In  variou s  tests, the theta* algorith m  has sm oo the r   movement th an the A*  alg o rithm. Th e d r awba ck of  t he theta*  alg o rithm i s  that  it is n o t able  to   detect dynam ic ob stacl e s.   In addition  to  the re se arch er me ntione d  previo usly, the theo ry of  gr ap h-se arch  has al so   been  devel o ped  by G a rci a  et  al [3] fo r  UAV path   planni ng i n  d ange rou s  en vironme n ts.  The   environ ment i s  divided into  small g r id s o n  a 2D m ap i n  whi c h  seve ral line s  a r e d r awn to co nn ect  them. Besi de s u s in g 2 D  e n vironm ent  maps, th e  re sea r che r  al so  used a  3 D  e n vironm ent  map   becau se the UAV works in  that environ ment. The al g o rithm used i n  this study is lazy theta wh ich   is then co mp ared  with A* and A*PS (Post-Sm oothin g ) algo rithm s . The simulati on re sult sh o w s  that lazy  the t a algo rithm  requi re s fa st er time  tha n  the  other t w o  algo rithm s . However,  this  algorith m  ha s merely bee n applie d in sta t ic but not dynamic e n viro nments.   Grap h theo ry  of B-Spline  curve meth od  use d  by Elba nha wi et al., [4] is a mo dification  of  B’ezie r cu rve s  used for Car-Like Rob o ts path plan ni ng. By using Curve s  B'e z i e r algo rithm, the  robot i s  able  to move to the goal po sitio n  and avoid  obsta cle s . Th e algo rithm is modified into  a  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  655 – 66 4   656 B-Spline curv e due to the robot motion that is not sm ooth. The we akn e ss of this algorithm is t hat  the robot  can not avoid mo ving obsta cle s .  Heu r isti c alg o rithm h a s b een u s ed  by Yao et al., [5] for robot  path plan nin g  in a n   unkno wn e n vironm ent. Th e alg o rithm  u s ed  is t he co mbination   of neural  n e two r k and   ge neti c   algorith m s  ap plied fo r robot  in a pl ann ar  environ ment  usin g glo bal  path pla nnin g  method.  Neu r al   netwo rk alg o rithm is u s ed  to mo del  a  sta t ic envi r onm e n t obtain ed  b y  usin g a  glo bal vie w , so t hat  the starting, g oal, and ob stacle po sition s of t he robot  can be vie w e d , while the genetic alg o rit h m   is used for  ro bot path plan ning. With th ese al gorit h m s, the rob o t is able to move  to goal po sition  and avoid  o b sta c le s, but  the wea k n e ss  of this al gorithm i s  th at it is appli ed only for  static   environ ment  and be ca use of this the rob o t cann ot avoid dynamic o b sta c le s.   There  a r e h euri s tic algo ri thms whi c h have  p r op erti es re sem b lin g  creatu r e s  su ch as  bacte ria  and  bee s. Foragi n ba cteri a  al gorithm  used   by Lian g et  al., [6] is one  of the he uri s ti c  algorith m s h a v ing ch ara c te ristics li ke b a c teria i n  which this alg o rith m can  create  a co ntour m a p   of the enviro n ment that is u s ed to a v oid obs ta cle s  and m o ve  to goal po sition in a st atic  environ ment.  Hon e y Bee  M a ting O p timization al go rithm u s ed  by  Rashmi  et  al., [7] for multi-ro bot   path plan ning  has  a ch ara c teri stic li ke i n se ct co lony in  whi c h  thi s  algorith m   ca n   make map s  of  the safest  pa th and  avoid  ob stacl e s to  move to   go al po sition. T he tra c k p a th s  cre a ted  usi n g   colo ny bees.  By using this algo rithm multi-ro bot can identified  a short pat h in a dynamic  environ ment.   Geneti c  algo rithms have b een studi ed  by Y ang et al., [8] used for robot path pl annin g   algorith m  co mbined  with visibility grap h. Visibilit y graph alg o rithm  is use d  to create a map o f  a n   environ ment  model  by u s i ng gl obal  vie w ,  so th at th e ob sta c le s  positio n  can   be d e termi n e d ,  while  gen etic algorith m  is  use d  to ma ke rob o t path  planni ng. By usin g both  of the algo rith ms,   robot can avo i d obsta cle s  a nd move to the goal po sitio n .  Geneti c  alg o rithms ha s b e en u s ed by P ehlivanogl u [9] for path pl annin g  by co mbinin g   Voron o i dia g ram meth od.  This  algo rith m is  applie d t o  a  UAV for  path pla nnin g  in an  urban -l ike  environ ment.  In the neigh borh ood the r e are ob sta c l e s in the form of skyscra per mo del s o r  tall  building s . Vo ronoi  diag ram   method  is u s ed to   create   a ma p of  an   unkno wn  envi r onm ent. A  UAV  is set at a certain height, so that with this  algorithm  the UAV will  avoid skyscraper s and pass  over the build ings.   The  other h euri s tic algo rithm such a s  Ba cteri a l  Potential Fiel d is a  me rg er  of two   algorith m s th at is potenti a l field and  bacte rial  p o tential field  algorithm s  con d u c ted b y   a   resea r cher  n a med Mo ntiel  et al., [10]. Bacteri a l  alg o ri thm is u s ed t o  create a n  e n vironm ent m a p   and a path pl annin g . The wea k n e ss of the algorithm  is  that it stops at certai n o b sta c le s, so that   it is modified  with the pot ential field al gorithm . With  the modifica tion of the two algo rithms,  a   robot is a b le to find the sho r test path a n d  avoid obsta cl es in a stati c  environ ment.   Heu r isti c algo rithm wa s de veloped by G hosh et al., [1 1] who appli e d Fuzzy algo rithm for  Micro air vehi cle path pla n n ing. The alg o rithm us ed  wa s the devel opment of fuzzy algorithm  with   quadtree fra m ewo r k. Qua d tree fu zzy al gorithm fram ewo r k i s  the  combi nation  of fuzzy alg o rithm   and graph th eory. Gra ph theory is u s e d  to creat e 2 - dime nsi onal  environ ment,  while the fuzzy   algorith m  is u s ed for p a th planni ng. The  quadtre e al g o rithm is u s e d  for path pla nning in a sta t ic  environ ment  for fixed  win g  ai rcraft mo dels.  Ho wev e r, thi s  al go rithm ha s  not  bee n  able  to   determi ne the  shorte st path .   The  other researcher  combined virtual fo rce fuzzy algorithm  wi th graph t heory  as  con d u c ted by Zhuonin g  et al., [12]. Graph theory is  u s ed to cre a te a 2-dime nsi o nal enviro n m ent  map by dividing the map i n to small g r id s and the n  the fuzzy alg o ri thm used to  get to the goal  positio n and  avoid ob stacl e s is i dentifi ed. In or de r  to rea c h the  goal po sitio n  quickly, fuzzy   algorith m  i s   combi ned  wit h  virtual  force alg o rith m.  The  pro b lem  of the  algo ri thms i s  th at  the  force o b taine d  from virtual  force alg o rit h m is co nsi d erably g r eat that results in  frequent fail s in  avoiding ob st acle s.   Fuzzy algo rit h m ha s be en  use d  by Wa ng et  al., [13] for path pl a nning in  an u n kn own  environ ment.  The algo rith m is com b in ed with exa c t cell de comp osition g r ap h  method use d  to   cre a te a ma p  by dividing the tra c ks into  equal  si ze t o  avoid ob sta c le s and  rea c h the goal a n d   the fuzzy alg o rithm i s  u s e d  for path  pla nning. To  rea c h  the goal  p o sition,  the algorithm doe s not   s e ac rh for the s hortes t  path.  Several al go rithms p r eviou s ly mentio ne d hav e  not b een a b le to i dentify the shorte st   path and ca nnot be appl ied in a dynamic environ ment. Hen c e ,  this paper  pre s ent s fuzzy  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Quad roto r Path Planning B a se d On Mod i fied Fu zzy  Cell De com position Algorith m  (Iswanto )   657 algorith m s  combine d   with cell  de comp osition  meth od an d mo di fied by ad din g  potential  field   algorith m  in o r de r to rea c h  the goal po sit i on more rapi dly and avoid  dynamic ob stacle s.       2. Non Linea r  Quadro tor  Modeling   Quad roto r is an unma nne d aircraft with  rotary wing t y pe using 4 rotors at ea ch  end of   the frame tha t  moves with  thrust as sh own in Fi gu re 1 which is a model of Mahony et al [14]  pre s ente d  in t h is p ape r. In the figure it is  see n  that the  quad roto r mo ves by u s ing  the four  rotors  whi c h rotate i n  opp osite  direction i.e. two roto rs  rotat e  in a  clo c kwi s e di re ction  a nd the two ot her  rotors rotates counte r cl ockwise.          Figure 1. Qua d roto r modelli ng       Quad roto r system  i s  a  n o n - linea r syste m   that  can  b e  controll ed  b y  six out  of th e twelve   states that re gulate the attitude  of quad rotor  system  that is. The  first six state s  involves Euler  angle s  con s isting of roll, pitch, yaw a ngle s  den oted a s   T 2  and an gula r   spe ed o n   three o r thog o nal axes of t he body of quadrotor d e n o ted as T r q p 4 . Whil e six other  states  are  th ree axis posi t ions denote d   a s   T m l k 1  and th ree li nea r vel o city of th e   cente r   of m a ss of  the  qua drot or  asso ciated   with fixed  referen c e  fra m e d enoted  as  T m l k 3 . So that the  equatio ns of  non-li nea r mo del of the qua droto r  are a s   follows:    k x   l y   m z   (1)     r t c q t s p   r s q c   r c c q c s  (2)    s s c s c T m k 1    c s s s c T m l 1       c c T m g m 1  (3)   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  655 – 66 4   658  qr db p x y z x 2 4 2 1 2 3 2 2    pr y db q y z x 2 2 2 1 2 4 2 3    pq k r z x y z 2 3 2 1 2 4 2 2  (4)       3. Rese arch  Metho d   Path plannin g  is an algo ri thm that is neede d  by a quadrotor in o r de r to reach  its goal  positio n an d  avoid o b sta c l e s. T here a r e two  meth o d s  of path  pl annin g  that i s  gl obal  and   local   path pla nning s. Lo cal pat h  plannin g  is  planni ng t hat  use s   sen s o r s attached to  the body of  the  robot  so  that  the ro bot id e n tifies me rely  the o b st a c le s pl aced i n  front of it, whil e the  glob al  path  planni ng use s  sen s o r s  to see   glo bally. This  pa per  p r ese n ts a re se arch  m e thod  for  the   stu d y of  global p a th pl annin g . The rese arch m e th ods  used in t h is p ape r are  map cre a tion , path planni n g ,  quad roto r ap plicatio n and  potential valu e provisi on to  the map.     3.1. Map Cre a tion   Cell de com p osition i s  on e of the methods in g r a ph theory u s ed to creat e two- dimen s ion a l  maps for  rob o t path pla nni ng. Thi s  meth od divide s th e map i n to a  several g r id s  that  serve s  to m a ke the  rob o t path. The r e a r e two  me tho d s that i s  ap proximate  cel l  decompo siti on   and  exact  cel l  de comp ositi on. App r oxim ate cell de co mpositio n i s   use d  by Val e nte et al., [15 ]  for  a quad rotor p a th plannin g  coverage. An  environme n t is divided into  several e qua l grids by u s i n g   these m e thod s. Then  a pat h is  cre a ted o n  the gri d s l o cated i n  the  map. Path pl annin g  cove rage   algorith m  is  use d  in thi s   study, so tha t  t he qua drot or move s to  the goal  po si tion and  avoi d  obsta cle s  wit hout se eki ng  the sho r test p a th.   Path plannin g  coverage  algorith m  ha s bee n us ed  by Galcera n  & Carrera s  [16] for  different path  planni ng coverag e  to cre a t e a map in  a n  un kno w n e n vironm ent b y  using  exact  cell   decompo sitio n . Several g r ids ma de in  the map  by u s ing thi s  al go rithm have  e qual  size. Pa th   planni ng coverag e  algo rit h m is u s ed fo r the grid divi sion. It is app lied for floor  clea ning robo t in  whi c h the ro b o t achieve s  the goal a nd a v oid obs ta cle s  witho u t see k ing the  sho r test path.           Figure 2. Environm ent mod e l      Approximate  cell de co mpo s ition alg o rith m is pr esente d  in this pa pe r as  sho w n i n  figure   2. It  sho w s that there a r e  initial  potition  of (Xr, Yr), st atic ob sta c le s positio n of  (Xo, Yo), and   the  goal p o sitio n  of (Xg, Yg)  in an u n kno w n e n viron m ent by viewin g glob ally. Using th e po si tion  data, an  envi r onm ent ma p  is o b tained.  The  sou r ce   code  sho w n i n  Figure 3 i s  u s ed to  create  a  map and  split  it into severa l grids.    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Quad roto r Path Planning B a se d On Mod i fied Fu zzy  Cell De com position Algorith m  (Iswanto )   659 Figure 3  sho w s th at   R R Y X , is th e po sition of  the rob o t,  O O Y X ,  is the po sition  of  obsta cle 1, a nd    G G Y X ,  is the po sition of goal.   G R  is the formul a of the dista n ce b e twe en  the  positio n of th e ro bot an d t he go al an d O R  is the fo rmul a  of the di stan ce b e twe en t he po sition  o f   the robot an d  the obsta cle.   Then  G R  and  O R   are summe d to an enviro n m ent matrix value.           Figure 3. Matrix environm e n t of cell decompo sition       3.2. Fuzzy  Path Planning   Basic b ehavi o r of robot p a th plannin g  in dec ompo si tion cell algo rithm is go-to -goal. In  this behavio r,  the robot sea r ch es fo r the smalle st gr id  to move by grid following to  get to the goal  positio n. Cell  decom po sition algo rithm  is a path pla nning al gorit hm in  2  environment while   positio n of q u adroto r  i s  in   2 environ ment.  Hen c e  this  p aper p r opo se d qu adrotor  p a th pla nning   with fuzzy algorithm for  2  environ menta l  position by providin g a consta nt value  at a certain   height. In this study, the quadrotor  i s  controlle d with  refere nce values of gri d  spaci ng obtain e d   from fuzzy algorithm.    This algo rith m which  i s  a n  a r tificial int e lligen ce  alg o rithm  used f o r  rob o t navi gation i n   unkno wn env ironm ent is d i scovere d  by  zad eh  [15]  and u s ed  by Lee [16]. F u zzy input is an   ultrasoni c se nso r  attached  to the front body of  the ro bot with angl e betwe en se nso r s i s  30 ° an d   there a r e 12  sen s o r s. Fu zzy algorith m  use d  ha s a  rule ba se by compa r ing det ection di stan ce of  obje c ts to  det ection  an gle  of obje c t. Th e fuzzy  al gori t hm ha s  su ccessfully pa ssed the  ob sta c le   toward goal p o sition.    The othe r re searche r s su ch as Kala et  al., [ 17] comb ining fuzzy al gorithm  with A* used   for ro bot path  planni ng. A*  algorith m  is  u s ed fo r path  p l annin g  on  co lored  map s   created by u s in g  grap h algo rithm, while fuzzy algorithm i s  used fo r na vigating rob o t. With the merge r  of the two   algorith m s, th e robot  can a v oid obsta cle s  and rea c h its goal p o sitio n .           Figure 4. Fuzzy path plan n i ng de sign   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  655 – 66 4   660       Figure 5. Set of fuzzy input  and output           Figure 6. Fuzzy path plan n i ng rule b a se       The fu zzy i n put of g r id v a lue s  is obt ained f r om  cell de com p o s ition o n  gl o bal path  planni ng  whil e the mem b e r  set fuzzy ou tput is motio n  dire ction  of quad roto r a s   sho w n i n  figu re  4. The  path  p l annin g  p r op o s ed  in thi s   study is for th e  rob o t in  2 R  po sition while q u adroto r  i s  a  robot that i s  in  3 R  positio n. Therefore, th e quad roto r  will wo rk in  2 R   position in which the  altitude is set up.   The fu zzy m e thod u s e d  i n  this  pap e  has eight i n p u ts  con s i s tin g  of three m e mbe r s ie   small, me diu m , and la rge   rangi ng from  0 to 300  a s  shown in Fi gu re 5. T here i s  on e outp u t  of  fuzzy  and  it  has eig h t m e mbe r s de riv ed from th eir pla c e s   nam ely obliq ue f r ont ri ght, fro n t,  oblique front l e ft, left, oblique rear l e ft, rear, obli que  rear  right, right and. The fuzzy path pl anning  rule ba se i s  shown in Figu re 6.     3.3. Potentia l Field   The m e rging   of both  algo rit h ms en able s   quad roto r to  avoid o b sta c l e s  and  go  to t he g oal   positio n, but   the qu ad rotor ha s  unide ntified the  s hort e st p a th. Th e alg o rithm  o f  this  pap er i s   modified  by a dding  potenti a l field al go rithm u s ed  to gi ve a weight v a lue fo r e a ch  grid  cell  form ed   from de comp osition. Poten t ial field algorithm is  an alg o rithm for ro b o t navigation that is used b y   Park  et al., [20] usi ng m agneti c  theo ry that is  attraction  and  repul sion. In  robot  navigat ion,   attractive pot ential is the force gen erat ed by the  goal potition of robot in  which the equatio n is as  follows :    2 2 1 ) ( d a A x x k x U   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Quad roto r Path Planning B a se d On Mod i fied Fu zzy  Cell De com position Algorith m  (Iswanto )   661 2 2 1 ) ( d a A y y k y U , (5)    Whe r e  a k  is th e  potential fiel d consta nt. T he value  of  d d y x ,  sho w s the  go al po sition  of the  robot a nd   y x ,  sh ows the  coo r dinate p o sitio n  of the ro bot . While p o ten t ial repul sio n   is a force  gene rated by  obsta cle s  in robot enviro n m ent issho w n  in the followi ng equ ation:     2 1 1 2 1 ) ( O r R x x k x U   2 1 1 2 1 ) ( O r R y y k y U , (6)    Whe r e  r k  is the  repul sive  co nstant. The v a lue of o o y x ,  sho w s t he o b st a c l e  po sit i on.   I n  t h is   pape r the p o tential field in  attractive an d  repul sive e q uation s  is m o dified to be  u s ed to  provid e  the value of the grid o n  the  cell de comp os ition. The  modificatio n  of the equatio n is:    ; 10 10 2 2 G R G G a A X X Y Y k U  (7)     ; 10 10 2 2 S S R S R r R X X Y Y k U   (8)     ; 10 10 2 2 D D R D R r R X X Y Y k U   (9)     Whi c h  D R U is the  potential field  force for dyn a mic o b sta c l e s,  S R U  is the pot ential field force f o r  static obst a cl es,  an d  A U  is t he pote n tial f i eld atractio n. While   G G Y X ,  is th e goal  po siti on,   S S Y X ,  is the static o b sta c le po siti on, and  D D Y X ,  is the dynamic o b s tacl e po sitio n .    3.4. Modifed  Map Cre a tio n   This pap er u s e s  a  dyna mic e n viron m en t whe r e  the  e n vironm ent h a s  a m o ving  obsta cl e   as  sho w n i n   Figure 6. In the figure G R is the dista n ce b e twen th e ro bot and th e  goal p o sitio n ,   D O R is the dista n ce betwe n the  robot  an d the dynamic  ob stacl e , and  S O R  is a dista n ce  betwe n  the robot  and  the  static  ob stacl e . By u s i ng a  cell d e compo s ition, t he e n viron m e n t is  divided  i n to  grid s with sou r ce  cod e  as i n  Figure 7.   Figure 8  sho w s th at cell  d e com p o s ition  algorit h m  is  modified to u pdate the i n formatio n   data of the e n vironm ent that is use d  to detect mo vin g  obsta cle s  so that the algorithm is pl ace d   in the  main  source  code. I n  this figu re  K is the  value  f o r th e  size of  the  grid,   R R Y X ,  is   th e  positio n of th e robot,   G G Y X ,  is t he  robot  go al po sition,  S S O O Y X ,  is  the po sition   of stati c   obsta cle s , an d  D D O O Y X ,  is the po sition of dynami c  ob st acl e s. Having creat ed  an  envi r on ment   map usi ng ce ll decom po sition, fuzzy pat h planni ng al gorithm i s  performed.       Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  655 – 66 4   662         Figure 7. Dyn a mic envi r on ment model   Figure 8. Modified cell d e compo s ition       The  novelty o f  the alg o rith m in thi s   stud y other  than  u pdated  inform ation i s  to  mo dify cell   decompo sitio n  alg o rithm  to p r ovide  weight valu es  to ea ch  gri d  with  modifie d  pote n tial fi eld  algorith m . From Equation  (7), (8), and  (9) the value for ea ch g r id o b tained i s :    D S R R A U U U F  (10 )     Equation  (1 0) is  used to  provide value s   to  grid s by  m odifying  the   source co de a s  sho w n   in Figure 9.           Figure 9. Matrix environm e n t of modified cell de comp osition       Matrix enviro n ment of mo dified cell d e c omp o sitio n  is sh own in Figure 9   in which  the  total force of  potential field is use d  for weight  value s  of colum n s and ro ws in  it.  If  the sum of  attraction a n d  repul sion i s  consi derably large, a limit value is give n .         Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Quad roto r Path Planning B a se d On Mod i fied Fu zzy  Cell De com position Algorith m  (Iswanto )   663 3. Results a nd Analy s is  The exp e rim ents i n  thi s  pap er i s   condu cted  by  usi ng M a tla b  software t o  mod e l  environ ment  and qu adroto r  and al so  si mulate the  pe rforma nce of quad roto r in reaching the g oal  positio n and  avoiding stati c  ob stacle s in  an unkn o wn environ ment. There are two experime n ts in   this pa per to test the  modified al g o rithm s .  The  first expe ri ment u s e s  static and  dynami c   obsta cle s  a n d  the  se cond   experim ent u s e s  stati c  o b stacle s. The  e x perime n ts  compa r e m odif i ed   Fuzzy Cell  De comp ositio n Artificial P o tentia l Field (FCDAPF) t o  Fuzzy Cell Decompositi o n  (FC D ) al go rithm.  The first expe riment te sts t he FCDAPF  algor ith m  in a n  un kno w n e n vironm ent containe d  static a nd dy namic  ob stacles a s  sho w n  in Figure 8.  The figure sh ows that t he  static o b sta c l e  is  locate d at  the  po sition  of (5 ,7) a nd th e d y namic ob sta c le i s  located  at the  po sitio n  of  (9,1 ) a n d  it  moves to  po sition  (1,7 ). T he e n vironm ent teste d   with FCD  algo rithm is sho w n  in Fig u re 10 (a )  and  FCDAPF  in Fi gu re  10(b). In  Figu re   10(a ) , it  ca n b e  seen  that th e g r ee n q uad rotor will   colli de   with the yello w on e at the  positio n of (5 , 5), wh il e Fi gure  10 (b ) sh ows that the  gree n q uad ro tor  will avoid the  moving ob sta c le of yellow  quad roto r at the po sition of  (4.5, 4.5).       Figure 10. Experim ent with  FCD a nd FCDAPF algo rithms      In this exp e ri ment the  rob o t is pl aced  a t  t he initial p o s ition of  (1 0,1 0 ) m o ving to  the goal   positio n of  (9 0, 100 ) in  the  enviro n me nt having  four   circula r   ob sta c le s lo cate d  at the p o sitio n  of  (3, 3),  (3,6  ), (6, 2.5), a nd  (6, 7) a s   sho w n in Fig u re  1 1 . The figu re  is si mulated   by two meth o d s  namely fu zzy cell  deco m positio n m e thod i ndica ted by the  gre en li ne  and  fuzzy  cell   decompo sitio n  that has be en modified  with the pote n tial field indicated by the blue line. It shows  that by using  modified fuzzy cell de co mpositio n  alg o rithm, the quadrotor rapi dly moves to the  goal po sition  and sta b ly flies be cau s e it moves in ea ch grid.         Figure 11. Experim ent with  FCD a nd FCDAPF algo rithms  0 10 20 30 40 50 60 70 80 90 10 0 0 10 20 30 40 50 60 70 80 90 100 Me t e r Me t e r Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  655 – 66 4   664 4. Conclusio n   The p ape r p r ese n ts  a ne w algo rithm u s i ng the  merge r  of  cell  de co mpositio n a n d  fuzzy  algorith m s. F u zzy algo rith ms i s  typical l y used  for  path pla nnin g  whi c h  serv es to  dete c t a n   obsta cle s  located in front of the robot by using se n s ors. In this study the alg o rithm is u s e d  to   detect  ob stacles that  are re ad fro m  the  cell de com p o s i t ion algo rithm .  By using th e  algo rithm, th e   quad roto r i s   able to  move  to the g oal  po sition  and  av oid o b sta c le s but it  requi re s a  lon g  p r o c ess  to re ach the  goal. S o  th at an  additio nal al gorith m  to resolve t he i s sue i s   need ed.  With  the  merg er of the three al g o rithm s , the quadrotor i s  able to a v oid obsta cl es in a dyn a mic  environ ment  and move s to the goal po si tion more q u i ckly.       Referen ces   [1]    R Abb a s, Q W u . Improved  Lea der F o llo w e r F o rmati on  control l er for  multip le Qu a d rotors b a se d   AFSA.  TELKOMNIKA.  2015; 13(1): 85- 92.   [2]    L Filip pis, G Gugli e ri, F Quag liotti. Path Pl a nni ng Strateg i e s  for UAVS in 3D Envir onme n ts.  J. Intell.   Robot. Syst.  2 011; 65( 1-4): 2 47-2 64.   [3]    M Garcia, A. Viguri a , A Ollero . D y nam ic gra p h -searc h  alg o ri thm for globa l path pl an nin g  i n  prese n ce   of hazard ous  w eather.  J. Intell . Robot. Syst.  T heory App l .  2013; 69( 1-4): 2 85-2 95.   [4]    M Elbanha w i , M Simic, RN Jaza r. Conti n u o u s Path Smoot hin g  for Car-L i k e Rob o ts Usi ng B-Spl i n e   Curves.  J. Intell. Robot. Syst.   201 5; 1(8): 1-3 4 .  [5]    P Yao,  H W ang, Z  Su.  U AV feasi b l e  p a th p l a nni ng   base d   on  dist urbe d fl uid  a n d  traj ector y   prop agati on.  C h in ese J. Aero naut . 20 15; 28( 4): 1163- 11 77.   [6]    X  Li ang,  L  Li,  J W u , H  Ch en. Mo bil e  r o b o t path  p l an ni ng  bas ed  on   ada ptive  bacte rial f o rag i n g   algorithm.  J. Cent. South Un i v .  2013; 20( 12) : 3391-3 4 0 0 .  [7]    RS Rashmi, R  Prat y u sh a, T H  Md, S Sujata, M  Sharmilla, P Rajara jes w a r i, C Sanja y , N Nag w a n i, D   Lop amudr a, C  Ramb abu,  et a l . Navi gati ona l  Path Pl ann in g of  Multi-R obot usin g  H one y B ee  Mati ng   Optimization Algorithm (HBMO).  Int .  J.  Comput. Appl.  20 11 ; 27(11): 1-8.   [8]    X Ya n. An Improved R o b o t Path Planning Algorithm.  TELKOMNIKA.  2012; 10(4): 62 9-6 3 6 .   [9]    YV Peh liva n o g l u. A n e w  v i br ation a l  gen etic  alg o rithm  en h ance d   w i t h  a  Voron o i  dia g ra m for path   pla nni ng of aut onom ous UAV.   Aerosp. Sci. Technol . 20 12; 16(1): 47- 55.   [10]    O Montiel, U  Orozco-Ros as, R Sep ú lve da.  Path  pl an nin g  for mobi le r obot s usin g Bacteri a l Pote nti a l   F i eld for avo i di ng static an d d y n a mic o b stacl e s.  Expert Syst. Appl.  201 5; 42(12): 51 77- 51 91.   [11]    S Ghosh, A Haid er, M Sinha . Micro air veh i cle p a th pl an n i ng i n  fuzz y   qu adtree frame w ork.  J. Inst.  Eng. Aerosp. E ng. J.  2010; 91 : 10-15.   [12]    D Z h u oni ng, Z   Ruli n, C  Z o n g ji , Z  Rui. St ud y  on  UAV P a th P l an nin g  A ppro a c h Bas e d  on  F u zz y Virtu a l   Fo rce .   Chin ese  J. Aeronaut.  2 010; 23( 3): 341 -350.   [13]    Y W ang, T  Wei, X Qu. St u d y   of multi-o b j e ctive fuzz y   o p timizati on for  path pl ann in g .   Chines e J.  Aeron aut.  201 2; 25(1): 51-5 6 .   [14]    R Mahony , V  Kumar, P  Corke. Multirotor  Aeri a l  V ehic l es: Mod e li ng,  Estimation,  an d Co ntrol  of   Quadrotor.  Robot. Autom .  Mag. IEEE.  2012; 19(3): 20- 32.   [15]    J Val ente,  D S anz, J  Del  C e r r o, A Barr ie nto s , MÁ  de  F r ut os. Ne ar-optim al c o vera ge  tra j ectori es for  imag e mosaic i ng usi ng a mi ni  quad-r o tor ove r  irregu lar-sh a p ed fiel ds.  Precis. Agric.  2013;  14(1): 11 5- 132.   [16]    E Galceran, M Carreras. A surve y   on cover age p a th pla n n i ng for robotics .   Rob. Auton. Syst . 2013;   61(1 2 ): 125 8-1 276.   [17]    LA Z ade h. Outl ine  of a N e w  A ppro a ch to th e  Anal ys is of Co mple x S y stems  and  Decis i o n   Processes.   Syst. Man Cybern. IEEE Trans.  1973; 3(1): 2 8 -44.   [18]    T  Lee. F u zzy   Motion Pl an nin g  of  Mobi le R obots i n  Unk n o w n E n viro nm ents.  J. Intell. Robot. Syst .  200 3; 37: 177- 191.   [19]    R Kal a , A Sh ukla, R  T i w a r i . Fusion  of pr o bab ilistic  A   * alg o rithm and  fuzz y  infere nc e  s y stem  for   robotic p a th pl ann ing.  Artif. Intell. Rev.  201 0;  33(4): 307- 32 7.  [20]    M Park, J Jeon, M Lee.  Obst acle  avo i d ance  for  mo bil e  ro b o ts usi ng  artific i al  pote n tia l  fie l d a ppro a ch   w i th simul a ted  anne ali ng.  In IEEE Internationa l S y m posi u m on  Industria l Electron ics, 200 1. 200 1 :   153 0-15 35.     Evaluation Warning : The document was created with Spire.PDF for Python.