情報経路計画のための近似逐次最適化
Approximate Sequential Optimization for Informative Path Planning
グラフ上で情報量を最大化する経路を、凸緩和と動的計画法による逐次近似で効率的に求める手法を提案。
著者: Joshua Ott, Mykel J. Kochenderfer, Stephen Boyd
分類: cs.RO
原文アブストラクト
We consider the problem of finding an informative path through a graph, given initial and terminal nodes and a given maximum path length. We assume that a linear noise corrupted measurement is taken at each node of an underlying unknown vector that we wish to estimate. The informativeness is measured by the reduction in uncertainty in our estimate, evaluated using several metrics. We present a convex relaxation for this informative path planning problem, which we can readily solve to obtain a bound on the possible performance. We develop an approximate sequential method where the path is constructed segment by segment through dynamic programming. This involves solving an orienteering problem, with the node reward acting as a surrogate for informativeness, taking the first step, and then repeating the process. The method scales to very large problem instances and achieves performance not too far from the bound produced by the convex relaxation. We also demonstrate our method's ability to handle adaptive objectives, multimodal sensing, and multi-agent variations of the informative path planning problem.
