On optimal cooperative patrolling

Pasqualetti, F; Franchi, A; Bullo, F

doi:10.1109/CDC.2010.5717873

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

On optimal cooperative patrolling

MPS-Authors

/persons/resource/persons83915

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

External Resource

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5717873
(出版社版)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-0013-BD36-4

要旨

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.