English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  On Cooperative Patrolling: Optimal Trajectories, Complexity Analysis, and Approximation Algorithms

Pasqualetti, F., Franchi, A., & Bullo, F. (2012). On Cooperative Patrolling: Optimal Trajectories, Complexity Analysis, and Approximation Algorithms. IEEE Transaction on Robotics, 28(3), 592-606. doi:10.1109/TRO.2011.2179580.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-B720-8 Version Permalink: http://hdl.handle.net/21.11116/0000-0001-8822-F
Genre: Journal Article

Files

show Files

Locators

show
hide
Description:
-

Creators

show
hide
 Creators:
Pasqualetti, F, Author
Franchi, A1, 2, Author              
Bullo, F, Author
Affiliations:
1Department Human Perception, Cognition and Action, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497797              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: The subject of this paper is the patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory and propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm.

Details

show
hide
Language(s):
 Dates: 2012-06
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: DOI: 10.1109/TRO.2011.2179580
BibTex Citekey: PasqualettiFB2011
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: IEEE Transaction on Robotics
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 28 (3) Sequence Number: - Start / End Page: 592 - 606 Identifier: -