분산 제약 조건 최적화

분산 구속조건 최적화(DCOP 또는 DisCOP)는 분산 아날로그-제약조건 최적화다.DCOP는 에이전트 그룹이 변수 집합에 대한 값을 분산 선택해야만 변수에 대한 제약 조건 집합의 비용을 최소화할 수 있는 문제다.null

분산된 제약조건 만족도는 고유한 참여자(대리점)에 의해 알려지고 시행되는 제약조건의 측면에서 문제를 기술하기 위한 프레임워크다.제약조건은 도메인이 미리 정의된 일부 변수에 설명되며, 서로 다른 에이전트에 의해 동일한 값에 할당되어야 한다.null

이 프레임워크로 정의된 문제들은 그것을 위해 설계된 알고리즘에 의해 해결될 수 있다.null

이 틀은 1980년대에 다른 이름으로 사용되었다.현재 이름으로 처음 알려진 용어는 1990년이다.^{[citation needed]}null

정의들

디코프

DCOP 문제의 주요 성분은 에이전트와 변수다.중요한 것은 각 변수는 에이전트에 의해 소유된다는 것이다. 이것이 문제를 분산시키는 것이다.정식으로 DCOP는 튜플 $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ A $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ , $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ , D $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ , $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ , $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ , $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ α , $⟩$ {\ $displaystyle$ \ $langle A,V,{\mathfrak {D},$ f,\ $alpha$ ,\ $etarangle }$ 이다 $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ 여기서:

$A$ 은 $A$ (는) $\{a_{1},\dots ,a_{|A|}\}$ 집합으로 $\{a_{1},\dots ,a_{|A|}\}$ { $\{a_{1},\dots ,a_{|A|}\}$ 1 $\{a_{1},\dots ,a_{|A|}\}$ , $\{a_{1},\dots ,a_{|A|}\}$ $\{a_{1},\dots ,a_{|A|}\}$ $\{a_{1},\dots ,a_{|A|}\}$ $\{a_{1},\dots,a_{A}\}}}}$ 입니다 $\{a_{1},\dots ,a_{|A|}\}$
$V$ $V$ 은 $V$ (는) 변수 집합으로 $\{v_{1},v_{2},\dots ,v_{|V|}\}$ { $\{v_{1},v_{2},\dots ,v_{|V|}\}$ $\{v_{1},v_{2},\dots ,v_{|V|}\}$ , $\{v_{1},v_{2},\dots ,v_{|V|}\}$ $\{v_{1},v_{2},\dots ,v_{|V|}\}$ , $\{v_{1},v_{2},\dots ,v_{|V|}\}$ $\{v_{1},v_{2},\dots ,v_{|V|}\}$ $\{v_{1},v_{2},\dots ,v_{|V|}\}$ ${\displaystyle \{v_{1},v_{2},\dots,v_{{V$
${\mathfrak {D}}$ is the set of variable-domains, $\{D_{1},D_{2},\dots ,D_{ V }\}$ , where each $D_{j}\in {\mathfrak {D}}$ is a finite set containing the possible values of variable $v_{j}$ .
- $D_{j}\in {\mathfrak {D}}$ $D_{j}\in {\mathfrak {D}}$ math D ${\$ 에 두 값(예: 0 또는 1)만 포함된 경우 $D_{j}\in {\mathfrak {D}}$ $v_{j}$ $v_{j}$ ${\$ 을 $v_{j}$ 이진 변수라고 한다.
$[\displaystyle f}$ 는 $f$ 비용 함수다.그것은^[1] 함수다.
$f:\bigcup _{S\subseteq V}\time _{v_{j}\in S}D_{j}\to \mathb {R}}}}}$
$f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R}$
모든 가능한 부분 배정을 비용에 매핑할 수 있다.일반적으로 $f$ $f$ 의 값이 0이 아닌 값만 $f$ 0이 아닌 값으로 할당되는 튜플의 목록으로 표시된다.그러한 각각의 튜플을 제약조건이라고 부른다.이 세트의 $C$ 각 $제약조건$ C $C$ 은(는) $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ : D $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ k $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ → $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ ${\$ $D_{1}\time \cdots \time D_{k}\\mathb {R}에 변수$ 할당 가능한 각 할당에 실제 값을 할당함 $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ .몇 가지 특별한 종류의 제약조건은 다음과 같다.
- 단항 제약 조건 - 단일 변수에 대한 제약 조건, 즉 $f_{C}:D_{j}\to \mathbb {R}$ $f_{C}:D_{j}\to \mathbb {R}$ : $f_{C}:D_{j}\to \mathbb {R}$ $f_{C}:D_{j}\to \mathbb {R}$ → R ${\$ $v_{j}\in V$ $v_{j}\in V$ $v_{j}\in V$ $v_{j}\in V$ V ${\displaystyle v_{j}\in V$ 에 대한 $f_{C}:D_{j}\to \mathbb {R}$ $D_{j}\to \mathb {R}.$
- 이항 제약 조건 - 두 변수의 제약 조건, $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ : $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ j $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ × $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ 2 $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ → R {\ $displaystyle$ f_ ${C}:$ $일부$ $v_{j_{1}},v_{j_{2}}\in V$ $v_{j_{1}},v_{j_{2}}\in V$ $v_{j_{1}},v_{j_{2}}\in V$ , $v_{j_{1}},v_{j_{2}}\in V$ j $v_{j_{1}},v_{j_{2}}\in V$ $v_{j_{1}},v_{j_{2}}\in V$ V ${\displaystyle v_{j_{1},v_{j_{$ 1},{j_{ $2}}\$ in V $v_{j_{1}},v_{j_{2}}\in V$ 에 $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ $대해$ D_{ $1}\time D_{j_{$ 2}}\ $mathb {R}}\to$ .
$\alpha$ $\alpha$ 은 $\alpha$ (는) 소유함수다.각 변수를 연결된 에이전트에 매핑하는 $\alpha :V\to A$ 함수 $\alpha :V\to A$ : $\alpha :V\to A$ → $\alpha :V\to A$ $\alpha :V\to A$ 이다. $\alpha (v_{j})\mapsto a_{i}$ j $\alpha (v_{j})\mapsto a_{i}$ $\alpha (v_{j})\mapsto a_{i}$ $\alpha (v_{j})\mapsto a_{i}$ ${\$ \ \( $v_{j})\mapsto a_$ ${$ $i$ $}}}$ 은(는) $a_{i}$ $v_{j}$ j {\ $displaystyle$ $v_{$ $}}}}$ 을( $v_{j}$ 를) 의미한다 $\alpha (v_{j})\mapsto a_{i}$ $a_{i}$ 이는 변수 $v_{j}$ 의 값을 할당하는 것이 에이전트 i {\ $displaystyle$ a_ $}$ 의 책임임을 $의미$ 한다. α {\displaystyle $v_{j}.$ $\alpha$ $\alpha}}$ 은(는) 주입이 $\alpha$ 아니므로, 즉, 한 에이전트가 둘 이상의 변수를 소유할 수 있다.그것은 또한 반드시 추론인 것은 아니다. 즉, 일부 대리인은 변수를 소유하지 않을 수도 있다.
$\eta$ $\eta$ 이 $\eta$ (가) 목표 함수다.가능한 모든 변수 할당에 대해 개별 $f$ $f$ 비용을 $f$ 모두 집계하는 운영자다.이는 보통 합계를 통해 이루어진다. $\eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\time _{v_{j}\time _{v_{j}\s}}fs.$

DCOP의 목적은 주어진 변수 할당에 대해 $\eta (f)$ ( $\eta (f)$ ) $displaystyle \eta$ ( $f)}을($ 를) 최소화하거나 최대화하기 위해 각 에이전트가 관련 변수에 값을 할당하도록 하는 것이다.null

과제들

값 할당은 쌍 $(v_{j},d_{j})$ j $(v_{j},d_{j})$ , d $(v_{j},d_{j})$ ) $(v_{j},d_{j}}$ 이며, $d_{j}$ 서 $(v_{j},d_{j})$ d $d_{j}$ ${\$ 는 도메인 $d_{j}$ $D_{j}$ $D_{j}$ ${\$ 의 요소다 $D_{j}$

부분 할당은 각 $v_{j}$ $v_{j}$ ${\$ 가 최대 한 번에 나타나는 $v_{j}$ 값 할당 집합이다.문맥이라고도 한다.이는 DCOP의 함수 매핑 변수와 현재 값이라고 생각할 수 있다.

t:V\to(D\in {\mathfrak {D})\컵 \{\emptyset \}.

컨텍스트는 본질적으로 부분적인 해결책이며 문제의 모든

t(v_{i})\mapsto \emptyset

에 대한 값을 포함할 필요는 없으므로 t

t(v_{i})\mapsto \emptyset

v

t(v_{i})\mapsto \emptyset

)

t(v_{i})\mapsto \emptyset

t(v_{i})\mapsto \emptyset }}

은(는) 에이전트

\alpha (v_{i})

i )

\alpha (v_{i})

{\

displaystyalpha(v_{i}})

가 아직

v_{i}

v_{i}

에 값을 할당하지

\alpha (v_{i})

않았음을 암시한다

t(v_{i})\mapsto \emptyset

.

v_{i}

. 이 표현에 따라 함수의 "도메인"(즉, 입력 값 집합)이 표시된다.fDCOP에 대해 가능한 모든 컨텍스트의 집합으로 생각할 수 있다.따라서 이 글의 나머지 부분에서는 컨텍스트(

즉

, t

t

함수

t

) 개념을

f

f

함수에

f

대한 입력으로 사용할 수 있다.null

전체 할당은 각 $v_{j}$ $v_{j}$ ${\$ 가 정확히 한 번 나타나는 $v_{j}$ 할당, 즉 모든 변수가 할당되는 할당이다.그것은 DCOP에 대한 해결책이라고도 불린다.null

최적 솔루션은 목표 함수 $\eta (f)$ ( $\eta (f)$ ) $\eta (f)$ 이(가) 최적화(즉, 문제 유형에 따라 최대화 또는 최소화)되는 $\eta (f)$ 완전 할당이다.null

예시 문제

서로 다른 도메인의 다양한 문제들은 DCOP로 제시될 수 있다.null

분산 그래프 컬러링

The graph coloring problem is as follows: given a graph $G=\langle N,E\rangle$ and a set of colors $C$ , assign each vertex, $n\subset N$ , a color, $c\leq C$ , such that the number of adjacent vertices with the same color is minimized.null

DCOP로서, 관련 색상을 결정하기 위해 할당된 정점당 하나의 에이전트가 있다.각 에이전트는 연결된 도메인이 $|C|$ C $displaystyle$ C $|C|$ }인 단일 변수를 가지고 있다( $|C|$ 가능한 각 색상에 대해 하나의 도메인 값이 있음).For each vertex $n_{i}\leq N$ , there is a variable $v_{i}\in V$ with domain $D_{i}=C$ . For each pair of adjacent vertices $\langle n_{i},n_{j}\rangle \in E$ , there is a constraint of cost 1 if both관련 변수 중 동일한 색상이 할당됨:

{\displaystyle(\all c\subseteq C:f(\langle v_{i}c\angle ,\langle v_{j}c\rangle )\mapsto 1)}

그러면 목표는

\eta (f)

(

\eta (f)

)

\eta (f)

을(를) 최소화하는 것이다

\eta (f)

여러 개의 배낭 문제 분산

배낭 문제의 분산된 복수 변종은 다음과 같다: 다양한 부피의 항목 집합과 다양한 용량의 배낭 집합이 주어진다면, 오버플로의 양이 최소화되도록 각 항목을 배낭에 할당한다. $I$ $I$ 을(를) 항목 집합으로 $I$ 하고, $K$ $K$ 을 $K$ (를) 배낭 $s:I\to \mathbb {N}$ 으로 하며, s $s:I\to \mathbb {N}$ : $s:I\to \mathbb {N}$ → N ${\$ $I\to \mathb {N}은($ 는) 해당 볼륨에 대한 함수 매핑 항목이며 $s:I\to \mathbb {N}$ , $c:K\to \mathbb {N}$ : $c:K\to \mathbb {N}$ → N ${\$ 는) 용량에 대한 함수 매핑 배낭입니다 $c:K\to \mathbb {N}$ .null

이 문제를 DCOP로 인코딩하려면 $i\in I$ $i\in I$ $i\in I$ I $i\in I$ 에 대해 연관된 도메인 $D_{i}=K$ = $D_{i}=K$ $D_{i}=K$ 와 $v_{i}\in V$ 함께 $v_{i}\in V$ $v_{i}\in V$ $v_{i}\in V$ ${\displaystyle v_{i}\}\in$ V $}$ 에 변수 하나를 생성하십시오 $i\in I$ $D_{i}=K$ 그런 다음 가능한 $모든$ 컨텍스트 t ${\displaysty t$ {\displaystytytesticate t:

f(t)\mapsto \sum _{k\in K}{\begin}0&r(t,k)\leq c(k),\r(t,k)-c(k)&{otherwise}, end{case}}}}}}}

