Motion planning

From Wikipedia, the free encyclopedia

Motion planning is a term used in robotics for the process of detailing a task into atomic robotic motions.

This issue, also known as the "navigation problem", though simple for humans, is one of the most challenging in computer science and robotics. The problem is in creating an algorithm that would be able to find its way around a room with obstacles, perhaps accomplishing some task on the way.

Contents

[edit] Introduction

The field of motion planning includes both practical examples such as manipulating a robot by computer, and theoretical problems such as the Alpha Puzzle

Motion planning is seen as a special case of computer planning, a much broader field that includes also the simpler task (for computers) of playing board games by brute-force search of the tree of possibilities. By and large, the whole family of motion planning algorithms is based on reducing the 3-d (or 2d) dynamic problems into a graph or tree, that in turn is easy to handle using conventional search algorithms.

[edit] Background

[edit] Discrete planning

One of the major techniques in artificial intelligence in general, used also in motion planning, is to represent a problem as a decision tree or a graph, and later to use a graph search algorithm to search this graph or tree for a "solution path" leading from the initial state to the goal state.

In motion planning, a graph is often constructed as a road map, where there is a clear "line of sight" (no obstacles) between the end-vertices of every edge, so that a robot traversing the graph would run into no obstacles. Once such a map is constructed, all one needs to do in order to bring a simple robot from one place to another in the problem-space is to find the nearest points in the graph to the beginning and goal points, connect these 2 points to the graph, and do a graph-search.

[edit] Geometric representations

In making a plan for a robot, a sequence of locations and orientations for the robot are required to be presented.

  • For a dot-sized robot in a 2-dimensional world, the robot can be expressed by its location x and y in Cartesian coordinates. Similarly, in 3-d space, it can be expressed as its 3-d location, x, y, and z.
  • For a robot larger than one dot in 2-d space, the robot can be specified by its location (x, y) and its orientation θ.
  • For a solid 3-d robot in 3d space, the location of the robot is expressed as x, y and z, and its angle in yaw, pitch, and roll.
    • Yaw is the degree of counter-clockwise rotation about the z axis expressed as α.
    • Pitch is the degree of counter-clockwise rotation about the y axis expressed as β.
    • Roll is the degree of counter-clockwise rotation about the x axis expressed as γ.

These dimensions are calculated by computer using the principles of computational geometry.

Any object in the space, whether the robot itself, an obstacle, or the boundaries of the space, is expressed as a convex polygon, or as a union of convex polygons. These polygons are represented as a list of lines, where if a point is on the "out" side of at least one of the lines, it is considered outside the object. A similar strategy can be employed for 3-d objects.

[edit] Basic algorithms

In the following sections, the starting position of the robot is notated as A, and the goal position as G. The strategy of most planning algorithms is to construct a more-or-less complete "roadmap" of the free space. A query is submitted as a start (A) and goal (G) position. All the computer needs to do once a roadmap exists is link A and G to the nearest roadmap locations, and do a fast graph search to come up with a plan of action. If no path is found through the graph, the search fails and it is assumed that there is no feasible path.

[edit] Configuration space

The configuration space is the set of possibilities for the robot's location. Every dot in the configuration space represents a possible arrangement of the robot in the problem space. A contiguous line in configuration space represents a plan - that is a sequence of planned locations, starting from A and leading to G. The configuration space, C, is divided in two, Cfree - the area the robot may occupy, and Cobs — the area obstructed by obstacles. Cobs may be empty.

In the following, several cases are described, and those are from the simplest case, a dot on a plane, to a complex robot system, e.g. multi-robot system or a robot arm in 3D space.

In the simplest case, the robot is a single point (zero-sized) and the world in which it operates is a 2-dimensional plane. A maze is an example of such a problem-space. In this simple case, the configuration-space is the same as the problem-space, i.e. a plane. In a solved maze, the line on the paper represents the sequence of locations that the robot would visit from the A to G.

The next, more complicated, case is when the robot is larger than a dot, and therefore has an orientation. The field of all possible states of the robot in the world consists of 3 parameters: x, y and θ. One must bear in mind that in angles, 2Π = 0, so one could visualize this configuration space as a 3D space which is 2Π tall, and there is an identification of the bottom and the top of the z axis. Alternately, for the more topologically-minded, the space is a type of cylinder: a normal cylinder has 2 coordinates, θ and h. This one has 3 - x, y and θ.

