Rozproszona optymalizacja ograniczeń

Rozproszona optymalizacja z ograniczeniami ( DCOP lub DisCOP ) jest rozproszonym odpowiednikiem optymalizacji z ograniczeniami . DCOP to problem, w którym grupa agentów musi w sposób rozproszony wybrać wartości dla zestawu zmiennych w taki sposób, aby zminimalizować koszt zestawu ograniczeń dotyczących zmiennych.

Distributed Constraint Satisfaction jest strukturą opisującą problem w kategoriach ograniczeń, które są znane i egzekwowane przez odrębnych uczestników (agentów). Ograniczenia są opisane dla niektórych zmiennych z predefiniowanymi domenami i muszą być przypisane do tych samych wartości przez różnych agentów.

Problemy zdefiniowane w tej strukturze można rozwiązać za pomocą dowolnego algorytmu, który jest dla niej przeznaczony.

Ramy były używane pod różnymi nazwami w latach 80. Pierwsze znane użycie obecnej nazwy pochodzi z 1990 roku. ^{[ Potrzebne źródło ]}

Definicje

DCOP

Głównymi składnikami problemu DCOP są agenci i zmienne . Co ważne, każda zmienna jest własnością agenta; to właśnie sprawia, że problem jest rozproszony. Formalnie DCOP jest krotką ${\ Displaystyle \ langle A, V, {\ mathfrak {D}}, f, \ alfa, \ eta \ rangle$ }

$A}$ ${\ Displaystyle \ {a_ {1}, \ kropki, a_ {| A |} \}}$ to zbiór agentów , za .
${\ Displaystyle V}$ to zbiór zmiennych , ${\ Displaystyle \ {v_ {1}, v_ {2}, \ kropki, v_ {| V |} \}}$ .
${\ Displaystyle {\ mathfrak {D}}}$ ${\mathfrak {D}}$ to zbiór domen zmiennych , ${\ Displaystyle \ {D_ {1}, D_ {2}, \ kropki, D_ {| V|} \}}$ , gdzie każdy ${\ Displaystyle D_ {j} \ w {\ mathfrak {D} }}$ $D_{j}\in {\mathfrak {D}}$ to skończony zbiór zawierający możliwe wartości zmiennej ${\ displaystyle v_ {j}}$ $v_{j}$ .
- Jeśli $zawiera$ $dwie wartości$ np. 0 lub 1) to zmienną .
${\ displaystyle f}$ $f$ jest funkcją kosztu . Jest to funkcja

${\ Displaystyle f: \ bigcup _ {S \ subseteq V} \ razy _ {v_ {j} \ w S} D_ {j} \ do \ mathbb { R} }$
$f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R}$
który odwzorowuje każde możliwe częściowe przypisanie do kosztu. Zwykle tylko kilka wartości $niezerowych$ $f$ i jest reprezentowane jako lista krotek, którym przypisano wartość różną od zera Każda taka krotka nazywana jest ograniczeniem . Każde ograniczenie w tym zestawie jest funkcją $C }: D_ {1} \$ $C$ $\ cdots \ razy D_ {k} \ do \mathbb {R} }$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ przypisanie wartości rzeczywistej do każdego możliwego przypisania zmiennych. Niektóre specjalne rodzaje ograniczeń to:
- Jednoargumentowe ograniczenia $}\w V}$ dotyczące pojedynczej zmiennej, tj. $jot$ niektórych ${\$ .
- Ograniczenia binarne - ograniczenia dotyczące dwóch zmiennych, tj. $\ Displaystyle f_ {C}: D_ {j_ {1}} \ razy D_ {j_ {2}} \ do \ mathbb {R}}$ dla niektórych ${\ Displaystyle v_ {j_ {1}}, v_ {j_ {2}} \ w V}$ .
jest funkcją własności. α $\ displaystyle \ alpha} Jest$ $.$ funkcja każdą zmienną na ${\ Displaystyle \ alfa (v_ {j}) \ mapsto a_ {i}}$ oznacza, że zmienna ${\ Displaystyle v_ {j}}$ „należy” do agenta ${\ Displaystyle a_ {i}}$ . Oznacza to, że obowiązkiem agenta jest $wartości$ zmiennej ${j}}$ . Zauważ, że $,$ jest to zastrzyk tj. jeden agent może posiadać więcej niż jedną zmienną. Niekoniecznie jest to również surjekcja , tzn. niektórzy agenci mogą nie posiadać żadnych zmiennych.
${\ displaystyle \ eta}$ jest funkcją celu . Jest to operator $,$ który agreguje wszystkie indywidualne dla wszystkich możliwych przypisań zmiennych. Zwykle osiąga się to poprzez sumowanie: ${\ Displaystyle \ eta (f) \ mapsto \ suma _ {s \ w \ bigcup _ {S \ subseteq V} \ razy _ {v_ {j} \ w S} D_ {j}} f (s).}$

