Reachable Set Approximation as a Non-Cooperative Multi-Agent Coverage Game

We estimate the reachable set of a dynamical system by posing reachable set construction as a multi-agent coverage problem. As the terminology implies, the reachable set is the set of all states that can be reached within a specified time, using exogenous inputs with a specified bound, and starting from a specified initial condition. In multi-agent coverage, mobile agents self-deploy in an online manner to cover a region that is unknown a priori. The mapping between the two settings is the unknown region being the reachable set. Using time discretization and randomized spatial discretization, the proposed algorithm simultaneously generates a finite graph contained within the true reachable set and deploys the agents to optimally cover the graph. The utilized game-theoretic methods assure that, asymptotically, the agents self-deploy in a manner that provides optimal coverage with high probability. The accuracy of the approximation of the reachable set depends on the temporal and spacial discretization. The proposed algorithm is illustrated on different dynamical systems, where the performance is compared to related scenario-based approaches to reachable set estimation.