Multi-agent Multi-target Path Planning in Markov Decision Processes

Inspired by autonomous vehicles operating underwater, we consider the problem of visiting a set of targets in minimum time by a team of non-communicating agents in a Markov decision process (MDP). The single-agent problem is at least NP-complete by reducing it to a Hamiltonian path problem. Even if the optimal solution to the single-agent problem is known, the multi-agent problem is NP-hard. 

1. An optimal algorithm for the single-agent problem based on Bellman’s optimality equation is exponential in the number of target states. 

2. We proposed a sub-optimal algorithm that is polynomial at each time step. 

3. Our algorithm generates optimal policies for certain classes of MDPs. 

4. We proposed a target partitioning algorithm that approximately minimizes the expected time to visit the targets for the multi-agent scenario. 

5. Our partitioning algorithm generates optimal partitions for clustered target scenarios. 

6. Our algorithms perform much faster than the optimal procedure and more optimal than the currently available heuristic on random MDPs and gridworld environments inspired by ocean dynamics.