$.$ wartości swoim powiązanym zmiennym w celu zminimalizowania lub zmaksymalizowania przypisania zmiennych

Zadania

Przypisanie wartości to $d_ {j$ , gdzie ${\ Displaystyle$ } $displaystyle D_{j}}$ .

Częściowe przypisanie to zestaw przypisań wartości, z których każde $pojawia$ co najwyżej raz Nazywa się to również kontekstem. Można to traktować jako funkcję odwzorowującą zmienne w DCOP na ich bieżące wartości:

{\ Displaystyle t: V \ do (D \ w {\ mathfrak {D}}) \ kubek \ {\ pusty zestaw \}.}

Zauważ, że kontekst jest zasadniczo rozwiązaniem częściowym i nie musi zawierać wartości dla każdej zmiennej w problemie; dlatego

{\ Displaystyle t (v_ {i}) \ mapsto \ pusty zbiór

oznacza, że agent nie przypisał jeszcze

∅ {\ Displaystyle \ alpha (v_ {i})}

wartość do zmiennej

{\ displaystyle v_ {i}}

. Biorąc pod uwagę tę reprezentację, „ domena ” (czyli zbiór wartości wejściowych) funkcji f może być traktowana jako zbiór wszystkich możliwych kontekstów dla DCOP. Dlatego w dalszej części tego

funkcji

możemy użyć pojęcia kontekstu (tj.

)

jako danych wejściowych do .

Pełne przypisanie to przypisanie, w którym każde $pojawia$ dokładnie raz, to znaczy wszystkie zmienne są przypisane Jest również nazywany rozwiązaniem DCOP.

Optymalnym rozwiązaniem jest pełne przypisanie, w którym funkcja celu $jest$ od rodzaju problemu)

Przykładowe problemy

Różne problemy z różnych dziedzin można przedstawić jako DCOP.

Kolorowanie grafów rozłożonych

Problem $,$ wykresów następujący: $displaystyle n \ podzbiór N}$ wykres i kolorów $przypisz$ , ⊂ $,$ , kolor taki, że liczba sąsiednich wierzchołków o tym samym kolorze jest

Jako DCOP istnieje jeden agent na wierzchołek, który jest przypisany do decydowania o powiązanym kolorze. Każdy agent ma pojedynczą zmienną, której powiązana domena ma liczność ${\ displaystyle | C |}$ (dla każdego możliwego koloru istnieje jedna wartość domeny). Dla każdego wierzchołka ${\ Displaystyle n_ {i} \ równoważnik N}$ istnieje zmienna ${\ Displaystyle v_ {i} \ in V}$ z domeną re $D_ {i }=C}$ . $każdej$ pary sąsiednich wierzchołków kosztu 1 przypisany ten sam kolor:

{\ Displaystyle (\ forall c \ subseteq C: f (\ langle v_ {i}, c \ rangle, \ langle v_ {j}, c \ rangle) \ mapsto 1).}

Celem jest zatem zminimalizowanie

{\ Displaystyle \ eta (f)}

.

Rozproszony problem z wieloma plecakami

Rozłożony wariant wielokrotny problemu plecakowego jest następujący: biorąc pod uwagę zestaw przedmiotów o różnej objętości i zestaw plecaków o różnej pojemności, przypisz każdy przedmiot do plecaka tak, aby zminimalizować ilość przepełnienia. Niech $displaystyle I}$ $będzie$ będzie zbiorem przedmiotów, plecaków, $na$ elementy $ich$ i funkcją odwzorowującą plecaki na

${i}=K}$ problem jako DCOP, dla każdego zmienną z powiązaną domeną. $\$ $ja$ $i$ . Następnie dla wszystkich możliwych kontekstów ${\ displaystyle t}$ :

