Randomized algorithm for informative path planning with budget constraints
Authors:
- 1 May 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 4997-5004
Abstract
Maximizing information gathered within a budget is a relevant problem for information gathering tasks for robots with cost or operating time constraints. This problem is also known as the informative path planning (IPP) problem or correlated orienteering. It can be formalized as that of finding budgeted routes in a graph such that the reward collected by the route is maximized, where the reward at nodes can be dependent. Unfortunately, the problem is NP-Hard and the state of the art methods are too slow to even present an approximate solution online. Here we present Randomized Anytime Orienteering (RAOr) algorithm that provides near optimal solutions while demonstrably converging to an efficient solution in runtimes that allows the solver to be run online. The key idea of our approach is to pose orienteering as a combination of a Constraint Satisfaction Problem and a Traveling Salesman Problem. This formulation allows us to restrict the search space to routes that incur minimum distance to visit a set of selected nodes, and rapidly search this space using random sampling. The paper provides the analysis of asymptotic near-optimality, convergence rates for RAOr algorithms, and present strategies to improve anytime performance of the algorithm. Our experimental results suggest an improvement by an order of magnitude over the state of the art methods in relevant simulation and in real world scenarios.Keywords
This publication has 15 references indexed in Scilit:
- PASP: Policy based approach for sensor planning2015
- Information-theoretic mapping using Cauchy-Schwarz Quadratic Mutual Information2015
- Emergency maneuver library - ensuring safe navigation in partially known environments2015
- Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks2014
- Improved algorithms for orienteering and related problemsACM Transactions on Algorithms, 2012
- The orienteering problem: A surveyEuropean Journal of Operational Research, 2011
- A probabilistic algorithm for k-SAT and constraint satisfaction problems2003
- A frontier-based approach for autonomous exploration2002
- The orienteering problemNaval Research Logistics (NRL), 1987
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978