Optimal Perimeter Guarding with Heterogeneous Robot Teams: Complexity Analysis and Effective Algorithms

Si Wei Feng, Jingjin Yu

Research output: Contribution to journalArticle


We perform structural and algorithmic studies of significantly generalized versions of the optimal perimeter guarding (OPG) problem. As compared with the original OPG where robots are uniform, in this paper, many mobile robots with heterogeneous sensing capabilities are to be deployed to optimally guard a set of one-dimensional segments. Two complimentary formulations are investigated where one limits the number of available robots (OPG{}_{LR}) and the other seeks to minimize the total deployment cost ({\rm OPG}_{MC}). In contrast to the original OPG which admits low-polynomial time solutions, both OPG{}_{LR} and {\rm OPG}_{MC} are computationally intractable with OPG{}_{LR} being strongly NP-hard. Nevertheless, we develop fairly scalable pseudo-polynomial time algorithms for practical, fixed-parameter subcase of OPG{}_{LR}; we also develop pseudo-polynomial time algorithm for general {\rm OPG}_{MC} and polynomial time algorithm for the fixed-parameter {\rm OPG}_{MC} case. The applicability and effectiveness of selected algorithms are demonstrated through extensive numerical experiments.

Original languageEnglish (US)
Article number8938724
Pages (from-to)430-437
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number2
StatePublished - Apr 2020

All Science Journal Classification (ASJC) codes

  • Mechanical Engineering
  • Control and Optimization
  • Artificial Intelligence
  • Human-Computer Interaction
  • Control and Systems Engineering
  • Computer Vision and Pattern Recognition
  • Biomedical Engineering
  • Computer Science Applications


  • Multi-robot systems
  • optimization and optimal control
  • surveillance systems

Fingerprint Dive into the research topics of 'Optimal Perimeter Guarding with Heterogeneous Robot Teams: Complexity Analysis and Effective Algorithms'. Together they form a unique fingerprint.

  • Cite this