Optimal Trajectory Planning and Assignment Problems for Kinematic Agents with State-Dependent Metrics

In the recent years there has been an increased interest in developing control and navigation strategies for multi-agent systems. Typical tasks include guiding a team of small autonomous agents (e.g., UAVs, UUVs) towards a given goal, or assigning a set of stationary or moving targets to a team of pursuing agents.  For heterogeneous teams of kinematic agents or for agents whose motion is affected by the environment they operate in (for example, the motion of unmanned aerial or marine/submersible vehicles may be significantly affected by the prevailing local winds or sea currents). For such problems the Euclidean distance may not be an appropriate figure of merit to define suitable proximity relationships. Instead, time-to-intercept or fuel-to-consume may be a more appropriate cost to use. In this talk, we will discuss the optimal partitioning problem for a team of agents in the plane when the proximity relationships are dominated by such state-dependent metrics. We will introduce the concept of Zermelo-Voronoi partitions to analyze the particular case of a team of UAVs/UUVs operating in the presence of winds or currents.  We provide a numerically efficient construction of these partitions by taking advantage of the structure of the underlying optimal control problem, which may include both regular and abnormal extremals. By exploiting the well-known duality between navigation in the presence of environmental disturbances and pursuit problems, we will then utilize these partitions to solve a certain class of group pursuit problems. We will finally briefly elaborate on some potential extensions.