\ Displaystyle f (t) \ mapsto \ suma _ {k \ w K}{\begin{przypadki}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{inaczej}},\end{przypadki}} }

gdzie

{\ Displaystyle r (t, k)}

reprezentuje całkowitą wagę przypisaną przez kontekst do plecaka

{\ displaystyle t}

{\ displaystyle k}

:

{\ Displaystyle r (t, k) = \ suma _ {v_ {i} \ w t ^ {- 1} (k)} s (i).}

Rozproszony problem alokacji pozycji

alokacji pozycji jest następujący. Istnieje kilka elementów, które należy podzielić między kilku agentów. Każdy agent ma inną wycenę przedmiotów. Celem jest optymalizacja jakiegoś globalnego celu, takiego jak maksymalizacja sumy użyteczności lub minimalizacja zazdrości. Problem alokacji pozycji można sformułować jako DCOP w następujący sposób.

Dodaj zmienną binarną v _ij dla każdego agenta i oraz pozycji j . Wartość zmiennej wynosi „1”, jeśli agent otrzymuje przedmiot, a „0” w przeciwnym razie. Zmienna jest własnością agenta i .
Aby wyrazić ograniczenie, że każda pozycja jest przypisana co najwyżej jednemu agentowi, dodaj ograniczenia binarne dla każdych dwóch różnych zmiennych związanych z tym samym przedmiotem, z nieskończonym kosztem, jeśli dwie zmienne są jednocześnie „1”, i zerowym kosztem w przeciwnym razie.
Aby wyrazić ograniczenie, że wszystkie elementy muszą być przydzielone, dodaj n -ary ograniczenie dla każdego elementu (gdzie n jest liczbą agentów), z nieskończonym kosztem, jeśli żadna zmienna związana z tym elementem nie wynosi „1”.

Inne aplikacje

DCOP zastosowano do innych problemów, takich jak:

koordynacja czujników mobilnych;
planowanie spotkań i zadań.

Algorytmy

Algorytmy DCOP można podzielić na kilka sposobów:

Kompletność - kompletne algorytmy przeszukiwania znajdujące optymalne rozwiązanie, a lokalne algorytmy przeszukiwania znajdujące lokalne optimum .
Strategia wyszukiwania - wyszukiwanie w pierwszej kolejności lub przeszukiwanie gałęzi i granic w pierwszej kolejności;
Synchronizacja między agentami - synchroniczna lub asynchroniczna;
Komunikacja między agentami - punkt-punkt z sąsiadami w grafie ograniczeń lub rozgłaszanie;
Topologia komunikacji - łańcuch lub drzewo.

ADOPT, na przykład, wykorzystuje wyszukiwanie najlepsze jako pierwsze, synchronizację asynchroniczną, komunikację punkt-punkt między sąsiednimi agentami na grafie ograniczeń i drzewo ograniczeń jako główną topologię komunikacji.

