I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   14 ,   N o .   1 A p r i l   201 9 ,   p p.   1 ~ 8   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 4 .i 1 . pp1 - 8             1       Jou r n al   h o m e pa ge ht t p: / / i ae s c or e . c om / j our na l s / i nde x . php/ i j e e c s   C o m p a r i so n   o f   d i f f e r e n t   c o n f i g u r a t i o n   sp a c e   r e p r e s e n t a t i o n s   f o r   p a t h   p l a n n i n g   u n d e r   c o m b i n a t o r i a l   m e t h o d       S an jo K u m ar   D e b n ath ,   R o s l i   O m ar ,   N o r   Bad ar i yah   A b d u l   Lati p   F a c ul t y   o f   E l e c t r i c a l   a nd   E l e c t r o ni c   E ng i ne e r i ng ,   U ni v e r s i t i   T un   H u s s e i n   O nn   M a l a y s i a ,   M a l a y s i a       A r ti c l e   I n fo     A B S TR A C T     Ar t i c l e   h i s t or y :   R e c e i v e D e c   1 5 ,   2018   R e v i s e F e b   16,   201 9   A c c e pt e F e b   27,   201 9       T he   u s e   o f   a u t o no m o us   v e hi c l e / r o bo t   ha s   be e a do pt e w i de l y   t o   r e pl a c e   hum a be i ng s   i pe r f o r m i ng   da ng e r o us   m i s s i o ns   i a dv e r s e   e nv i r o nm e nt s .   K e e pi ng   t h i s   i n   m i nd ,   pa t p l a nni ng   e ns u r e s   t ha t   t he   a u t o no m ous   v e hi c l e   m us t   s a f e l y   a r r i v e   t o   i t s   de s t i n a t i o w i t r e q ui r e d   c r i t e r i a   l i ke   l o w e r   c om put a t i o t i m e ,   s ho r t e s t   t r a v e l l e pa t a nd  c o m pl e t e ne s s .   T he r e   a r e   f e w   ki nd s   o f   pa t pl a nn i ng   s t r a t e g i e s ,   s uc a s   c o m bi na t o r i a l   m e t ho d,   s a m pl i ng   ba s e m e t ho a n b i o - i ns p i r e m e t ho d.   A m o n g   t he m ,   c o m bi na t o r i a l   m e t ho c a a c c o m pl i s c o upl e   o f   c r i t e r i a   w i t ho ut   f ur t he r   a d j us t m e n t   i c o nv e nt i o na l   a l g o r i t hm .   C o nf i g ur a t i o s pa c e   pr o v i de s   d e t a i l e i nf o r m a t i o a bo ut   t h e   po s i t i o o f   a l l   po i nt s   i t he   s y s t e m   a nd  i t   i s   t he   s pa c e   f o r   a l l   c o nf i g ur a t i o ns .   T he r e f o r e ,   C - s pa c e   de no t e s   t h e   a c t ua l   f r e e   s pa c e   z o ne   f o r   t he   m ov e m e nt   o f   r o bo t   a nd  g ua r a nt e e s   t h a t   t he   v e h i c l e   o r   r o bo t   m us t   no t   c o l l i d e   w i t t h e   o bs t a c l e .   T hi s   pa pe r   a na l y s e s   di f f e r e n t   C - S pa c e   r e p r e s e n t a t i o t e c hni qu e s   unde r   c o m bi na t o r i a l   m e t ho ba s e o t he   p a s t   r e s e a r c he s   a n t he i r   f i nd i ng s   w i t d i f f e r e nt   c r i t e r i a   s uc a s   o pt i m a l i t y ,   c o m pl e t e ne s s ,   s a f e t y ,   m e m o r y   us e s ,   r e a l   t i m e   a nd  c o m put a t i o na l   t i m e   e t c .   V i s i bi l i t y   G r a ph  ha s   o pt i m a l i t y   w hi c h   i s   a   un i qu e   f r o m   o t he r .   Ke y w or ds :   Ce l l - de c o m po s i t i o n   P a t pl a nn i ng   P o t e n t i a l   f i e l d   V i s i b i l i t y   gra p h   V o r o n o i   di a g ra m   C opy r i gh t   ©   201 9   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e .     A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   Ro s l i   O m a r ,     F a c ul t y   of   E l e c t r i c a l   &   E l e c t r o n i c   E n gi n e e r i n g ,     U n i v e r s i t i   T u n   H us s e i O nn  M a l a y s i a ,   P a ri t   R a j a ,   B a t u   P a ha t - 8 6400 ,   J o h o r ,   M a l a y s i a .   E m a i l :   r o s l i o @ ut hm . e du . m y       1.   I N TR O D U C TI O N     P a t h   pl a nni n a l go r i t hm   i s   i m po r t a n t   t o   pr o duc e   a n   o pt i m a l   pa t h   t ha t   e n a b l e s   t h e   s h o r t e s t   di s t a n c e   m o ve m e n t   o f   a   ve h i c l e   o r   r o b o t   f r o m   a   s t a r t i n po i n t   t o   a   t a r ge t   po i n t   w i t h   m i ni m u m   c o m put a t i o na l   t i m e .     T h e   pa t h   pl a nn i ng  a l go r i t h m   s h o ul a l s o   h o l c o m pl e t e   c r i t e ri o n   s o   t h a t   i t   i s   a b l e   t f i n a   pa t h,   i f   o n e   e xi s t s .   B e s i de s   t h a t ,   t h e   v e h i c l e ’s   s a f e t y ,   m e m o r y   us a ge   fo r   c o m put i n a n t h e   r e a l - t i m e   a p pl i c a b l e   a l go r i t h m   a r e   a l s o   s i gni f i c a nt   [1 - 6] .   P a t h   p l a nni ng  a pp r o a c h e s ,   i n   ge n e ra l ,   c a n   b e   c l a s s i f i e i n   t hr e e   w a y s ,   s uc h   a s   c o m b i na t o ri a l   m e t h o d,   s a m pl i n g - b a s e m e t h o d,   a nd  b i o - i n s pi r e m e t h o d.   T h e   c o m b i na t o r i a l   p a t p l a nni n g   c r e a t e s   a   r o ut e   by   r e s o l v i n que r i e s   a l o n t h e   w a y .   F i gu r e   i l l us t r a t e s   t h e   c l a s s i f i c a t i o n   o f   p a t h   p l a nni n g   a pp r o a c h e s .   It   c o m p r i s e s   m a i nl y   t w o   m e t h o ds   l i ke   C - s pa c e   r e p r e s e n t a t i o t e c hni que   a n g r a p s e a r c h   a l go r i t hm .   T h i s   pa pe r   f o c us e s   o n   C - s pa c e   r e pr e s e nt a t i o n   t e c hn i que s .   Ro a m a (R M ),   c e l l   de c o m po s i t i o n   (CD a n d   po t e n t i a l   f i e l (P F t e c hni que s   a r e   a m o n t h e   w a y s   of   s p a c e   r e p r e s e n t a t i o n .   R o a m a p   t e c hni que   i s   a l s di v i de i nt o   t w o   c a t e go r i e s   -   v i s i b i l i t y   gr a p (V D )   a nd  V o r o n o i   di a g r a m   (V D [7 ].   V i s i b i l i t y   gra p h   (V G a l go r i t h m   f i nds   a   p a t by   c o n n e c t i ng  a l l   t h e   v i s i b l e   v e r t i c e s   of   a n   o b s t a c l e   i n c l u di ng  a   s t a rt i ng  a n a n   e n di ng  po i nt .   A f t e r   t ha t ,   a   s h o rt e s t   pa t h   i s   s e a r c h e f r o m   t h e   c o n n e c t e gra p h.     In  c e l l   de c o m po s i t i o n   ( CD m e t h o d,   t h e   f i r s t   s t e p   i s   t o   de c om po s e   t h e   c o n f i gu ra t i o n   s p a c e   i n t o   c e l l s   a n t h e n   i t   f i n ds   a   c e l l   w h i c h   i s   n o t   o c c upi e by   a n y   ob s t a c l e .   T h e   V o r o n o i   di a g r a m   (V D i s   a e qui d i s t a n t   po i n t   f r o m   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   14 ,   N o .   1 A p r i l   20 19   :     1     8   2   t w o   o r   a l l   t h e   n e a r e s t   o b s t a c l e s   a n b y   c o n n e c t i n a l l   t h e s e   po i n t s ,   a   pa t h   c a b e   fo un [6] ,   [8]  a n d   [9] .     P F   a l go r i t hm   i s   a   pa t pl a nn i ng  t e c hni que   b a s e o a t t ra c t i v e   a n d   r e pul s i v e   po t e n t i a l   [9 - 10 ].           F i gu r e   1 .   C l a s s i f i c a t i o o f   pa t h   pl a nni ng  a pp r o a c h       B e s i de s   t h e   c o m b i n a t o r i a l   m e t h o d,   ra p i dl y   e xpl o r i n ra n do m   t r e e   (RR T i s   a n   e xa m pl e   o s a m pl i ng - b a s e pa t h   pl a nn i ng  w h e r e   pr e - r e gi s t ra t i o n   o t h e   de s i gn   s p a c e   i s   n o t   r e qui r e d.   H e r e   f i r s t l y ,   t h e   s t a r t i n a nd  t h e   t a rge t   po i n t s   a r e   de f i n e d .   T h e n ,   i t   c o n s i de r s   t h e   s t a r t i ng  po i nt   a s   t h e   f o un da t i o f o r   t h e   t r e e ,   b a s e o n   w h i c a   n e w   b r a n c i s   g r o w n   u n t i l   i t   r e a c h e s   t h e   t a rge t   po i n t   [11 - 13] .   P r o b a b i l i s t i c   r o a d m a p   (P R M t e c hni que   i s   a   pa t h - p l a nni n g   a l go ri t hm   t h a t   t a ke s   a r b i t r a r y   s a m p l e s   f r o m   t h e   c o n f i gu r a t i o n   s p a c e   by   c h e c ki n g   t h e   a c c e s s i b l e   f r e e   s pa c e   a n do dgi n t h e   c ra s h e s   t o   f i n a   w a y .   A   l oc a l   pl a nn e r   i s   us e t o   j o i n   t h e s e   c o n f i gur a t i o n s   w i t h   c l o s e - by   c o n f i gura t i o n s .   A   g ra p h   s e a r c a l go ri t hm   i s   a pp l i e a f t e r   a dd i n t h e   i ni t i a l   a nd  go a l   c o n f i gu r a t i o n s   t o   de t e r m i n e   a   p a t [14 - 15] .     T h e   b i o - i n s pi r e m e t h o ds   a r e   t h e   n a t u r e - m o t i v a t e a l go r i t hm s .   V a ri o us   e xa m pl e s   of   b i o - i n s pi r e m e t h o ds   a r e   t h e   G e n e t i c   a l go r i t h m   (G A ) ,   P a r t i c l e   S w a r m   O pt i m i z a t i o n   (P S O ),   S i m ul a t e a nn e a l i ng  (S A ),     a n A n t   Co l o n y   O pt i m i z a t i o n   (A CO ) .   T h e   n a t u ra l   s e l e c t i o pr o c e s s   t o   f i n a   p a t h   s t i m ul a t e s   G A .   T h e r e   a r e   t w s t e ps   of  t h i s   p a t h   pl a nni n g .   F i r s t l y ,   i t   s e t s   up  a   C - s pa c e   i n   a   f r e e   s pa c e   a n t h e n,   i t   f i n ds   a   pa t h   f r o m   t h e   s t a r t   po i n t   t o   t a r ge t   po i nt   [1 6].   P S O   i s   a e s t a b l i s h e m e t a - h e u r i s t i c   po pul a c e   b a s e c a l c ul a t i o n ,   i ni t i a l l y   pr e s e nt e by   K e n n e y   a n E b e rh a rt   i n   1 995 ,   t o   r e s o l v e   t h e   gl o b a l   o pt i m i z a t i o n   i s s ue s   i t h e   l i g ht   o f   s h a r e d   c o n duc t   of   n a t u ra l   po pul a c e s   [17].   A   P S O   b a s e pa t h - p l a nn i n a l go r i t hm   t r i e s   t o   s o l v e   t h e   i s s ue s   of   m ul t i - t a r ge t   pa t h   p l a nni n g   m o de l s   r e ga rdi n g   r o bo t ' s   e n e r gy   c o n s um pt i o n   a n d   pa t h ' s   s a f e t y   [18].   T h e   A CO   e m u l a t e s   a n   a nt   t o   m a ke   a   pa t h   w h e n   t h e   f oo s o ur c e   i s   c o n f i rm e d.   T h e   a nt   s e pa ra t e s   i t s   r o ut e   t o   t h e   f oo s o ur c e   w i t h   ph e r o m o n e s   fo r   t r a c ki ng  pu r po s e .   In   A CO ,   t h e   pa t h   i n   b e t w e e n   t h e   i ni t i a l   a n t a r ge t   po i nt s   a r e   ha p ha z a r dl y   ge n e ra t e [19 - 21] .   S A   a l go r i t hm   l o o ks   l i ke   t h e   w a r m i n a n c oo l i n p r o c e s s   of   m e t a l s   t o   r e gul a t e   t h e   i nn e r   s t ruc t u r e   o f   i t s   p r o pe r t i e s .   H i g h e t e m pe r a t u r e   p r o c e dur e   i n v e s t i ga t e s   a   b i gge r   r e gi o n   o f   s e a r c s pa c e .     T h e   g r a d ua l   p r o b a b i l i s t i c   p r o pe r t i e s   pe rm i t   t hi s   a l go ri t hm   t o   a v o i l o c a l   m i ni m a   a nd  m a x i m a   s o l ut i o n s     [10 - 12] ,   [ 16],   [21 24] .   C - s pa c e   r e p r e s e n t a t i o n   t e c hn i que   us e i n   V G ,   V D ,   CD   a nd  P F   a r e   s t udi e b e c a us e   i t   i s   us e i c o m b i na t o ri a l   pa t h   pl a nni n g.   C - s pa c e   pr o v i de s   de t a i l e i n f o r m a t i o n   a b o ut   t h e   po s i t i o n   o f   a l l   po i n t s   i n   t h e   s y s t e m   a n i t   i s   t h e   s p a c e   fo r   a l l   c o n f i gu r a t i o n s .   A n   i l l us t ra t i o n   o f   a   C - s pa c e   fo r   a   c i r c ul a r   v e h i c l e   i s   s h o w n   i F i gu r e   2 .   It   a s s um e s   t h e   v e h i c l e   o r   r o bo t   a s   a   po i nt   a nd  a dds   t h e   a r e a   o f   t h e   o bs t a c l e s   s o   t h a t   t h e   p a t h   p l a nni n g   c a n   b e   do n e   m o r e   e ff i c i e n t l y .   C - s pa c e   i s   ob t a i n e by   a ddi n t h e   v e h i c l e   r a d i us   w h i l e   s l i di n i t   a l o n t h e   e dge   of   t h e   o b s t a c l e s   a n d   t h e   b o r de r   o f   t h e   s e a r c h   s p a c e .     In  F i gu r e   2( a ) ,   t h e   o b s t a c l e - f r e e   a r e a   i s   r e p r e s e n t e by   t h e   w h i t e   c e l l s .   T h e   v e h i c l e   i s   s h o w n   by   a   da r b l a c do t   h o v e r e w i t di m   s ha di n g .   T hr e e   po s s i b l e   c o l l i s i o n - f r e e   pa t h s   a r e   d ra w n   a nd  t h o s e   a r e   do t t e d,   s e m i - da b b e a n s o l i l i n e s   t o   a c hi e v e   t h e   t a r ge t / go a l   c o n f i gur a t i o n   f r o m   s t a r t / i ni t i a l   c o n f i gura t i o G r a ph   S e a r c h   A l go ri t hm s   P r o ba bi l i t y   r o a dm a p   RRT   P a r t i c l e   S w a r m   O pt i m i z a t i o ( P S O )   G e ne t i c   A l g o r i t hm   A nt   c o l o n y   o pt i m i z a t i o ( A C O )   S i m ul a t e d   A nne a l i ng   ( S A )   B i o l o gi c a l l y   In s pi r e d   P a t h   P l a n ni ng   A ppr o a c he s   Co m b i n a t o r i a l   S a m p l i n g   B a s e d   V i s i bi l i t y   g r a ph   V o r o n o i   di ag r am   C - S pa c e   R e p r e s e n t a t i o   T e c hni qu e s   C e l l   D e c o m po s i t i o n   R o a M a p   P o t e nt i a l   F i e l d   B e s t   F i r s t   D e pt h   F i r s t   S e a r c h   D i j k s t r a s   A*   a nd  D *     B r e a d   F i r s t   S e a r c h   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       Com par i s on   of   di f f e r e n t   c onf i gur a t i on   s pa c e   r e pr e s e nt at i ons   f or   pa t pl a n ni ng…   ( Sanj o y   K um ar   D e bnat h )   3   c o n s i de r i ng  t ha t   C - s p a c e   i s   n o t   c r e a t e d.   Co n v e r s e l y ,   w h e n   t h e   w o r ks pa c e   i s   c o n s i de r e a s   C - s p a c e ,     a s   a p pe a r e i F i g u r e   2(b ),   t h e   r o b o t   h a s   j us t   a   s i n g l e   po s s i bl e   w a y .   T h i s   a l s o   r e v e a l s   t ha t   t h e   f r e e   s pa c e   h a s   b e e n   r e duc e w h i l e   t h e   o bs t a c l e s ’  r e gi o n   ha s   b e e n   e n l a r ge d.   T h e r e f o r e ,   C - s pa c e   de n o t e s   t h e   a c t ua l   f r e e   s pa c e   z o n e   f o r   t h e   m o v e m e n t   o f   r o b o t   a n i t   gu a r a nt e e s   t h a t   t h e   v e hi c l e   o r o bo t   m us t   n o t   c o l l i de   w i t t h e   o b s t a c l e .   In   t h i s   c a s e ,   t h e   f i r s t   s t e i s   t o   c o n s t ruc t   t h e   C - s p a c e   e n v i r o nm e nt   a nd  t h e   s e c o n s t e i s   t o   ge n e r a t e   a   p a t us i n g   a   g ra p s e a r c a l go r i t hm .   D i j ks t r a ’s ,   A o D *,   D e pt h - f i r s t   s e a r c h,   B r e a F i r s t ,   B e s t   f i r s t   a r e   t h e   a l go ri t hm s   t o   f i n d   t h e   o pt i m a l   p a t de pe ndi n g   o t h e   ge n e ra t e pa t [1 ],   [25 - 2 6].           F i gu r e   2 .   Co n f i gu r a t i o s pa c e   f o r   p a t p l a nni n g       2.   C O M B I N A T O R I A P A T H   P LA N N I N G   2. 1 .      V i s i b i l i ty   G r ap h   (V G )   V G   i s   a   pa t h   pl a nn i ng  m e t h o b a s e o n   c o m b i n a t o r i a l   s y s t e m   [4]  t h a t   f i n ds   o ut   a   pa t h   by   s o l v i n g   que r i e s   a l o n t h e   w a y .   V G   i s   us e i n   m a n y   a ppl i c a t i o n s   s uc h   a s   g r a p hi c s   a n r o b o t i c s   [27].   It   i s   a   s e t   o po l y g o n a l   c o n f i gu r a t i o i a   pl a n e   (e i t h e t w o   o r   t hr e e   di m e ns i o n a l a t   a n   u n di r e c t e g ra p w h e r e   v e r t i c e s   a r e   t h e   ob s t a c l e s ’  ve r t i c e s   a nd  t h e   e dge s   a r e   t h e   pa i r s   o f   v e r t i c e s .   A n   o pe n   l i n e   s e gm e n t   b e t w e e n   t w o   v e r t i c e s   do e s   n o t   i n t e r s e c t   a n y   ob s t a c l e   [28 - 29].   I n   V G ,   t h e   v e r t i c e s   i n c l ude   s t a rt i ng  po i n t   a nd  t a r g e t   po i n t   [ 28].     It   i s   i m po r t a n t   t ha t   o b s t a c l e s   a r e   i n   a n   o pe n   s e t   t o   e n s ur e   t ha t   t h e   s h o r t e s t   pa t h   e xi s t s .   T o   pr o c e e w i t h   t h e   v i s i b i l i t y   gr a p h   i n   s e a r c h   s pa c e ,   t h e   s e t s   of   v e r t i c e s   t h a t   a r e   m ut ua l l y   v i s i b l e   n e e t be   di s c ov e r e d.     T h i s   i m pl i e s   t h a t   f o r   e a c h   pa i r   o f   ve r t i c e s ,   i t   n e e ds   t o   be   t e s t e w h e t h e r   t h e   c o n n e c t i n l i n e   s e gm e nt   h i t s   a n y   ob s t a c l e   [30].   T h e   c o nn e c t e v e r t i c e s   w i t c a nt e s h o w n   i F i gu r e   3 .           F i gu r e   3 .   T h e   c o nn e c t e v e r t i c e s   w i t h   c a nt e r   p   [30]       E xt e n s i v e   i n v e s t i ga t i o n s   ha v e   b e e n   do n e   o n   V G   t o   r e duc e   t h e   c o m put a t i o n a l   t i m e .   F o r   i n s t a n c e ,   r e s e a r c h e r s   a pp l i e V G   i n   [5]  b a s e o n   t h e   po l y go n   a ggr e g a t i o n .   T h e   m a i n   i de a   o f   t h i s   t e c hni que   i s   t o   c l us t e r   s m a l l   o b s t a c l e s   a n m e r ge   t h e   po l y g o n s   a f t e r   c l us t e r i ng.   F urt h e r,   i n   [ 14],   a n   a l go ri t hm   w a s   pr o po s e t s e pa ra t e   t h e   C - s pa c e s   i n   m a n y   pa r t s   a nd  V G   w a s   ut i l i z e t o   a s s e m b l e   e a c h   pa rt   a t   pa ra l l e l   di r e c t i o n.     T h e   s h o r t e s t   pa t h   w a s   de t e r m i n e by   i n t e g ra t i n e a c h   pa rt i a l   m i n i m u m   di s t a n c e   pa t h.   B e s i de s   t h a t ,   a   s t udy   i n   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   14 ,   N o .   1 A p r i l   20 19   :     1     8   4   [31]  e nha n c e t h e   V G   a l go ri t hm   by   s h a r i ng  l o c a l   i n f o r m a t i o n   b e t w e e n   m ul t i p l e   r o b o t s   t o   ov e r c o m e   i t s   di s a dv a n t a ge s .   T h e   p r o po s e a l go r i t hm   ge n e r a t e po l y go n s   f r o m   a   s e ri e s   o f   l i n ke s e gm e nt s   a nd  m e r ge t h e m ,   i f   n e c e s s a r y .   T h e   r e s ul t   o t h e   s h a ri n i n f o rm a t i o n   w a s   c o m pa r e w i t h   t h e   n o n - s h a ri n i n f o r m a t i o n   by   V G   a n d   t h e   p r o po s e a l go ri t hm   w a s   m o r e   e f fe c t i ve .   T h e   m o di f i e V G   i de v e l o p e a   V i rt u a l   rub b e r   b a n d   v i s i b i l i t y   gr a p h   (V R B V G m e t h o t o   ge n e ra t e   a   V G   u n de r   t h e   a s s u m pt i o n   t h a t   C - s p a c e s   w e r e   un k n o w n   a n l o c a t e o ut s i de   t h e   v e h i c l e   o f   s o n a r   c o v e r a ge .   T h e y   us e t o r pe do - t y p e   un de r   a c t ua t e v e hi c l e s   t o   t ra v e l   i n   a unk n o w n   u n de r w a t e c o n di t i o n.     2. 2 .      V o r o n o i   D i agr am   (V D )   T h e   a i m   o f   V D   i s   t o   f i n a   pa t h   f a r   f r o m   t h e   ob s t a c l e s   [24].   T h e   i de a   b e h i nd  t h e   V D   i s   t o   ge n e r a t e   a   l i n e   s e gm e n t   c a l l e V o r o n o i   E dge   w h i c h   i s   e qui di s t a nt   f r o m   a l l   t h e   po i nt s   of   t h e   ob s t a c l e   a r e a   i n   C - s p a c e     [6] [ 33] .   T h e   po i nt ,   w h e r e   t h e   V o r o n o i   E dge   j o i n s   w i t e a c o t h e r,   i s   c a l l e V o r o n o i   V e rt e x.   A e xa m pl e   o V D   r e p r e s e n t a t i o n   t ha t   i s   us e fo r   pa t h   pl a nni n i s   d i s pl a y e d   i n   F i gu r e   4.   T h e   r e s ul t i n p a t h   i s   s h o w n   i n   s o l i d   b l a c l i n e .   A s   pe r   t h e   i l l us t ra t i o n   o f   F i gur e   4 ,   V D   ha s   e dge s   t o   gi v e   a   m a x i m u m   c l e a ra n c e   pa t a m o n s e t   o ob s t a c l e s   i n   t h e   C - s pa c e .   If   a   v e h i c l e   t r a v e r s e s   t h e   pl a nn e d   pa t h,   i t   i s   g ua ra n t e e t ha t   t h e   v e h i c l e   m us t   n o t   i n t e r s e c t   a n y   ob s t a c l e .   H ow e v e r ,   t h e   V D   ge n e r a t e p a t h s   a r e   n o t   o pt i m a l   i t e r m s   o f   l e n gt h.           F i gu r e   4 .   T h e   d a s h e l i n e s   i V o r o n o i   di a g ra m   a r e   t h e   s e t   o f   po i n t s   e qui d i s t a nt   t o   o b s t a c l e s .   T h e   p a t i s   s h o w n   i s o l i d   da rke l i n e s .       In   [6],   i m p r o v e m e n t s   w e r e   do n e   o n   V D   t o   fo l l ow   t h e   ki n e m a t i c   c o n s t r a i n t   o f   a a i r c ra f t   i n   t hr e e   s t e ps .   F i r s t l y ,   a n   i n i t i a l   di a g ra m   w a s   ge n e ra t e by   t h e   f un da m e n t a l   V D .   S e c o n dl y ,   t h e   i n i t i a l   di a g ra m   w a s   e nh a n c e by   s m oo t h i ng  t h e   i m p ra c t i c a l   c o rn e o f   a l l   pa t h s   f r o m   s t a r t i n po i nt   t o   t a r ge t   po i n t .   T h e n ,   t h e   c o s t   of   t h e   e dge   of  i m p r o v e d   V D   w a s   m o de l e a n w e i gh t e d.   F i na l l y ,   t h e   o pt i m a l   pa t h   w a s   s e l e c t e d   us i n t h e   D i j ks t ra ’s   a l go r i t hm   f r o m   t h e   s m o o t h   pa t h .   I m p r o v e V D   w a s   m uc h   l o w e r   c o m pa r e t o   t h e   f un da m e nt a l   o n e .   A n o t h e r   e nha n c e m e nt   w a s   do n e   o n   t h e   f un da m e nt a l   V D   i n   [ 24]  w i t h   D e l a u na y   t r i a ngul a t i o n.     T h e   a l go r i t h m   w a s   t e s t e w i t h   25  d i f fe r e nt   s e t t i ngs .   T h e   o ut c o m e s   r e v e a l e t ha t   t h e   i m p r o v e V D   w a s   c o m put a t i o n a l l y   l e s s   e xpe n s i v e   a n i t   r e s po n de i s h o rt e r   t i m e .   B ut   i t   p r o duc e a   p a t h   t ha t   m i g ht   n o t   b e   t h e   s h o rt e s t   o n e   a nd  t h i s   w a s   t h e   d r a w b a c o t h i s   a l go ri t hm .   T h e   m o di f i e V D   w a s   a ppl i e i n   o n   u nm a nn e a i r   v e h i c l e   i n   a   dy n a m i c   e n v i r o n m e n t .   H e r e ,   t h e   pa t w a s   c r e a t e by   us i n t h e   ra d a r   t hr e a t   f i e l b a s e V D .     T h e D i j ks t r a ’s   a l go r i t hm   w a s   a pp l i e t o   c a l c ul a t e   t h e   s h o rt e s t   di s t a n c e .   T o   r e duc e   t h e   c o m put a t i o na l   t i m e ,     i n   [33]  t h e   i m a ge s   w e r e   c a pt ur e a n t h e n   c l us t e r e i n t o   a   s m a l l e r   gr o up .   A   s m oo t h   pa t h   f o r   a   r o bo t   w a s   a l s c r e a t e f r o m   a   p a t pl a nni n g   a l go ri t hm   b a s e o t h e   f uz z y   i nt e r f e r e n c e   m e c h a ni s m .     2. 3 .      C e l l - D e c o m p o s i ti o n   (C D )   CD   m e t h o m a i n l y   f i n ds   a o b s t a c l e - f r e e   c e l l   a nd  b ui l ds   a   f i ni t e   g ra p f o r   t h e s e   c e l l s   [11] .   I t   b r e a ks   t h e   e n v i r o nm e nt   i n t o   c e l l s   a n d   e n s u r e s   t ha t   e a c h   c e l l   i s   di s c r e t e ,   n o n - o ve r l a ppi ng  a nd  n o t   o c c upi e by   a n y   ob s t a c l e .   A   f i n i t e   g r a p i s   b ui l t   by   r e l e ga t i n g   e v e r y   c e l l   a s   a   h ub .   I n   c e l l   de c o m po s i t i o n   m e t h o d,   t h e   f i r s t   s t e i s   t o   de c o m po s e   t h e   c o n f i gura t i o n   s p a c e   i nt o   c e l l s .   A f t e r   t ha t ,   t h e   c o nn e c t i v i t y   gr a p h   i s   b ui l t .   E a c h   n o de   of  t h e   ge n e r a t e g ra p h   r e p r e s e nt s   a   c e l l   a n t h e y   a r e   b e t w e e t w o   n o de s   r e p r e s e n t   t w o   c o r r e s po n d i n c e l l s   a dj o i n i ng  e a c h   o t h e r.   T h e n   t h e   c o nn e c t i v i t y   gr a p h   f r o m   i ni t i a l   t o   e n po i nt   i s   de t e r m i n e [9] .   T h e r e   a r e   s e v e r a l   t y pe s   o c e l l   de c o m po s i t i o n   m e t h o ds   s uc h   a s   r e gul a r   g ri de c o m po s i t i o n   (R G ),   a da pt i v e   c e l l   de c o m po s i t i o n   (A CD a n d   e xa c t   c e l l   de c o m po s i t i o n   ( E CD )   [ 9],   [29] .   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       Com par i s on   of   di f f e r e n t   c onf i gur a t i on   s pa c e   r e pr e s e nt at i ons   f or   pa t pl a n ni ng…   ( Sanj o y   K um ar   D e bnat h )   5   In  o r de r   t o   o v e r c o m e   t h e   d ra w b a c of   CD   m e t h o d,   a n   i m p r o v e m e n t   w a s   m a de   i n   [11 t o   i n c r e a s e   t h e   e ff i c i e n c y   of   t h e   a l go r i t h m   by   di v i di n t h e   c e l l   qua r t e r l y .   T he n ,   t h e   c e l l   w a s   c h e c ke t o   f i n o ut   t h e   pr e s e n c e   of   a n y   ob s t a c l e .   A f t e r   t h a t ,   t h e   c e l l   w a s   di v i de a ga i n   i qua r t e r.   T hi s   m e t h o w a s   us e t a c h i e v e   t h e   o pt i m u m   pa t h.   E x a c t   c e l l   de c o m po s i t i o n   m e t h o a n e x h a us t i v e   pa t h   pl a nn i ng  w e r e   us e i n   [35] .   T h e   s t e f o r   t h i s   a l go r i t hm   b e ga n   w i t h   t h e   m i n e a b l e   a r e a   t ha t   w a s   di v i de d   i n t o   a e xa c t   c e l l .   T h e n,   e a c h   c e l l   c o v e r a ge   pa t w a s   ge n e r a t e w i t h   c o v e r i n di r e c t i o n   a n t h e   ge n e r a t e g ra p h   p a t h s   w e r e   b a s e o n   t h e   a dj a c e n c y   gr a p h.     By   c o n s i de ri n a l l   g ra p h   p a t h s   w i t h   a l l   c o ve r i n d i r e c t i o n s ,   a   m o v i n p a t h   w a s   ge n e r a t e d.   L a s t l y ,   a   s h o r t e s t   m o v i n p a t f o r   a l l   g ra p h   pa t h s   w a s   de t e rm i n e d   a nd  t h e   e xha us t i v e   pa t w a s   ge n e r a t e d.   T h e   n o n - o pt i m a l   p a t i s   o n e   of   t h e   dra w b a c ks   of   CD .   A   r e s e a r c h   i n   [ 36]  h a de ri v e t h r e e   f o r m ul a s   us i n L n o rm ,   s qu a r e L 2,   a n L ∞  n o rm .   A s   a n   a l t e rna t i v e   t o   us e   t h e   c e l l ’s   m i dpo i n t s   i n   t h e   f unda m e nt a l   CD ,   t h i s   t e c hn i q ue   us e t hr e e   fo r m u l a s   t o   de f i n e   t h e   m e t r i c s .   A   s t udy   i n   [37]  ge n e r a t e CD   di r e c t l y   i n t o   w o r ks pa c e s .   T h e y   a ppl i e t h e   pa t p l a nni n g   f o r   pa l l e t i z i ng  a nd  c o m m o h a ndl i n j o b s .   T h e   a l go r i t hm   p r o duc e c y l i n d r i c a l   c e l l   de c o m pos i t i o i n   t h e   w o r ks pa c e   o f   a   s i D O F   r o bo t   t o   s pe e up  t h e   t i m e   w i t h o ut   a n y   r e qui r e m e nt   o f   a o b s t a c l e s   t r a n s f o r m a t i o n   i a   w o r ks pa c e   i n t o   c o n f i gu r a t i o s pa c e s     2. 4 .      P o te n ti a l   F i e l d   (P F )   P F   w a s   f i r s t l y   s ugge s t e by   K h a t i b   [38].   T hi s   p a t pl a nni n g   a l go ri t hm   i s   b a s e o n   t h e   a t t r a c t i v e   po t e n t i a l   a n r e pul s i v e   po t e n t i a l   i n   t h e   c o n f i gur a t i o n   s pa c e   c o n s i s t i n o f   a   s t a rt i ng  po i nt ,   a   t a rge t   po i nt ,     a n o b s t a c l e s .   T h e   v e h i c l e   i s   r e pr e s e nt e a s   a   po i n t   t ha t   m o ve s   un de r   t h e   po t e n t i a l   f i e l d.   T h e   t a r ge t   po i n t   a c t s   a s   a a t t ra c t i v e   po t e n t i a l   w h i l e   t h e   o b s t a c l e s   i c o n f i gura t i o s pa c e s   s i m u l a t e   r e pu l s i v e   po t e n t i a l .   R e pul s i v e   po t e n t i a l   t a s ks   i p a t pl a nni n a r e   t o   a v e r t   t h e   v e h i c l e s   t h a t   m a y   c o l l i de   w i t h   a n y   e xi s t i ng  o b s t a c l e   i n   c o n f i gur a t i o n   s p a c e s ,   m o v i n g   u n de t h e   i n f l ue n c e s   o f   a t t ra c t i v e   f o r c e s   [9 - 10] .   A   gl o b a l   o ff - l i n e   pa t h   p l a nni n m e t h o do l o g y   w a s   a ppl i e us i n a n   e n e rgy - b a s e a ppr o a c r e c o gn i z e a s   A rt i f i c i a l   P o t e nt i a l   F i e l (A P F f o r   M ul t i - R o bo t   S y s t e m s   (M RS s ).   B a s e o n   t h e   po t e n t i a l   f i e l d,   a   de ve l o pe d   a r t i f i c i a l   po t e nt i a l   f i e l (A P F pa t h   p l a nni n t e c hni que   w a s   h o s t e a n i t   w a s   m o r e   o pe r a t i v e   i f i n di ng  t h e   s h o r t e s t   p a t [39] .   A n o t h e r   po t e nt i a l   f i e l m e t ho us e t h e   k i n e m a t i c s   o f   a   s i x - w h e e l   r o v e r   fo r   m o t i o n   o n   r o ug h   3D   t e rr a i n   w h e r e   c o m pa ra t i v e   s i gn i f i c a n c e   of   t h e   pa t h s   w a s   ob t a i n e f r o m   f o ur   di s s i m i l a c os t   f un c t i o n s   w i t r e s pe c t   t o   e n e rgy ,   t ra c t i o f o r c e ,   s l i a n d   de v i a t i o n   f r o m   a   s t r a i g ht   l i n e .   W i de   e xpe r i m e n t s   an s i m u l a t i o n s   r e v e a l e t ha t   t hi s   t e c hn i que   w a s   b e t t e r   i n   o b t a i ni n pa t h s   [4 0].       3.   DISCUSSIO O C O M B INAT O RIAL   P AT H   P L ANNING   F e w   c o m b i n a t o ri a l   p a t h   p l a nni n m e t h o ds   a r e   t a b ul a t e i T a b l e   a n e xhi b i t s   t h e i r   p r o s   a n d   c o n s .   It   r e v e a l s   t ha t   V G   i s   c a pa b l e   t o   r e s o l ve   pa t h   p l a nni n i s s ue   by   f i n di ng  t h e   s h o rt e s t   di s t a n c e   w i t h o ut   t h e   pr o b a b i l i t y   o f   l o c a l   m i ni m a   [4] ,   [7] ,   [31 ],   [ 41]  a n [45 ].   I t   s a t i s f i e s   t w o   c r i t e r i a   f o r   o pt i m a l   pa t pl a nni n i n   t e rm s   o f   c o m pl e t e n e s s   a n m i ni m um   t r a v e l l e p a t h   [4],   [ 5],   [7 a nd  [ 46] .   B e s i de s   t h a t ,   i t   i s   s i m pl e   t o   i m p l e m e nt   [31] .   T h e   l i m i t a t i o n   o f   V G   i s   t h e   c o m put a t i o na l   t i m e   s i n c e   i t   i n c r e a s e s   w i t h   t h e   i n c r e a s i n g   qua n t i t y   of   ob s t a c l e s   i C - s p a c e s .     T h e   m a i a dv a nt a ge   o f   V D   i s   t h e   m i ni m u m   c o m put a t i o na l   t i m e   a n d   t h e   a b i l i t y   t o   a t t a i t h e   g l o b a l   o pt i m a l   s o l ut i o n   [18] .   F u r t h e rm o r e ,   i t   i s   a   c o m pl e t e   a l go r i t hm   s i n c e   i t   i s   c a pa b l e   t o   f i n a   w a y   w i t h o ut   t h e   c h a n c e   o f   l o c a l   m i ni m a   o c c urr e n c e .   I a n y   c a s e ,   t h e   w e a kn e s s   of   V D   i s   t ha t   i t   i s   u na b l e   t o   c r e a t e   t h e   s h o rt e s t   pa t [7]   f o r   w h i c t h e r e   i s   a   h i g h   po s s i b i l i t y   of   w a s t a ge   o f   e n e r gy   c o n s um p t i o a nd  c o s t .     T h e   a dv a n t a ge s   o f   CD   a r e   t h a t   i t   gi v e s   gua r a nt e e   t o   f i n d   a   c o l l i s i o n - f r e e   pa t h,   i f   e xi s t s   a n i s   m a na ge a b l e   by   a   r o b o t .   H e n c e ,   i t   i s   a   c o m pl e t e   a l go ri t hm   s i nc e   t h e   r o b o t   c a n   e xpl o r e   t h e   p a t w i t h o ut   t h e   ri s of   l o c a l   m i n i m a   o c c urr e n c e   [8].   N e v e r t h e l e s s ,   t h e   p r o b l e m   of   CD   i s   t h a t   i f   t h e   p r o duc e c e l l   i s   t o o   r o ugh ,   t h e i t   w i l l   n o t   b e   po s s i b l e   t o   a c c o m pl i s h   t h e   m i ni m um   pa t h   l e n g t h .   O n   t h e   o t h e r   ha nd,   i f   t h e   c e l l   i s   t o o   s m a l l ,   t h e n   l o n ge r   c o m p ut a t i o n   t i m e   i s   n e e de [1],   [33],   a n [42 ] .   T h e   c e l l   de c o m pos i t i o n   s t ra t e gy   a l s o   d o e s   n o t   w o r e xt r e m e l y   w e l l   i n   a   dy n a m i c   s i t u a t i o n   a n d   i r e a l - t i m e   c o n di t i o [8] ,   [11 ],   a n d   [33] .   It   i s   n e c e s s a r y   fo r   CD   t o   a dj us t   w i t h   t h e   c o n di t i o n   a s   r e qui r e d;   e . g . ,   i n   e xa c t   CD ,   t h e   c e l l s   a r e   n o t   p r e de f i n e d,   b ut   t h e y   a r e   n o m i na t e d   b a s e o n   t h e   l o c a t i o n   a n d   s h a pe   o f   t h e   o b s t a c l e s   w i t h i t h e   C - s p a c e   [32].   O n e   m a j o r   s h o r t c o m i n o f   P F   m e t h o i s   l o c a l   m i n i m a   a t   w h i c h   t h e   v e h i c l e   c a n   ge t   s t uc k.   A s   P F   m e t h o l e a ds   t h e   v e h i c l e   i n   t h e   d i r e c t i o n   o f   a   m i ni m a   w i t h i n   t h e   f i e l d,   i t   i s   n o t   a s s u r e t ha t   t h e   m i ni m a   i s   t h e   gl o b a l   o n e .   T h i s   m a ke s   t h e   P F   r e c o gn i z e a s   a   l o c a l   m e t h o b e c a us e   t h e   o ut c o m e   of   t h e   f i e l i s   a l m o s t   e xc l us i v e l y   b a s e o n   t h e   n e a r b y   ob s t a c l e s   of   t h e   ve h i c l e .   D i s t a n t   o b s t a c l e s   m a y   h a v e   s m a l l   o r   e v e n   n o   e ff e c t   o n   t h e   v e h i c l e ' s   m o t i o n .   A dd i t i o n a l   d r a w b a c of  P F   m e t h o i s   i t s   l e a s t   s a t i s f a c t o r y   a vo i da n c e   o o bs t a c l e   w h e n   t h e   v e h i c l e   m a n e uv e r s   t hr o ug h   c l o s e - f i t t i n e n v i r o nm e nt   [34].   T h i s   i s   b e c a us e   t h e   P F   i s   n o r m a l l y   m o de l e d   a s   c o n t i n uo us   a n di f f e r e n t i a b l e   oc c upa t i o n,   l e a di ng  t o   a   v a gue   de s c r i p t i o n   o f   t h e   ob s t a c l e ’s   s h a pe   a n di m e n s i o n .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   14 ,   N o .   1 A p r i l   20 19   :     1     8   6   T a b l e   1 .   Co m p a r i s o o f   D i ff e r e n t   C - S p a c e   R e pr e s e n t a t i o n s   u n de Co m b i na t o r i a l   M e t h o d   M e t h o d   O p t i m a l   P a t h   Co m p u t a t i o n a l   T i m e   Re a l   t i m e   M e m o r y   S a fe t y   Co m p l e t e n e s s   RM   VG               VD               CD   RG               A CD               E CD               PF   PF                   T a b l e   2 .   Co m p a r i s o o f   Co m pl e xi t y   of   e a c h   C - S p a c e   R e pr e s e n t a t i o n   M e t h o d   Co m p u t a t i o n a l   Co m p l e x i t y   RM   VG   O (n 2 )   VD   O (n   l o g   n )   CD   RG   O (n   l o g   n )   A CD   O (n   l o g   n )   E CD   O (n   l o g   n )   PF   PF   ---       4.   F U TU R WO R K S   O N   C - S P A C R EP R ES EN TA TI O N   F O R   P A TH   P LA N N I N G   In   t h e   f ut u r e ,   a u t o n o m o us   s y s t e m s   w i l l   b e   o n e   of   t h e   r e qui r e m e n t s   i n   e nh a n c i n h u m a n   qu a l i t y   of  l i f e .   By   a ppl y i n g   a u t o n o m o us   s y s t e m s ,   h u m a n   m o ve m e n t   f r o m   po i nt   A   t o   po i n t   B   w i l l   b e   f a s t e r   a n m o r e   e ff i c i e n t .   I t h e s e   r e g a r I ndus t r y   4. s t a nda rd  i s   a do pt e by   c o m pa ni e s   b a s e o n   f o ur   de s i gn  p r i n c i pl e s   s uc a s   i n t e r o pe r a b i l i t y ,   i n f o r m a t i o n   t r a n s p a r e n c y ,   T e c hni c a l   a s s i s t a n c e ,   a nd  de c e n t ra l i z e de c i s i o n s   [43 i n   i de nt i f y i n a nd  i m pl e m e n t i n g   di f f e r e n t   s c e n a ri o s .   U A V s   a r e   i n c r e a s i n g l y   be i n us e t o   r e pl a c e   hum a n s   i pe r f o r m i n ri s ky   m i s s i o n s   a t   a dv e r s e   e n v i r o n m e n t s   a n d   t hi s   m e e t s   t h e   c ri t e r e a   o f   t e c h ni c a l   a s s i s t a n c e .   T h e   U A V   h a s   t o   t r a v e r s e   a   p r e - pl a nn e pa t h   a u t o n o m o us l y   f r o m   a   s t a r t i n po i nt   t o   t h e   f i n a l   de s t i na t i o n   a nd  t h i s   c a n   b e   de s c r i b e a s   t h e   de c e n t r a l i z e de c i s i o n s   t ha t   i s   a   v i t a l   e n a b l e t o   de v e l o a n   a ut o n o m o us   i n d us t r y .   T h e   P r o j e c t   i a dv a n c e   l a v e l   c a n   a l s o   b e   i n v o l v e w i t h I nt e r o pe ra b i l i t y   t ha t   e n b l e s   t h e   c o m m u n i c a t i o n   w i t h   t h e   U A V   v i a   t h e   Int e rn e t   o f   T h i n gs   (Io T ) .   T hi s   c o n f i rm s   t h e   I n f o r m a t i o t r a n s p a r e n c y .   F urt h e r m o r e ,   t h e   r e qui r e ke y   t e c hn o l o gi e s   fo r   In d us t r y   4. t r a n s f o r m a t i o n   s uc h   a s   a r t i f i c i a l   i nt e l l i ge n c e ,   Io T ,   m a c h i n e   l e a rni n g ,   c l o ud  s y s t e m s ,   c y be r s e c ur i t y   a n a d a pt i v e   r o bo t i c s   pa r t l y   o r   f ul l y   c a n   b e   i m pl e m e nt e w i t h   t h e   c h o s e n   a l go ri t hm   t o   a c hi e v e   t h e   de s i r e o ut c o m e   [44] .       5.   C O N C LU S I O N   R e s e a r c h e r s   a l r e a dy   de v e l o p e a   num b e r   o f   pa t h   p l a nn i n g   a l go r i t hm s   a n d   t h e i r   f i n d i n gs   a r e   c o m pa r e i n   t h i s   pa pe r   f o r   a l l   t h e   c o m b i na t o r i a l   t e c hni que s   c o n s i de ri n g   t h e   na t u r e   o f   m o t i o n   a l o n w i t t h e i a dv a n t a ge s   a n d ra w b a c ks .   E xc e pt   t h a t ,   s e v e r a l   m o di f i c a t i o n s   t ha t   w e r e   pr o po s e by   di ff e r e n t   r e s e a r c h e r s   t ov e r c o m e   t h e   dr a w b a c o e a c h   t e c hn i que   a r e   di s c us s e i n   S e c t i o n   2.   Cu rr e n t l y ,   pa t h   p l a nni n a pp r o a c h   i s   m ul t i - d i m e n s i o n a l .   T o   b e   a n   e f f i c i e n t   pa t pl a nn i ng  a l go r i t hm ,   i t   ( i c a f i n a n   o pt i m a l   c o l l i s i o n - f r e e   p a t h,   (i i i s   c o m pl e t e ,   (i i i ha s   m i ni m a l   c o m p u t a t i o n   t i m e ,   a nd  (i v pr o duc e s   e n e r gy   e ff i c i e n t   p a t h s .   B a s e o n   t h e   ob j e c t i ve   of   t h e   v e h i c l e ’s   m i s s i o a nd  c o n s i de r i n g   t h e   o ut c o m e   of   t h e   a v a i l a b l e   pa t pl a nn i ng  a l go ri t hm s ,   s uc h   a s   c o m put a t i o t i m e ,   c o m pl e t e n e s s   a nd  s a f e t y ,   t h e s e   a l go r i t hm s   c a b e   o pt i m i z e t o   o b t a i n   t h e   e n e r gy   e ff i c i e n t   pa t h   pl a nn i ng.   E a c h   p a t pl a nni n t e c hni que   ha s   i t s   ow n   a dv a n t a ge s   a n d   d ra w b a c ks ;   i t s   a p pl i c a t i o n   c o m pl e t e l y   de pe n ds   o n   t h e   m i s s i o a n d   i t s   p r e de f i n e r e qui r e m e n t s .   F o r   e x a m p l e ,   V D   t e c hn i que   i s   s ui t a b l e   fo r   a i r c r a f t   b e c a u s e   o i t s   h uge   ph y s i c a l   bo d y   a n t h us ,   i t   n e e ds   m o r e   s pa c e s .   V G   pe r fo r m s   w e l l   i n   l e s s   c o m pl e e n v i r o n m e nt   a n d   CD   i s   s ui t a b l e   f o r   a n   a m e na b l e   e nv i r o nm e nt .       A C K N O WL ED G E M EN TS     T h i s   r e s e a r c h   s uppo r t e by   U n i v e r s i t i   T u n   H us s e i n   O nn   M a l a y s i a   ( U T H M a n f un de by   T IE R - V o t   H 131.       R EF ER EN C ES     [ 1]   O m a r ,   R o s l i   b i n . P a t pl a nn i ng   f o r   unm a nne a e r i a l   v e h i c l e s   us i ng   v i s i bi l i t y   l i ne - ba s e m e t ho ds . P hD   di s s . , U n i v e r s i t y   of   L e i c e s t e r ,   201 2.     Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       Com par i s on   of   di f f e r e n t   c onf i gur a t i on   s pa c e   r e pr e s e nt at i ons   f or   pa t pl a n ni ng…   ( Sanj o y   K um ar   D e bnat h )   7   [ 2]     L a t o m be ,   J e a n - C l a ude .   R o bo t   m o t i o pl a nn i ng .   Sp r i n ge r   S c i e nc e   &   B us i ne s s   M e di a,   V o l .   12 4,   20 12 .   [ 3]   G a ne s hm ur t hy ,   M .   S . ,   a nd   G .   R .   S ur e s h .   " P a t h   pl a nn i ng   a l g o r i t hm   f o r   a ut o no m o us   m o bi l e   r o bo t   i dy na m i c   e nv i r o nm e nt . "   S i g na l   P r o c e s s i ng ,   C o m m uni c a t i o a nd   N e t w o r k i n g   ( I C S C N ) ,   2015  3 r I n t e r na t i o na l   C on f e r e nc e   on.   I E E E ,   20 15.   [ 4]   T .   N g u y e t ,   N .   D uy - T ung ,   V .   D uc - L un g ,   a nd  T .   N g u y e n - Vu .   G l o ba l   P a t P l a nn i ng   f o r   A ut o no m o us   R o b o t s   us i ng   M o di f i e d   V i s i bi l i t y g r a ph” .   I E E E ,   201 3;   v o l .   1 3,   pp .   317 32 1.     [ 5]   N g u y e t ,   T r a T hi   N hu ,   T r a n   V a n   H o a i ,   a n N g uy e A nh  T hi .   " S o m e   a dv a nc e d   t e c hni qu e s   i n   r e duc i ng   t i m e   f o r   pa t h   pl a n ni ng   ba s e o v i s i b i l i t y   g r a ph. "   K no w l e dg e   a nd  S y s t e m s   E ng i ne e r i ng   ( K S E ) ,   2 011  T h i r I n t e r na t i o nal   C onf e r e nc e   on .   I E E E ,   201 1.   [ 6]   C he n,   P e ng ,   e t   a l .   " R e s e a r c o f   pa t pl a nn i ng   m e t ho ba s e o n   t he   i m p r o v e V o r o no i   di a g r a m . "   C on t r ol   an D e c i s i o C onf e r e nc e   ( C C D C ) ,   2013   25 t h   C h i ne s e I E E E ,   2013 .     [ 7]   O m a r ,   R o s l i ,   a nd  D a - W e i   G u.   " V i s i b i l i t y   l i ne   ba s e m e t ho ds   f o r   U A V   pa t pl a n ni ng . "   I C C A S - S I C E ,   2009 .   I E E E ,   2 009 .   [ 8]   G l a v a š k i ,   D a n ,   M a r i o   V o l f ,   a nd  M i r j a n a   B o nko v i c .   " R o bo t   m o t i o pl a n ni ng   u s i ng   e xa c t   c e l l   de c o m po s i t i o a nd   po t e nt i a l   f i e l m e t ho ds . "   P r oc e e di ngs   o f   t he   9t W SE A i nt e r n at i onal   c o nf e r e nc e   on   Si m ul a t i on ,   m o de l l i ng   and   opt i m i z at i o n .   W o r l d   S c i e n t i f i c   a n d   E ng i n e e r i ng   A c a de m y   a nd  S o c i e t y   ( W S E A S ) ,   200 9.   [ 9]   S i c i l i a no ,   B r u no ,   L o r e nz o   S c i a v i c c o ,   L ui g i   V i l l a n i ,   a nd  G i us e pp e   O r i o l o .   R o bo t i c s :   m o de l l i ng ,   p l a n ni ng   a nd   c o nt r o l .   Spr i nge r   Sc i e nc e   &   B us i ne s s   M e di a ,   2010 .   [ 10]   L i ,   G ua ng hu i ,   e t   a l .   " A e f f i c i e nt   i m p r o v e a r t i f i c i a l   po t e n t i a l   f i e l ba s e d   r e g r e s s i o s e a r c m e t ho f o r   r o bo t   p a t h   pl a n ni ng . "   M e c hat r on i c s   a nd   A u t om a t i o ( I C M A ) ,   20 12   I n t e r na t i on al   C on f e r e nc e   on .   I E E E ,   2 012 .   [ 11]   A .   A bba di   a nd  R .   M a t o us e k . P a t P l a nn i ng   I m pl e m e n t a t i o U s i ng   M A T L A B   i T e c hni c a l   C o m put i ng   B r a t i s l a v a ,   2014 ,   pp.   1 5.   [ 12]   A di y a t ov ,   O l z ha s ,   a nd  H us e y i A t a ka V a r o l .   " R a p i d l y - e xpl o r i n g   r a ndo m   t r e e   ba s e m e m o r y   e f f i c i e nt   m o t i o pl a n ni ng . "   M e c hat r on i c s   a nd   A u t om a t i o ( I C M A ) ,   20 13   I E E E   I nt e r nat i ona l   C on f e r e nc e   on .   I E E E ,   2013 .   [ 13]   D e v a ur s   D ,   S i m é o T ,   C o r t é s   J .   P a r a l l e l i z i ng   R R T   o di s t r i but e d - m e m o r y   a r c hi t e c t ur e s .   I nR o bot i c s   a nd   aut om at i on   ( I C R A ) ,   20 11  I E E E   I nt e r na t i ona l   C on f e r e nc e   on   201 M ay   9 .   pp .   2261 - 22 66 .   [ 14]   L a t o m be   J C .   M o t i o pl a n ni ng :   A   j o ur ne y   of   r o b o t s ,   m o l e c ul e s ,   di g i t a l   a c t o r s ,   a nd  o t he r   a r t i f a c t s .     T he   I n t e r na t i o na l   J our na l   o f   R obo t i c s   R e s e ar c h .   19 99  N o v ; 18( 11) : 1119 - 28 .   [ 15]   M a r bl e   J D ,   B e k r i s   K E . A s y m pt o t i c a l l y   ne a r - o pt i m a l   pl a nn i ng   w i t p r o ba b i l i s t i c   r o a dm a s pa nne r s .   I E E E   T r ans ac t i ons   on   R o bot i c s , v o l .   29 ( 2) ,   pp . 43 2 - 44,   A pr   2 013 .   [ 16]   A c ho ur   N ,   C ha a l a l   M . M o b i l e   r o bo t s   p a t p l a n ni ng   us i ng   g e n e t i c   a l g o r i t hm s .   I nT he   s e v e nt i n t e r na t i o na l   c onf e r e nc e   o aut onom i c   and   a ut o nom ou s   s y s t e m s ,   B a ke r ( I C A S   20 11) . 201 1;   pp .   111 - 11 5.   [ 17]   E be r h a r t   R ,   K e nne dy   J .   A   ne w   o pt i m i z e r   us i ng   pa r t i c l e   s w a r m   t he o r y .   I M i c r o   M ac h i ne   an H um a S c i e nc e   ( M H S' 95) .   P r oc e e di ngs   o f   t he   S i x t h   I nt e r na t i ona l   Sy m p os i um   on   19 95  O c t   4 .   I E E E .   1 995; pp .   39 - 43 .   [ 18]   D a v oo di   M ,   P a na h i   F ,   M o ha de s   A ,   H a s he m i   S N .   C l e a r   a n s m o o t pa t pl a nn i ng .   A pp l i e Sof t   C om pu t i ng .   2015   J ul   1; 32: pp. 56 8 - 79.     [ 19]   S ha o g a ng   Z ,   M i ng   L .   P a t pl a nn i ng   o f   i ns pe c t i o r o bo t   ba s e o a nt   c o l o n y   o pt i m i z a t i o a l g o r i t hm .   I E l e c t r i c a l   and  C ont r o l   E ng i ne e r i ng   ( I C E C E ) . 20 10   I n t e r na t i ona l   C onf e r e nc e   o 20 10   J un   2 5; I E E E .   p p.   14 74 - 1477 .   [ 20]   W .   H a o   a nd  X .   X u. I m m une   a nt   c o l o n y   o pt i m i z a t i o ne t w o r a l g o r i t hm   f o r   m ul t i - r o bo t   pa t pl a nn i ng   P r o c .   I E E E   I nt .   C on f .   So f t w .   E ng .   Se r v . Sc i . I C SE SS . 201 4; pp. 1118 112 1.   [ 21]   H s u,   C h e n - C hi e n ,   W e i - Y e W a ng ,   Y i - H s i ng   C h i e n ,   R u - Y H o u,   a nd  C h i n - W a ng   T a o .   " F P G A   i m pl e m e n t a t i o o f   i m pr o v e a n t   c o l o n y   o pt i m i z a t i o a l g o r i t hm   f o r   pa t pl a nn i ng . "   I n   E v o l u t i ona r y   C om pu t at i o ( C E C ) ,   2 016   I E E E   C ongr e s s   on ,   pp .   4516 - 4 521 .   I E E E ,   2016 .   [ 22]   G oy a l ,   J i t i K um a r ,   a nd  K .   S .   N a g l a .   " A   ne w   a ppr o a c o f   pa t pl a n ni ng   f o r   m o bi l e   r o bo t s . "   I n   A dv anc e s   i C om put i ng ,   C om m un i c a t i on s   and  I n f o r m at i c s   ( I C A C C I ,   2014  I nt e r nat i ona l   C on f e r e nc e   on ,   pp.   86 3 - 867 .   I E E E ,   2014 .   [ 23]   Y o ng ni a Z ,   L i f a ng   Z ,   Y o ng pi ng   L .   A i m pr o v e g e ne t i c   a l g o r i t h m   f o r   m o bi l e   r o bo t i c   pa t p l a nni ng .   In   C ont r o l   and  D e c i s i on   C on f e r e nc e   ( C C D C )   C hi na   2 012   M ay   23 ; I E E E .   pp .   3 255 - 3260 .     [ 24]   G o m e z   E J ,   S a nt a   F M ,   S a r m i e n t o   F H .   A   c om pa r a t i v e   s t u dy   of   g e om e t r i c   pa t p l a n ni ng   m e t ho ds   f o r   a   m o bi l e   r o bo t :   P o t e nt i a l   f i e l a nd  V o r o no i   di a g r a m s .   I E ngi ne e r i ng  M e c h at r o ni c s   a nd  A u t om a t i on  ( C I I M A ) ,   2013  I I   I nt e r n at i on al   C on gr e s s   o f   2 013   O c t   23; I E E E .   pp .   1 - 6 .     [ 25]   S .   M .   L a v a l l e ,   P l a nn i ng   a l g o r i t hm .   C am br i d ge   U ni v e r s i t y ,   200 6.   [ 26]   K uni g a ha l l i ,   R a g ha v a n,   a nd  J e f f r e y   S .   R us s e l l .   " V i s i b i l i t y   g r a ph  a p pr o a c t o   de t a i l e pa t p l a n ni ng   i c nc   c o n c r e t e   pl a c e m e n t . "   I n   A ut om at i on   an r obo t i c s   i n   c on s t r uc t i on   X I ,   pp .   141 - 147.   19 94 .   [ 27]   D e hg ha ni ,   G .   a nd  M o r a dy ,   H .   A a l g o r i t hm   f o r   v i s i b i l i t y   g r a ph  r e c o g ni t i o o pl a na r   g r a p hs .   I n   F ut ur e   C om put e r   and   C om m u ni c at i on , I C F C C   2009 .   I n t e r na t i ona l   C onf e r e nc e   on   I E E E   2 009 ,   pp .   5 18 - 521 .     [ 28]   K a l e r ,   H r v o j e ,   M i š e l   B r e z a k ,   a nd  I v a P e t r o v i ć .   " A   v i s i b i l i t y   g r a ph  ba s e m e t ho f o r   p a t h   p l a nn i ng   i dy na m i c   e nv i r o nm e nt s . "   I n   M I P R O ,   20 11   P r oc e e di ngs   o f   t he   3 4t h   I nt e r n at i o nal   C on v e nt i on ,   p p.   71 7 - 721 .   I E E E ,   2 011 .   [ 29]   H .   C ho s e t   e t   a l . P r i nc i pl e s   o f   R o bo t   M o t i o T he o r y ,   A l go r i y hm   a nd  i m pl e m e n t a t i o n.   T he   M I T   P r e s s ,   200 5.   [ 30]   M .   D e   be r g ,   O .   C he o ng ,   M .   V a kr e v a l d ,   a nd   M .   O v e r m a r s ,   V i s i bi l i t y   G r a phs . S p r i ng e r .   [ 31]   M .   Y i ng c ho ng ,   Z .   G a ng ,   a nd  P .   W i l f r i d. C o o pe r a t i v e   pa t p l a n ni ng   f o r   m o bi l e   r o bo t s   ba s e o v i s i b i l i t y   g r a ph.     I C ont r o l   C onf e r e nc e   ( C C C ) , C h i na ,   2013 ,   pp .   4915 492 0.   [ 32]   G i e s br e c h t ,   J .   G l o ba l   p a t p l a nni ng   f o r   unm a nne g r o und  v e hi c l e s .   N o .   D R D C - TM - 2004 - 272 .   D e f e nc e   R e s e r c A nd  D e v e l opm e nt   S uf f i e l A l be r t a ,   20 04 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   14 ,   N o .   1 A p r i l   20 19   :     1     8   8   [ 33]   G o nz a l e z ,   R a m o n,   C r i s t i a M a hu l e a ,   a nd  M a r i u s   K l o e t z e r .   " A   M a t l a b - ba s e i nt e r a c t i v e   s i m ul a t o r   f o r   m o bi l e   r o bo t i c s . "   I n   A ut om a t i on  Sc i e nc e   and  E ng i ne e r i ng  ( C A SE ) ,   20 15  I E E E   I nt e r n at i on al   C o nf e r e nc e   on ,   I E E E ,   2015 ,   pp.   31 0 - 315.     [ 34]   D .   C he n,   L .   Z ha n,   X .   C he n . M o bi l e   r o bo t   pa t pl a nn i ng   ba s e o b e ha v i o ur   i nf o r m a t i o po t e n t i a l   f i e l i unkno w n   e nv i r o nm e nt s .   I P r oc e e di ngs   o f   t he   I E E E   I n t e r na t i ona l   C on f e r e nc e   on  R obot i c s   and  B i om i m e t i c s ,   20 04 ,   pp.   68 3 68 7.   [ 35]   K i m ,   D a e   H w a n ,   G i a ng   H o a ng ,   M i n - J i   B a e ,   J i W o o K i m ,   S uk  M i Y o o n,   T a e - K y e o n g   Y e o ,   H o ng  S up,   a nd   S a ng - B o n g   K i m .   " P a t t r a c ki ng   c o nt r o l   c ov e r a g e   o f   a   m i ni ng   r o bot   ba s e d   o e xh a us t i v e   pa t p l a nni ng   w i t e x a c t   c e l l   de c o m po s i t i o n. "   I C o nt r o l ,   A ut o m a t i o a nd  S y s t e m s   ( I C C A S ) ,   2014  14 t I nt e r n a t i o na l   C o nf e r e nc e   o n,   I E E E ,   2014 ,   pp.   7 30 - 735 .     [ 36]   K l o e t z e r ,   M a r i u s ,   C r i s t i a M a hu l e a ,   a n R a m o G o n z a l e z .   " O pt i m i z i ng   c e l l   de c o m po s i t i o pa t pl a nni ng   f o r   m o bi l e   r o bo t s   us i ng   di f f e r e n t   m e t r i c s . "   I S y s t e m   T he o r y ,   C o nt r o l   a nd   C o m put i ng   ( I C S T C C ) ,   2015  19 t h   I nt e r na t i o na l   C o nf e r e nc e   o n.   I E E E ,   201 5,   pp .   56 5 - 570.   [ 37]   S c he ur e r ,   C hr i s t i a n,   a nd  U w e   E .   Z i m m e r m a n n.   " P a t p l a nni ng   m e t ho f o r   pa l l e t i z i ng   t a s ks   us i ng   w o r ks pa c e   c e l l   de c o m po s i t i o n. "   I n   R obo t i c s   an A ut om at i on ,   201 1I n t e r na t i ona l   C o nf e r e nc e   on   I E E E ,   20 11 ,   p p.   1 - 4.   [ 38]   K ha t i b ,   O us s a m a .   R e a l - t i m e   o bs t a c l e   a v o i da nc e   f o r   m a ni pul a t o r s   a nd  m o bi l e   r o bo t s .   T he   i n t e r nat i o nal   j our na l   of   r obo t i c s   r e s e ar c h.   19 86, v o l .   5 . 1 . pp .   90 - 98.   [ 39]   C he Y B ,   L uo   G C ,   M e i   Y S ,   Y J Q ,   S X L .   U A V   pa t pl a nni ng   us i ng   a r t i f i c i a l   po t e nt i a l   f i e l m e t ho upda t e by   o pt i m a l   c o nt r o l   t h e o r y .   I n t e r na t i o nal   J our nal   o f   Sy s t e m s   Sc i e nc e .   2 016, v o l . 4 7( 6 ) : 1407 - 20.     [ 40]   R a j a   R ,   D u t t a   A ,   V e n ka t e s K S .   N e w   po t e n t i a l   f i e l m e t ho f o r   r o u g t e r r a i pa t p l a nni ng   us i ng   g e ne t i c   a l g o r i t hm   f o r   a   6 - w he e l   r o v e r .   R o bo t i c s   and   A u t on om ous   S y s t e m s .   2015   O c t   1; 72: 295 - 306 .   [ 41]   L o uc he ne ,   A . ,   B o ug ue c ha l ,   N . E . ,   D a hm a n i ,   A . ,   Y a hi a o ui ,   S .   a nd  M e r r o uc hi ,   S . ,   A ut o m a t e g ui de v e h i c l e   pa t h   pl a n ni ng   w i t ho u t   o bs t a c l e s   e x pa n s i o n.   I C o nt r ol   A pp l i c a t i o ns ,   P r oc e e di ng s   o f   t he   19 98  I E E E   I n t e r nat i o nal   C onf e r e nc e . 19 98 ;   V o l .   2 . pp .   133 3 - 1337 .     [ 42]   H o a ng ,   V . D . ,   H e r n a nd e z ,   D . C . ,   H a r i y o no ,   J .   a nd  J o ,   K . H . G l o b a l   p a t pl a nn i ng   f o r   unm a nne g r o und  v e hi c l e   ba s e o r o a m a i m a g e s .   I H um an  Sy s t e m   I n t e r ac t i o ns   ( H SI ) ,   20 14  7 t I nt e r n at i on al   C onf e r e nc e .   I E E E .   2014; pp .   82 - 87 .   [ 43]   H e r m a nn   M ,   P e nt e T ,   O t t o   B .   D e s i g p r i nc i pl e s   f o r   i nd us t r i e   4. s c e na r i o s .   I nSy s t e m   Sc i e nc e s   ( H I C SS) ,     2016   49 t h   H aw ai i   I nt e r na t i ona l   C on f e r e nc e .   I E E E .   2 016;   pp.   3 928 - 3937 .   [ 44]   S a r v a r i   P A ,   U s t un da g   A ,   C e v i kc a E ,   K a y a   I ,   C e bi   S .   T e c hno l o gy   R o a dm a f o r   I ndus t r y   4. 0. M a nag i ng  T he   D i gi t a l   T r an s f or m a t i on .   Spr i n ge r ,   C ham .   2018   ; pp .   9 5 - 103 .     [ 45]   D e bna t h ,   S . K . ,   O m a r ,   R .   a n L a t i p ,   N . B . A . ,   A   R e v i e w   o E ne r g y   E f f i c i e nt   P a t P l a nn i ng   A l go r i t hm s   f o r   U nm a nne d   A i r   V e h i c l e s .   I C om pu t at i o nal   S c i e nc e   a nd   T e c hno l o gy   S pr i nge r ,   Si n gapo r e .   2019;   pp .   523 - 532 .   [ 46]   L a t i p ,   N . B . A . ,   O m a r ,   R .   a nd  D e bna t h ,   S . K . , .   O pt i m a l   P a t P l a nn i ng   us i ng   E qui l a t e r a l   S pa c e s   O r i e nt e V i s i bi l i t y   G r a ph   M e t ho d.   I nt e r n a t i o na l   J o ur na l   o f   E l e c t r i c a l   a nd   C o m put e r   E ng i ne e r i ng   ( I J E C E ) ,   7( 6) ,   pp . 304 6 - 3051 , 20 17.       B I O G R A P H I ES   O F   A U T H O R S           S a nj o y   K um a r   D e bna t i s   a   P hD   s c ho l a r   i F a c ul t y   of   E l e c t r i c a l   &   E l e c t r o n i c   E ng i ne e r i ng   i t h e   U ni v e r s i t i   T un  H u s s e i O nn  M a l a y s i a   (U T H M ).   H e   r e c e i v e h i s   M a s t e r s   o f   E ng i ne e r i ng   f r o m   U ni v e r s i t i T e kno l o g i   M a l a y s i a   i n   201 4.   H e   j o i n e a   r e s e a r c o O pt i m a l   E ne r g y   E f f i c i e nt   P a t h   P l a n ni ng   f o r   a U nm a nne d   A i r   V e h i c l e   (U A V )   i O bs t a c l e - R i c E n v i r o nm e nt   i 2 015  a t   U T H M   unde r   t he   O f f i c e   o f   R e s e a r c h ,   I nno v a t i o n,   C o m m e r c i a l i z a t i o n,   a nd  C o ns u l t a nc y   M a na g e m e nt   (O RICC)             D r . R o s l i   O m a r   c u r r e nt l y   i s   D e a a t   f a c ul t y   o f   E l e c t r i c a l   a nd   E l e c t r o ni c   E ng i ne e r i ng ,   U n i v e r s i t i   T un  H us s e i O nn   M a l a y s i a .   H e   r e c e i v e h i s   P hD   i e ng i n e e r i ng   f r o m   U ni v e r s i t y   of   L e i c e s t e r ,   U ni t e K i ng do m   i 2012.   H i s   r e s e a r c i nt e r e s t s   a r e   i r o bo t i c   e ng i ne e r i ng ,   a u t o no m o us   s y s t e m   a nd  s y s t e m   i de n t i f i c a t i o n.         N o r   B a da r i y a A bdul   L a t i p,   r e c e i v e he r   ba c he l o r   o f   E l e c t r o ni c   E ng i ne e r i ng   f r om   U ni v e r s i t i   T un  H us s e i O nn  M a l a y s i a   ( U T H M )   i 2 015 .   H e r   r e s e a r c i n t e r e s t s   a r e   i r o bo t i c   pa t p l a nn i ng ,   c o nt r o l   s y s t e m   a nd  m e di c a l   e l e c t r o ni c .   I 2018,   s he   f i n i s h e h e r   m a s t e r   o f   E l e c t r i c a l   E ng i ne e r i ng   f r o m   U T H M .       Evaluation Warning : The document was created with Spire.PDF for Python.