여기서

r(t,k)

(

r(t,k)

,

r(t,k)

)

r(t,k)

은(는) 컨텍스트

t

{\displaystyle

t

}

에서 배낭 k

{\displaysty

k

}

에

t

할당한 총 중량을 나타낸다

r(t,k)

k

r(t,k)=\sum _{v_{i}\in t^{-1}s(i).

분산 항목 할당 문제

품목 할당 문제는 다음과 같다.여러 대리점 사이에서 나눠야 할 항목이 몇 가지 있다.각 대리점마다 항목에 대한 평가가 다르다.공공요금의 합을 극대화하거나 부러움을 최소화하는 등 일부 글로벌 목표를 최적화하는 것이 목표다.품목 할당 문제는 다음과 같이 DCOP로 공식화할 수 있다.^[2]null

각 에이전트 i 및 항목 j에 대해 이진 변수 v를_ij 추가하십시오.에이전트가 항목을 가져오면 변수 값은 "1"이고, 그렇지 않으면 "0"이다.변수는 에이전트 i가 소유하고 있다.
각 항목이 최대 하나의 에이전트에 부여되는 제약조건을 표현하려면 동일한 항목과 관련된 서로 다른 두 변수 각각에 대해 2진수 제약조건을 추가하고, 두 변수가 동시에 "1"이면 무한비용, 그렇지 않으면 0원가를 추가한다.
모든 항목을 할당해야 하는 제약 조건을 표현하려면 각 항목(여기서 n은 에이전트 수)에 대해 n-arry 제약 조건을 추가하십시오(이 항목과 관련된 변수가 "1"이 아닐 경우 무한 비용).

기타 응용 프로그램

DCOP는 다음과 같은 다른 문제에 적용되었다.

모바일 센서 조정.
미팅 및 태스크 스케줄링.

알고리즘

DCOP 알고리즘은 다음과 같은 여러 가지 방법으로 분류할 수 있다.^[3]

완전성 - 최적의 솔루션을 찾는 완전한 검색 알고리즘과 로컬 검색 알고리즘의 로컬 최적 검색 알고리즘 비교.
검색 전략 - 최상의 첫 번째 검색 또는 깊이 우선 분기 및 바인딩된 검색
에이전트 간 동기화 - 동기식 또는 비동기식;
에이전트 간 통신 - 제약 조건 그래프 또는 브로드캐스트에서 이웃과 점 대 점
통신 토폴로지 - 체인 또는 트리.

예를 들어, INTICE는 가장 먼저 검색, 비동기 동기화, 제약 조건 그래프에 있는 인접 에이전트와 제약 조건 트리 사이의 포인트 투 포인트 통신을 주 통신 토폴로지로 사용한다.null

알고리즘 이름	소개된 해	메모리 복잡성	메시지 수	정확성(컴퓨터 과학)/ 완전성(로직)	구현
ABT^{[필요하다]} 비동기식 역추적	1992	^{[필요하다]}	^{[필요하다]}	참고: 정적 순서, 완료	^{[필요하다]}
AWC^{[필요하다]} 비동기 취약 커밋	1994	^{[필요하다]}	^{[필요하다]}	참고: 순서 변경, 빠름, 완료(지수 공간만 포함)	^{[필요하다]}
DBA 분산 브레이크아웃 알고리즘	1995	^{[필요하다]}	^{[필요하다]}	참고: 불완전하지만 빠름	FRODO 버전 1^{[영구적 데드링크]}
SyncBB^[4] 동기 분기 및 바운드	1997	^{[필요하다]}	^{[필요하다]}	완전하지만 느림
IDB 반복 분산 브레이크아웃	1997	^{[필요하다]}	^{[필요하다]}	참고: 불완전하지만 빠름
AAS^{[필요하다]} 비동기 집계 검색	2000	^{[필요하다]}	^{[필요하다]}	ABT의 값 집합	^{[필요하다]}
DFC^{[필요하다]} 분산 포워드 체인	2000	^{[필요하다]}	^{[필요하다]}	참고: 낮음, ABT와 유사함	^{[필요하다]}
ABTR^{[필요하다]} 재주문을 통한 비동기식 역추적	2001	^{[필요하다]}	^{[필요하다]}	참고: ABT에서 한정된 재화 없음으로 전자 주문	^{[필요하다]}
DMAC^{[필요하다]} 비동기식 구성성 유지	2001	^{[필요하다]}	^{[필요하다]}	참고: 가장 빠른 알고리즘	^{[필요하다]}
반신뢰 서버를 통한 안전한 계산^{[필요하다]}	2002	^{[필요하다]}	^{[필요하다]}	참고: 신뢰할 수 있는 서버의 수에 따라 보안이 향상됨	^{[필요하다]}
DISCSP 해결을 위한 시큐어 멀티파티 계산 (MPC-DisCSP1-MPC-DisCSP4)^{[citation needed]}	2003	^{[필요하다]}	^{[필요하다]}	참고: 참가자의 1/2이 신뢰할 수 있는 경우 안전하게 보호	^{[필요하다]}
채택하다 비동기식 역추적^[5]	2003	다항식(또는 모든 공간^[6])	지수적	검증된	참조 구현: 채택하다 디코폴리스(GNU LGPL) FRODO(GNU 아페로 GPL)
옵타포 비동기 부분 오버레이^[7]	2004	다항식	지수적	입증되었지만 완벽함을 증명하는 데 어려움이^[8] 있음	참조 구현: "OptAPO". Artificial Intelligence Center. SRI International. Archived from the original on 2007-07-15. DCOPLis(GNU LGPL); 개발 중
DPOP 분산 유사 트리 최적화 절차^[9]	2005	지수적	선형	검증된	참조 구현:FRODO(GNU 아페로 GPL) 디코폴리스(GNU LGPL)
NCBB 커밋되지 않은 분기 및 바인딩^[10]	2006	다항식(또는 모든 공간^[11])	지수적	검증된	참조 구현: 공개되지 않음 디코폴리스(GNU LGPL)
CFL 커뮤니케이션 없는 학습^[12]	2013	선형	없음: 메시지가 전송되지 않지만 로컬 제약 조건의 만족도에 대한 지식을 가정함	불완전

이러한 DCOP 알고리즘의 하이브리드도 존재한다.예를 들어 BnB-Adopt는 Attract의 검색 전략을 Best-first search에서 deep-first branch-and-bound search로 변경한다.^[3]null

비대칭 DCOP

비대칭 DCOP는 각 제약조건의 비용이 서로 다른 작용제에 대해 다를 수 있는 DCOP의 확장이다.응용 프로그램의 예는 다음과 같다.^[13]

이벤트 스케줄링: 동일한 이벤트에 참석하는 에이전트는 이벤트로부터 다른 값을 도출할 수 있다.
스마트 그리드: 적재 시간 내 전기 가격 상승은 서로 다른 요인이 될 수 있다.

ADCOP를 나타내는 한 가지 방법은 제약조건을 함수로 표현하는 것이다.

f_{C}:D_{1}\time \dots \time D_{k}\to \mathb {R}^{k}}}}}

