We present a new mixed integer formulation for the discrete informative path planning problem in random fields. The objective is to compute a budget constrained path while collecting measurements whose linear estimate results in minimum error over a finite set of prediction locations. The problem is known to be NP-hard. However, we strive to compute optimal solutions by leveraging advances in mixed integer optimization. Our approach is based on expanding the search space so we optimize not only over the collected measurement subset, but also over the class of all linear estimators. This allows us to formulate a mixed integer quadratic program that is convex in the continuous variables. The formulations are general and are not restricted to any covariance structure of the field. In simulations, we demonstrate the effectiveness of our approach over previous branch and bound algorithms.
|Title of host publication||Proceedings of the IEEE 61st Conference on Decision and Control (CDC 2022)|
|Publication status||Published - 2022|
|Event||IEEE 61st Conference on Decision and Control (CDC 2022) - Cancún, Mexico|
Duration: 6 Dec 2022 → 9 Dec 2022
|Conference||IEEE 61st Conference on Decision and Control (CDC 2022)|
|Period||6/12/22 → 9/12/22|
Bibliographical noteGreen Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
- Integer programming
- Measurement uncertainty
- Prediction algorithms
- Approximation algorithms
- Path planning