Optimalizace distribuovaných omezení - Distributed constraint optimization

Optimalizace distribuovaných omezení (DCOP nebo DisCOP) je distribuováno analogicky k optimalizace omezení. DCOP je problém, při kterém skupina agentů musí distribuovaně volit hodnoty pro sadu proměnných tak, aby byla minimalizována cena sady omezení přes proměnné.

Distributed Constraint Satisfaction je rámec pro popis problému z hlediska omezení, která jsou známá a vynucená různými účastníky (agenty). Omezení jsou popsána u některých proměnných s předdefinovanými doménami a různým agentům musí být přiřazena ke stejným hodnotám.

Problémy definované v tomto rámci lze vyřešit kterýmkoli z algoritmů, které jsou pro něj navrženy.

Rámec byl používán pod různými názvy v 80. letech. První známé použití se současným názvem je v roce 1990.^{[Citace je zapotřebí ]}

Definice

DCOP

A DCOP lze definovat jako a n-tice ${displaystyle langle A, V, {mathfrak {D}}, f, alfa, eta úhel}$, kde:

• ${displaystyle A}$ je soubor z agenti;
• ${displaystyle V}$ je sada proměnných, ${displaystyle {v_ {1}, v_ {2}, cdots, v_ {| V |}}}$;
• ${displaystyle {mathfrak {D}}}$ je sada domén, ${displaystyle {D_ {1}, D_ {2}, ldots, D_ {| V |}}}$, kde každý ${displaystyle Din {mathfrak {D}}}$ je konečná množina obsahující hodnoty, ke kterým lze přiřadit přidruženou proměnnou;
• ${displaystyle f}$ je funkce^[1][2]${displaystyle f: igcup _ {Sin {mathfrak {P}} (V)} součet {v_ {i} v S} vlevo ({v_ {i}} je D_ {i} ight) ightarrow mathbb {N} pohár {infty }}$který mapuje každé možné přiřazení proměnné k ceně. Tuto funkci lze také považovat za definování omezení mezi proměnnými, avšak proměnné nesmí být Hermitian;
• ${displaystyle alpha}$ je funkce ${displaystyle alpha: Vightarrow A}$ mapování proměnných na jejich přidruženého agenta. ${displaystyle alpha (v_ {i}) mapa pro a_ {j}}$ znamená, že jde o agenta ${displaystyle a_ {j}}$Odpovědnost za přiřazení hodnoty proměnné ${displaystyle v_ {i}}$. Všimněte si, že to nemusí být nutně pravda ${displaystyle alpha}$ je buď injekce nebo surjection; a
• ${displaystyle eta}$ je operátor který agreguje všechny jednotlivce ${displaystyle f}$ náklady na všechna možná přiřazení proměnných. Toho se obvykle dosahuje součtem:${displaystyle eta (f) mapsto sum _ {sin igcup _ {Sin {mathfrak {P}} (V)} sum {v_ {i} in S} left ({v_ {i}} imes D_ {i} ight)} f (s)}$.

Cílem DCOP je nechat každého agenta přiřadit hodnoty jeho přidruženým proměnným, aby se buď minimalizovalo, nebo maximalizovalo ${displaystyle eta (f)}$ pro dané přiřazení proměnných.

Kontext

A kontext je přiřazení proměnné pro DCOP. Lze to považovat za funkci mapující proměnné v DCOP na jejich aktuální hodnoty:

${displaystyle t: Vightarrow (Din {mathfrak {D}}) cup {emptyset}.}$

Všimněte si, že kontext je v podstatě částečné řešení a nemusí obsahovat hodnoty pro každý proměnná v problému; proto, ${displaystyle t (v_ {i}) mapsto emptyset}$ znamená, že agent ${displaystyle alpha (v_ {i})}$ dosud nepřiřadil hodnotu proměnné ${displaystyle v_ {i}}$. Vzhledem k tomuto zastoupenídoména " (tj., sada vstupních hodnot) funkce F lze považovat za soubor všech možných kontextů pro DCOP. Proto ve zbývající části tohoto článku můžeme použít pojem kontext (tj., ${displaystyle t}$ funkce) jako vstup do ${displaystyle f}$ funkce.

Ukázkové problémy

Distribuované zbarvení grafu

The zbarvení grafu problém je následující: daný a graf ${displaystyle G = langle N, Eangle}$ a sada barev ${displaystyle C}$, přiřadit každý vrchol, ${displaystyle nsubset N}$, barva, ${displaystyle cleq C}$, takže je minimalizován počet sousedních vrcholů se stejnou barvou.