여기서, 각각의 제약조건에 대해 하나의 비용이 아니라, 제약조건에 관련된 각 대리점마다 하나의 비용 벡터가 있다.비용 벡터는 각 변수가 다른 에이전트에 속할 경우 k 길이의 길이다. 두 개 이상의 변수가 동일한 에이전트에 속할 경우, 비용의 벡터는 더 짧아진다. 각 변수에 대해가 아니라 관련된 각 에이전트에 대해 단일 비용이 발생한다.null

ADCOP를 해결하기 위한 접근 방식

ADCOP를 해결하기 위한 간단한 방법은 각 제약조건 $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ : $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ × $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ k → $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ ${\$ 를 교체하는 것이다. $제약$ 조건 $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ : $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ × × $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ × × D k $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ → $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ ${\$ 이 있는 $\cdots \time D_{k}\c$ }}}} \mathb {R} ^{ $k}}}}}}$ 에 대한 제약 조건: $f_{C}^{1}+\cdots +f_{C}^{k}$ ${1}\time \cdots \time D_{k}\$ to $f_{C}^{1}+\cdots +f_{C}^{k}$ $mathb$ { $R$ $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ 에 대한 \cdots $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $\$ times D_ ${k}\mathb$ { $R}$ 의 함수 $f_{C}^{1}+\cdots +f_{C}^{k}$ 와 같으나 $,$ 이 $솔루션$ 은 $f_{C}^{1}+\cdots +f_{C}^{k}$ 에게 비용 함수를 공개하도록 요구한다 $f_{C}^{1}+\cdots +f_{C}^{k}$ 종종 프라이버시 고려사항 때문에 이것은 원하지 않는다.^[14]^[15]^[16]null

또 다른 접근방식은 변수로서의 개인 사건(PEAV)이라고 불린다.^[17]이 접근법에서, 각 변수는 자신의 변수 외에도 제약망에서 그의 이웃이 소유한 모든 변수의 "거울 변수"를 소유한다.거울 변수가 원래의 변수와 동일하다는 것을 보장하는 추가적인 제약 조건(무한도 비용)이 있다.이 방법의 단점은 변수와 제약조건이 원래보다 훨씬 많아 런타임이 높다는 것이다.null

세 번째 접근방식은 DCOP용으로 개발된 기존 알고리즘을 ADCOP 프레임워크에 적응시키는 것이다.이는 전체 검색 알고리즘과 로컬 검색 알고리즘 모두에 대해 수행되었다.^[13]null

전략 게임과 비교

ADCOP 문제의 구조는 동시 게임의 게임 이론적 개념과 유사하다.두 경우 모두 변수를 제어하는 에이전트가 있다(게임 이론에서 변수는 에이전트의 가능한 행동이나 전략이다).두 경우 모두 서로 다른 에이전트에 의한 변수의 각 선택은 각 에이전트에 대한 다른 보상으로 귀결된다.그러나 근본적인 차이점은 다음과 같다.^[13]

동시 게임에서 에이전트는 이기적이다. 즉, 각 에이전트는 자신의 효용성을 최대화(또는 자신의 비용을 최소화)하기를 원한다.따라서 이러한 상황에서 추구할 수 있는 최선의 결과는 균형이다. 즉 어떤 대리인도 일방적으로 자신의 이익을 늘릴 수 없는 상황이다.
ADCOP에서 대리인은 협조적인 것으로 간주된다. 대리인은 자신의 효용성을 감소시키더라도 프로토콜에 따라 행동한다.따라서, 목표는 더 어려운 것이다: 우리는 유틸리티의 합계를 최대화하기를 원한다(또는 비용 합계를 최소화한다).내시 균형은 대략 이 문제의 국소 최적화와 일치하지만, 우리는 전지구적 최적화를 찾고 있다.

부분협력

에이전트들이 부분적으로 협력하는 몇몇 중간 모델들이 있다: 그들은 글로벌 목표를 돕기 위해 그들의 효용을 기꺼이 줄이려고 하지만, 그들 자신의 비용이 너무 높지 않을 때만 그렇다.부분적인 협력 요원의 한 예는 회사의 직원들이다.한편으로, 각각의 직원들은 그들 자신의 효용을 극대화하기를 원하고, 다른 한편으로, 그들은 또한 회사의 성공에 기여하기를 원한다.따라서, 그들은 다른 사람들을 돕거나, 기업에게 너무 부담이 되지 않는 한, 기업에게 도움이 되는 몇 가지 다른 시간 소모적인 일을 기꺼이 할 것이다.부분 협력 에이전트의 일부 모델은 다음과 같다.^[18]

보장된 개인적 이익: 대리인은 자신의 효용이 최소한 비협조적 환경(즉, 최종 결과는 원래 상태의 파레토 개선이어야 한다)에서만큼 높은 경우 글로벌 선을 위해 행동하기로 동의한다.
람다-협력: 매개 변수 $\lambda \in [0,1]$ [ 0 $\lambda \in [0,1]$ $\lambda \in [0,1]$ $\lambda \in [0,1]$ $\lambda \in [0,1]$ 이(가) 있다 $\lambda \in [0,1]$ 에이전트는 자신의 효용이 적어도 $(1-\lambda )$ 비협조 효용의 ( $(1-\lambda )$ - $){\displaystyle (1-\lambda )}$ 만큼 $(1-\lambda )$ 높을 경우 글로벌 선을 위해 행동하기로 동의한다.

이러한 부분적 준비 ADCOP를 해결하려면 ADCOP 알고리즘의 조정이 필요하다.^[18]null

참고 항목

참고 및 참조

^ " $\times$ $[\displaystyle \times }$ $\times$ 또는 "×"는 데카르트 제품을 의미한다.
^ Netzer, Arnon; Meisels, Amnon; Zivan, Roie (2016-03-01). "Distributed envy minimization for resource allocation". Autonomous Agents and Multi-Agent Systems. 30 (2): 364–402. doi:10.1007/s10458-015-9291-7. ISSN 1387-2532. S2CID 13834856.
^ ^a ^b Yeoh, William; Felner, Ariel; Koenig, Sven (2008), "BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm", Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 591–8, ISBN 9780981738116
^ Hirayama, Katsutoshi; Yokoo, Makoto (1997). Smolka, Gert (ed.). "Distributed partial constraint satisfaction problem". Principles and Practice of Constraint Programming-CP97. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 1330: 222–236. doi:10.1007/BFb0017442. ISBN 978-3-540-69642-1.
^ 입양의 원래 출판된 버전은 정보가 없었다. 참조하라.Adopt의 원래 버전이 나중에 알려 주기를, 그것은, 더 빨리 달리구글의 검색 집중하기 위하여 해결책 비용의 추정 사용할, 알리, 솃;코엔 크는 스벤;Tambe, Milind(2005년),"그 DCOP 알고리즘 ADOPT의 가속 팽창을 Preprocessing 기술"(PDF), 자율적 나이를 4국제 공동 회의 회보를 참조하십시오. 확대되었다.Nts과multiagent 시스템, ACM출판부를 대신하여 서명함. 1041–8, doi:10.1145/1082473.1082631, 아이 에스비엔 1595930930, S2CID 10882572.이 채택의 확장은 일반적으로 채택의 기준 구현으로 사용된다.
^ Matsui, Toshihiro; Matsuo, Hiroshi; Iwata, Akira (February 2005), "Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm" (PDF), Proceedings of Artificial Intelligence and Applications, pp. 727–732, CiteSeerX 10.1.1.408.7230
^ Mailler, Roger; 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, pp. 438–445, ISBN 1581138644
^ Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), "Termination Problem of the APO Algorithm" (PDF), Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning, pp. 117–124
^ Petcu, Adrian; Faltings, Boi (August 2005), "DPOP: A Scalable Method for Multiagent Constraint Optimization", Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, Edinburgh, Scotland, pp. 266-271
^ Chechetka, Anton; Sycara, Katia (May 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, pp. 1427–9, doi:10.1145/1160633.1160900, ISBN 1595933034, S2CID 43918609
^ Chechetka, Anton; Sycara, Katia (March 2006), "An Any-space Algorithm for Distributed Constraint Optimization" (PDF), Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management
^ Duffy, K.R.; Leith, D.J. (August 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). "Asymmetric Distributed Constraint Optimization Problems". Journal of Artificial Intelligence Research. 47: 613–647. doi:10.1613/jair.3945. ISSN 1076-9757.
^ Greenstadt, Rachel; Pearce, Jonathan P.; Tambe, Milind (2006-07-16). "Analysis of privacy loss in distributed constraint optimization". Proceedings of the 21st National Conference on Artificial Intelligence - Volume 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). "Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications". Autonomous Agents and Multi-Agent Systems. 13 (1): 27–60. doi:10.1007/s10458-006-5951-y. ISSN 1573-7454. S2CID 16962945.
^ Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (ed.). "Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information". Principles and Practice of Constraint Programming - CP 2002. Lecture Notes in Computer Science. 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). "Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling". www.computer.org. Retrieved 2021-04-12.{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
^ ^a ^b Zivan, Roie; Grubshtein, Alon; Friedman, Michal; Meisels, Amnon (2012-06-04). "Partial cooperation in multi-agent search". Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3. AAMAS '12. Valencia, Spain: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1268. ISBN 978-0-9817381-3-0.

서적 및 설문 조사

Fioretto, Ferdinando; Pontelli, Enrico; Yeoh, William (2018), "Distributed Constraint Optimization Problems and Applications: A Survey", Journal of Artificial Intelligence Research, 61: 623–698, arXiv:1602.06347, doi:10.1613/jair.5565, S2CID 4503761
Faltings, Boi (2006), "Distributed Constraint Programming", in Walsh, Toby (ed.), Handbook of Constraint Programming, Elsevier, ISBN 978-0-444-52726-4 편집된 책의 한 장.
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, New York: Cambridge University Press, ISBN 978-0-521-89943-7 1장 및 2장, 온라인 무료 다운로드 가능을 참조하십시오.
Yokoo, Makoto (2001), Distributed constraint satisfaction: Foundations of cooperation in multi-agent systems, Springer, ISBN 978-3-540-67596-9
Yokoo, M. Hirayama K. (2000), "Algorithms for distributed constraint satisfaction: A review", Autonomous Agents and Multiagent Systems, 3 (2): 185–207, doi:10.1023/A:1010078712316, S2CID 2139298

[1] " $\times$ $[\displaystyle \times }$ $\times$ 또는 "×"는 데카르트 제품을 의미한다.

[:2-2] Netzer, Arnon; Meisels, Amnon; Zivan, Roie (2016-03-01). "Distributed envy minimization for resource allocation". Autonomous Agents and Multi-Agent Systems. 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: An Asynchronous Branch-and-Bound DCOP Algorithm", Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 591–8, ISBN 9780981738116

[4] Hirayama, Katsutoshi; Yokoo, Makoto (1997). Smolka, Gert (ed.). "Distributed partial constraint satisfaction problem". Principles and Practice of Constraint Programming-CP97. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 1330: 222–236. doi:10.1007/BFb0017442. ISBN 978-3-540-69642-1.

[5] 입양의 원래 출판된 버전은 정보가 없었다. 참조하라.Adopt의 원래 버전이 나중에 알려 주기를, 그것은, 더 빨리 달리구글의 검색 집중하기 위하여 해결책 비용의 추정 사용할, 알리, 솃;코엔 크는 스벤;Tambe, Milind(2005년),"그 DCOP 알고리즘 ADOPT의 가속 팽창을 Preprocessing 기술"(PDF), 자율적 나이를 4국제 공동 회의 회보를 참조하십시오. 확대되었다.Nts과multiagent 시스템, ACM출판부를 대신하여 서명함. 1041–8, doi:10.1145/1082473.1082631, 아이 에스비엔 1595930930, S2CID 10882572.이 채택의 확장은 일반적으로 채택의 기준 구현으로 사용된다.

[matsui05efficient-6] Matsui, Toshihiro; Matsuo, Hiroshi; Iwata, Akira (February 2005), "Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm" (PDF), Proceedings of Artificial Intelligence and Applications, pp. 727–732, CiteSeerX 10.1.1.408.7230

[mailler04solving-7] Mailler, Roger; 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, pp. 438–445, ISBN 1581138644

[dcr07proceedings-8] Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), "Termination Problem of the APO Algorithm" (PDF), Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning, pp. 117–124

