Multi-agent Visibility-Based Target Tracking Game

In this paper, we address the problem of visibility-based target tracking for a team of mobile observers trying to track a team of mobile targets. Based on the results of previous work, the notion of pursuit fields around a single corner is introduced. We use the pursuit fields to generate navigation strategies for a single observer to track a single target in general environments. In order to tackle the case when more than one observer or target is present in the environment, we propose a two level hierarchical approach. At the upper level, the team of observers use a ranking and aggregation technique for allocating each target to an observer. At the lower level, each observer computes its navigation strategy based on the results of the single observer-single target problem, thereby, decomposing a large multi-agent problem into several 2-agent problems. Finally, we present a scalable algorithm that can accommodate an arbitrary number of observers and targets. The performance of this algorithm is evaluated based on simulation and implementation.