Page 13 - Introduction to AI Robotics

xiv
9.5 Case Study of Topological Navigation with a Contents
Hybrid Architecture 338
9.5.1 Path planning 339
9.5.2 Navigation scripts 343
9.5.3 Lessons learned 346
9.6 Summary 348
9.7 Exercises 348
9.8 End notes 350

10 Metric Path Planning 351
10.1 Objectives and Overview 351
10.2 Configuration Space 353
10.3 Cspace Representations 354
10.3.1 Meadow maps 354
10.3.2 Generalized Voronoi graphs 357
10.3.3 Regular grids 358
10.3.4 Quadtrees 359
10.4 Graph Based Planners 359
10.5 Wavefront Based Planners 365
10.6 Interleaving Path Planning and Reactive Execution 367
10.7 Summary 371
10.8 Exercises 372
10.9 End Notes 374
11 Localization and Map Making 375
11.1 Overview 375
11.2 Sonar Sensor Model 378
11.3 Bayesian 380
11.3.1 Conditional probabilities 381
11.3.2 Conditional probabilities for P (Hjs) 384
11.3.3 Updating with Bayes’ rule 385
11.4 Dempster-Shafer Theory 386
11.4.1 Shafer belief functions 387
11.4.2 Belief function for sonar 389
11.4.3 Dempster’s rule of combination 390
11.4.4 Weight of conflict metric 394
11.5 HIMM 395
11.5.1 HIMM sonar model and updating rule 395
11.5.2 Growth rate operator 398