Unit 2: Slam and Path Planning Flashcards
Occupancy Grid Mapping representation
A robot represents a map of the environment as an evenly-spaced field of cells.
Each cell represents the presence or absence of an obstacle at that location in the environment.
Occupancy Grid Mapping algorithm
As the robot moves around an environment:
- If a laser beam returns a hit for a cell, then the algorithm increments the counter of that cell.
- If a laser beam travels through a cell, then the algorithm decrements the counter for that call.
When the robot completed the survey, threshold the counter value in each cell:
- If the counter value is greater than the threshold, assume it is occupied.
- If the counter value is lower, assume it to be a free cell.
Occupancy Grid Mapping algorithm
Why might there be unobserved cells?
It is possible for a cell to still be set at its initial counter value after a robot has completed its survey of the environment.
Because the robot didn’t travel through this cell, we don’t know whether it is actually free or an obstacle.
- There are always some corner cells that remain at their initial values.
- cell might be inside an obstacle, meaning you can never hit it, as you’ll always hit the outer boundary.
- The cell may be in an area that the robot has not explored.
Occupancy Grid Mapping algorithm
Safest way to deal with unobserved cells
For all cells still at their initial counter value at the end of the mapping, mark as occupied.
Chicken & Egg problem:
Localisation & Mapping
- If you have a good map, then you can perform good localisation.
- If you have good localisation, then you can construct a good map.
Simultaneous Localisation and Mapping (SLAM)
The computational problem of constructing a map of an unknown environment, while simultaneously keeping track of an agent’s location within it.
Path Planning
Fixed-size cell decomposition
- Overlay a grid onto the space.
- Mark as occupied any cell containing an obstacle, even if partially.
- Perform graph search to find a sequence of free cells from start to goal.
- Convert the sequence of cells into a path for the robot.
Path Planning
Adaptive-size cell decomposition.
- Start with a coarse grid on the space.
- Any cell containing an obstacle is further devided until a threshold is reached.
- Mark any cell at the threshold containing an obstacle as occupied.
- Perform graph search to find a sequence of free cells from start to goal.
- Convert the sequence of cells into a path for the robot.
Path Planning
Exact cell decomposition
- Move along a fixed direction through the map.
- Whenever a corner is encountered, split the cell.
- Create a graph, where cells are represented as nodes, and cells sharing a border are connected.
- Perform graph search to find a sequence of cells.
- Convert the sequence of cells into a path for the robot. First connect mid-points of boundaries, then connect the start and the goal.
Convex Polygon
A planar polygon is convex if it contains all the line segments connecting any pair of its points.
Exact cell decomposition
Why do we create a new cell at each corner?
Cells should be convex.
We want the inside of the cell to require no planning. I.e. we want to be able to connect any two points in a cell using simply a straight line.
Path planning
Visibility Graph
- Connect each obstacle corner with each other corner that is directly visible.
- Also connect start and goal with corners that are directly visible.
- Search this graph.
Benefit of a visibility graph
Gives the shortest path in geometrical environments.
2 Problems with the visibility graph approach
- It creates many edges. The connections between the corners increase quadratically as the number of corners increases. We need to do straight-line visibility checks, meaning that this can take a lot of time when generating a first graph. I.e. it requires extensive computation.
- Visibility graphs generate paths which ‘graze’ obstacles because they often require a robot to take very tight turns around obstacles.
Voronoi diagram
The set of points that are equi-distant from the two closest surfaces.
