GEOMETRIC TASK DECOMPOSITION IN A MULTI-AGENT ENVIRONMENT

Authors: Kamali, Kaivan¹; Ventura, Dan²; Garga, Amulya³; Kumara, Soundar⁴

Source: Applied Artificial Intelligence, Volume 20, Number 5, May-June 2006 , pp. 437-456(20)

Buy & download fulltext article:

Price: $56.94 plus tax (Refund Policy)

Abstract:

Task decomposition in a multi-agent environment is often performed online. This paper proposes a method for sub-task allocation that can be performed before the agents are deployed, reducing the need for communication among agents during their mission. The proposed method uses a Voronoi diagram to partition the task-space among team members and includes two phases: static and dynamic. Static decomposition (performed in simulation before the start of the mission) repeatedly partitions the task-space by generating random diagrams and measuring the efficacy of the corresponding sub-task allocation. If necessary, dynamic decomposition (performed in simulation after the start of a mission) modifies the result of a static decomposition (i.e., in case of resource limitations for some agents). Empirical results are reported for the problem of surveillance of an arbitrary region by a team of agents.

Document Type: Research article

DOI: http://dx.doi.org/10.1080/08839510500313737

Affiliations: 1: Department of Computer Science & Engineering, The Pennsylvania State University, University Park, Pennsylvania, USA 2: Computer Science Department, Brigham Young University, Provo, Utah, USA 3: The Applied Research Laboratory, The Pennsylvania State University, University Park, Pennsylvania, USA 4: Department of Industrial & Manufacturing Engineering, The Pennsylvania State University, University Park, Pennsylvania, USA

Publication date: 2006-05-01

More about this publication?