Probabilistic Maximum Set Cover with Path Constraints for Informative Path Planning

Abstract

We pose a new formulation for informative path planning problems as a generalisation of the well-known maximum set cover problem. This new formulation adds path constraints and travel costs, as well as a probabilistic observation model, to the maximum set cover problem. Our motivation is informative path planning applications where the observation model can be naturally encoded as overlapping subsets of a set of discrete elements. These elements may include features, landmarks, regions, targets or more abstract quantities, that the robot aims to observe while moving through the environment with a given travel budget. This formulation allows directly modelling the dependencies of observations from different viewpoints. We show this problem is NP-hard and propose a branch and bound tree search algorithm. Simulated experiments empirically evaluate the bounding heuristics, several tree expansion policies and convergence rate towards optimal. The tree pruning allows finding optimal or bounded-approximate solutions in a reasonable amount of time, and therefore indicates our work is suitable for practical applications.