Resoluo Distribuda de Problemas e Planejamento MultiagentePablo Sampaio e Talita Menezes

Tpicos

IntroduoResoluo Distribuda de ProblemasPlanejamento Clssico e Planejamento MultiagentePlanejamento Centralizado de Planos DistribudosPlanejamento Distribudo de Planos Centralizados Planejamento Distribudo de Planos DistribudosExecuo de Planos DistribudosConcluso

1. IntroduoFoco da aulaAgentes trabalhando em conjunto para resolver um problema comumMotivaesAcelerar a obteno da soluoEx.: agentes em diferentes mquinasDistribuio inerente ao problemaEx.: monitoramento de uma grande rea geogrficaResultados finais sero distribudos entre mltiplos agentesEx.: correios

2. Resoluo Distribuda de ProblemasViso otimista de sistemas multiagentesAgentes benevolentesObjetivos comuns (ou complementares)Exige dos agentesCoerncia: agentes querem trabalhar juntosCompetncia: agentes sabem trabalhar em conjuntoO problema comum pode ser construir um planoPlanejamento multiagente como caso especial de Resoluo Distribuda de Problemas (RDP)

2. Resoluo Distribuda de ProblemasDuas principais classes de estratgias usadas

Diviso de Tarefas (task sharing): um agente com muitas tarefas repassa tarefas ou sub-tarefas a outros agentesCompartilhamento de Resultados (result sharing): agentes compartilham os resultados obtidos da resoluo de uma sub-tarefa

2.1 Diviso de TarefasA soluo obtida hierarquicamente pela diviso de uma tarefa complexa em tarefas menoresPrincipais etapas:Decomposio das tarefas: um agente gera o conjunto de sub-tarefas a ser dividido entre os agentesAlocao das tarefas: atribuio de sub-tarefas aos agentes apropriadosResoluo da tarefa: o agente pode executar a tarefa diretamente ou fazer uma nova diviso de tarefasSntese do resultado: integrao dos resultados parciais gerados pelos agentes

2.1 Diviso de TarefasExemplo: agentes precisam encontrar figuras escondidas numa regioDecomposio: dividir a regio ou as figuras para a buscaAlocao: cada agente cuida de uma rea ou figuraExecuo: buscar quaisquer figuras na regio destinada a ele, ou buscar em toda a regio uma figura especficaSntese: cada agente apresenta as figuras encontradas

2.1 Diviso de Tarefas difcil construir um agente competente em qualquer tipo de tarefaOs agentes possuem diferentes habilidades Sistemas heterogneosHabilidades devem ser consideradas na diviso de tarefas !Escalar agentes sob-demanda, de acordo com sua especialidadeUma aboragem seria manter uma tabela de serviosProblema: e se o agente j estiver ocupado ?

2.1 Diviso de TarefasAdaptaes do Contract-NetContratao via broadcast: Envia uma proposta contendo a especificao do problemaApenas os agentes capazes de resolver e que estiverem em disponibilidade respodemNovas tentativas Quando nenhum agente responder, o contratante anuncia novamente aps um certo tempoReviso do anncioPropostas contm restries sobre os possveis (requisitos de eligibilidade)Requisitos podem ser relaxadosDecomposies alternativasDivide diferentemente o problema original

2.1 Diviso de TarefasNem sempre possvel criar sub-tarefas totalmente independentesEx.: Engenharia de produtosUma abordagemUm gerente acompanha o andamento das sub-tarefasCabe ao gerente solucionar dependncias, repassando os resultados das tarefasProblema - Interdependncias podem se tornar aparentes somente aps iniciada a resoluo da tarefaNecessidade de compartilhar resultados parciais

2.2 Compartilhamento de ResultadosAgentes compartilham informaes relevantes para resoluo dos sub-problemasResultados parciais podem ser trocados entre os agente de modo a resolver problemas de interdependnciaCompartilhamento pode ser:Pr-ativo: agente envia informao por acreditar que essa informao auxiliar outro agenteReativo: agente envia informao como resposta a uma solicitao

2.2 Compartilhamento de ResultadosRetorno em relao performance do grupo:ConfianaDiferentes agentes chegando ao mesmo resultadoCompletudeResultados de sub-problemas cobrem o problema como um todoPrecisoPara refinar sua soluo, um agente precisa saber mais sobre a soluo de outros agentesRapidezO reaproveitamento de resultados parciais de outros agentes pode agilizar a soluo de uma sub-problema

2.2 Compartilhamento de ResultadosProblema: possibilidade de overhead de comunicaoLimitando a comunicaoRepositrios CompartilhadosDiversas alternativas de solues parciaisBusca Heurstica Distribuda com RestriesAcesso s informaes (recursos) de maneira controladaEstruturao organizacionalDefine papis, responsabilidades, etcApenas agentes de papis relacionados se comunicam

3. Relembrando PlanejamentoPlanejamento: elaborao de uma seqncia de aes para alcanar um objetivo

Planejamento ClssicoMundo simples: completamente observvel, determinstico, finito, esttico, discretoConsidera um nico agenteNatureza indiferente ao agente

