creators_name: Stefanovich, Nicolas
creators_name: Farinelli, Alessandro
creators_name: Rogers, Alex
creators_name: Jennings, Nicholas R
type: article
datestamp: 2011-11-14 10:40:10
lastmod: 2012-03-22 09:37:19
metadata_visibility: show
title: Resource-Aware Junction Trees for Efficient Multi-Agent Coordination 
ispublished: pub
subjects: ABC
subjects: at
full_text_status: public
abstract: In this paper we address efficient decentralised coordination of cooperative multi-agent systems by taking into account the actual computation and communication capabilities of the agents. We consider coordination problems that can be framed as Distributed Constraint Optimisation Problems, and as such, are suitable to be deployed on large scale multi-agent systems such as sensor networks or multiple unmanned aerial vehicles. Specifically, we focus on techniques that exploit structural independence among agents’ actions to provide optimal solutions to the coordination problem, and, in particular, we use the Generalized Distributive Law (GDL) algorithm. In this settings, we propose a novel resource aware heuristic to build junction trees and to schedule GDL computations across the agents. Our goal is to minimise the total running time of the coordination process, rather than the theoretical complexity of the computation, by explicitly considering the computation and communication capabilities of agents. We evaluate our proposed approach against DPOP, RDPI and a centralized solver on a number of benchmark coordination problems, and show that our approach is able to provide optimal solutions for DCOPs faster than previous approaches. Specifically, in the settings considered, when resources are scarce our approach is up to three times faster than DPOP (which proved to be the best among the competitors in our
settings).
date: 2011-05
date_type: published
publication: The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)
pagerange: 363-370
refereed: TRUE
citation:   Stefanovich, Nicolas and Farinelli, Alessandro and Rogers, Alex and Jennings, Nicholas R  (2011) Resource-Aware Junction Trees for Efficient Multi-Agent Coordination.  The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011).  pp. 363-370.      
document_url: http://www.orchid.ac.uk/eprints/18/1/main_a11.pdf