1.Lecture 8 Mapping 5 April, 2005 UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

2.Quiz 5 1.What is the most significant integration error in dead reckoning? 2.State two requirements for a good landmark. 3.Give two examples of navigation in nature. Are these examples using dead-reckoning, landmarks, or other techniques? 4.What is perceptual aliasing? What are some methods to combat it? 5.Name one issue each with single position, and multiple position, belief representations. UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

3.Overview • Why do we map? • Spatial decomposition • Representing the robot • Current challenges UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

4.Mapping • Represent the environment around the robot • Impacted by robot position representation • Relationships – Map precision must match application – Precision of features on map must match precision of robots data (and hence sensor output) – Map complexity directly affects computational complexity, and reasoning about localization and navigation • Two basic approaches – Continuous – Decomposition (discretization) UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

5.Environment representation • Continuous metric -> x, y, theta • Discrete metric -> metric grid • Discrete topological -> topological grid • Environmental modeling – Raw sensor data • Large volume, uses all acquired information – Low level features (e.g. lines, etc) • Medium volume, filters out useful information, still some ambiguities – High level features (e.g. doors, car) • Low volume, few ambiguities, not enough information UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

6.Continuous representation • Exact decomposition of environment • Closed-world assumption – Map models all objects – Any area of map without objects has no objects in corresponding environment – Map storage proportional to density of objects in environment • Map abstraction and selective capture of features to ease computational burden UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

7.Continuous representation • Match map type with sensing device – For laser ranger finder, may represent map as series of infinite lines – Fairly easy to fit laser range data to series of lines UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

8.Continuous representation • In conjunction with position representation – Single hypothesis: extremely high accuracy possible – Multiple hypothesis: • Either, depict as geometric shape • Or, as discrete set of possible positions • Benefits of continuous – High accuracy possible • Dangers – Can be computationally expensive – Typically only 2D UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

9.Decomposition • Capture only useful features of world • Computationally better for reasoning, particularly if map is hierarchical UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

10.Exact cell decomposition • Model empty areas with geometrical shapes • Can be extremely compact (18 nodes in this figure) • Assumption: robot position within each area of free space does not matter UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

11.Fixed cell decomposition • Tessellate world: discrete approximation • Each cell is either empty or full • Inexact (note loss of narrow passageway on right) UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

12.Adaptive cell decomposition • Multiple types of adaptation: quadtree, BSP, exact • Recursively decompose until a cell is completely free or completely an object • Very space efficient compared to fixed cell approach UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

13.Occupancy grid • Typically fixed decomposition – Each cell is either filled or free • Counter for cell: 0 indicates free, above a certain threshold is considered to be filled with an object – Particularly useful with range-based sensors • If sensor strikes something in a cell, increase cell counter • If sensor goes over cell and strikes something else, decrease cell counter (presuming is free space) • By also discounting cell values over time, can deal with transient obstacles – Disadvantages • Map size a function of size of environment and size of cell • Imposes a priori geometric grid on world UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

14.Occupancy grid • Darkness of cell proportional to cell counter value UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

15.Topological decomposition • Use environment features most useful to robots • A graph specifying nodes and the connectivity between them – Nodes not of fixed size nor specify free space – A node is an area the robot can recognize its entry to and exit from UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

16.Topological example • For this example, robot must be able to detect intersections between halls, and halls and rooms. UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

17.Topological decomposition • To robustly navigate with a topological map a robot – Must be able to localize relative to nodes – Must be able to travel between nodes – These constraints require the robot’s sensors to be tuned to the particular topological decomposition • Major advantage is ability to model non-geometric features (like artificial landmarks) that benefit localization UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

18.Map updates: occupancy grids • Occupancy grid – Each cell indicates probability is free space and probability is occupied – Need method to update cell probabilities given sensor readings at time t • Update methods – Sensor model – Bayesian – Dempster-Shafer UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

19.Representing the robot • How represent the robot itself on a map? • Point-robot assumption – Represent the robot as a point – Assume it is capable of omnidirectional motion • Robot in reality is of nonzero size – Dilation of obstacles by robot’s radius – Resulting objects are approximations – Leads to problems with obstacle avoidance UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

20.Current challenges • Real world is dynamic • Perception still very error prone – Hard to extract useful information – Occlusion • Traversal of open space • How to build up topology • Sensor fusion UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

21.Summary • Decomposition – Continuous – Discrete • Map updating – Bayes – Dempster-Shafer • Robot representation • Current challenges UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND 

22.References • “Introduction to Autonomous Mobile Robots”, R Siegwart and I Nourbaksh, Bradford • “Mobile Robotics: A Practical Introduction”, U Nehmzow, Springer • “Computational Principles of Mobile Robotics”, G Dudek, M Jenkin, Cambridge University Press • “Introduction to AI Robotics”, R Murphy, Bradford • “Rover Localizaton Results for the FIDO Rover”, E Baumgartner, H Aghazarian, A Trebi-Ollennu, SPIE Photinics East Conference, October, 2001. UNIVERSITY OF Planetary Surface Robotics ENAE 788U, Spring 2005 MARYLAND