Motion planning

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

This article or section uses first-person or second-person inappropriately or excessively.
Please edit this article to use the more formal tone expected of an encyclopedia, per Wikipedia's style guidelines. (help, talk)

In making a plan for a robot, we would be required to present a sequence of locations and orientations for the robot (and its various parts, if it is not solid).

In order to represent any one state the robot may be in, we need to specify both its location and orientation. For this purpose, we need to choose (arbitrarily) a location on the robot's body itself, that would count as the robot's zero-point, and a zero angle.

  • For a dot-sized robot, in a 2-dimensional world, all we need to specify to give the robot's state is its location, expressed in x and y Cartesian coordinates.
  • For robot any larger than one dot, in 2-d space, we need to specify x, y, and the orientation, θ.
  • For a dot-robot in 3-d space, we need to express only location: x, y, and z.
  • For a solid 3-d robot in 3d space, we need to express the location of the robot's "0-point", in x, y and z, and also the 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 section we will represent the starting position of the robot as A, and the goal position as G. The strategy of most all 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. In no path is found through the graph, the search fails and it is assumed that there is no feasible path.

[edit] Configuration space

In this section we will examine the structure of the configuration space, that is the field 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 form 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.

We start with the simplest case (a dot on a plane), and move towards the full complexity of a multi-bodied robot (e.g. with an arm) in 3D space.

In the simplest interesting 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 to sample as much as possible of the configuration space, and create a roadmap based of these samples. Sampling algorithms are fast, and therefore feasible (unlike their combinatorial cousins) but often incomplete, meaning that they will in some cases not find a path between A and G, even when one exists.

In sampling C, one hopes to sample the space in a uniform manner, not wasting too much compute-power of one section while neglecting other areas. In order to facilitate this one needs to develop a metric function that will express the distance between two points. This is simple enough in Cartesian space, but more difficult on 3-spheres. An aid in visualizing the quality of sampling in Cartesian space are Voronoi diagrams.

Also, in sampling a space one would like to use available compute time efficiently. Especially in real-time algorithms when it is not known in advance how long the algorithm will have to survey the entire space before an answer is demanded. The Van der Corput sequence is a good example of techniques used to sample C more-or-less evenly.

In cases where only one query is expected, or in cases where C is too large to build a useful roadmap, a directed-search approach can be taken, in which one starts at some point (A, G, or some intermediate point) and searches toward the other pertinent points in the query (Fig 5.13, discuss).

Another technique is using search trees that expand rapidly to cover the space, see fig 5.19.

[edit] Combinatorial algorithms

In this approach, we want to actually follow 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 appoaches 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.

Fig 6.22, 6.23 (critical points) 2.26, 2.27, 6.28, 2.29.

[edit] See also

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

[edit] References

Retrieved from "http://en.wikipedia.org../../../m/o/t/Motion_planning.html"
In other languages