Decentralized Information-driven Approach for Tracking Multiple Moving Targets with Multi-Robot Networks

Significant advances in robot sensing and mobility have enabled the use of multi-robot networks to track multiple targets moving in an environment. Tracking moving targets that outnumber the size of the robot network involves the network to collaboratively assume a subset of targets to be tracked and plan the actions of the robots. This paper focuses on the scenario when the targets outnumber the robots in the network. The goal of the network is to assign targets to the robots and plan robot actions to track these assigned targets. This has to be done consistently as the robots and targets move in the environment to ensure the tracking performance is maximized. However, this problem, as shown in this paper, is NP-hard. This paper leverages decomposition theory to solve this problem efficiently in real-time in two stages. The first stage leverages inter-robot communication in the network to assign robots to targets, and the second stage, solved on each robot locally, optimizes the control to track the targets assigned to it. A novel decentralized approach, called bundle-based assignment, is presented to find adaptive and conflict-free target assignment in the first stage that guarantees \(\frac{1}{2}\) $\frac{1}{2}$ -approximation in the worst case. Since robots can be assigned more than one target, the second stage optimizing for control is shown to take the form of a multi-objective control problem with conflicting objectives, and a strategy is proposed to solve it for real-time applications. A novel information-gain-based tracking objective is developed, which can be used to solve the two stages, suited specifically for the scenario under consideration. Simulation results show that the novel approach, called bundle-based assignment and control (BBAC), optimizing the novel tracking objective, outperforms existing algorithms and achieves performance very close to that of the optimal solution in a shorter time. Physical experiments with a network of ground robots tracking human targets further validate the applicability of these approaches in the real world.