Distributed constraint optimization - Revision history

GreenC bot: Move 1 url. Wayback Medic 2.5 per WP:URLREQ#citeftp

2025-05-27T22:57:41Z

Move 1 url. Wayback Medic 2.5 per WP:URLREQ#citeftp

← Previous revision		Revision as of 22:57, 27 May 2025
Line 221:		Line 221:
	[https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[GNU Affero General Public License\|AGPL]])		[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">{{~~Citation~~		\| '''OptAPO'''<br />Asynchronous Partial Overlay<ref name="mailler04solving">{{Cite FTP \| last1 = Mailler
	\| last1 = Mailler
	\| first1 = Roger		\| first1 = Roger
	\| last2 = Lesser		\| last2 = Lesser
Line 230:		Line 229:
	\| pages = 438–445 <!-- \|doi=10.5555/1018409.1018777 -->		\| pages = 438–445 <!-- \|doi=10.5555/1018409.1018777 -->
	\| isbn = 1581138644		\| isbn = 1581138644
⚫	\| ~~publisher~~ = [[IEEE Computer Society]]
	\| year = 2004		\| year = 2004
		⚫	\| server = [[IEEE Computer Society]]
			\| url-status = dead
	\| contribution-url = ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf		\| contribution-url = ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf
			}}</ref>
	}}{{Dead link\|date=February 2024 \|bot=InternetArchiveBot \|fix-attempted=yes }}</ref>
	\| 2004		\| 2004
	\| Polynomial		\| Polynomial

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-27T03:03:48Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 03:03, 27 May 2025
Line 50:		Line 50:

	=== Distributed item allocation problem ===		=== Distributed item allocation problem ===
	The [[Fair item allocation\|item allocation]] problem is as follows. There are several items that have to be divided among several agents. Each agent has a different valuation for the items. The goal is to optimize some global goal, such as maximizing the sum of utilities or minimizing the envy. The item allocation problem can be formulated as a DCOP as follows.<ref name=":2">{{Cite journal\|last1=Netzer\|first1=Arnon\|last2=Meisels\|first2=Amnon\|last3=Zivan\|first3=Roie\|date=2016-03-01\|title=Distributed envy minimization for resource allocation\|url=https://doi.org/10.1007/s10458-015-9291-7\|journal=Autonomous Agents and Multi-Agent Systems \| volume=30\|issue=2\|pages=364–402\|doi=10.1007/s10458-015-9291-7\|s2cid=13834856\|issn=1387-2532}}</ref>		The [[Fair item allocation\|item allocation]] problem is as follows. There are several items that have to be divided among several agents. Each agent has a different valuation for the items. The goal is to optimize some global goal, such as maximizing the sum of utilities or minimizing the envy. The item allocation problem can be formulated as a DCOP as follows.<ref name=":2">{{Cite journal\|last1=Netzer\|first1=Arnon\|last2=Meisels\|first2=Amnon\|last3=Zivan\|first3=Roie\|date=2016-03-01\|title=Distributed envy minimization for resource allocation\|url=https://doi.org/10.1007/s10458-015-9291-7\|journal=Autonomous Agents and Multi-Agent Systems \| volume=30\|issue=2\|pages=364–402\|doi=10.1007/s10458-015-9291-7\|s2cid=13834856\|issn=1387-2532\|url-access=subscription}}</ref>

	* Add a binary variable ''v<sub>ij</sub>'' for each agent ''i'' and item ''j''. The variable value is "1" if the agent gets the item, and "0" otherwise. The variable is owned by agent ''i''.		* Add a binary variable ''v<sub>ij</sub>'' for each agent ''i'' and item ''j''. The variable value is "1" if the agent gets the item, and "0" otherwise. The variable is owned by agent ''i''.
Line 327:		Line 327:

	=== Approaches to solving an ADCOP ===		=== 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}}</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>		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\|last=Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, 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.		Another approach is called Private Events as Variables (PEAV).<ref>{{Cite web\|last=Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, 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.

Citation bot: Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Mathematical optimization | #UCB_Category 5/126

2025-04-07T04:14:10Z

Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Mathematical optimization | #UCB_Category 5/126

← Previous revision		Revision as of 04:14, 7 April 2025
Line 64:		Line 64:
	== Algorithms ==		== Algorithms ==

	DCOP algorithms can be classified in several ways:<ref name="yeoh06">{{Citation \|last1=Yeoh\|first1=William\|title=Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems \|volume=2 \|pages=591–8 \|year=2008 \|contribution=BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm\|contribution-url=http://idm-lab.org/bib/abstracts/Koen08d.html <!-- publisher is https://dl.acm.org/doi/10.5555/1402298.1402307 note that 10.5555 is a fake doi -->\|isbn=9780981738116 \|last2=Felner\|first2=Ariel\|last3=Koenig\|first3=Sven}}</ref>		DCOP algorithms can be classified in several ways:<ref name="yeoh06">{{Citation \|last1=Yeoh\|first1=William\|title=Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems \|volume=2 \|pages=591–8 \|year=2008 \|contribution=BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm\|contribution-url=http://idm-lab.org/bib/abstracts/Koen08d.html <!-- publisher is https://dl.acm.org/doi/10.5555/1402298.1402307 note that 10.5555 is a fake doi -->\|isbn=9780981738116 \|last2=Felner\|first2=Ariel\|last3=Koenig\|first3=Sven\|publisher=Ifaamas }}</ref>

	* ''Completeness'' - complete search algorithms finding the optimal solution, vs. [[Local search (optimization)\|local search]] algorithms finding a [[local optimum]].		* ''Completeness'' - complete search algorithms finding the optimal solution, vs. [[Local search (optimization)\|local search]] algorithms finding a [[local optimum]].

Citation bot: Altered title. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine

2024-06-22T01:44:28Z

Altered title. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 01:44, 22 June 2024
Line 104:		Line 104:
	\| [http://liawww.epfl.ch/frodo1/ FRODO version 1]{{dead link\|date=September 2017 \|bot=InternetArchiveBot \|fix-attempted=yes }}		\| [http://liawww.epfl.ch/frodo1/ FRODO version 1]{{dead link\|date=September 2017 \|bot=InternetArchiveBot \|fix-attempted=yes }}
	\|-		\|-
	\|'''SyncBB'''<ref>{{Cite book\|last1=Hirayama\|first1=Katsutoshi\|last2=Yokoo\|first2=Makoto\|date=1997\|editor-last=Smolka\|editor-first=Gert\|~~title~~=Distributed partial constraint satisfaction problem\|url=https://link.springer.com/chapter/10.1007/BFb0017442\|~~journal~~=Principles and Practice of Constraint Programming-CP97\|series=Lecture Notes in Computer Science\|volume=1330\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=222–236\|doi=10.1007/BFb0017442\|isbn=978-3-540-69642-1}}</ref>		\|'''SyncBB'''<ref>{{Cite book\|last1=Hirayama\|first1=Katsutoshi\|last2=Yokoo\|first2=Makoto\|date=1997\|editor-last=Smolka\|editor-first=Gert\|chapter=Distributed partial constraint satisfaction problem\|chapter-url=https://link.springer.com/chapter/10.1007/BFb0017442\|title=Principles and Practice of Constraint Programming-CP97\|series=Lecture Notes in Computer Science\|volume=1330\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=222–236\|doi=10.1007/BFb0017442\|isbn=978-3-540-69642-1}}</ref>
	Synchronous Branch and Bound		Synchronous Branch and Bound
	\|1997		\|1997
Line 327:		Line 327:

	=== Approaches to solving an ADCOP ===		=== 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}}</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\|~~title~~=Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information\|url=https://link.springer.com/chapter/10.1007/3-540-46135-3_26 \|~~journal~~=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>		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}}</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\|last=Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, 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.		Another approach is called Private Events as Variables (PEAV).<ref>{{Cite web\|last=Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, 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.

Kissaki0: Update AGPL links

2024-02-26T16:27:06Z

Update AGPL links

← Previous revision		Revision as of 16:27, 26 February 2024
Line 219:		Line 219:
	\| ''Reference Implementation:'' [http://teamcore.usc.edu/dcop/ Adopt] {{Webarchive\|url=https://web.archive.org/web/20060916180148/http://teamcore.usc.edu/dcop/ \|date=2006-09-16 }}<br />		\| ''Reference Implementation:'' [http://teamcore.usc.edu/dcop/ Adopt] {{Webarchive\|url=https://web.archive.org/web/20060916180148/http://teamcore.usc.edu/dcop/ \|date=2006-09-16 }}<br />
	[https://archive.today/20080919011453/http://dcopolis.sf.net/ DCOPolis] ([[GNU Lesser General Public License\|GNU LGPL]])<br />		[https://archive.today/20080919011453/http://dcopolis.sf.net/ DCOPolis] ([[GNU Lesser General Public License\|GNU LGPL]])<br />
	[https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[Affero General Public License\|~~GNU Affero GPL~~]])		[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">{{Citation		\| '''OptAPO'''<br />Asynchronous Partial Overlay<ref name="mailler04solving">{{Citation
Line 263:		Line 263:
	\| Linear		\| Linear
	\| Proven		\| Proven
	\| ''Reference Implementation:'' [https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[Affero General Public License\|~~GNU Affero GPL~~]])<br />		\| ''Reference Implementation:'' [https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[GNU Affero General Public License\|AGPL]])<br />
	[https://archive.today/20080919011453/http://dcopolis.sourceforge.net/ DCOPolis] ([[GNU Lesser General Public License\|GNU LGPL]])		[https://archive.today/20080919011453/http://dcopolis.sourceforge.net/ DCOPolis] ([[GNU Lesser General Public License\|GNU LGPL]])
	\|-		\|-

InternetArchiveBot: Rescuing 3 sources and tagging 1 as dead.) #IABot (v2.0.9.5

2024-02-04T05:20:44Z

Rescuing 3 sources and tagging 1 as dead.) #IABot (v2.0.9.5

← Previous revision		Revision as of 05:20, 4 February 2024
Line 164:		Line 164:
	\| '''Adopt'''<br />Asynchronous Backtracking<ref>The originally published version of Adopt was uninformed, see		\| '''Adopt'''<br />Asynchronous Backtracking<ref>The originally published version of Adopt was uninformed, see
	{{Citation		{{Citation
	\| last1 = Modi \| first1 = Pragnesh Jay		\| last1 = Modi
			\| first1 = Pragnesh Jay
	\| last2 = Shen \| first2 = Wei-Min		\| last2 = Shen
			\| first2 = Wei-Min
	\| last3 = Tambe \| first3 = Milind		\| last3 = Tambe
			\| first3 = Milind
	\| last4 = Yokoo \| first4 = Makoto		\| last4 = Yokoo
			\| first4 = Makoto
	\| contribution = An asynchronous complete method for distributed constraint optimization		\| contribution = An asynchronous complete method for distributed constraint optimization
	\| title = Proceedings of the second international joint conference on autonomous agents and multiagent systems		\| title = Proceedings of the second international joint conference on autonomous agents and multiagent systems
Line 173:		Line 177:
	\| year = 2003		\| year = 2003
	\| pages = 161–168		\| pages = 161–168
	\| contribution-url = http://teamcore.usc.edu/papers/2003/modi-aamas03.pdf~~}}. The original version of Adopt was later extended to be informed, that is, to use estimates of the solution costs to focus its search and run faster, see~~		\| contribution-url = http://teamcore.usc.edu/papers/2003/modi-aamas03.pdf
			\| access-date = 2009-09-07
			\| archive-date = 2019-11-04
			\| archive-url = https://web.archive.org/web/20191104183451/http://teamcore.usc.edu/papers/2003/modi-aamas03.pdf
			\| url-status = dead
			}}. The original version of Adopt was later extended to be informed, that is, to use estimates of the solution costs to focus its search and run faster, see
	{{Citation		{{Citation
	\| ~~last1~~ = ~~Ali~~ \| ~~first1~~ = ~~Syed~~		\|last1 = Ali
	\| ~~last2~~ = ~~Koenig~~ \| ~~first2~~ = ~~Sven~~		\|first1 = Syed
	\| ~~last3~~ = ~~Tambe~~ \| ~~first3~~ = ~~Milind~~		\|last2 = Koenig
			\|first2 = Sven
⚫	\| ~~contribution~~ = Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT
			\|last3 = Tambe
⚫	\| ~~title~~ = Proceedings of the fourth international joint conference on autonomous agents and multiagent systems
			\|first3 = Milind
⚫	\| ~~publisher~~ = [[Association for Computing Machinery\|ACM]] Press
		⚫	\|contribution = Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT
	\| year = 2005
		⚫	\|title = Proceedings of the fourth international joint conference on autonomous agents and multiagent systems
	\| pages = 1041–8 \|doi=10.1145/1082473.1082631 \|isbn=1595930930
		⚫	\|publisher = [[Association for Computing Machinery\|ACM]] Press
	\| s2cid = 10882572
			\|year = 2005
⚫	~~\| contribution-url = http://teamcore.usc.edu/papers/2005/aamas-paper.pdf~~}}. This extension of Adopt is typically used as reference implementation of Adopt.</ref>
			\|pages = 1041–8
			\|doi = 10.1145/1082473.1082631
			\|isbn = 1595930930
			\|s2cid = 10882572
			\|contribution-url = http://teamcore.usc.edu/papers/2005/aamas-paper.pdf
			\|access-date = 2009-09-07
			\|archive-date = 2010-07-07
			\|archive-url = https://web.archive.org/web/20100707183003/http://teamcore.usc.edu/papers/2005/aamas-paper.pdf
			\|url-status = dead
		⚫	}}. This extension of Adopt is typically used as reference implementation of Adopt.</ref>
	\| 2003		\| 2003
	\| Polynomial (or any-space<ref name="matsui05efficient">		\| Polynomial (or any-space<ref name="matsui05efficient">
Line 198:		Line 217:
	\| Exponential		\| Exponential
	\| Proven		\| Proven
	\| ''Reference Implementation:'' [http://teamcore.usc.edu/dcop/ Adopt]<br />		\| ''Reference Implementation:'' [http://teamcore.usc.edu/dcop/ Adopt] {{Webarchive\|url=https://web.archive.org/web/20060916180148/http://teamcore.usc.edu/dcop/ \|date=2006-09-16 }}<br />
	[https://archive.today/20080919011453/http://dcopolis.sf.net/ DCOPolis] ([[GNU Lesser General Public License\|GNU LGPL]])<br />		[https://archive.today/20080919011453/http://dcopolis.sf.net/ DCOPolis] ([[GNU Lesser General Public License\|GNU LGPL]])<br />
	[https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[Affero General Public License\|GNU Affero GPL]])		[https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/ FRODO] ([[Affero General Public License\|GNU Affero GPL]])
	\|-		\|-
	\| '''OptAPO'''<br />Asynchronous Partial Overlay<ref name="mailler04solving">		\| '''OptAPO'''<br />Asynchronous Partial Overlay<ref name="mailler04solving">{{Citation
			\| last1 = Mailler
	{{Citation
	~~\| last1 = Mailler~~ \| first1 = Roger		\| first1 = Roger
	\| last2 = Lesser \| first2 = Victor		\| last2 = Lesser
			\| first2 = Victor
	\| contribution = Solving Distributed Constraint Optimization Problems Using Cooperative Mediation		\| contribution = Solving Distributed Constraint Optimization Problems Using Cooperative Mediation
	\| title = Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems		\| title = Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems
	\| pages = 438–445 <!-- \|doi=10.5555/1018409.1018777 --> \|isbn=1581138644		\| pages = 438–445 <!-- \|doi=10.5555/1018409.1018777 -->
			\| isbn = 1581138644
	\| publisher = [[IEEE Computer Society]]		\| publisher = [[IEEE Computer Society]]
	\| year = 2004		\| year = 2004
	\| contribution-url = ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf~~}}</ref>~~		\| contribution-url = ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf
			}}{{Dead link\|date=February 2024 \|bot=InternetArchiveBot \|fix-attempted=yes }}</ref>
	\| 2004		\| 2004
	\| Polynomial		\| Polynomial

OAbot: Open access bot: arxiv updated in citation with #oabot.

2024-01-03T01:21:08Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 01:21, 3 January 2024
Line 294:		Line 294:

	== {{Anchor\|adcop}}Asymmetric DCOP ==		== {{Anchor\|adcop}}Asymmetric DCOP ==
	An '''asymmetric DCOP''' is an extension of DCOP in which the cost of each constraint may be different for different agents. Some example applications are:<ref name=":0">{{Cite journal\|last1=Grinshpoun\|first1=T.\|last2=Grubshtein\|first2=A.\|last3=Zivan\|first3=R.\|last4=Netzer\|first4=A.\|last5=Meisels\|first5=A.\|date=2013-07-30\|title=Asymmetric Distributed Constraint Optimization Problems\|url=https://www.jair.org/index.php/jair/article/view/10828\|journal=Journal of Artificial Intelligence Research\|language=en\|volume=47\|pages=613–647\|doi=10.1613/jair.3945\|issn=1076-9757\|doi-access=free}}</ref>		An '''asymmetric DCOP''' is an extension of DCOP in which the cost of each constraint may be different for different agents. Some example applications are:<ref name=":0">{{Cite journal\|last1=Grinshpoun\|first1=T.\|last2=Grubshtein\|first2=A.\|last3=Zivan\|first3=R.\|last4=Netzer\|first4=A.\|last5=Meisels\|first5=A.\|date=2013-07-30\|title=Asymmetric Distributed Constraint Optimization Problems\|url=https://www.jair.org/index.php/jair/article/view/10828\|journal=Journal of Artificial Intelligence Research\|language=en\|volume=47\|pages=613–647\|doi=10.1613/jair.3945\|issn=1076-9757\|doi-access=free\|arxiv=1402.0587}}</ref>

	* ''[[Event scheduling]]'': agents who attend the same event might derive different values from it.		* ''[[Event scheduling]]'': agents who attend the same event might derive different values from it.

Citation bot: Alter: template type. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 396/2500

2023-12-08T14:11:03Z

Alter: template type. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 396/2500

← Previous revision		Revision as of 14:11, 8 December 2023
Line 104:		Line 104:
	\| [http://liawww.epfl.ch/frodo1/ FRODO version 1]{{dead link\|date=September 2017 \|bot=InternetArchiveBot \|fix-attempted=yes }}		\| [http://liawww.epfl.ch/frodo1/ FRODO version 1]{{dead link\|date=September 2017 \|bot=InternetArchiveBot \|fix-attempted=yes }}
	\|-		\|-
	\|'''SyncBB'''<ref>{{Cite ~~journal~~\|last1=Hirayama\|first1=Katsutoshi\|last2=Yokoo\|first2=Makoto\|date=1997\|editor-last=Smolka\|editor-first=Gert\|title=Distributed partial constraint satisfaction problem\|url=https://link.springer.com/chapter/10.1007/BFb0017442\|journal=Principles and Practice of Constraint Programming-CP97\|series=Lecture Notes in Computer Science\|volume=1330\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=222–236\|doi=10.1007/BFb0017442\|isbn=978-3-540-69642-1}}</ref>		\|'''SyncBB'''<ref>{{Cite book\|last1=Hirayama\|first1=Katsutoshi\|last2=Yokoo\|first2=Makoto\|date=1997\|editor-last=Smolka\|editor-first=Gert\|title=Distributed partial constraint satisfaction problem\|url=https://link.springer.com/chapter/10.1007/BFb0017442\|journal=Principles and Practice of Constraint Programming-CP97\|series=Lecture Notes in Computer Science\|volume=1330\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=222–236\|doi=10.1007/BFb0017442\|isbn=978-3-540-69642-1}}</ref>
	Synchronous Branch and Bound		Synchronous Branch and Bound
	\|1997		\|1997
Line 305:		Line 305:

	=== Approaches to solving an ADCOP ===		=== 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}}</ref><ref>{{Cite ~~journal~~ \|last1=Yokoo \|first1=Makoto \|last2=Suzuki \|first2=Koutarou \|last3=Hirayama\|first3=Katsutoshi\|date=2002\|editor-last=Van Hentenryck\|editor-first=Pascal\|title=Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information\|url=https://link.springer.com/chapter/10.1007/3-540-46135-3_26 \|journal=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>		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}}</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\|title=Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information\|url=https://link.springer.com/chapter/10.1007/3-540-46135-3_26 \|journal=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\|last=Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, 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.		Another approach is called Private Events as Variables (PEAV).<ref>{{Cite web\|last=Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, 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.

Citation bot: Add: volume. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2023-07-24T15:58:07Z

Add: volume. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 15:58, 24 July 2023
Line 318:		Line 318:

	=== Partial cooperation ===		=== Partial cooperation ===
	There are some intermediate models in which the agents are ''partially-cooperative'': they are willing to decrease their utility to help the global goal, but only if their own cost is not too high. An example of partially-cooperative agents are employees in a firm. On one hand, each employee wants to maximize their own utility; on the other hand, they also want to contribute to the success of the firm. Therefore, they are willing to help others or do some other time-consuming tasks that help the firm, as long as it is not too burdensome on them. Some models for partially-cooperative agents are:<ref name=":1">{{Cite journal\|last1=Zivan \|first1=Roie\|last2=Grubshtein\|first2=Alon\|last3=Friedman\|first3=Michal\|last4=Meisels\|first4=Amnon\|date=2012-06-04\|title=Partial cooperation in multi-agent search\|url=https://dl.acm.org/doi/abs/10.5555/2343896.2343956\|journal=Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3\|series=AAMAS '12\|location=Valencia, Spain \|publisher=International Foundation for Autonomous Agents and Multiagent Systems\|pages=1267–1268\|doi= \|isbn=978-0-9817381-3-0}}</ref>		There are some intermediate models in which the agents are ''partially-cooperative'': they are willing to decrease their utility to help the global goal, but only if their own cost is not too high. An example of partially-cooperative agents are employees in a firm. On one hand, each employee wants to maximize their own utility; on the other hand, they also want to contribute to the success of the firm. Therefore, they are willing to help others or do some other time-consuming tasks that help the firm, as long as it is not too burdensome on them. Some models for partially-cooperative agents are:<ref name=":1">{{Cite journal\|last1=Zivan \|first1=Roie\|last2=Grubshtein\|first2=Alon\|last3=Friedman\|first3=Michal\|last4=Meisels\|first4=Amnon\|date=2012-06-04\|title=Partial cooperation in multi-agent search\|url=https://dl.acm.org/doi/abs/10.5555/2343896.2343956\|journal=Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3\|series=AAMAS '12\|volume=3 \|location=Valencia, Spain \|publisher=International Foundation for Autonomous Agents and Multiagent Systems\|pages=1267–1268\|doi= \|isbn=978-0-9817381-3-0}}</ref>

	* ''Guaranteed personal benefit'': the agents agree to act for the global good if their own utility is at least as high as in the non-cooperative setting (i.e., the final outcome must be a [[Pareto improvement]] of the original state).		* ''Guaranteed personal benefit'': the agents agree to act for the global good if their own utility is at least as high as in the non-cooperative setting (i.e., the final outcome must be a [[Pareto improvement]] of the original state).

Headbomb: Autonomous Agents and Multi-Agent Systems

2023-07-24T15:56:12Z

Autonomous Agents and Multi-Agent Systems

← Previous revision		Revision as of 15:56, 24 July 2023
Line 340:		Line 340:
	* {{Citation \| last1=Shoham \| first1=Yoav \| last2=Leyton-Brown \| first2=Kevin \| title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations \| publisher=[[Cambridge University Press]] \| isbn=978-0-521-89943-7 \| url=http://www.masfoundations.org \| year=2009 \| location=New York}} See Chapters 1 and 2; [http://www.masfoundations.org/download.html downloadable free online].		* {{Citation \| last1=Shoham \| first1=Yoav \| last2=Leyton-Brown \| first2=Kevin \| title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations \| publisher=[[Cambridge University Press]] \| isbn=978-0-521-89943-7 \| url=http://www.masfoundations.org \| year=2009 \| location=New York}} See Chapters 1 and 2; [http://www.masfoundations.org/download.html downloadable free online].
	* {{Citation \| last1=Yokoo \| first1=Makoto \| title=Distributed constraint satisfaction: Foundations of cooperation in multi-agent systems \| publisher = [[Springer Science+Business Media\|Springer]] \| isbn=978-3-540-67596-9 \| year=2001}}		* {{Citation \| last1=Yokoo \| first1=Makoto \| title=Distributed constraint satisfaction: Foundations of cooperation in multi-agent systems \| publisher = [[Springer Science+Business Media\|Springer]] \| isbn=978-3-540-67596-9 \| year=2001}}
	* {{Citation \| last1=Yokoo \| first1=M. Hirayama K. \|year=2000 \|title=Algorithms for distributed constraint satisfaction: A review \|journal=Autonomous Agents and ~~Multiagent~~ Systems \|volume=3 \| issue=2 \|pages=185–207 \|doi=10.1023/A:1010078712316\| s2cid=2139298 }}		* {{Citation \| last1=Yokoo \| first1=M. Hirayama K. \|year=2000 \|title=Algorithms for distributed constraint satisfaction: A review \|journal=Autonomous Agents and Multi-Agent Systems \|volume=3 \| issue=2 \|pages=185–207 \|doi=10.1023/A:1010078712316\| s2cid=2139298 }}

	{{DEFAULTSORT:Distributed Constraint Optimization}}		{{DEFAULTSORT:Distributed Constraint Optimization}}