Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Proposta de um Algoritmo para Problema de Satisfação
de Restrição Distribuída
Formando: Daniel Moser TralamazzaOrientador: Jomi Fred Hübner
Roteiro
• Introdução• Fundamentação• Desenvolvimento• Resultados• Conclusão
Contexto
• Problemas de satisfação de restrição• Algoritmos distribuídos• Sistemas Multiagentes (SMA)
Objetivos
• Implementar o algoritmo AWC proposto por Makoto Yokoo
• Criar um algoritmo derivado que utilize novas heurísticas
Constraint SatisfactionProblems (CSP)
• Simples representação (TSANG 1993):– Conjunto de variáveisvariáveisvariáveisvariáveis x1, x2,... xn com valoresvaloresvaloresvalores v1,
v2,... vn pertencentes à domíniosdomíniosdomíniosdomínios D1, D2,... Dnnão vazios;
– Conjunto de restriçõesrestriçõesrestriçõesrestrições C1, C2,... Cn sobre os valores das variáveis.
• Em geral NP-Completos (YOKOO 2001)• Capaz de modelar diversos problemas na IA:
– Alocação de recursos;– Coloração de grafos;– Agendamento de tarefas.
Exemplos
x2
x1
x4
x3
Distributed CSP (DCSP)
• Pioneiro: Makoto Yokoo• Distribuição da informação entre agentes• Paralelismo: vantagens e desvantagens
Asynchronous Backtracking(ABT)
• Assíncrono• Ordenação (estática) dos agentes• Completo
Asynchronous Weak Commitment (AWC)
• Derivado do ABT• Ordenação dinâmica dos agentes
(prioridade)• Heurística para escolha de valores
Funcionamento do AWC
0
0
2
1 1
2
0
0
1
0 0
0
0
0
0
0
Desenvolvimento
• Utilização de um framework específico para DCSP desenvolvido pelo Grupo de Pesquisa de DCSP da FURB
• Implementado em Java Sun ®
Framework
Classe BaseAlg
Desenvolvimento AWC
• Implementado a partir do pseudo-código original desenvolvido por Yokoo(2001)
Classe AWC
Heurística Min-Conflict
Funcionamento do protótipo: Criação de launchers
Execução distribuída
Funcionamento do protótipo: Criação de agentes
Avaliação do AWC
• Problema das n-Rainhas (40)• Número de computadores variando de
1 a 40• Configuração:
– Rede 100Mbit– Pentium 1GHz, 256 RAM– Conectiva Linux 9
Resultado AWC
Protótipo
• Heurísticas propostas:– Valores menos utilizados;– Ordenação de restrições.
• Não armazenamento de nogoods
Conclusão
• O AWC foi implementado com sucesso• A garantia de completude AWC causa
grande perda de desempenho• Novas heurísticas para escolha de
valores aumentaram o desempenho
Extensões
• DCSP dinâmicos• Domínios infinitos• Novos algoritmos e heurísticas• Segurança da comunicação e
exposição do problema• Tornar os agentes “menos” reativos
Referencias Bibliográficas• YOKOO, M. Distributed constraint satisfaction. Berlin:
Springer, 2001.
• TSANG, E.Foundations of constraint satisfaction.London: Academic Press, 1993.
Demonstração
• AWC– Uma máquina com 4-Rainhas– 20 máquinas com 40-Rainhas
• AWC sem nogood– 20 máquinas com 40-Rainhas
• AWC sem nogood e least used values– 20 máquinas com 40-Rainhas