Advances in Multi-agent Polygonal Area Coverage

Candidate: Alireza Davoodi
Type: Master of Science (MSc), School of Interactive Arts and Technology
Date: April 12, 2011
Senior Supervisor: Dr. Philippe Pasquier
Thesis: Download Thesis Document

Abstract

The Multi-agent Polygonal Area Coverage refers to the problem in which a team of an arbitrary number of agents with limited panoramic visual sensors is collectively visiting a given polygonal area. The goal is to build efficient paths for the agents which jointly ensure that every single point in the area is seen by at least one of the agents during the coverage mission. Search and rescue operations, floor cleaning, intruder detection, and environment monitoring are examples of practical applications for the solution algorithms.

In this research, the proposed method starts by locating a set of guide points, known as Guards, on the 2D map of the target area. One graph representation of a polygonal area Visibility Graph or Constrained Delaunay Triangulation, is built on the union of the set of guards and the end-points of the eventual polygonal obstacles. Due to the unnecessary density of both the representations, a graph reduction algorithm is applied to remove as many edges as possible from the graph while preserving connectivity. Then, four segmentation approaches including the Informed Tree Partition, the Uninformed Tree Partition, the k-Means Partition, and the Cyclic Partition are applied to distribute the resulting reduced graph amongst the agents. While the three former decomposition methods result in a forest of trees and consequently, need an additional method for constructing tours, the latter directly builds a tour on the vertices of the reduced graphs. In order to construct tours of the resultant trees, a so-called Constrained Spanning Tour algorithm is proposed in addition to the existing Double-Minimum Spanning Tree method. Finally, the tours are distributed amongst the agents.

All the approaches are complete, meaning that they guarantee every point of interest in the area is visited at least once during the coverage operation. Extensive empirical studeis were conducted to compare and evaluate the coverage algorithms and the different environment representations under several evaluation criteria. A simulator as well as a 2D map generator have been developed and used to evaluate the proposed coverage approaches as well as the environment representations based on the frequency of visits to points of interest, the total amount of resources used during the coverage operatoin and the balance in workload distribution among the agents. The experiment results show that none of the proposed approaches dominates the others under all the criteria. Therefore, more nuanced conclusions and guidelines are drawn from the results.