Otimização de restrição distribuída

A otimização de restrição distribuída ( DCOP ou DisCOP ) é ​​o análogo distribuído da otimização de restrição . Um DCOP é um problema no qual um grupo de agentes deve escolher valores distribuídos para um conjunto de variáveis, de modo que o custo de um conjunto de restrições sobre as variáveis ​​seja minimizado.

A Satisfação de Restrições Distribuídas é uma estrutura para descrever um problema em termos de restrições que são conhecidas e aplicadas por participantes distintos (agentes). As restrições são descritas em algumas variáveis ​​com domínios pré-definidos, e devem ser atribuídas aos mesmos valores pelos diferentes agentes.

Os problemas definidos com esta estrutura podem ser resolvidos por qualquer um dos algoritmos projetados para ela.

A estrutura foi usada com nomes diferentes na década de 1980. O primeiro uso conhecido com o nome atual foi em 1990. [ citação necessária ]

Definições

DCOP

Os principais ingredientes de um problema DCOP são agentes e variáveis . É importante ressaltar que cada variável pertence a um agente; é isso que torna o problema distribuído. Formalmente, um DCOP é uma tupla , onde:

  • é o conjunto de agentes , .
  • é o conjunto de variáveis ​​, .
  • é o conjunto de domínios variáveis , onde cada um é um conjunto finito contendo os valores possíveis da variável .
    • Se contém apenas dois valores (por exemplo, 0 ou 1), então é chamada de variável binária .
  • é a função custo . É uma função [1]
    que mapeia todas as atribuições parciais possíveis a um custo. Normalmente, apenas alguns valores de são diferentes de zero e são representados como uma lista de tuplas às quais é atribuído um valor diferente de zero. Cada uma dessas tuplas é chamada de restrição . Cada restrição neste conjunto é uma função que atribui um valor real a cada atribuição possível das variáveis. Alguns tipos especiais de restrições são:
    • Restrições unárias - restrições em uma única variável, ou seja, para alguns .
    • Restrições binárias - restrições em duas variáveis, ou seja, para algumas .
  • é a função de propriedade . É uma função que mapeia cada variável para seu agente associado. significa que a variável "pertence" a agent . Isto implica que é responsabilidade do agente atribuir o valor da variável . Observe que não é necessariamente uma injeção , ou seja, um agente pode possuir mais de uma variável. Também não é necessariamente uma sobrejeção , ou seja, alguns agentes podem não possuir variáveis.
  • é a função objetivo . É um operador que agrega todos os custos individuais para todas as atribuições variáveis ​​possíveis. Isso geralmente é feito por meio de soma:

O objetivo de um DCOP é fazer com que cada agente atribua valores às suas variáveis ​​associadas, a fim de minimizar ou maximizar uma determinada atribuição das variáveis.

atribuições

Uma atribuição de valor é um par onde é um elemento do domínio .

Uma atribuição parcial é um conjunto de atribuições de valores onde cada um aparece no máximo uma vez. Também é chamado de contexto. Isso pode ser pensado como uma função que mapeia variáveis ​​no DCOP para seus valores atuais:

Observe que um contexto é essencialmente uma solução parcial e não precisa conter valores para todas as variáveis ​​do problema; portanto, implica que o agente ainda não atribuiu um valor à variável . Dada esta representação, o “ domínio ” (ou seja, o conjunto de valores de entrada) da função pode ser pensado como o conjunto de todos os contextos possíveis para o DCOP. Portanto, no restante deste artigo poderemos usar a noção de contexto (ou seja, a função) como entrada para a função. f

Uma atribuição completa é uma atribuição em que cada uma aparece exatamente uma vez, ou seja, todas as variáveis ​​são atribuídas. Também é chamada de solução para o DCOP.

Uma solução ótima é uma atribuição completa na qual a função objetivo é otimizada (ou seja, maximizada ou minimizada, dependendo do tipo de problema).

Problemas de exemplo

Vários problemas de diferentes domínios podem ser apresentados como DCOPs.

Coloração de gráfico distribuído

O problema de coloração de grafos é o seguinte: dado um grafo e um conjunto de cores , atribua a cada vértice , , uma cor, , de modo que o número de vértices adjacentes com a mesma cor seja minimizado.

Como DCOP, existe um agente por vértice designado para decidir a cor associada. Cada agente possui uma única variável cujo domínio associado é de cardinalidade (existe um valor de domínio para cada cor possível). Para cada vértice , existe uma variável com domínio . Para cada par de vértices adjacentes , existe uma restrição de custo 1 se ambas as variáveis ​​associadas receberem a mesma cor:

