• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Yehuda Elmaliach. Multi-Robot Frequency-Based Patrolling . Ph.D.
Thesis, Bar Ilan University, 2009.
Mobile robots can save human lives and financial costs by replacing humans inmundane, or dangerous tasks. Patrolling is one such task: It is often mundane, is inherently repetitive, and may involve risk to human patrollers. One important type of patrollingis frequency-based patrolling, which involves visiting all points within a target work area at a fixed frequency (as much as possible).Our focus in this dissertation is on frequency-based patrolling by teams of multiple, cooperating, robots.First, it formally defines the frequency-based patrolling problem, and distinguishes three different possible optimization criteria by which to evaluate solutions. Second, it presents solutions that are provably robust to robot death, guaranteeing that patrolling will continue as long as at least one robot is functioning. It also addresses event handling in patrolling, exploring algorithms that optimally select which robot shouldbreak the patrolling motion to respond to an event at a given location, and how todistribute the event handling load among different robots.The dissertation makes a clear distinction between patrolling areas (enclosed by polygons), and patrolling polylines. In particular, the dissertation shows that patrolling an open polyline (e.g., a two-ended fence) is inherently in conflict with the goal of achieving uniform point visit frequency. Different algorithms are therefore presented for patrolling areas and for patrolling polylines.In Part I of this thesis, we address optimal multi-robot patrolling algorithms for areas enclosed by polygons. We begin by presenting 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.We then present a set of algorithms for handling events along the patrol path, which requirethe robots to stop at the event location to carry out some event-handling activity. Handling events is always in conflict with optimal frequency-based patrolling, as it always requires robots to stop, rather than continue their patrolling motions. The advantage of the algorithms we develop is that they handle the events while maintaining the patrol path and minimizing the disturbance to the system as much as the time constraint on the event permits.In Part II, we discuss patrolling polylines. A polyline (e.g., a two-ended fence) inherently poses challenges for existing algorithms, since no circular paths exists, and thus some points necessarily are visitedmore often than others. In this part of the dissertation, we first show thatin general, a coordinated approach to multi-robot patrolling, where robots are equidistant from each other in travel time, outperforms uncoordinated methods. We then present FOP (Frequency-based Overlapping Patrol), a general coordinated patrolling algorithm, in which robots move backand forth along the polyline, in an synchronized manner, such thatthey are assigned overlapping areas of movement. Weanalyze the performance of this coordinated method in depth. We extend the analysis of the FOP algorithm to account for more realistic settings, e.g., turn durations, and errors in the robots' velocities. These extensions change the predictions of the optimal overlap settingsto be used in applications, based on the measureable physical performance of the robots in practice. We use thedeveloped models to predict the independently-programmed patrolling movementsof physical robots, in extensive experiments conducted in our laboratory. We show that the extended models accurately predicts the behavior of the robots accurately, supporting the compatibilityof the analytical model with actual robot performance.Finally, we allow each patrolling unit to include multiple robots that move in formation. Unfortunately, known algorithms for formation maintenance typically utilize the robots' sensors to carry out the formation, thus prohibiting their use for carryingout the surveillance task.We thus present a first step towards a novel formation-maintenance technique which multiplexes the use of sensors and communications,and allows the robots to utilize their sensors for monitoring their surroundings, whilemaintaining the formation.Throughout the dissertation utilize experiments with real and simulated robots to evaluate the various techniques and demonstrate their effectiveness. Where possible, we analytically provide hard guarantees on the optimality and capabilities of the different models.
@PhdThesis{yehudaelmaley-phd,
author = {Yehuda Elmaliach},
abstract = {Mobile robots can save human lives and financial costs by replacing humans in
mundane, or dangerous tasks. Patrolling is one such task: It is often mundane, is inherently repetitive, and may involve risk to human patrollers. One important type of patrolling
is \emph{frequency-based patrolling}, which involves visiting all points within a target work area at a fixed frequency (as much as possible).
Our focus in this dissertation is on frequency-based patrolling by teams of multiple, cooperating, robots.
First, it formally defines the frequency-based patrolling problem, and distinguishes three different possible optimization criteria by which to evaluate solutions. Second, it presents solutions that are provably robust to robot death, guaranteeing that patrolling will continue as long as at least one robot is functioning. It also addresses event handling in patrolling, exploring algorithms that optimally select which robot should
break the patrolling motion to respond to an event at a given location, and how to
distribute the event handling load among different robots.
The dissertation makes a clear distinction between patrolling areas (enclosed by polygons), and patrolling polylines. In particular, the dissertation shows that patrolling an open polyline (e.g., a two-ended fence) is inherently in conflict with the goal of achieving uniform point visit frequency. Different algorithms are therefore presented for patrolling areas and for patrolling polylines.
In Part I of this thesis, we address optimal multi-robot patrolling algorithms for areas enclosed by polygons. We begin by presenting 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.
We then present a set of algorithms for handling events along the patrol path, which require
the robots to stop at the event location to carry out some event-handling activity. Handling events is always in conflict with optimal frequency-based patrolling, as it always requires robots to stop, rather than continue their patrolling motions. The advantage of the algorithms we develop is that they handle the events while maintaining the patrol path and minimizing the disturbance to the system as much as the time constraint on the event permits.
In Part II, we discuss patrolling polylines. A polyline (e.g., a two-ended fence) inherently poses challenges for existing algorithms, since no circular paths exists, and thus some points necessarily are visited
more often than others. In this part of the dissertation, we first show that
in general, a coordinated approach to multi-robot patrolling, where robots are equidistant from each other in travel time, outperforms uncoordinated methods. We then present FOP (Frequency-based Overlapping Patrol), a general coordinated patrolling algorithm, in which robots move back
and forth along the polyline, in an synchronized manner, such that
they are assigned overlapping areas of movement. We
analyze the performance of this coordinated method in depth. We extend the analysis of the FOP algorithm to account for more realistic settings, e.g., turn durations, and errors in the robots' velocities. These extensions change the predictions of the optimal overlap settings
to be used in applications, based on the measureable physical performance of the robots in practice. We use the
developed models to predict the independently-programmed patrolling movements
of physical robots, in extensive experiments conducted in our laboratory. We show that the extended models accurately predicts the behavior of the robots accurately, supporting the compatibility
of the analytical model with actual robot performance.
Finally, we allow each patrolling unit to include multiple robots that move in formation. Unfortunately, known algorithms for formation maintenance typically utilize the robots' sensors to carry out the formation, thus prohibiting their use for carrying
out the surveillance task.
We thus present a first step towards a novel formation-maintenance technique which multiplexes the use of sensors and communications,
and allows the robots to utilize their sensors for monitoring their surroundings, while
maintaining the formation.
Throughout the dissertation utilize experiments with real and simulated robots to evaluate the various techniques and demonstrate their effectiveness. Where possible, we analytically provide hard guarantees on the optimality and capabilities of the different models.
},
school = {{B}ar {I}lan {U}niversity},
year = {2009},
OPTkey = {},
OPTtype = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
title = { Multi-Robot Frequency-Based Patrolling },
wwwnote = {},
OPTannote = {}
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51