Gal A. Kaminka's Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Multi-Robot Area Patrol under Frequency Constraints

Yehuda Elmaliach, Noa Agmon, and Gal A. Kaminka. Multi-Robot Area Patrol under Frequency Constraints. Annals of Math and Artificial Intelligence, 57(3--4):293–320, 2010.

Download

(unavailable)

Abstract

Patrolling requires an area to be visited repeatedly by the robot(s) in orderto monitor its current state. In general, the challenge of patrolling involves generating patrol paths for a team of mobile robots inside a designated target work area, such thatevery point in the area is repeatedly covered. However, previous work has oftenignored the frequency in which points in the area are visited, and focused insteadon finding paths that allow for repeated coverage. In this paper, we first present formal frequency optimization criteria used for evaluation of patrol algorithms. Then, wepresent a patrol algorithm that guarantees maximal uniformfrequency, i.e., each point in the target area is covered at thesame optimal frequency. This solution, called Spanning-Tree Patrolling (STP), is based on finding a circular path that visits all points in the area, while taking into accountterrain directionality and velocity constraints. Robots arepositioned uniformly along this path in minimal time, using a second algorithm.Moreover, the solution is guaranteed to be robust in the sense thatuniform frequency of the patrol is achieved as long as at least onerobot works properly. We then present a set of algorithms for handling events along the patrol path. The algorithms differ in the way they handle the event, as a function of the time constraints for handling them. The advantage of these algorithms, is that they handle the events as well as maintaining the patrol path and minimizing the disturbance to the system as much as the time constraint on the event permits.

BibTeX

@Article{amai10yehuda,
author = {Yehuda Elmaliach and Noa Agmon and Gal A. Kaminka},
title = {Multi-Robot Area Patrol under Frequency Constraints},
journal = AMAI,
year = {2010},
OPTkey = {},
volume = {57},
number = {3--4},
pages = {293--320},
OPTmonth = {},
note = {},
abstract = {Patrolling requires an area to be visited repeatedly by the robot(s) in order
to monitor its current state. In general, the challenge of patrolling involves generating patrol paths for a team of mobile robots inside a designated target work area, such that
every point in the area is repeatedly covered. However, previous work has often
ignored the frequency in which points in the area are visited, and focused instead
on finding paths that allow for repeated coverage.  In this paper, we first present 
formal frequency optimization criteria used for evaluation of patrol algorithms. Then, we
present a patrol algorithm that guarantees maximal uniform
frequency, i.e., each point in the target area is covered at the
same optimal frequency. This solution, called Spanning-Tree Patrolling (STP), is based on finding a circular path that visits all points in the area, while taking into account
terrain directionality and velocity constraints. Robots are
positioned uniformly along this path in minimal time, using a second algorithm.
Moreover, the solution is guaranteed to be robust in the sense that
uniform frequency of the patrol is achieved as long as at least one
robot works properly. We then present a set of algorithms for handling events along the patrol path. The algorithms differ in the way they handle the event, as a function of the time constraints for handling them. The advantage of these algorithms, is that they handle the events as well as maintaining the patrol path and minimizing the disturbance to the system as much as the time constraint on the event permits.},
OPTannote = {}
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun Oct 29, 2017 21:31:22