15.1.   INTRODUCTION

This chapter focuses on one of the basic problems that must be faced and
solved by autonomous vehicles - that is, the generation and execution of a
motion plan, aimed at moving the vehicle from its initial location in space to
a given target location, to accomplish a desired task. It is desired that the
motion planning algorithm provide safety and possibly performance guarantees;
moreover, in realistic situations, the motion planning problem must be
solved in real time, using limited on-board computational resources. The
fulfillment of the mission objectives might also require the exploitation of the
full maneuvering capabilities of the vehicle.

The real-time interaction that occurs between the physical components
and the software components of a system such as an autonomous vehicle
creates a new set of challenging problems which have attracted the attention
of both the computer science and the systems and control communities. In
particular, we are concerned with systems which evolve on a state space that
includes both continuous dynamics (i.e., the physical component of system)
and a discrete logic component (i.e., the software component). These systems
are commonly referred to as hybrid systems.

Hybrid control systems have been the object of a very intense and
productive research effort in the recent years, which has resulted in the
definition of very general frameworks (for example, see references 1-3 and
references therein). Using these general frameworks, methods for analyzing
the properties of hybrid systems, such as well-posedness and stability, and for
solving optimal control problems have been developed. However, the applicability
of such methods for nontrivial real-time applications is still limited.
This can be seen as a consequence of the fact that very little structure is
imposed on the system’s dynamics, to preserve the generality of the model.
The main limitation of such approaches is the rapid explosion of the
computation requirements as the number of dimensions of the state space of
the system increases. Stronger results have been obtained for limited classes
of systems, which possess a relatively simple structure [4]. Unfortunately,
these results cannot be readily extended to systems with the rich dynamics of
aerospace vehicles or other complex systems, at least at the desired levels of
performance.

On the other hand, it should be recognized that the dynamics of most
vehicles are inherently continuous, and that the introduction of discrete logic
is a design choice in the development of the flight control software. This
choice is most often linked to hierarchical designs, in which a set of low-level
control laws, driving directly the vehicle’s actuators, is defined for each mode
of operation of the vehicle; a higher level control logic is responsible for
switching among the available modes, and the corresponding control laws
[5-7].