Distributed Problem Solvingand Distributed Planning

Aydano PamponetGiordano Ribeiro

Prof. Jacques Robin

Introdução

Resolução de problemas distribuída– definição mais geral equivalente a sistemas

multiagentes

– definição mais restrita: resolução de problema por meio de busca na qual a exploração do espaço de soluções é distribuída entre vários agentes

Busca distribuída:– são incapazes de explorar individualmente o espaço

de soluções inteiro

– ou exploram o espaço mais rapidamente quando cooperam

Introdução

Na solução distribuída de problemas:

– coerência ( os agentes precisam querer trabalhar em grupo )

– competência ( os agentes precisam saber como trabalhar bem em grupo )

Introdução

Geralmente assumimos a coerência– os agentes já são projetados para trabalhar em

grupo, os objetivos só são conseguidos se houver trabalho em grupo etc.

Nos concentramos na competência– como alguém joga em um time, trabalha em

grupo num projeto, participa de uma orquestra etc.

Introdução

Muitos problemas envolvem a construção de um plano

Planejamento distribuído:– não apenas decompor problemas em

subproblemas

– como também: alocar esses subproblemas entre os agentes trocar soluções de subproblemas

Distributed Planning fortemente ligado com Distributed Problem Solving

Distributed Problem Solving

Motivações e Problemas Exemplos

Problemas com sub-tarefas iguais e independentes:– que podem ser executadas em paralelo para

processamento mais eficiente (ToH)– que devem ser executadas em paralelo por

distribuição inerente: dos sensores (DNSE/DVM) ou dos efetuadores (DD) percepção, atuação ou raciocínio podem ser distribuídos

Problemas com sub-tarefas distintas envolvendo competências especializadas (montagem de um carro)

Compartilhamentode tarefas

De idéia simples:– Quando um agente têm várias tarefas a fazer, ele

recruta a ajuda de outros agentes com poucas ou nenhuma tarefa

Os principais passos são:– Decomposição

– Alocação

– Execução

– Síntese dos resultados

– Cada um pode ser trivial

Compartilhamento em ToH

Decomposição:<figura 3.3>

Alocação:– Como os agentes são igualmente competentes, a

alocação resume-se a escolher randomicamente um deles Execução/realização:

– As tarefas são recursivamente decompostas até que o estado inicial e final sejam o mesmo

Síntese dos resultados:– Quando um agente resolve um problema, ele passa a

solução para o de cima, que irá utilizá-la para encontrar sua própria solução

Compartilhamento de tarefasem sistemas heterogêneos Com várias habilidades e tarefas,

alocação de tarefa não trivial Alocação não depende apenas de

habilidade como também de carga Então deve ser dinâmica Exemplo de método de alocação

dinâmica: redes contratuais

Rede Contratual (Contract Net)

Broadcast Contracting Retry Announcement Revision Alternative Decompositions

E’ bom elaborar com Fig. 2.6

Tarefas interdependentes

Planejamento de sub-tarefas não pode ser inteiramente paralelizado como nas ToH

Conhecer estado inicial de uma subtarefa pode depender do plano construído para outra

As vezes a interdependência surge apenas durante a execução

Compartilhamentodos Resultados

Resultados diferentes para a mesma tarefa ?!?

Aspectos:– Confiabilidade– Completude– Precisão– Tempo de resposta

Compartilhamentodos Resultados

Cada agente manda todos seus resultados parciais para todos os outros agentes?– ex, spamming generalizado

Se for o caso, agentes podem consumir maioria dos seus recursos assimilando resultados recebidos e até impossibilitar encontrar uma solução

Como selecionar quais resultados mandar para quem quando?

Cooperação funcionalmente acurada

ToH: confiabilidade, completude e precisão garantidas, cooperação apenas para atingir eficiência

DVM: – cooperação necessária para atingir

confiabilidade, completude e precisão– através de troca de hipóteses parciais– como combinar essas hipóteses parciais em uma

solução completa?– como reificar hipóteses parciais inconsistente?

Functionally Accurate Cooperation

Espera-se que a troca leve a algum agente ter informação suficiente para chegar a solução

É necessário tomar certas decisões para evitar:– overhead de comunicação devido à grande quantidade de dados– Computação desnecessária (perdida/wasted)

Por exemplo:– Distração – todos os agentes explorando a mesma parte do espaço de

busca Possíveis soluções

– Limitar a comunicação– Dar aos agentes um grau de “desconfiança” na hora de assimilar ou

reagir a informações dos outros

Repositórios Compartilhadose Busca Negociada

Único repositório compartilhado de resultados parciais evita sobrecarga de comunicação

