COM2009-3009 Robotics: Lecture 10 Maps & Path Planning PDF

© 2023 The University of Sheffield COM2009-3009 Robotics Lecture 10 Maps & Path Planning Dr Tom Howard Multidisciplinary Engineering Education (MEE) COM2009-3009 Robotics: Lecture 10 slide 1 © 2023 The University of Sheffield Previous lecture: Localisation 1. External references can be used for...

© 2023 The University of Sheffield COM2009-3009 Robotics Lecture 10 Maps & Path Planning Dr Tom Howard Multidisciplinary Engineering Education (MEE) COM2009-3009 Robotics: Lecture 10 slide 1 © 2023 The University of Sheffield Previous lecture: Localisation 1. External references can be used for triangulation but suffer due to: – Line of sight blocked (indoors, cities) – Can be jammed/intentionally restricted – Generally limited accuracy Not sufficient for robot navigation 2. Odometry (aka Dead-reckoning (sailing) / Path Integration (biology)) – Can function independent of external cues – BUT accumulates error Only good for local positioning This Lecture: Maps 1. Types of maps used in modern robotics 2. How to path plan to optimally navigate mapped environments COM2009-3009 Robotics: Lecture 10 slide 2 © 2023 The University of Sheffield Maps are useful for many tasks Localisation Manipulation COM2009-3009 Robotics: Lecture 10 Planning / Navigation Human Robot Interaction slide 3 © 2023 The University of Sheffield What do we mean by a map? Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. (Not all maps are necessarily “topographic”) COM2009-3009 Robotics: Lecture 10 slide 4 © 2023 The University of Sheffield Type 1: “Topological” maps Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Record of the connections (links) between a set of places (nodes) COM2009-3009 Robotics: Lecture 10 slide 5 © 2023 The University of Sheffield Topological maps for robots Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Record of the connections (links) between a set of places (nodes) First Step: Build the map Figures from: Dayoub et al, 2011: https://eprints.qut.edu.au/72973/ COM2009-3009 Robotics: Lecture 10 slide 6 © 2023 The University of Sheffield Topological maps for robots Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Record of the connections (links) between a set of places (nodes) Use Case 1: Localisation Figures from: Dayoub et al, 2011: https://eprints.qut.edu.au/72973/ COM2009-3009 Robotics: Lecture 10 slide 7 © 2023 The University of Sheffield Topological maps for robots Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Record of the connections (links) between a set of places (nodes) Use Case 2: Navigation Figures from: Dayoub et al, 2011: https://eprints.qut.edu.au/72973/ COM2009-3009 Robotics: Lecture 10 slide 8 © 2023 The University of Sheffield Topological maps - Summary Can represent known locations and the connections between them as nodes and edges in a graph The edges could represent actions needed to get from one node to the next, or direction and distance Can determine an optimal route by standard graph search methods (e.g. Dijkstra) or A*, if distances (or costs) are added to the edges COM2009-3009 Robotics: Lecture 10 slide 9 © 2023 The University of Sheffield Type 2: Topographic maps Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Record of the location of objects in an absolute coordinate system COM2009-3009 Robotics: Lecture 10 slide 10 © 2023 The University of Sheffield Topographic (Metric) Map Formats 1. Discrete / “raster” format: Occupancy grids Free space 2D or 3D 2. Continuous / “vector” format: Points, linear or curved segments, surface patches Unexplored Boundaries/obstacles COM2009-3009 Robotics: Lecture 10 slide 11 © 2023 The University of Sheffield Topographic (Metric) Map Sensors 1. LiDAR Scanner 2. 3D vision sensors e.g. Kinect; Intel RealSense… COM2009-3009 Robotics: Lecture 10 slide 12 © 2023 The University of Sheffield Robot Using an Occupancy Grid https://www.youtube.com/watch?v=XzkC4Ez8GYE COM2009-3009 Robotics: Lecture 10 slide 13 © 2023 The University of Sheffield From Topological to Metric Maps COM2009-3009 Robotics: Lecture 10 slide 14 © 2023 The University of Sheffield Metric vs Topological Maps Summary COM2009-3009 Robotics: Lecture 10 slide 15 © 2023 The University of Sheffield Type 3: Semantic maps Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Stairs Record of semantic information (metadata), incl. segmentation, function etc. Desk Person Sofa Floor COM2009-3009 Robotics: Lecture 10 slide 16 © 2023 The University of Sheffield Type 4: Hybrid Maps Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Attempt to combine the complementary strengths of different representations (metric, topological, semantic maps) Example: Topological level: - connected set of places Metric level: - each place is associated with a local metric map - Overlay position of people (potential field / cost maps) COM2009-3009 Robotics: Lecture 10 slide 17 © 2023 The University of Sheffield Type 4: Hybrid Maps Map: A collection of elements or features at some scale of interest, and a representation of the spatial and/or semantic relationships between them. Cost maps: COM2009-3009 Robotics: Lecture 10 slide 18 © 2023 The University of Sheffield Example: time-dependent topological maps for path planning COM2009-3009 Robotics: Lecture 10 slide 19 © 2023 The University of Sheffield But maps come at a cost… Can be resource intensive Validity (accuracy, error bounds) COM2009-3009 Robotics: Lecture 10 Currency (updates?) slide 20 © 2023 The University of Sheffield What type of map is used in Minecraft? A. B. C. D. Semantic Topographic Topological Hybrid Image from flickr– labelled for noncommercial re-use COM2009-3009 Robotics: Lecture 10 slide 21 © 2023 The University of Sheffield What type of map is presented in Google Maps? A. B. C. D. Semantic Topographic Topological Hybrid Image from flickr– labelled for non-commercial re-use COM2009-3009 Robotics: Lecture 10 slide 22 © 2023 The University of Sheffield Path Planning with maps COM2009-3009 Robotics: Lecture 10 slide 23 © 2023 The University of Sheffield Path Planning with maps Task: Plan the path from Start (S) to Finish (F) that minimises the total cost. Obstacle Q. What is the minimum-cost path? A. 5 S 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A topological map COM2009-3009 Robotics: Lecture 10 slide 24 F © 2023 The University of Sheffield Path Planning with maps Task: Plan the path from Start (S) to Finish (F) that minimises the total cost. Q. What is the minimum-cost path? A. 5 S 1 1 1 1 1 1 COM2009-3009 Robotics: Lecture 10 1 1 1 1 1 1 1 1 1 1 1 slide 25 F © 2023 The University of Sheffield Path Planning with maps Task: Plan the path from Start (S) to Finish (F) that minimises the total cost. Djikstra’s algorithm will flood search densely and homogeneously connected nodes. S 1 1 Undirected Wiki has a great resource with demos & pseudocode: https://en.wikipedia.org/wiki/Dij kstra's_algorithm 1 1 1 1 COM2009-3009 Robotics: Lecture 10 1 1 1 1 1 1 1 1 1 1 1 slide 26 F © 2023 The University of Sheffield Path Planning with maps Task: Plan the path from Start (S) to Finish (F) that minimises the total cost. Djikstra’s algorithm will flood search densely and homogeneously connected nodes. S 1 1 Undirected Wiki has a great resource with demos & pseudocode: https://en.wikipedia.org/wiki/Dij kstra's_algorithm 1 1 1 1 This type of “Brute force search” is often too costly in reality COM2009-3009 Robotics: Lecture 10 1 1 1 1 1 1 1 1 1 1 1 slide 27 F © 2023 The University of Sheffield A* Algorithm Overview Nilsson et al adapted Dijkstra’s algorithm to improve performance and implemented on Shakey the robot in 1968. The resultant approach is A* search. A* selects its distance of travel by optimising 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) where: n is the current node g(n) is the cost of the path from the start node to n h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal. Common heuristic is straight line distance to goal but is problem specific COM2009-3009 Robotics: Lecture 10 slide 28 © 2023 The University of Sheffield A* Algorithm – from the designer Nils Nilson https://www.youtube.com/watch?v=mQ7M-zhiu7U Wiki has a great resource with demos & pseudocode: https://en.wikipedia.org/wiki/A*_search_algorithm COM2009-3009 Robotics: Lecture 10 slide 29 © 2023 The University of Sheffield A* Algorithm – Q table example 1. Setup Phase V S A B C D E F S 0S ∞ ∞ ∞ ∞ ∞ ∞ 1. Set start node as current node with distance 0 2. Set distance to all other start node from start node to infinity (∞) A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 30 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 3 F h(F)=0 C h(C)=6 7 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 31 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ B 0S 11S 8S ∞ ? ∞ ∞ 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 32 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ B 0S 11S 8S ∞ 8B ∞ ∞ 𝑓 𝑛 =𝑔 𝑛 +ℎ 𝑛 𝑓 𝑛 = (2 + 2) + 4 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 33 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ B 0S 11S 8S ∞ 8B ∞ ∞ ? 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 34 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ B 0S 11S 8S ∞ 8B ∞ ∞ D 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 35 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ B 0S 11S 8S ∞ 8B ∞ ∞ D 0S 11S 8S ∞ 8B 8D ∞ ? 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 𝑓 𝑛 =𝑔 𝑛 +ℎ 𝑛 𝑓 𝑛 = (2 + 2 + 2) + 2 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 36 © 2023 The University of Sheffield A* Algorithm – Update Cost Function Repeat until all cannot expand goal node 1. Update table with total cost (e.g. from start) from current node to all connected, unvisited nodes. V S A B C D E F S 0S 11S 8S ∞ ∞ ∞ ∞ B 0S 11S 8S ∞ 8B ∞ ∞ D 0S 11S 8S ∞ 8B 8D ∞ E 0S 11S 8S ∞ 8B 8D 8E 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 2. Update path length and previous node if less than current setting 3. Move to node with smallest total path length A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 2 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D E h(E)=2 slide 37 © 2023 The University of Sheffield What type of map did we just path plan on? A. B. C. D. Semantic Topographic Topological Hybrid A 1 4 7 F h(F)=0 C h(C)=6 3 h(A)=10 S 2 COM2009-3009 Robotics: Lecture 10 h(B)=6 B 2 h(D)=4 2 D 2 E h(E)=2 slide 38 © 2023 The University of Sheffield This lecture has covered … 1. Types of maps used in modern robotics: – – – – Topological (Local Guidance -> Topological Maps) Topographic (Metric maps – 2D/3D Occupancy Grids) Semantic Maps Hybrid Maps / (e.g. Cost Maps or “Potential Fields”) 2. How to path plan on a topological map – Undirected Dijkstra Search – A* Search COM2009-3009 Robotics: Lecture 10 slide 39 © 2023 The University of Sheffield Where to find out more Reading Materials: - Kostavelis, Ioannis, and Antonios Gasteratos. "Semantic mapping for mobile robotics tasks: A survey." Robotics and Autonomous Systems 66 (2015): 86-103. - Choset, H. M., Hutchinson, S., Lynch, K. M., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of robot motion: theory, algorithms, and implementation. MIT press. - Siegwart, Roland, Illah Reza Nourbakhsh, Davide Scaramuzza, and Ronald C. Arkin. Introduction to autonomous mobile robots. MIT press, 2011. - Wiki resources as linked throughout COM2009-3009 Robotics: Lecture 10 slide 40 © 2023 The University of Sheffield Next time … Sensors & Sensor Fusion COM2009-3009 Robotics: Lecture 10 slide 41