Gal A. Kaminka's Publications

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

Multi-Robot Patrolling and Other Multi-Robot Cooperative Tasks: An Algorithmic Approach

Noa Agmon. Multi-Robot Patrolling and Other Multi-Robot Cooperative Tasks: An Algorithmic Approach. Ph.D. Thesis, Bar Ilan University, 2009.

Download

[PDF]1.4MB  

Abstract

The subject of cooperative multi robot systems has been thoroughly investigatedover the past decade. These systems have immediate applicability in a wide variety of tasks, such as militaryoperations and space missions. Building algorithms for multi-robot systems is a complex challenge, for which solutions and methods are brought from many different disciplines. There is significant interest in multi-robot systems also in the discipline of theoretical computer science, mainly by using distributed systems analysis. However, researchers who have worked on multi-robot systems from a distributed algorithms perspective have tended to make unrealistic assumptions about the robots' capabilities, resulting in algorithms impractical for realistic systems. In our work, we were motivated by methods from the theoretical computer science discipline, yet we incorporated realistic assumptions on the robots' capabilities.In the first and the main part of the work we consider the task of multi-robot patrol in adversarial environments. In this task, a team of robots is required to continuously visit some target area in order to detect an adversary trying to pass through the patrol path undetected. The challenge is to maximize the robots' chances of detecting the adversary. We model the robots and the environment, and find a family of optimal patrol algorithms for the robots. The algorithms address different adversarial models, characterized by the knowledge obtained by the adversary on the patrolling robots. Furthermore, we consider various robotic models, based on possible movement and sensing models of the robots, and different environmental models---patrolling around a perimeter (closed polygon) and fence (open polyline).In the second part of the work, we discuss two additional canonical tasks in multi-robot systems. First, we address the problem of task reallocation in multi-robot formation, in which a subgroup of the robots should be extracted from the formation in order to perform some new task. We therefore propose a new model of the system that is based on the interaction between the team members, which helps in finding an efficient solution to the problem. Second, we consider the problem of multi-robot coverage, in which a team of robots is required to jointly visit a target area once. We propose a heuristic algorithm that is shown to significantly improve the time to complete the coverage task.

Additional Information

BibTeX

@PhdThesis{noagmon-phd, 
author = {Noa Agmon}, 
title = {Multi-Robot Patrolling and Other Multi-Robot Cooperative Tasks: An Algorithmic Approach}, 
school = {{B}ar {I}lan {U}niversity}, 
year = {2009}, 
OPTkey = {}, 
OPTtype = {}, 
OPTaddress = {}, 
OPTmonth = {}, 
 OPTnote = {}, 
  abstract = { The subject of cooperative multi robot systems has been thoroughly investigated
over the past decade. These systems have immediate applicability in a wide variety of tasks, such as military
operations and space missions. Building algorithms for multi-robot systems is a complex challenge, for which solutions and methods are brought from many different disciplines. There is significant interest in multi-robot systems also in the discipline of theoretical computer science, mainly by using distributed systems analysis. However, researchers who have worked on multi-robot systems from a distributed algorithms perspective have tended to make unrealistic assumptions about the robots' capabilities, resulting in algorithms impractical for realistic systems. In our work, we were motivated by methods from the theoretical computer science discipline, yet we incorporated realistic assumptions on the robots' capabilities.
In the first and the main part of the work we consider the task of multi-robot patrol in adversarial environments. In this task, a team of robots is required to continuously visit some target area in order to detect an adversary trying to pass through the patrol path undetected. The challenge is to maximize the robots' chances of detecting the adversary. We model the robots and the environment, and find a family of optimal patrol algorithms for the robots. The algorithms address different adversarial models, characterized by the knowledge obtained by the adversary on the patrolling robots.  Furthermore, we consider various robotic models, based on possible movement and sensing models of the robots, and different environmental models---patrolling around a perimeter (closed polygon) and fence (open polyline).
In the second part of the work, we discuss two additional canonical tasks in multi-robot systems.  First, we address the problem of task reallocation in multi-robot formation, in which a subgroup of the robots should be extracted from the formation in order to perform some new task. We therefore propose a new model of the system that is based on the interaction between the team members, which helps in finding an efficient solution to the problem. Second, we consider the problem of multi-robot coverage, in which a team of robots is required to jointly visit a target area {\em once}. We propose a heuristic algorithm that is shown to significantly improve the time to complete the coverage task. }, 
  wwwnote = {}, 
OPTannote = {} 
} 

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