GEOMETRIC TASK DECOMPOSITION IN A MULTI-AGENT ENVIRONMENT

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 p...

Full description

Saved in:
Bibliographic Details
Published in:Applied artificial intelligence 2006-06, Vol.20 (5), p.437-456
Main Authors: Kamali, Kaivan, Ventura, Dan, Garga, Amulya, Kumara, Soundar R. T.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. This material is based on work carried out at the Applied Research Laboratory at The Pennsylvania State University under the ONR grant N000149615026.
ISSN:0883-9514
1087-6545
DOI:10.1080/08839510500313737