Research Vision: Multi-Agent Path Planning for Cops And Robbers Via Reactive Synthesis
This work addresses path planning in multi-agent systems for applications like security or robotics, but it is incremental as it formalizes the problem and proposes directions without presenting concrete results.
The paper tackles the problem of multi-agent path planning for a generalized Cops and Robbers game using reactive synthesis, aiming to determine if a winning strategy exists for cops and construct it as an executable program.
We propose the problem of multi-agent path planning for a generalization of the classic Cops and Robbers game via reactive synthesis. Specifically, through the application of LTLt and Coordination Synthesis, we aim to check whether various Cops and Robbers games are realizable (a strategy exists for the cops which guarantees they catch the robbers). Additionally, we construct this strategy as an executable program for the multiple system players in our games. In this paper we formalize the problem space, and propose potential directions for solutions. We also show how our formalization of this generalized cops and robbers game can be mapped to a broad range of other problems in the reactive program synthesis space.