Multi-agent persistent monitoring in stochastic environments with temporal logic constraints

Abstract

In this paper, we consider the problem of generating control policies for a team of robots moving in an environment containing elements with probabilistic behaviors. The team is required to achieve an optimal surveillance mission, in which a certain proposition needs to be satisfied infinitely often. The goal is to minimize the average time between satisfying instances of the proposition, while ensuring that the mission is accomplished. By modeling the robots as Transition Systems and the environmental elements as Markov Chains, the problem reduces to finding an optimal control policy satisfying a temporal logic specification on a Markov Decision Process. The existing approaches for this problem are computational intensive and therefore not feasible for a large environment or a large number of robots. To address this issue, we propose an approximate dynamic programming framework. Specifically, we choose a set of basis functions to approximate the optimal cost and find the best parameters for these functions based on the least-square approximation. We develop an approximate policy iteration algorithm to implement our framework. We provide illustrative case studies and evaluate our method through simulations.