2016/12/10 by Pratap Tokekar, Tokekar, Pratap, Ashish Kumar Budhiraja +3
Computer Science · #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO) #cs.RO
paper · pdf · doi:10.48550/arxiv.1612.03246
12 pages, 10 figures, submitted to IEEE Transactions on Robotics(TRO) and preliminary version of the paper was published in Intelligent Robots and Systems (IROS), 2015
arxiv created 2016/12/10 · openalex publication_date 2016/12/10 · arxiv updated 2016/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of planning paths for a team of robots for visually monitoring an environment. Our work is motivated by surveillance and persistent monitoring applications. We are given a set of target points in a polygonal environment that must be monitored using robots with cameras. The goal is to compute paths for all robots such that every target is visible from at least one path. In its general form, this problem is NP-hard as it generalizes the Art Gallery Problem and the Watchman Route Problem. We study two versions: (i) a geometric version in street polygons for which we give a polynomial time 4--approximation algorithm; and (ii) a general version for which we present a practical solution that finds the optimal solution in possibly exponential time. In addition to theoretical proofs, we also present results from simulation studies.