Resolução Distribuída de Problemas

e Planejamento Multiagente

Pablo Sampaio e Talita Menezes

Tópicos

1. Introdução

2. Resolução Distribuída de Problemas

3. Planejamento Clássico e Planejamento Multiagente

4. Planejamento Centralizado de Planos Distribuídos

5. Planejamento Distribuído de Planos Centralizados

6. Planejamento Distribuído de Planos Distribuídos

7. Execução de Planos Distribuídos

8. Conclusão

1. Introdução

Foco da aula Agentes trabalhando em conjunto para resolver um

problema comum

Motivações Acelerar a obtenção da solução

Ex.: agentes em diferentes máquinas Distribuição inerente ao problema

Ex.: monitoramento de uma grande área geográfica Resultados finais serão distribuídos entre

múltiplos agentes Ex.: correios

2. Resolução Distribuída de Problemas

Visão otimista de sistemas multiagentes Agentes benevolentes Objetivos comuns (ou complementares)

Exige dos agentes Coerência: agentes querem trabalhar juntos Competência: agentes sabem trabalhar em conjunto

O problema comum pode ser construir um plano Planejamento multiagente como caso especial de

Resolução Distribuída de Problemas (RDP)

2. Resolução Distribuída de Problemas

Duas principais classes de estratégias usadas

Divisão de Tarefas (task sharing): um agente com muitas tarefas repassa tarefas ou sub-tarefas a outros agentes

Compartilhamento de Resultados (result sharing): agentes compartilham os resultados obtidos da resolução de uma sub-tarefa

2.1 Divisão de Tarefas

A solução é obtida hierarquicamente pela divisão de uma tarefa complexa em tarefas menores

Principais etapas:1. Decomposição das tarefas: um agente gera o conjunto de

sub-tarefas a ser dividido entre os agentes

2. Alocação das tarefas: atribuição de sub-tarefas aos agentes apropriados

3. Resolução da tarefa: o agente pode executar a tarefa diretamente ou fazer uma nova divisão de tarefas

4. Síntese do resultado: integração dos resultados parciais gerados pelos agentes

2.1 Divisão de Tarefas

Exemplo: agentes precisam encontrar figuras escondidas numa região Decomposição: dividir a região ou as figuras para a

busca Alocação: cada agente cuida de uma área ou figura Execução: buscar quaisquer figuras na região

destinada a ele, ou buscar em toda a região uma figura específica

Síntese: cada agente apresenta as figuras encontradas

2.1 Divisão de Tarefas

É difícil construir um agente competente em qualquer tipo de tarefa

Os agentes possuem diferentes habilidades Sistemas heterogêneos

Habilidades devem ser consideradas na divisão de tarefas ! Escalar agentes sob-demanda, de acordo com sua

especialidade

Uma aboragem seria manter uma tabela de serviços Problema: e se o agente já estiver ocupado ?

2.1 Divisão de Tarefas

Adaptações do Contract-Net1. Contratação via broadcast:

Envia uma proposta contendo a especificação do problema Apenas os agentes capazes de resolver e que estiverem em

disponibilidade respodem

2. Novas tentativas Quando nenhum agente responder, o contratante anuncia novamente

após um certo tempo

3. Revisão do anúncio Propostas contém restrições sobre os possíveis (requisitos de

eligibilidade) Requisitos podem ser relaxados

4. Decomposições alternativas Divide diferentemente o problema original

2.1 Divisão de Tarefas

Nem sempre é possível criar sub-tarefas totalmente independentes Ex.: Engenharia de produtos

Uma abordagem Um gerente acompanha o andamento das sub-tarefas Cabe ao gerente solucionar dependências, repassando os

resultados das tarefas

Problema - Interdependências podem se tornar aparentes somente após iniciada a resolução da tarefa Necessidade de compartilhar resultados parciais

2.2 Compartilhamento de Resultados Agentes compartilham informações relevantes

para resolução dos sub-problemas

Resultados parciais podem ser trocados entre os agente de modo a resolver problemas de interdependência

Compartilhamento pode ser: Pró-ativo: agente envia informação por acreditar que

essa informação auxiliará outro agente Reativo: agente envia informação como resposta a

uma solicitação

2.2 Compartilhamento de Resultados Retorno em relação à performance do grupo:

Confiança Diferentes agentes chegando ao mesmo resultado

Completude Resultados de sub-problemas cobrem o problema como um

todo Precisão

Para refinar sua solução, um agente precisa saber mais sobre a solução de outros agentes

Rapidez O reaproveitamento de resultados parciais de outros

agentes pode agilizar a solução de uma sub-problema

2.2 Compartilhamento de Resultados Problema: possibilidade de overhead de

comunicação

Limitando a comunicação Repositórios Compartilhados

Diversas alternativas de soluções parciais Busca Heurística Distribuída com Restrições

