A COMPLETE ALGORITHM FOR SEARCHLIGHT SCHEDULING

DOI Web Site 被引用文献1件
  • KARL J. OBERMEYER
    Center for Control, Dynamical Systems, and Computation, University of California at Santa Barbara, Santa Barbara, CA 93106, USA
  • ANURAG GANGULI
    Center for Control, Dynamical Systems, and Computation, University of California at Santa Barbara, Santa Barbara, CA 93106, USA
  • FRANCESCO BULLO
    Center for Control, Dynamical Systems, and Computation, University of California at Santa Barbara, Santa Barbara, CA 93106, USA

この論文をさがす

説明

<jats:p> This article develops an algorithm for a group of guards statically positioned in a non-convex polygonal environment with holes. Each guard possesses a single searchlight, a ray sensor which can rotate about the guard's position but cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which move arbitrarily fast. The objective of the proposed algorithm is to compute a schedule to rotate a set of searchlights in such a way that any target in an environment will necessarily be detected in finite time. This is known as the Searchlight Scheduling Problem and was described originally in 1990 by Sugihara et al. We take an approach known as exact cell decomposition in the motion planning literature. The algorithm operates by decomposing the searchlights' joint configuration space and the environment, and then by constructing a so-called information graph. Searching the information graph for a path between desired states yields a search schedule. We also introduce a new problem called the ϕ-Searchlight Scheduling Problem in which ϕ-searchlights sense not just along a ray, but over a finite field of view. We show that our results for searchlight scheduling can be directly extended for ϕ-searchlight scheduling. Proofs of completeness, complexity bounds, and computed examples are presented. </jats:p>

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