(13) (15) Elastc Band Bubble Band (16) Real-Tme A RTA (17) Laser Range Fnder: LRF Real-Tme A* 5 6 Illustraton of workspace and proposed graph- F

Size: px

Start display at page:

Download "(13) (15) Elastc Band Bubble Band (16) Real-Tme A RTA (17) Laser Range Fnder: LRF Real-Tme A* 5 6 Illustraton of workspace and proposed graph- F"

えのみうら
5 years ago
Views:

1 D IEEJ Transactons on Industry Applcatons Vol.131 No.1 pp.1 9 DOI: /eejas Autonomous Varable-Resoluton Map Buldng for Moble Robots n Unknown Envronments Jngyu Xang, Non-member, Yuch Tazak, Non-member, Shnkch Inagak, Non-member, Tatsuya Suzuk, Member Ths paper presents a method that allows smultaneous map buldng and path plannng for moble robots n unknown envronments. A graphcal representaton of a workspace n varable resolutons s constructed usng measurement data obtaned by omndrectonal dstance sensors. At the same tme, a search for a feasble path to the target destnaton s executed usng the constructed graph map. The proposed method s evaluated by performng smulatons and experments usng an omn drectonal moble robot equpped wth laser range fnders. Keywords: Sensor-based Navgaton, Graph Map, Path Plannng, Varable-Resoluton 1. (1) (1) (2) Smultaneous Localzaton and Map Buldng SLAM (3) (5) SLAM Dept. of Mech. Sc. & Eng., Nagoya Unversty Furo-cho, Chkusa-ku, Nagoya, (6) (8) (9) (12) c 2011 The Insttute of Electrcal Engneers of Japan. 1

(13) (15) Elastc Band Bubble Band (16) Real-Tme A RTA (17) Laser Range Fnder: LRF 2 3 4

1. (L W H)=(420 400 630) Omn-drectonal camera Personal computer DC motor 3 Omn-wheel 3 Moble

2 (13) (15) Elastc Band Bubble Band (16) Real-Tme A RTA (17) Laser Range Fnder: LRF Real-Tme A* 5 6 Illustraton of workspace and proposed graph- Fg. 2. map Laser range fnder 2 Fg. 1. (L W H)=( ) Omn-drectonal camera Personal computer DC motor 3 Omn-wheel 3 Moble robot for experment 2. Fg. 1 DC 500mm/s LRF Fg. 2 LRF C-space C-space 2 IEEJ Trans. IA, Vol.131, No.1, 2011

3 Table 1. Defntons of terms and symbols C-space (x, y) p (n) : C-space n G C-space n p S : n S : p S p G : n G : p G (x, y) θ C-space C-space C-space Confguraton Obstacle C-space C-space 2 C-space (x, y) 2 C-space Fg. 2 C-space Table 1 Fg. 2 C-space C-space (x, y) n p (n) (18) (19) n G n G Fg. 3 Intate searchng at Start node Clear heurstc cost Has current node been arrved at before? Yes Chap.4 No Sensng Sec.3.1 Cell generaton Sec.3.2 Node generaton Lnk generaton Goal n cell? RTA* search No A: Decde next node B: Update heurstc cost C: Move to next node Fg. 3. Yes Move to Goal End Flowchart of overall procedure RTA (17) RTA 4 RTA n S p G n G n G p G 4 n G Fg. 4 R max C-space 3 IEEJ Trans. IA, Vol.131, No.1, 2011