The case of a simple, solid robot in 3D space would require 6 parameters: x, y, z, α, β and γ. remember, 2Π = 0 for all angles, so this space is, topologically, the multiplication of 3D space with the 3S, which in turn has one more (angular) dimension than our common sphere.

Adding arms to a robot, or multiple robots in the same problem, would add further dimensions to the configuration space.

[edit] Sampling-based algorithms

The general idea of sampling algorithms is represent the configuration space with a roadmap of sampled configurations. These algorithms work well for high-dimensional configuration spaces, because unlike combinatorial algorithms, their running time is not (explicitly) exponentially dependent on the dimension of C. They are also (generally) substantially easier to implement. However, they are only probabilistically complete, meaning the probability that they will produce a solution approaches 1 as more time is spent. However, they cannot determine if no solution exists. They are currently the state-of-the-art approaches for high-dimensional spaces, and have been applied to robotic manipulators, biological molecules, digital actors, and legged robots, problems which have dozens or even hundreds of dimensions.

The basic algorithm samples N configurations in C, and retains those in Cfree to use as milestones. A roadmap is then constructed that connects two milestones P and Q if the line segment PQ is completely in Cfree. To find a path that connects A and G, they are added to the roadmap. If A and G are connected in the roadmap, the planner succeeds. If not, the reason is not definitive: either there is no path in Cfree, or the planner did not sample enough milestones.

Given basic visibility conditions on Cfree, it has been proven that as the number of configurations N grows higher, the probability that the algorithm finds a solution approaches 1 exponentially [1]. Visibility is not explicitly dependent on the dimension of C; it is possible to have a high-dimensional space with "good" visibility or a low dimensional space with "poor" visibility. The experimental success of sample-based methods suggests that most commonly seen spaces have good visibility.

There are many variants of this basic scheme:

  • It is typically much faster to only test segments between nearby pairs of milestones, rather than all pairs.
  • Nonuniform sampling distributions attempt to place more milestones in areas that improve the connectivity of the roadmap.
  • Quasirandom samples typically produce a better covering of configuration space than pseudorandom ones, though some recent work argues that the effect of the source of randomness is minimal compared to the effect of the sampling distribution.
  • If only one or a few planning queries are needed, it is not always necessary to construct a roadmap of the entire space. Tree-growing variants are typically faster for this case (single-query planning). Roadmaps are still useful if many queries are to be made on the same space (multi-query planning)

[edit] Combinatorial algorithms

This approach follows the boundaries of Cfree, and build a roadmap that is based on the actual boundaries and not a sampling thereof. In the case of a dot-robot in 2d space, this is simple enough: Cfree can be divided into triangles, and a roadmap constructed through the centre-points of the edges of each triangle.

However, note how rapidly the complexity of the algorithms in this approach go out of control: even allowing for a dot-robot in 2d space, once there are curves in the boundary between Cfree and a non-polygon in Cobs, complexity takes off.

In order to illustrate the approaches required and the complexity issues, let's look at the case of a line-robot (1d) in 2 space. The robot will be represented by a line with a dot at one end, to mark the "zero point", or the base of the θ rotation.

[edit] See also

  • The driverless car is an example of an application of motion planning.

[edit] References

  1. ^ Hsu, D; Latombe, J.C. & Motwani (1997), “Path Planning in Expansive Configuration Spaces”, Proc. IEEE Int. Conf. on Robotics and Automation 
  • Robot Motion Planning, Jean-Claude Latombe, 1991, Kluwer Academic Publishers
  • Planning Algorithms, Steven M. LaValle,2006, Cambridge University Press, ISBN 0-521-86205-1. Available online at http://planning.cs.uiuc.edu/
  • Principles of Robot Motion: Theory, Algorithms, and Implementation, H. Choset, W. Burgard, S. Hutchinson, G. Kantor, L. E. Kavraki, K. Lynch, and S. Thrun, MIT Press, April 2005.
  • Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry, 2nd revised edition, Springer-Verlag. ISBN 3-540-65620-0.  Chapter 13: Robot Motion Planning: pp.267–290.

[edit] External links

Languages