![icy [labs]](/moin_static171/common/wikilogo.png)
Related: Back to Robotics Portal | Graph Searching | Obstacle Avoidance
Path Planning
For your robot to work out how to travel from point A to point B in a complicated map, it will probably need to plan its path more intelligently than what can be achieved by an obstacle avoidance algorithm alone.
This tutorial demonstrates a few simple algorithms and techniques to help plan such a path.
Work Space and Configuration Space
In software, the robot's position in its environment is often represented as a single coordinate. For the following examples a 2D environment is used, and the position of the robot is represented as an (x,y) coordinate.
Robots themselves take up space, so testing this (x,y) coordinate against the map will not account for the extra space of the chassis and any clearance room required. To take this into account we can either test a set of points on the chassis against the positions of obstacles, or we can change the map to take our chassis (and other constraints or rotations in our movement) into account. The second option is often the easier option, transforming our work space (the locations of obstacles relative to the robot) into a configuration space (a map that takes into account the space and movement of the robot).
The configuration space for a robot can be quite complicated for robots with interesting constraints on their movement (due to their locomotion technique or their shape). This can result in a configuration space with a higher dimensionality than the work space, in order to describe the full space of robot interactions with obstacles. For most of the following examples we'll use a circular robot that can move any direction, so that our configuration space is simple:
Example
- Work Space: Black
- Robot: Red, with Blue origin - (x,y) coordinate
- Configuration Space for Robot: Grey
The blue dot (robot origin) can not pass into the grey area (configuration space).
Higher Dimensional Configuration Space
- To Be Completed
See also:
Once the configuration space has been determined, this can be used as the planning space for the movement of the coordinate (x,y) of the robot, without needing to take movement constraints into account.
Making the Map Discrete
Space and distance in the "real world" are usually considered continuous. That is, for any two points in space you can find another point between them. The opposite of this is a discrete world, which would be quantized (chopped up) into separate parts. Two points in discrete space can be considered adjacent (no space between them is considered).
The output of this discretization process is a set of connected waypoints which the robot can use as a road-map to navigate the space. In other words, turning a continuous map into a discrete map allows the map to be considered as a graph and turns the problem of path planning into a graph-searching problem.
To travel from point A to point B, the robot makes its way to the nearest node to A, the graph is searched to find a path from this node to the nearest node to B, and the robot then makes its way to B.
The following are some methods of discretisation:
Grid
The following shows a discretisation of the space using a grid. This diagram has the routes and locations which can be occupied as green, and the invalid routes and locations as red. The green section is a graph of locations (nodes) and routes (edges).
N.B. In grid-space the unit circle becomes a unit square which may throw off distance calculations (euclidean distance vs. manhattan distance). A closer approximation to a unit circle can be achieved with a grid of hexagons (or 6 directions instead of 4 coming out of each node). See Wikipedia on Hexagonal Tiling
Topological Skeleton
The topological skeleton, or medial axis of the space is a shape consisting of all the points which have more than one closest point to the obstacles. This shape can be generated using an algorithm similar to that used to generate Voronoi diagrams. This skeleton forms a tree-like structure, the point of branching forms a waypoint node and each branch a path between nodes. Any curved paths require extra information about the curvature of their connectivity, or can be approximated with straight line polygons of a desired resolution.
A more approximate variation is to form a straight skeleton. This is particularly useful when the environment is defined as a polygon. A straight skeleton can be generated by a continuous shrinking process where the edges of the polygon are moved inwards parallel to each other at a constant speed, until the vertices collide with a non-adjacent edge. At this point the process divides and starts again. The resulting movement of the vertices defines the straight skeleton.
The following diagram shows a graph generated from the topological skeleton of the configuration space:
Vertical Cell Decomposition
The Vertical Cell Decomposition algorithm splits a polygon map into cells using a vertical sweep.
A vertical line sweeps across the map, each time this sweep line touches a vertex on a polygon, a line segment is extended vertically in both directions from this vertex until it hits another obstacle polygon. This divides the map into a set of cell polygons, bounded by the generated vertical line segments and the bounding obstacles. A graph vertex is created at the centroid of each cell polygon and joined to graph vertices created at the mid-points of the line segments.
This diagram shows our example configuration space vertically decomposed into cells, and the resulting graph.
You may notice that thin cells can give undesired (or inefficient looking) behaviour. A minimum cell width, or simplifying the obstacle polygons can reduce this.
Another example from this source is shown below:
Rapidly-Exploring Random Trees
The Rapidly-Exploring Random Tree algorithm randomly generates a tree within the configuration space, biased towards the topological skeleton (or Voronoi regions) described above. It is very fast to compute and the following is a 2D example of the algorithm:
To set up:
Create a tree T with a single vertex (and no edges). This vertex is a uniform randomly selected position inside the configuration space.
Choose an incremental distance, q, which will be the edge length between nodes
repeat, until the tree is detailed enough (has filled up enough of the space):
let Crand be a uniform randomly selected position inside the configuration space
let Cnear be the position of the nearest vertex to Crand in the constructed tree, T
let v be the vector from Cnear to Crand
let d be the minimum of q and the distance in the direction of v from Cnear to an obstacle
let Cnew be the point in the direction of v a distance d away from Cnear
join Cnew and Cnear with an edge, updating the tree T
See also:
Putting It All Together
Once you have discretised the map into a roadmap graph, you will need to perform a graph searching algorithm. These are covered on the Graph Searching page.
To navigate around obstacles to reach the first waypoint node or when travelling between nodes, you may need an obstacle avoidance algorithm. These are covered on the Obstacle Avoidance page.