Home/Randomized Algorithm for Informative Path Planning with Budget Constraints

Randomized Algorithm for Informative Path Planning with Budget Constraints

Sankalp Arora and Sebastian Scherer
Conference Paper, International Conference on Robotics and Automation (ICRA), June, 2017, May, 2017

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


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 Orien- teering (RAOr) algorithm that provides near optimal solutions while demonstrably converging to an efficient solution in run- times 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.

BibTeX Reference
title = {Randomized Algorithm for Informative Path Planning with Budget Constraints},
author = {Sankalp Arora and Sebastian Scherer},
booktitle = {International Conference on Robotics and Automation (ICRA), June, 2017},
keyword = {Orienteering, correlated orienteering, budgeted exploration, RAOr, informative, path, planning, exploration, planning},
sponsor = {Office of Naval Research, Qualcomm},
publisher = {IEEE},
month = {May},
year = {2017},