A CLASS OF ALGORITHMS FOR DISTRIBUTED CONSTRAINT OPTIMIZATION Frontiers in Artificial Intelligence and Applications Volume 194 Published in the subseries Dissertations in Artificial Intelligence Under the Editorship of the ECCAI Dissertation Board Recently published in this series Vol. 193. B. Apolloni, S. Bassis and M. Marinaro (Eds.), New Directions in Neural Networks – 18th Italian Workshop on Neural Networks: WIRN 2008 Vol. 192. M. Van Otterlo (Ed.), Uncertainty in First-Order and Relational Domains Vol. 191. J. Piskorski, B. Watson and A. Yli-Jyrä (Eds.), Finite-State Methods and Natural Language Processing – Post-proceedings of the 7th International Workshop FSMNLP 2008 Vol. 190. Y. Kiyoki et al. (Eds.), Information Modelling and Knowledge Bases XX Vol. 189. E. Francesconi et al. (Eds.), Legal Knowledge and Information Systems – JURIX 2008: The Twenty-First Annual Conference Vol. 188. J. Breuker et al. (Eds.), Law, Ontologies and the Semantic Web – Channelling the Legal Information Flood Vol. 187. H.-M. Haav and A. Kalja (Eds.), Databases and Information Systems V – Selected Papers from the Eighth International Baltic Conference, DB&IS 2008 Vol. 186. G. Lambert-Torres et al. (Eds.), Advances in Technological Applications of Logical and Intelligent Systems – Selected Papers from the Sixth Congress on Logic Applied to Technology Vol. 185. A. Biere et al. (Eds.), Handbook of Satisfiability Vol. 184. T. Alsinet, J. Puyol-Gruart and C. Torras (Eds.), Artificial Intelligence Research and Development – Proceedings of the 11th International Conference of the Catalan Association for Artificial Intelligence Vol. 183. C. Eschenbach and M. Grüninger (Eds.), Formal Ontology in Information Systems – Proceedings of the Fifth International Conference (FOIS 2008) Vol. 182. H. Fujita and I. Zualkernan (Eds.), New Trends in Software Methodologies, Tools and Techniques – Proceedings of the seventh SoMeT_08 Vol. 181. A. Zgrzywa, K. Choroś and A. Siemiński (Eds.), New Trends in Multimedia and Network Information Systems ISSN 0922-6389 A Class of Algorithms for Distributed Constraint Optimization Adrian Petcu École Polytechnique Fédérale de Lausanne (EPFL) Amsterdam • Berlin • Tokyo • Washington, DC © 2009 The author and IOS Press. All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without prior written permission from the publisher. ISBN 978-1-58603-989-9 Library of Congress Control Number: 2009922682 doi:10.3233/978-1-58603-989-9-i Publisher IOS Press BV Nieuwe Hemweg 6B 1013 BG Amsterdam Netherlands fax: +31 20 687 0019 e-mail: [email protected] Distributor in the UK and Ireland Distributor in the USA and Canada Gazelle Books Services Ltd. IOS Press, Inc. White Cross Mills 4502 Rachael Manor Drive Hightown Fairfax, VA 22032 Lancaster LA1 4XS USA United Kingdom fax: +1 703 323 3668 fax: +44 1524 63232 e-mail: [email protected] e-mail: [email protected] LEGAL NOTICE The publisher is not responsible for the use which might be made of the following information. PRINTED IN THE NETHERLANDS Tomyfamily v vi Abstract MultiAgentSystems(MAS)haverecentlyattractedalotofinterestbecauseoftheirabilitytomodel manyreallifescenarioswhereinformationandcontrolaredistributedamongasetofdifferentagents. Practical applications include planning, scheduling, distributed control, resource allocation, etc. A majorchallengeinsuchsystemsiscoordinatingagentdecisions,suchthatagloballyoptimaloutcome is achieved. Distributed Constraint Optimization Problems (DCOP) are a framework that recently emergedasoneofthemostsuccessfulapproachestocoordinationinMAS. ThisthesisaddressesthreemajorissuesthatariseinDCOP:efficientoptimizationalgorithms,dy- namicandopenenvironments,andmanipulationsfromself-interestedusers.Wemakesignificantcon- tributionsinallthesedirections:Efficiency-wise,weintroduceaseriesofDCOPalgorithms,whichare basedondynamicprogramming,andlargelyoutperformpreviousDCOPalgorithms.Thebasisofthis classofalgorithmsisDPOP,adistributedalgorithmthatrequiresonlyalinearnumberofmessages, thusincurringlownetworkingoverhead. Fordynamicenvironmentsweintroduceself-stabilizingal- gorithmsthatcandealwithchangesandcontinuouslyupdatetheirsolutions. Forselfinterestedusers, weproposetheM-DPOPalgorithm,whichisthefirstDCOPalgorithmthatmakeshonestbehaviour anex-postNashequilibriumbyimplementingtheVCGmechanismdistributedly. Wealsodiscussthe issueofbudgetbalance,andintroducetwoalgorithmsthatallowforredistributing(someof)theVCG paymentsbacktotheagents,thusavoidingthewelfarelosscausedbywastingtheVCGtaxes. Keywords: artificialintelligence, constraintoptimization, dynamicsystems, multiagentsystems, self-interest viii Re´sume´ Lessyste`mesmultiagent(MAS)ontre´cemmentattire´beaucoupd’inte´reˆtenraisondeleurcapacite´ demode´liserbeaucoupdesce´nariosre´elsou` l’informationetlecontroˆlesontdistribue´sparmiunen- semble de diffe´rents agents. Les applications pratiques incluent la planification, l’ordonnancement, lessyste`mesdecontroˆledistribue´s,ouencorel’attributionderessources. Unde´fiimportantdansde telssyste`mesestlacoordinationdesde´cisionsdesagents,afinquedesre´sultatsglobalementoptimaux soientobtenus. Lesproble`mesd’optimisationdistribue´esouscontraintes(DCOP)sontuncadrequi are´cemmente´merge´ commee´tantunedesapprocheslesplusperformantespourlacoordinationde MAS. Cettethe`seadressetroispointsprincipauxdeDCOP:lesalgorithmesefficacesd’optimisation,les environnementsdynamiquesetouverts,etlesmanipulationspardesagentsstrate´giques. Nousappor- tonsdescontributionssignificativesdanstoutescesdirections: encequiconcernel’e´fficacite´,nous pre´sentonsunese´ried’algorithmesdeDCOPquisontbase´ssurlaprogrammationdynamique,etoffrent desperformancesconsiderablementmeilleuresquelesalgorithmespre´ce´dents.Labasedecetteclasse d’algorithmesestDPOP,unalgorithmedistribue´quiexigeseulementunnombreline´airedemessages, e´conomisantainsidesressourcesdere´seau.Pourlesenvironnementsdynamiques,nouspre´sentonsdes algorithmesauto-stabilisantsquipeuventprendreencomptedeschangementsdansl’environnement etmettenta` jourlessolutionsentempsre´el. Pouragentsstrate´giques,nousproposonsl’algorithme M-DPOP,quiestlepremieralgorithmedeDCOPquifaitducomportementhonneˆteune´quilibrepost- Nashenappliquantleme´canismedeVCGdefac¸ondistribue´e.Nousdiscutonse´galementdelaquestion dele´quilibredubudget,etpre´sentonsdeuxalgorithmesquipermettentderedistribuer[partiellement] les paiements VCG aux agents, e´vitant ainsi laperted’utilite´ provoque´e par le gaspillagedes taxes VCG. Mots-cle´s:intelligenceartificielle,optimisationsouscontraintes,syste`mesdynamiques,syste`mes multiagent,agentsstrate´giques