Probabilistic Maximum Set Cover with Path Constraints for Informative Path Planning
- Publisher:
- ARAA
- Publication Type:
- Conference Proceeding
- Citation:
- Website Proceedings of Australasian Conference on Robotics and Automation 2016, 2016, pp. 1 - 10
- Issue Date:
- 2016-12
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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.
Please use this identifier to cite or link to this item: