Informative Path Planning with Limited Adaptivity

We study a stochastic vehicle routing problem arising in robotics, the informative path planning problem (IPP). In this problem, a robot needs to gather information in an uncertain environment by visiting various locations. The goal is to minimize the expected travel cost so as to cover a given monotone submodular function. In a fully adaptive solution, the robot may incorporate all observed information in order to select the next location to visit. Although such adaptive solutions achieve the best objective value, they are resource intensive because they entail recomputing after every visited location. In this paper, we consider a more practical class of solutions that require only a small number of adaptive “rounds,” where the robot recomputes only once at the start of each round. We design an algorithm for IPP parameterized by the number of adaptive rounds, and provide a smooth trade-off between the number of rounds and the solution quality (relative to fully adaptive solutions). We validate our theoretical results through experiments on previously used synthetic instances as well as a real road network. We observe that the cost using just two rounds of adaptivity is typically within 12% (for synthetic instances) and 50% (for road network instances) of the fully adaptive cost. Moreover, the runtime is over 15 times faster.

History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete.

Funding: This research was supported in part by the National Science Foundation, Division of Computing and Communication Foundations [CCF-2418495].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0893) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0893). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.