4 Confguraton obstacle Blnd spot Cell of node n Cell boundary Node n Algorthm: Cell generaton STEP1 R (n) 0 R (n) 0 R max R (n) 0 := R max. (5) Moble robot Fg. 4. Measured dstance D (n) (θ) and cell radus R (n) R (n) n θ R 1 (0 θ < 2π) D (n) (θ) C-space n θ D (n) (θ) := R max Fg. 4 n C (n) C (n) = { p p p (n) mn ( D (n)( arg(p p (n) ) ), R (n))}. (1) arg( ) p (n) R (n) R (n) ˆR (n) = max r R (n) = max ( R mn, mn(r max, ˆR (n) ) ), (2) s.t. 1 2π 2π 0 max ( r D (n) (θ), 0 ) dθ R th. (3) ˆR (n) R th θ (3) max ( r D (n) (θ), 0 ) (3) ˆR (n) (2) R (n) R mn R th R th = 0 ˆR (n) R mn R th 3 3 R th (3) ˆR (n) (3) (3) 1 m 1 max ( ˆR (n) D (n) (k θ), 0 ) R th. (4) m k=0 m θ θ [ ] m m = [2π/ θ] (4) (2) R (n) STEP1 3 STEP2 STEP4 STEP3 1 m 1 max(r (n) D (n) (k θ), 0) R th, (6) m k=0 R (n) R mn. (7) STEP3 + 1 R (n) STEP2 R (n) STEP4 = 1 m k=0 m 1 mn ( D (n) (k θ), R (n) 1). (8) R (n) = max(r (n), R mn ). (9) mn ( D (n) (0), D (n) ( θ),..., D (n)( (m 1) θ ) ) R (n) R (n) 1 (10) R (n) R (n) (6) R (n) R th (7) R (n) R mn R (n) n Fg. 4 R (n) A 1 3 (Fg. 5) Rule: Node generaton A 1 A 2 A 3 A 2 θ f (θ) = mn(d (n) (θ), R (n) ) f (θ) A 3 4 IEEJ Trans. IA, Vol.131, No.1, 2011

5 Rule A-1: Node generaton pont Cell Confguraton obstacle Wdth at entrance of narrowest path Goal Current node Rule A-2: Node generaton ponts Confguraton obstacle Rule A-3: Node generaton prohbted regon Current node Current node Exstng node (a) bad case (b) Good case Fg. 7. Decson ndcator of R mn and R th Fg. 5. Node generaton rules Current node Exstng node (a) A node s nsde the cell of another node. (a) Search phase (b) Update and move Fg. 8. Image of path plannng usng RTA Fg. 6. (b) Two cells overlap, no obstacle n-between. (c) Obstacles exst between two nodes. Lnk generaton rule B (Fg. 6) Rule: Lnk generaton B Fg. 6(a),(b) c C-space Confguraton obstacle C-space 3 3 R mn R th Fg. 7 d r Fg. 7 C-space (3) ˆR (n) = 2R th. (11) R (n) (2) R (n) = max ( R mn, 2R th ). (12) R (n) < d r R mn < d r, (13) 2R th < d r. (14) R mn R th IEEJ Trans. IA, Vol.131, No.1, 2011

6 A (20) (17) (21) (24) RTA (17) RTA RTA L n n l(n, n ) N (n) k (k 0) N (n) 0 := n, N (n) k k 1 = {n l(ˆn, n ) L, ˆn N (n) k 1, n =0 N (n) }. (15) n k Algorthm: RTA* search n c d g(n, n ) h (n) f (n, n ) n n n n n STEP1 h (n) n S n c STEP2 n( N (n c) 1 ) f (n c, n) f (n c, n) n (Fg. 8(a)) f (n c, n) = g(n c, n) + h (n), n = arg mn n N (nc) 1 f (n c, n). (16) h (n) n h (n) = { mn g(n, nd+1 ) + h } (n d+1). (17) n d+1 N (nc) d+1 h (n d+1) n d+1 h (n d+1) = n d+1 p G 2 n d n d d (17) d = 0 h (n) = n p G 2 n d n G h (n) = g(n, n G ) STEP3h (n c) (Fg. 8(b)) h (n c) = mn f (n c, n). (18) n N (nc) 1 \{n } STEP4 n c n n n c STEP2 4 Fg. 3 RTA search A,B C STEP3 R mn RTA Table 2,3 15 RTA Table 2 d r R mn R th RTA d N (n c) 1 d d = 0 θ mm Table 2 R mn Fg. 9 p S p G R mn R th 100 Fg. 9 0 < R th < R mn /2 R mn 6 IEEJ Trans. IA, Vol.131, No.1, 2011

Table 2. Condton settngs for R mn wth 0 < R th < d r /2 Case Parameter settng Success rate Average of dfference to Case 1-2 1-1 0 < R mn < d r /2 100% +3.