Nazwa algorytmu	Rok wprowadzenia	Złożoność pamięci	Liczba wiadomości	Poprawność (informatyka) / Kompletność (logika)	Implementacje
ABT ^{[ potrzebne źródło ]} Asynchroniczne śledzenie wsteczne	1992	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: zamówienie statyczne, kompletne	^{[ potrzebne źródło ]}
AWC ^{[ potrzebne źródło ]} Asynchroniczne słabe zaangażowanie	1994	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: zmiana kolejności, szybka, kompletna (tylko z wykładniczą przestrzenią)	^{[ potrzebne źródło ]}
Rozproszony algorytm przerwania DBA	1995	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: niekompletne, ale szybkie	FRODO wersja 1 ^{[ stały martwy link ]}
SyncBB Oddział synchroniczny i związany	1997	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Kompletny, ale powolny
IDB Iteracyjne rozproszone wyłamanie	1997	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: niekompletne, ale szybkie
AAS ^{[ potrzebne źródło ]} Asynchroniczne wyszukiwanie agregacji	2000	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	agregacja wartości w ABT	^{[ potrzebne źródło ]}
DFC ^{[ potrzebne źródło ]} Rozproszone łańcuchowanie do przodu	2000	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: niska, porównywalna z ABT	^{[ potrzebne źródło ]}
ABTR ^{[ potrzebne źródło ]} Asynchroniczne wycofywanie ze zmianą kolejności	2001	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: zmiana kolejności w ABT z ograniczonymi nogoods	^{[ potrzebne źródło ]}
DMAC ^{[ potrzebne źródło ]} Utrzymywanie spójności asynchronicznie	2001	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: najszybszy algorytm	^{[ potrzebne źródło ]}
Bezpieczne obliczenia z częściowo zaufanymi serwerami ^{[ potrzebne źródło ]}	2002	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: bezpieczeństwo wzrasta wraz z liczbą zaufanych serwerów	^{[ potrzebne źródło ]}
Bezpieczne obliczenia wielostronne do rozwiązywania problemów DisCSP (MPC-DisCSP1-MPC-DisCSP4) ^{[ potrzebne źródło ]}	2003	^{[ potrzebne źródło ]}	^{[ potrzebne źródło ]}	Uwaga: bezpieczne, jeśli 1/2 uczestników jest godna zaufania	^{[ potrzebne źródło ]}
Zastosuj asynchroniczne śledzenie wsteczne	2003	Wielomian (lub dowolna przestrzeń)	Wykładniczy	Udowodniony	Implementacja referencyjna: Adopt DCOPolis ( GNU LGPL ) FRODO ( GNU Affero GPL )
OptAPO Asynchroniczna nakładka częściowa	2004	Wielomian	Wykładniczy	Udowodnione, ale dowód kompletności został zakwestionowany	Implementacja referencyjna: „OptAPO” . Centrum Sztucznej Inteligencji . SRI Międzynarodowy . Zarchiwizowane od oryginału w dniu 15.07.2007 . DCOPolis ( GNU LGPL ); w rozwoju
Procedura optymalizacji rozproszonego pseudodrzewa DPOP	2005	Wykładniczy	Liniowy	Udowodniony	Implementacja referencyjna: FRODO ( GNU Affero GPL ) DCOPolis ( GNU LGPL )
Oddział bez zobowiązań NCBB i związany	2006	Wielomian (lub dowolna przestrzeń)	Wykładniczy	Udowodniony	Implementacja referencyjna: niepubliczna DCOPolis ( GNU LGPL )
Nauka bez komunikacji CFL	2013	Liniowy	Brak Uwaga: żadne komunikaty nie są wysyłane, ale zakłada się wiedzę o spełnieniu ograniczenia lokalnego	Niekompletny

Istnieją również hybrydy tych algorytmów DCOP. BnB-Adopt, na przykład, zmienia strategię wyszukiwania Adopt z wyszukiwania najlepszego najpierw na przeszukiwanie gałęzi i ograniczeń w pierwszej kolejności.

Asymetryczny DCOP

Asymetryczny DCOP jest rozszerzeniem DCOP, w którym koszt każdego ograniczenia może być różny dla różnych agentów. Niektóre przykładowe aplikacje to:

Planowanie wydarzeń : agenci, którzy biorą udział w tym samym wydarzeniu, mogą czerpać z niego różne wartości.
Inteligentna sieć : wzrost ceny energii elektrycznej w godzinach obciążenia może być różny.

Jednym ze sposobów przedstawienia ADCOP jest przedstawienie ograniczeń jako funkcji:

\ Displaystyle f_ {C}: D_ {1} \ razy \ kropki \ razy D_ {k} \ do \ mathbb {R} ^ {k}}

Tutaj dla każdego ograniczenia nie jest pojedynczy koszt, ale wektor kosztów - jeden dla każdego agenta zaangażowanego w ograniczenie. Wektor kosztów ma długość k , jeśli każda zmienna należy do innego agenta; jeśli dwie lub więcej zmiennych należy do tego samego agenta, to wektor kosztów jest krótszy - istnieje jeden koszt dla każdego zaangażowanego agenta , a nie dla każdej zmiennej.

Podejścia do rozwiązywania ADCOP

