Visibility-Based Target-Tracking Game: Bounds and Tracking Strategies
Authors:
- 13 June 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 2 (4) , 1917-1924
Abstract
The art gallery problem or museum problem is a well-known visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. This letter deals with a variant of the art gallery problem in which guards are deployed to track a mobile intruder. We consider a team of free guards equipped with omnidirectional cameras deployed to track a bounded speed intruder inside a simply connected polygonal environment. We present a partitioning technique for any simply connected polygon using its diagonals such that each partition is at most a nonagon. Next, we propose an event-triggered strategy for a single guard to track an intruder around a reflex vertex. Based on the proposed strategy, we formulate the problem of finding the minimum speed of the guard and its corresponding trajectory inside any partition as a convex-optimization problem. The solution to the convex-optimization problem provides an upper bound on the speed of the mobile guard required for persistent tracking of the mobile intruder. Furthermore, we show that the number of guards deployed by the proposed technique belongs to $\mathcal {O}(\frac{2n}{7})$ and $\Omega (\frac{n}{6})$ , which is strictly less than $\lfloor {\frac{n}{3}} \rfloor$ (sufficient and sometimes necessary number of guards required for coverage). Finally, we extend the analysis to orthogonal polygons, and show that the upper bound on the number of guards deployed for tracking is strictly less than $\lfloor {\frac{n}{4}} \rfloor$ which is sufficient and sometimes necessary for the coverage problem.
Keywords
This publication has 22 references indexed in Scilit:
- Camera Networks: The Acquisition and Analysis of Videos over Wide AreasSynthesis Lectures on Computer Vision, 2012
- A cell decomposition approach to visibility-based pursuit evasion among obstaclesThe International Journal of Robotics Research, 2011
- GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERASInternational Journal of Computational Geometry & Applications, 2011
- Multi‐agent deployment for visibility coverage in polygonal environments with holesInternational Journal of Robust and Nonlinear Control, 2011
- A COMPLETE ALGORITHM FOR SEARCHLIGHT SCHEDULINGInternational Journal of Computational Geometry & Applications, 2011
- Visibility-based Pursuit—Evasion with Bounded SpeedThe International Journal of Robotics Research, 2008
- Surveillance Strategies for a Pursuer with Finite Sensor RangeThe International Journal of Robotics Research, 2007
- Finding the Shortest Watchman Route in a Simple PolygonDiscrete & Computational Geometry, 1999
- Galleries need fewer mobile guards: A variation on Chv tal's theoremGeometriae Dedicata, 1983
- A combinatorial theorem in plane geometryJournal of Combinatorial Theory, Series B, 1975