## 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.

Formulation 7..3 (Hybrid-System Motion Planning)
1. The and components from Formulation 4.1 are included.
2. A nonempty mode space, that is a finite or countably infinite set of modes.
3. A semi-algebraic obstacle region for each .
4. 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 .
5. A state space is defined as the Cartesian product . A state is represented as , in which and . Let

 (7.13)

and .
6. For each state, , there is a finite action space, . Let denote the set of all possible actions (the union of over all ).
7. 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.
8. There is a state transition function, , that is derived from by changing the mode and holding the configuration fixed. Thus, .
9. A configuration is designated as the initial state.
10. 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.
11. 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 .

Example 7..2 (The Power of the Portiernia)   In this example, a robot, , is modeled as a square that translates in . Therefore, . The obstacle region in 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, , 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.

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 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 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 2020-08-14