T E L KO M NIK A In d o n e s i a n  J o u r n a l o f   E le c t r ic a E n g in e e r in g V o l . 1 2 , No .  9 S e p te m b e r  2 0 1 4 , p p . 6 8 0 5 ~ 6 8 1 0 DO I: 1 0 . 1 1 5 9 1 /t e l k o m n i k a .v 1 2 i 9 . 6 2 7 1 6 8 0 5 Re c e i v e d M a y 1 5 2 0 1 4 ; R e v i s e d J u n e  2 0 , 2 0 1 4 ;  A c c e p te d J u l y 6 , 2 0 1 4 A u t o m a t ed   G r o u n d  V eh icle s N a v i g at i o n w it h  G en e t ic A l g o r i t h m A l i r e z a   Re z a e e As s i s t a n t   p ro f e s s o o f   D e p a rt m e n t   o f   s y s t e m   a n d   M e c h a t ro n i c s   En g i n e e ri n g , F a c u l t y   o f   N e w   s c i e n c e s   a n d   t e c h n o l o g i e s ,   U n i v e r s i t y   o f   T e h ra n , P. O . Bo x   1 4 3 9 5 1 3 7 4 ,   T e h ra n , I R AN E - m a i l : a rre z a e e @ u t . a c . i r Ab s t r a c t Au t o m a t e d   g ro u n d   v e h i c l e s   a re   b e i n g   u s e d   i n c re a s i n g l y   i n   a u t o m a t i o n   o f   f a c t o ri e s   f o m a t e ri a l t ra n s m i t t i n g   o o t h e m i s s i o n s .   T h e   n a v i g a t i o n   o f   t h e s e   v e h i c l e s   i s   a   c h a l l e n g e   a s   t h e   c o n f i g u ra t i o n   o f   t h e e n v i r o n m e n t   s u c h   a s   f a c t o ry   c h a n g e s .   T h e   p a t h - p l a n n i n g   p ro b l e m   h a s   b e e n   s h o w n   t o   b e   N P - h a rd ,   t h u s t h i s   p ro b l e m   i s   o f t e n   s o l v e d   u s i n g   h e u ri s t i c   o p t i m i z a t i o n   m e t h o d s   s u c h   a s   g e n e t i c   a l g o r i t h m s .   I n   t h i s   p a p e r a   g e n e t i c   a l g o ri t h m   f o p a t h   p l a n n i n g   o f   t h e   m o b i l e   ro b o t s   s p e c i f i c a l l y   a u t o m a t e d   g ro u n d   v e h i c l e s   w i t h   a b a s i c   k n o w l e d g e   a b o u t   n a v i g a t i o n   a re a   b o u n d a r i e s   a n d   c o n f i g u ra t i o n   o f   o b s t a c l e s .   T h e   g o a l   i n   t h i s   p a p e r i s   t o   t ra v e l   t h e s h o r t e s t   p a t h   i n   m i n i m a l   t i m e   w h i l e   a v o i d i n g   o b s t a c l e s   i n   a   n a v i g a t i o n   e n v i ro n m e n t .   F o t h i s re a s o n ,   a n   e f f e c t i v e   s t r u c t u r e   f o g e n e t i c   a l g o ri t h m   w a s   i m p l e m e n t e d . K e y w o r d s : C o p y r i g h t © 2 0 1 4 I n s ti tu t e   o f   A d v a n c e d   En g i n e e r i n g   a n d   Sc i e n c e .   A l l   r i g h t s r e s e r v e d . 1 . In t r o d u c t io n M o b i l e   r o b o ts   a r e   d e s i r a b l e   f o r   s u r v e i l l a n c e   a n d   o p e r a ti o n s   s u c h   a s   b o m b   d i s p o s a l   o r h a z a r d o u s   m a te r i a l   m a n a g e m e n t,  w h i c h   wo u l d   b e   p o te n t i a l l y   d a n g e r o u s   f o r   h u m a n s K i n d   o f i n d u s tr i a l   m o b i l e   r o b o ts   b e i n g   u s e d   i n   f a c to r y   a u to m a ti o n f o r   m a te r i a l   h a n d l i n g   a r e   a u t o m a te d g r o u n d   v e h i c l e s   ( A G V s ) A n   i m p o r ta n ta s k   f o r   th e s e   v e h i c l e s   i s   a u to n o m o u s   n a v i g a t i o n wh e r e th e   v e h i c l e   tr a v e l s   b e t w e e n   a   s ta r ti n g   p o i n a n d   a   t a r g e p o i n wi th o u th e   n e e d   f o r   h u m a n i n te r v e n ti o n   [ 1 2 ].  W h i l e   b a s i c   i n f o r m a ti o n   m a y   b e   a v a i l a b l e   t o   th e   r o b o t   a b o u t   th e   n a v i g a t i o n a r e a   b o u n d a r i e s u n k n o w n   o b s ta c l e s   m a y   e x i s w i th i n   th e   n a v i g a t i o n   a r e a .   A   p a t h   b e t we e n   th e s ta r ti n g   a n d   t a r g e t   p o i n ts   t h a a v o i d s   c o l l i s i o n s   wi th   o b s ta c l e s   i s   s a i d   t o   b e   f e a s i b l e - th i s   i s   a p a th t h a l i e s   w i th i n   f r e e   s p a c e T h u s r o b o n a v i g a t i o n   m e th o d s   n e e d   to   s o l v e   t h e   p a th - p l a n n i n g p r o b l e m w h i c h   i s   to   g e n e r a te   a   f e a s i b l e   p a th   a n d   o p ti m i z e   th i s   p a t h   wi th   r e s p e c to   c e r ta i n c r i te r i a .   F i g u r e   1   i l l u s tr a te s   a   f e a s i b l e   p a th   i n   a   n a v i g a t i o n   e n v i r o n m e n f r o m   th e   to p   t o   t h e b o tto m . F i g u r e 1 . A  F e a s i b l e   P a th  i n  a N a v i g a ti o n   E n v i r o n m e n t Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 2 3 0 2 - 4 0 4 6 T E L KO M NIK A V o l 1 2 , No . 9 S e p t e m b e r  2 0 1 4 : 6 8 0 5 6 8 1 0 6 8 0 6 T h e   g o a l   f o r   r e a l - ti m e   m o b i l e   r o b o ts   i s   t o   tr a v e l   th e s h o r te s p a t h   i n   m i n i m a l   ti m e   wh i l e a v o i d i n g   o b s ta c l e s   i n   a   n a v i g a t i o n   e n v i r o n m e n t.  A u t o n o m o u s   n a v i g a ti o n   a l l o w s   r o b o ts   to   p l a n th i s   p a t h   wi th o u th e   n e e d   f o r   h u m a n   i n te r v e n t i o n A s   th e   p a t h - p l a n n i n g   p r o b l e m   h a s   b e e n s h o w n   t o   b e   N P - h a r d ,   th i s   p r o b l e m   i s   o f te n   s o l v e d   u s i n g   g e n e ti c   a l g o r i th m A n   i m p o r ta n t   p a r t   o f th e   g e n e t i c   a l g o r i th m   s o l u ti o n   i s   th e   s tr u c tu r e   o f   th e   g e n o t y p e   th a r e p r e s e n t s   p a th s   i n   th e n a v i g a ti o n   e n v i r o n m e n t. T h e  g e n o t y p e  m u s t r e p r e s e n t   a   v a l i d  p a th ,  b u t  s ti l l  b e  s i m p l e  to  p r o c e s s b y   th e   g e n e t i c   a l g o r i th m   i n   o r d e r   to   r e d u c e   c o m p u ta ti o n a l   r e q u i r e m e n ts Un f o r tu n a te l y m a n y c o n te m p o r a r y   g e n e t i c   p a t h - p l a n n i n g   a l g o r i th m s   u s e   c o m p l e x   s tr u c tu r e s   th a r e q u i r e   a   s i g n i f i c a n t a m o u n o f   p r o c e s s i n g ,   wh i c h   c a n   a f f e c th e   r e a l - t i m e   r e s p o n s e   o f   th e   r o b o t.  T h i s   p a p e r d e s c r i b e s   t h e   d e v e l o p m e n o f   a   g e n o t y p e   s tr u c tu r e   th a c o n t a i n s   o n l y   th e   e s s e n t i a l   i n f o r m a ti o n f o r   p a th   p l a n n i n g wh i c h   a l l o w s   f o r   m o r e   e ff i c i e n p r o c e s s i n g T h e   g e n e t i c   a l g o r i t h m   u s i n g   th i s s tr u c tu r e   i s   e v a l u a te d   o n   a   v a r i e t y   o f   n a v i g a ti o n   s p a c e s   a n d   i s   f o u n d   t o   p r o d u c e   v a l i d o b s ta c l e - f r e e  p a th s  f o r  m o s t c a s e s . Ro b o t   p a t h   p l a n n i n g   i s   p a r o f   a   l a r g e r   c l a s s   o f   p r o b l e m s   p e r ta i n i n g   to   s c h e d u l i n g   a n d r o u ti n g a n d   i s   k n o wn   t o   b e   NP - h a r d T h u s a   h e u r i s ti c   o p ti m i z a t i o n   a p p r o a c h   i s   r e c o m m e n d e d [3 ].  O n e o f   th e s e   a p p r o a c h e s   i s   th e   u s e   o f   g e n e ti c   a l g o r i th m s A   g e n e ti c   a l g o r i t h m   ( G A )   i s   a n e v o l u t i o n a r y   p r o b l e m   s o l v i n g   m e th o d w h e r e   th e   s o l u t i o n   to   a   p r o b l e m   e v o l v e s   a f t e r   a   n u m b e r   o f i te r a t i o n s .   A   g e n e t i c   a l g o r i th m   s ta r ts   w i t h   a   p o p u l a t i o n   o f   c h r o m o s o m e s E a c h   c h r o m o s o m e r e p r e s e n ts   a   p o s s i b l e   s o l u ti o n   f o r   a   g i v e n   p r o b l e m F o r   r o b o n a v i g a ti o n a   c h r o m o s o m e   m a y r e p r e s e n t  a   p a t h  b e t w e e n  t h e  s ta r t i n g  a n d  ta r g e t p o i n t s . E a c h  c h r o m o s o m e  i s  a s s i g n e d   a  f i tn e s s v a l u e b a s e d   o n   h o w   we l l   th e   i n d i v i d u a l   m e e ts   th e   p r o b l e m   o b j e c ti v e s Us i n g   th e s e   f i tn e s s v a l u e s i n d i v i d u a l s   a r e   s e l e c te d   to   b e   p a r e n ts T h e s e   p a r e n ts   f o r m   n e w   i n d i v i d u a l s o r   o f fs p r i n g , v i a   c r o s s o v e r   a n d   m u ta ti o n P a r e n s e l e c t i o n c r o s s o v e r   a n d   m u ta ti o n   o p e r a t i o n s   c o n ti n u e   f o r s e v e r a l  g e n e r a t i o n s  u n t i l  th e  a l g o r i t h m  c o n v e r g e s  t o  a n  o p t i m a l  o r  n e a r - o p ti m a l  s o l u t i o n . V a r i o u s   g e n e ti c   a l g o r i th m   m e th o d s   h a v e   b e e n   a p p l i e d   to   th e   r o b o n a v i g a t i o n   p r o b l e m . O n e   a p p r o a c h   i s   to   c o m b i n e   f u z z y   l o g i c   w i th   g e n e ti c   a l g o r i th m s   [4 - 6 ].  I n   t h i s   a p p r o a c h t h e g e n o t y p e   s tr u c tu r e r e p r e s e n ts   f u z z y   r u l e s   th a g u i d e   th e   r o b o n a v i g a t i o n s o   th e   g e n e ti c a l g o r i th m   e v o l v e s   th e   b e s s e o f   r u l e s W h i l e   th i s   a p p r o a c h   c a n   p r o d u c e   a   f e a s i b l e   p a t h   th r o u g h a n   u n c e r t a i n   e n v i r o n m e n t,  th e   g e n o t y p e   s tr u c tu r e   b e c o m e s   v e r y   c o m p l e x a s   i n e e d s   to r e p r e s e n t  a   v a r i e t y   o f  f u z z y  r u l e s .  A n o t h e r   a p p r o a c h   i s   to  u s e  g e n o t y p e  s tr u c tu r e s   th a t  r e p r e s e n t l o c a l   d i s ta n c e   a n d   d i r e c ti o n a s   o p p o s e d   to   r e p r e s e n t i n g   a n   e n ti r e   p a th   [ 7 - 1 0 ] W h i l e   th e s e   a r e s i m p l e   to   p r o c e s s   a n d   a l l o w   f o r   f a s te r   r e a l - ti m e   p e r f o r m a n c e th e   l o c a l   v i e wp o i n o f   th e s e m e th o d s   m a y   n o a l l o w   th e   r o b o to   r e a c h   i ts   ta r g e t S o m e   m e th o d s   h a v e   r e l a ti v e l y   s i m p l e g e n o t y p e   s tr u c tu r e s   th a c a n   r e p r e s e n f e a s i b l e   p a t h s b u r e q u i r e   c o m p l e x   d e c o d e r s   a n d   f i tn e s s f u n c ti o n s   w h i c h  c a n   a f f e c t r e a l - t i m e  r e s p o n s e  [1 1 - 1 3 ]. O u r   r e s e a r c h   i s   f o c u s e d   o n   i m p r o v i n g   th e   g e n e t i c   a l g o r i th m   p e r f o r m a n c e   b y   d e v e l o p i n g a  s i m p l e  a n d  e f f i c i e n t g e n o t y p e  s tr u c tu r e . 2 . G e n e t ic   A lg o r it h m   S t r u c t u r e   F o r   M o b ile   Ro b o t   Na v ig a t io n   P r o b le m G e n o t y p e S t r u c t u r e T h e   m a i n   p o i n i n   s o l v i n g   th e n a v i g a t i o n   p r o b l e m   i s   d e f i n i n g   th e   g e n o t y p e s   s tr u c tu r e   to m a k e   i p o s s i b l e   to   s o l v e   t h e   p r o b l e m   w i th   g e n e ti c   a l g o r i th m   s tr a te g y In   o r d e r   to   s i m p l i f y   th e n a v i g a ti o n   p r o b l e m   a n d   d e f i n i n g   t h e   p a th   wh i c h   t h e   r o b o n e g o ti a te s th e   e n v i r o n m e n o f   th e r o b o i s   c o n v e r te d   t o   r o w s   a n d   c o l u m n s T h e   n a v i g a ti o n   m o d e l   o f   th e   r o b o t   c o u l d   b e   e i th e r   r o w - wi s e  o r  c o l u m n - w i s e . In   r o w - wi s e   n a v i g a t i o n , a s   i l l u s tr a te d   i n   F i g u r e   2 th e   r o b o m o ti o n   s ta r ts   fr o m   o n e   r o w to w a r d   a n o th e r   r o p a s s i n g   r o w s   c o n s e c u t i v e l y .   G i v e n   a   n a v i g a ti o n   e n v i r o n m e n th a i s m o d e l e d   b y   r o w s a   p a t h   i n   th a e n v i r o n m e n i s   r e p r e s e n te d   b y   a   g e n o t y p e   wi th   g e n e s . E a c h   g e n e   p o s i t i o n  c o r r e s p o n d s  t o  a r o w i n d e x ,   w h i l e   e a c h   g e n e   v a l u e  c o r r e s p o n d s  to   a  c o l u m n i n d e x   w i t h i n   th a r o w.  F o r   e x a m p l e th e   { 1 , 7 ,4 , 4 , 5 ,8 ,6 ,2 ,3 ,1 0 }   c h r o m o s o m e   i n F i g u r e   1 , r e p r e s e n ts   a   p a th   th a s ta r ts   i n   r o w   1 c o l u m n   1   ( 1 ,1 )   a n d   e n d s   a r o w   1 0 c o l u m n   1 0   ( 1 0 ,1 0 ) . T h e   i n te r m e d i a t e p o i n ts   o n   th i s   p a th   a r e   ( 2 , 7 ) ( 3 , 4 ) ( 4 ,4 ) ( 5 ,5 ) ( 6 ,8 ) ( 7 ,6 ) ( 8 , 2 ) ,   ( 9 ,3 ) ( 1 0 ,1 0 ) r e s p e c ti v e l y .   F i g u r e   2   s h o ws   th e   n a v i g a t i o n   a l o n g   th i s   p a th   i n   th e   wo r l d   s p a c e ,   w h e r e   p o i n ( 1 , 1 ) i s  a s s u m e d  to  b e   a t th e  to p  l e f t c o r n e r . In   c o l u m n - w i s e   n a v i g a ti o n ,   i n   a   c h r o m o s o m e e a c h   g e n e   p o s i ti o n   c o r r e s p o n d s   to   a c o l u m n   i n d e x w h i l e   e a c h   g e n e   v a l u e   c o r r e s p o n d s   to   a   r o w   i n d e x   w i th i n   t h a t   c o l u m n F o r e x a m p l e th e   { 7 ,5 ,4 ,8 ,1 0 , 6 , 5 ,3 ,7 ,8 }   c h r o m o s o m e   i n F i g u r e   3 r e p r e s e n ts   a   p a th   th a s ta r ts   i n Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 2 3 0 2 - 4 0 4 6 V a r i a b l e - we i g h t  Co m b i n a t i o n P r e d i c ti o n o f T h e r m a l  E r r o r   M o d e l i n g  o n   CNC… ( Z h i m i n g F e n g ) 6 8 0 7 c o l u m n   1 r o w   7   ( 7 ,1 )   a n d   e n d s   a c o l u m n   1 0 r o w   8   ( 8 ,1 0 ) T h e   i n te r m e d i a te   p o i n ts   o n   th i s   p a t h a r e   ( 5 ,2 ) ( 4 , 3 ) ( 8 ,4 ) ( 1 0 , 5 ) ( 6 ,6 ) ( 5 , 7 ) ( 3 ,8 ) ( 7 ,9 ) ,   ( 8 ,1 0 )   r e s p e c t i v e l y F i g u r e   3   s h o w s   t h e n a v i g a ti o n  a l o n g  t h i s  p a th   i n  th e   w o r l d  s p a c e . F i g u r e 2 . R o w - w i s e   N a v i g a t i o n   a n d  Re l a te d Co r o m o s o m e F i g u r e 3 . C o l u m n - wi s e N a v i g a t i o n  a n d  Re l a t e d Co r o m o s o m e T h e   d i r e c ti o n   i n f o r m a ti o n   o f   a   c h r o m o s o m e   r e p r e s e n ts   th e   i n te r m e d i a t e   s te p s   o f   a   p a th . Ho w e v e r s e n d i n g   th e   r o b o o n   a   s tr a i g h l i n e   d i r e c t l y   f r o m   th e   c e n te r   o f   o n e   v e r te x   to   th e   c e n te r o f   th e   n e x v e r t e x   wo u l d   m e a n   th a th e   r o b o m o v e s   o n   a   d i a g o n a l   l i n e a c r o s s   m a n y   a d j a c e n t c e l l s T h i s   w i l l   c a u s e   p r o b l e m s   i f   a n y   a d j a c e n c e l l s   th a th e   r o b o t   tr a v e r s e s   f r o m   o n e   r o w   to   t h e n e x h a v e   a n   o b s t a c l e A   b e tte r   a p p r o a c h   i s   to   s p l i th e   d i a g o n a l   p a th   s e g m e n i n to   a   h o r i z o n t a l s e g m e n t a n d  a  v e r ti c a l  s e g m e n t, w h i c h   w i l l  a l l o w th e  r o b o to  c i r c u m v e n t o b s ta c l e s . A s s u m e   th a w e   h a v e   a   s e g m e n th a s ta r ts   i n   r o w   1 c o l u m n   2   ( d e n o te d   b y   ( 1 ,2 ) )   a n d e n d s   i n   r o w   2 c o l u m n   5   ( 2 ,5 ) If   th e   d i r e c ti o n   b i t   i s   0   ( F i g u r e   4 ) th e n   t h e   p a th   s e g m e n i s   s p l i t i n to   a   v e r t i c a l   s e g m e n f r o m   ( 1 ,2 )   to   ( 2 ,2 )   a n d   a   h o r i z o n ta l   s e g m e n f r o m   ( 2 ,2 )   to   ( 2 ,5 ) Ho w e v e r , i f   th e   d i r e c t i o n   b i i s   1   ( F i g u r e   5 ) th e n   th e   p a th   s e g m e n i s   s p l i i n to   a   h o r i z o n ta l   s e g m e n f r o m ( 1 ,2 )  to   ( 1 , 5 )  a n d  a   v e r t i c a l   s e g m e n t f r o m   ( 1 ,5 )  to   ( 2 ,5 ) . F i g u r e 4 . V e r ti c a l - h o r i z o n t a l D i r e c ti o n F i g u r e 5 . H o r i z o n t a l - v e r ti c a l D i r e c ti o n F o r   c o l u m n - wi s e   o r i e n ta t i o n th e   d i r e c t i o n   b i i s   i n te r p r e te d   a s   f o l l o w s A s s u m e   th a we h a v e   a   c o l u m n - w i s e   p a t h   s e g m e n a s   s h o wn   i n F i g u r e   6 T h e   s e g m e n t s ta r ts   i n   r o w   2 c o l u m n   1 ( 2 ,1 )   a n d   e n d s   i n   r o 5 c o l u m n   2   ( 5 ,2 ) If   th e   d i r e c ti o n   b i i s   1   ( F i g u r e   6 ) t h e n   th e   p a th   s e g m e n t i s   s p l i i n t o   a   v e r ti c a l   s e g m e n f r o m   ( 2 ,1 )   to   ( 5 , 1 ) a n d   a   h o r i z o n ta l   s e g m e n f r o m   ( 5 ,1 )   t o   ( 5 , 2 ) . Co n v e r s e l y i f   th e   d i r e c t i o n b i t   i s   0   ( F i g u r e   7 ) t h e n   th e   p a t h   s e g m e n i s   s p l i i n t o   a   h o r i z o n ta l s e g m e n t f r o m   ( 2 ,1 )  to   ( 2 ,2 )   a n d   a  v e r ti c a l  s e g m e n t f r o m   ( 2 ,2 )  to   ( 5 ,2 ) . F i g u r e 6 . V e r ti c a l - h o r i z o n t a l D i r e c ti o n F i g u r e 7 . H o r i z o n t a l - v e r ti c a l D i r e c ti o n Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 2 3 0 2 - 4 0 4 6 T E L KO M NIK A V o l 1 2 , No . 9 S e p t e m b e r  2 0 1 4 : 6 8 0 5 6 8 1 0 6 8 0 8 T h e r e f o r e a   d i r e c ti o n   b i i s   a d d e d   to   th e   c h r o m o s o m e   s tr u c tu r e   to   i n d i c a t e   t h e   f i r s t d i r e c ti o n  t h a t t h e  r o b o wi l l  t u r n  to   p r o c e e d  to  t h e   n e x v e r te x . 2 .1 . C r o s s o v e r  a n d  M u t a t i o n In   o u r   G A t wo   p a r e n c h r o m o s o m e s   a r e   c o m b i n e d   a p p l y i n g   a   s i n g l e - c r o s s - p o i n t,   v a l u e e n c o d i n g   c r o s s o v e r T h e   c r o s s o v e r   o p e r a to r   p r o d u c e s   two   o f f s p r i n g   c h r o m o s o m e s   w i t h   e a c h c r o s s o v e r   o p e r a t i o n Du r i n g   th e   o p e r a ti o n   o f   r e p r o d u c ti o n c r o s s o v e r   i s   a p p l i e d   o n   th e   c h o s e n p a r e n t   c h r o m o s o m e s   o n l y   wi th i n   th e   c r o s s o v e r   p r o b a b i l i t y I n   t h e   c h o s e n   c r o s s o v e r   o p e r a to r , two   p a r e n c h r o m o s o m e s   a r e   c o m b i n e d   a p p l y i n g   a   s i n g l e - c r o s s - p o i n t,  v a l u e e n c o d i n g   c r o s s o v e r . T h e   c r o s s o v e r   o p e r a t o r   h a s   b e e n   m o d i f i e d   to   p r o d u c e   t w o   o f f s p r i n g   c h r o m o s o m e s   w i t h   e a c h c r o s s o v e r   o p e r a ti o n T h i s   i s   a c h i e v e d   b y   u s i n g   th e   g e n e   i n f o r m a ti o n w h i c h   w e r e   n o u s e d   to b u i l d   o f f s p r i n g  o n e i n   o r d e r  to  b u i l d  a  s e c o n d  c h r o m o s o m e . T h e   c h o s e n   m u ta ti o n   o p e r a to r   c h e c k s   w i t h   a   m u ta ti o n   p r o b a b i l i t y   f o r   e v e r y   s i n g l e   g e n e wh e th e r   i s h o u l d   b e   m u ta te d   o r   n o t If   a   g e n e   i s   to   b e m u ta te d a   r a n d o m   n u m b e r   b e t we e n   1 a n d   th e   to t a l   n u m b e r   o f   c o l u m n s   i n   t h e   s e a r c h   s p a c e   i s   a s s i g n e d   to   l o c a ti o n   a n d   a   r a n d o m d i r e c ti o n e i t h e r   v e r ti c a l   o r   h o r i z o n ta l i s   a s s i g n e d   to   d i r e c ti o n T h i s   m u ta ti o n   v a r i a n t   h a s   t h e a d v a n t a g e   th a i g i v e s   th e   o p p o r t u n i t y   f o r   a   c h r o m o s o m e   to   b e c o m e   s i g n i f i c a n tl y   a l t e r e d T h a t m e a n s   th a th e   c o m p l e te   s e a r c h   s p a c e   w i l l   b e   e x p l o r e d   a n d   i t h e r e f o r e   p r e v e n t s   th e   G A   f r o m g e tt i n g  s t u c k  i n  a  l o c a l  o p ti m u m . 2 .2 . F it n e s s   E v a lu a t io n E a c h   c h r o m o s o m e   r e p r e s e n ts   a   p a th   i n   th e   w o r l d   s p a c e Re c a l l   th a t   th e   g o a l   f o r a u to n o m o u s   r o b o t   n a v i g a t i o n   i s   to   d e te r m i n e   th e   s h o r te s f e a s i b l e   p a t h   a n d   tr a v e r s e   th i s   p a t h   i n m i n i m a l   ti m e A   p a th   i s   e v a l u a te d   b y   e x a m i n i n g   i ts   s e g m e n ts . T h e   to ta l   p a th   l e n g t h   i s   th e   s u m   o f i ts   s e g m e n ts If   a   s e g m e n t i n te r s e c ts   a n   o b s ta c l e th e n   th i s   i s   c a l l e d   a n   i n f e a s i b l e   s te p T h u s a p a th   i s   o b s ta c l e - f r e e   o n l y   i f   a l l   o f   i ts   s te p s   a r e   f e a s i b l e M i n i m i z i n g   p a th   l e n g th   wi l l   m i n i m i z e tr a v e l  t i m e ; h o w e v e r , s o   wi l l  m i n i m i z e  t h e  n u m b e r  o f  tu r n s  r e q u i r e d  t o  tr a v e r s e  th i s   p a th . G i v e n   t h e s e   c r i te r i a o u r   f i t n e s s   f u n c ti o n   m u s c o n s i d e r   f e a s i b i l i t y ,   l e n g t h a n d   n u m b e r   o f tu r n s   a s   th e   f i tn e s s   f a c to r s T h e   f i tn e s s   f u n c ti o n   F   i s   s h o w n   i n   E q ( 1 )   wh i c h   i n c l u d e s   S   a s   th e n u m b e r   o f   i n f e a s i b l e   s te p s   i n   th e   c h r o m o s o m e L   a s   th e   to ta l   l e n g t h o f   th e   p a th   s e g m e n ts   a n d   T a s   th e   t o ta l   n u m b e r   o f   tu r n s . f K , L K a n d T K a r e   we i g h ts   f o r   fe a s i b i l i t y l e n g th a n d   n u m b e r o f   tu r n s r e s p e c ti v e l y A f te r   th e   f i tn e s s   v a l u e   f o r   a l l   c h r o m o s o m e s   i n   th e   p o p u l a ti o n   h a v e   b e e n c o m p u te d R a n k   S e l e c ti o n   i s   u s e d   t o   d e te r m i n e   th e   p a r e n c h r o m o s o m e s   th a wi l l   b e   u s e d   f o r r e p r o d u c t i o n B y   a tt e n ti o n   t o   th i s   th a th e   c r o m o s o m e s   w i t h   h i g h   f i tn e s s   w o u l d   b e   s e l e c te d   f o r n e x g e n e r a r ti o n s th e   f i tn e s s   f u n c ti o n   i s   w r i tte n   i n   a   wa y   wh i c h   i n c r e a s e s   wi th   d e c r e a s e   o f m e n ti o n e d   p a r a m e te r s . 1 ) ( T K L K F K F T L f f ( 1 ) In   th i s   e q u a t i o n b y   c h a n g i n g   th e   w e i g h ts w e   c o u l d   i n c r e a s e   th e   v a l u e   o f   th e   p a r a m e te r wh i c h   i s   m o r e   i m p o r ta n f o r   u s   i n   r e s u l ts F o r   e x a m p l e a v o i d i n g   o b s ta c l e s   i s   v e r y   i m p o r ta n i n r o b o n a v i g a ti o n s o f K i s   c o n s i d e r e d   m o r e   th a n   th e   o t h e r   c o n s ta n ts In   o u r   s i m u l a ti o n s th e c o n ta n ts   a r e  c o n s i d e r e d  a s : 100 f K , 1 L K , 1 T K . 3 . S im u la t io n  a n d   Re s u lt s T h e   g e n e t i c   a l g o r i th m   w a s   a p p l i e d   to   s e v e r a l   s a m p l e   s p a c e s   to   s i m u l a te   t h e   n a v i g a ti o n p r o c e s s T h e s e   s p a c e s   v a r y   i n   s i z e   a n d   i n   o b s ta c l e   c o n f i g u r a t i o n S e v e r a l   tr i a l s   w e r e   r u n   f o r e a c h  s p a c e .  Cr o s s o v e r  r a te  i s  0 .7 w h i l e  m u ta ti o n  r a te   i s  0 .3 . T h e  p o p u l a t i o n  s i z e  i s  3 0 . T h e   n u m b e r s   o f   g e n e r a ti o n s   d e p e n d   o n   th e   c o m p l e x i t y   o f   th e   e n v i r o n m e n t; c o n s e q u e n tl y   th e   g e n e r a ti o n s   i n c r e a s e   a s   th e   e n v i r o n m e n s p a c e   b e c o m e s   l a r g e   F i g u r e   8   a n d F i g u r e   9  i l l u s tr a te   e x a m p l e s  o f  s u c c e s s f u l  r u n s  f o r  tw o   s e ts . Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 2 3 0 2 - 4 0 4 6 V a r i a b l e - we i g h t  Co m b i n a t i o n P r e d i c ti o n o f T h e r m a l  E r r o r   M o d e l i n g  o n   CNC… ( Z h i m i n g F e n g ) 6 8 0 9 ( a ) ( b ) F i g u r e 8 . ( a )  r e s u l t p a th  f o r   a  1 0 × 1 0  e n v i r o n m e n t , ( b )  a l g o r i th m  c o n v e r g a n c e ( a ) ( b ) F i g u r e 9 . ( a )  r e s u l t p a th  f o r   a  2 0 × 2 0  e n v i r o n m e n t , ( b )  a l g o r i th m  c o n v e r g a n c e In   o u r   s i m u l a ti o n s to   g e to   b e tt e r   r e s u l ts th e   f i tn e s s   c o n s ta n ts   c h a n g e   a s   th e e n v i r o n m e n t s i z e   i n c r e a s e . O u r   m o d i f i c a ti o n   to   t h e   g e n o t y p e   s tr u c tu r e   to   a l l o m o r e   o p ti o n s   i n   p a th   p l a n n i n g i m p r o v e s  th e  s u c c e s s  o f  r o b o t n a v i g a ti o n . 4 . Co n c lu s io n  a n d   S u g g e s t i o n S i m u l a ti o n s   s h o w   th e   s u c c e s s   o f   th e   g e n e ti c   a l g o r i th m   a n d   th e   i n tr o d u c e d a p p r o a c h   i n f i n d i n g  s u i t a b l e  p a th  i n  n a v i g a ti o n . W h i l e   th e   s u c c e s s   r a te   w a s   h i g h th e r e   w e r e   s t i l l   tr i a l s   w h e r e   o u r   G A   f a i l e d   to   f i n d   a f e a s i b l e   p a th De f e n i t i o n   o f   f i tn e s s   f u n c ti o n   c o u l d   e f f e c ti v e l y   c h a n g e   th e   r e s u l ts Ho we v e r d e f i n i n g   s u i ta b l e   f i t n e s s e s i n d e p e n d e n o f   e n v i r o n m e n t   s i z e   to w a r d   p r o b l e m   g o a l s   c o u l d   b e   v e r y e f f e c ti v e Ne w   m e th o d s   w h i c h   c o m b i n e   r o w - wi s e   a n d   c o l u m n - w i s e   r e p r e s e n ta ti o n s   i n   th e   s a m e g e n o t y p e  s tr u c tu r e  c o u l d  b e  e x p l o r e d . A n o t h e r   a p p r o c h   w h i c h   w i l l   b e   o u r   f u tu r e   wo r k   i s   i m p l e m e n ti n g   c o e v o l u ti o n   b e t we e n p a th e s   a n d   d i r e c ti o n s   i n   o r d e r   to   i m p r o v e   t h e   s u c c e s s   o f   th e   a l g o r i t h m   e i th e r   i n   ti m e   o r n a v i g a ti o n  p e r f o r m a n c e . 0 5 1 0 - 1 0 - 8 - 6 - 4 - 2 0 5 1 0 1 5 2 0 - 2 0 - 1 5 - 1 0 - 5 Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 2 3 0 2 - 4 0 4 6 T E L KO M NIK A V o l 1 2 , No . 9 S e p t e m b e r  2 0 1 4 : 6 8 0 5 6 8 1 0 6 8 1 0 Re f e r e n c e s [ 1 ] Sh a n e   F a rri t o r,   St e v e n   D u b o w s k y . G e n e t i c   Al g o ri t h m   Ba s e d   N a v i g a t i o n   a n d   Pl a n n i n g M e t h o d o l o g y   f o r Pl a n e t a r y   R o b o t i c   Ex p l o r a t i o n . Pro c e e d i n g s   o f   t h e   8 t h   I n t e rn a t i o n a l C o n f e re n c e   o n Ad v a n c e d   R o b o t i c s . 1 9 9 7 . [ 2 ] Pra h l a d   Va d a k k e p a t ,   Ka y   C h e n   T a n . Ev o l u t i o n a r y   Art i f i c i a l   Po t e n t i a l   F i e l d s   a n d   T h e i r A p p l i c a t i o n   i n R e a l   T i m e   R o b o t   P a t h   P l a n n i n g . Pro c e e d i n g s   o n   C o n g r e s s   o n   Ev o l u t i o n a ry   C o m p u t a t i o n . 2 0 0 0 . [ 3 ] H w a n g Y K,   Ah u j a   N . G ro s s   M o t i o n   Pl a n n i n g - Su r v e y . AC M   C o m p u t i n g Su rv e y s . 1 9 9 2 ; 2 4 : 2 1 9 - 2 9 1 . [ 4 ] Ars e n e C T C ,   Z a l z a l a A M S. C o n t ro l   o f   Au t o n o m o u s   R o b o t s   U s i n g   F u z z y   L o g i c C o n t ro l l e rs   T u n e d   b y G e n e t i c Al g o ri t h m s . Pro c e e d i n g s   o f   t h e   1 9 9 9   C o n g re s s   o n E v o l u t i o n a ry   C o m p u t a t i o n   ( C EC 9 9 ) . 1 9 9 9 ; 4 2 8 - 4 3 5 . [ 5 ] Ku b o t a   N ,   M o ri o k a   T ,   Ko j i m a   F ,   F u k u d a   T . Pe r c e p t i o n - B a s e d   G e n e t i c Al g o ri t h m f o r   a   M o b i l e   R o b o t w i t h   F u z z y   C o n t ro l l e rs . Pro c e e d i n g s   o f   t h e   1 9 9 9   C o n g re s s   o n Ev o l u t i o n a ry   C o m p u t a t i o n   ( C EC 9 9 ) . 1 9 9 9 ; 3 9 7 - 4 0 4 . [ 6 ] Pra t i h a D K,   D e b   K,   G h o s h   A. F u z z y - G e n e t i c   Al g o ri t h m s   a n d   M o b i l e   R o b o t N a v i g a t i o n   Am o n g   St a t i c O b s t a c l e s . Pro c e e d i n g s   o f   t h e   1 9 9 9   C o n g re s s   o n   Ev o l u t i o n a r y   C o m p u t a t i o n   ( C EC 9 9 ) .   1 9 9 9 ; 3 2 7 - 3 3 4 . [ 7 ] C a z a n g i   R R ,   F i g u i e r e d o ,   M . Si m u l t a n e o u s   Em e rg e n c e   o f   C o n f l i c t i n g   Ba s i c Be h a v i o r s   a n d   T h e i r C o o rd i n a t i o n   i n   a n   Ev o l u t i o n a ry Au t o n o m o u s   N a v i g a t i o n   Sy s t e m . Pro c .   2 0 0 2   I EEE  C o n f .   o n   Ev o l . C o m p .   ( C EC   ' 0 2 ) .   2 0 0 2 ; 4 6 6 - 4 7 1 . [ 8 ] D i   G e s u V,   L e n z i t t i   B ,   L o   B o s c o G ,   T e g o l o   D . d i s t ri b u t e d   a rc h i t e c t u re   f o r a u t o n o m o u s   n a v i g a t i o n   o f ro b o t s . Pro c e e d i n g s   F i f t h I E EE  I n t e rn a t i o n a l   W o rk s h o p   o n C o m p u t e Ar c h i t e c t u re s   f o M a c h i n e Pe rc e p t i o n ,   2 0 0 0 : 1 9 0 - 1 9 4 . [ 9 ] G a l l a rd o D ,   C o l o m i n a   O ,   F l o r e z F ,   R i z o   R .   G e n e t i c   A l g o ri t h m   f o R o b u s t M o t i o n Pl a n n i n g . 1 1 t h   I n t . C o n f .   o n   I n d u s t ri a l   a n d   En g i n e e ri n g   Ap p l i c a t i o n s   o f   Art i f i c i a l I n t e l l i g e n c e   a n d   Ex p e rt   Sy s t e m s .   1 1 5 - 1 2 2 . [ 1 0 ] Va d a k k e p a t P ,   T a n KC ,   M i n g - L i a n g   W . E v o l u t i o n a r y   Art i f i c i a l   Po t e n t i a l   F i e l d s a n d   T h e i r   Ap p l i c a t i o n   i n R e a l   T i m e   R o b o t   Pa t h   Pl a n n i n g . Pro c .   2 0 0 0   C o n g r e s s   o n Ev o l u t i o n a ry   C o m p u t a t i o n   ( C E C 0 0 ) .   2 0 0 0 : 2 5 6 - 2 6 3 . [ 1 1 ] H o c a o g l u   C ,   S a n d e rs o n   AC .   Pl a n n i n g   M u l t i p l e   Pa t h s   w i t h   Ev o l u t i o n a ry Sp e c i a t i o n . I EEE  T ra n s . Ev o l u t i o n a ry   C o m p u t a t i o n .   2 0 0 1 ;   5 :   1 6 9 - 1 9 1 . [ 1 2 ] Su g i h a r a K,   Sm i t h   J . G e n e t i c   Al g o ri t h m s f o Ad a p t i v e   M o t i o n   P l a n n i n g   o f   a n Au t o n o m o u s   M o b i l e R o b o t . Pro c .   1 9 9 7   I EEE  I n t .   S y m p .   C o m p u t a t i o n a l   I n t e l l i g e n c e   i n R o b o t i c s   a n d   Au t o m a t i o n   ( C I R ' 9 7 ) . 1 3 8 - 1 4 3 . [ 1 3 ] X i a o J ,   M i c h a l e w i c z Z ,   Z h a n g L , T ro j a n o w s k i K.   Ad a p t i v e   E v o l u t i o n a ry Pl a n n e r/ N a v i g a t o r   f o r M o b i l e R o b o t s . I EEE  T ra n s .   Ev o l u t i o n a ry   C o m p u t a t i o n . 1 9 9 7 ; 1 ; 1 8 - 2 8 . [ 1 4 ] H e rm a n u ,   K A s h e n a y i ,   T W   M a n i k a s ,   R L   W a i n w ri g h t . Au t o n o m o u s   R o b o t N a v i g a t i o n   U s i n g   A G e n e t i c   Al g o ri t h m   W i t h   A n   Ef f i c i e n t   G e n o t y p e   St ru c t u re . U n i v e rs i t y o f   T u l s a , T u l s a ,   O k l a h o m a . [ 1 5 ] G e i s l e r T ,   M a n i k a s   T W . Au t o n o m o u s   R o b o t   N a v i g a t i o n   Sy s t e m   U s i n g   a   N o v e l Va l u e   En c o d e d   G e n e t i c Al g o ri t h m . 4 5 t h   I EEE  I n t .   M i d w e s t   Sy m p .   O n   C i rc u i t s   a n d Sy s t e m s ,   T u l s a ,   O K . 2 0 0 2 ; 4 5 - 4 8 . Evaluation Warning : The document was created with Spire.PDF for Python.