Prostym sposobem rozwiązania ADCOP jest zastąpienie każdego ograniczenia ${\ Displaystyle f_ {C}: D_ {1} \ razy \ cdots \ razy D_ {k} \ do \ mathbb {R} ^ {k}}$ z ograniczeniem ${\ Displaystyle f_ {C} ': D_ {1} \ razy \ cdots \ razy D_ {k} \ do \mathbb {R}}$ , co jest równe sumie funkcji $\ Displaystyle f_ {C} ^ {1} + \ cdots + f_ {C} ^ {k}}$ . Jednak to rozwiązanie wymaga od agentów ujawnienia ich funkcji kosztów. Często nie jest to pożądane ze względu na względy prywatności.

Inne podejście nosi nazwę Zdarzenia prywatne jako zmienne (PEAV). W tym podejściu każda zmienna posiada, oprócz własnych zmiennych, również „zmienne lustrzane” wszystkich zmiennych należących do jej sąsiadów w sieci ograniczeń. Istnieją dodatkowe ograniczenia (o koszcie nieskończoności), które gwarantują, że zmienne lustrzane są równe zmiennym oryginalnym. Wadą tej metody jest to, że liczba zmiennych i ograniczeń jest znacznie większa niż w oryginale, co prowadzi do dłuższego czasu wykonywania.

Trzecie podejście polega na dostosowaniu istniejących algorytmów, opracowanych dla DCOP, do struktury ADCOP. Dokonano tego zarówno dla algorytmów wyszukiwania pełnego, jak i algorytmów wyszukiwania lokalnego.

Porównanie z grami strategicznymi

Struktura problemu ADCOP jest podobna do teoretycznej koncepcji gry symultanicznej . W obu przypadkach istnieją agenci, którzy kontrolują zmienne (w teorii gier zmiennymi są możliwe działania lub strategie agentów). W obu przypadkach każdy wybór zmiennych przez różnych agentów skutkuje inną wypłatą dla każdego agenta. Jest jednak zasadnicza różnica:

W grze symultanicznej agenci są samolubni – każdy z nich chce zmaksymalizować własną użyteczność (lub zminimalizować własny koszt). Dlatego najlepszym rezultatem, do którego można dążyć w takich warunkach, jest równowaga — sytuacja, w której żaden podmiot nie może jednostronnie zwiększyć własnego zysku.
W ADCOP agenci są uważani za współpracujących: działają zgodnie z protokołem, nawet jeśli zmniejsza to ich użyteczność. Dlatego cel jest trudniejszy: chcielibyśmy zmaksymalizować sumę użyteczności (lub zminimalizować sumę kosztów). Równowaga Nasha odpowiada z grubsza lokalnemu optimum tego problemu, podczas gdy my szukamy optimum globalnego.

Częściowa współpraca

Istnieją pewne modele pośrednie, w których agenci są częściowo skłonni do współpracy : są gotowi zmniejszyć swoją użyteczność, aby pomóc globalnemu celowi, ale tylko wtedy, gdy ich własny koszt nie jest zbyt wysoki. Przykładem agentów częściowo współpracujących są pracownicy firmy. Z jednej strony każdy pracownik chce zmaksymalizować własną użyteczność; z drugiej strony chcą również przyczynić się do sukcesu firmy. Dlatego chętnie pomagają innym lub zajmują się innymi czasochłonnymi zadaniami, które pomagają firmie, o ile nie jest to dla nich zbyt uciążliwe. Niektóre modele dla agentów częściowo współpracujących to:

Gwarantowana korzyść osobista : agenci zgadzają się działać dla dobra globalnego, jeśli ich własna użyteczność jest co najmniej tak wysoka, jak w warunkach niewspółpracujących (tj. ostatecznym rezultatem musi być poprawa Pareto stanu pierwotnego).
Lambda-współpraca : istnieje parametr ${\ Displaystyle \ lambda \ w [0,1]}$ . Agenci $się działać dla globalnego$ użyteczność jest co najmniej tak wysoka jak razy ich użyteczność niewspółpracująca

Rozwiązanie takich ADCOP z częściową współpracą wymaga adaptacji algorytmów ADCOP.

Zobacz też

Uwagi i odniesienia

^ „ ${\ displaystyle \ razy}$ ” lub „×” oznacza iloczyn kartezjański .
Bibliografia _ Meisels, Amnon; Zivan, Roie (2016-03-01). „Rozproszona minimalizacja zazdrości dla alokacji zasobów” . Autonomiczne agenty i systemy wieloagentowe . 30 (2): 364–402. doi : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .
^ ^b ^; Yeoh, William Felner, Ariel; Koenig, Sven (2008), „BnB-ADOPT: asynchroniczny algorytm DCOP z rozgałęzieniem i powiązaniem” , Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems , tom. 2, s. 591–8, ISBN 9780981738116
Bibliografia _ Yokoo, Makoto (1997). Smołka, Gert (red.). „Rozproszony problem spełnienia częściowych ograniczeń” . Zasady i praktyka programowania z ograniczeniami — CP97 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 1330 : 222–236. doi : 10.1007/BFb0017442 . ISBN 978-3-540-69642-1 .
^ Pierwotnie opublikowana wersja Adopt była niedoinformowana, patrz Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), „Asynchroniczna kompletna metoda optymalizacji rozproszonych ograniczeń” (PDF) , Materiały z drugiej międzynarodowej wspólnej konferencji na temat autonomicznych agentów i systemów wieloagentowych , ACM Press, s. 161–168 . Oryginalna wersja Adopt została później rozszerzona, aby uzyskać informacje, to znaczy wykorzystać szacunki kosztów rozwiązania, aby skoncentrować się na wyszukiwaniu i działać szybciej, patrz Ali, Syed; Koenig, Sven; Tambe, Milind (2005), „Techniki przetwarzania wstępnego dla przyspieszenia algorytmu DCOP ADOPT” (PDF) , Materiały z czwartej międzynarodowej wspólnej konferencji na temat autonomicznych agentów i systemów wieloagentowych , ACM Press, s. 1041–8, doi : 10.1145/1082473.1082631 , ISBN 1595930930 , S2CID 10882572 . To rozszerzenie Adopt jest zwykle używane jako referencyjna implementacja Adopt.
Bibliografia _ Matsuo, Hiroshi; Iwata, Akira (luty 2005), „Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm” (PDF) , Proceedings of Artificial Intelligence and Applications , s. 727–732, CiteSeerX 10.1.1.408.7230
Bibliografia _ Lesser, Victor (2004), „Solving Distributed Constraint Optimization Problems using Cooperative Mediation” (PDF) , Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems , IEEE Computer Society , s. 438–445, ISBN 1581138644
Bibliografia _ Zazon, Mosze; Binsztok, Maksym; Meisels, Amnon (2007), „Problem zakończenia algorytmu APO” (PDF) , Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning , s. 117–124
Bibliografia _ Faltings, Boi (sierpień 2005), „DPOP: A Scalable Method for Multiagent Constraint Optimization” , Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, Edynburg, Szkocja, s. 266-271
^ Czeczetka, Anton; Sycara, Katia (maj 2006), „No-Commitment Branch and Bound Search for Distributed Constraint Optimization” (PDF) , Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems , s. 1427–9, doi : 10.1145/1160633.1160900 , ISBN 1595933034 , S2CID 43918609
^ Czeczetka, Anton; Sycara, Katia (marzec 2006), „An Any-space Algorithm for Distributed Constraint Optimization” (PDF) , Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management
Bibliografia _ Leith, DJ (sierpień 2013), „Decentralized Constraint Satisfaction”, IEEE / ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103,3240 , doi : 10.1109/TNET.2012.2222923 , S2CID 11504393
^ ^a ^b ^c Grinshpoun, T .; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A. (2013-07-30). „Problemy optymalizacji asymetrycznych rozproszonych ograniczeń” . Dziennik badań nad sztuczną inteligencją . 47 : 613–647. doi : 10.1613/jair.3945 . ISSN 1076-9757 .
^ Greenstadt, Rachel; Pearce, Jonathan P.; Tambe, Milind (2006-07-16). „Analiza utraty prywatności w rozproszonej optymalizacji ograniczeń” . Materiały z 21. Krajowej Konferencji Sztucznej Inteligencji - Tom 1 . AAAI'06. Boston, Massachusetts: AAAI Press: 647–653. ISBN 978-1-57735-281-5 .
^ Maheswaran, Rajiv T.; Pearce, Jonathan P.; Bowring, Emma; Varakantham, Pradeep; Tambe, Milind (2006-07-01). „Utrata prywatności w rozproszonym rozumowaniu z ograniczeniami: ilościowe ramy analizy i jej zastosowań” . Autonomiczne agenty i systemy wieloagentowe . 13 (1): 27–60. doi : 10.1007/s10458-006-5951-y . ISSN 1573-7454 . S2CID 16962945 .
Bibliografia _ Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (red.). „Bezpieczna rozproszona satysfakcja z ograniczeń: osiągnięcie porozumienia bez ujawniania prywatnych informacji” . Zasady i praktyka programowania z ograniczeniami - CP 2002 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 2470 : 387–401. doi : 10.1007/3-540-46135-3_26 . ISBN 978-3-540-46135-7 .
^ Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, Pradeep Varakantham (2004). „Przeniesienie DCOP do prawdziwego świata: wydajne kompletne rozwiązania do rozproszonego planowania wielu zdarzeń” . www.komputer.org . Źródło 2021-04-12 . {{ cite web }} : CS1 maint: wiele nazw: lista autorów ( link )
^ ^ab ^Zivan , Roie; Grubshtein, Alon; Friedmann, Michał; Meisels, Amnon (2012-06-04). „Częściowa współpraca w wyszukiwaniu wieloagentowym” . Materiały z 11. Międzynarodowej Konferencji Agentów Autonomicznych i Systemów Multiagentowych - Tom 3 . AAMAS '12. Walencja, Hiszpania: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1268. ISBN 978-0-9817381-3-0 .

