The goal of this project was to develop and test strategies for controlling several unmanned vehicles pursuing a common goal under external disturbances and uncertainty. The disturbances are the medium the vehicles move through — winds for aerial vehicles, currents for marine vehicles, surrounding traffic for self-driving cars. The uncertainty is of a different kind: it comes from the gap between how an adversary actually behaves and how it is perceived to behave, that is, from asymmetric information. Within that setting the project sought decentralized strategies for the players of a multi-player pursuit-evasion game, computed efficiently enough to be useful.
The starting point was the two-pursuer, single-evader problem under different information structures, with both pursuers faster than the evader and no external disturbance, for which the time-optimal evading strategies were identified. The useful object here is the region of non-degeneracy. If the players begin in a degenerate configuration, one of the two pursuers plays no part in the game at all and the evader’s optimal strategy is pure evasion from the other; the non-degenerate region is therefore exactly where a second pursuer buys anything. Optimal evasion against relay pursuit was studied in the same way, by holding one pursuer stationary.
Regions of degeneracy and non-degeneracy when the pursuers use a constant-bearing strategy, for three configurations. The yellow region is where the second pursuer changes the outcome; outside it the game reduces to a single pursuer.
The same regions when the pursuers use pure pursuit. The boundaries differ from the constant-bearing case, so which pursuit law the adversaries use changes where a second pursuer is worth deploying.
These results generalize from two pursuers to many. In both cases the time-optimal evading strategy turns out to depend only on the initial positions of those pursuers that capture the evader at the final time. Since neither that strategy nor the identity of the capturing pursuers is available in closed form, we introduced instead a notion of the relevance of a pursuer to the evader, computed from the positions of all the players by way of Apollonius circles. Relevance can be evaluated online, so pursuers can be assigned to the capture task dynamically, whatever evading strategy is in play. Combining Apollonius circles with Voronoi partitions extends the same idea to the multi-pursuer, multi-evader setting, with a guarantee that every evader is captured in finite time.
Dynamic task allocation in a multi-pursuer, multi-evader engagement. Assignments are recomputed as the players move, rather than fixed at the outset.
A second thread concerns steering a distribution rather than a state. We considered a discrete-time linear system to be driven from an initial Gaussian distribution to a final one, in a game-theoretic setting: one player minimizes a quadratic payoff while trying to meet a prescribed mean and covariance at the terminal time, and the other maximizes the same payoff while being indifferent to that terminal constraint. The unconstrained game was treated first, giving necessary conditions for a saddle point. We then showed that the one-sided constrained game need not admit a solution at all, analyzed the players’ best responses in that case, and finally recovered a tractable formulation by converting the problem of steering the distribution under an adversary into a convex program.
Terminal covariance met (left) and missed (right). The mean can be steered to the target in both cases; whether the covariance constraint can be met as well is what the one-sided constrained game does not guarantee.
A third thread addresses optimal control problems with parametric uncertainty, through desensitized optimal control. A sensitivity function records the first-order variation of the state under a change in the parameters at a given instant along a trajectory, and we showed that it can be used to desensitize either a whole optimal trajectory or the state at one particular instant, the final state being the case of most interest.
Desensitized trajectories for a time-optimal Zermelo problem, where weights the sensitivity cost (left), and the spread of the corresponding Monte-Carlo runs under parameter variation (right). A larger weight buys a trajectory that is less sensitive, at the price of a longer path.
Sponsors
This project is supported by NSF.