{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T16:02:30Z","timestamp":1757779350533},"reference-count":70,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T00:00:00Z","timestamp":1498521600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2017,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper explores the use of<jats:italic>Answer Set Programming (ASP)<\/jats:italic>in solving<jats:italic>Distributed Constraint Optimization Problems (DCOPs)<\/jats:italic>. The paper provides the following novel contributions: (1) it shows how one can formulate DCOPs as logic programs; (2) it introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (3) it experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative programming counterpart) as well as solve some problems that DPOP fails to solve, due to memory limitations; and (4) it demonstrates the applicability of ASP in a wide array of multi-agent problems currently modeled as DCOPs.<\/jats:p>","DOI":"10.1017\/s147106841700014x","type":"journal-article","created":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T09:04:10Z","timestamp":1498554250000},"page":"634-683","source":"Crossref","is-referenced-by-count":3,"title":["Solving distributed constraint optimization problems using logic programming"],"prefix":"10.1017","volume":"17","author":[{"given":"TIEP","family":"LE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TRAN CAO","family":"SON","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ENRICO","family":"PONTELLI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WILLIAM","family":"YEOH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,6,27]]},"reference":[{"key":"S147106841700014X_ref16","doi-asserted-by":"crossref","DOI":"10.2200\/S00457ED1V01Y201211AIM019","volume-title":"Answer Set Solving in Practice","author":"Gebser","year":"2012"},{"key":"S147106841700014X_ref26","unstructured":"Gutierrez P. and Meseguer P. 2012a. Improving BnB-ADOPT+-AC. In Proc. of AAMAS, 273\u2013280."},{"key":"S147106841700014X_ref55","unstructured":"Petcu A. and Faltings B. 2006. ODPOP: An algorithm for open\/distributed constraint optimization. In Proc. of 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference. July 16\u201320, 2006, Boston, Massachusetts, USA, 703\u2013708."},{"key":"S147106841700014X_ref44","unstructured":"Maheswaran R. , Pearce J. and Tambe M. 2004. Distributed algorithms for DCOP: A graphical game-based approach. In Proc. of PDCS, 432\u2013439."},{"key":"S147106841700014X_ref47","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S147106841700014X_ref35","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018934223383"},{"key":"S147106841700014X_ref32","doi-asserted-by":"crossref","unstructured":"Jain P. , Gupta S. , Ranade S. and Pontelli E. 2012. Optimum operation of a customer-driven microgrid: A comprehensive approach. In Proc. of PEDES.","DOI":"10.1109\/PEDES.2012.6484437"},{"key":"S147106841700014X_ref34","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2672"},{"key":"S147106841700014X_ref51","unstructured":"Ottens B. , Dimitrakakis C. and Faltings B. 2012. DUCT: An upper confidence bound approach to distributed constraint optimization problems. In Proc. of AAAI, 528\u2013534."},{"key":"S147106841700014X_ref8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.3233\/FI-2010-359","article-title":"An investigation of multi-agent planning in CLP","volume":"105","author":"Dovier","year":"2010","journal-title":"Fundamentae Informatica"},{"key":"S147106841700014X_ref41","unstructured":"L\u00e9aut\u00e9 T. and Faltings B. 2011. Coordinating logistics operations with privacy guarantees. In Proc. of IJCAI, 2482\u20132487."},{"key":"S147106841700014X_ref15","unstructured":"Fioretto F. , Yeoh W. and Pontelli E. 2016. Multi-variable agents decomposition for dcops. In Proc. of 30th AAAI Conference on Artificial Intelligence, Phoenix, Arizona, USA, February 12\u201317, 2016, 2480\u20132486."},{"key":"S147106841700014X_ref19","unstructured":"Gelfond G. and Watson R. 2007. Modeling cooperative multi-agent systems. In Proc. of ASP Workshop."},{"key":"S147106841700014X_ref2","unstructured":"Baral C. , Gelfond G. , Pontelli E. and Son T. C. 2010. Modeling multi-agent scenarios involving agents knowledge about other's knowledge using ASP. In Proc. of AAMAS, 259\u2013266."},{"key":"S147106841700014X_ref14","doi-asserted-by":"crossref","unstructured":"Fioretto F. , Le T. , Yeoh W. , Pontelli E. and Son T. C. 2014. Improving DPOP with branch consistency for solving distributed constraint optimization problems. In Proc. of CP.","DOI":"10.1007\/978-3-319-10428-7_24"},{"key":"S147106841700014X_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000013"},{"key":"S147106841700014X_ref30","unstructured":"IEEE Distribution Test Feeders. 2014. URL: http:\/\/ewh.ieee.org\/soc\/pes\/dsacom\/testfeeders\/ [Accessed on: 29\/07\/2014]."},{"key":"S147106841700014X_ref43","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212357"},{"key":"S147106841700014X_ref5","unstructured":"Citrigno S. , Eiter T. , Faber W. , Gottlob G. , Koch C. , Leone N. , Mateis C. , Pfeifer G. and Scarcello F. 1997. The dlv system: Model generator and application frontends. In Proc. of Workshop on Logic Programming, 128\u2013137."},{"key":"S147106841700014X_ref64","unstructured":"Ueda S. , Iwasaki A. and Yokoo M. 2010. Coalition structure generation based on distributed constraint optimization. In Proc. of AAAI, 197\u2013203."},{"key":"S147106841700014X_ref7","volume-title":"Constraint Processing","author":"Dechter","year":"2003"},{"key":"S147106841700014X_ref36","unstructured":"Kumar A. , Faltings B. and Petcu A. 2009. Distributed constraint optimization with structured resource constraints. In Proc. of AAMAS, 923\u2013930."},{"key":"S147106841700014X_ref52","volume-title":"A Class of Algorithms for Distributed Constraint Optimization","author":"Petcu","year":"2009"},{"key":"S147106841700014X_ref6","doi-asserted-by":"crossref","unstructured":"De Vos M. , Crick T. , Padget J. A. , Brain M. , Cliffe O. and Needham J. 2005. LAIMA: A multi-agent platform using ordered choice logic programming. In Proc. of DALT.","DOI":"10.1007\/11691792_5"},{"key":"S147106841700014X_ref61","unstructured":"Sakama C. , Son T. C. and Pontelli E. 2011. A logical formulation for negotiation among dishonest agents. In Proc. of IJCAI, 1069\u20131074."},{"key":"S147106841700014X_ref42","unstructured":"L\u00e9aut\u00e9 T. , Ottens B. and Szymanek R. 2009. FRODO 2.0: An open-source framework for distributed constraint optimization. In Proc. of Distributed Constraint Reasoning Workshop, 160\u2013164."},{"key":"S147106841700014X_ref39","unstructured":"Le T. , Pontelli E. , Son T. C. and Yeoh W. 2014. Logic and constraint logic programming for distributed constraint optimization. Technical Communications of the Thirtieth International Conference on Logic Programming (ICLP' 14). Theory and Practice of Logic Programming, Online Supplement."},{"key":"S147106841700014X_ref45","unstructured":"Maheswaran R. , Tambe M. , Bowring E. , Pearce J. and Varakantham P. 2004. Taking DCOP to the real world: Efficient complete solutions for distributed event scheduling. In Proc. of AAMAS, 310\u2013317."},{"key":"S147106841700014X_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"},{"key":"S147106841700014X_ref29","unstructured":"Hamadi Y. , Bessi\u00e8re C. and Quinqueton J. 1998. Distributed intelligent backtracking. In Proc. of ECAI, 219\u2013223."},{"key":"S147106841700014X_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90033-7"},{"key":"S147106841700014X_ref3","doi-asserted-by":"crossref","unstructured":"Bessiere C. , Gutierrez P. and Meseguer P. 2012. Including soft global constraints in DCOPs. In Proc. of CP, 175\u2013190.","DOI":"10.1007\/978-3-642-33558-7_15"},{"key":"S147106841700014X_ref33","unstructured":"Kakas A. , Torroni P. and Demetriou N. 2004. Agent Planning, negotiation and control of operation. In Proc. of ECAI."},{"key":"S147106841700014X_ref22","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1613\/jair.2591","article-title":"Asynchronous forward-bounding for distributed COPs","volume":"34","author":"Gershman","year":"2009","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S147106841700014X_ref4","volume-title":"SICStus Prolog User's Manual","author":"Carlsson","year":"2015"},{"key":"S147106841700014X_ref54","unstructured":"Petcu A. and Faltings B. 2005b. Superstabilizing, fault-containing multiagent combinatorial optimization. In Proc. of AAAI, 449\u2013454."},{"key":"S147106841700014X_ref65","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-010-9132-7"},{"key":"S147106841700014X_ref25","doi-asserted-by":"crossref","unstructured":"Gutierrez P. , Lee J. , Lei K. M. , Mak T. and Meseguer P. 2013. Maintaining soft arc consistencies in BnB-ADOPT+ during search. In Proc. of CP, 365\u2013380.","DOI":"10.1007\/978-3-642-40627-0_30"},{"key":"S147106841700014X_ref60","doi-asserted-by":"crossref","unstructured":"Sadri F. and Toni F. 2003. Abductive logic programming for communication and negotiation amongst agents. ALP Newsletter.","DOI":"10.1007\/3-540-45757-7_35"},{"key":"S147106841700014X_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139342124"},{"key":"S147106841700014X_ref18","doi-asserted-by":"crossref","unstructured":"Gebser M. , Kaufmann B. , Neumann A. and Schaub T. 2007. Clasp: A conflict-driven answer set solver. In Proc. of LPNMR, 260\u2013265.","DOI":"10.1007\/978-3-540-72200-7_23"},{"key":"S147106841700014X_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000615"},{"key":"S147106841700014X_ref21","unstructured":"Gelfond M. and Lifschitz V. 1990. Logic programs with classical negation. In Proc. of ICLP, 579\u2013597."},{"key":"S147106841700014X_ref46","unstructured":"Mailler R. and Lesser V. 2004. Solving distributed constraint optimization problems using cooperative mediation. In Proc. of AAMAS, 438\u2013445."},{"key":"S147106841700014X_ref27","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1613\/jair.3696","article-title":"Removing redundant messages in n-ary BnB-ADOPT","volume":"45","author":"Gutierrez","year":"2012","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S147106841700014X_ref48","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.09.003"},{"key":"S147106841700014X_ref40","doi-asserted-by":"crossref","unstructured":"Le T. , Son T. C. , Pontelli E. and Yeoh W. 2015. Solving distributed constraint optimization problems with logic programming. In Proc. of AAAI.","DOI":"10.1609\/aaai.v29i1.9365"},{"key":"S147106841700014X_ref11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u00f6s","year":"1959","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"S147106841700014X_ref58","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1613\/jair.2500","article-title":"M-DPOP: Faithful distributed implementation of efficient social choice problems","volume":"32","author":"Petcu","year":"2008","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S147106841700014X_ref37","unstructured":"Kumar A. , Petcu A. and Faltings B. 2008. H-DPOP: Using hard constraints for search space pruning in DCOP. In Proc. of AAAI, 325\u2013330."},{"key":"S147106841700014X_ref13","unstructured":"Fioretto F. , Campeotto F. , Da Rin Fioretto L. , Yeoh W. and Pontelli E. 2014. GD-Gibbs: A GPU-based sampling algorithm for solving distributed constraint optimization problems (Extended Abstract). In Proc. of AAMAS."},{"key":"S147106841700014X_ref28","unstructured":"Gutierrez P. , Meseguer P. and Yeoh W. 2011. Generalizing ADOPT and BnB-ADOPT. In Proc. of IJCAI, 554\u2013559."},{"key":"S147106841700014X_ref63","unstructured":"Sultanik E. , Lass R. and Regli W. 2007. DCOPolis: A framework for simulating and deploying distributed constraint reasoning algorithms. In Proc. of Distributed Constraint Reasoning Workshop."},{"key":"S147106841700014X_ref68","unstructured":"Yeoh W. , Varakantham P. and Koenig S. 2009. Caching schemes for DCOP search algorithms. In Proc. of AAMAS, 609\u2013616."},{"key":"S147106841700014X_ref17","doi-asserted-by":"crossref","first-page":"107","DOI":"10.3233\/AIC-2011-0491","article-title":"Potassco: The potsdam answer set solving collection","volume":"24","author":"Gebser","year":"2011","journal-title":"AI Communications"},{"key":"S147106841700014X_ref69","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v33i3.2429"},{"key":"S147106841700014X_ref12","unstructured":"Farinelli A. , Rogers A. , Petcu A. and Jennings N. 2008. Decentralised coordination of low-power embedded devices using the Max-Sum algorithm. In Proc. of AAMAS, 639\u2013646."},{"key":"S147106841700014X_ref62","doi-asserted-by":"crossref","unstructured":"Son T. C. , Pontelli E. and Sakama C. 2009. Logic programming for multiagent planning with negotiation. In Proc. of ICLP, 99\u2013114.","DOI":"10.1007\/978-3-642-02846-5_13"},{"key":"S147106841700014X_ref49","unstructured":"Nguyen D. T. , Yeoh W. and Lau H. C. 2013. Distributed Gibbs: A memory-bounded sampling-based DCOP algorithm. In Proc. of AAMAS, 167\u2013174."},{"key":"S147106841700014X_ref70","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.03.002"},{"key":"S147106841700014X_ref53","unstructured":"Petcu A. and Faltings B. 2005a. A scalable method for multiagent constraint optimization. In Proc. of IJCAI, 1413\u20131420."},{"key":"S147106841700014X_ref56","unstructured":"Petcu A. and Faltings B. 2007. MB-DPOP: A new memory-bounded algorithm for distributed optimization. In Proc. of IJCAI, 1452\u20131457."},{"key":"S147106841700014X_ref24","unstructured":"Gupta S. , Jain P. , Yeoh W. , Ranade S. and Pontelli E. 2013. Solving customer-driven microgrid optimization problems as DCOPs. In Proc. of Distributed Constraint Reasoning Workshop, 45\u201359."},{"key":"S147106841700014X_ref59","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1017\/S1471068410000359","article-title":"Logic programming for finding models in the logics of knowledge and its applications: A case study","volume":"10","author":"Pontelli","year":"2010","journal-title":"Theory and Practice of Logic Programming"},{"key":"S147106841700014X_ref66","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(02)00190-1"},{"key":"S147106841700014X_ref67","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1613\/jair.2849","article-title":"BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm","volume":"38","author":"Yeoh","year":"2010","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S147106841700014X_ref50","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S147106841700014X_ref38","unstructured":"Lass R. , Kopena J. , Sultanik E. , Nguyen D. , Dugan C. , Modi P. and Regli W. 2008. Coordination of first responders under communication and resource constraints (Short Paper). In Proc. of AAMAS, 1409\u20131413."},{"key":"S147106841700014X_ref23","unstructured":"Greenstadt R. , Pearce J. P. and Tambe M. 2006. Analysis of privacy loss in distributed constraint optimization. In Proc. of 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference. July 16\u201320, 2006, Boston, MA, USA, 647\u2013653."},{"key":"S147106841700014X_ref57","unstructured":"Petcu A. , Faltings B. and Mailler R. 2007. PC-DPOP: A new partial centralization algorithm for distributed optimization. In Proc. of IJCAI, 167\u2013172."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106841700014X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T05:13:41Z","timestamp":1692854021000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841700014X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,27]]},"references-count":70,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["S147106841700014X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841700014x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,27]]}}}