Jako DCOP existuje jeden agent na vrchol, který je přiřazen k rozhodnutí o přidružené barvě. Každý agent má jednu proměnnou, jejíž přidružená doména je mohutnost ${displaystyle | C |}$ (pro každou možnou barvu existuje jedna hodnota domény). Pro každý vrchol ${displaystyle n_ {i} leq N}$, vytvořte proměnnou v DCOP ${displaystyle v_ {i} ve V}$ s doménou ${displaystyle D_ {i} = C}$. Pro každou dvojici sousedních vrcholů ${displaystyle langle n_ {i}, n_ {j} úhel v E}$, vytvořte omezení ceny 1, pokud mají obě přidružené proměnné přiřazenu stejnou barvu:

${displaystyle (forall csubseteq C: f (langle v_ {i}, cangle, langle v_ {j}, cangle) mapsto 1).}$

Cílem tedy je minimalizovat ${displaystyle eta (f)}$.

Distribuovaný problém s více batohy

The distribuováno více varianta batoh problém je následující: vzhledem k sadě položek s různým objemem a sadě batohů s různou kapacitou přiřaďte každou položku k batohu tak, aby bylo minimalizováno množství přetečení. Nechat ${displaystyle I}$ být souborem položek, ${displaystyle K}$ být sadou batohů, ${displaystyle s: Iightarrow mathbb {N}}$ být funkcí mapující položky na jejich objem a ${displaystyle c: Kightarrow mathbb {N}}$ být funkcí mapující batohy na jejich kapacitu.

Chcete-li tento problém kódovat jako DCOP, pro každou z nich ${displaystyle iin I}$ vytvořit jednu proměnnou ${displaystyle v_ {i} ve V}$ s přidruženou doménou ${displaystyle D_ {i} = K}$. Pak pro všechny možné kontexty ${displaystyle t}$:

${displaystyle f (t) mapsto sum _ {kin K} {egin {cases} 0 & r (t, k) leq c (k), r (t, k) -c (k) & {ext {jinak}}, konec {případů}}}$

kde ${displaystyle r (t, k)}$ je funkce taková, že

${displaystyle r (t, k) = součet _ {v_ {i} v t ^ {- 1} (k)} s (i).}$

Algoritmy

Algoritmy DCOP lze klasifikovat podle vyhledávací strategie (nejlepší vyhledávání první nebo hloubkové vyhledávání větví a vazeb), synchronizace mezi agenty (synchronní nebo asynchronní), komunikace mezi agenty (bod-bod se sousedy v graf omezení nebo vysílání) a hlavní topologie komunikace (řetězec nebo strom).^[3]Například ADOPT používá jako první topologii vyhledávání vyhledávání podle první, asynchronní synchronizaci, komunikaci mezi dvěma sousedními agenty v grafu omezení a strom omezení.

Hybridy těchto DCOP algoritmů také existují. BnB - přijmout,^[3] například změní vyhledávací strategii aplikace Adopt z nejlepšího prvního vyhledávání do hloubkového prvního větveného a vázaného vyhledávání.

Viz také

• Problém spokojenosti s omezením

Poznámky a odkazy

Knihy a průzkumy

• Fioretto, Ferdinando; Pontelli, Enrico; Yeoh, William (2018), „Problémy a aplikace s optimalizací distribuovaných omezení: průzkum“, Journal of Artificial Intelligence Research, 61: 623–698, arXiv:1602.06347, doi:10.1613 / jair.5565
• Faltings, Boi (2006), „Programování distribuovaných omezení“, ve Walsh, Toby (ed.), Příručka programování omezení, Elsevier, ISBN  978-0-444-52726-4 Kapitola v upravené knize.
• Meisels, Amnon (2008), Distribuované vyhledávání omezenými agenty, Springer, ISBN  978-1-84800-040-7
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagentní systémy: Algoritmické, herně teoretické a logické základy, New York: Cambridge University Press, ISBN  978-0-521-89943-7 Viz kapitoly 1 a 2; ke stažení zdarma online.
• Yokoo, Makoto (2001), Spokojenost s distribuovaným omezením: Základy spolupráce v systémech s více agenty, Springer, ISBN  978-3-540-67596-9
• Yokoo, M. a Hirayama, K. (2000). Algoritmy pro uspokojení distribuovaných omezení: Přehled. Sborník z mezinárodní společné konference o autonomních agentech a multiagentních systémech (str. 185–207). Průzkum.