An approximation algorithm for the least overlapping p-frame problem with non-partial coverage for networked robotic cameras

Yiliang Xu, Dezhen Song, Jingang Yi, A. Frank Van Der Stappen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

We report our algorithmic development of the p-frame problem that addresses the need of coordinating a set of p networked robotic pan-tilt-zoom cameras for n, (n > p), competing polygonal requests. We assume that the p frames have almost no overlap on the coverage between frames and a request is satisfied only if it is fully covered. We then propose a Resolution Ratio with Non-Partial Coverage (RRNPC) metric to quantify the satisfaction level for a given request with respect to a set of p candidate frames. We propose a lattice-based approximation algorithm to search for the solution that maximizes the overall satisfaction. The algorithm builds on an induction-like approach that finds the relationship between the solution to the (p - 1)-frame problem and the solution to the p-frame problem. For a given approximation bound ∈, the algorithm runs in O(n/∈3+p2/∈6) time. We have implemented the algorithm and experimental results are consistent with our complexity analysis.

Original languageEnglish (US)
Title of host publication2008 IEEE International Conference on Robotics and Automation, ICRA 2008
Pages1011-1016
Number of pages6
DOIs
StatePublished - 2008
Externally publishedYes
Event2008 IEEE International Conference on Robotics and Automation, ICRA 2008 - Pasadena, CA, United States
Duration: May 19 2008May 23 2008

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other2008 IEEE International Conference on Robotics and Automation, ICRA 2008
Country/TerritoryUnited States
CityPasadena, CA
Period5/19/085/23/08

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'An approximation algorithm for the least overlapping p-frame problem with non-partial coverage for networked robotic cameras'. Together they form a unique fingerprint.

Cite this