Condton settngs for R th wth d r /2 R mn < d r Case Parameter settng Success rate 2-1 0 < R th < d r /2 100% 2-2 d r /2 R th < d r 92% 2-3 d r R th < 3d r /2 71% p G p G d r Fg. 10. Graph-map constructed by smulaton n large envronment p S (a)case 1-1 Fg.

9(b) Table 3 R th Fg. 9 p S p G R mn R th 100 1 st. Start 2400 Fg. 11. Landmark Obstacle 1 1 st. tral 6000 2 nd.goal Obstacle 2 Obstacle 3 Landmark Envronment for experment 2 nd.

7 Table 2. Condton settngs for R mn wth 0 < R th < d r /2 Case Parameter settng Success rate Average of dfference to Case < R mn < d r /2 100% +3.1 (steps) 1-2 d r /2 R mn < d r 100% 1-3 R mn = d r 87% 0.9 (steps) 1-4 d r < R mn < 3d r /2 76% 2.1 (steps) 1-5 3d r /2 R mn 2d r 70% 4.3 (steps) Table 3. Condton settngs for R th wth d r /2 R mn < d r Case Parameter settng Success rate < R th < d r /2 100% 2-2 d r /2 R th < d r 92% 2-3 d r R th < 3d r /2 71% p G p G d r Fg. 10. Graph-map constructed by smulaton n large envronment p S (a)case 1-1 Fg. 9. p S (b)case 1-3 Result of smulaton p G 0 < R mn < d r. (19) (13) p G p S p G p G Case 1-2 (19) R mn Case 1-1 Fg. 9(a) Fg. 9(a) p S p G R mn Case 1-3 R mn = d r p G Fg. 9(b) Table 3 R th Fg. 9 p S p G R mn R th st. Start 2400 Fg. 11. Landmark Obstacle 1 1 st. tral nd.goal Obstacle 2 Obstacle 3 Landmark Envronment for experment 2 nd. tral 1 st.goal 2 nd.start (mm) d r /2 R mn < d r R th p G 0 < R th < d r /2. (20) (14) Case 2-2, 3 R (n) R mn Fg. 9(a) 20m 20m Fg. 10 Fg RTA 5 2 (Fg. 1) 7 IEEJ Trans. IA, Vol.131, No.1, 2011

Start Start (a) Frst tral Goal (b) Second tral (c) Thrd tral

Graph-map constructed by the moble robot (a,b) and path of the

depth set as 5 (c) 500mm/s 2 500mm/s RTA d = 0 d 1 LRF θ 0.

8 Start Start (a) Frst tral Goal (b) Second tral (c) Thrd tral Goal Start Goal Fg. 12. Graph-map constructed by the moble robot (a,b) and path of the moble robot usng path-plannng on the graph-map wth the search depth set as 5 (c) 500mm/s 2 500mm/s RTA d = 0 d 1 LRF θ 0.36 R max LRF 4000mm R mn (19) 300mm R th (20) 40mm Fg. 11 C-space LRF C-space Fg. 12 Fg. 12(a) C-space Obstacle3 R (n) R (n) Obstacle1,3 A 2 B RTA Obstacle2,3 R (n) R mn RTA Fg. 12(b) Fg. 12(b) d = 5 Fg. 12(c) 6. 8 IEEJ Trans. IA, Vol.131, No.1, 2011

