Advances in autonomous vehicles and networked control systems have created a need for more flexible mission planning and execution architectures than the traditional single-platform, monolithic paradigm allows, in military and civilian applications alike. A network of autonomous vehicles promises more robust planning and execution at higher levels of autonomy, across applications from environmental monitoring and distributed surveillance to resource allocation and the tracking of multiple targets. This network-centric paradigm has teams of aerial, terrestrial and underwater vehicles working in unison, exchanging information to plan and execute a common mission in a decentralized yet cooperative manner, and it brings with it a slew of hard problems: persistent communication, coordinated task assignment and prioritization, distributed estimation and distributed decision-making.
These challenges are sharper still for small UAVs and MAVs, whose dynamic response is dominated by short time scales and which interact strongly with their environment — winds, pop-up threats — while carrying limited computational and power resources on board. The objective of this research was therefore to develop coordination strategies for teams of such vehicles that account for the interaction with the environment, and to do so efficiently enough to run on board.
Motion coordination and path planning were approached through state-dependent performance metrics that capture the vehicle’s interaction with the environment, the mission objectives and the system-theoretic attributes of the network. The generalized Zermelo-Voronoi diagram plays the central role. A standard Voronoi decomposition partitions space by Euclidean distance; a generalized Zermelo-Voronoi diagram partitions it by a metric that reflects the agents’ dynamics, such as the estimated time of arrival in the presence of a wind field, which is what actually determines which agent should service which point.
A generalized Voronoi partition. Each cell collects the points that one agent reaches before any other, with the nested curves marking equal time-to-go from that agent.
Two problems follow from this. The first is computational: building generalized Voronoi diagrams with respect to a suitable generalized metric, by algorithms simple and efficient enough to be distributed, with the partition tailored to the mission at hand. The second is to use those diagrams to characterize the proximity relations between agents, and between agents and a set of targets. Together they support decentralized and distributed control strategies across a wide spectrum of applications: environmental monitoring, distributed surveillance, multiple target allocation, coordinated intercept and landing-site selection.
The Zermelo-Voronoi diagram and its dual, for two different wind fields, drawn over the Euclidean Voronoi diagram of the same generators. The wind alone is enough to reassign large regions from one agent to another.
The same construction answers a pursuit problem. When several pursuers chase a single evader in a flow field, it is wasteful for all of them to chase at once; the relay pursuit scheme instead assigns the pursuit to the one pursuer that can reach the evader soonest, and hands it off as the evader moves and that assignment changes. The hand-off rule falls directly out of the partition, which is what makes the scheme cheap enough to run online. Alongside this, we characterized time-optimal and feedback navigation for a vehicle in a known wind field, and studied pursuit-evasion games in which the dynamics are stochastic, where the saddle-point solution is obtained by linking the game to a stochastic optimal control problem.
Sponsors
This project is supported by NSF.