This chapter is mainly about navigation and metric path planning,which generally includes Introduction to navigation,impact of sensor uncertainty,spatial memory,configuration space,object growing and so on.

1. Navigation and Metric Path Planning Minerva tour guide robot (CMU): Example of Minerva’s occupancy Gave tours in Smithsonian’s National Museum of History map used for navigation

2. Objectives • Understand techniques for metric path planning: – Configuration space – Meadow maps – Generalized Voronoi graphs – Grids – Quadtrees – Graph-based planners: A* – Wavefront-based planners

3. Introduction to Navigation • Navigation is fundamental ability in autonomous mobile robotics • Primary functions of navigation: – Where am I going? • Usually defined by human operator or mission planner – What’s the best way to get there? • Path planning: qualitative and quantitative – Where have I been? • Map making – Where am I? • Localization: relative or absolute

4. Introduction to Navigation (con’t.) • Navigation is a fundamental robotics problem because it involves almost everything about AI robotics: – Sensing – Acting – Planning – Architectures – Hardware – Computational efficiencies – Problem solving

5. Introduction to Navigation (con’t.) • Path Planning Research – goes back to 1970s • Lots of approaches: proper choice depends upon ecological niche • Criteria for Evaluating Path Planners: – Complexity – Sufficiently represents the terrain – Sufficiently represents the physical limitations of the robot platform – Compatible with the reactive layer – Supports corrections to the map and re-planning

6. Intro. (con’t.): Impact of Sensor Uncertainty • Early path planning research (in simulation) assumed: – Sensors give an accurate representation of world – Robot ability to localize • But, as we’ve learned, these assumptions aren’t true • Therefore, robot has to operate in presence of uncertainty • Result: new techniques for dealing with sensor noise in localization, map building, and path planning

7. Intro. (con’t.): Spatial Memory • Spatial memory: – World representation used by robot – Provides methods and data structures for processing and storing information derived from sensors – Organized to support methods that extract relevant expectations about a navigational task

8. Intro. (con’t.): Spatial Memory (con’t.) • Four basic functions of Spatial memory: – Attention: What features, landmarks to look for next? – Reasoning: E.g., can I fit through that door? – Path Planning: What is the best way through this building? – Information collection: What does this place look like? Have I ever seen it before? What has changed since I was here before?

9. Intro. (con’t.): Spatial Memory (con’t.) • Examples of two forms of Spatial memory: – Qualitative (route): derived from: – Quantitative (metric or layout):

10. Intro. (con’t.): Spatial Memory (con’t.) • Two forms of Spatial memory: – Qualitative (route): • Express space in terms of connections between landmarks • Dependent upon perspective of the robot • Orientation clues are egocentric • Usually cannot be used to generate quantitative (metric/layout) representations – Quantitative (metric or layout): • Express space in terms of physical distances of travel • Bird’s eye view of the world • Not dependent upon the perspective of the robot • Independent of orientation and position of robot • Can be used to generate qualitative (route) representations

11. Intro. (con’t.): Spatial Memory (con’t.) • Questions regarding spatial memory: – How accurately and efficiently does robot need to navigate? – Is navigation time-critical, or is a slightly sub-optimal route acceptable? – What are the characteristics of the environment? – Are there landmarks to provide orientation cues? – Are distances known accurately? – What are the sources of information about the environment that specify terrains, surface properties, obstacles, etc.? – What are the properties of the available sensors in the environment?

12. Metric Path Planning • Objective: determine a path to a specified goal • Metric methods: – Tend to favor techniques that produce an optimal path – Usually decompose path into subgoals called waypoints • Two components to metric methods for path planning: – Representation (i.e., data structure) – Algorithm

