7.3.1 Hybrid Systems Framework

Figure 7.11: A hybrid state space can be imagined as having layers of C-spaces that are indexed by modes.

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.

Formulation 7..3 (Hybrid-System Motion Planning)  

1. The ${\cal W}$ and ${\cal C}$ components from Formulation 4.1 are included.
2. A nonempty mode space, $M$ that is a finite or countably infinite set of modes.
3. A semi-algebraic obstacle region ${\cal O}(m)$ for each $m \in M$.
4. A semi-algebraic robot ${\cal A}(m)$, for each $m \in M$. 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 $q$, is denoted as ${\cal A}(q,m)$.
5. A state space $X$ is defined as the Cartesian product $X = {\cal C}\times M$. A state is represented as $x = (q,m)$, in which $q \in {\cal C}$ and $m \in M$. Let

   $$X_{obs} = \{ (q,m) \in X \;\vert\; {\cal A}(q,m) \cap {\cal O}(m) \not = \emptyset\},$$ (7.13)

   
   
   and $X_{free} = X \setminus X_{obs}$.
6. For each state, $x \in X$, there is a finite action space, $U(x)$. Let $U$ denote the set of all possible actions (the union of $U(x)$ over all $x \in X$).
7. There is a mode transition function $f_m$ that produces a mode, $f_m(x,u) \in M$, for every $x \in X$ and ${ u}\in U(x)$. It is assumed that $f_m$ is defined in a way that does not produce race conditions (oscillations of modes within an instant of time). This means that if $q$ is fixed, the mode can change at most once. It then remains constant and can change only if $q$ is changed.
8. There is a state transition function, $f$, that is derived from $f_m$ by changing the mode and holding the configuration fixed. Thus, $f(x,u) = (q,f_m(x,u))$.
9. A configuration ${x_{I}}\in {X_{free}}$ is designated as the initial state.
10. A set ${X_{G}}\in {X_{free}}$ 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.
11. An algorithm must compute a (continuous) path $\tau: [0,1] \rightarrow {X_{free}}$ and an action trajectory $\sigma : [0,1] \rightarrow U$ such that $\tau(0) = {x_{I}}$ and $\tau(1) \in {X_{G}}$, 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, $\sigma$ indicates when these occur. Note that $\tau$ and $\sigma$ are closely coupled; one cannot simply associate any $\sigma$ with a path $\tau$; it must correspond to the actions required to generate $\tau$.

Figure 7.12: In the upper left (at the portiernia), the robot can pick up and drop off keys that open one of two doors. If the robot contacts a door while holding the correct key, then it opens.

Example 7..2 (The Power of the Portiernia)   In this example, a robot, ${\cal A}$, is modeled as a square that translates in ${\cal W}= {\mathbb{R}}^2$. Therefore, ${\cal C}= {\mathbb{R}}^2$. The obstacle region in ${\cal W}$ is mode-dependent because of two doors, which are numbered ``1'' and ``2'' in Figure 7.12a. In the upper left sits the portiernia,^7.2 which is able to give a key to the robot, if the robot is in a configuration as shown in Figure 7.12b. The portiernia only trusts the robot with one key at a time, which may be either for Door 1 or Door 2. The robot can return a key by revisiting the portiernia. As shown in Figures 7.12c and 7.12d, the robot can open a door by making contact with it, as long as it holds the correct key.

The set, $M$, 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 $12$ 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 $f$ 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. $\blacksquare$

Figure 7.13: An example in which the robot must reconfigure itself to solve the problem. There are two modes: elongated and compressed.

Figure 7.14: When the robot reconfigures itself, ${\cal C}_{free}(m)$ changes, enabling the problem to be solved.

Example 7.2 allows the robot to change the obstacles in ${\cal O}$. 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.

Example 7..3 (Reconfigurable Robot)   To solve the problem shown in Figure 7.13, the robot must change its shape. There are two possible shapes, which correspond directly to the modes: elongated and compressed. Examples of each are shown in the figure. Figure 7.14 shows how ${\cal C}_{free}(m)$ appears for each of the two modes. Suppose the robot starts initially from the left while in the elongated mode and must travel to the last room on the right. This problem must be solved by 1) reconfiguring the robot into the compressed mode; 2) passing through the corridor into the center; 3) reconfiguring the robot into the elongated mode; and 4) passing through the corridor to the rightmost room. The robot has actions that directly change the mode by reconfiguring itself. To make the problem more interesting, we could require the robot to reconfigure itself in specific locations (e.g., where there is enough clearance, or possibly at a location where another robot can assist it).

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 $X$ 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 $X$ 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.