[petcu04distributed-9] Petcu, Adrian; Faltings, Boi (August 2005), "DPOP: A Scalable Method for Multiagent Constraint Optimization", Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, Edinburgh, Scotland, pp. 266-271

[chechetka06no-10] Chechetka, Anton; Sycara, Katia (May 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, pp. 1427–9, doi:10.1145/1160633.1160900, ISBN 1595933034, S2CID 43918609

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

[cfl-12] Duffy, K.R.; Leith, D.J. (August 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). "Asymmetric Distributed Constraint Optimization Problems". Journal of Artificial Intelligence Research. 47: 613–647. doi:10.1613/jair.3945. ISSN 1076-9757.

[14] Greenstadt, Rachel; Pearce, Jonathan P.; Tambe, Milind (2006-07-16). "Analysis of privacy loss in distributed constraint optimization". Proceedings of the 21st National Conference on Artificial Intelligence - Volume 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). "Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications". Autonomous Agents and Multi-Agent Systems. 13 (1): 27–60. doi:10.1007/s10458-006-5951-y. ISSN 1573-7454. S2CID 16962945.

[16] Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (ed.). "Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information". Principles and Practice of Constraint Programming - CP 2002. Lecture Notes in Computer Science. 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). "Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling". www.computer.org. Retrieved 2021-04-12.{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)

[:1-18] Zivan, Roie; Grubshtein, Alon; Friedman, Michal; Meisels, Amnon (2012-06-04). "Partial cooperation in multi-agent search". Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3. AAMAS '12. Valencia, Spain: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1268. ISBN 978-0-9817381-3-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Search