Muitas vezes pode ser formulado como problema de satisfação de restrições distribuído

Diferenças

Juntar com precedente

Não se supõe que os agentes sabem quais restrições são afetadas por suas escolhas– Motiva a utilização de um repositório

compartilhado Os agentes podem relaxar restrições num

momento crítico– Motiva a utilização de uma heurística para

controlar a busca distribuída

Busca heurística distribuída com restrições (pode tirar)

Problemas de satisfação de restrições também se devem a a contenção de recursos

Em vez de um repositório, associa-se um agente a cada recurso, dando a ele o poder de restringir a utilização de recursos. Esta estratégia possui duas formas:– Programação orientada ao mercado

agentes suportam a busca por equilíbrio de acordo com uma alocação eficiente dos recursos

– Permitir aos recursos computarem suas “aggregate demands” por exemplo, DCHS

Estruturação Organizacional

Redo from scratch or scrap Quando não pode-se suportar um

repositório compartilhado ou quando problem-solving não é equivalente a resource scheduling, uma estratégia alternativa para reduz comunicação é explorar a estrutura de decomposição de tarefas

Em DVM, por exemplo, agentes vizinhos devem se comunicar quando detectarem atividade em suas fronteiras

Estruturação Organizacional

Estrutura organizacional define:– regras– responsabilidades– preferências– controle e comunicação entre os agentes

Alocação de tarefas e prioridades em termos de papeis organizacionais (organograma)

Define:– interesse dos agentes em resultados parciais

procedentes de outros– confiabilidade desses resultados

Estruturação Organizacional

Geralmente implementadas com regras:– padrão de resultado parcial padrão de ação

Escolher estrutura organizacional envolve geralmente em si uma busca complexa

Estratégias de Comunicação

Estruturas organizacionais podem indicar quem

geralmente está interessado em quais recursos,

mas ignora aspectos temporais

É preciso encontrar um equilíbrio entre– mandar todos os resultados parciais

– mandar apenas localmente resultados completos

Dependendo do problema pode fazer mais

sentido enviar pedidos do que comunicar

resultados

Distributed Planning

Planejamento Distribuído

Caso particular de resolução distribuída de problemas– onde o problema é fazer um plano

Exatamente o que é distribuído ?!?!– a execução do plano?– a elaboração do plano?– ambos?

Planejamento centralizado de planos distribuídos

plano executado de forma distribuída embora seja criado de maneira centralizada

as ações que não necessitam de ordem podem ser executadas de forma paralela

um agente coordenador centralizado pode gerenciar a execução dessa tarefas em paralelo

Planejamento centralizado de planos distribuídos

1. Gerar um plano de ordem parcial com o número mínimo possível de restrições de ordenamento

2. Decomponha o plano em subplanos de maneira que a minimizar a sobreposição de subplanos

3. Inserir ações de sincronização entre os subplanos

4. Alocar os subplanos para os agentes (task-passing)

5. Início da execução e monitoramento do processo.

Planejamento centralizado de planos distribuídos

Passamos a ter o objetivo:– encontrar entre todos os planos, o que pode ser

decomposto e distribuído de forma mais eficiente

Impactos causados pela estrutura de comunicação:– as ações de sincronização, canais de comunicação

podem deixar a execução distribuída mais lenta que a centralizada

– na prática decompor planos apenas a partir de um tamanho mínimo

Planejamento distribuído de planos centralizados

Tem sua utilização quando os planos são complexos

Exigem a colaboração vários especialistas Compartilhamento de tarefas e resultados

também relevantes ex, plano construído pela colaboração de 3

planejadores:– um de propósito geral– um especializado para raciocínio geométrico– um especializado para escalonamento

Planejamento distribuído de planos distribuídos

não existe um plano global da tarefa em nenhum ponto do sistema

apenas planos parciais de relevância local mesmo assim, compatibilidade global entre esses

planos parciais deve ser mantida para evitar conflitos durante a execução e fomentar ajuda mútua sempre que possível 3 técnicas: fusão de planos, construção iterativa de

planos e negociação em planejadores distribuídos

Fusão de planos

cada agente faz seu plano individualmente

depois, eventuais conflitos

têm que ser identificados e resolvidos

análise de alcance– dado um conjunto de estados iniciais

– e um conjunto de ações

– enumerar todos os estados possíveis

– e inserir restrições nas seqüências

– para eliminar os que devem ser evitados

Plan merging

<explicação de como funciona>

Interative plan formation

Negociação em planejamento distribuído

Representação de planos distribuídos

Planejamento e Execução

Conclusões