O objetivo, então, é minimizar .

Problema de mochila múltipla distribuída

A variante múltipla distribuída do problema da mochila é a seguinte: dado um conjunto de itens de volume variável e um conjunto de mochilas de capacidade variável, atribua cada item a uma mochila de modo que a quantidade de excesso seja minimizada. Seja o conjunto de itens, seja o conjunto de mochilas, seja uma função que mapeia os itens para seu volume e seja uma função que mapeia as mochilas para suas capacidades.

Para codificar este problema como um DCOP, para cada um crie uma variável com domínio associado . Então, para todos os contextos possíveis :

onde representa o peso total atribuído pelo contexto à mochila :

Problema de alocação de itens distribuídos

O problema de alocação de itens é o seguinte. Existem vários itens que devem ser divididos entre vários agentes. Cada agente tem uma avaliação diferente para os itens. O objetivo é otimizar algum objetivo global, como maximizar a soma das utilidades ou minimizar a inveja. O problema de alocação de itens pode ser formulado como um DCOP da seguinte forma. [2]

  • Adicione uma variável binária v ij para cada agente i e item j . O valor da variável é “1” se o agente obtiver o item e “0” caso contrário. A variável pertence ao agente i .
  • Para expressar a restrição de que cada item seja dado a no máximo um agente, adicione restrições binárias para cada duas variáveis ​​diferentes relacionadas ao mesmo item, com custo infinito se as duas variáveis ​​forem simultaneamente “1”, e custo zero caso contrário.
  • Para expressar a restrição de que todos os itens devem ser alocados, adicione uma restrição n -ária para cada item (onde n é o número de agentes), com custo infinito se nenhuma variável relacionada a este item for “1”.

Outras aplicações

O DCOP foi aplicado a outros problemas, como:

  • coordenação de sensores móveis;
  • agendamento de reuniões e tarefas.

Algoritmos

Os algoritmos DCOP podem ser classificados de várias maneiras: [3]

  • Completude - algoritmos de pesquisa completos que encontram a solução ótima, versus algoritmos de pesquisa local que encontram um ótimo local .
  • Estratégia de pesquisa - pesquisa melhor primeiro ou pesquisa ramificada em profundidade;
  • Sincronização entre agentes – síncrona ou assíncrona;
  • Comunicação entre agentes – ponto a ponto com vizinhos no grafo de restrição, ou broadcast;
  • Topologia de comunicação - cadeia ou árvore.

O ADOPT, por exemplo, utiliza busca pelo melhor primeiro, sincronização assíncrona, comunicação ponto a ponto entre agentes vizinhos no grafo de restrições e uma árvore de restrições como topologia de comunicação principal.

Nome do algoritmo Ano de introdução Complexidade de memória Número de mensagens Correção (ciência da computação) /
Completude (lógica)
Implementações
ABT [ citação necessária ]
Retrocesso assíncrono
1992 [ carece de fontes ] [ carece de fontes ] Nota: ordenação estática, completa [ carece de fontes ]
AWC [ citação necessária ]
Compromisso fraco assíncrono
1994 [ carece de fontes ] [ carece de fontes ] Nota: reordenação, rápida, completa (somente com espaço exponencial) [ carece de fontes ]

Algoritmo de Breakout Distribuído DBA
1995 [ carece de fontes ] [ carece de fontes ] Nota: incompleto, mas rápido FRODO versão 1 [ link morto permanente ]
SincronizarBB [4]

Ramificação e limite síncrono

1997 [ carece de fontes ] [ carece de fontes ] Completo, mas lento
BID

Breakout Distribuído Iterativo

1997 [ carece de fontes ] [ carece de fontes ] Nota: incompleto, mas rápido
AAS [ citação necessária ]
Pesquisa de agregação assíncrona
2000 [ carece de fontes ] [ carece de fontes ] agregação de valores em ABT [ carece de fontes ]
DFC [ citação necessária ]
Encadeamento direto distribuído
2000 [ carece de fontes ] [ carece de fontes ] Nota: baixo, comparável ao ABT [ carece de fontes ]
ABTR [ citação necessária ]
Retrocesso assíncrono com reordenação
2001 [ carece de fontes ] [ carece de fontes ] Nota: reordenamento em ABT com bens limitados [ carece de fontes ]
DMAC [ citação necessária ]
Mantendo consistências assíncronas
2001 [ carece de fontes ] [ carece de fontes ] Nota: o algoritmo mais rápido [ carece de fontes ]
Computação segura com servidores semiconfiáveis ​​[ carece de fontes ] 2002 [ carece de fontes ] [ carece de fontes ] Nota: a segurança aumenta com o número de servidores confiáveis [ carece de fontes ]
Computação multipartidária segura para resolver DisCSPs
(MPC-DisCSP1-MPC-DisCSP4) [ carece de fontes ]
2003 [ carece de fontes ] [ carece de fontes ] Nota: seguro se 1/2 dos participantes for confiável [ carece de fontes ]
Adote
retrocesso assíncrono [5]
2003 Polinômio (ou qualquer espaço [6] ) Exponencial Comprovado Implementação de referência: Adote arquivado em 16/09/2006 na Wayback Machine

