Multi-Agent Nonholonomic Systems with Spatio-Temporal Constraints

The goal of this thesis is to study the problem of designing a path planner for a set of unmanned vehicles in the following scenario: The planner receives a request for a plan for a specified subset of vehicles under its control. The planner also receives an entry and exit state for each vehicle (3-D location, velocity vector and time of arrival). In addition, the planner receives additional information; such as obstacle or threat locations, no-fly zones and sensor availability. The task of the planner is to generate trajectories that maximize spatio-temporal coverage while satisfying such hard constraints as collision avoidance and specifications on initial and final positions. This is an example of a multi-vehicle path planning problem with spatio-temporal specifications. In this thesis we introduce a novel technique using elastic multi-particle dynamical systems for addressing general bounded curvature path planning problems with such spatio-temporal constraints. The trajectories of vehicles are approximated using sequence of waypoints, and each waypoint is treated as a moving particle in the space. We define nonsmooth interaction forces between the particles such that the resulting multi-particle system is stable; moreover, the trajectories generated by the waypoints in the equilibria of the multi-particle system satisfy all of the hard constraints such as bounded-curvature constraints and obstacle avoidance. Since we are using discontinuous dynamical system, we need nonsmooth analysis and stability of nonsmooth systems to analyze the dynamical system with discontinuous righthand sides. When considering a discontinuous vector field the classical notion of solution to the dynamical system is too restrictive and may not exist. In this thesis we use Filippov solutions concept for differential equations whose right-hand sides are only required to be Lebesgue measurable in the state and time variables. For stability analysis we use nonsmooth Lyapunov stability theory and LaSalle's invariance principle for a class of nonsmooth Lipschitz continuous Lyapunov functions. This approach could be used for variety of problems, including multi-vehicle path planning in a dynamically-changing environment, coverage problem and multi-vehicle rendezvous problem. The unique advantage of this technique is its ability to accommodate a new task without violating other constraints. For example, consider the example given above, we can easily add other tasks such as rendezvous or avoiding moving obstacles to the planner.