Książki i ankiety

Fioretto, Ferdinando; Pontelli, Enrico; Yeoh, William (2018), „Problemy i zastosowania optymalizacji rozproszonych ograniczeń: ankieta” , Journal of Artificial Intelligence Research , 61 : 623–698, arXiv : 1602,06347 , doi : 10,1613/jair.5565 , S2CID 4503761
Faltings, Boi (2006), „Distributed Constraint Programming” , w: Walsh, Toby (red.), Handbook of Constraint Programming , Elsevier , ISBN 978-0-444-52726-4 Rozdział w redagowanej książce.
Meisels, Amnon (2008), Distributed Search by Constrained Agents , Springer , ISBN 978-1-84800-040-7
Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations , Nowy Jork: Cambridge University Press , ISBN 978-0-521-89943-7 Patrz rozdziały 1 i 2; do pobrania za darmo w Internecie .
Yokoo, Makoto (2001), Rozproszone spełnienie ograniczeń: Podstawy współpracy w systemach wieloagentowych , Springer , ISBN 978-3-540-67596-9
Yokoo, M. Hirayama K. (2000), „Algorytmy dla rozproszonego spełniania ograniczeń: przegląd”, Autonomous Agents and Multiagent Systems , 3 (2): 185–207, doi : 10,1023 / A: 1010078712316 , S2CID 2139298

