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 .   18 ,   N o .   3 J u n e   20 20 ,   pp .   16 46 ~ 16 56   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 8 .i 3 . pp 164 6 - 16 56             1646       Jou r n al   h o m e pa ge ht t p: / / i j e e c s . i a e s c or e . c om   Op e r a t i v e C r i t i c a l P o i n t B u g   a l g o r i t h m - l o c a l   p a t h   p l a n n i n g   o f   m o b i l e   r o b o t   a v o i d i n g   o b st a c l e s       S u b i r   K u m ar   D as 1 ,   A jo K u m ar   D u tta 2 ,   S u b i r   K u m ar   D e b n ath 3   1 D e p ar t m e n t   o f   C o m put e r   A ppl i c a t i o n,   A s a n s o l   E ng i ne e r i ng   C o l l e g e ,   I ndi a     2 , 3 D e pa r t m e n t   o f   P r o duc t i o E ng i n e e r i ng ,   J a da v pu r   U n i v e r s i t y ,   I ndi 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 S e p   7 ,   20 19   R e v i s e N o v   9 ,   2019   A c c e pt e N o v   23 ,   201 9       F o r   A ut o n o m o us   M o bi l e   R o bo t   o ne   o f   t he   bi g g e s t   a nd  i n t e r e s t i ng   i s s ue s   i s   pa t p l a n ni ng .   A a ut o no m o us   m o bi l e   r o bo t   s ho ul be   a bl e   de t e r m i ne   i t s   o w pa t t o   r e a c d e s t i na t i o n.   T hi s   p a pe r   o f f e r s   a   n e w   a l g o r i t hm   f o r   m o bi l e   r o bo t   t o   pl a a   pa t i l o c a l   e nv i r o nm e n t s   w i t s t a t i o na r y   a s   w e l l   a s   m o v i n o bs t a c l e s .   F o r   m o v a bl e   r o bo t s   pa t p l a nn i ng   O pe r a t i v e C r i t i c a l P o i nt B ug   ( O C P B )   a l g o r i t hm ,   i s   a   n e w   B ug   a l g o r i t hm .   T h i s   a l g o r i t hm   i s   c a r r i e o ut   by   t he   r o bo t   t hr o ug ho ut   t he   m o v e m e nt   f r o m   s o ur c e   t o   g o a l ,   he nc e   a l l o w i ng   t he   r o bo t   t o   r e c t i f y   i t s   w a y   i f   a   ne w   o bs t a c l e   c o m e s   i nt o   t he   r o ut e   o r   a ny   e xi s t i ng   o bs t a c l e   c ha ng e s   i t s   r o ut e .   A c c o r di ng   a s ,   no t   o nl y   t he   r o bo t   t r i e s   t o   a vo i d   c l a s w i t o t he r   o bs t a c l e   bu t   a l s o   t r i e s   a   s e r i e s   o f   r un  t i m e   a d j u s t m e nt   i i t s   w a y   t o   pr o duc e   r o ug hl y   a   be s t   po s s i b l e   p a t h .   D u r i ng   j o ur ne y   t he   r o bo t   i s   be l i e v e t o   be   c a p a bl e   t o   a c t   i a un kno w l o c a t i o by   a c qui r i ng   i nf o r m a t i o pe r c e i v e l o c a l l y .   U s i ng   t hi s   a l g o r i t hm   t he   r o bo t   c a a v o i d   o bs t a c l e   by   c o ns i de r i ng   i t s   o w a s   w e l l   a s   t he   o bs t a c l e s   d i m e ns i o n.     T he   o bs t a c l e   m a y   be   s t a t i c   o r   dy na m i c .   T he   a l g o r i t hm   be l o ng s   t o   b u g   f a m i l y .   Ke y w or ds :   A ut o n o m o us   m o b i l e   r o b o t   B ug  a l go r i t hm   Cri t i c a l   po i n t   O b s t a c l e   a v o i da n c e   O pe n   po i nt   P a t pl a nn i ng   C opy r i gh t   ©   2020   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 :   S ub i r   K u m a D a s   D e pa rt m e n t   o f   Co m put e A ppl i c a t i o n   A s a n s o l   E n g i n e e r i ng  Co l l e ge ,     A s a n s o l ,   W e s t   B e n ga l ,   I ndi a .   E m a i l s :   s ub i r k r d a s @ gm a i l . c o m       1.   I N TR O D U C TI O N     A ut o n o m o us   M o b i l e   Robo t   i s   a   m a c hi n e   w hi c h a s   t h e   c a pa b i l i t y   t o   n a v i g a t e   i n   a   c o m pl e e n v i r o n m e n t   w i t h o ut   t h e   r e qu i r e m e n t   a n y   ki n d   o f   s upe r v i s i o n   f r o m   a n y   de v i c e   o r   h um a n   b e i n g.   R obo t   pa t pl a nni n i s   t h e   t a s o de t e r m i ni n c o l l i s i o n - f r e e   pa t h   du ri n a   r o b o t   t ra v e l s   f r o m   a n   i ni t i a l   po s i t i o n   t o   a   de s t i na t i o n   po s i t i o n   i n   a n   u n k n o w n   o r   pa rt i a l l y   kn o w n   l o c a l i t y   t o   a c c o m pl i s h   i t s   o bj e c t i v e .   T h i s   t a s i n v o l v e s   a   s e r i e s   o f   c o m put a t i o n   t o   ge n e ra t e   a   n o n   c o l l i di ng  p a t h.   T o   a c c o m pl i s h   f ul l y   i n de pe n de n t   n a v i ga t i ng  p a t pl a nni n i s   t h e   o n e   of   t h e   m a j o r   c r i t e r i a   f o r   m o b i l e   r o bo t s .   It   i n c l ude s   s e a r c hi n a   ge o m e t r i c   pa t h   f r o m   t h e   o r i gi l o c a t i o n   o f   t h e   r o b o t   t o   t h e   de s t i na t i o n .     W h i l e   di s c us s i n a b o ut   pa t h   p l a nni n g   t h e   p r o pe rt y   of   e n v i ro n m e n t   o r   t h e   l o c a l i t y   w h e r e   t h e   r o b o t   w i l l   w o r i s   a n   i m po r t a n t   i s s ue .   D e pe n d i n o n   t h e   e n v i r o nm e n t   pa t h   pl a nni n c a n   b e   c a t e go r i e s   i n   t w o   t y p e :   1)  S t a t i c   e n v i r o nm e n t     w h e r e   t h e   ob s t a c l e s   a r e   s t a t i c   o r   w h a t   w e   c a n   s a y   t h e   w h o l e   e n v i r o nm e n t   i s   s t a t i c   i n   na t u r e   a nd  2)  D y n a m i c   e n v i r o nm e nt     t h e   e n v i r o nm e nt   i s   dy na m i c ,   m e a n s   t h e   o b j e c t   i n   t h e   e n v i r o n m e n t   m a y   b e   s t a t i c   o r   m a y   be   d y n a m i c .   I n   t h i s   dy n a m i c   e n v i r o n m e n t   pa t h   p l a nni n c o m e s   i n   t w o   fo r m   a G l o b a l   pa t pl a nni n   w h e r e   t h e   i n f o r m a t i o n   a b o ut   t h e   e n v i r o n m e n t   i s   kn o w n   t o   r o bo t   b e fo r e   i t   s t a r t s   m o v i n a n b L oc a l   pa t h   p l a nni n g     w h e r e   t h e   r o b o t   doe s n ’t   ha v e   a n y   i n f o r m a t i o r e ga r d i n t h e   e n v i r o nm e n t .   T h i s   i s   s e n s o r y   b a s e pa t h   p l a nni n w h e r e   t h e   r o bo t   us e s   s e n s o r s   t o   g e t   i n f o r m a t i o n   a b o ut   t h e   o b s t a c l e s   t o   a vo i i s   a n r e a c de s t i na t i o n.     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       O pe r at i v e Cr i t i c a l P oi n t B ug   a l gor i t hm     l oc a l   p at h   pl anni ng  of   m ob i l e   r o bot   av oi d i ng…   ( Sub i r   Kum ar   D as )   1647   Mo v i n g   o b s t a c l e   a vo i da n c e   a t   a n y   t i m e   c o m e s   u n de d y n a m i c   p a t pl a nn i ng  [ 1 - 3] .   A rt i f i c i a l   P o t e n t i a l   F i e l d   i s   o n e   o f   t h e   w i de l y   us e t e c h ni que s   t o   a v o i ob s t a c l e   i n   dy n a m i c   e n v i r o n m e n t   [4,   5].     T h e r e   a r e   m a n y   t e c h n i que s   gi v e n   by   m a n y   r e s e a r c h e r s   t o   a v o i d y n a m i c   ob s t a c l e   a n p l a n   a   n e w   pa t h .   M d .   A ra f a t   H os s a i n   a n Is ra t   F e r do us   i n t r o duc e b a c t e r i a l   f o r a g i n t e c hni que   f o r   pa t pl a nn i ng  [6] .   D o n gs h e n Z h o u,   L a W a n g   a nd  Q i a n g   Z ha n g   ga v e   a i de a   o f   ob s t a c l e   a v o i da n c e   us i n a n t   c o l o n y   a l go ri t hm   [ 7].     In  m a n y   c a s e s   of   pa t h   p l a nni n g   t h e   u l t i m a t e   t ra j e c t o r y   m a y   n o t   r e m a i s a m e   a s   p l a nn e d .   T h e   f i n a l   p a t de fo r m s   w h i l e   ge n e r a t i n t h e   t ra j e c t o r y   [8].   T h i s   h a ppe n s   due   t m a n y   r e a s o n s   s uc h   a s   e rr o r   i n   c a l c ul a t i o n   o di m e n s i o n s   o f   r o b o t   i t s e l f   a n o b s t a c l e s .   D uri n na v i ga t i o i t   i s   n e c e s s a r y   t o   c o n s i de t h e   di m e n s i o n s   o f   t h e   r o b o t   a s   w e l l   t h e   o b s t a c l e s ,   pa r t i c ul a rl y   w h e n   t h e   f un c t i o ni n do m a i n   o f   t h e   r o b o t   i s   c o m pl e x.   R ob e r t   L .   W i l l i a m s   II  a n J i a nhua W g a v e   a n   i de a   o f   D y n a m i c   O b s t a c l e   A v o i da n c e   fo r   a O m ni   d i r e c t i o na l   M o b i l e   Ro bo t   c o n s i de ri n t h e   di m e n s i o n s   [9] .   I n s t e a o f   o bs t a c l e   a v o i da n c e   M u h a nna d   M uj a h e e t .   a l .   us e s   c o l l i s i o n   a v o i da n c e   a pp r o a c h   us i n ga na v i ga t i o n   [10] .   H ow   t pl a n   m o t i o n   fo r   d y n a m i c   o bs t a c l e s   w i t h   U n c e r t a i M o t i o n   P a t t e rn s   i s   a pp r o a c h e by   G e o r ge s   S .   A o ude   e t .   a l .   [ 11].   A   m o b i l e   r o b o t   m a y   h a v e   s i n g l e   o r   m ul t i p l e   t r a i l s   w i t h   t h e   m a i n   r o b o t   bo d y   (S n a ke   L i ke ).   I n   t h o s e   c a s e s   pa t h   pl a nn i ng  a r e   l i t t l e   b i t   c o m pl e [12 - 14].   A pa r t   f r o m   t h e s e   t h e r e   a r e   f e w   o t h e t e c hni que s   f o r   o b s t a c l e   a v o i da n c e .   F e w   of   t h e m   a r e   c l a s s i c a l   t e c hni que s   o r   a   v a ri a t i o n   o f   e xi s t i n c l a s s i c a l   t e c hni que s   l i ke   E qu i l a t e r a l   S pa c e   O r i e nt e V i s i b i l i t y   G r a p h   (E S O V G [1 5]  e t c   a n f e w   i n n o v a t i v e   l i ke   T D O A   (T i m e   D i f fe r e n c e   of   A rri v a l a l go r i t h m   [1 6]  e t c .   T h e   b ug  a l go r i t hm s     [1 7 - 2 5 ]   a r e   b i o - i n s pi r e d   pa t h   pl a nn i ng  a l go r i t h m .     Cr i t i c a l - P o i nt B ug  A l go r i t hm   [2 2 ]   i s   us e t o   a v o i s t a t i c   o bs t a c l e   i n   dy n a m i c   e n v i r o nm e n t .   F urt h e rm o r e   t hi s   i s   a   p a t h   p l a nni ng  a l go r i t hm   f o r   a   po i n t   r o b o t .   B ut   i r e a l   w o r l a   r o b o t   us e t o   h a v e   di m e n s i o n.   Th is   p a pe r   a t t e m pt s   t o   de v e l o m o r e   t h e   C r i t i c a l - P o i n t B ug  A l go ri t hm   [2 2 i t h e   s a i a r e a .   In  t hi s   pa pe r,   t h e   p r o po s e s c h e m e   t r i e s   t o   ke e t h e   r o b o t   a w a y   f r o m   b o t h   f i xe a n dy n a m i c   ob s t a c l e s .   T h e   b ug  a l go ri t hm   i s   a   m o di f i c a t i o o f   e xi s t i n C ri t i c a l - P o i n t B ug  A l go r i t h m   fo r   pa t p l a nni n g   i d y n a m i c   s i t ua t i o n   f o r   a   r o b o t   h a v i n g   di m e n s i o n.   T h e   p r o j e c t e a l go r i t h m   i s   na m e a s   O pe r a t i v e Cri t i c a l P o i nt B ug  (O CP B ).   U s i n t hi s   a l go ri t hm   a   r o b o t   c a n   r e a c h   t o   a   pa r t i c ul a de s t i na t i o n   po i n t   a v o i di n a n y   m ov i n a n s t a t i o n a r y   ob s t a c l e s   c o n s i de r i n i t s   ow n   di m e n s i o n   a s   a   c o n s t ra i nt   w i t h   a n   a i m   t o   l e s s e n   t h e   di s t a n c e   t ra v e l   a n d   t i m e   t o   a rri v e   a t   t a rge t .         2.     P R O P O S ED   M ETH O D     T h e   B ug  a l go r i t hm s   a r e   v e r y   w e l l   kn o w n ,   a b s o l ut e   a n s i m pl e   a l go r i t hm s   us e i n   l o c a l   pa t h   pl a nni n a n m o b i l e   r o bo t   n a v i g a t i o n   w i t h   m i n i m u m   s e n s o rs .   T o   a c c o m pl i s i t s   go a l   t h e   r o bo t   us e s   a s   l i t t l e   gl o b a l   i n f o r m a t i o a s   po s s i b l e .   T h e   m a i l o gi c   i s   v e r y   s i m p l e :   1.   m o v e   t ow a r ds   go a l   u nt i l   a n   o b s t r uc t i o i s   r e v e a l e d.   2.   If   t h e r e   i s   ob s t r uc t i o n   t h e n   c o n t o u r   t h e   ob s t r uc t i o n   unt i l   go a l   i s   o n c e   m o r e   a c h i e v a b l e .   3.   If  go a l   po i n t   i s   v i s i b l e   m o ve   t ow a r ds   i t   a g a i n.   I n   B ug  f a m i l y   m o r e   t h a n   t w e l ve   di ff e r e n t   b ug  a l go ri t hm s   e xi s t   a n e a c h   a l go r i t h m   o f   w h i c h   c a rri e s   i t s   ow n   c o nn c l udi ng  p r o c e s s .   N a m e s   of   F e w   b ugs   a r e   B ug1,   B ug2,   A l g1,   Al g2,   D i s t B ug,   V i s B ug,   T a n ge n t B ug,   Cl a s s 1 ,   R e v ,   Re v 2,   O n e B ug,   L e a v e B ug,   P o i n t B ug ,   K - B ug,   C ri t i c a l - P o i n t B ug  e t c .           F i gu r e   1 .   T r a j e c t o r i e s   f o r m e by   di f fe r e nt   B ug  A l go ri t hm   w i t h   r e f e r e n c e   t o   l i t e r a t u r e   [ 22]   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 .   18 ,   N o .   3 J u n e   20 2 :     1 6 4 6   -   1 6 5 6   1648   T h e   C r i t i c a l P o i nt B ug  a l go r i t h m   a l w a y s   a vo i ds   ob s t a c l e s   by   f i n di ng  a nd  m o v i n t o   a   po i nt   w hi c i s   c l o s e r   t o   go a l   po i nt   t ha n   o t h e r s   a n t h us   gi v e s   us   a n   o pt i m a l   p a t h.   T h e   t r a j e c t o r i e s   of   Cr i t i c a l P o i nt B ug  a n d   o t h e b ug  a l go r i t hm   i s   s h o w n   i n   F i g u r e   1 .   I t   i s   c l e a r   f r o m   t he   f i gur e   t h a t   h o w   t h i s   a l go r i t h m   p e r f o r m s   b e t t e t h a o t h e e xi s t i ng  b ug  a l go ri t hm s .   T h o ug t hi s   i s   a e ff i c i e nt   a l go ri t hm   b ut   c o n s i s t s   o f   s o m e   dr a w b a c a l s o .     T h e   a l go r i t h m   a s s um e s   r o bo t   a s   po i n t   r o b o t .   B ut   i r e a l   w o r l a   r o b o t   m a y   be   2D   o r   3D   b ut   m us t   ha v e   di m e n s i o n.   It   i s   l o c a l   pa t h   pl a nni ng  i n   p r e s e n c e   of  ob s t a c l e s   w h i c h   a r e   s t a t i c   i n   na t u r e .   Cu rr e n t l y   pr o po s e d   a t t e m pt s   t o   de v e l o t h e   a l go r i t h m   a nd  c o n s i de r s   a   r o b o t   w i t h   di m e n s i o n .   T h e   a l go r i t h m   i s   o n   l o c a l   pa t pl a nni n a v o i di n s t a t i c   a s   w e l l   a s   m o v i n ob s t a c l e s .   T h e   a l go r i t hm   i s   a l s o   de ve l o p e f r o m   M o di f i e dCr i t i c a l P o i n t B ug  a l go ri t hm   w h i c h   c a b e   us e t o   a v o i dy n a m i c   o b s t a c l e   b ut   t h e   r o b o t   i s   po i nt   r o b o t .   T h e   O pe r a t i v e Cr i t i c a l P o i nt B us   a l go r i t hm   us e s   r e fe r e n c e   f r o m   [2 2 t o   f i n t h e   s ub  go a l   p o i n t s   a nd  c r i t i c a l   po i n t   f o r   a v o i di n g   o b s t a c l e s   a n d   m o ve   t o   t h e   n e xt   po i nt   t o   r e a c a t   go a l .     2. 1 .      O p e r ati v e C r i t i c a l - P o i n tB u A l go r i th m   T h e   a l go r i t hm   i s   s uppo s e t o   c a rr y   o ut   o n   a   r o bo t   na m e A c t i v i t y   Bo t .   T h e   A c t i v i t y - B o t   i s     a   c o m pa c t ,   z i ppy   r o bo t   w h i c h   c o n s i s t s   o f   a   m u l t i - c o r e   P r o p e l l e r   m i c r o c o n t r o l l e r   a l o n w i t h   g r e a t   ha r dw a r e .   F i g u r e   2.   s h o w s   t h e   r o b o t   a n F i g u r e   3.   S h o w s   t h e   h o w   a   r a n ge   s e n s o r   de t e c t s   a n   o b s t a c l e .   T h e   r o b o t   s c a n s   t h e   l o c a l i t y   t o   n o t i c e   t h e   p r e s e n c e   o f   a n y   o bs t a c l e .     H e r e   w e   a r e   c o n s i de ri n t h e   r o bo t   i n   a   2D   pl a n e   f o r   s i m u l a t i o n   pu r po s e .   L e t   us   a s s um e   a   un b o un de s pa c e   Q     R 2   t h a t   c o n t a i n s   a   s e t   o f   bo un de s t a t i o n a r y   a nd  m o v i n o b s t a c l e s   O   =   { O 1 ,O 2 ,   .   .   . , O K } .     W e   c o n s i de r   t h e   r o bo t   i n   r e c t a n gul a r   s ha pe   w i t w h e e l   a n d   o t h e r   e qui p m e nt   a s   s h o w n   i n   F i g u r e   4 .   A s   pe gl o b a l   f r a m e   o f   r e f e r e n c e   t h e   r o b o t   kn o w s   i t s   i ni t i a l   c o o r di na t e s .   B e fo r e   go i n i n   t o   t h e   f ul l   di s c us s i o n   o f   t h e   a l go ri t hm s ,   w e   c o n s i de r   f e w   e s s e n t i a l   a nd  h e l pf ul   a s s u m pt i o n   a n de s c ri pt i o n   f o r   t hi s   a l go r i t h m   w h i c h   a r e   r e f e r e n c e f r o m   [2 2 ].   F i g u re   s h o w s   h ow   ob s t a c l e s   a r e   de t e c t e by   s e n s o r .   T h e   o bs t a c l e s   a r e   O 1 , O 2 , O 3 , O 4 O 5 .   T h e   o b s t a c l e s   i de n t i f i e by   t h e   s e n s o r   a r e   s h o w n   us i ng  b l a c l i n e s .   T h e   o pe n   po i n t s   a r e   t h e   f i ni s h i ng  po i n t s   o f   e a c h   b l a c l i n e .             F i gu r e   2 .   P a ra l l a a c t i v i t y   bo t                 F i gu r e   3 .   W o r k i n g   p r i n c i pl e   o f   ul t ra s o n i c   ra n ge   s e n s o r           F i gu r e   4 .   D i s p l a y   of   r o b o t   a nd  o b s t a c l e s   i n   2D   pl o t       F i gu r e   5 .   O b s t a c l e s   de t e c t e by   R a n ge   s e n s o r   (R )   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       O pe r at i v e Cr i t i c a l P oi n t B ug   a l gor i t hm     l oc a l   p at h   pl anni ng  of   m ob i l e   r o bot   av oi d i ng…   ( Sub i r   Kum ar   D as )   1649   2. 1 .   A s s u m p ti o n s   A 1.   W o r l c o - o r di na t e   s y s t e m   i s   us e d   A 2.   A l l   po i nt s   ( i n c l ud i n s o u r c e   a n d   de s t i na t i o n )   a r e   a t   f i r s t   qua d ra n t   A 3.   T h e   v e l o c i t y   a n d   a n g ul a r   v e l o c i t y   of   r o bo t   i s   c o n s t a n t   i e v e r y   m ove m e n t   a n d   r o t a t i o r e s pe c t i v e l y   A 4.   S ur f a c e   i s   s m o o t h   a n d   i s a m e   a l t i t ude   A 5.   T h e   m o b i l e   r o bo t   t r a v e l   i n   a   t w o - di m e n s i o na l   a r e a   a n d   r o t a t e s   w i t h o ut   s l i p pi n g   A 6.   Bo t h   t h e   r o b o t   a n d   dy n a m i c   o b s t a c l e s   a r e   ru n   i n   c o n s t a nt   s p e e a nd  i s t ra i g h t   l i n e .   If   a n y o n e   w a n t s   t o   c h a nge   di r e c t i o n   i t   h a s   t o   s t o t h e t u rn  t h e n   a ga i s t a rt   m o v i n g     2. 1 .   Es s e n t i al   D e f i n i ti o n s   W e   c o n s i de r   o n   b o un de o u n b o un de s p a c e   O   a n d   Q   a t   s o m e   s t a ge   i a n y   r e a di n g   f r o m   ra n ge   s e n s o r   w i t hi n   a   t i m e   pe r i o d,   t n   t o   t n + 1   i f   i t   de t e c t s   t h e   di ff e r e n c e   Δd  i n   r a n ge   a t   a n y   p o i n t   t h e n   t h a t   po i nt   i s   c o n s i de r e a s   O pe n   P o i n t   w h e r e   Δd  i s   de f i n e d.   T h e   r o bo t   s c a n s   t h e   s urr o u n d i n gs   0 0   t o   360 0   by   r a n ge   s e n s o r.   T h e   pri m a r i l y   t h e   r o bo t   f a c i n di r e c t l y   t go a l   po i n t   a n d   a f t e r w a r i t   b e gi n s   s c a nni n f o r   o pe n   po i n t .   D e pe n di n o n   t h e   c o o r di na t e   o f   o pe n   po i nt   s ub   go a l   po i n t   i s   c a l c ul a t e d.   T h e   s ub   go a l   po i n t   s i t u a t e s   a t   a   s pe c i f i c   di s t a n c e   f r o m   t h e   o pe n   po i n t   a n po s s i b l y   m a ke s   a   pe r pe ndi c ul a r   a t   o pe n   po i nt   t o   t h e   l i n e   j o i ni n t h e   s e n s o r   po i nt   a n o pe n   po i nt .   T h i s   s ub   go a l   po i n t   i s   i n t e r m e di a r y   t a r ge t   o f   t h e   r o bo t   t o   r e a c h   a t   f i n a l   t a r ge t .   F r o m   a   s e t   o f   s u b   go a l   po i nt s   t h e   r o b o t   c h oo s e s   o n e   po i n t   f o r   n e xt   m o v e   w h i c h   i s   c a l l e c ri t i c a l   po i nt .   T h e   r o b o t   t r i e s   t o   m o ve   i t s   c e n t e r   o v i r t ua l   c i r c l e   t o   c r i t i c a l   po i nt .   T hi s   po i n t   i s   c h o s e n   o n   t h e   b a s i s   of  m i ni m um   di s t a n c e   f r o m   t h e   de s t i n a t i o n   a n d   y e t   n o t   v i s i t e d.     W e   pl o t   t h e   r o bo t   a n d   t h e   o b s t a c l e   i n   2D   pl a n e   a n a s s um e   a   v i r t u a l   c i r c l e   s u rr o undi n g   t h e   r o b o t .   Ce n t r e   o f   t h e   v i rt ua l   c i r c l e   i s   l o c a t e a t   t h e   m i dpo i n t   o f   t h e   t w o   f a r t h e s t   po i nt s   o f   t h e   r o b o t   a nd  t h e   r a d i us   i s   ha l f   b e t w e e n   t h e   t w o   f a r t h e s t   po i nt s   o f   t h e   r o bo t +   w h e r e     i s   a   s a f e t y   c o n s t a nt .   T h e   m i ni m u m   v a l ue   o f     c a n   b e   o b t a i n e f r o m   f e w   n u m b e r   o f   e xpe r i m e n t s .   F i g u r e   s how s   t h e   p l o t t i n g   a nd  o t h e r e qui r e d   ge o m e t ri c a l   de t a i l s .       P e r pe n di c ul a r   di s t a n c e   o f   ob s t a c l e   f r o m   t h e   s e n s o r     L o c a t i o o f   r o bo t   w h e e l - ‘a xl e ’  (i m a g i n a r y   l i n e c e n t e r     D i s t a n c e   f r o m   s e n s o t o   o pe po i n t     D i s t a n c e   b e t w e e n   w h e e l - ‘a x l e ’  c e nt e a nd  w h e e l   c e n t e r     D i s t a n c e   b e t w e e n   t h e   r e a r   e n d   a nd  w h e e l   a x l e ’  c e n t e     D i s t a n c e   b e t w e e n   t h e   w h e e l   a xl e ’  c e n t e r   a n d   t h e   r e a r   e nd  o f   t h e   r o b o t     Ce nt e r   o f   t h e   v i rt ua l   c i r c l e   α     O pe po i n t   de t e c t i o a ngl e   by   t h e   s e n s o r     -   S a f e t y   c o n s t a nt   f o r   t h e   r o b o t     R a d i o us   o f   t h e   v i r t u a l   c i r c l e   β    S e n s o r   di r e c t i o n   a n g l e   a t   o pe n   po i nt   w i t h   r e s pe c t   t o   t h e   l i n e   pa ra l l e l   t o   x - a x i s   a n pa s s i ng  t hr o ug h   (x i ,y i b e fo r e   m o v e m e n t   θ    A ngl e   ge n e r a t e by   β   w i t r e s pe c t   t o   t h e   l i n e   p a ra l l e l   t o   x - a xi s   f o r   s ub   go a l   po i nt   c o o r di n a t e s   c a l c ul a t i o n     A n g l e   c r e a t e o n   a   l i n e   pa ra l l e l   t o   a xi s   a n d   p a s s i n g   t hr o ug h   s e n s o r   b y   a   l i n e   f r o m   s e n s o r   t o   o pe n   po i n t         A n gl e   b e t w e e n   l i n e   j o i n i n o pe n   po i n t   &   s ub go a l   a n d   t h e   l i n e   pa r a l l e l   t o   x - a xi s   a nd  pa s s i ng  t hr o ug h   o pe n   po i n t   d k     D i s t a n c e   o f   a   s ub   go a l   po i nt   f r o m   c u rr e n t   l o c a t i o n   x s   a n d   y   a r e   t h e   s i g n   f a c t o r s   us e i de t e r m i na t i o n   o f   t h e   c o o r di na t e s   o f   o pe n   po i nt s   s x   a n s y     a r e   t h e   s i g n   f a c t o r s   us e t o   de t e r m i n e   t h e   c o o r di n a t e s   o f   s u b   go a l   po i n t s   W e   c o n s i de r ,   T =   { (x 1 ,y 1 ), (x 2 ,y 2 ), . . . , (x i ,y i )}   a s   a   s e t   po i nt s   na v i ga t e d   by   t h e   r o b o t   w h e r e   ( x i ,y i s y m bo l i z e   t h e   c oo r di na t e   v a l ue s   O P = { ((α a ,d a ), b ,d b )) , . . . . , ((α k ,d k ) , j ,d j ))}   a s   a   s e t   o s ubs e q ue n t   o pe n   po i nt s   o ob s t a c l e s   i de n t i f i e by   t h e   s e n s o r   w h e r e   α  a n d   s y m bo l i z e   t h e   a n gl e s   &   di s t a n c e s   of   ope n   po i n t s   r e s pe c t i v e l y   f r o m   t h e   r o bo t   a n e a c h   ((α a ,d a ) , b ,d b ))  r e p r e s e nt s   o pe n   po i nt s   c o nn e c t e t o   e a c h   o b s t a c l e ,   i f   o n l y   o n e   po i n t   i s   de t e c t e t h e n   α a a n d   d a =d b   S G =   { (a i ,b i ), …. . , (x j ,y j )}   a s   a   s e t   of   s u b   go a l   po i n t s   o f   obs t a c l e s   i de nt i f i e by   t h e   r o b o t   a n e a c h   ( a i ,b i r e p r e s e n t s   s ub   go a l   po i nt   w hi c t h e   c a n   c h o o s e   f o r   n e xt   m o ve   T obs =   { (( a i ,b i ), …(a j ,b j )), . . , ((x i ,y i ), . . , (x j ,y j ))}   a s   a   s e t   of  pr o v i s i o n a l y   i de n t i f i e ob s t a c l e s   w h e r e   e a c h   ( (a i ,b i ), …(a j ,b j ))  a r e   t h e   s e t   o f   po i nt s   o f   e a c h   o b s t a c l e .   S obs =   { ((a i ,b i ), …(a j ,b j )), …. . , ((x i ,y i ), . . , (x j ,y j ))}   a s   a   s e t   of   s t a t i o n a r y   ob s t a c l e s   w h e r e   e a c h   ((a i ,b i ), …( a j ,b j ))  a r e   t h e   s e t   o f   po i n t s   o f   e v e r y   s t a t i o na r y   ob s t a c l e .   TD obs =   { ( (a i ,b i ), …( a j ,b j )), …. . , (( x i ,y i ), . . , (x j ,y j ))}   a s   a   s e t   of  pr o v i s i o n a l y   d y n a m i c   o bs t a c l e s   w h e r e   e a c h   ((a i ,b i ), …(a j ,b j ))  a r e   t h e   s e t   o f   po i nt s   o f   e a c h   t e m po ra r y   d y n a m i c   o b s t a c l e .   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 .   18 ,   N o .   3 J u n e   20 2 :     1 6 4 6   -   1 6 5 6   1650   D obs =   { ((a i ,b i ), …(a j ,b j )), …. . , ((x i ,y i ), . . , (x j ,y j ))}   a s   a   s e t   of   m o vi n o b s t a c l e s   w h e r e   e a c h   ((a i ,b i ), …( a j ,b j ))  a r e   t h e   s e t   o f   po i n t s   o f   e a c h   m o v i n o b s t a c l e .   D =   { ((x a ,y a ), δ a ) , …, ((x j ,y j ), δ j )}   a s   a   s e t   of   s u b   go a l   po i n t s   a nd  di s t a n c e   f r o m   t a rge t   o f   t h a t   po i nt   w h e r e   e a c h   s e t   ((x a ,y a ), δ a r e p r e s e n t s   t h e   s e t   o f   s ub   go a l   po i n t   a n t h e i di s t a n c e   f r o m   t a rge t   H e r e   d m i n   i s   t h e   di s t a n c e   f r o m   t h e   r o b o t   t o   go a l   po i n t   a nd    i s   t h e   d i r e c t i o o f   t h e   s a m e .   P C   i s   t h e   po s i t i o n   w h e r e   t h e   r o b o t   m a y   c o l l i de   w i t h   t h e   o bs t a c l e   a n t h e   di s t a n c e   f r o m   c urr e nt   po s i t i o n   o r o b o t   t o   t h e   po i nt   o f   c o l l i s i o n   i s   D C .   In   C a r t e s i a n   s pa c e   w e   c a n   r e p r e s e n t   t h e   r o b o t   s t a t e   a s   q= [x,   y ,   ,   v ,   t ] T ,   w h e r e   (x,   y a r e   t h e   c oo r di n a t e   o f   c e n t r e ,   r o b o t ’s   a n g ul a r   v e l o c i t y ,   t h e   s pe e o f   t he   m o b i l e   r o b o t   i s   v   a n d   t   i s   t h e   t i m e .       2. 1 .   A l go r i th m   M A IN   P r o c e dur e   1.   Ro bo t   S t a r t   2.   T a ke   i n pu t   o f   t h e   po s i t i o n   c o - o r di na t e s   o f   s o ur c e   a n d   de s t i na t i o n   3.   Ca l c ul a t e   t h e   d i s t a n c e   a n di r e c t i o f r o m   s o ur c e   t o   de s t i na t i o d m i n   a n d     r e s pe c t i v e l y   4.   W H I L E   n o t   D e s t i na t i o n   5.     S t a r t   O B S T A CL E _D E T E CT IO N   p r o c e dur e   i F O V   6.   IF   o b s t a c l e   o r   v i rt ua l   o b s t a c l e   i di r e c t i o n   7.   Ca l c ul a t e   t h e   c oo r di n a t e s   of  s u b   g o a l s   f r o m   O P ,   d o n ’t   c a l c ul a t e   s a m e   s e t   f r o m   O P   t w i c e   a n s a v e   i t   i s e t   S G   a nd  D   8.   Ca l c ul a t e   d i s t a n c e   o f   e a c h   s ub   go a l   f r o m   de s t i na t i o n   a n d   s a v e   i t   i s e t   D   9.   S e l e c t   t h e   c o o r di na t e   po i nt   P   h a v i n g   t h e   l o w e s t   di s t a n c e   i D   10.   IF   t h e   po i nt   e xi s t s   i T r a v e r s e   po i n t   s e t   T   11.   D i s c a r d   t h e   po i n t   12.   S e l e c t   t h e   n e x t   l o w e s t   di s t a n c e   po i nt   P   f r o m   D   13.   F o l l ow   s t e 10   14.   E L S E     15.   IF   P   i s   S A F E _P O IN T   16.   S a v e   t h e   c o o r di na t e   i t r a v e r s e   po i n t   s e t   T   17.   Ca l c ul a t e   a n g l e   o f   r o t a t i o a n d   r o t a t e   18.   M ov e   t ow a r ds   t h e   c ri t i c a l   po i n t   19.   Ca l c ul a t e   d i r e c t i o   a nd  d i s t a n c e   d m i n   20.   E N D IF   21.   E N D IF   22.   E L S E     23.   Ca l c ul a t e   t h e   n e xt   po i n t   c o o r di n a t e   P   t o w a r ds   t h e   di r e c t i o   24.   IF   P   i s   S A F E _P O IN T   25.     S a v e   t h e   c o o r di na t e   i T   26.     M ov e   t o   P   27.     Ca l c ul a t e   n e w   d m i n   28.   E N D   IF   29.   E N D   IF   30.   E N D   W H IL E   31.   Ro bo t   S t o p     O B S T A CL E _D E T E CT IO N   P r o c e dur e   1.   Ide n t i fy   ob s t a c l e s   i F O V   2.   Ca l c ul a t e   t h e   c o o r di n a t e s   o f   o p e n   po i n t s   a nd  s a v e   t h o s e   po i nt s   i s e t   T obs   3.   F O R   a n y   c oo r di n a t e   i T obs   4.     IF   c oo r di na t e   s e t   o f   T o b s   e xi s t s   i S o b s     5.       D i s c a r d   t h e   c o o r di na t e   f r o m   T o b s   6.     E L S E   7.       IF   t h e r e   e xi s t s   a n y   n e a r e s t   po i n t   i S obs   w i t   s m a l l   c ha n ge   i x   o y   v a l ue   8.     T h e   o b s t a c l e   m a y   be   d y n a m i c   9.     S a v e   c oo r di na t e   i T D o b s   10.     E L S E     11.     IF   t h e r e   e xi s t s   a n y   n e a r e s t   po i n t   i T D obs     w i t s m a l l   c h a n ge   i o r   y   v a l ue   12.     It   i s   p a r t   o f   m o v i n o b s t a c l e   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       O pe r at i v e Cr i t i c a l P oi n t B ug   a l gor i t hm     l oc a l   p at h   pl anni ng  of   m ob i l e   r o bot   av oi d i ng…   ( Sub i r   Kum ar   D as )   1651   13.     S a v e   t h e   po i nt s   o f   T D obs   a nd  T o b s   t o   t h e   r o b o t   r e gi s t r y   a n d   a l l   t h e   o pe n   po i nt s   o f     t h e   ob s t a c l e     i n   D obs   14.     E L S E   15.     S a v e   t h e   po i nt s   i S o b s   16.     R E T U R N   ob s t a c l e   17.     E N D   IF   18.     E N D   IF   19.     E N D   IF     20.   E N D   F O R   21.   IF   o b s t a c l e   d y n a m i c   22.     Ca l c ul a t e   d i r e c t i o   a n s pe e v obs   o f   t h e   o b s t a c l e     f r o m   t h e   po i nt s   e xi s t s   i r o b o t   r e gi s t r y     23.     IF   t h e   o b s t a c l e   di r e c t i o   i nt e r s e c t i ng  r o b o t     di r e c t i o   24.     Ca l c ul a t e   p r o b a b l e   po s i t i o n   P C   o f   c o l l i s i o n   25.     Ca l c ul a t e   p r o b a b l e   di s t a n c e   D C   f r o m   t h e     r o b o t   t o   P C   26.     IF   D C <d m i n   27.     Ca l c ul a t e   t h e   t i m e   R TC   a n O TC   bo t h   t h e   r o b o t   a n o b s t a c l e   w i l l   t a ke   t o   r e a c h   a t   D C     r e s pe c t i v e l y   28.     IF   R TC =O TC   29.     Ide n t i fy   t h e   po i nt   P C   a nd  a l l   t h e     a dj a c e n t   po i n t s   o f   t h e   o b s t a c l e   a s   v i r t u a l   O b s t a c l e   30.       Ca l c ul a t e   t h e   o pe po i n t s   a n d   s a v e   i n   O P   31.       R E T U R N   v i r t u a l   o b s t a c l e   32.     E N D IF   33.     E N D   IF   34.     E N D   IF   35.   E N D   IF     S A F E _P O IN T   P R O CE D U R E   1.   IF   P   c o rr e s po n ds   t o   a   s ub   s ub   s e t   o f   O P   2.     S e l e c t   t h e   s ub   s e t   f r o m   O P   t ha t   c o r r e s po n ds   t o   P   3.     IF   i t   i s   f i r s t   s ub   s e t   4.     S e l e c t   t h e   s e c o n s ub   s e t   f r o m   p r e v i o us   s e t   f r o m   O P   5.     E L S E   6.     S e l e c t   t h e   f i r s t   s ub   s e t   f r o m   n e xt   s e t   f r o m   O P   7.     E N D   IF   8.     Ca l c ul a t e   t h e   d i s t a n c e   S d   b e t w e e n   t w o   s ub   s e t s   9.   E L S E   10.     S e l e c t   t h e   t w o   po i n t s   f r o m   O P   ha v i n m i ni m um   d i s t a n c e   f r o m   P   11.     Ca l c ul a t e   t h e   d i s t a n c e   S d   b e t w e e n   t w o   po i n t s   12.   E N D   IF   13.   IF   S >   2 r   14.       R E T U R N   s a f e   15.   E L S E     16.     R E T U R N   n o t   s a f e   17.   E N D IF       3.   DISCUSSIO AND  RE SUL T     T h e   f o r e m o s t   pur po s e   of   t h e   a l go ri t hm   i s   t o   p r o duc e   a n   u n i nt e rr u pt e p a t h   f r o m   i ni t i a l   t o   e n d   po i n t s   a n t h e s e   po i n t s   r e m a i n   f i xe fo r   a n y   pa r t i c ul a r   c a s e .   W h e n   t h e   m o b i l e   r o bo t   s t a r t s   t o   t r a v e r s e   t hr o ug h   t h e   e n v i r o n m e n t ,   i t   w i l l   s t a rt   b e a ri n i n   m i nd  u n i de n t i f i e s t a t i o n a r y   obs t a c l e s .   T h e   ge n e r a l   o b s e r v a t i o n   o a v o i di n g   a u ni de n t i f i e s t a t i o na r y   ob s t a c l e   a s   pe [22 i s   s how n   i F i g u r e   1.   T h i s   a l go ri t hm   t ri e s   t o   a v o i d y n a m i c   o b s t a c l e   a l s o .   N o t   o n l y   t h a t   u nl i ke   a l go ri t hm   o f   [22]  a n i t s   n e xt   o t h e r   a l go ri t hm   t hi s   a l go r i t h m   c o n s i de r s   t h e   r o b o t   a s   a   w h o l e   bo d y   n o t   a   po i n t   r o b o t   a n t h e n   a v o i t h e   ob s t a c l e s   us i n g   s a f e t y   pr e c a ut i o n .   F i g u r e   6   s h o w s   h ow   a   r o bo t   c a b e   c o n s i de r e u n de r   a   v i r t u a l   c i r c l e   f o r   ob s t a c l e   a v o i da n c e .   F i g u r e   s h o w s   t h e   o pe n   po i nt s   a nd  i t s   a s s o c i a t e   s ub   go a l   po i nt s .   F ig u r e   r e f l e c t s   h o w   t h e   r o bo t   i s   c a l c ul a t i n v a l ue   o f   a   s ob   go a l   po i nt   us i n f o rm ul a .   A l l   t h e   s ub   go a l s   s i t u a t e   a t   a   di s t a n c e   of  v i r t u a l   c i r c l e s   r a d i us   f r o m   t h e   o pe n   po i nt   a nd  a t   pe rpe n d i c ul a rl y   o ppos i t e   di r e c t i o n   o f   t h e   l i n e   j o i ni n t h e   s e n s o r   po i n t   a n d   a s s o c i a t e o pe po i nt .       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 .   18 ,   N o .   3 J u n e   20 2 :     1 6 4 6   -   1 6 5 6   1652   3. 1 .       A n a l ys i s   o A l go r i th m   E v e r y   ob s t a c l e ,   i t   m a y   be   d y n a m i c   o r   s t a t i c ,   b ut   i s   s t a t i c   a t   a   p a r t i c ul a po i n t   o f   t i m e .   A f t e r   s m a l l   t i m e   t ,   i f   t h e   po s i t i o n   o f   a o b s t a c l e   r e m a i n s   s a m e   t h e n   i t   i s   s t a t i c   o t h e r w i s e   d y n a m i c .   A n t i c i pa t i n g   t h e   pr o b a b l e   po s i t i o n   o f   c o n t a c t   w i t h   dy n a m i c   o b s t a c l e   f r o m   i t s   di r e c t i o n   a n d   s pe e a n t h e n   us i ng  p r o pe r   a c t i o fo r   a v o i da n c e   i s   n e c e s s a r y   i n   d y n a m i c   e n v i r o nm e nt .   F i g ure   9   a n F i g u r e   10   e xpl a i n s   h o w   w e   c a n   a v o i d   d y n a m i c   o b s t a c l e s   us i n t h i s   a l go ri t hm   b y   e s t i m a t i ng  t h e   v i r t ua l   o b s t a c l e   po s i t i o n .   L e t   a n   o pe po i n t   i s   de t e c t e by   s e n s o r   a t   a n gl e   α.   A s   pe r   [22 ]     β i ( α  i - 1 ) % 360   ( 1)       (2)             F i gu r e   6 .   W h o l e   r o bo t   i n s i de   t h e   v i r t u a l   c i r c l e   w i t s a f e t y   m e a s ur e m e n t         F i gu r e   7 .   O b s t a c l e s ’  O pe n   po i nt   a n d   S ub   go a l   P o i n t   de t e c t e by   r obo t       H e r e   (x i ,y i i s   t h e   c oo r di na t e   o f   s e n s o r   a n ( x i + 1 , j ,y i + 1 , j i s   t h e   c oo r di n a t e   of   j t h   de t e c t e d,   o n e   of   n e xt   o pe n   p o i n t s   a t   (i + 1) t h   i t e r a t i o n   a n a c c o r di n t o   w o r l ds   c oo r di n a t e   Ca l c ul a t i o n   o o pe n   po i n t   a nd  i t s   s ub   g o a l   po i n t   s y s t e m .   T h e   o pe n   po i n t   c o m e s   i t w o   w a y s .   1.   If   pr e vi o us   v a l ue   of   α,   t h e   s e n s o a n g l e   α  - de t e c t s   a ob s t a c l e   a n 2 .   N e xt   v a l ue   o f   α,   t h e   s e n s o r   a n g l e   α+ de t e c t s   ob s t a c l e   o r   - i s   n o t   a n   o b s t a c l e .   S o   t h e   c a s e s   a r e   o bs t a c l e   t o   o p e n   po i n t   a n o pe n   po i n t   t o   o bs t a c l e .   E a c of   t h e   c a s e s   a l s o   ha v e   t w o   s u b   c a s e s   a n t h o s e   a r e :   a   >   90 0   a nd  b   < =   90 0       w h e r e   = % 180 °   (3)           F i gu r e   8 .   O pe po i nt   t o   S ub   go a l   po i nt   c a l c ul a t i o n   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       O pe r at i v e Cr i t i c a l P oi n t B ug   a l gor i t hm     l oc a l   p at h   pl anni ng  of   m ob i l e   r o bot   av oi d i ng…   ( Sub i r   Kum ar   D as )   1653       F i gu r e   9 .   A v o i di n a   m o v i n g   o b s t a c l e   pe r pe ndi c ul a r   di r e c t i o t o   t h e   m o b i l e   r o b o t       F i gu r e   10 .   A v o i di n g   a   m o v i n g   o b s t a c l e   i n   o ppo s i t e   di r e c t i o t o   t h e   m o b i l e   r o b o t       S o   w e   c a n   de f i n e     a s   f o l l ow s ,     = { 90° , Sx =   1 , Sy =   1           if   > 90°         1   n o t   o bst a c l e 90° , Sx = 1 , Sy = 1         if     > 90°       1   is   o bst a c l e       90° , Sx = 1 , Sy = 1             if   90°     1   n o t   o bst a c l e 90° , Sx = 1 , Sy = 1               if     90°   1   is   o bst a c l e                 (4)     A c c o r di n g   t o   F i g u r e   8   i f   (x i + 1 , j ,y i + 1 , j i s   o pe po i nt   P   t h e n,   a s s o c i a t e   s ub   go a l   po i n t   Q   i s :      =  +  .     =  +  .  }   (5)     A f t e r   ge n e r a t i n t h e   n e xt   c o o r di n a t e   po i n t   t o   m o v e   t h e   v i r t u a l   c i r c l e ’s   c e n t r e ,   t h e   w h e e l   a xe l   c e n t r e   of   t h e   r o bo t   w i l l   t u rn   a n s t a r t   m o v i n t o w a r ds   t h a t   po i n t .   A c c o r di n t o   F i g u r e   A   i s   t h e   w h e e l   a xe l   c e n t r e .   Q   s h o ul b e   t h e   n e x t   v i rt u a l   c i r c l e   c e n t r e .   If   (A x, A y be   t h e   n e xt   c o o r di na t e   o f   w h e e l   a xe l   c e n t r e   A   a n A C   i s   t h e   di s t a n c e   b e t w e e n   w h e e l   a xe l   c e n t r e   a nd  v i r t u a l   c i r c l e   c e nt r e   t h e n,      =  +  .   =  +  .    }   (6)     N ow   t h e   r o b o t   w i l l   c a l c ul a t e   t h e   a ngl e   t o   r o t a t e   t o   t h e   n e xt   c oo r di n a t e   f r o m   c urr e n t   c o o r di n a t e   of  w h e e l   a xe l   c e nt r e   a nd  t h e m o ve   di r e c t l y .   U s i n g   t h e   s t a t e d   m e t h o t h e   r o bo t   w i l l   s a f e l y   a v o i s t a t i c   o b s t a c l e s .   B ut   i n   c a s e   of   d y n a m i c   ob s t a c l e s   i s   h a s   de t e r m i n e   t h e   s pe e of   t h e   r u nni n o b s t a c l e   by   c a pt u r i ng  t h e   l o c a t i o n   of   t w o   di f fe r e nt   t i m e   t n + 1   a n d   t n   w h e r e   t = t n + 1 - t n .   T h e r e f o r e ,       v obs = ( O t + 1 O t ) t   (7)     w h e r e   O t + 1 ,O t   a n v obs   a r e   O b s t a c l e   l o c a t i o n s   a t   m o m e n t   t n + 1   a n d   t n   a nd  s pe e of   t h e   r u nni n g   o b s t a c l e   r e s pe c t i v e l y .   S i n c e   t h e   di r e c t i o n   o f   ob s t a c l e   a n r o b o t   f i xe (a s   pe r   A 7)  s o   t h e   c a l c ul a t i ng  t h e   c o n f l i c t i ng  po i n t   (P C i s   po s s i b l e .   T h e   a l go r i t hm   w i l l   c o n s i de t h e   a r e a   o f   pr o b a b l e   c o l l i s i o n   a s   a   v i r t u a l   o b s t a c l e .   If  P R ( rx n + 1 , r y n + 1 )   b e   pr e s e nt   l o c a t i o o f   t h e   r o b o t   a t   t n + 1 .   T h e n,     D C = ( Cx rx n + 1 ) 2 + ( Cy ry n + 1 ) 2   (8)     W h e r e   (Cx , Cy i s   t h e   c o o r di na t e   v a l ue   o f   P C .   U s i n v a l ue   o f   D C   t h e n   r o b o t   t h e de t e r m i n e s ,     R TC = D C v   (9)     O TC = D C v obs   (10)   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 .   18 ,   N o .   3 J u n e   20 2 :     1 6 4 6   -   1 6 5 6   1654   T h e   v e l oc i t y   of   r o bo t   i s   v .   R TC   a n d   O TC   a r e   t h e   t i m e   t h e   r o bo t   a n d   r u nni n g   o b s t a c l e   w i l l   t a ke   t o   a rri v e   a t   c o l l i d i n g   po i nt   r e s pe c t i v e l y .   R TC   a n O TC   e qua l   m e a n s   t he y   w i l l   t a ke   s a m e   t i m e   t o   r e a c a t   s a m e   po i n t   P C   i n   n e a f ut u r e .   S o   t h e   po i n t   w i l l   b e   de n o t e a s   v i rt ua l   o b s t a c l e   a n c h a nge t ra j e c t o r y   w i l l   b e   fo r m e w i t s a f e t y   pr e c a ut i o n   a s   s h o w n   i n   F i g u r e   11   by   t h e   r o bo t   f r o m   c urr e nt   po s i t i o n   t o   t h e   t a r ge t   a s   pe r   a l go ri t hm ,   t hr o ugh  t h e   de v i a t i o n   po i n t   a s   s h o w n   i n   F i g u r e   5 .   S na ps h o t s   o f   t r a j e c t o r y   us i n O pe r a t i v e Cri t i c a l P o i n t B ug  a l go ri t hm   o f   a   c o un t e r pa rt   o f   a c t i v i t y   bo t   o n   2D   p l a n e   a s   s h o w n   i F i gu r e   12 .           F i gu r e   11 .   O b s t a c l e   a v o i da n c e   w i t h   s a f e t y   m e a s ur e m e n t           F i gu r e   12 .   S na ps h o t s   o f   t ra j e c t o r y   us i ng  O pe r a t i v e Cri t i c a l P o i nt B ug  a l go ri t hm   o f   a   c o unt e rpa rt   o f   a c t i v i t y   bo t   o n   2D   pl a n e       3. 2 .       To tal   T i m e   A n d   P ath   Le n gth   C al c u l ati o n   If   v i   a n d   i   a r e   t h e   s pe e a n d   a ngul a r   v e l o c i t y   a t   i t h   i t e ra t i o n   t h e n,   t i m e   t a ke i m o v i n g   a nd    r o t a t i n g   [20 ]:     = = 0     = = 0       S o   t h e   c o s t   f un c t i o i t e r m s   o f   t i m e   i s :     = ( + ) = 0 +  = 0     W h e r e   D O T   i s   t h e   t i m e   t a ke t o   de t e c t   m o v i n g   o b s t a c l e   a n d   i t s   di r e c t i o n   o f   m o v e m e n t   a nd  s pe e d   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       O pe r at i v e Cr i t i c a l P oi n t B ug   a l gor i t hm     l oc a l   p at h   pl anni ng  of   m ob i l e   r o bot   av oi d i ng…   ( Sub i r   Kum ar   D as )   1655   3. 3 .       S i m u l ati o n   R e s u l ts   T h e   F i g u r e   12  s h o w s   t h e   s i m ul a t i o n   m o de l   o f   t h e   O pe ra t i v e Cri t i c a l P o i nt b u a l go ri t hm   a nd  h o w   i t   a v o i ds   s t a t i c   a s   m o v i ng  o b s t a c l e .   T h e r e   a r e   e i g ht   d i f f e r e nt   s na s h o t s   o f   di ff e r e n t   m o m e nt s .   T h e   r e c t a ngu l a s ha pe g ra y   c o l o ur e o b j e c t   i s   m o v i n o b s t a c l e   a n d   g r e e n   re c t a n g ul a o b j e c t s   a r e   s t a t i c   o b s t a c l e s .     T h e   a l go r i t hm   i s   m o de l l e us i ng  P y t h o n   3 . 5   o n   w i n do w s   7   pl a t f o rm .   I nt e l   c o r e   i 3 - 23 50 @ 2 . 3 G hz   L a p t o w i t h   G B   R A M   i s   us e d.   T h e   o r a nge   c i r c l e   a t   t he   t o a nd  r e d   c i r c l e   a t   t h e   f o o t   a r e   t h e   t a rge t   a n s o u r c e   po i nt s   r e s pe c t i v e l y .   T h e   d m i n   i s   s h o w by   r e l i n e .   B l a c k   l i n e   i s   t h e   p a t t h e   r o b o t   t r a v e r s e t hr o ug h.       4.   C O N C LU S I O N S   A N D   F U TU R E   W O R K   T h i s   p a pe r   i s   a   c o n t i n u a t i o n   o f   i t s   t w o   pr e v i o us   w o r ks .   T h e   m a i n   o b j e c t i v e   i s   b ui l di n a   s i m p l e   s e n s o r   b a s e a l go r i t hm   o n   l o c a l   pa t h   p l a nni n g .   T h e   a l go r i t h m   t ri e s   t o   c o n s i de r   t h e   c o n s t ra i nt s   o r o bo t s   di m e n s i o n.   U s i n t h i s   b ug  a l go r i t h m   v e r y   l i t t l e   p ri o i n f o r m a t i o n   i s   r e qui r e f o r   t h e   r o bo t   t o   c o m pl e t e   t a s k.   T h e   s a f e t y   po i n t   c a l c ul a t i o n   m a ke s   t h e   a l go ri t hm   m o r e   e f f i c i e n t .   It   h e l ps   t h e   r o bo t   t o   pa s s   t hr o ugh   s m a l l   ga p   a s   w e l l   a l s o   t o   a v o i t h e   ga p   w h i c i s   t o o   s m a l l   t o   pa s s   t hr o ug h .   If   t h e   e n v i r o n m e n t   i s   n o t   m uc c o m pl e o t h e   num b e r   o f   ob s t a c l e   i s   ve r y   fe w ,   t h e t hi s   a l go r i t hm   a nd   o t h e r   e xi s t i ng  a l go ri t hm   m a y   t a ke   a l m o s t   s a m e   t i m e .   F e w   f a vo r a b l e   po i n t s   o f   t hi s   a l go ri t hm   a r e :   ( a o t h e t h a t h o s e   w h i c h   m a y   c a us e   c o l l i s i o n,   i t   n e v e r   c o n s i de r s   t h e   e nt i r e   o b s t a c l e s   fo r   a v o i da n c e .   (b U s e s   e ff i c i e n t   t e c hn i q ue   t o   c a l c ul a t e   c oo r di na t e s   o po i n t s .   (c T h e   a l go r i t h m   r e qu i r e s   o n l y   s o ur c e   a n de s t i na t i o n   c o o r di n a t e s   t o   c o m pl e t e   t a s k.   (d)   N um b e r   o f   i t e r a t i o n   i s   l e s s   t o   r e a c h   t h e   go a l I n   t h e   f ut u r e ,   t h e   a l go r i t h m   w i l l   b e   us e fo r   r e a l   t e s t .   F u r t h e r   i t   w i l l   b e   s t udi e o n   pa t pl a nni n g   o s n a ke   l i ke   r o b o t   a n d   pa t h   pl a nni ng  o f   m ul t i pl e   r o bo t s   i n   o n e   e n v i r o nm e n t .       A C K N O WL ED G E M EN T   T h a nk  y o t o   P r o duc t i o n   E n g i n e e r i ng  D e pa r t m e nt ,   J a da v p ur   U ni v e r s i t y   a n A s a n s o l   E n g i n e e r i ng  Co l l e ge   fo r   g i v i ng  us   t h e   o ppo rt u n i t y   t o   us e   t h e i r e s o ur c e s .       R EF ER EN C ES   [ 1]   C r uz ,   V .   M u i i o z ,   A .   G a r c i a . C e r e z o ,   A .   O l l e r o ,   M o v i ng   O bs t a c l e   A   V o i da nc e   A l g o r i t hm   F o r   M o bi l e   R o bo t s   U nd e r   S pe e d   R e s t r i c t i o ns ,   I F A C   I nt e l l i ge nt   C om pone nt s   f o r   V e h i c l e s ,   19 98,   pp .   205     21 0   [ 2]   H a o j i e   Z ha ng ,   G ua ng m i ng   X i o ng ,   B o   S u,   J i a nw e i   G o ng , Y a J i a ng ,   H ui y a C he a nd  W e i   L a n,   A n y t i m e   P a t P l a n ni ng   i n   G r a dua t e S t a t e   S p a c e ,   I E E E   I n t e l l i ge nt   V e hi c l e s   Sy m pos i um   ( I V ) ,   2 013 ,   pp .   3 58     362   [ 3]   J ung he e   P a r k ,   J e o ng   S .   C ho i ,   J i m i n   K i n ,   a nd  B e o m   H .   L e e ,   M o v i ng  O bs t ac l e   A v oi danc e   f or   M ob i l e   R obot ,   I E E E   I nt e r na t i o na l   C o nf e r e nc e   o C o n t r o l   a nd   A ut o m a t i o n ,   2 009 ,   3 67    3 72   [ 4]   Z hi h a o   X u,   R o bi H e s s ,   K l a u s   S c hi l l i ng ,   C ons t r a i n t s   o f   P ot e nt i al   F i e l f or   O b s t ac l e   A v oi d anc e   on  C a r - l i k e   M ob i l e   R obo t s ,   I F A C   C o n f e r e nc e   o E m be dde S y s t e m s ,   C o m put a t i o na l   I nt e l l i g e nc e   a nd  T e l e m a t i c s   i C o nt r o l     C E S C I T ,   2012 ,   169     175   [ 5]   N i c M a l o ne ,   H a o - T i e C h i a ng ,   K e n dr a   L e s s e r ,   M e e ko   O i s h i ,   L y di a   T a p i a ,   H y br i D y na m i c   M o v i ng   O bs t a c l e   A vo i da nc e   U s i ng   a   S t o c ha s t i c   R e a c ha b l e   S e t - B a s e P o t e nt i a l   F i e l d” ,   I E E E   T r a ns a c t i on s   on  R o bot i c s ,   v o l .   33 ( 5) ,   2017 ,   1124 - 11 38   [ 6]   M d .   A r a f a t   H o s s a i n ,   I s r a t   F e r do us ,   A ut o no m o us   r o bo t   pa t p l a nni ng   i dy na m i c   e nv i r o nm e n t   us i ng   a   n e w   o pt i m i z a t i o t e c hn i que   i ns pi r e by   ba c t e r i a l   f o r a g i ng   t e c hni qu e ,   R obot i c s   a nd  A u t onom ous   S y s t e m s   64 ,   201 5,   137 1 41   [ 7]   D o ng s he ng   Z ho u,   L a W a ng ,   Q i a ng   Z ha ng ,   O bs t a c l e   a v o i da nc e   p l a nn i ng   o f   s pa c e   m a ni pul a t o r   e n d - e f f e c t o r   ba s e d   o i m pr o v e a nt   c o l o n y   a l g o r i t hm ,   S pr i ng e r P l u s   ( 201 6)   5 ,   509     5 21   [ 8]   H a nna   K u r n i a w a t i ,   T hi e r r y   F r a i c ha r d,   F r om   P at t T r aj e c t or y   D e f or m a t i on ,   I E E E / R S J   I nt e r na t i o na l   C o nf e r e nc e   o I nt e l l i g e nt   R o bo t s   a nd   S y s t e m s ,   20 07,   1 59    164     [ 9]   R o be r t   L . W i l l i a m s   I I ,   J i a nhu a W u,   O bs t a c l e   A vo i da nc e   f o r   a O m ni d i r e c t i o na l   M o bi l e   R o bo t ,   J o ur na l   o f   R obot i c s ,   V o l .   2 010 ,   A r t i c l e   I D   901365   [ 10]   M uh a nna M uj a he d,   D i r F i s c he r ,   B ä r be l   M e r t s c hi ng ,   A dm i s s i bl e   g a p   na v i g a t i o n:   A   ne w   c o l l i s i o a v o i da nc e   a ppr o a c h” ,   R obo t i c s   and   A u t on om ou s   S y s t e m s   1 03,   2 018 ,   93    110     [ 11]   G e o r g e s   S .   A o ude ,   B r a ndo D .   L ude r s ,   J o s hu a   M .   J o s e ph ,   N i c ho l a s   R oy ,   J o na t ha P .   H o w ,   P r o ba bi l i s t i c a l l y   S a f e   M o t i o P l a nn i ng   t o   A vo i D y na m i c   O bs t a c l e s   w i t U nc e r t a i M o t i o P a t t e r n s ,   A ut o no m o us   R o bo t s ,   2013 ,   v o l .   35( 1 ) ,   5 1 - 76   [ 12]   J i C h e ng ,   Y o ng   Z ha ng ,   Z ho ng hua   W a ng ,   M o t i o P l a n ni ng   A l go r i t hm   f o r   T r a c t o r - t r a i l e r   M o bi l e   R o bo t   i U nkno w E nv i r o nm e n t ,   I E E E   I C N C   2 012 ,   1050     10 55     [ 13]   F i l i ppo   S a nf i l i ppo ,   J o A z pi a z u,   G i a nc a r l o   M a r a f i o t i ,   A ks e l   A .   T r a n s e t h,   Ø y v i nd  S t a v da h l   a nd  P ˚ a l   L i l j e a c k,     A   R e v i e w   on  P e r c e pt i on - dr i v e O b s t a c l e - a i de L o c om o t i on  f or   Sn ak e   R obo t s ,   I E E E   I nt e r na t i o na l   C o nf e r e nc e   o C o nt r o l ,   A ut o m a t i o n,   R o bo t i c s   &   V i s i o n,   20 16   [ 14]   A j oy   K um a r   D ut t a ,   S u bi r   K um a r   D e b na t h.   S u bi r   K um a r   D a s   P a t P l a nn i ng   o f   S na ke - L i ke   R o bo t   i P r e s e nc e   of   S t a t i c   O bs t a c l e s   U s i ng   B ug   A l g o r i t hm ,   A dv a nc e s   i C om pu t e r ,   C om m uni c a t i on  and  C o nt r o l ,   S pr i ng e r ,   201 8,   4 49   -   458   Evaluation Warning : The document was created with Spire.PDF for Python.