13. Configuration Space • Configuration Space (abbreviated: “Cspace”): – Data structure that allows robot to specify position and orientation of objects and robot in the environment – “Good Cspace”: Reduces # of dimensions that a planner has to deal with – Typically, for indoor mobile robots: • Assume 2 DOF for representation • Assume robot is round, so that orientation doesn’t matter • Assumes robot is holonomic (i.e., it can turn in place) – (Although there is much research dealing with path planning in non- holonomic robots) – Typically represents “occupied” and “free” space • “Occupied”  object is in that space • “Free”  space where robot is free to move without hitting any modeled object

14. Object Growing • Since we assume robot is round, we can “grow” objects by the width of the robot and then consider the robot to be a point • Greatly simplifies path planning • New representation of objects typically called “configuration space object”

15. Method for Object Growing • In this example: Triangular robot • Configuration growing: based on robot’s bottom left Robot desired position corner • Method: conceptually move robot around obstacles without collision, marking path of robot’s bottom left corner Robot starting position

16. Method for Object Growing Robot desired position Robot starting position

17. Result of Object Growing: New Configuration Space Can now plan path of point through this space without dealing with shape of robot Robot desired position Robot now considered a point: IMPORTANT NOTE: Must make multiple Robot starting position configurations spaces corresponding to various degrees of rotations for moving objects. Then, generalize search to move from space to space

18. Also works for Manipulator Robots • Motion planning: Plan in configuration space defined by the robot’s degrees of freedom Manipulator Robot’s workspace Manipulator Robot’s configuration space • Solution is a point trajectory in free configuration space (C-space)

19. Examples of Cspace Representations • Voronoi diagrams • Regular grids • Quadtrees/octtrees • Vertex graphs • Hybrid free space/vertex graphs (meadow map)

20. Meadow Maps (Hybrid Vertex-graph Free-space) • Transform space into convex polygons – Polygons represent safe regions for robot to traverse • Important property of convex polygons: – If robot starts on perimeter and goes in a straight line to any other point on the perimeter, it will not go outside the polygon • Path planning: – Involves selecting the best series of polygons to transit through

21. Example Meadow Map Grow objects Construct convex polygons 3. Mark midpoints; these become graph nodes for path planner 4. Path planner plans path based upon new graph

22. Path Relaxation • Disadvantage of Meadow Map: – Resulting path is jagged • Solution: path relaxation – Technique for smoothing jagged paths resulting from any discretization of space • Approach: – Imagine path is a string – Imagine pulling on both ends of the string to tighten it – This removes most of “kinks” in path

23. Example of Path Relaxation Starting point Goal point Originally planned path Relaxed path

24. Limited Usefulness of Meadow Maps • Three problems with meadow maps: – Technique to generate polygons is computationally complex – Uses artifacts of the map to determine polygon boundaries, rather than things that can be sensed – Unclear how to update or repair diagrams as robot discovers differences between a priori map and the real world

25. Generalized Voronoi Diagrams (GVGs) • GVGs: – Popular mechanism for representing Cspace and generating a graph – Can be constructed as robot enters new environment • Basic GVG approach: – Generate a Voronoi edge, which is equidistant from all points – Point where Voronoi edge meets is called a Voronoi vertex – Note: vertices often have physical correspondence to aspects of environment that can be sensed – If robot follows Voronoi edge, it won’t collide with any modeled obstacles  don’t need to grow obstacle boundaries

26.Example Generalized Voronoi Graph (More on this next time)

27. Regular Grids / Occupancy Grids • Superimposes a 2D Cartesian grid on the world space • If there is any object in the area contained by a grid element, that element is marked as occupied • Center of each element in grid becomes a node, leading to highly connected graph • Grids are either considered 4-connected or 8-connected

28.Example of Regular Grid / Occupancy Grid

29. Disadvantages of Regular Grids • Digitization bias: – If object falls into even small portion of grid element, the whole element is marked as occupied – Leads to wasted space • Solution: use fine-grained grids (4-6 inches) • But, this leads to high storage cost and high # nodes for path planner to consider • Partial solution to wasted space: Quadtrees