DCOPolis ( GNU LGPL )
FRODO ( AGPL )


Sobreposição parcial assíncrona OptAPO [7]
2004 Polinomial Exponencial Comprovado, mas a prova de integridade foi contestada [8] Implementação de referência: "OptAPO". Centro de Inteligência Artificial . SRI Internacional . Arquivado do original em 15/07/2007.

DCOPolis ( GNU LGPL ); Em desenvolvimento


Procedimento de otimização de pseudoárvore distribuída DPOP [9]
2005 Exponencial Linear Comprovado Implementação de Referência: FRODO ( AGPL )

DCOPolis ( GNU LGPL )


Filial e limite sem compromisso da NCBB [10]
2006 Polinômio (ou qualquer espaço [11] ) Exponencial Comprovado Implementação de referência: não divulgada publicamente

DCOPolis ( GNU LGPL )


Aprendizagem sem comunicação CFL [12]
2013 Linear Nenhuma Nota: nenhuma mensagem é enviada, mas pressupõe conhecimento sobre a satisfação da restrição local Incompleto

Também existem híbridos desses algoritmos DCOP. BnB-Adopt, [3] por exemplo, muda a estratégia de busca do Adopt de busca melhor para busca em profundidade branch-and-bound.

DCOP assimétrico

Um DCOP assimétrico é uma extensão do DCOP em que o custo de cada restrição pode ser diferente para diferentes agentes. Alguns exemplos de aplicações são: [13]

  • Agendamento de eventos : os agentes que participam do mesmo evento podem derivar valores diferentes dele.
  • Rede inteligente : o aumento do preço da eletricidade nas horas carregadas pode ser de diferentes agentes.

Uma maneira de representar um ADCOP é representar as restrições como funções:

Aqui, para cada restrição não existe um custo único, mas um vetor de custos – um para cada agente envolvido na restrição. O vetor de custos tem comprimento k se cada variável pertencer a um agente diferente; se duas ou mais variáveis ​​pertencem ao mesmo agente, então o vetor de custos é mais curto - existe um único custo para cada agente envolvido , não para cada variável.

Abordagens para resolver um ADCOP

Uma maneira simples de resolver um ADCOP é substituir cada restrição por uma restrição , que seja igual à soma das funções . No entanto, esta solução exige que os agentes revelem as suas funções de custo. Muitas vezes, isto não é desejado devido a considerações de privacidade. [14] [15] [16]

Outra abordagem é chamada de Eventos Privados como Variáveis ​​(PEAV). [17] Nesta abordagem, cada variável possui, além de suas próprias variáveis, também "variáveis ​​espelho" de todas as variáveis ​​pertencentes a seus vizinhos na rede de restrições. Existem restrições adicionais (com um custo infinito) que garantem que as variáveis ​​​​espelho sejam iguais às variáveis ​​originais. A desvantagem deste método é que o número de variáveis ​​e restrições é muito maior que o original, o que leva a um tempo de execução maior.

Uma terceira abordagem é adaptar algoritmos existentes, desenvolvidos para DCOPs, à estrutura ADCOP. Isso foi feito tanto para algoritmos de pesquisa completa quanto para algoritmos de pesquisa local. [13]

Comparação com jogos estratégicos

A estrutura de um problema ADCOP é semelhante ao conceito da teoria dos jogos de um jogo simultâneo . Em ambos os casos, existem agentes que controlam variáveis ​​(na teoria dos jogos, as variáveis ​​são as possíveis ações ou estratégias dos agentes). Em ambos os casos, cada escolha de variáveis ​​pelos diferentes agentes resulta num payoff diferente para cada agente. No entanto, há uma diferença fundamental: [13]

  • Num jogo simultâneo, os agentes são egoístas - cada um deles quer maximizar a sua própria utilidade (ou minimizar o seu próprio custo). Portanto, o melhor resultado que pode ser procurado em tal cenário é um equilíbrio – uma situação em que nenhum agente pode aumentar unilateralmente o seu próprio ganho.
  • Num ADCOP, os agentes são considerados cooperativos: agem de acordo com o protocolo mesmo que isso diminua a sua própria utilidade. Portanto, o objetivo é mais desafiador: gostaríamos de maximizar a soma das utilidades (ou minimizar a soma dos custos). Um equilíbrio de Nash corresponde aproximadamente a um ótimo local deste problema, enquanto procuramos um ótimo global.

