Extensions of the Basic Problem

The Basic Problem:  A Formal Statement

This formulation of the basic problem is outlined by Jean-Claude Latombe in his Robot Motion Planning.

While this simplification was useful in developing basic approaches to solving the motion planning problem, usually additional factors ignored by the basic problem need to be considered.  Among these are moving obstacles, coordinating the motion of multiple robots, and the presence of uncertainty.

Moving obstacles and kinematic considerations

        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.

Multiple Robots

        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.