Acesso às informações (recursos) de maneira controlada

Estruturação organizacional Define papéis, responsabilidades, etc Apenas agentes de papéis relacionados se comunicam

3. Relembrando Planejamento

Planejamento: elaboração de uma seqüência de ações para alcançar um objetivo

Planejamento Clássico Mundo simples: completamente observável,

determinístico, finito, estático, discreto Considera um único agente Natureza indiferente ao agente

3. Planejamento Clássico

STRIPS Linguagem usada para representar problemas de planejamento Estados

Proposições lógicas Hipótese do mundo fechado

Objetivos Conjunção de literais básicos positivos

Ações Pré-condições Efeitos: literais verdadeiros (adicionados) e falsos

(removidos)

3. Planejamento Clássico

Algoritmos Podem ser aplicados algoritmos de busca

Geração de planos de ordem total: ações em ordem rigidamente definida

POP (Planejador de Ordem Parcial) Não é imposta nenhuma ordem entre ações

independentes Precedência para ações em conflito O resultado é um grafo dos planos possíveis

z A

B

D

C

E

F

3. Planejamento Multiagente

Mecanismo de coordenação que permite organizar as interações (futuras) entre agentes de maneira a alcançar um objetivo comum

Pode ser visto como caso especial de RDP O problema a ser solucionado é criar é um plano

Estende o planejamento clássico para domínios onde vários agentes podem planejar e/ou agir juntos Ambiente mais complexo: parcialmente observável,

estocástico, dinâmico

3. Planejamento Multiagente

Elaboração de um Plano Conjunto composto de ações para cada agente

A execução de todas as partes do Plano Conjunto leva a sociedade a atingir seu objetivo comum

Distribuição pode estar presente No Planejamento (elaboração do plano) No Plano (tarefas a serem executadas)

3. Planejamento Multiagente

Elaboração do Plano Conjunto:

Planejamento Centralizado de Planos Distribuídos Planejamento Distribuído de Planos Centralizados Planejamento Distribuído de Planos Distribuídos

4. Planejamento Centralizado de Planos Distribuídos Um agente coordenador planeja e os demais executam

O agente coordenador é responsável por Criar um plano conjunto

Identificar ações independentes Dividir em sub-planos

Distribuir tarefas entre os agentes Gerenciar a execução do plano

Sincronização, para evitar conflitos

Caso especial de Divisão de Tarefas, porém com o uso de técnicas de planejamento clássico na etapa de decomposição

4. PCPD – Algoritmo

1. Dada a descrição STRIPS do mundo, gerar plano de ordem parcial

2. Decompor em sub-planos, minimizando relações de ordem entre os sub-planos

Decomposição 1:

Decomposição 2:

A decomposição 1 é preferível !

A

B

D

C

E

F

Sub-plano 1: B < C < FSub-plano 2: A < D < EOutras restrições: B < E

Sub-plano 1: B < D < ESub-plano 2: A < C < FOutras restrições: B < C e A < D

4. PCPD – Algoritmo

3. Inserir ações de sincronização nos pontos de dependência dos planos

4. Alocar sub-planos aos agentes. Se não for possível, retornar para passo 2 ou 1

5. Inicia a execução e monitora o progresso

Sub-plano 1: B < send(condE) < C < FSub-plano 2: A < D < wait(condE) < E

Agente1 ← Sub-plano 1: B < send(condE) < C < FAgente2 ← Sub-plano 2: A < D < wait(condE) < E

4. PCPD - Avaliação

Vantagens Simplicidade na geração do plano Problemas de coordenação resolvidos a priori

Desvantagens Dependência do coordenador para realização do

plano Confiabilidade do coordenador Supõe coordenador onisciente

5. Planejamento Distribuído de Planos Centralizados O planejamento se realiza de maneira distribuída,

resultando num único plano centralizado

Divisão de Tarefas O problema é divido e repassado a agentes especialistas Os agentes geram planos parciais em paralelo para os sub-

problemas

Os agentes interagem trocando planos parciais Planos parciais podem ser passados

seqüencialmente Planos podem ser unidos num único plano global

usando técnicas de result sharing

5. PDPC – Exemplos

Atletismo: vários especialistas planejam a preparação de um atleta Nutricionista planeja a dieta do atleta Treinador faz planos de treinamento e decide a

estratégia durante a prova

Manufatura (exemplo computacional) Um especialista em geometria analisa a peça a ser

manufaturada e gera um plano abstrato Um planejador geral recebe esse plano e

acrescenta as operações de máquina necessárias O plano é passado para um especialista em

montagem que vai garantir que a execução do plano

5. PDPC – Avaliação

Vantagens Utiliza as habilidades dos especialistas para

construção dos sub-planos Problemas de coordenação podem ser resolvidos

antes da execução

Desvantagens Necessidade de intensa comunicação durante o

