不完全なセンサを用いた探索のための保証付き手法
Provable Methods for Searching with an Imperfect Sensor
移動ロボットの不完全なセンサと限られた時間予算のもとで、目標検出確率を最大化する探索経路を計算する高速アルゴリズムを提案し、性能保証と計算複雑性の結果を示した。
著者: Nilanjan Chakraborty, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, Linh Nguyen, Michael Perk
分類: cs.RO, cs.CG
原文アブストラクト
Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e.g., based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to observe their performance.
