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.
Path planning
Voronoi diagram algorithm
- Construct the Voronoi diagram from the map.
- Find closest segments to the start and goal.
- Perform graph search to find the shortest path.
Voronoi diagram algorithm: Strengths
Very safe paths.
Voronoi diagram algorithm: Weaknesses
Paths are far from optimal.
5 Methods for path planning
- Fixed-size decomposition
- Adaptive-size sell decomposition
- Exact cell decomposition
- Visibility graphs
- Voronoi diagrams
4 Key considerations for planning algorithms
- Completeness
- Optimality
- Computational complexity (planning time)
- Ease of implementation
4 Key considerations for planning algorithms
Completeness
A planner is complete if it finds a solution whenever one exists.
4 Key considerations for planning algorithms
Optimality
A planner is optimal if it always produces the shortest possible path.
4 Key considerations for planning algorithms
Computational complexity (planning time)
This is a function of how complex the chosen planner is, and the complexity of the environment.
Balance optimality with the time to plan suitable paths.
4 Key considerations for planning algorithms
Fixed-size sell decomposition
Properties
- Not complete
- Not optimal (but can get close if cell sizes are small)
- Planning gets slow as cell sizes get smaller.
- Very easy to implement
4 Key considerations for planning algorithms
Adaptive-size cell decomposition
Properties
- Not complete (but can get close)
- Not optimal.
- Planning gets slow as cell sizes get smaller.
- Not easy to implement.
4 Key considerations for planning algorithms
Exact cell decomposition
Properties
- Complete
- Not optimal.
- Planning is fast if environment is sparse, slow otherwise.
- Difficult to implement.
4 Key considerations for planning algorithms
Visibility graphs
- Complete
- Optimal (but not safe if there is an execution error).
- Planning is fast if environment is sparse, slow otherwise.
- Difficult to implement.
4 Key considerations for planning algorithms
Voronoi diagrams
- Complete
- Not optimal (but very safe even if there is execution error)
- Slow
- Difficult to implement.
Path planning
2 Local methods
- Potential fields
- Bug algorithm
Path planning
Potential fields method
- Robot should be attracted by the goal. Define an attraction force
F_att. - It should be repelled by any obstacles. Define a repulsive force
F_rep. -
F = F_att + F_repwhereFis the resultant force and direction of travel for the robot.
Benefit of Potential fields method
No global planning is needed.
We can continually compute which forces we are attracted to at any point along the path.
Following these forces creates smooth motion.
Problem with the Potential fields method
Robot can get stuck at a local minima.
Bug algorithm
- Move towards the goal
- If you hit an obstacle, follow the wall.
Configuration of a robot
A complete specification of the position of every point on the robot.
Such that, given the configuration for a robot, one should be able to determine where every point of the robot is in the environment, and you should be able to draw the exact space the robot’s body will occupy.
