Informative Path Planning with Limited Adaptivity

Rayen Tan, Rohan Ghuge, Viswanath Nagarajan
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:4006-4014, 2024.

Abstract

We consider the informative path planning (IPP) problem in which a robot interacts with an uncertain environment and gathers information by visiting locations. The goal is to minimize its expected travel cost to cover a given submodular function. Adaptive solutions, where the robot incorporates all available information to select the next location to visit, achieve the best objective. However, such a solution is resource-intensive as it entails recomputing after every visited location. A more practical approach is to design solutions with a small number of adaptive "rounds", where the robot recomputes only once at the start of each round. In this paper, we design an algorithm for IPP parameterized by the number k of adaptive rounds, and prove a smooth tradeoff between k and the solution quality (relative to fully adaptive solutions). We validate our theoretical results by experiments on a real road network, where we observe that a few rounds of adaptivity suffice to obtain solutions of cost almost as good as fully-adaptive ones.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-tan24a, title = {Informative Path Planning with Limited Adaptivity}, author = {Tan, Rayen and Ghuge, Rohan and Nagarajan, Viswanath}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {4006--4014}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/tan24a/tan24a.pdf}, url = {https://proceedings.mlr.press/v238/tan24a.html}, abstract = {We consider the informative path planning (IPP) problem in which a robot interacts with an uncertain environment and gathers information by visiting locations. The goal is to minimize its expected travel cost to cover a given submodular function. Adaptive solutions, where the robot incorporates all available information to select the next location to visit, achieve the best objective. However, such a solution is resource-intensive as it entails recomputing after every visited location. A more practical approach is to design solutions with a small number of adaptive "rounds", where the robot recomputes only once at the start of each round. In this paper, we design an algorithm for IPP parameterized by the number k of adaptive rounds, and prove a smooth tradeoff between k and the solution quality (relative to fully adaptive solutions). We validate our theoretical results by experiments on a real road network, where we observe that a few rounds of adaptivity suffice to obtain solutions of cost almost as good as fully-adaptive ones.} }
Endnote
%0 Conference Paper %T Informative Path Planning with Limited Adaptivity %A Rayen Tan %A Rohan Ghuge %A Viswanath Nagarajan %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-tan24a %I PMLR %P 4006--4014 %U https://proceedings.mlr.press/v238/tan24a.html %V 238 %X We consider the informative path planning (IPP) problem in which a robot interacts with an uncertain environment and gathers information by visiting locations. The goal is to minimize its expected travel cost to cover a given submodular function. Adaptive solutions, where the robot incorporates all available information to select the next location to visit, achieve the best objective. However, such a solution is resource-intensive as it entails recomputing after every visited location. A more practical approach is to design solutions with a small number of adaptive "rounds", where the robot recomputes only once at the start of each round. In this paper, we design an algorithm for IPP parameterized by the number k of adaptive rounds, and prove a smooth tradeoff between k and the solution quality (relative to fully adaptive solutions). We validate our theoretical results by experiments on a real road network, where we observe that a few rounds of adaptivity suffice to obtain solutions of cost almost as good as fully-adaptive ones.
APA
Tan, R., Ghuge, R. & Nagarajan, V.. (2024). Informative Path Planning with Limited Adaptivity. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:4006-4014 Available from https://proceedings.mlr.press/v238/tan24a.html.

Related Material