This research aims at delivering fundamental new tools and techniques for how to structure the coordination and control strategies in teams of mobile robots. In particular, two general thrust areas are identified, focusing on human-swarm interactions and deception-based motion control strategies. Although interesting in their own right, the unifying theme behind these two different thrusts is the notion of intent, where the first thrust, which can be thought of as evolving at a higher level of abstraction, focuses on how user intent can be injected into a network of mobile agents in a fundamentally sound manner. The second thrust, in turn, focuses on how the intent can be hidden in order to produce effective, deception-based coordination and pursuit strategies.
Much of the work carried out under this project concerned pursuit and evasion when the agents do not move through still air or water. Once a flow field acts on the players, the set of points each can reach within a given time is no longer a disk centered on its current position, and the geometric constructions that underpin the classical theory stop applying. We built the strategies instead on Zermelo’s navigation problem, which gives the minimum-time steering law in a drift field, and on the partition of the plane it induces: the Zermelo-Voronoi diagram, in which each cell collects the points a given pursuer can reach sooner than any of the others. Because the diagram moves as the flow and the players move, assigning pursuers to targets becomes a matter of tracking a partition that is changing under the agents’ feet. We gave sequential assignment algorithms for this setting, together with conditions on the strength of the flow relative to the pursuers’ speed advantage under which every target is guaranteed to be captured in finite time, and showed that they capture faster than the naive line-of-sight strategy.
A sequential assignment of twelve pursuers to three moving targets in a wind field, computed on the Zermelo-Voronoi diagram. The partition itself moves with the flow and the players, so the assignment is recomputed as the pursuit unfolds.
For several pursuers against one evader in realistic, time-varying flows, we took a reachability view of the same problem. Rather than solving for feedback strategies directly, the forward reachable front of each player is propagated under the flow using a level-set formulation, and the capture time and the optimal paths are read off the first contact between the fronts. This makes the method indifferent to how complicated the flow is: it handles arbitrary spatiotemporal fields, including ones computed from ocean models, and obstacles are accommodated simply by stopping the parts of a front that would otherwise pass through them, so that the recovered paths are collision-free by construction. The approach extends to three dimensions and to flows in which the evader, being slower than its pursuers, can nonetheless escape by exploiting the field. This part of the work was carried out in collaboration with the MSEAS group at MIT.
Optimal pursuer (red) and evader (blue) paths in a vortex, obtained from the evolving reachability fronts. Both players ride the field rather than heading straight for one another, and capture occurs where the two fronts first meet.
Alongside these, we studied the underlying two-player games and the computational tools needed to solve them. We solved an asymmetric version of the two-car game, in which the players differ in speed and turning radius, and the suicidal pedestrian differential game, whose barrier surface we then turned into a collision-avoidance law for a UAV facing an agent whose intentions are unknown. On the computational side, we extended continuous-time differential dynamic programming to problems with terminal constraints, and then to game-theoretic and stochastic settings, which yields a practical way of computing saddle-point trajectories for nonlinear systems without discretizing the state space.
This project is in collaboration with Magnus Egerstedt.
Sponsors
This project is supported by AFOSR.