~~SLIDESHOW~~ ====== Cap. 3: Agentes Dedutivos Racionais====== Sistemas Multiagentes Baseado em “An Introduction to MultiAgent Systems” por Michael Wooldridge, John Wiley & Sons, 2002. Por João Araujo. ===== Arquiteturas de Agentes ===== * Um **agente** é um sistema computacional capaz de **ação** autônoma e **flexível**... * Temas que precisam ser enfrentados para se construir sistemas baseados em agentes... * Três tipos de arquiteturas de agentes: * simbólica/lógica * reativa * híbrida ===== Arquiteturas de Agentes ===== * Queremos construir agentes que apreciem as propriedades de autonomia, reatividade, pró-atividade e habilidade social que falamos anteriormente * Esta é a área de arquitetura de agentes ===== Arquiteturas de Agentes ===== Maes define um arquitetura de agentes como: * "Uma metodologia particular de construir [agentes]. Ela especifica como... o agente pode ser decomposto numa construção de um conjunto de módulos componentes e como estes módulos poderiam interagir. O conjunto total de módulos e suas interações tem que fornecer a resposta para a questão de como o sensor de dados e o estado atual do agente determinam as ações... e o estado futuro do estado interno do agente. Uma arquitetura compreende técnicas e algoritmos que suportam esta medodologia." ===== Arquiteturas de Agentes ===== Kaelbling considera que uma arquitetura de agentes tem que ser: * "Uma coleção específica de módulos de software (ou hardware), tipicamente designado por caixas com setas indicando o fluxo de controle e de dados entre os módulos. Uma visão mais abstrata é como uma metodologia para projetar uma particular decomposição de módulos para uma determinada tarefa." ===== Arquiteturas de Agentes ===== * Originalmente (1956-1985), quase todos os agentes projetados dentro da IA eram agentes de //raciocínio simbólico//. * Sua mais pura expressão propõe que os agentes usem //explícito raciocínio simbólico// para decidir o que fazer * Problemas com o raciocínio simbólico levou a uma reação contra eles - o então chamado movimento dos //agentes reativos//, 1985-presente * De 1990-presente, várias alternativas foram propostas: Arquiteturas híbridas, que tentam combinar o melhor das arquiteturas racionais e reativas ===== Agentes de raciocínio simbólico ===== * O enfoque clássico para construir agentes é vê-los como um tipo particular de sistema baseado em conhecimento e trazer todas as metodologias associadas (desacreditadas???) que tais sistemas sustentam. * Este paradigma é conhecido como IA simbólica * Definimos um agente deliberativo ou arquitetura de agentes como uma das seguintes: * contém um modelo simbólico, representado explícitamente, do mundo * toma decisões ( por exemplo sobre que ações tomar) por meio de raciocínio simbólico ===== Agentes de raciocínio simbólico ===== Se queremos contruir agentes desta maneira, existem dois problemas-chave a serem resolvidos: - O problema da tradução: que é a translação do mundo real em uma descrição simbólica adequada e acurada, no tempo correto para ela ser útil... visão, fala, compreensão, aprendizado - O problema da representação/raciocínio: que é como representar informação simbólica de entidades e processos complexos de um mundo real, e como fazer os agentes raciocinar com esta informação no tempo certo para os resultados serem úteis... representação do conhecimento, raciocínio automático, planejamento automático ===== Agentes de raciocínio simbólico ===== * Muitos pesquisadores acham que nenhum dos problemas está mesmo próximo de ser resolvido * O problema subjacente reside na complexidade dos algoritmos de manipulação de símbolos em geral: muitos ( a maior parte) dos algoritmos interessantes de manipulação de símbolos baseados em busca é //altamente intrátavel// * Por conta desses problemas, alguns pesquisadores têm olhado para técnicas alternativas para construir agentes; olharemos para elas mais tarde. ===== Agentes racionais dedutivos ===== * Como pode um agente decidir o que usar usando a prova de um teorema? * A ideia básica é usar lógica para codificar uma teoria estabelecendo a //melhor// ação a tomar para qualquer situação * Seja: * ρ esta teoria (tipicamente um conjunto de regras) * Δ um banco de dados lógico que descreve o estado atual do mundo * //Ac// um conjunto de ações que o agente pode fazer * Δ ⊢ρφ significa que φ pode ser provado por Δ usando ρ ===== Agentes racionais dedutivos ===== /* tenta encontrar uma ação prescrita explicitamente */ for each α ∈ Ac do if Δ ⊢ρ Do(α) then return α end-if end-for /* tenta encontrar uma ação não excluída */ for each α ∈ Ac do if Δ ⊬ρ ¬Do(α) then return α end-if end-for return null /* nenhuma ação encontrada */ ===== Agentes racionais dedutivos ===== * Exemplo: O mundo do aspirador * Meta do robô é limpar toda sujeira {{:agentes:fig14.png?300&nolink| }} ===== Agentes racionais dedutivos ===== * Uso de 3 predicados do domínio para resolver o problema: - //In(x,y)// o agente está em //(x,y)// - //Dirt(x,y)// tem sujeira em //(x,y)// - //Facing(d)// o agente está de frente para direção //d// * Ações Possíveis: //Ac = {turn, foward, suck}// * Ps: //turn// é virar à direita ===== Agentes racionais dedutivos ===== * Regras para determinar o que fazer: * //In(0,0) Λ Facing(north) Λ ¬Dirt(0,0) --> Do(forward)// * //In(0,1) Λ Facing(north) Λ ¬Dirt(0,1) --> Do(forward)// * //In(0,2) Λ Facing(north) Λ ¬Dirt(0,2) --> Do(turn)// * //In(0,2) Λ Facing(east) --> Do(forward)// * E assim por diante * Usando estas regras (+ outras óbvias), começando em 0,0 o robô limpará tudo. ===== Agentes racionais dedutivos ===== * Problemas: * Como converter a entrada da câmera para //Dirt(0,1)//? * Tomada de decisão assume um ambiente //estático//: racionalidade //calculada// * tomada de decisão usando lógica de primeira ordem é intratável * Mesmo onde usamos lógica proposicional, a tomada de decisão em seu pior caso significa resolver um problema co-NP-completo (más notícias!) ===== Agentes racionais dedutivos ===== * Soluções típicas: * enfraquecer a lógica * usar representações simbólicas não-lógicas * deslocar a ênfase de raciocínio do tempo de execução para o tempo de projeto * Olharemos alguns exemplos com este enfoque ===== Mais problemas... ===== * O "enfoque lógico" que foi apresentado implica em adicionar e remover coisas de um banco de dados * Isto não é lógica pura * As primeiras tentativas de criar um "agente de planejamento" tentaram usar dedução lógica pura para resolver o problema. ===== Sistemas de Planejamento ===== Sistemas de planejamento encontram uma sequência de ações que transformam um estado inicial em um estado objetivo {{:agentes:fig15.png?300&nolink |}} ===== Planejamento ===== * Planejamento envolve temas de ambas Busca e Representação do Conhecimento * Alguns sistemas de planejamento: - Planejamento de Robô (STRIPS) - de experimentos biológicos (MOLGEN) * Para nossos propósitos de exposição, usaremos um domínio bem simples: O Mundo dos Blocos ===== O Mundo dos Blocos ===== * O Mundo dos Blocos (hoje) consiste de blocos de mesmo tamanho sobre uma mesa * Um braço robótico pode manipular os blocos usando as ações: * UNSTACK(a,b) * STACK(a, b) * PICKUP(a) * PUTDOWN(a) ===== O Mundo dos Blocos ===== Também temos predicados para descrever o mundo: * ON(A,B) * ONTABLE(B) * ONTABLE(C) * CLEAR(A) * CLEAR(C) * ARMEMPTY ===== O Mundo dos Blocos ===== {{:agentes:fig16.png?300&nolink |}} ===== O Mundo dos Blocos ===== Em geral:\\ ON(a,b)\\ HOLDING(a)\\ ONTABLE(a)\\ ARMEMPTY\\ CLEAR(a) ===== Fórmulas Lógicas ===== para descrever fatos sempre verdadeiros sobre o Mundo * e claro, podemos escrever verdades lógicas gerais relacionando os predicados [ ∃x HOLDING(x) ] --> ¬ARMEMPTY\\ ∀x [ ONTABLE(x) --> ¬ ∃y [ON(x,y)]]\\ ∀x [ ¬ ∃y [ON(y, x)] --> CLEAR(x) ] * Então... como podemos usar a técnica de prova de teorema para construir planos? ===== Método de Green ===== * Adicione variáveis de estado aos predicados e usa uma função DO que mapeia ações e estados em novos estados: * DO: A x S --> S * Exemplo: DO(UNSTACK(x, y), S) é um novo estado ===== UNSTACK ===== * Então, para caracterizar a ação UNSTACK poderíamos escrever: {{:agentes:fig18.png?300&nolink|}} * Podemos provar que se S0 é {{:agentes:fig19.png?300&nolink|}} \\ então\\ {{:agentes:fig17.png?300&nolink|}} ===== Mais provas ===== * A prova poderia ir mais além, se caracterizarmos PUTDOWN: HOLDING(x,s) --> ONTABLE(x,DO(PUTDOWN(x),s)) * Então poderíamos provar {{:agentes:fig20.png?300&nolink|}} * As ações aninhadas nesta prova construtiva fornece o plano:1. UNSTACK(A,B); 2. PUTDOWN(A) ===== Mais provas ===== * Então, temos em nosso banco de dados: ON(A,B,S0) Λ ONTABLE(B,S0) Λ CLEAR(A,S0)\\ e nossa meta é\\ ∃s(ONTABLE(A, s))\\ podemos usar a prova de teroema para encontrar o plano * Mas poderia provar: {{:agentes:fig21.png?300&nolink|}} ===== O problema do quadro ===== * Como se pode determinar o que //muda// e o que //não muda// quando uma ação é feita? * Uma solução: "Axioma do quadro" que especifica como predicados podem permanecer imutáveis após uma ação * Exemplo - ONTABLE(z, s) --> ONTABLE(z,DO(UNSTACK(x,y),s)) - [ON(m, n, s) Λ DIFF(m, x)] --> ON(m,n,DO(UNSTACK(x,y),s)) ===== Axiomas do quadro ===== * Problema: menos que usemos uma lógica de mais alta ordem, o método de Green nos força a escrever muitos axiomas de quadro * Exemplo: COLOR(x, c, s) --> COLOR(x,c,DO(UNSTACK(y,z),s)) * Queremos evitar isso... precisamos de outro enfoque... ===== AGENT0 e PLACA ===== * Muito do interesse em agentes da comunidade de IA surgiu a partir da noção de Shoham de programação Orientada a Agente (AOP) * AOP é um "novo paradigma de programação baseado numa visão social da computação * A ideia chave de AOP é que devemos programar diretamente os agentes com noções como crenças, obrigações e intenções ===== AGENT0 e PLACA ===== * A motivação por detrás disto é que nós como humanos usamos posturas intencionais como um mecanismo de abstração para representar as propriedades de um sistema complexo. * //Da mesma forma que usamos posturas intencionais para descrever humanos, pode ser útil usar posturas intencionais para programar máquinas// ===== AGENT0 ===== * Shoham sugeriu que um sistema de AOP completo teria 3 componentes: - uma lógica para especificar agentes e descrever seus estados mentais - uma linguagem de programação interpretada para programar agentes - um processo de "//agentificação//" para converter "//aplicações neutras//" (ex. database) em agentes ===== AGENT0 ===== * Somente apareceram resultados para os dois primeiros componentes * A relação entre lógica e linguagem de programação é a //semântica// * Iremos pular a lógica(!) e considerar AGENT0 com a primeira linguagem de AOP. ===== AGENT0 ===== * AGENT0 é implementada como uma extensão de LISP * Cada agente em AGENT0 tem 4 componentes: - um conjunto de capacidades (coisas que o agente pode fazer) - um conjunto de crenças iniciais - um conjunto de obrigações iniciais (coisas que o agente deverá fazer) - um conjunto de regras * O componente-chave, que determina como o agente age, é o conjunto de regras de obrigações ===== AGENT0 ===== * Cada regra de obrigação contém: - uma claúsula de mensagem - uma claúsula mental - uma ação ===== AGENT0 ===== * A cada "ciclo do agente"... - A claúsula de mensagem é comparada contra as mensagens que o agente recebeu - A claúsula mental é comparada com as crenças do agente - se a regra é disparada, então o agente fica obrigado à ação (a ação é adicionada ao conjunto de ações do agente) ===== AGENT0 ===== * Ações podem ser * privadas: uma computação interna, ou * comunicativa: enviando mensagens ===== AGENT0 ===== * Mensagens são limitadas a serem um dos três tipos: * "requests" para fazer uma ação * "unrequests" para reprimir ações * "informs" para passar a informação ===== AGENT0 ===== {{:agentes:agentes3.png?400&nolink |}} ===== AGENT0 ===== * Uma regra de obrigação: COMMIT( ( agent, REQUEST, DO(time, action) ), ;;; msg condition ( B, [now, Friend agent] AND CAN(self, action) AND NOT [time, CMT(self, anyaction)] ), ;;; mental condition self, DO(time, action) ) ===== AGENT0 ===== Esta regra pode parafraseada como: * Se eu recebo uma mensagem de //agente// que pede para fazer uma //ação (action)// no //tempo (time)// e acredito que: * agent é atualmente um amigo * Posso fazer a ação * No tempo time, não estou obrigado a fazer nenhuma outra ação * então obrigue a fazer ação (//action//) no tempo (//time//) ===== AGENT0 e PLACA===== * AGENT0 fornece suporte para multiplos agentes cooperarem e comunicarem, além de fornecer recursos básicos de depuração... * ... ele é, contudo, um protótipo, que foi projetado para ilustrar alguns princípios, em vez de ser uma linguagem de produção * Uma implementação mais refinada foi desenvolvida por Thomas, para sua tese de doutorado, de 1993 * Sua linguagem Planning Communicating Agents (PLACA) tinha a intenção de endereçar um problema sério de AGENT0: a inabilidade dos agentes de planejar e comunicar pedidos para uma ação por meio de metas de alto nível * Agentes em PLACA são programados quase da mesma forma que em AGENT0, em termos de regras de mudança mental ===== AGENT0 e PLACA===== * Um exemplo de regra de mudança mental: (((self ?agent REQUEST (?t (xeroxed ?x))) (AND (CAN-ACHIEVE (?t xeroxed ?x))) (NOT (BEL (*now* shelving))) (NOT (BEL (*now* (vip ?agent)))) ((ADOPT (INTEND (5pm (xeroxed ?x))))) ((?agent self INFORM (*now* (INTEND (5pm (xeroxed ?x))))))) * Parafraseando: se alguém perguntar a você para xerocar algo e você puder, e você não acreditar que eles são VIP ou que você estaria supostamente arrumando livros na estante, então * adote a intenção de xerocar para 5pm e * informe eles de sua recem adotada intenção. ===== METATEM concorrente ===== * METATEM concorrente é uma linguagem multiagente na qual cada agente é programado dando a ele uma especificação em lógica temporal do comportamento que ele deveria exibir * Essas especificações são executadas diretamente para gerar o comportamento do agente * Lógica temporal é a lógica clássica ampliada por operadores modais para descrever como a verdade das proposições muda com o tempo ===== Lógica Temporal ===== {{:agentes:fig22.png?700&nolink|}} ===== METATEM concorrente ===== Por exemplo: * ⬜importante(agentes) Significa "é agora e sempre será verdade que os agentes são importantes" * ◇importante(ConcurrentMetateM) significa "em algum tempo no futuro ConcurrentMetateM será muito importante" * ◆importante(Prolog) significa "algum tempo no passado foi verdade que Prolog foi importante" * (¬amigos(nós)) ⋃ desculpas(você) significa "nós não somos amigos até você se desculpar" * ◯desculpas(você) significa "amanhã (no próximo estado), você se desculpa" ===== METATEM concorrente ===== * MetateM é um framework para executar diretamente especificações de lógica temporal * A raiz do conceito de MetateM é o teorema de separação de Gabbay: Qualquer fórmula arbitrária de lógica temporal pode ser reescrita numa forma logicamente equivalente //passado// => //futuro//. * Esta forma //passado// => //futuro// pode ser usada como regras de execução ===== METATEM concorrente ===== * Um programa MetateM é um conjunto de tais regras * A execução prossegue por um processo de casar continuamente regras contra uma "história" e disparanado aquelas regras cujos antecedentes forem satisfeitos * Os tempos-futuros instanciados consequentemente se tornam //compromissos// que serão subsequentemente satisfeitos ===== METATEM concorrente ===== * A execução é então um processo de gerar interativamente um modelo para a fórmula feita pelas regras do programa * As partes do tempo-futuro das regras instanciadas representam restrições neste modelo ===== METATEM concorrente ===== * Um exemplo de programa MetateM: um controlador de recursos... * ∀x ◉ ask(x) => give(x) * ∀x,y give(y) => (x=y) * A primeira regra se certifica que um "ask" é finalmente seguido por um "give" * A segunda regra se certifica que somente um "give" é executado em qualquer tempo unitário * Existem algoritmos para a execução de programas MetateM que alcançam um de desempenho razoável ===== METATEM concorrente ===== * METATEM concorrente fornece um framework operacional pelo qual sociedades de processos MetateM podem operar e comunicar * Ele é baseado em um novo modelo de concorrência em lógica executável: a noção de executar uma especificação lógica para gerar um comportamento individual do agente * Um sistema MetateM concorrente contém um número de agentes (objetos), cada objeto tem 3 atributos: * um nome * uma interface * um programa MetateM ===== METATEM concorrente ===== * Uma interface do objeto contém dois conjuntos: * predicados do ambiente: correspondem a mensagens que o objeto aceitará * predicados dos componentes: correspondem a messagens que o objeto pode enviar ===== METATEM concorrente ===== * Por exemplo, uma interface para uma objeto pilha (stack): * stack(pop,push))[popped, stackfull] * {pop,push} = predicados do ambiente * {popped, stackfull} = predicados do componente * Se um agente recebe uma mensagem encabeçada por um predicado de ambiente, ele a aceita * Se um objeto satisfaz um compromisso correspondente a um predicado de componente, ele o espalha ===== METATEM concorrente ===== * Para ilustrar a linguagem MetateM concorrente em maiores detalhes, aqui estão alguns exemplos de programas... * Branca de Neve tem alguns doces (recursos) que ela vai dar para os Anões (consumidores de recursos) * Ela dará somente para um Anão por vez * Ela finalmente sempre dará para um anão que peça. ===== Branca de Neve ===== Aqui está o programa da Branca de Neve escrito em MetateM Concorrente: BrancaDeNeve(ask)[give]\\ ◉ask(x) => ◇give(x)\\ give(x) Λ give(y) => (x=y) ===== Anão Ansioso ===== * Um anão "ansioso" pede um doce inicialmente, e então, independente de ter acabado de receber um, ele pede novamente: ansioso(give)[ask]:\\ start => ask(ansioso)\\ ◉give(ansioso) => ask(ansioso)\\ ===== Anão Guloso ===== * Alguns Anões são ainda menos educados: "guloso" pede o tempo todo guloso(give)[ask]:\\ start => ⬜ask(guloso) ===== Anão Educado ===== * felizmente, alguns possuem boas maneiras e "educado" só pede quando "ansioso" e "guloso" tenham comido: educado(give)[ask]:\\ ( (¬ask(educado) //S// give(ansioso)) Λ\\ ( (¬ask(educado) //S// give(guloso))) =>\\ ask(educado) ===== Anão Tímido ===== * e finalmente, "tímido" só pedirá um doce quando ninguém mais tiver pedido tímido(give)[ask]:\\ start => ◇ask(tímido)\\ ◉ask(x) => ¬ask(tímido)\\ ◉give(tímido) => ◇ask(tímido) ===== METATEM concorrente ===== Resumo: * Uma (outra) linguagem experimental * muito boa na teoria... * Básico ambiente desenvolvido em Prolog * Um sistema para MetateM concorrente desenvolvido em C++ * Um framework em Java ===== Agentes de planejamento ===== * Desde o início dos anos 1970 a comunidade de planejamento em IA tem estado proximamente ligada ao projeto de agentes artificiais * Planejamento é essencialmente programação automática: o projeto de uma linha de ação que atingirá determinado objetivo * Dentro da comunidade de IA simbólica, já há muito tempo foi assumido que alguma forma de sistema de planejamento em IA será um componente central em qualquer agente artificial * Construídos principalmente nos trabalhos iniciais de Fikes & Nilsson, muitos algoritmos de planejamento foram propostos e a teoria de planejamento bem desenvolvida * Porém, no meio dos anos 1980, Chapman estabeleceu alguns resultados teóricos que indicavam que planejadores em IA finalmente se tornariam inutilizáveis em qualquer sistema com restrições temporais.