[1] „ ${\ displaystyle \ razy}$ ” lub „×” oznacza iloczyn kartezjański .

[:2-2] Bibliografia _ Meisels, Amnon; Zivan, Roie (2016-03-01). „Rozproszona minimalizacja zazdrości dla alokacji zasobów” . Autonomiczne agenty i systemy wieloagentowe . 30 (2): 364–402. doi : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .

[yeoh06-3] ; Yeoh, William Felner, Ariel; Koenig, Sven (2008), „BnB-ADOPT: asynchroniczny algorytm DCOP z rozgałęzieniem i powiązaniem” , Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems , tom. 2, s. 591–8, ISBN 9780981738116

[4] Bibliografia _ Yokoo, Makoto (1997). Smołka, Gert (red.). „Rozproszony problem spełnienia częściowych ograniczeń” . Zasady i praktyka programowania z ograniczeniami — CP97 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 1330 : 222–236. doi : 10.1007/BFb0017442 . ISBN 978-3-540-69642-1 .

[5] Pierwotnie opublikowana wersja Adopt była niedoinformowana, patrz Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), „Asynchroniczna kompletna metoda optymalizacji rozproszonych ograniczeń” (PDF) , Materiały z drugiej międzynarodowej wspólnej konferencji na temat autonomicznych agentów i systemów wieloagentowych , ACM Press, s. 161–168 . Oryginalna wersja Adopt została później rozszerzona, aby uzyskać informacje, to znaczy wykorzystać szacunki kosztów rozwiązania, aby skoncentrować się na wyszukiwaniu i działać szybciej, patrz Ali, Syed; Koenig, Sven; Tambe, Milind (2005), „Techniki przetwarzania wstępnego dla przyspieszenia algorytmu DCOP ADOPT” (PDF) , Materiały z czwartej międzynarodowej wspólnej konferencji na temat autonomicznych agentów i systemów wieloagentowych , ACM Press, s. 1041–8, doi : 10.1145/1082473.1082631 , ISBN 1595930930 , S2CID 10882572 . To rozszerzenie Adopt jest zwykle używane jako referencyjna implementacja Adopt.

