An Efficient Algorithm For Solving Dynamic Complex DCOP Problems

File Size Format
59445_1.pdf 739Kb Adobe PDF View
Title An Efficient Algorithm For Solving Dynamic Complex DCOP Problems
Author Khanna, Sankalp; Sattar, Abdul; Hansen, David; Stantic, Bela
Publication Title Proceedings. 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology
Editor Ricardo Baeza-Yates, Jerome Lang, Sushmita Mitra, Simon Parsons, Gabriella Pasi
Year Published 2009
Place of publication Los Alamitos, CA
Publisher IEEE Computer Society
Abstract Multi Agent Systems and the Distributed Constraint Optimization Problem (DCOP) formalism offer several asynchronous and optimal algorithms for solving naturally distributed optimization problems efficiently. There has been good application of this technology in addressing real world problems in areas like Sensor Networks and Meeting Scheduling. Most of these algorithms however exploit static tree structures and are thus not well suited to modeling and solving problems in rapidly changing domains. Also, while in theory most DCOP algorithms can be extended to handle complex local sub-problems, we argue that this generally results in making their performance sub-optimal, and thus their application less suitable. In this paper we present new measures that emphasize the interconnectedness between each agent's local and interagent sub-problems and use these measures to guide dynamic agent ordering during distributed constraint reasoning. The resulting algorithm, DCDCOP, offers a robust, flexible, and efficient mechanism for modeling and solving dynamic complex problems. Experimental evaluation of the algorithm shows that DCDCOP significantly outperforms ADOPT, the gold standard in search-based DCOP algorithms.
Peer Reviewed Yes
Published Yes
Publisher URI http://portal.acm.org/citation.cfm?id=1632191.1632539
Alternative URI http://dx.doi.org/10.1109/WI-IAT.2009.175
Copyright Statement Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
ISBN 978-0-7695-3801-3
Conference name 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT 2009)
Location Milano, Italy
Date From 2009-09-15
Date To 2009-09-18
URI http://hdl.handle.net/10072/29999
Date Accessioned 2010-01-22
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Information Systems Development Methodologies
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice