Surveillance of perimeters and securing perimeters are important tasks in civilian and military defense applications, and it has become practical to deploy a large number of autonomous agents to address these problems using multi-robot systems.
A recent paper by members of the DCIST alliance formulates this scenario as a variant of multi-player pursuit-evasion games, where we suppose that intruders must be intercepted before they can reach a region of interest. Finding the optimal strategies in such a game is challenging due to the high dimensionality of the joint state space. To perform a tractable analysis, we developed a decomposition method that reduces the problem to an efficient combinatorial optimization problem . We derived a set of intruder and defender team strategies, and proved their optimality in the sense that they form a Nash equilibrium. In addition, our algorithm finds the upper bound on the number of intrusions which the defender team can certify at the beginning of a game.
Highlight Video: https://youtu.be/6zUPkzh_iPU
The performance certified by the defender team can also be used to inform higher level coalition forming algorithms. In the extension of the above work, we considered a scenario where defensive agents have limited sensor footprint, and so they deploy both defenders to intercept along the perimeter and patrollers to scout outside the defended region. In this context, the problems of team formation and task allocation were studied . In particular, we consider how uncertainty in the environment or opponent capabilities introduce uncertainty in the parameters (speed advantage, detection range, and capture range). When designing a team to satisfy a task specification, species may be selected to complement each other both with respect to trait specialization under any known environment but also with respect to their complementary variability when the environment (as modeled by trait parameters) is uncertain.
 D. Shishika, J. Paulos, and Vijay Kumar. “Cooperative team strategies for multi-player perimeter- defense games,” Accepted to IEEE Robotics and Automation Letters, available at https://arxiv. org/abs/1912.04342.
 D. Shishika, J. Paulos, M. R. Dorothy, M. A. Hsieh, and V. Kumar. “Team Composition for Perimeter Defense with Patrollers and Defenders,” IEEE Conference on Decision and Control, pp. 7325-7332, France, 2019.
RA2.A1: Abstraction of Task Diversity
RA2.A3: Composable Autonomy in Heterogeneous Groups
Points of Contact:
Vijay Kumar (PI), Daigo Shishika, James Paulos, Douglas Macharet