TELKOM NIKA , Vol.13, No .1, March 2 0 1 5 , pp. 93~1 0 2   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v13i1.1275        93      Re cei v ed O c t ober 1 3 , 201 4; Revi se d Decem b e r  21, 2014; Accept ed Ja nua ry 8,  2015   Hierarchical-map Updating Approach for Simultaneous  Localization and Mapping of Mobile Robots      Yingmin Yi*,  Zhimin Wan g    F a cult y   of Automation a nd Inf o rmatio n  Engi n eeri ng, Xi’a n U n iversit y  of T e chno log y ,    Xi ’a n71 00 48, Shaa n x i, Chi na    *Corres p o ndi n g  author, e-ma i l :  yi ym@ x a u t.edu.cn       A b st r a ct   For the treme n dous ly incre a si ng of system s t ate in  w ild fiel d, the comput ation a l co mp le xities of   m o bile robot system  should be tak en into account. This paper propos es a hierarchic al- m ap updating  appr oach for  simulta neo us l o cali z a tio n  an d ma ppi ng of  robots. T he basic ide a  of hierarch ica l -ma p is   defin ing tw o ki nds of  ma ps d u rin g  the rec u r s ive u pdati ng process,  n a m e l y  loca l map  ( upp er map) a n d   global   m a p (l ow er m a p). The system states  w ill  be  updat ed  by the pr eset maps . The hi erarchical- m ap  upd atin g proc e ss is just for th e up per  map  a nd the  lo w e r  map is  up date d   after a certa i n  runn ing  ter m . In   the ca lcul atio n, the st ate   d a ta of  the up per map is  far less  t han   t hat  of the   low e r  ma p. It is  vali date d   by th e   exper iments th at, the appro a c h is more o p ti ma l than  other s in co mp utati ona l co mpl e xiti es w h ile e n suri ng   the consiste nc y estimat e .    Ke y w ords : h i erarchic al- m ap  up datin g, co mp utatio nal  c o mpl e xity, si multan eo us l o ca li z a tio n   and   ma p  buil d i ng, mob i l e  robots       1. Introduc tion  The m o ving a nd ma p b u ildi ng in  wild  env ironm ent i s  of  gre a t impo rt ance in th e  re sea r ch  of robot filed.  Due to the l a rge  are a , the syst em  stat es in crea se e x ponentially. The re se arch es  for ro bot SL AM follow th e variation s   of the  appli c ation environ ments, fro m  2-dim ention a l  environ ment  [1] to 3-dime ntional envi r onment  [2], from  stru cture d  enviro n me nt [3] to none- stru ctured e n v ironme n t [4], from ind oor [5] to  outdo or [6] an d ot her  natural n one-structu r e d   environ ment  [7]. For the  SLAM  of ve hi cle  rob o ts, it  is n e cessa r y  to upd ate the  po se  and  m ap  after every ne w ob servatio n [8].  With the in creasi ng of the  feature s  on t he m ap, the   comp utationa l compl e xity increa se s  as well. For the compu t ational pro b l em, res earchers put forward seve ra l map-divi sio n   approa che s  [ 9 ]. The e s sen c e of th e ma p-divisi on a p p roa c h e s is t o  re du ce the   times of u pda ting  the glob al m ap while e n suring th e opti m al estim a te. The ma p-di vision a pproa che s  h a ve two   categ o rie s :  o ne i s  o p e r ati ng o n  the  lo cal  pa rts  of  the ma p, re maining  the   global  refe re nce  coo r din a tes. The Comp re ssed  Extend ed  Kalma n   Filtering  (CEKF) p r opo se d in p ape r [ 10],   addresse s th e local a r ea  data combi n g  app roa c h, lo weri ng th e co mputational  complexity of the   algorith m ; the othe r is the  sub - ma p te chnolo g y und e r  the lo cal  co ordin a te fra m es. Th e eve r y- increa sing p r oblem of matrix es is di scussed in [11].   The EKF a p p r oa ch fo r SL AM is b a sed  on the  minim u m me an  sq uare  erro r, co mpleting   the optimal  re cursio n for  ro bot po se s in t i me dom ain.  But for ea ch  updatin g, the  whol e matrix  is  pro c e s sed, i n crea sing  th e comp utatio nal  com p le xity, w h ic h gre a t ly r e s t r i c t s  th e ap p r oa c h   applying  in th e la rge - scal e  environ ment.  For t he  ever-i ncrea s ing  p r o b lem  of the  EKF-SLAM  wit h   the in cre m en t of the stat es, thi s  pa p e r p r o pos es  a hie r archi c a l -map  upd ating a pproa ch  for  SLAM (HMU-SLAM). Du rin g  the re cursio n process of t he robot, t he  state  spa c e i s  divided to t w o  layers,  nam el y the lo we r-map  (glo bal)  state  sp a c e  and upp er-m ap (lo c al)  sta t e  sp ace.  In the  SLAM alg o rit h m, at eve r y  recursio n  ste p , the  upd ating  step  is ju st fo r updatin g   the upp er  st ate   spa c e.  When  the robot n a v igates out th e uppe r-m ap  area, the n  the lowe r-map i s  upd ated. T h is  algorith m  ca n lowe r the computation d i mensi o n s   effectively so a s  to lowe r the comp utatio nal   compl e xity, makin g  it possi ble of its implementation in  large - scal e e n vironm ent.    The next section p r e s e n ts the p r o c e ss  and o b se rvation  model s u s e d  in ou r  experim ents,  whi c h  sets t he  context fo r the s e  re sult s in  term s  of a 2 - D vehi cl e with  a  ra n ge  beari ng  sensor. The l andmark model  is di scus sed in the  section.  Section III describes  hiera r chi c al-map upd atin g approa ch  for simulta n e ous lo cali zati on and ma p p ing of rob o t s .   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  93 – 10 2   94   Section IV presents the  results of th e simula tio n  experime n ts in terms of  computatio n a l  compl e xities  and e s timate con s i s ten c y. The final se ct ion provid e di scussio n  and  con c lu sio n s.       2. Sy stem model  2.1. SLAM s y stem model  The de scribe d SLAM system is com p o s ed by  rob o t’s po sition an d dire ction a nd the   observed coo r dinate s   on static  enviro n m ent landma r k. The  united  state vector u nder  k  state is  s h ow n  as       1 1 x x n vk vk rk vk k N N x y x y x y                                                                                                                                                                          (1 )                          In the form ula, vk vk r k x ,y ,  r e pr es en t r e sp ec tive ly th e  r o bo t’s  co o r d i na te s  in  tw o- dimen s ion a l spa c e a nd direction a ngle.  The map i s  static, param eter   11 n, , , , NN x yx y T  has n o   time index. The rob o t’s mo vement mode l is rolling mo tion con s trai n t s (i.e., assu ming ze ro wh eel   s lip) [12].      11 11 1 1 co s ( ) x( x , u ) s i n ( ) sin( ) k vk k r k k kv v k k v k k r k k vT rk k B xv T G fy v T G G                                                                                                   (2)                                          The time  int e rval from  1 k to  k  mom ent i s T , spe ed  k v and  driving  an gl e  k G are  con s tant, whi c h con s titutes controll ed qu antity   u, kk k vG T , robot’ s  wh eel ba se  is  B .       2.2. SLAM observ a tion model  The ob se rved  model is  wh e r e  ik z  is the ob servation ve ctor at time k a nd  i h  is the mo del  of the ob se rvation of the  i th land mark.  The ve ctor  ik z  is a ob se rvatio n of the la nd mark lo cation   i p  relative to the robot’s  location vk x . This type of observ ation will be  referred to as a vehicle- landma r k ob servation o r  a VLM observa tion.                                                                       22 () ( ) z( x ) a r ct an iv k iv k iv k i v k ik i k yy rk xx xx y y h                                                                                   (3)                                  The mod e l is not assume d to be perfe ct and unm o delled  sen s o r  characte ri stics a nd  noise  corrupti on a r e l u mpe d  into a  ob se rvation e r ror  vector ik . The  o b se rvation  error vecto r  i s   again ta ken t o  be a tempo r ally uncorrel a ted and  zero  mean ra ndo m sequ en ce.       2.3. Landma r k model  Landm arks a r e fixed and  con s pi cu ou s featur e s  withi n  the enviro n m ent. Landm arks  can   have many  p h ysical form s; corner s,  pla nes, rou gh surfaces, pole s ,  natu r al  o r  artificial  te rrai n   feature s   can  all be  con s i dere d  lan d m a rks if  they  are  rep eatedl y and reli abl y obse r ved b y  a  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Hierarchi c al -m ap Updating Approach for Si m u ltaneous Localization and .... (Yingm in Yi)  95 sen s o r . Exact l y what  co nst i tutes a  lan d m ark i s   dr ive n  by th e p h ysics  of the  ob servin g  sen s or  -  landma r ks a r e con s pi cu o u s through t he eyes of  the ob servin g  sen s or. Thi s  se nsor-cen tric  definition of  a  landm ark m e ans that  it i s   not al ways  po ssi ble to  re ad ily asso ciate  a lan d mark  with   visually perce ived feature s .   Mathemati c al ly, landma r ks are rep r e s e n ted a s   a ve ctor of p a ra meters that  d e fine the   locatio n  and  other prope rti e s of t he landmark. This t hesi s  gen erally  employs the simple st of all  landma r k mo dels: a  lan d m ark is a  st ationary   poi nt like  entity in two  dime nsio ns. A p o i nt  landma r k is d e fined by two  param eters  spe c ifying it s  positio n in ca rtesia n spa c e  with re spe c t to  some  glob al coo r din a te frame. A point  landma r k i s   visible from  a ll viewing a n g les. In ge ne ral,  more  com p le x landmarks  can b e  in corporate d   into the map s  an d  model s empl oyed thro ugh out  this  thes is .   The  i th point l andma r k in t he environm e n t will be  den oted a s   i p and will  be define d   as  follows    T i i i x y    p                                                                                                                                     (4)                                           The rel a tion ship between t he point lan d m ark  state at times k  + 1 a nd k is trivial.   The land mark is stationa ry and so     (1 ) ( ) ii i kk  pp p                                                                                                                (5)                                         Importantly, and in cont ra st to the vehicle m odel, there is no additi ve unce r taint y  term in  the landma r k model.   The vehicl e motion mod e l , the obse r vation model,  and the me asu r ed valu e s  of the  control pa ra meters   u, kk k vG T  , are not exa c t, but are su bject to n o ise, whi c h le a d  to  uncertainty in  the state est i mate. For thi s  re ason,  we  requi re a p r obabili stic filter to re cu rsiv ely  estimate a di stributio n ove r  the  state giv en noi sy information.      3. Hierarchic al-map upda ting algorith m  for SLAM   3.1. Basic id eas of hier ar chical-map   Whe n  the  ro b o t co ndu cts  SLAM in the   wild  enviro n m ent, the m a p data  an d th e sy stem  state  spa c e  will increa se  ex pone ntially. Whe n  the  ro b o t is wo rking  i n  the  wild,  wh at co ncerns a r e   the intere sted  area s a r ou n d  and the  ge neral  obje c ts.  Hen c e, for th e map buil d in g of the rob o t, it  is available  to divide the intereste d  area s  an d the gene ral  obje c ts to hiera r chical maps.   Acco rdi ng to   the re qui rem ents, the  ma p can  be divi ded i n to  N la yers. T he to p  layer i s   den oted  by 1. And  th e bottom  lay e r i s   den oted  by  N. Th e  schem atic gra ph of  the  hie r archi c al  ma p s  i s   s h ow n  in  F i gu r e  1 .           Figure 1. Sch e matic g r ap h of the hiera r chical ma ps  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  93 – 10 2   96   3.2. Upda ting for the hier archical map s   For the p r obl em of com p u t ational co mp lexity  increa se re sulted by  the increme n t of the  state sp ace, the system a r ea is divided i n to tw o part s  durin g the EKF recursion p r ocess, nam e l y  the  up per-m ap state spa c e and   the  l o we r-m ap st at e spa c e.  During  ea ch  st ep of th e SL AM  recursio n ste p , the updati ng step j u st  update s   the uppe r-m ap state  spa c e. Whe n   the  ro bot  navigate s  out  of the up per-map a r ea, th en the lo we r- map i s  up dat ed. As it i s  sh own i n  Fig u re  2,  the recta ngul ar Area A is t he initial upp er-m ap stat e  spa c e; Are a  B is the initial lower-ma p st ate  spa c e. When  the sen s o r  of the m obile ro bot observe s the feature s  o f  the lower-m ap state space  while navigating in the upper-map  state space,  the lower m ap  will be updated. Besides, the  uppe r-m ap st ate spa c e a n d  the lowe r-m ap state spa c e are re-divid ed, as sho w n  in Figure 2.   The HM U-S L AM algorithm  is described  as follo ws:   Initialisation  and p r edi ctio n: the uppe r-map  a r ea i s  indepe nde nt from the lo wer-ma p   area. Th e sta t e vectors are  divided to two parts .          Figure 2. Upd a ting for the state spa c e s       To p Lo w To p To p L o w Lo w n n X ,X R , X R X     X                                                                                                    (6)                                                                           whe r e, n presents the num ber of  the virtual feature s . The cova ria n c e matrixe s  a r e divided a s   follows :     TT TL LT LL n PP E ( X X )(X X) R PP     P                                                                                  (7)                                             The auxiliary matrix: Top L o w To p T o p L o w ,, * LL ,, , nn n n n RR Q R     The initial time  1 k :    * 11 1 L L 1 ( ) , ( )0 , ( )0 , ( )0 kI k k Q k                                                                                                       (8)                                             Different fro m  the EKF-SLAM algo rithm,  the HM U-SLAM  alg o rithm  con d u cts th e  predi ction  in t he u ppe r-m a p  area. At thi s  time,  only  Top T T , X P  are i n volved i n  the  pre d icti on. Th e   auxiliary matrix has a recursiv e equation as the followi ng.    TT () ( 1 ) kJ k                                                                                                                                  (9)                                    () ( 1 ) kk                                                                                                                                  (10)                                 Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Hierarchi c al -m ap Updating Approach for Si m u ltaneous Localization and .... (Yingm in Yi)  97   () ( 1 ) kk                                                                                                                                  (11)                                     TT To p T o p To p (/ ) | ( ) J fX X k                                                                                                              (12)                                  ** LL L L LL () ( 1 ) ( ) Qk Qk Qk                                                                                                               (13)                                    Upd a ting: the  upd ating i s   divided to  up per-map  up d a ting a nd l o wer-m ap  upd ating. Th e   uppe r-m ap  u pdating  is ju st for the  lo cal  area s a nd th e lo we r-ma p   updatin g i s   condu cted  via  the  recursion of the auxiliary  matrix.    () ( ( )( 1 ) ) kI k k                                                                                                                           (14)          T1 To p T o p () () () () kH k S k H k                                                                                                                   (15)         T ( ) (1 ) ( 1 ) ( ) (1 ) kk k k k                                                                                                     (16)       To p () () ( ( ) , ) Z ky k h X k k                                                                                                                        (17)    T To p T T T o p () () ( ) ( ) Sk H k P k H k R                                                                                                                (18)    To p T o p To p () ( / ) | () Hk h X X k                                                                                                                   (19)    TT () () k Pk k                                                                                                                                          (20)    TT 1 To p ( ) (1 ) ( 2 ) (1 ) ( 1 ) (1 ) kk k H k S k Z k                                                                           (21)                                      Upd a ting of  Low T L L L ,, XP P : Once the  are a  of the  lower state  sp ace i s  o b served  (a t time K2   here ) , the lower-m ap up dat ing is cond uct ed via the recursi on form ul a.      TL 2 2 TL 1 () () ( ) Pk k P K                                                                                                                     (22)         * L L 2 L L 1 TL 1 2 TL 1 L L 2 () ( ) ( ) () ( ) () Pk Pk Pk k P k Q k                                                                             (23)       Low 2 L o w 1 2 () ( ) ( ) Xk X k k                                                                                                                 (24)                                  3.3. Steps fo r HMU-SLAM   HMU-SLAM  pro c e ss i s  pe rforme d as fol l ows.  Step1 Initialisation ：  Initiall y define  and   assign  value s  for th e p r edi ction l o cation,  syste m   covari an ce matrixes,  hi e r archi c al are a s,  t he  auxi liary matrix,  the sy stem  pro c e s s no ise  covari an ce  matrix, the system observation noise  covaria n ce matrix, control variable s ,  the  maximum ob servatio n dist ance and the  time interval.  Step2 Location pre d ictio n  for the robo t:  predict the curre n t location and co varian ce  matrix of the robot ac cording to the pos i tion  es timat e , c o varianc e  matr ix, auxili ary matrix  and  moving mod e l  of the former moment in t he upp er-ma p  area.   Step3 Pra c tical ob se rvatio n: Obtain th e  pra c ti cal ob servatio ns by  the ob se rvations  of  the environ m ent feature s  u s ing the  sen s ors of the rob o t.    Step4 Predi ct ion ob servati on: Cal c ulate  the  predi ctio n observation s of the environment   feature s   usi n g the  mea s u r ement m odel  acco rdin g  to  the  coo r di na tes of  the l o cation p r edi cti on  and ob se rvation enviro n me nt f eature s  on  the lower m a p.  Step5 Data  asso ciation (relating ) : con duct  the dat a asso ciation  for the observation   feature s  of the uppe r map.   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  93 – 10 2   98   |1 1 ˆˆ () ( , ) kk k k In n z k h x m                                                                                                                        (25)                           1 kk k k DI n n S I n n T                                                                                                                            (26)      Step6 State updatin g: the stat e updati ng is divide d  to upper-ma p  updatin g a nd lower- map up dating .  The uppe r-map up dating  is just for  the  associ ated f eature s . The  data is g ene rally  far less than t hat of the lower map.   The lower-m ap updatin g is gene rally condu cted a fte r a certai n distance of mov e ment of  the robot, to modify the data of the global map.  Step7 State increme n ting: Add  the ne w observed fe ature s  to the m ap. The HMU-SLAM   algorith m  i s  recu rsive  by  steps i n   seq u e n ce  of  p r edi ct ion, ob se rvation,  data  a s so ciation,  upp er- map upd ating  or lowe r-map  updating a n d  state increm enting.     1 (, ) new kn k v k h xz x                                                                                                                        (27)                                   T k k new k    x x x                                                                                                                               (28)      4. Results a nd Analy s is  The initial state and co varian ce  ma trix of the  experim ents are  0/ 0 ˆ (3 , 1 ) xz e r o s ， 0/ 0 (3 ) Pz e r o s , res p ec tively. In the initia lisation pro c e ss, the noise co varian ce an d the observati on  cov a ri an ce a r e  22 [0 . 3 , ( 3 / 180) ] Qd i a g ,  22 [0. 1 , ( / 180) ] Rd i a g ,respe ctively.The expe riment s also  perfo rmed th e cla ssi c EKF -SLAM, Fast SLAM, UKFS LAM , for co mpari ng with  and an alyzin g the  prop osed alg o rithm. Figure 3 sho w s cl assical  EKF-SLAM algorit hm. Figure 4  shows cl assica l   Fast-S LAM a l gorithm. Fig u re 5  sho w s  the hiera r chi c al-map SLA M  of the pro posed alg o rit h m.  Figure 6 sh o w s the two-la yer map SLA M .  The m ap is built by usin g the prop ose d  algorith m .             Figure 3. The  map of the robot EKF-SL A M  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Hierarchi c al -m ap Updating Approach for Si m u ltaneous Localization and .... (Yingm in Yi)  99     Figure 4. The  map of the robot Fa st-SL A M          Figure 5. State spa c e u pda ting gram       The data p r oce s sing q u antity of a single-step  cal c ulatio n is a n  importa nt index for  deci d ing th e  efficien cy of  an alg o rithm   [10]. For  the   large - scale m ap, to verify the comp utation  compl e xity of the algorith m , the experi m ents al so p e rf orm ed t he  cla ssi c E K F - S LA M,  Fast S L A M   and  UKFSL A M re spe c ti vely in the  same  envi r o n ment, for compa r ing  wit h  the  pro p o s ed   algorith m  in this pap er. Fi gure 7  sho w s the ti me co nsumi ng average s of the above algo rith ms   unde r 50 si ng le-ste p cal c ul ations. i pre s ents ste p  len g th. T presen ts time (unit: s).     Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  93 – 10 2   100     Figure 6. Hierarchical map p ing of rob o t SLAM          Figure 7. Co mpari s io n for singl e-st ep consusi ng of the algo rithm s       As it can be  seen from  Figure 7, under t he sam e  con d itions,  the single - step time  con s umi ng  curve of the   FastSLAM  algorithm  goe s top; UKFSL A M is infe rio r ; EKFSLAM is  bene ath UKF S LAM; HM USLAM is  at the bottom.  T h is in dicates the p r op ose d  algo rithm  has  minimum  sin g le-step time  con s umin g,  optimal  tha n  the other  algorith m s in  comp utation a l  c o mplexity.         For the prop ose d  algo rith m, the estimation issue of  con s isten c y sho u ld be co nsid ere d .  For line a r  Gau ssi an filter, the filter perfo rm an ce can b e  chara c te rized  through  NEES  (no r mali zed e s timation e rro r squ a red) [1 1].    1 xx P x x || | ˆ ˆ () () kk k k k k k k k  T                                                                                         (29)                                           Und e r the hy pothe sis that  the filter is co n s i s tent an d approximately linear-Ga u ssian,  NEES obeys  2 distrib u tion.  Con s i s ten c y of the algo rithm is eval ua ted by perfo rming N time s  Monte Carlo runs .  The  algorith m performance  indicato rs are evaluated  by  the average NEES.  Whe n   N  ， k  approache s to the state vector  dimen s ion.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Hierarchi c al -m ap Updating Approach for Si m u ltaneous Localization and .... (Yingm in Yi)  101   1 1 N ki k N i                                                                                                                      (30)     Given the hy pothe sis of a  con s i s tent linear-G au ssi a n  filter,  k N  has  a  2  dens i ty with  N dim ( x k ). Thu s , for the 3 - dime nsi onal  robot p o se , with N=50 , the 95% prob ability   c o nc en tr a t io n r e g i on  fo r k is  boun ded by t he interval [2. 36, 3.72]. If  k  rise s si gnifica ntly higher  than the  upp er b oun d, the filter is  opt imistic, if it tend s bel ow  t he lo we r bo u nd, the filter  is  c o ns er va tive .  To verify the  con s i s ten c y estimate, a s   to EKF-SLAM, FastSLA M , UKFSLA M and the  prop osed alg o rithm, we co ndu cted 50  MonteCarl o  runs on the ro bot for each. Figure 8 sho w s  the NEES consi s tency esti mate cu rves.  As it can be seen from  Figure 8, the  NEES curves o f   the algorithm s are alm o st within [2.36 ， 3.72]. Hence, they are all  con s i s ten c y estimate s. From   the ab ove, th e p r opo se d  algorith m  i s   optimal in  co mputational  complexity wh ile en su ring  the   c o ns is tenc y es timate.       5. Conclusio n   For the  probl em of the  ever-i ncrea s in g  com putation a l co mplexity re sulted  by the eve r - increa sing  st ate spa c e i n   the large - scal e environm e n t, this p ape r pro p o s e s  a   hiera r chi c al-map  updatin g alg o rithm for si multaneo us l o cali zatio n  and mappi ng.  Acco rding t he algo rithm, the   robot  will  buil d  multiple  ma p laye rs at m ap b u ild in g.  Duri ng  state   updatin g, onl y a fe w  state s  of   the uppe r ma p are up date d , thus lowe ri ng the com p utational co m p lexity of the  algorithm. T h e   experim ents  validated that the pr opo se d algorithm h a s the minim u m com putational co mplex i ty  while e n surin g  the co nsi s t ency e s timat e . The idea s  of this pap er  provide  a me aningful  clue  for  the map build ing of the larg e-scal e un kn own e n viron m ent for ro bo t.          Figure 8. NEES c ons is tenc y es timate  curves  of the algorithms      Ackn o w l e dg ments   This  work  was  supp orte d  by National  Natural Sci ence Fou n d a tion of Chi na (No.  5127 5405 ) a nd the scie n c e research  prog ram s   of  edu cation d e partme n t of Shaanxi Prov ince  (201 3JK 107 8 ) .      Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  93 – 10 2   102 Referen ces   [1]  Yang P.  Effici ent partic l e fi lter al gorithm f o r  ultraso n ic se nsor-b ased  2D  rang e-on l y  si multan eo u s   local i sati on a n d  mapp ing  app licatio n.  IET Wi reless Sensor  System s.  20 12 ; 2(4): 394 -40 1 .  [2]  Bosse M, Zlot  R, Flick PZ. Desi gn  of a  Spr i n g -Mou n ted  3-D  Ra nge  Se nsor   w i th  App licati o n to M obi le   Mapp ing.  IEEE  T r ansactions  on Ro botics.  2 012; 28( 5): 110 4-11 19.   [3]  Mitch B, Sal a h  S. Architectur e s for C oop er ativ e  Air bor ne Simulta neo us Loca lisati on a nd  Ma pp ing.   Journ a l of Intell ige n t and R obo tic Systems.  20 09;   55(4): 2 67- 297.   [4]  W e izhe n Z ,  Miro JV, Diss ana y a ke G. Information-Efficient 3-D  Vis ual S L AM for  Unstructure d   Domains.  IEEE Transactions  on Robotics.  2 008; 24( 5): 107 8-10 87.   [5]  S T h run, D Fox, W  Burg ard.   A pro bab ilisti c  appr oac h to  concurr ent m app ing  an d l o calizati on f o r   mobil e  ro bots.  Machi ne Lear n i ng.  19 98 ;   (31) : 29-53.  also  a ppe ared  in  Aut ono mous Rob o ts  5. 19 98;   253- 271 (j oi nt issue).  [6]  Jose G, E dua rdo  N, Step ha n B. A u tonom ous  Navi gati o n a n d  Map  b u ild in g Us in g  Laser  Ra ng e   Sensors i n  Outdoor Ap plic atio ns.  Journa l of Rob o tic Systems.  20 00;   17( 1 0 ): 565-5 83.   [7]  Jose G, Eduar do N, Juan N, F a vio M. Navig a ti on a nd Map p in g in Lar ge u n structured En vironme n ts .   T he Internati o n a l Jour nal of R obotics R e sear ch.  2004; 2 3 (4) :  449-47 2.  [8]  Si-Yao F ,  Xi n- Kai K, Rui Z ,  Guo-She ng Y,  Z eng-Gua ng  H.  Compress iv e sensi ng a p p r oach b a se d  ma pp ing  an d l o cali z a tio n  for  mo bil e  ro bot in  an in do or w i reless se nsor  n e tw ork . 2010 I n ternati o n a l  Confer ence  on  Net w o r ki ng, Sensi ng a nd Co ntrol. Chic ago, USA,  IEEE. 2010: 122- 12 7.  [9]  Bai-F an  C, Z i -Xi ng  C, Z h i-R o ng Z .   A hybr id  data ass o ci atio n ap pro a ch for  mo bi le ro bot  SLAM . 2010  Internatio na l C onfere n ce o n   Contro l Autom a tion  a nd S y st ems. Gy eo ng g i -do, Kore a, IEEE. 2010:  190 0-19 03.   [10]  Jose G, Edu a rdo N.  I m pr ovin g Co mput ation a l a nd  Memory  Re qu ire m ents of  Simulta neo us   Loca l i z a t i on  an d Map B u il din g  Algorit h m s . Proceedings of the 2002 IEEE  international Conference on  Robotics 8 Automation .  Washingto n , DC, IEEE. 2002: 27 3 1 -27 36.   [11]  Y Bar-Sh a l o m,  XR  Li, T  Kiru bara j an.   Estimation  w i th a p p l icatio ns to  trac king  an d  nav ig ation . John  W ile y   an d Son s . 2001: 23 4-2 35.   [12]  R Smith, M Self, P Chees em an. A stochasti c map for unce r tain spati a l rel a tions hips.  In International  Sym p osium  of Robotics Research.  198 7: 46 7-47 4.   Evaluation Warning : The document was created with Spire.PDF for Python.