3. Planejamento ClssicoSTRIPSLinguagem usada para representar problemas de planejamentoEstadosProposies lgicasHiptese do mundo fechadoObjetivosConjuno de literais bsicos positivosAesPr-condiesEfeitos: literais verdadeiros (adicionados) e falsos (removidos)

3. Planejamento ClssicoAlgoritmosPodem ser aplicados algoritmos de buscaGerao de planos de ordem total: aes em ordem rigidamente definidaPOP (Planejador de Ordem Parcial)No imposta nenhuma ordem entre aes independentesPrecedncia para aes em conflitoO resultado um grafo dos planos possveis

z

3. Planejamento MultiagenteMecanismo de coordenao que permite organizar as interaes (futuras) entre agentes de maneira a alcanar um objetivo comumPode ser visto como caso especial de RDPO problema a ser solucionado criar um planoEstende o planejamento clssico para domnios onde vrios agentes podem planejar e/ou agir juntosAmbiente mais complexo: parcialmente observvel, estocstico, dinmico

3. Planejamento MultiagenteElaborao de um Plano Conjunto composto de aes para cada agenteA execuo de todas as partes do Plano Conjunto leva a sociedade a atingir seu objetivo comumDistribuio pode estar presenteNo Planejamento (elaborao do plano)No Plano (tarefas a serem executadas)

3. Planejamento MultiagenteElaborao do Plano Conjunto:

Planejamento Centralizado de Planos DistribudosPlanejamento Distribudo de Planos CentralizadosPlanejamento Distribudo de Planos Distribudos

4. Planejamento Centralizado de Planos DistribudosUm agente coordenador planeja e os demais executamO agente coordenador responsvel porCriar um plano conjuntoIdentificar aes independentesDividir em sub-planosDistribuir tarefas entre os agentesGerenciar a execuo do planoSincronizao, para evitar conflitosCaso especial de Diviso de Tarefas, porm com o uso de tcnicas de planejamento clssico na etapa de decomposio

4. PCPD AlgoritmoDada a descrio STRIPS do mundo, gerar plano de ordem parcial

Decompor em sub-planos, minimizando relaes de ordem entre os sub-planosDecomposio 1:

Decomposio 2:

A decomposio 1 prefervel !

Sub-plano 1: B < C < FSub-plano 2: A < D < EOutras restries: B < ESub-plano 1: B < D < ESub-plano 2: A < C < FOutras restries: B < C e A < D

4. PCPD AlgoritmoInserir aes de sincronizao nos pontos de dependncia dos planos

Alocar sub-planos aos agentes. Se no for possvel, retornar para passo 2 ou 1

Inicia a execuo e monitora o progressoSub-plano 1: B < send(condE) < C < FSub-plano 2: A < D < wait(condE) < EAgente1 Sub-plano 1: B < send(condE) < C < FAgente2 Sub-plano 2: A < D < wait(condE) < E

4. PCPD - AvaliaoVantagensSimplicidade na gerao do planoProblemas de coordenao resolvidos a priori

DesvantagensDependncia do coordenador para realizao do planoConfiabilidade do coordenadorSupe coordenador onisciente

5. Planejamento Distribudo de Planos CentralizadosO planejamento se realiza de maneira distribuda, resultando num nico plano centralizadoDiviso de TarefasO problema divido e repassado a agentes especialistasOs agentes geram planos parciais em paralelo para os sub-problemasOs agentes interagem trocando planos parciaisPlanos parciais podem ser passados seqencialmentePlanos podem ser unidos num nico plano global usando tcnicas de result sharing

5. PDPC ExemplosAtletismo: vrios especialistas planejam a preparao de um atletaNutricionista planeja a dieta do atleta Treinador faz planos de treinamento e decide a estratgia durante a prova

Manufatura (exemplo computacional)Um especialista em geometria analisa a pea a ser manufaturada e gera um plano abstratoUm planejador geral recebe esse plano e acrescenta as operaes de mquina necessriasO plano passado para um especialista em montagem que vai garantir que a execuo do plano

5. PDPC Avaliao VantagensUtiliza as habilidades dos especialistas para construo dos sub-planosProblemas de coordenao podem ser resolvidos antes da execuo

DesvantagensNecessidade de intensa comunicao durante o planejamentoA decomposio adequada do problema pode ser complicada

6. Planejamento Distribudo de Planos DistribudosTanto o processo de planejamento quanto os resultados so distribudosNo existe um plano global da tarefa em nenhum ponto do sistemaAgentes fazem seus planos individuais procurando evitar conflitos entre siO grande problema manter a compatibilidade entre os planos individuaisAgentes podem comunicar planos e objetivos

6. PDPD AvaliaoVantagensTratamento homogneo entre os agentesAgentes agem conforme suas habilidades e interesses

DesvantagensMaior complexidade (implementao, avaliao, ...)Necessidade de intensa comunicao durante o planejamento e execuo

6. PDPD TcnicasTcnicas para Planejamento Distribudo de Planos Distribudos:

