The Basic Problem: A Formal Statement
This formulation of the basic problem is outlined by Jean-Claude Latombe in his Robot Motion Planning.
Extending the
basic problem by introducing moving obstacles is often coupled with introducing
kinematic constraints on robot motion, because time becomes a factor in
planning the path of motion. Instead of using plain configuration
spaces, the planning is done in a configuration-time (CT) space, which
also includes a time dimension. The path in a CT-space is restricted
because objects, including the robot itself, cannot move back in time.
Furthermore, it is often necessary to consider kinematic constraints and
mechanical limitations of the robot, such is its maximum speed or maximum
acceleration, or the ability to turn while moving at high speed.
These considerations may limit the slope and curvature of the CT-path,
and can greatly increase the computational difficulty of the problem.
One solution
to the increasing computational complexity is using the potential field
approach. Moving objects will change the potential field with time,
but this time-dependence of the potential field function is not very complex
as an additional consideration. The inherent drawbacks of the potential
field approach, however, become more significant because the existence
of local minima becomes more difficult to predict if the field changes
with time.
There are two
common approaches to dealing with multiple robots -- centralized planning
and decoupled planning. In centralized planning, the multiple robots
are considered as parts of one composite robot, for which a composite configuration
space is constructed. The problem is then reduced to finding a path
within this composite configuration space for the composite robot.
While this may seem effective, in practice the computational complexity
of working with the composite configuration space is very high, because
these spaces normally have high dimensions.
One approach
that is simpler computationally is the method of decoupled planning.
This method first plans the paths for each individual robot independent
of the others, and then considers the interactions between these paths.
Prioritized planning and path coordination are two types of decoupled planning.
Prioritized planning restricts robots to moving one at a time, along their
target path, in a certain "prioritized" order. Path coordination
allows concurrent robot motion, with some precautionary measures taken
to avoid collision. Both techniques in the decoupled planning approach
are computationally simple compared to centralized planning, but allow
only limited robot cooperation and therefore are likely to fail when this
cooperation is necessary, as illustrated in the diagram below.
The basic problem
and its extensions that include moving obstacles and multiple robots all
assume that the robot(s) are able to perfectly perceive the locations and
the configurations of all surrounding objects in the environment (obstacles
and other robots), and precisely predict the motion of each moving obstacle
and robot. They also assume the robot always has perfect control
over its motion. In reality, there is often a moderate degree of
uncertainty involved in both perceiving the outside environment and executing
planned motion. In most cases this uncertainty can be accounted for
by slightly enlarging the obstacles in the configuration space of the robot,
so that there is some room for error when a path is constructed.
Sometimes,
especially when the robot's sensors are not very sophisticated, the uncertainty
has such a great impact that it becomes impossible to calculate the robot's
path prior to the motion. Alternate techniques, such as mapping out
obstacles by touch, can sometimes be used in place of the standard ones
that work when all obstacle locations are known exactly. (see diagram below)
Our robot Rex
avoids obstacles in much the same way. His sensors are limited to
touching an object with an arm and detecting ground color with the optical
eye. When he runs into an obstacle, the touch signal is detected
by the sensors, and Rex backs up, turns slightly and moves forward until
he hits an obstacle again. Uncertainty is the dominating influence
in this situation, and the approaches used to solve the basic motion planning
problem don't apply because of insufficient information.