de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

On optimal cooperative patrolling

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons83915

Franchi,  A
Department Human Perception, Cognition and Action, Max Planck Institute for Biological Cybernetics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Pasqualetti, F., Franchi, A., & Bullo, F. (2010). On optimal cooperative patrolling. In 49th IEEE Conference on Decision and Control (CDC 2010) (pp. 7153-7158). Piscataway, NJ, USA: IEEE.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0013-BD36-4
Zusammenfassung
This work considers the problem of designing optimal multi-agent trajectories to patrol an environment. In both civil and military applications it is of increasing importance to instruct a team of autonomous agents to accomplish repetitive tasks, such as the monitoring of strategic regions or the detection of life threatening situations. As performance criterion for optimal patrolling we minimize the worst-case time gap between any two visits of an environment location. We characterize the computational complexity of the trajectory design (patrolling) problem with respect to the environment topology and to the number of robots to be employed in the surveillance task. Even though the patrolling problem is generally NP-hard, we identify particular cases that are solvable efficiently, and we describe optimal patrolling trajectories. Finally, we present a heuristic with performance guarantee, and an 8-approximation algorithm to solve the NP-hard patrolling problem.