Informative Path Planning in Random Fields via Mixed Integer Programming
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Efficient Online Learning and Adaptive Planning for Robotic Information Gathering Based on Streaming Data
Robotic information gathering (RIG) techniques refer to methods where mobile robots are used to acquire data about the physical environment with a suite of sensors. Informative planning is an important part of RIG where …
Streaming Gaussian Dirichlet Random Fields for Spatial Predictions of High Dimensional Categorical Observations
We present the Streaming Gaussian Dirichlet Random Field (S-GDRF) model, a novel approach for modeling a stream of spatiotemporally distributed, sparse, high-dimensional categorical observations. The proposed approach ef…
Safe Aerial 3D Path Planning for Autonomous UAVs using Magnetic Potential Fields
Safe autonomous Uncrewed Aerial Vehicle (UAV) navigation in urban environments requires real-time path planning that avoids obstacles. MaxConvNet is a potential-field planner that leverages properties of Maxwell's equati…
LIPP: Load-Aware Informative Path Planning with Physical Sampling
In classical Informative Path Planning (C-IPP), robots are typically modeled as mobile sensors that acquire digital measurements such as images or radiation levels. In this model, since making a measurement leaves the ro…
DyPNIPP: Predicting Environment Dynamics for RL-based Robust Informative Path Planning
Informative path planning (IPP) is an important planning paradigm for various real-world robotic applications such as environment monitoring. IPP involves planning a path that can learn an accurate belief of the quantity…
Reinforcement Learning (RL)