9 1 :, Vol.19, No.8, pp , I.Kamon and E.Rvln: Sensory-Based Moton Plannng wth Global Proofs, IEEE Trans. on Robotcs and Automaton, Vol.13, No.6, pp , M.W.G.Dssanayake, P.Newman, S.Clark, H.F.Durrant-Whyte and M.Csorba: A Soluton to the Smultaneous Localzaton and Map Buldng(SLAM) Problem, IEEE Trans. on Robotcs and Automaton, Vol.17, No.3, pp , L.M.Paz, P.Pnés, J.D.Tardos, and J.nera: Large-Scale 6-DOF SLAM Wth Stereo-n-Hand, IEEE Trans. on Robotcs, Vol24, No.5, pp , A.Angel, D.Flat, S.Donceux, and J-A.Meyer: Fast and Incremental Method for Loop-Closure Detecton Usng Bags of Vsual Words, IEEE Trans. on Robotcs, Vol24, No.5, pp , R.Brooks and T.Lozano-Perez: A subdvson algorthm n confguraton space for fndpath wth rotaton, Proceedngs of the 8th Internatonal Conference on Artfcal Intellgence, pp , S.Kambhampat and L.S.Davs: Multresoluton path plannng for moble robots, IEEE Journal of Robotcs and Automaton, Vol.2, No.3, pp , C.O Dunlang and C.K.Yap: A retracon method for plannng the moton of a dsk, J.Algorthms, No.6, pp , V. Boor, M. H. Overmars, A. F. van der Stappen: The Gaussan Samplng strategy for probablstc roadmap planners, IEEE Int. Conf. Robotcs and Automaton, pp , R.Bohln, L.E.Kavarak: Path Plannng Usng Lazy PRM, IEEE Int. Conf. Robotcs and Automaton, pp , L.E.Kavrak, P.Svestka, J.-C.Latombe, M.H.Overmars: Probablstc Roadmaps for Path Plannng n Hgh-Dmensonal Confguraton Spaces, IEEE Trans. Robotces and Automaton, Vol.12, No.4, pp , S.Behnke: Local Multresoluton Path Plannng, Robot Soccer World Cup VII, LNCS 3020, pp , Sprnger, H.Noboro, T.Nanwa, S.Armoto: A Quadtree-Based Path-Plannng Algorthm for a Moble Robot, Journal of Robotcs Systems, Vol.7, No.4, pp , G.K.Kraetzschmar, G.P.Gassull, K.Uhl: Probablstc Quad-trees for Varable-Resoluton Mappng of Large Envronments, Proceedngs of the 5th IFAC/EURON Symposum on Intellgent Autonomous Vehcles, S.Qunlan and O.Khatb: Elastc Bands:Connectng Path Plannng and Control. In Proceedngs of IEEE Internatonal Conference on Robotcs and Automaton, Atlanta, Georga vol.2, pp , R.Korf: Real-tme heurstc search, Artfcal Intelgence, Vol.42, No.2-3, pp , B.Kupers, J.Modayl, P.Beeson, M.Macmaho and F.Savell: Local Metrcal and Global Topologcal Maps n the Hybrd Spatal Semantc Herarchy, In Proceedngs of IEEE Internatonal Conference on Robotcs and Automaton, pp , T.B.Kwon, J.B.Song: Real-tme buldng of a thnnng-based topologcal map, Intellgent Servce Robotcs, Vol.1, No.3, pp , P.E.Hart, N.J.Nlsson and B.Raphael: A Formal Bass for the Heurstc Determnaton of Mnmum Cost Paths, IEEE Trans. Systems Sc. Cybernet., Vol.4, No,2, pp , A.Stentz: Optmal and effcent path plannng for unknown and dynamc envronments, In Proceedngs of the IEEE Internatonal Conference on Robotcs and Automaton, pp , A.Stentz: The Focussed D Algorthm for Real-Tme Replannng. In Proceedngs of the Internatonal Jont Conference on Artfcal Intellgence, pp , S.Koeng and M.Lkhachev: D Lte. In Proceedngs of the Natonal Conference on Artfcal Intellgence, pp , R.Phllppsen: A Lght Formulaton of the E Interpolated Path Replanner. Techncal Report. Autonomous Systems Lab. Ecole Polytechnque Federale de Lausanne IEEE Honda Research Insttute Europe (Germany) 2009 IEEE Fnalst of the SICE Annual Conference Young Author s Award IEEE U.C.Berkeley ICCAS Outstandng paper award, IEEE 9 IEEJ Trans. IA, Vol.131, No.1, 2011

3 1, 1, 1, 1 3D Environment Measurement Using Binocular Stereo and Motion Stereo by Mobile Robot with Omnidirectional Stereo Camera Shinichi GOTO 1, R

3 1, 1, 1, 1 3D Environment Measurement Using Binocular Stereo and Motion Stereo by Mobile Robot with Omnidirectional Stereo Camera Shinichi GOTO 1, R 3 1, 1, 1, 1 3D Envronment Measurement Usng Bnocular Stereo and Moton Stereo by Moble Robot wth Omndrectonal Stereo Camera Shnch GOTO 1, Ryosuke KAWANISHI 1, Atsush YAMASHITA 1 and Toru KANEKO 1 1 Department