Maps, Navigation & Path-finding
Types of Navigation
Global Navigation
This is about deciding how to get from some start point to a goal point:
- The robot plans in some sense.
- This plan consists of a series of waypoints.
Local Navigation
This is about obstacle avoidance:
- We can use sensors to ensure that we don’t hit an object on the way to a waypoint.
Configuration Space
Configuration space (or Cspace) defines how much space a robot should leave between itself and any obstacle:
- We can use a circle around the centre of the robot to the further point on the robot to represent this.
This assumes that the robot can turn on the spot (holonomic).
Voronoi Diagrams
A Voronoi diagram defines barriers around a set of points:
We can extend this to objects to generate paths that stay equidistant from objects.
Bushfire Planning
This calculates the distance to the nearest obstacle:
- Approximates the repulsive function for a potential field.
- Neighbours are either 4 point or 8 point connectivity.
We can calculate the grid like so:
- Label all empty cells as 0, and occupied cells as 1.
- Assume $i=1$
- For each cell neighbouring a cell with the value $i$, label it with $i+1$.
- Repeat until all cells have a non-zero value.
We can then compute paths by following the gradient around the map.
Higher numbers are more attractive cells.
Topological Maps
Topological maps record:
- Nodes - Representing areas in the world.
- Arcs - Representing adjacency and traversability between nodes.
By making a map into a graph, we can use graph searching algorithms to finds routes around a space.
Topological Map Types
Topological:
- Route based.
- Express space in terms of connections between landmarks.
- Orientation cues are egocentric.
Quantitative:
- Layout based.
- Independent of the robot pose.
Search
With grid based maps we can consider each cell as a node with $N4$ or $N8$ connectivity.
To find the way to a destination we will need to search the map for a route. To do this we can use the following search techniques:
- Naive searches:
- Depth-first Search
- Breadth-first Search
- Heuristic Searches:
- Dijkstra’s Shortest Path
-
Greedy Best-first Search
This is much faster than Dijkstra’s but is suboptimal and can be lured into local minima.
- A* Search
-
D* Search
This is a version of A* that keeps track of the search that led to a plan and only fixes the errors. This is faster than replanning from scratch.
- Wavefront Planning
Waypoints
As we find a route we should record waypoints, typically at the centre of each cell.