Collaborative Task Allocation and Motion Planning for Multi-Agent Systems in the Presence of Adversaries

Abstract

The presence of adversarial robotic swarms, a large number of small robotic vehicles operating together, around safety-critical areas such as airports, military bases, and government facilities, with the intention of collecting critical information, or physically damaging the area, could have disastrous consequences. In this dissertation, we consider a multi-agent area defense game that consists of 1) a swarm of autonomous, adversarial robotic vehicles (called attackers) that aims to reach a safety-critical area, 2) a team of autonomous robotic vehicles (called defenders) that aims to prevent the attackers from reaching the safety-critical area and thereby preventing any damage that could be inflicted by the attackers. We consider two types of attackers: i) risk-averse, attackers that want to survive, ii) risk-taking, attackers that do not necessarily care about their own survival in an attempt to reach the safety-critical area. We provide collaborative task assignment and motion planning algorithms for the team of defenders so that they prevent the possible damage that could be caused by the presence of both risk-averse as well as risk-taking attackers in the neighborhood of the safety-critical area. First, `StringNet Herding' algorithm is developed for the defenders to herd risk-averse attackers to a pre-specified safe area away from the safety-critical area in an obstacle-populated environment. In this method, the `risk-averse attackers, which move away from the defenders, are enclosed inside a closed formation of barriers, called `StringNet', formed by the defenders, so that the motion of the attackers is restricted to the interior of `StringNet' and the attackers can be herded safely to the safe area. A combination of open-loop time-optimal and state-feedback finite-time control laws is developed, which provides a strategy for the defenders to successfully perform `StringNet Herding' in an obstacle-populated environment. The `StringNet Herding' is demonstrated through simulations as well as through an experimental demonstration using quadrotor vehicles. The `StringNet Herding' approach is extended to scenarios where the adversarial swarm may split into multiple small swarms. Second, an inter-defender collision-aware interception strategy (IDCAIS) is developed for the defenders to intercept as many risk-taking attackers and as quickly as possible, while ensuring that the defenders do not collide with each other. The defenders are assigned to intercept attackers using a mixed-integer quadratic program (MIQP) that: 1) minimizes the sum of times taken by the defenders to capture the attackers under time-optimal control, and 2) helps eliminate or delay possible future collisions among the defenders on the optimal trajectories. To prevent inevitable collisions on optimal trajectories, or collisions arising due to time-sub-optimal behavior by the attackers, a minimally-augmented control using an exponential control barrier function is provided for each defender. Finally, an integrated strategy is provided for the defenders by combining the `StringNet Herding' strategy against the risk-averse attackers and the collision-aware interception strategy, IDCAIS, against the risk-taking attackers in a collaborative framework. Several algorithms are developed using mixed-integer programs (MIPs) and geometry-inspired heuristics to group and assign teams of defenders, or individual defenders, to either herd swarms of the risk-averse attackers, or intercept the risk-taking attackers in response to behaviors by the attackers such as splitting into smaller swarms to evade defenders, or high-speed maneuvers by risk-taking attackers to maximize damage to the protected area. A theoretical as well as numerical comparison of the computational costs of these MIPs and the geometry-inspired heuristics is provided.