7.3.1 Hybrid Systems Framework

As illustrated in Figure 7.11, a hybrid system involves interaction between discrete and continuous spaces. The formal model will first be given, followed by some explanation. This formulation can be considered as a combination of the components from discrete feasible planning, Formulation 2.1, and basic motion planning, Formulation 4.1.

- The and components from Formulation 4.1 are included.
- A nonempty
*mode space*, that is a finite or countably infinite set of*modes*. - A semi-algebraic
*obstacle region*for each . - A semi-algebraic
*robot*, for each . It may be a rigid robot or a collection of links. It is assumed that the C-space is not mode-dependent; only the geometry of the robot can depend on the mode. The robot, transformed to configuration , is denoted as . - A
*state space*is defined as the Cartesian product . A state is represented as , in which and . Let(7.13)

and . - For each state, , there is a finite
*action space*, . Let denote the set of all possible actions (the union of over all ). - There is a
*mode transition function*that produces a mode, , for every and . It is assumed that is defined in a way that does not produce race conditions (oscillations of modes within an instant of time). This means that if is fixed, the mode can change at most once. It then remains constant and can change only if is changed. - There is a
*state transition function*, , that is derived from by changing the mode and holding the configuration fixed. Thus, . - A configuration
is designated as the
*initial state*. - A set
is designated as the
*goal region*. A region is defined instead of a point to facilitate the specification of a goal configuration that does not depend on the final mode. - An algorithm must compute a (continuous)
*path*and an*action trajectory*such that and , or the algorithm correctly reports that such a combination of a path and an action trajectory does not exist.

The obstacle region and robot may or may not be mode-dependent, depending on the problem. Examples of each will be given shortly. Changes in the mode depend on the action taken by the robot. From most states, it is usually assumed that a ``do nothing'' action exists, which leaves the mode unchanged. From certain states, the robot may select an action that changes the mode as desired. An interesting degenerate case exists in which there is only a single action available. This means that the robot has no control over the mode from that state. If the robot arrives in such a state, a mode change could unavoidably occur.

The solution requirement is somewhat more complicated because both a path and an action trajectory need to be specified. It is insufficient to specify a path because it is important to know what action was applied to induce the correct mode transitions. Therefore, indicates when these occur. Note that and are closely coupled; one cannot simply associate any with a path ; it must correspond to the actions required to generate .

The set, , of modes needs to encode which key, if any, the robot holds, and it must also encode the status of the doors. The robot may have: 1) the key to Door 1; 2) the key to Door 2; or 3) no keys. The doors may have the status: 1) both open; 2) Door 1 open, Door 2 closed; 3) Door 1 closed, Door 2 open; or 4) both closed. Considering keys and doors in combination yields possible modes.

If the robot is at a portiernia configuration as shown in Figure 7.12b, then its available actions correspond to different ways to pick up and drop off keys. For example, if the robot is holding the key to Door 1, it can drop it off and pick up the key to Door 2. This changes the mode, but the door status and robot configuration must remain unchanged when is applied. The other locations in which the robot may change the mode are when it comes in contact with Door 1 or Door 2. The mode changes only if the robot is holding the proper key. In all other configurations, the robot only has a single action (i.e., no choice), which keeps the mode fixed.

The task is to reach the configuration shown in the lower right with
dashed lines. The problem is solved by: 1) picking up the key for
Door 1 at the portiernia; 2) opening Door 1; 3) swapping the key at the
portiernia to obtain the key for Door 2; or 4) entering the innermost room
to reach the goal configuration. As a final condition, we might want
to require that the robot returns the key to the portiernia.

Example 7.2 allows the robot to change the obstacles
in . The next example involves a robot that can change its shape.
This is an illustrative example of a *reconfigurable robot*. The
study of such robots has become a popular topic of research
[209,385,552,990]; the reconfiguration
possibilities in that research area are much more complicated than the
simple example considered here.

The examples presented so far barely scratch the surface on the possible hybrid motion planning problems that can be defined. Many such problems can arise, for example, in the context making automated video game characters or digital actors. To solve these problems, standard motion planning algorithms can be adapted if they are given information about how to change the modes. Locations in from which the mode can be changed may be expressed as subgoals. Much of the planning effort should then be focused on attempting to change modes, in addition to trying to directly reach the goal. Applying sampling-based methods requires the definition of a metric on that accounts for both changes in the mode and the configuration. A wide variety of hybrid problems can be formulated, ranging from those that are impossible to solve in practice to those that are straightforward extensions of standard motion planning. In general, the hybrid motion planning model is useful for formulating a hierarchical approach, as described in Section 1.4. One particularly interesting class of problems that fit this model, for which successful algorithms have been developed, will be covered next.

Steven M LaValle 2012-04-20