I n t e r n a t i o n a l   J o u r n a l   o f   R o b o t i c s   a n d   A u t o m a t i o n   ( I J R A )   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 ,   p p .   4 9 ~ 6 3   I S S N :   2 0 8 9 - 4 8 7 2             4 9       J o u r n a l   h o m e p a g e :   h t t p : / / i a e s j o u r n a l . c o m / o n l i n e / i n d e x . p h p / I J R A   R e d u c e d   S e a r c h   S p a c e   A l g o r i t h m   f o r   S i m u l t a n e o u s   L o c a l i z a t i o n   a n d   M a p p i n g   i n   M o b i l e   R o b o t s       H .   O m r a n p o u r   * ,   S .   S h i r y   *   *   D e p a r t e m e n t   o f   Co m p u t e r   E n g i n e e r i n g ,   A m i r k a b i r   U n i v e r s i t y   o f   T e c h n o l o g y ,   T e h r a n ,   I r a n .       A r t i c l e   I n f o     A B S T R A C T     A r t i c l e   h i s t o r y :   R e c e i v e d   F e b   1 3 ,   2 0 1 2   R e v i s e d   M a r   1 4 ,   2 0 1 2   A c c e p t e d   M a r   2 3 ,   2 0 1 2         I n   t h i s   p a p e r ,   w e   p r o p o s e   a   n e w   a l g o r i t h m   f o r   s i m u l t a n e o u s   l o c a l i z a t i o n   a n d   m a p p i n g   i n   m o b i l e   r o b o t s   w h i c h   u s e s   e v o l u t i o n a r y   a l g o r i t h m   a n d   p a r t i c l e   s w a r m   o p t i m i z a t i o n .   T h e   p r o p o s e d   m e t h o d   i s   b a s e d   o n   b o t h   l o c a l   a n d   g l o b a l   h e u r i s t i c   s e a r c h   m e t h o d s .   I n   e a c h   s t e p   o f   r o b o t   m o v e m e n t s ,   t h e   l o c a l   s e a r c h   i s   a p p l i e d   i n   t h e   s m a l l   s e a r c h   s p a c e   o f   o d o m e t r y   e r r o r s   t o   i m p r o v e   t h e   m a p   a c c u r a c y .   A   g l o b a l   s e a r c h   m e t h o d   i s   a p p l i e d   f o r   l o o p   c l o s i n g .   T h e   p r o p o s e d   a l g o r i t h m   d e t e c t s   l o o p s   a n d   c l o s e s   t h e m ,   d e t e c t s   a n d   s o l v e s   c o r r e s p o n d e n c e   a n d   a v o i d s   l o c a l   e x t r e m u m s .   W i t h   a   p r o p e r   r e p r e s e n t a t i o n   o f   p r o b l e m   p a r a m e t e r s   i n   c h r o m o s o m e ,   t h e   d i m e n s i o n a l i t y   o f   s e a r c h   s p a c e   i s   r e d u c e d .   T h e   p r o p o s e d   a l g o r i t h m   u t i l i z e s   o c c u p a n c y   g r i d   a n d   d o e s   n o t   r e q u i r e   l a n d   m a r k s   w h i c h   a r e   n o t   a v a i l a b l e   i n   m o s t   n a t u r a l   e n v i r o n m e n t s .   A   n e w   f i t n e s s   f u n c t i o n   i s   p r o p o s e d   t h a t   i s   c o m p u t a t i o n a l l y   e f f i c i e n t   a n d   e l i m i n a t e s   t h e   n e e d   f o r   c o m p l e x   s t a t i s t i c a l   c a l c u l a t i o n s   a s   u s e d   i n   c u r r e n t   a p p r o a c h e s .   Re s u l t s   o f   e x p e r i m e n t s   o n   r e a l   d a t a s e t s   e x h i b i t   t h e   s u p e r i o r   p e r f o r m a n c e   o f   t h e   p r o p o s e d   m e t h o d   c o m p a r e d   t o   t h e   c u r r e n t   m e t h o d s .   K e y w o r d :   E v o l u t i o n a r y   a l g o r i t h m   F i t n e s s   f u n c t i o n   P a r e t o   P a r t i c l e   s w a r m   o p t i m i z a t i o n   S e a r c h   s p a c e   S L A M   Co p y r i g h t   ©   2 0 1 2   I n s t i t u t e   o f   A d v a n c e d   E n g i n e e r i n g   a n d   S c i e n c e .     A l l   r i g h t s   r e s e r v e d .   C o r r e s p o n d i n g   A u t h o r :   S .   S h i r y     D e p a r t e m e n t   o f   Co m p u t e r   E n g i n e e r i n g ,   A m i r k a b i r   U n i v e r s i t y   o f   T e c h n o l o g y ,   T e h r a n ,   I r a n .   E m a i l :   S h i r y @ a u t . a c . i r       1 .   I N T R O D U C T I O N   R a p i d   p r o g r e s s e s   i n   a u t o n o m o u s   m o b i l e   r o b o t s   e n a b l e   t h e m   t o   a u t o n o m o u s l y   e x p l o r e   u n k n o w n   e n v i r o n m e n t s   o f   o t h e r   p l a n e t s   o r   o c e a n   f l o o r s .   B e c a u s e   t h e r e   i s   n o   p r i o r   k n o w l e d g e   a b o u t   t h e s e   e n v i r o n m e n t s   a v a i l a b l e   t o   t h e   r o b o t s ,   t h e y   m u s t   b e   a b l e   t o   b u i l d   t h e   e n v i r o n m e n t   m a p   o n l i n e   a n d   t o   l o c a l i z e   t h e m s e l v e s   o n   t h e   m a p   c o n c u r r e n t l y .   M a p   b u i l d i n g   i s   t o   a c q u i r e   a   m o d e l   o f   t h e   s u r r o u n d i n g   o f   t h e   r o b o t   a n d   l o c a l i z a t i o n   i s   t o   i d e n t i f y   t h e   l o c a t i o n   a n d   s t a t e   o f   t h e   r o b o t   i n   t h e   o b t a i n e d   m o d e l .   M a p s   a r e   u s e d   f o r   r o b o t   l o c a l i z a t i o n   a n d   n a v i g a t i o n .   T o   b u i l d   a   m a p ,   r o b o t   m u s t   b e   e q u i p p e d   w i t h   s e n s o r s   l i k e   c a m e r a ,   s o n a r ,   l a s e r ,   i n f r a r e d ,   r a d a r ,   t o u c h   s e n s o r ,   c o m p a s s   a n d   G l o b a l   P o s i t i o n i n g   S y s t e m .   B e c a u s e   m o s t   o f   t h e s e   s e n s o r s   h a v e   l i m i t e d   r a n g e   a n d   m e a s u r e m e n t   e r r o r ,   t h e   r o b o t   m u s t   e x p l o r e   t h e   e n v i r o n m e n t   t o   b u i l d   a   c o m p l e t e   m a p .   I n   8 0 s   a n d   e a r l y   9 0 s ,   m a p   b u i l d i n g   m e t h o d s   w e r e   c l a s s i f i e d   i n t o   t o p o l o g i c   a n d   m e t r i c   c a t e g o r i e s .   A n   e x a m p l e   o f   m e t r i c   m e t h o d s   i s   o c c u p a n c y   g r i d   w h i c h   r e p r e s e n t s   t h e   m a p   w i t h   a   n e t w o r k   o f   e m p t y   o r   o c c u p i e d   c e l l s .   T o p o l o g i c   m e t h o d s   d i s p l a y   t h e   e n v i r o n m e n t   w i t h   t h e   u s e   o f   a   l i s t   o f   s p e c i a l   l o c a t i o n s   w h i c h   a r e   c o n n e c t e d   t o g e t h e r   w i t h   a   s e t   o f   e d g e s .   T h e s e   e d g e s   c o n t a i n   i n f o r m a t i o n   a b o u t   h o w   t h e   r o b o t   n a v i g a t e s   a m o n g   d i f f e r e n t   p l a c e s   [ 1 ] .   I n   o r d e r   t o   n a v i g a t e   a u t o n o m o u s l y   a n d   i n t e l l i g e n t l y ,   a   m o b i l e   r o b o t   m u s t   h a v e   t h e   e n v i r o n m e n t   m a p   a n d   i t s   l o c a t i o n   o n   i t .   I n   r e c e n t   y e a r s ,   s i m u l t a n e o u s   l o c a l i z a t i o n   a n d   m a p p i n g   ( S L A M )   m e t h o d s   a r e   d e v e l o p e d   t o   p r o v i d e   a   s o l u t i o n   f o r   t h e   n e e d   o f   c o n c u r r e n t   l o c a l i z a t i o n   o f   r o b o t   a n d   o t h e r   i m p o r t a n t   o b j e c t s   i n   t h e   e n v i r o n m e n t   [ 2 ] .   I n   S L A M ,   m o b i l e   r o b o t   r e c e i v e s   i n f o r m a t i o n   a b o u t   t h e   e n v i r o n m e n t   f r o m   i t s   s e n s o r s ,   p r o c e s s e s   t h e m ,   b u i l d s   a   c o r r e c t   m a p   a n d   l o c a l i z e s   i t s e l f   t o   a u t o n o m o u s l y   e x p l o r e   t h e   e n v i r o n m e n t   [ 3 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 5 6   I J R A   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 :     4 9     6 3   5 0 S e v e r a l   m e t h o d s   h a v e   b e e n   p r o p o s e d   t o   s o l v e   t h i s   p r o b l e m   w h i c h   w i l l   b e   d i s c u s s e d   i n   f o l l o w i n g   s e c t i o n .   I n   t h i s   p a p e r ,   w e   p r o p o s e   a   n e w   i n t e l l i g e n t   m e t h o d   f o r   s i m u l t a n e o u s   l o c a l i z a t i o n   a n d   m a p p i n g   w h i c h   m i n i m i z e s   e r r o r   i n   m a p   a n d   p a t h .   B e c a u s e   o f   t h e i r   d e s i r e d   f e a t u r e s   i n   t h i s   p r o b l e m ,   w e   h a v e   u s e d   e v o l u t i o n a r y   a l g o r i t h m   a n d   p a r t i c l e   s w a r m   o p t i m i z a t i o n .   I n   s e c t i o n   2 ,   w e   e x p l a i n   s i m u l t a n e o u s   l o c a l i z a t i o n   a n d   m a p p i n g   a n d   r e v i e w   c u r r e n t   s o l u t i o n s   t o   t h i s   p r o b l e m .   I n   s e c t i o n   3   w e   d e s c r i b e   t h e   p r o p o s e d   a l g o r i t h m   a n d   c o m p a r e   i t s   f e a t u r e s   t o   o t h e r   m e t h o d s .   S e c t i o n   4   i s   d e d i c a t e d   t o   e x h i b i t   t h e   r e s u l t s   o f   e x p e r i m e n t s .   I n   s e c t i o n   5   w e   d i s c u s s   t h e   i d e a s   i n   t h e   p r o p o s e d   m e t h o d   a n d   s e c t i o n   6   i s   t h e   c o n c l u d i n g   r e m a r k s .     2 .   S I M U L T A N E O U S   L O C A L I Z A T I O N   A N D   M A P P I N G   T h e   p r o b l e m s   o f   l o c a l i z a t i o n   a n d   m a p p i n g   f o r   r o b o t   d e p e n d   o n   e a c h   o t h e r ;   i t   m e a n s   t h a t   i f   t h e   r o b o t   l o c a t i o n   i s   k n o w n   t h e n   m a p   b u i l d i n g   w o u l d   b e   e a s y .   A l s o   i f   t h e   m a p   i s   k n o w n ,   t h e r e   a r e   m a n y   e f f i c i e n t   a l g o r i t h m s   t o   d e t e r m i n e   t h e   r o b o t   l o c a t i o n .   B u t   s o l v i n g   b o t h   p r o b l e m s   s i m u l t a n e o u s l y   i s   v e r y   d i f f i c u l t   [ 1 ] .   A   s o l u t i o n   t o   S L A M   m u s t   d e a l   w i t h   t h e   f o l l o w i n g   p r o b l e m s   [ 1 , 4 , 5 ] :   S e n s o r   u n c e r t a i n t y :   O n e   o f   t h e   m o s t   i m p o r t a n t   p r o b l e m s   i n   S L A M   i s   m e a s u r e m e n t   e r r o r   o f   r o b o t   o d o m e t r y   w h i c h   r e s u l t s   i n   r o b o t   l o c a l i z a t i o n   u n c e r t a i n t y .   I n   m o d e l i n g   p r o b l e m s ,   i f   d i f f e r e n t   m e a s u r e m e n t   e r r o r s   a r e   s t a t i s t i c a l l y   i n d e p e n d e n t ,   i t   w o u l d   b e   e a s y   t o   r e s o l v e   t h e m .   H o w e v e r   i n   m a p   b u i l d i n g   f o r   r o b o t ,   t h e s e   e r r o r s   a r e   s t a t i s t i c a l l y   d e p e n d e n t .   T h i s   i s   b e c a u s e   c o n t r o l   e r r o r   a c c u m u l a t e s   o v e r   t i m e   w h i c h   l e a d s   i n   m o r e   e r r o r   i n   i n t e r p r e t a t i o n   o f   d a t a   f o r   s u b s e q u e n t   m e a s u r e m e n t s .   F i g . 1   i l l u s t r a t e s   t h i s   p r o b l e m .   R e s o l v i n g   t h e s e   e r r o r s   i s   i m p o r t a n t   t o   b u i l d   a   c o r r e c t   m a p .           F i g . 1   A   m a p   g e n e r a t e d   u s i n g   l a s e r   a n d   o d o m e t r y   w i t h   m e a s u r e m e n t   e r r o r s   [ 2 7 ]           F i g . 2   T h e   a c t u a l   m a p   i n   F i g . 1   [ 2 7 ]       C o r r e s p o n d e n c e   p r o b l e m :   A n o t h e r   m a i n   p r o b l e m   i n   m a p   g e n e r a t i o n   i s   t h e   c o r r e s p o n d e n c e   p r o b l e m .   D e t e c t i n g   c o r r e s p o n d e n c e   m e a n s   t o   r e c o g n i z e   t h a t   d i f f e r e n t   s e n s o r y   m e a s u r e m e n t s   b e l o n g   t o   a   u n i q u e   p h y s i c a l   o b j e c t .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I S S N :   2 0 8 9 - 4 8 7 2       R e d u c e d   S e a r c h   S p a c e   A l g o r i t h m   f o r   S i m u l t a n e o u s   L o c a l i z a t i o n   a n d   M a p p i n g     ( H .   O m r a n p o u r )   5 1 L o o p   c l o s i n g :   A   s o l u t i o n   t o   t h i s   p r o b l e m   a i m s   t o   d e t e c t   a n d   c l o s e   l o o p s   i n   m a p   w i t h   t h e   u s e   o f   c o r r e s p o n d e n c e   d e t e c t i o n .   W h e n   t h e   r o b o t   r e a c h e s   t h e   e n d   o f   a   l o o p ,   i t   m u s t   l o c a t e   i t s e l f   i n   t h e   m a p   i t   h a s   b u i l t   s o   f a r .   T h i s   i s   d i f f i c u l t   b e c a u s e   t h e   a c c u m u l a t e d   m e a s u r e m e n t   e r r o r s   m i g h t   b e   e n o r m o u s .   A n o t h e r   d i f f i c u l t y   a r i s e s   b e c a u s e   t h e   n u m b e r   o f   h y p o t h e t i c a l   m a p s   a n d   r o b o t   l o c a t i o n s   g r o w   e x p o n e n t i a l l y   w i t h   t i m e .   F i g . 2   r e p r e s e n t s   t h e   m a p   i n   F i g . 1   w i t h   t h e   a f o r e m e n t i o n e d   p r o b l e m s   s o l v e d .     T i m e   c o m p l e x i t y :     c o m p u t a t i o n a l   e f f i c i e n c y   i s   a n   i m p o r t a n t   i s s u e   i n   t h e   d e s i g n   o f   a l g o r i t h m s   f o r   a u t o n o m o u s   m o b i l e   r o b o t s   b e c a u s e   t h e y   h a v e   l i m i t e d   c o m p u t a t i o n a l   r e s o u r c e s .   A n   a l g o r i t h m   p r o p o s e d   f o r   S L A M   m u s t   g u a r a n t e e   r e a l - t i m e   p e r f o r m a n c e   o n   t h e s e   l i m i t e d   s e t   o f   r e s o u r c e s .   M e m o r y   c o m p l e x i t y :   m e m o r y   u s a g e   i s   t o o   a n   i m p o r t a n t   p r o b l e m   i n   a l g o r i t h m s   d e v e l o p e d   f o r   m o b i l e   r o b o t s .   A   m e m o r y   c o n s u m i n g   p r o c e s s   c a n   p r e v e n t   o t h e r   p r o c e s s e s   f r o m   e x e c u t i o n   a n d   t h e r e f o r e   s u s p e n d   r o b o t   a c t i v i t i e s .     2 . 1   R e l a t e d   W o r k s   S e v e r a l   m e t h o d s   h a v e   b e e n   p r o p o s e d   t o   s o l v e   t h e   S L A M   p r o b l e m .   E x t e n d e d   K a l m a n   F i l t e r   ( E K F ) ,   F a s t   S L A M   a n d   D i s t r i b u t e d   P a r t i c l e   ( D P )   S L A M   a r e   t h e   m o s t   p o p u l a r   o n e s .   E K F   e l i m i n a t e d   t h e   l i n e a r   m o t i o n   m o d e l   r e q u i r e m e n t   i n   K a l m a n   F i l t e r   ( K F ) ,   a n d   p r o d u c e s   a c c u r a t e   r e s u l t s .   H o w e v e r   i t   f a i l s   i n   e n v i r o n m e n t s   w h e r e   e r r o r   m o d e l   i s   n o t   G a u s s i a n   a n d   i t   i s   c o m p u t a t i o n a l l y   i n e f f i c i e n t   [ 6 - 1 0 ] .   F a s t   S L A M   c o m b i n e s   t h e   p a r t i c l e   f i l t e r   [ 1 1 - 1 3 ]   a n d   K F   m e t h o d s   t o   i m p r o v e   t h e   e f f i c i e n c y   o f   K F   m e t h o d .   E a c h   p a r t i c l e   s t o r e s   t h e   r o b o t   t r a j e c t o r y   a n d   m a p   t o   i n c r e a s e   t h e   s p e e d   o f   a l g o r i t h m .   H o w e v e r ,   s t o r i n g   m a p   i n   e a c h   p a r t i c l e   r e q u i r e s   a   l a r g e   a m o u n t   o f   m e m o r y .   R a o B l a c k w e l l i z e d   p a r t i c l e   f i l t e r   m e t h o d   [ 1 4 , 1 5 ]   p r o p o s e d   a   m e c h a n i s m   t o   s h a r e   t h e   m a p s   b e t w e e n   p a r t i c l e s   t o   c o m p e n s a t e   m e m o r y   r e q u i r e m e n t   o f   F a s t   S L A M ,   b u t   r e q u i r e s   p r e d e t e r m i n e d   l a n d m a r k s   i n   t h e   e n v i r o n m e n t .   D P - S l a m   u s e s   a   c o m p l e x   d a t a   s t r u c t u r e   t o   r e p r e s e n t   m u l t i p l e   p a r t i c l e s   i n   a   s i n g l e   m a p .   I n   t h i s   m e t h o d   a   o c c u p a n c y   m a p   i s   u s e d   w h i c h   c e l l s   a r e   t r e e s   t h a t   r e p r e s e n t   m a p   p a r t s   o f   d i f f e r e n t   p a r t i c l e s .   T h i s   d a t a   s t r u c t u r e   r e d u c e s   t h e   m e m o r y   r e q u i r e m e n t   b u t   p u t   a   b u r d e n   o n   s p e e d   o f   a l g o r i t h m   d u e   t o   d a t a   m a n i p u l a t i o n   c o m p l e x i t y .   T h i s   a l g o r i t h m   d o e s   n o t   r e q u i r e   l a n d m a r k s   a n d   i t s   c o r r e s p o n d e n c e   d e t e c t i o n   i s   n o t   a c c u r a t e   [ 1 6 , 1 7 ] .   I n   [ 1 8 ] ,   p a r t i c l e   f i l t e r   i s   c o m b i n e d   w i t h   G e n e t i c   a l g o r i t h m s   t o   a l l e v i a t e   t h e   p r o b l e m   o f   l o c a l   m i n i m a .   T h i s   m e t h o d   u s e s   i m a g e   p r o c e s s i n g   f o r   c o r r e s p o n d e n c e   d e t e c t i o n   w h i c h   a c t s   v e r y   w e l l ,   h o w e v e r   t h i s   p u t s   a   b u r d e n   o n   p r o c e s s i n g   t i m e   o f   t h e   a l g o r i t h m .   B e g u m   e t . a l .   [ 5 ]   u s e d   a   s e t   o f   f u z z y   r u l e s   t o   d e t e c t   e r r o r s   i n   s e n s o r y   m e a s u r e m e n t s .   I t   i s   b a s e d   o n   G e n e t i c   a l g o r i t h m s   a n d   u s e s   a   f i t n e s s   f u n c t i o n   w i t h   a   c o m p l i c a t e d   f o r m u l a   f o r   m a t c h i n g .   T h e   m e t h o d   u s e d   t h e   I s l a n d   G e n e t i c   a l g o r i t h m s   ( I G A )   t o   i n c r e a s e   s p e e d   a n d   v a r i e t y .   T h e   I G A   i s   f a s t   i f   t h e   n u m b e r   o f   p r o c e s s o r s   i s   e q u a l   t o   t h e   n u m b e r   o f   i s l a n d s .   H o w e v e r ,   a n   a u t o n o m o u s   m o b i l e   r o b o t   u s u a l l y   h a s   a   s i n g l e   p r o c e s s o r .   I n   t h i s   c a s e ,   I G A   p e r f o r m a n c e   i s   l i k e   s i m p l e   G A   a n d   t h e r e f o r e   s p e e d   d e c r e a s e s .   M o r e o v e r ,   t h e   m e m o r y   r e q u i r e m e n t   f o r   I G A   i s   m o r e   t h a n   s i m p l e   G A .   W e   r e d u c e d   t h e   s e a r c h   s p a c e   t o   i n c r e a s e   t h e   s p e e d   o f   f i n d i n g   o p t i m a l   s o l u t i o n   i n   t h e   e v o l u t i o n a r y   a l g o r i t h m .   T h i s   r e d u c t i o n   a l s o   l o w e r s   t h e   m e m o r y   r e q u i r e m e n t s   o f   t h e   p r o p o s e d   a l g o r i t h m .       3 .   P R O P O S E D   A L G O R I T H M   T h e   p r o b l e m   o f   S L A M   c a n   b e   d e f i n e d   a s   a n   o p t i m i z a t i o n   i n   t h e   s p a c e   o f   a l l   p o s s i b l e   m a p s   a n d   r o b o t   t r a j e c t o r i e s   [ 1 9 ] .   H o w e v e r   t h e   s e a r c h   s p a c e   o f   m a p s   a n d   p a t h s   a r e   e x t r e m e l y   l a r g e   b e c a u s e   t h e y   a r e   h i g h   d i m e n s i o n a l   d a t a   s t r u c t u r e s .   S e a r c h   i n   t h i s   l a r g e   s p a c e   f o r   o p t i m u m   s o l u t i o n s   i s   v e r y   t i m e   c o n s u m i n g   [ 5 ,   1 9 ] .   I n   o r d e r   t o   d e c r e a s e   t h e   n u m b e r   o f   d i m e n s i o n s   i n   s e a r c h   s p a c e ,   w e   q u a n t i z e d   t h e   e r r o r   m e a s u r e m e n t s   i n t o   L < < M   p a r t i t i o n s   w h e r e   M   i s   t h e   t o t a l   n u m b e r   o f   s e n s o r y   m e a s u r e m e n t s   a l o n g   t h e   r o b o t   t r a j e c t o r y .   O p t i m i z a t i o n   i s   p e r f o r m e d   o n   e a c h   r o b o t   s t e p   a n d   o n   t h e   s e t   o f   a l l   p a r t i t i o n s   w h i c h   b o t h   h a v e   m u c h   s m a l l e r   n u m b e r   o f   d i m e n s i o n s .   O p t i m i z a t i o n   o n   e a c h   r o b o t   s t e p   i n c r e a s e s   t h e   c o n v e r g e n c e   s p e e d   o f   t h e   o p t i m i z a t i o n   o n   a l l   p a r t i t i o n s .   T h e   a l g o r i t h m   w e   p r o p o s e   h e r e   i s   b a s e d   o n   t w o   s e a r c h   m e t h o d s   ( F i g . 3 ) .   O n e   i s   a   l o c a l   s e a r c h   a l g o r i t h m   t h a t   u s e s   p a r t i c l e   s w a r m   o p t i m i z a t i o n .   T h e   g o a l   o f   l o c a l   s e a r c h   i s   t o   e x t e n d   a n d   i m p r o v e   t h e   m a p   a n d   r o b o t   p a t h   e f f i c i e n t l y   a n d   i n   r e a l - t i m e ,   u s i n g   c u r r e n t   m a p   a n d   s e n s o r y   i n f o r m a t i o n .   G l o b a l   s e a r c h   a l g o r i t h m   i s   u s e d   t o   s o l v e   c o r r e s p o n d e n c e   a n d   l o o p   c l o s i n g   p r o b l e m s .   T h e   a l g o r i t h m   d e t e c t s   c o r r e s p o n d e n c e   o r   l o o p   a n d   t h e n   p e r f o r m s   a   g l o b a l   s e a r c h .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 5 6   I J R A   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 :     4 9     6 3   5 2     F i g . 3   F l o w   c h a r t   o f   t h e   p r o p o s e d   a l g o r i t h m       T h e   e v a l u a t i o n   f u n c t i o n s   w e   u s e d   h e r e   a r e   b a s e d   o n   c o m b i n a t i o n   o f   l o c a l i z a t i o n   a n d   m a p p i n g   i n f o r m a t i o n .   M a p   r e p r e s e n t a t i o n   m o d e l   i s   i m p o r t a n t   b e c a u s e   i t   i n f l u e n c e s   t h e   t i m e   a n d   m e m o r y   c o m p l e x i t y   o f   a l g o r i t h m .   W e   u s e d   o c c u p a n c y   g r i d   t o   r e p r e s e n t   t h e   m a p   b e c a u s e   o f   i t s   s i m p l i c i t y   i n   s t r u c t u r e   a n d   u s e ,   m o r e o v e r   i t   i s   f a s t   i n   p r o c e s s i n g   h o m o g e n e o u s   i n f o r m a t i o n .   A n o t h e r   r e a s o n   t o   u s e   o c c u p a n c y   g r i d   i s   t h a t   o u r   p r o p o s e d   a l g o r i t h m   d o e s   n o t   r e q u i r e   l a n d m a r k s .     3 . 1   L o c a l   s e a r c h   a l g o r i t h m   L o c a l   o p t i m i z a t i o n   i s   p e r f o r m e d   t o   i n c r e a s e   t h e   a c c u r a c y   o f   o d o m e t r y   m e a s u r e m e n t s   i n   e a c h   r o b o t   s t e p .   L o c a l l y   a c c u r a t e   m a p s   a n d   r o b o t   p o s e s   a r e   t h e n   g r o u p e d   t o g e t h e r   b y   t h e   g l o b a l   s e a r c h   a l g o r i t h m   t o   f i n d   t h e   g l o b a l l y   a c c u r a t e   m a p   a n d   p a t h   w i t h   h i g h   s p e e d .   I n   o r d e r   t o   p e r f o r m   o p t i m i z a t i o n   e f f i c i e n t l y   a n d   w i t h   l o w   m e m o r y   r e q u i r e m e n t s ,   a n d   a l s o   t o   k e e p   t h e   s i z e   o f   s e a r c h   s p a c e   s m a l l   i n   e a c h   s t e p ,   w e   u s e d   p a r t i c l e   s w a r m   o p t i m i z a t i o n   ( P S O ) .   P S O   i s   a   s t o c h a s t i c   o p t i m i z a t i o n   t e c h n i q u e   b a s e d   o n   s o l u t i o n s   o f   a   p o p u l a t i o n   o f   p a r t i c l e s .   I n s p i r e d   b y   s o c i a l   b e h a v i o r s   o f   b i r d   f l o c k i n g   a n d   f i s h   s c h o o l i n g ,   i t   w a s   f i r s t   i n t r o d u c e d   b y   K e n n e d y   a n d   E b e r h a r t   i n   1 9 9 5   [ 2 0 ] .   T h i s   m e t h o d   i s   b a s e d   o n   a   s e t   o f   p a r t i c l e s   w h i c h   m o v e   i n   s e a r c h   s p a c e .   E a c h   p a r t i c l e   c o n s i s t s   o f   a   l o c a t i o n   ( p [ ] )   a n d   a   v e l o c i t y   ( v [ ] )   v e c t o r .   I t   a l s o   r e t a i n s   t h e   b e s t   o b s e r v e d   s o l u t i o n   o f   i t s e l f   ( p b e s t [ ] )   a n d   o f   i t s   g r o u p   ( g b e s t [ ] ) .   E a c h   p a r t i c l e   m o v e s   w i t h   a p p r o p r i a t e   v e l o c i t y   t o w a r d   t h e   b e s t   f o u n d   s o l u t i o n   o f   i t s e l f   a n d   i t s   g r o u p   t o   f i n d   t h e   o p t i m u m   s o l u t i o n .   P S O   c a n   f i n d   a c c e p t a b l e   a n s w e r s   t o   d i f f i c u l t   n o n l i n e a r   a n d   d i s c r e t e   o p t i m i z a t i o n   p r o b l e m s   [ 2 1 ] .   I n   t h e   p r o p o s e d   a l g o r i t h m ,   w e   u s e d   e a c h   p a r t i c l e   t o   r e p r e s e n t   a c c u m u l a t e d   e r r o r   i n   r o b o t   m o v e m e n t .   x ,   y   a n d   Ө   r e p r e s e n t   t h e   a m o u n t   o f   e r r o r   i n   l o c a t i o n   ( X , Y )   a n d   o r i e n t a t i o n   Ө ,   r e s p e c t i v e l y   f o r   t h e   l a s t   r o b o t   s t e p .   A s   t h e   r o b o t   m o v e s ,   t h e s e   e r r o r s   a r e   c a l c u l a t e d   i n   e a c h   s t e p   a n d   a d d e d   t o   s e n s o r y   m e a s u r e m e n t s   t o   l o c a l i z e   t h e   r o b o t   a n d   g e n e r a t e   t h e   m a p   c o r r e c t l y .   I n   t h i s   p r o b l e m ,   t h e   s e a r c h   s p a c e   i s   t h e   c u b e   o f   [ - m a x x ,   m a x x ] ,   [ - m a x y ,   m a x y ]   a n d   [ - m a x Ө ,   m a x Ө ]   i n   ( x ,   y ,   Ө )   s p a c e .   T h i s   i s   a   s m a l l   s e a r c h   s p a c e   b e c a u s e   m e a s u r e m e n t   e r r o r   i n   e a c h   s t e p   l i e s   i n   a   t i g h t   r a n g e   ( F i g . 4 ) .   T h e r e f o r e   w e   c a n   f i n d   a n s w e r   q u i c k l y   b y   a p p l y i n g   t h e   P S O   A l g o r i t h m .   F i r s t   w e   d i s t r i b u t e   t h e   p a r t i c l e s   i n   a   s m a l l   s e a r c h   c u b e ,   a n d   t h e n   t h e   a c c e p t a b l e   s o l u t i o n   i s   f o u n d   a s   t h e   p a r t i c l e s   m o v e   i n   t h i s   s p a c e .   I n   o r d e r   t o   c a l c u l a t e   t h e   e v a l u a t i o n   f u n c t i o n   i n   r e a l - t i m e ,   w e   u s e d   E q .   1 .     = = = > - = t t n i m j t p a r t t p a r t j i m a p j i m a p t e v a l u a t i o n 1 1 ) ] ( [ ) ] ( [ 1 ) 0 ) , ( i f (             0 ) 0 ) , ( i f (             1 ) (   ( 1 )     m a p [ p a r t ( t ) ]   i s   p a r t   o f   t h e   m a p   t h a t   i s   b e i n g   u p d a t e d   c u r r e n t l y   a n d   m t   a n d   n t   r e p r e s e n t   i t s   d i m e n s i o n s .   E v e r y   t i m e   a n   o b s t a c l e   i s   d e t e c t e d   i n   t h e   l o c a t i o n   ( i , j )   o f   t h e   m a p ,   t h e   c o r r e s p o n d i n g   c e l l   v a l u e   i s   i n c r e a s e d   b y   1 .   T h e   e v a l u a t i o n   f u n c t i o n   o f   ( E q . 1 )   c a l c u l a t e s   t h e   n u m b e r   o f   o b s e r v e d   o b s t a c l e s   i n   t h e   m a p .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I S S N :   2 0 8 9 - 4 8 7 2       R e d u c e d   S e a r c h   S p a c e   A l g o r i t h m   f o r   S i m u l t a n e o u s   L o c a l i z a t i o n   a n d   M a p p i n g     ( H .   O m r a n p o u r )   5 3 W h a t e v e r   t h e s e   o b s t a c l e s   o v e r l a p   a n d   d e c r e a s e   i n   n u m b e r ,   t h e   o b t a i n e d   m a p   w i l l   b e   m o r e   a c c u r a t e .   W e   s e e k   t o   f i n d   t h e   m a x i m u m   o f   t h e   e v a l u a t i o n   f u n c t i o n ;   t h e r e f o r e   a   n e g a t i v e   s i g n   i s   a p p l i e d   i n   ( E q . 1 ) .           F i g . 4   S e a r c h   s p a c e   f o r   l o c a l   s e a r c h   a l g o r i t h m   i s   c o n f i n e d   t o   t h e   c u b e .   T h i s   i s   a   s m a l l   s e a r c h   s p a c e   b e c a u s e   m e a s u r e m e n t   e r r o r s   i n   e a c h   s t e p   a r e   s m a l l       W e   h a v e   t r i e d   a   s e c o n d   e v a l u a t i o n   f u n c t i o n   w h i c h   c a l c u l a t e s   t h e   m e a n   o f   t h e   n u m b e r   o f   o b s e r v e d   o b s t a c l e   c e l l s   ( E q .   2 ) .     = = = = = > = t t t t n i m j t p a r t t p a r t n i m j t p a r t j i m a p j i m a p j i m a p t e v a l u a t i o n 1 1 ) ] ( [ ) ] ( [ 1 1 ) ] ( [ 2 ) 0 ) , ( i f (             0 ) 0 ) , ( i f (             1 ) , ( ) (   ( 2 )     I n i t i a l l y   a   p o p u l a t i o n   o f   r a n d o m   p a r t i c l e s   i s   g e n e r a t e d .   M o v i n g   t h e   p a r t i c l e s   o f   p o p u l a t i o n ,   w e   s e e k   t o   f i n d   t h e   o p t i m u m   s o l u t i o n .     I n   e a c h   i t e r a t i o n ,   p b e s t   a n d   g b e s t   a r e   d e t e r m i n e d .   T h e n   w e   u s e   E q .   3   t o   c a l c u l a t e   t h e   v e l o c i t y   a n d   E q .   4   t o   u p d a t e   t h e   p o s i t i o n   o f   e a c h   p a r t i c l e .     ) . ( . ) . ( . . , 2 2 , 1 1 1 , , t i i t i i t i t i p g b e s t r c p p b e s t r c v w v - + - + = -   ( 3 )     t i t i t i v p p , , 1 , + = +   ( 4 )     H e r e ,   1 r   a n d   2 r   a r e   r a n d o m   n u m b e r s   i n   t h e   i n t e r v a l   [ 0 , 1 ] ,   1 c   a n d   2 c   a r e   l e a r n i n g   r a t e s   u s u a l l y   s e t   t o   2 .     B e c a u s e   t i m e   o r d e r   o f   P S O   a l g o r i t h m   i s   c o n s t a n t   a n d   i t   d o e s   n o t   r e q u i r e   e v a l u a t i o n   o f   c o m p l i c a t e d   m a t h e m a t i c a l   e x p r e s s i o n s   [ 2 2 ] ,   t h i s   a l g o r i t h m   c a n   s e e k   l o c a l   s e a r c h   s p a c e   a n d   f i n d   t h e   o p t i m a l   s o l u t i o n   i n   r e a l - t i m e   w i t h   f e w   p a r t i c l e s   a n d   m o v e m e n t s .     3 . 2   G l o b a l   S e a r c h   A l g o r i t h m   T h e   g o a l   o f   t h e   g l o b a l   s e a r c h   i s   t o   d e t e c t   c o r r e s p o n d e n c e s   a n d   c l o s e   l o o p s .   I f   t h e   r o b o t   e n c o u n t e r s   a   p l a c e   f o r   t h e   s e c o n d   t i m e   b u t   t h e   l a s e r   s e n s o r   c a n   n o t   d e t e c t   o b s t a c l e s   i n   t h e i r   r i g h t   l o c a t i o n   t h e n   l o o p   o r   c o r r e s p o n d e n c e   i s   d e t e c t e d   a n d   t h e   g l o b a l   s e a r c h   a l g o r i t h m   i s   c a l l e d .   T h e   g l o b a l   s e a r c h   i s   a n   e v o l u t i o n a r y   a l g o r i t h m   w h i c h   a i m s   t o   f i n d   t h e   m i n i m u m   e r r o r   o f   p o s e s   t o   b u i l d   a   c o n s i s t e n t   m a p .   C o n t r a r y   t o   t h e   l o c a l   s e a r c h ,   t h e   g l o b a l   s e a r c h   a l g o r i t h m   u s e s   a   s e q u e n c e   o f   r o b o t   p o s e s   a n d   l a s e r   s e n s o r   m e a s u r e m e n t s   t o   u p d a t e   a   l a r g e   p o r t i o n   o f   t h e   m a p .   A   p r o b l e m   t h a t   a r i s e s   h e r e   i s   t h a t   t h e   d i m e n s i o n a l i t y   o f   s e a r c h   s p a c e   i s   p r o p o r t i o n a l   t o   t h e   n u m b e r   o f   r o b o t   s t e p s   a l o n g   t h e   p a t h .   I n   o r d e r   t o   r e d u c e   t h e   d i m e n s i o n a l i t y ,   w e   d i v i d e d   t h e s e   s t e p s   i n t o   a   s m a l l   n u m b e r   o f   g r o u p s .   E r r o r   i n   p o s e s   a n d   m a p   o f   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 5 6   I J R A   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 :     4 9     6 3   5 4 e a c h   g r o u p   i s   r e p r e s e n t e d   w i t h   a   v e c t o r   i n   c h r o m o s o m e .   T h e s e   e r r o r s   a r e   m u l t i p l i e d   t o   a   G a u s s i a n   f u n c t i o n   a n d   a r e   d i s t r i b u t e d   o v e r   g r o u p   s t e p s   t o   a v o i d   l o o s i n g   p r e c i s i o n .   E v o l u t i o n a r y   a l g o r i t h m s   a r e   a   c l a s s   o f   s e a r c h   a l g o r i t h m s   i n s p i r e d   b y   e v o l u t i o n   o f   a n i m a t e s .   T h e   m o s t   i m p o r t a n t   a d v a n t a g e   o f   e v o l u t i o n a r y   a l g o r i t h m s   i s   t h a t   t h e y   a r e   a p p l i c a b l e   t o   a   w i d e   r a n g e   o f   p r o b l e m s   w i t h   l a r g e   s p a c e   o f   p o s s i b l e   s o l u t i o n s .   W i t h   p r o p e r   u s e   o f   e v o l u t i o n a r y   o p e r a t o r s ,   t h e y   c a n   p a s s   l o c a l   e x t r e m u m s   a n d   f i n d   t h e   g l o b a l   e x t r e m u m   [ 2 3 ] .   E a c h   e v o l u t i o n a r y   a l g o r i t h m   i s   c o m p o s e d   o f   e i g h t   p a r t s   w h i c h   m u s t   b e   d e s i g n e d   c a r e f u l l y   t o   m e e t   t h e   s p e c i f i c   p r o b l e m   r e q u i r e m e n t s .   W e   w i l l   c o n s i d e r   e a c h   p a r t   f o r   t h e   p r o p o s e d   a l g o r i t h m .     3 . 2 . 1   R e p r e s e n t a t i o n   T h e   f i r s t   s t e p   i n   u s i n g   a n   e v o l u t i o n a r y   a l g o r i t h m   i s   t o   a p p r o p r i a t e l y   c o d e   t h e   p a r a m e t e r s   o f   p r o b l e m   i n   a   f o r m a t   s u i t a b l e   f o r   t h e   a l g o r i t h m .   I n   t h i s   s e c t i o n ,   w e   c o d e   t h e   i m p o r t a n t   p a r a m e t e r s   o f   t h e   p r o b l e m   i n   p e r s o n s   o f   p o p u l a t i o n   w h i c h   a r e   c a l l e d   c h r o m o s o m e .   W e   a s s u m e   t h a t   t h e   d a t a   o f   M   s u c c e s s i v e   t i m e   s t e p s   a r e   a v a i l a b l e   t o   t h i s   a l g o r i t h m .   A s   m e a s u r e m e n t   e r r o r   i s   a   c o n t i n u o u s   f u n c t i o n ,   w e   d i v i d e   t h i s   d a t a   i n t o   L   p a r t s .   T h e r e f o r e   e a c h   c h r o m o s o m e   b e c o m e s   a   3 * L * 2   m a t r i x .   W e   c h o s e   L < < M   t o   s p e e d   u p   t h e   a l g o r i t h m   a n d   r e d u c e   t h e   m e m o r y   r e q u i r e m e n t s .   E a c h   c o l u m n   i n   t h e   c h r o m o s o m e   r e p r e s e n t s   a n   e r r o r   p a r t .   E r r o r s   o f   l o c a t i o n   i n   ( x , y )   c o o r d i n a t e   a n d   d i r e c t i o n   i n   t h e   i - t h   p a r t   a r e   r e p r e s e n t e d   b y   x i ,   y i   a n d   Ө i   r e s p e c t i v e l y .   T h e s e   e r r o r s   a r e   w e i g h t e d   w i t h   a   G a u s s i a n   f u n c t i o n   a n d   a d d e d   t o   t h e   i - t h   p a r t   o f   t h e   r o b o t   l o c a t i o n s   a n d   t h e r e f o r e   t o   t h e   o b s t a c l e s   l o c a t i o n s .   E r r o r   o f   i - t h   p a r t   f o r   x ,   y   a n d   Ө   a x i s   a r e   m u l t i p l i e s   t o   a   G a u s s i a n   f u n c t i o n s   w i t h   m e a n s   µ x i ,   µ y i   a n d   µӨ i .   T h e   c h r o m o s o m e   w i t h   L   p a r t s   i s   r e p r e s e n t e d   i n   F i g . 5 .         F i g . 5   ( a )   3 D   r e p r e s e n t a t i o n   o f   c h r o m o s o m e ,   ( b )   2 D   r e p r e s e n t a t i o n   o f   c h r o m o s o m e       E a c h   o b t a i n e d   c o l u m n   o f   e r r o r   i s   a d d e d   t o   t h e   c o r r e s p o n d i n g   p a r t   u s i n g   a   G a u s s i a n   w e i g h t i n g   f u n c t i o n .   T h i s   i s   s h o w n   f o r   x   c o o r d i n a t e   a n d   i - t h   p a r t   i n   E q .   5 .     ) 2 ) ( e x p ( 2 1 2 2 , , x x i x j i x i x j i p a t h x e r r o r d m p d - - ´ D =   ( 5 )     Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I S S N :   2 0 8 9 - 4 8 7 2       R e d u c e d   S e a r c h   S p a c e   A l g o r i t h m   f o r   S i m u l t a n e o u s   L o c a l i z a t i o n   a n d   M a p p i n g     ( H .   O m r a n p o u r )   5 5 W h e r e   x j i e r r o r ,   r e p r e s e n t s   t h e   o b t a i n e d   e r r o r   a n d   x j i p a t h ,   i s   t h e   i n d e x   i n   t h e   r a n g e   L M , 1   o f   j - t h   m e a s u r e m e n t   i n   t h e   i - t h   p a r t   f o r   x   a x i s .   S t a n d a r d   d e v i a t i o n s   f o r   x ,   y   a n d   Ө   d e p e n d   o n   t h e   m o d e l   o f   e n v i r o n m e n t   a n d   r o b o t   s e n s o r s .   W e   h a v e   c o n s i d e r e d   t h e m   t o   b e   c o n s t a n t   f o r   t h i s   e x p e r i m e n t .   T o   a v o i d   l o o s i n g   p r e c i s i o n   b e c a u s e   o f   d i v i d i n g   m e a s u r e m e n t s   t o   L   p a r t s ,   w e   u s e d   a   s i m i l a r   G a u s s i a n   w e i g h t i n g   m e c h a n i s m   w i t h   a n   a p p r o p r i a t e l y   s e l e c t e d   m e a n   t o   i n c r e a s e   t h e   s p e e d   a n d   a c c u r a c y   o f   t h e   a l g o r i t h m .     3 . 2 . 2   I n i t i a l i z a t i o n   T h e r e   i s   n o   i n f o r m a t i o n   a v a i l a b l e   a b o u t   t h e   p a t t e r n   o f   s o l u t i o n   t o   t h i s   p r o b l e m .   T h e r e f o r e   r a n d o m   n u m b e r s   o f   u n i f o r m   d i s t r i b u t i o n   i n   a   r a n g e   b e t w e e n   m i n i m u m   a n d   m a x i m u m   v a l u e s   o f   t h e   m e a s u r e m e n t   e r r o r s   a n d   m e a n   a r e   u s e d   t o   i n i t i a l i z e   t h e   p o p u l a t i o n .     3 . 2 . 3 .   F i t n e s s   F u n c t i o n   I n   o r d e r   t o   s e l e c t   p a r e n t s   a n d   s u r v i v o r s ,   w e   m u s t   e v a l u a t e   c h r o m o s o m e s   i n   t h e   p o p u l a t i o n .   T h e   g o a l   o f   t h e   e v o l u t i o n a r y   a l g o r i t h m   i s   t o   f i n d   t h e   m a x i m u m   ( m i n i m u m )   o f   t h e   f i t n e s s   f u n c t i o n .   W e   c o m b i n e d   t w o   d i f f e r e n t   f i t n e s s   f u n c t i o n s   i n   E q .   6   a n d   E q .   7   t o   e v a l u a t e   t h e   p o p u l a t i o n .     = = = = = > = n i m j n i m j j i m a p j i m a p j i m a p f i t n e s s 1 1 1 1 1 ) 0 ) , ( i f (             0 ) 0 ) , ( i f (             1 ) , (   ( 6 )     ) ) ( ) , ( ( t a n . 0 ) )   1 j ) ( t r a j ( i ,   &   )   0 ) , ( ( (   i f 1 . 2 1 2 1 1 1 2 t o b j t o b j c e D i s W e l s e j i m a p W f i t n e s s n i m j - = = > - = = =   ( 7 )     I n   E q .   6 ,   s u m   o f   o b s e r v a t i o n s   o f   o b s t a c l e s   i n   e a c h   m a p   c e l l   i s   d i v i d e d   t o   t h e   n u m b e r   o f   o c c u p i e d   c e l l s   t o   c a l c u l a t e   t h e   m e a n   o f   t h e   t i m e s   a n   o b s t a c l e   i s   o b s e r v e d   i n   a   c e l l .   A   w e i g h t e d   s u m   o f   t w o   t e r m s   i s   c a l c u l a t e d   i n   E q .   7 .   T h e   f i r s t   t e r m   w i t h   w e i g h t   W 1 ,   c o u n t s   t h e   n u m b e r   o f   p o i n t s   i n   t h e   r o b o t   p a t h   w h i c h   h a v e   c o n f l i c t   w i t h   t h e   o b s e r v e d   o b s t a c l e s   i n   t h e   m a p .   T h e   s e c o n d   t e r m ,   m e a s u r e s   t h e   d i s t a n c e   b e t w e e n   t w o   o b j e c t s   i n   t h e   m a p   w h e r e   a   c o r r e s p o n d e n c e   h a s   b e e n   d e t e c t e d   a m o n g   t h e m .   T h e   W 1   a n d   W 2   a r e   u s e d   t o   a d j u s t   t h e   e f f e c t   o f   e a c h   t e r m .   T h e i r   v a l u e s   d e p e n d   o n   t h e   s p e c i f i c   p r o b l e m   i n   h a n d .   I n   o r d e r   t o   a v o i d   t h e   u n d e s i r a b l e   e f f e c t   o f   r e l a t i v e   m a g n i t u d e   o f   e a c h   f i t n e s s   f u n c t i o n   o n   t h e   o t h e r ,   w e   u s e d   P a r e t o s   m e t h o d   t o   m a x i m i z e   b o t h   c o n c u r r e n t l y   [ 2 4 ] .     3 . 2 . 4   P a r e n t   s e l e c t i o n   C o n s i d e r i n g   c h r o m o s o m e   r e p r e s e n t a t i o n ,   w e   p r e f e r r e d   t o   s e l e c t   p a r e n t s   i n   r a n d o m ,   b e c a u s e   i t   i s   p o s s i b l e   t o   c o m b i n e   a   g o o d   a n d   a   p o o r   s o l u t i o n   a n d   g e n e r a t e   a   b e t t e r   o n e .   E v e n   c o m b i n i n g   t w o   p o o r   s o l u t i o n s   m i g h t   r e s u l t   i n   a n   o f f s p r i n g   w i t h   h i g h   f i t n e s s   v a l u e .   T h i s   i n c r e a s e s   t h e   p o p u l a t i o n   v a r i e t y   a n d   e x t e n d s   s e a r c h   s p a c e .     3 . 2 . 5   C r o s s o v e r     T o   i m p r o v e   t h e   p o p u l a t i o n   v a r i e t y ,   a   u n i f o r m   c r o s s o v e r   i s   u s e d .   T w o   p a r e n t s   a r e   s e l e c t e d   i n   r a n d o m   a n d   c o m b i n e d   w i t h   p r o b a b i l i t y   P c .   T h e   o d d   a n d   e v e n   c o l u m n s   a r e   s e l e c t e d   f r o m   e a c h   p a r e n t   a n d   i n t e r l e a v e d   t o   g e n e r a t e   t w o   c h i l d r e n .   T h i s   o p e r a t i o n   i s   r e p e a t e d   t o   p r o d u c e   a   p r e d e t e r m i n e d   n u m b e r   o f   o f f s p r i n g .   E a c h   c o l u m n   o f   t h e   c h r o m o s o m e   i n   F i g . 5   c o n t a i n s   3   p a i r s   o f   n u m b e r s .   E a c h   p a i r   r e p r e s e n t s   e r r o r   a n d   m e a n   f o r   x ,   y   a n d   Ө   d i m e n s i o n s .   T h e   p r o p o s e d   c r o s s o v e r   o p e r a t o r   i s   d e s i g n e d   t o   e n s u r e   t h e   v a r i e t y   a n d   c o n v e r g e n c e   s p e e d   o f   t h e   g l o b a l   s e a r c h   a l g o r i t h m .   I n   o r d e r   t o   a c h i e v e   v a r i e t y ,   i n   t h e   f i r s t   h a l f   o f   t h e   g e n e r a t i o n s   e a c h   n u m b e r   i s   s e l e c t e d   w i t h   t h e   p r o b a b i l i t y   0 . 5   f r o m   a   p a r e n t .   T o   i n c r e a s e   t h e   c o n v e r g e n c e   s p e e d ,   i n   t h e   s e c o n d   h a l f   o f   t h e   g e n e r a t i o n s ,   e a c h   p a i r   o f   n u m b e r s   c o m e s   f r o m   a   p a r e n t   w i t h   p r o b a b i l i t y   0 . 5   ( F i g . 6 ) .   E r r o r   a n d   m e a n   i n   e a c h   o f   x ,   y   a n d   Ө   d i m e n s i o n s   a r e   s e l e c t e d   t o g e t h e r   t o   p r e v e n t   c h a n g e s   i n   e r r o r   e f f e c t   o n   m e a s u r e m e n t   p a r t s .   T h i s   i n h i b i t s   g e n e r a t i n g   i n c o m p e t e n t   o f f s p r i n g   a n d   s p e e d s   c o n v e r g e n c e   t o   o p t i m u m   s o l u t i o n .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 5 6   I J R A   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 :     4 9     6 3   5 6     F i g . 6   U n i f o r m   c r o s s o v e r   u s e d   i n   t h e   s e c o n d   h a l f   o f   g e n e r a t i o n s   i n   g l o b a l   s e a r c h   a l g o r i t h m       3 . 6 . 2   M u t a t i o n   T h i s   i s   a n   i m p o r t a n t   o p e r a t o r   f o r   g e n e r a t i n g   n e w   p o p u l a t i o n s   i n   i n t a c t   p o r t i o n s   o f   t h e   s e a r c h   s p a c e .   I t   a l s o   c a n   h e l p   s e a r c h   a l g o r i t h m   t o   p a s s   o v e r   l o c a l   e x t r e m u m s   [ 2 5 ] .   M u t a t i o n   t a k e s   p l a c e   f o r   e a c h   o f f s p r i n g   c o l u m n   w i t h   p r o b a b i l i t y   P m   ( F i g . 7 ) .   E a c h   o n e   o f   t h e   t h r e e   p a i r s   i n   c h r o m o s o m e   c o l u m n   i s   s e l e c t e d   w i t h   p r o b a b i l i t y   1 / 3 .   A   r a n d o m   n u m b e r   i n   t h e   r a n g e   [ - c . m a x x ,   c . m a x x ]   o r   [ - c . M / L , c . M / L ]   i s   a d d e d   t o   o n e   o f   t h e   e r r o r   v a l u e s   o r   µ   c o r r e s p o n d i n g l y ,   i f   i t   d o e s   n o t   v i o l a t e   t h e   v a l i d   r a n g e .   c   i s   a   s m a l l   c o n s t a n t   e . g .   0 . 1 .         F i g . 7   M u t a t i o n   o p e r a t o r   i n   g l o b a l   s e a r c h   a l g o r i t h m   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R A   I S S N :   2 0 8 9 - 4 8 7 2       R e d u c e d   S e a r c h   S p a c e   A l g o r i t h m   f o r   S i m u l t a n e o u s   L o c a l i z a t i o n   a n d   M a p p i n g     ( H .   O m r a n p o u r )   5 7   F o r   m u t a t i o n ,   i t   i s   p r o b a b l e   f o r   a l l   v a l u e s   i n   t h e   c h r o m o s o m e   t o   c h a n g e .   A l l   v a l u e s   o f   e r r o r   i n   t h e   v a l i d   r a n g e   a r e   e x p l o r e d   b y   c h a n g i n g   x ,   y   a n d   Ө .   C h a n g e s   i n   t h e   c o r r e s p o n d i n g   µ   a r e   a d m i t t e d   t o   r e a c h   a   b e t t e r   e r r o r   d i s t r i b u t i o n .   M u t a t i o n   i s   a n   i m p o r t a n t   o p e r a t o r .   A   s e a r c h   a l g o r i t h m   u s i n g   o n l y   c r o s s o v e r   c a n n o t   f i n d   t h e   o p t i m u m   s o l u t i o n   b u t   w i t h   m u t a t i o n   a l o n e   i t   i s   p o s s i b l e .   T h e   r e a s o n   i s   t h a t   c r o s s o v e r   s e a r c h e s   a   s p a c e   c o n f i n e d   t o   c u r r e n t   p a r e n t s   b u t   m u t a t i o n   i s   a b l e   t o   g e n e r a t e   p o p u l a t i o n s   i n   a l l   p o i n t s   o f   s e a r c h   s p a c e .     3 . 2 . 7   S u r v i v o r s   s e l e c t i o n   T h i s   m e t h o d   i s   b a s e d   o n   t o u r n a m e n t   a n d   µ + λ   w h e r e   µ   i s   t h e   p o p u l a t i o n   s i z e   a n d   λ   i s   t h e   o f f s p r i n g   n u m b e r .   A d v a n t a g e   o f   t h i s   s e l e c t i o n   i s   i t s   h i g h   s p e e d   a n d   g u a r a n t e e d   c o n v e r g e n c e   t o   g l o b a l   o r   l o c a l   o p t i m u m .   P a r e t o s   m e t h o d   i s   u s e d   i n   s u r v i v o r s   s e l e c t i o n .   E i g h t y   p e r c e n t   o f   s u r v i v o r   p o p u l a t i o n   i s   s e l e c t e d   f r o m   o f f s p r i n g   a n d   t h e   r e m a i n i n g   2 0 %   c o m e s   f r o m   p a r e n t s .   I n   t o u r n a m e n t ,   q   c h r o m o s o m e s   a r e   s e l e c t e d   r a n d o m l y   a n d   t h e   b e s t   o f   t h e m   i s   c h o s e n   t o   r e m a i n   i n   t h e   n e x t   g e n e r a t i o n .   T o   s e l e c t   µ   s u r v i v o r s ,   t o u r n a m e n t   i s   r e p e a t e d   f o r   8 0 %   o f   p o p u l a t i o n   s i z e   ( µ )   i n   t h e   o f f s p r i n g   p o p u l a t i o n   a n d   f o r   2 0 %   o f   µ   i n   t h e   p a r e n t   p o p u l a t i o n .   A n o t h e r   b e n e f i t   o f   t h i s   m e t h o d   i s   t o   s e l e c t   p r o p e r   p e r s o n s   f r o m   p r e v i o u s   p o p u l a t i o n   t h a t   r e s u l t s   i n   d i v e r s i t y   a n d   c o n v e r g e n c e   a b i l i t y   t o   r e a c h   o p t i m u m   s o l u t i o n   [ 2 6 ] .     3 . 2 . 8   T e r m i n a t i o n   c o n d i t i o n   W e   u s e d   d i s j u n c t i v e   c o m b i n a t i o n   o f   t w o   c o n d i t i o n s   t o   r e a c h   t h e   s o l u t i o n   q u i c k l y   a n d   w i t h   h i g h   p r e c i s i o n ,   u n t i l   t h e   n u m b e r   o f   g e n e r a t i o n s   r e a c h e s   a   m a x i m u m   v a l u e   o r   v a r i a n c e   o f   t h e   f i t n e s s   r e a c h e s   a   l o w e r   t h r e s h o l d .   I f   c o r r e s p o n d e n c e   o r   l o o p   i s   n o t   d e t e c t e d   a f t e r   k   t i m e   s t e p s   ( F i g . 3 ) ,   t h e   g l o b a l   s e a r c h   a l g o r i t h m   i s   c a l l e d   b e c a u s e   d e t e c t i o n   a l g o r i t h m   m i g h t   w o r k   i m p r o p e r l y .   I n   t h i s   c a s e ,   W 2   i n   E q .   7   i s   s e t   t o   0 .     3 . 3   C o m p a r i s o n   w i t h   o t h e r   m e t h o d s   I n   t h i s   s e c t i o n   w e   c o m p a r e   t h e   p r o p e r t i e s   o f   t h e   p r o p o s e d   m e t h o d   w i t h   c u r r e n t   m e t h o d s   ( t a b l e . 1 ) .       T a b l e . 1     C o m p a r i n g   p r o p o s e d   m e t h o d   w i t h   o t h e r   m e t h o d s   E K F   F a s t   s l a m   D P - s l a m   P r o p o s e d   M e t h o d     Y e s   Y e s   N o   N o   L a n d m a r k   H i g h   H i g h   M e d   H i g h   L o o p   c l o s i n g   a n d   c o r r e s p o n d e n c e   H i g h   L o w   H i g h   M e d   T i m e   c o m p l e x i t y   N o   N o   Y e s   N o   L o c a l   m i n i m a   H i g h   H i g h   M e d   L o w   M e m o r y   c o m p l e x i t y   Y e s   Y e s   Y e s   Y e s   C o n v e r g e n c e   G a u s s i a n   A n y   A n y   A n y   E r r o r     m o d e l       E a c h   r o w   c o m p a r e s   o n e   f e a t u r e   o f   a l l   m e t h o d s .   T h e   l a s t   r o w   i n d i c a t e s   t h a t   e r r o r   m o d e l   w h i c h   e n t i r e l y   m i s l e a d s   t h e   r o b o t   p a t h   g e n e r a t i o n   i s   a r b i t r a r y   i n   t h e   p r o p o s e d   m e t h o d .   I t   i s   c l e a r   f r o m   T a b l e .   1   t h a t   t h e   p r o p o s e d   m e t h o d   i s   s u p e r i o r   i n   f e a t u r e s   t o   o t h e r   m e n t i o n e d   m e t h o d s .   F o r   e x a m p l e   t h e   t i m e   r e q u i r e d   t o   p r o c e s s   m a p   i n   F i g .   8 . b   f o r   t h e   p r o p o s e d   a l g o r i t h m   i s   ½   o f   t h e   t i m e   r e q u i r e d   f o r   D P - S L A M   m e t h o d .       4 .   E X P E R I M E N T A L   R E S U L T S   W e   u s e d   t w o   d a t a s e t s   t o   d e m o n s t r a t e   t h e   r e s u l t s   o f   p r o p o s e d   m e t h o d   [ 2 7 ] .   P r i m a r y   m a p   a n d   p a t h   t r a j e c t o r y   w i t h   o d o m e t r y   e r r o r   i s   s h o w n   i n   F i g .   8 .   B y   s e l e c t i n g   1 0   p a r t i c l e s   a n d   a p p l y i n g   t h e   l o c a l   s e a r c h   a l g o r i t h m   f o r   t h e   f i r s t   l o o p   o f   F i g . 8   m a p s   a n d   p a t h s   s h o w n   i n   F i g . 9   a r e   g e n e r a t e d   a f t e r   5 0   m o v e m e n t s .   G l o b a l   s e a r c h   a l g o r i t h m   i s   c a l l e d   a f t e r   a   c o r r e s p o n d e n c e   o r   l o o p   h a s   b e e n   d e t e c t e d .   R e s u l t s   o f   t h i s   a l g o r i t h m   a r e   s h o w n   i n   F i g . 1 0 .   I n   g l o b a l   s e a r c h   a l g o r i t h m   t h e   p o p u l a t i o n   s i z e   i s   1 0 ,   n u m b e r   o f   g e n e r a t i o n s   i s   1 0 0 ,   s i z e   o f   c h i l d r e n   i s   7 * µ   a n d   q   i n   t o u r n a m e n t   s e l e c t i o n   i s   s e t   t o   5 .   P m   a n d   P c   a r e   s e t   t o   0 . 0 5   a n d   0 . 8   c o r r e s p o n d i n g l y .   T h e s e   v a l u e s   a r e   s e l e c t e d   t o   m a x i m i z e   t h e   c o n v e r g e n c e   o f   e x p e r i m e n t s   t o   o p t i m a l   s o l u t i o n .   I t   i s   o b v i o u s   i n   F i g . 1 0   t h a t   t h e   g l o b a l   s e a r c h   a l g o r i t h m   h a s   c o r r e c t l y   c l o s e d   t h e   l o o p s .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 5 6   I J R A   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 :     4 9     6 3   5 8 ( a )     ( b )       F i g . 8   M a p s   a n d   t r a j e c t o r y   u s e d   i n   e x p e r i m e n t s       ( a )     ( b )       F i g . 9   R e s u l t s   o f   t h e   l o c a l   s e a r c h   a l g o r i t h m   f o r   m a p   i n   F i g . 8 . a   ( a )   u s i n g   E q . 1   a n d   ( b )   u s i n g   E q .   2   a s   e v a l u a t i o n   f u n c t i o n     Evaluation Warning : The document was created with Spire.PDF for Python.