Distributed constraint optimization: Difference between revisions

Revision as of 22:57, 27 May 2025

Latest revision as of 01:27, 2 June 2025

Line 221:

[https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[GNU Affero General Public License|AGPL]])

|-

| '''OptAPO'''<br />Asynchronous Partial Overlay<ref name="mailler04solving">{{Cite FTPbook | last1 = Mailler

| first1 = Roger

| last2 = Lesser

| first2 = Victor

| contributionchapter = Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

| title = Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems

| pages = 438–445 <!-- |doi=10.5555/1018409.1018777 -->

| isbn = 1581138644

| year = 2004

| serverpublisher = [[IEEE Computer Society]]

<!-- | url-status = dead -->

| contribution-url = ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf

}}{{dead link|date=June 2025}}</ref>

| 2004

| Polynomial

Line 327:

=== Approaches to solving an ADCOP ===

A simple way for solving an ADCOP is to replace each constraint <math> f_C: D_1\times\cdots\times D_k \to \mathbb{R}^k</math> with a constraint <math> f_C': D_1\times\cdots\times D_k \to \mathbb{R}</math>, which equals the sum of the functions <math> f_C^1 + \cdots + f_C^k</math>. However, this solution requires the agents to reveal their cost functions. Often, this is not desired due to privacy considerations.<ref>{{Cite journal|last1=Greenstadt|first1=Rachel|last2=Pearce|first2=Jonathan P. |last3=Tambe|first3=Milind|date=2006-07-16|title=Analysis of privacy loss in distributed constraint optimization |url=https://dl.acm.org/doi/abs/10.5555/1597538.1597642|journal=Proceedings of the 21st National Conference on Artificial Intelligence - Volume 1|series=AAAI'06|___location=Boston, Massachusetts|publisher=AAAI Press |pages=647–653 |doi= |isbn=978-1-57735-281-5}}</ref><ref>{{Cite journal|last1=Maheswaran|first1=Rajiv T.|last2=Pearce|first2=Jonathan P.|last3=Bowring |first3=Emma|last4=Varakantham|first4=Pradeep|last5=Tambe|first5=Milind|date=2006-07-01|title=Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications|url=https://doi.org/10.1007/s10458-006-5951-y|journal=Autonomous Agents and Multi-Agent Systems|language=en|volume=13|issue=1|pages=27–60|doi=10.1007/s10458-006-5951-y|s2cid=16962945|issn=1573-7454|url-access=subscription}}</ref><ref>{{Cite book |last1=Yokoo |first1=Makoto |last2=Suzuki |first2=Koutarou |last3=Hirayama|first3=Katsutoshi|date=2002|editor-last=Van Hentenryck|editor-first=Pascal|chapter=Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information|chapter-url=https://link.springer.com/chapter/10.1007/3-540-46135-3_26 |title=Principles and Practice of Constraint Programming – CP 2002|series=Lecture Notes in Computer Science |volume=2470|language=en|___location=Berlin, Heidelberg |publisher=Springer |pages=387–401 |doi=10.1007/3-540-46135-3_26 |isbn=978-3-540-46135-7}}</ref>

Another approach is called Private Events as Variables (PEAV).<ref>{{Cite web|lastauthor1=Rajiv T. Maheswaran, |author2=Milind Tambe, |author3=Emma Bowring, |author4=Jonathan P. Pearce, |author5=Pradeep Varakantham|date=2004|title=Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling|url=https://www.computer.org/csdl/proceedings-article/aamas/2004/20920310/12OmNvjyxDN|access-date=2021-04-12|website=www.computer.org}}</ref> In this approach, each variable owns, in addition to his own variables, also "mirror variables" of all the variables owned by his neighbors in the constraint network. There are additional constraints (with a cost of infinity) that guarantee that the mirror variables equal the original variables. The disadvantage of this method is that the number of variables and constraints is much larger than the original, which leads to a higher run-time.

A third approach is to adapt existing algorithms, developed for DCOPs, to the ADCOP framework. This has been done for both complete-search algorithms and local-search algorithms.<ref name=":0" />