Informative Path Planning in Random Fields via Mixed Integer Programming

Shamak Dutta, N. Wilde, Stephen L. Smith

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationProceedings of the IEEE 61st Conference on Decision and Control (CDC 2022)
ISBN (Print)978-1-6654-6761-2
Publication statusPublished - 2022
EventIEEE 61st Conference on Decision and Control (CDC 2022) - Cancún, Mexico
Duration: 6 Dec 20229 Dec 2022


ConferenceIEEE 61st Conference on Decision and Control (CDC 2022)

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
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
  • Optimization
  • Robots


Dive into the research topics of 'Informative Path Planning in Random Fields via Mixed Integer Programming'. Together they form a unique fingerprint.

Cite this