planejamento A decomposição adequada do problema pode ser

complicada

6. Planejamento Distribuído de Planos Distribuídos Tanto o processo de planejamento quanto os

resultados são distribuídos Não existe um plano global da tarefa em nenhum ponto do

sistema

Agentes fazem seus planos individuais procurando evitar conflitos entre si

O grande problema é manter a compatibilidade entre os planos individuais Agentes podem comunicar planos e objetivos

6. PDPD – Avaliação

Vantagens Tratamento homogêneo entre os agentes Agentes agem conforme suas habilidades e

interesses

Desvantagens Maior complexidade (implementação, avaliação, ...) Necessidade de intensa comunicação durante o

planejamento e execução

6. PDPD – Técnicas

Técnicas para Planejamento Distribuído de Planos Distribuídos:

1. Fusão de planos

2. Construção iterativa de planos

3. Negociação de planejadores distribuídos

6.1 PDPD – Fusão de Planos

Mecanismo centralizado de coordenação

Cada agente, individualmente, formula planos individuais

Necessidade de garantir que esses planos podem ser executados separadamente sem conflitos

Duas fases: Reachability analisis: dados os estados iniciais possíveis e as

ações aplicáveis, identifica os estados do mundo que podem ser alcançados

Identifica estados indesejáveis do mundo e insere restrições entre os planos para evitar estes estados

6.1 PDPD – Fusão de Planos

Algoritmo de Georgeff (1983)

A partir de um conjunto de planos iniciais gera planos para vários agentes de forma que não haja conflitos entre eles.

Utiliza uma versão aumentada do formalismo STRIPS

Cada ação definida a partir de: Nome, pré-condições e efeitos (como em STRIPS) Georgeff + Lista de fatos que devem ser verdadeiros

durante a execução da ação (during list)

6.2 PDPD – Construção Iterativa de Planos Problema das abordagens anteriores: às vezes,

decisões locais dependem das decisões de outros agentes Exemplo: Agent1 vai empurrar o bloco junto com Agent2

Uma solução: cada agente, ao invés de propor um único plano, propõe um conjunto de planos alternativos Espaço de Planos x Plano Único

O processo de planejamento consiste, então, em uma busca pelos planos (dentre os propostos) que podem ser combinados Várias técnicas para isso…

6.3 PDPD – Negociação em Planejamento Distribuído Nas técnicas anteriores, a resolução de conflitos entre

agentes se dá de maneira arbitrária Qual agente vai esperar por qual?

Solução: agentes negociam esse tipo de resolução Protocolo comum: processo de decisão usado para determinar

suas posições, concessões e critérios Heurística: dar preferência ao agente mais restringido

Exemplo: controle de tráfego aéreo (Steeb e Camarata) Sistemas de aviões em rota de colisão analisam suas

possibilidades O que tivesse mais opções alternativas mudaria de direção

7. Execução de Planos Distribuídos Necessidade de monitoramento da execução do plano

(coordenação)

Técnicas de Coordenação pós-planejamento: Planejamento de Contingência: planos alternativos Monitoramento e Replanejamento: repete o ciclo planejar-

coordenar-executar

Técnicas de Coordenação pré-planejamento: Leis de sociabilidade: proibe certar ações em certos contextos

Coordenação de planos em tempo de execução sem comunicação Coordenação de planos baseada em observações

7. Planejamento, Coordenação e Execução Intercalados Planejar continuamente quando:

Aspectos do mundo podem mudar dinamicamente Aspectos do mundo são revelados incrementalmente Limitações de tempo fazem com que a execução comece antes

do plano ter sido totalmente gerado

Planejamento Global Parcial Agentes fazem planos locais parciais: detalhado e abstrato Planos parciais abstratos são compartilhados e objetivos

globais parciais são indentificados Execução: alterações maiores nos planos locais podem levar a

um replanejamento Realocação de tarefas desproporcionais

8. Conclusão

Há várias técnicas e ferramentas para Planejamento Multiagente A maioria derivada de técnicas de RDP

Desafio é entender quando aplicar cada técnica

Potenciais aplicações para PMA: Ambientes multirobôs Tarefas militares Logística Manufatura Design de peças/produtos

8. Referências

Wooldridge, M. J.: An Introduction to MultiAgent Systems. John Wiley and Sons, 2002.

Weis, G.: Multiagent Systems – A Modern Approach to Distributed Artificial Intelligence

Russel, S. Norvig, P.: Inteligência Artifical (segunda edição)

A Multiagent Planning Architecture, http://www.ai.sri.com/~wilkins/mpa/

CODA, http://www.ai.sri.com/~coda/

Ferber, J.: Multi-Agent Systems – An Introduction to Distributed Artificial Intelligence

Mardhana, E.: Overview of Distributed Collaborative Planning: Concepts and Applications