Fuso de planos Construo iterativa de planos Negociao de planejadores distribudos

6.1 PDPD Fuso de PlanosMecanismo centralizado de coordenaoCada agente, individualmente, formula planos individuaisNecessidade de garantir que esses planos podem ser executados separadamente sem conflitosDuas fases:Reachability analisis: dados os estados iniciais possveis e as aes aplicveis, identifica os estados do mundo que podem ser alcanadosIdentifica estados indesejveis do mundo e insere restries entre os planos para evitar estes estados

6.1 PDPD Fuso de PlanosAlgoritmo de Georgeff (1983)A partir de um conjunto de planos iniciais gera planos para vrios agentes de forma que no haja conflitos entre eles.Utiliza uma verso aumentada do formalismo STRIPSCada ao definida a partir de:Nome, pr-condies e efeitos (como em STRIPS)Georgeff + Lista de fatos que devem ser verdadeiros durante a execuo da ao (during list)

6.2 PDPD Construo Iterativa de PlanosProblema das abordagens anteriores: s vezes, decises locais dependem das decises de outros agentesExemplo: Agent1 vai empurrar o bloco junto com Agent2Uma soluo: cada agente, ao invs de propor um nico plano, prope um conjunto de planos alternativosEspao de Planos x Plano nicoO processo de planejamento consiste, ento, em uma busca pelos planos (dentre os propostos) que podem ser combinadosVrias tcnicas para isso

6.3 PDPD Negociao em Planejamento DistribudoNas tcnicas anteriores, a resoluo de conflitos entre agentes se d de maneira arbitrriaQual agente vai esperar por qual?Soluo: agentes negociam esse tipo de resoluoProtocolo comum: processo de deciso usado para determinar suas posies, concesses e critriosHeurstica: dar preferncia ao agente mais restringidoExemplo: controle de trfego areo (Steeb e Camarata)Sistemas de avies em rota de coliso analisam suas possibilidadesO que tivesse mais opes alternativas mudaria de direo

7. Execuo de Planos DistribudosNecessidade de monitoramento da execuo do plano (coordenao)Tcnicas de Coordenao ps-planejamento:Planejamento de Contingncia: planos alternativosMonitoramento e Replanejamento: repete o ciclo planejar-coordenar-executarTcnicas de Coordenao pr-planejamento:Leis de sociabilidade: proibe certar aes em certos contextosCoordenao de planos em tempo de execuo sem comunicaoCoordenao de planos baseada em observaes

7. Planejamento, Coordenao e Execuo IntercaladosPlanejar continuamente quando:Aspectos do mundo podem mudar dinamicamenteAspectos do mundo so revelados incrementalmenteLimitaes de tempo fazem com que a execuo comece antes do plano ter sido totalmente geradoPlanejamento Global ParcialAgentes fazem planos locais parciais: detalhado e abstratoPlanos parciais abstratos so compartilhados e objetivos globais parciais so indentificadosExecuo: alteraes maiores nos planos locais podem levar a um replanejamentoRealocao de tarefas desproporcionais

8. ConclusoH vrias tcnicas e ferramentas para Planejamento MultiagenteA maioria derivada de tcnicas de RDPDesafio entender quando aplicar cada tcnicaPotenciais aplicaes para PMA:Ambientes multirobsTarefas militaresLogsticaManufaturaDesign de peas/produtos

8. RefernciasWooldridge, M. J.: An Introduction to MultiAgent Systems. John Wiley and Sons, 2002.Weis, G.: Multiagent Systems A Modern Approach to Distributed Artificial IntelligenceRussel, S. Norvig, P.: Inteligncia Artifical (segunda edio)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 IntelligenceMardhana, E.: Overview of Distributed Collaborative Planning: Concepts and Applications

Agentes self-interested tambm podem decidir cooperar diante de um problema comumSub-tarefas so independentes !Exemplo ??Explicar conflito: desfazer o resultado de outra ao j existenteAmbiente: agentes no so mais oniscientes, estocstico porque outros agentes podem mudar o ambiente, e dinmico pq isso pode acontecer enquanto o agente deliberaPlanejamento multiagente como caso especial de Coordenao. Coordenao pode acontecer sem planejamento. Exemplo: jogadores de tnis. Se um subir pra rede o outro desce pra o fundo de quadra.Falar de Planejamento x ExecuoSincronizao: pode fazer um agente esperar at que outro agente termine alguma atividadeO POP um bom ponto de partida porque identifica independncia entre sub-objetivos.Manter relaes de ordem dentro dos planos e no entre elesDependncia: por exemplo, se o coordenador se tornar incomunicvelConfivel: no s quanto capacidade mas quanto honestidade (pode tentar se beneficiar)Onisciente: conhecer no s sobre mundo/objetos relacionados ao problema, como conhecer as capacidades dos agentesVant. 1: Remove necessidade de oniscinciaVant. 2: Devido ao uso de um Plano GlobalDesvant. 1: Devido ao Result SharingDesvant. 2: maior complexidade, precisa considerar as especialidades dos agentes planejadoresSemelhana com o outro algoritmo visto