[matsui05efficient-6] Bibliografia _ Matsuo, Hiroshi; Iwata, Akira (luty 2005), „Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm” (PDF) , Proceedings of Artificial Intelligence and Applications , s. 727–732, CiteSeerX 10.1.1.408.7230

[mailler04solving-7] Bibliografia _ Lesser, Victor (2004), „Solving Distributed Constraint Optimization Problems using Cooperative Mediation” (PDF) , Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems , IEEE Computer Society , s. 438–445, ISBN 1581138644

[dcr07proceedings-8] Bibliografia _ Zazon, Mosze; Binsztok, Maksym; Meisels, Amnon (2007), „Problem zakończenia algorytmu APO” (PDF) , Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning , s. 117–124

[petcu04distributed-9] Bibliografia _ Faltings, Boi (sierpień 2005), „DPOP: A Scalable Method for Multiagent Constraint Optimization” , Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, Edynburg, Szkocja, s. 266-271

[chechetka06no-10] Czeczetka, Anton; Sycara, Katia (maj 2006), „No-Commitment Branch and Bound Search for Distributed Constraint Optimization” (PDF) , Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems , s. 1427–9, doi : 10.1145/1160633.1160900 , ISBN 1595933034 , S2CID 43918609

[chechetka06anyspace-11] Czeczetka, Anton; Sycara, Katia (marzec 2006), „An Any-space Algorithm for Distributed Constraint Optimization” (PDF) , Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management

[cfl-12] Bibliografia _ Leith, DJ (sierpień 2013), „Decentralized Constraint Satisfaction”, IEEE / ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103,3240 , doi : 10.1109/TNET.2012.2222923 , S2CID 11504393

[:0-13] Grinshpoun, T .; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A. (2013-07-30). „Problemy optymalizacji asymetrycznych rozproszonych ograniczeń” . Dziennik badań nad sztuczną inteligencją . 47 : 613–647. doi : 10.1613/jair.3945 . ISSN 1076-9757 .

[14] Greenstadt, Rachel; Pearce, Jonathan P.; Tambe, Milind (2006-07-16). „Analiza utraty prywatności w rozproszonej optymalizacji ograniczeń” . Materiały z 21. Krajowej Konferencji Sztucznej Inteligencji - Tom 1 . AAAI'06. Boston, Massachusetts: AAAI Press: 647–653. ISBN 978-1-57735-281-5 .

[15] Maheswaran, Rajiv T.; Pearce, Jonathan P.; Bowring, Emma; Varakantham, Pradeep; Tambe, Milind (2006-07-01). „Utrata prywatności w rozproszonym rozumowaniu z ograniczeniami: ilościowe ramy analizy i jej zastosowań” . Autonomiczne agenty i systemy wieloagentowe . 13 (1): 27–60. doi : 10.1007/s10458-006-5951-y . ISSN 1573-7454 . S2CID 16962945 .

[16] Bibliografia _ Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (red.). „Bezpieczna rozproszona satysfakcja z ograniczeń: osiągnięcie porozumienia bez ujawniania prywatnych informacji” . Zasady i praktyka programowania z ograniczeniami - CP 2002 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 2470 : 387–401. doi : 10.1007/3-540-46135-3_26 . ISBN 978-3-540-46135-7 .

[17] Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, Pradeep Varakantham (2004). „Przeniesienie DCOP do prawdziwego świata: wydajne kompletne rozwiązania do rozproszonego planowania wielu zdarzeń” . www.komputer.org . Źródło 2021-04-12 . {{ cite web }} : CS1 maint: wiele nazw: lista autorów ( link )

[:1-18] Zivan , Roie; Grubshtein, Alon; Friedmann, Michał; Meisels, Amnon (2012-06-04). „Częściowa współpraca w wyszukiwaniu wieloagentowym” . Materiały z 11. Międzynarodowej Konferencji Agentów Autonomicznych i Systemów Multiagentowych - Tom 3 . AAMAS '12. Walencja, Hiszpania: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1268. ISBN 978-0-9817381-3-0 .