Topologically, the configuration space of this robot is a torus. This is easy to see because the orientation, 2π, is equivalent to the orientation, 0, for both joints. If this torus is “unwrapped,” the correspondence between the work space and configuration spaces can be seen (see Figure 3).
Figure 3: Work space and configuration space of a two-joint robot parameterized by angles, [q1,q2]. Note that the mapping from work space to configuration space is not as intuitive as the disc robot. (Drawing courtesy of Prof. Jean-Claude Latombe)
Moving obstacles in the work space can be elegantly represented by simply introducing another dimension, time, to the configuration space. The configuration space provides a simple mathematical representation of the robot’s possible states, given the present environment. The generalized planning problem now reduces to finding a path fully contained in the free space that connects two configurations, p, p . It is easy to see that while all robot states actually occur in 2-D or 3-D Euclidean space, there are many parameters that define those states. Because there are many such parameters (to define a human’s exact state can take hundreds of parameters), this space is often high dimensional and of complex topology.
The free space can be analyzed using standard search methods, such as gradient descent, or even by explicitly computing and partitioning the free space and obstacle geometry. However, these techniques generally work only for low-dimensional configuration spaces. Explicit computation of the geometry of configuration spaces is extremely difficult for spaces of more than three dimensions. Gradient descent works well for slightly higher dimensions but fails to find solutions when the dimensionality further increases, because of its tendency to get “trapped” in local minima [ 5].
Because standard algorithms fail to produce results in high-dimensional spaces, a new method known as the probabilistic roadmap was introduced. A probabilistic roadmap chooses configurations at random in the configuration space. Configurations that belong to the free space and are within a certain metric of each other are connected via an arc. This arc must also satisfy the property that all points on the arc are in the free space. The primary cost of building the roadmap is checking this arc to ensure that it is collision free. After many samples, this method creates a graph approximating the connectivity of the free space (see Figure 4).
This graph is known as the probabilistic roadmap. The nodes of this graph are often referred to as milestones. In order to find a path, the roadmap is simply searched to see if a configuration can be
Figure 4: Probabilistic roadmaps of a simple configuration space. Nodes are connected to approximate connectivity of free space.
reached within some metric of the goal configuration. This can be done using standard graph-search algorithms. It is important to note that the path returned by the roadmap may be far from optimal, due to the random nature of milestone selection. The running time of the roadmap, however, is bounded, given that the configuration space satisfies a geometric property known as expansiveness. Expansiveness, in the simplest sense, is the lack of “narrow passages” in the space being sampled. To picture this concept, consider two rooms connected by a long hallway. As the width of the hallway decreases, so does the expansiveness of the space. If this expansiveness is sufficiently high, the probability of the planner finding a path grows exponentially with the number of configurations sampled. Thus, this type of planner is said to be probabilistically complete [4].
Various improvements can also be implemented to better characterize the connectivity. One simple method is to oversample regions where failed nodes and successful nodes occur within a certain distance of each other—the intuition being that more information is needed near obstacle boundaries than near large empty portions of free space [ 1].
Planning with Non-Holonomic or Dynamic Robots The probabilistic roadmap approach assumes that given two configurations whose connecting arc is in the free space, the robot can travel from one to the other. This works well for multijoint arm type robots or omnidirectional robots, which can move along any arc in free space. This is not the case if there is a robot with a non-holonomic constraint. A non-holonomic robot’s motion constraints are described by a set of nonintegrable differential equations. The theory behind these constraints is quite complex. For the purposes of this paper, the main point is that such constraints limit the robot from travelling along an arbitrary path in the free space. Given constraints such as these, a path found in the free space may not be feasible because the vehicle cannot transition between two milestones. Because of this limitation, a new planning method was created that extends the basic roadmap; this method is known as kinodynamic roadmap-based planning [ 6]. Instead of randomly sampling configurations in the configuration space, the initial position, p, is the starting point. From p, new configurations are expanded based on a sampling of the control space. The control space is simply the set of possible actions the robot can take from the present state. For a car, this may correspond to turning the wheels left or right or accelerating. The application of a control results in new configuration that is reachable from p. Thus, the roadmap takes the form of a tree, with the initial position being the root node. Any node can be chosen to expand
References:
Archives