Cooperação parcial

Existem alguns modelos intermédios em que os agentes são parcialmente cooperativos : estão dispostos a diminuir a sua utilidade para ajudar o objectivo global, mas apenas se o seu próprio custo não for demasiado elevado. Um exemplo de agentes parcialmente cooperativos são os empregados de uma empresa. Por um lado, cada funcionário quer maximizar a sua própria utilidade; por outro lado, também querem contribuir para o sucesso da empresa. Portanto, eles estão dispostos a ajudar outras pessoas ou a realizar outras tarefas demoradas que ajudem a empresa, desde que não seja muito oneroso para eles. Alguns modelos para agentes parcialmente cooperativos são: [18]

  • Benefício pessoal garantido : os agentes concordam em agir para o bem global se a sua própria utilidade for pelo menos tão elevada como no cenário não cooperativo (ou seja, o resultado final deve ser uma melhoria de Pareto do estado original).
  • Cooperação lambda : existe um parâmetro . Os agentes concordam em agir para o bem global se a sua própria utilidade for pelo menos tão elevada quanto a sua utilidade não-cooperativa.

A resolução de tais ADCOPs de cooperação parcial requer adaptações dos algoritmos ADCOP. [18]

Veja também

Notas e referências

  1. ^ " " ou "×" denota o produto cartesiano .
  2. ^ Netzer, Arnon; Meisels, Amnom; Zivan, Roie (01/03/2016). “Minimização da inveja distribuída para alocação de recursos”. Agentes Autônomos e Sistemas Multiagentes . 30 (2): 364–402. doi :10.1007/s10458-015-9291-7. ISSN  1387-2532. S2CID13834856  .
  3. ^ ab Sim, William; FELNER, Ariel; Koenig, Sven (2008), "BnB-ADOPT: Um Algoritmo DCOP Assíncrono Branch-and-Bound", Anais da Sétima Conferência Conjunta Internacional sobre Agentes Autônomos e Sistemas Multiagentes , vol. 2, pp . 9780981738116
  4. ^ Hirayama, Katsutoshi; Yokoo, Makoto (1997). Smolka, Gert (ed.). Problema de satisfação de restrições parciais distribuídas. Notas de aula em Ciência da Computação. Vol. 1330. Berlim, Heidelberg: Springer. págs. 222–236. doi :10.1007/BFb0017442. ISBN 978-3-540-69642-1. {{cite book}}: |journal=ignorado ( ajuda )
  5. ^ A versão publicada originalmente de Adopt foi desinformada, consulte Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo , Makoto (2003), "Um método completo assíncrono para otimização de restrições distribuídas" (PDF) , Anais da segunda conferência conjunta internacional sobre agentes autônomos e sistemas multiagentes , ACM Press, pp. ) em 04/11/2019 , recuperado em 07/09/2009. A versão original do Adopt foi posteriormente ampliada para ser informada, ou seja, para utilizar estimativas dos custos da solução para focar sua busca e rodar mais rapidamente, ver Ali, Syed; Koenig, Sven; Tambe, Milind (2005), "Técnicas de pré-processamento para acelerar o algoritmo DCOP ADOPT" (PDF) , Anais da quarta conferência conjunta internacional sobre agentes autônomos e sistemas multiagentes , ACM Press , pp. ISBN 1595930930, S2CID  10882572, arquivado do original (PDF) em 07/07/2010 , recuperado em 07/09/2009. Esta extensão do Adopt é normalmente usada como implementação de referência do Adopt.
  6. ^ Matsui, Toshihiro; Matsuo, Hiroshi; Iwata, Akira (fevereiro de 2005), "Método eficiente para algoritmo de otimização de restrição distribuída assíncrona" ( PDF) , Proceedings of Artificial Intelligence and Applications , pp.  
  7. ^ Mailler, Roger; Lesser, Victor (2004), "Resolvendo problemas de otimização de restrições distribuídas usando mediação cooperativa" (PDF) , Anais da Terceira Conferência Conjunta Internacional sobre Agentes Autônomos e Sistemas Multiagentes , IEEE Computer Society , pp. 1581138644[ link morto permanente ]
  8. ^ Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), "Problema de terminação do algoritmo APO" (PDF) , Anais do Oitavo Workshop Internacional sobre Raciocínio de Restrições Distribuídas , pp.
  9. ^ Petcu, Adrian; Faltings, Boi (agosto de 2005), "DPOP: A Scalable Method for Multiagent Constraint Optimization", Anais da 19ª Conferência Conjunta Internacional sobre Inteligência Artificial, IJCAI 2005, Edimburgo, Escócia, pp.
  10. ^ Chechetka, Anton; Sycara, Katia (maio de 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 . , ISBN  1595933034, S2CID43918609 ​
  11. ^ Chechetka, Anton; Sycara, Katia (março de 2006), "An Any-space Algorithm for Distributed Constraint Optimization" (PDF) , Anais do Simpósio AAAI Spring sobre Plano Distribuído e Gerenciamento de Cronograma
  12. ^ Duffy, KR; Leith, DJ (agosto de 2013), "Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103.3240 , doi :10.1109/TNET.2012.2222923, S2CID  11504393
  13. ^ Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A. (30/07/2013). "Problemas de otimização de restrições distribuídas assimétricas". Jornal de Pesquisa em Inteligência Artificial . 47 : 613–647. arXiv : 1402.0587 . doi : 10.1613/jair.3945 . ISSN  1076-9757.
  14. ^ Greenstadt, Rachel; Pearce, Jonathan P.; Tambe, Milind (16/07/2006). “Análise de perda de privacidade na otimização de restrições distribuídas”. Anais da 21ª Conferência Nacional de Inteligência Artificial - 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 (01/07/2006). "Perda de privacidade no raciocínio de restrições distribuídas: uma estrutura quantitativa para análise e suas aplicações". Agentes Autônomos e Sistemas Multiagentes . 13 (1): 27–60. doi :10.1007/s10458-006-5951-y. ISSN  1573-7454. S2CID16962945  .
  16. ^ Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (ed.). Satisfação segura de restrições distribuídas: chegar a um acordo sem revelar informações privadas. Notas de aula em Ciência da Computação. Vol. 2470. Berlim, Heidelberg: Springer. páginas 387–401. doi :10.1007/3-540-46135-3_26. ISBN 978-3-540-46135-7. {{cite book}}: |journal=ignorado ( ajuda )
  17. ^ Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, Pradeep Varakantham (2004). "Levando o DCOP para o mundo real: soluções completas e eficientes para agendamento distribuído de vários eventos" . www.computador.org . Recuperado em 12/04/2021 .{{cite web}}: CS1 maint: multiple names: authors list (link)
  18. ^ ab Zivan, Roie; Grubshtein, Alon; Friedman, Mical; Meisels, Amnon (04/06/2012). “Cooperação parcial na busca multiagente”. Anais da 11ª Conferência Internacional sobre Agentes Autônomos e Sistemas Multiagentes - Volume 3 . AAMAS '12. 3 . Valência, Espanha: Fundação Internacional para Agentes Autônomos e Sistemas Multiagentes: 1267–1268. ISBN 978-0-9817381-3-0.

Livros e pesquisas

  • Fioretto, Ferdinando; Pontelli, Enrico; Yeoh, William (2018), "Problemas e aplicações de otimização de restrições distribuídas: uma pesquisa", Journal of Artificial Intelligence Research , 61 : 623–698, arXiv : 1602.06347 , doi :10.1613/jair.5565, S2CID  4503761
  • Faltings, Boi (2006), "Distributed Constraint Programming", em Walsh, Toby (ed.), Handbook of Constraint Programming , Elsevier , ISBN 978-0-444-52726-4Um capítulo de um livro editado.
  • Meisels, Amnon (2008), Pesquisa distribuída por agentes restritos , Springer , ISBN 978-1-84800-040-7
  • Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagentes: fundamentos algorítmicos, teóricos de jogos e lógicos, Nova York: Cambridge University Press , ISBN 978-0-521-89943-7Consulte os Capítulos 1 e 2; para download gratuito on-line.
  • Yokoo, Makoto (2001), Satisfação de restrições distribuídas: Fundamentos de cooperação em sistemas multiagentes , Springer , ISBN 978-3-540-67596-9
  • Yokoo, M. Hirayama K. (2000), "Algoritmos para satisfação de restrições distribuídas: uma revisão", Agentes Autônomos e Sistemas Multiagentes , 3 (2): 185–207, doi :10.1023/A:1010078712316, S2CID  2139298


Retrieved from "https://en.wikipedia.org/w/index.php?title=Distributed_constraint_optimization&oldid=1210435410"