Sistemas Multiagentes Baseado em “An Introduction to MultiAgent Systems” por Michael Wooldridge, John Wiley & Sons, 2002.

Por João Araujo.

• O ponto principal sobre agentes é que eles são autônomos: capazes de agir independentemente, exibindo controle sobre seu estado interno
• Logo: Um agente é um sistema computacional capaz de ação autônoma em algum ambiente para atender seus objetivos projetados.

• Agentes triviais (sem interesse)
  • Termostato
  • Unix daemon (ex. biff)
• Um agente inteligente é um sistema computacional capaz de ação flexível e autônoma em algum ambiente
• Por “flexível”, entendemos:
  • reativo
  • proativo
  • social

• Se é garantido que um ambiente de um programa é fixo, o programa nunca se preocupa com seu próprio sucesso ou falha - ele apenas executa cegamente (ex. o ambiente fixo de um compilador)
• O mundo real não é assim: coisas mudam, a informação é incompleta. Vários (a maior parte?) dos ambientes interessantes são dinâmicos.
• É difícil construir software para domínios dinâmicos: os programas devem levar em conta uma possível falha - perguntar a si mesmo se vale a pena executar!
• Um sistema reativo é aquele que mantém uma constante interação com seu ambiente e responde a mudanças que ocorram nele (em tempo para a resposta ser útil)

• Reagir a um ambiente é fácil (ex. Estímulo –> regras de resposta)
• Mas nós geralmente queremos agentes que façam coisas para nós.
• Daí um comportamento direcionado a um objetivo
• Proatividade = gerar e tentar objetivos; que não reage apenas a eventos; tomar a iniciativa
• Reconhecer oportunidades

• Queremos que nossos agentes sejam reativos, respondendo às condições mutáveis de um modo apropriado (no tempo)
• Que eles trabalhem sistematicamente em prol de objetivos de longo prazo
• Estas considerações podem ser antagônicas
• Projetar um agente que se equilibre entre estes dois comportamentos é um problema de pesquisa em aberto.

• O mundo real é um ambiente multiagente: Não podemos tentar atingir objetivos sem levar os outros em conta.
• Alguns objetivos só podem ser atingidos com a cooperação de outros
• O mesmo se passa em alguns ambientes computacionais: vide Internet
• Habilidade social em agentes é a habilidade de interagir com outros agentes (e possivelmente humanos) via alguma forma de linguagem de comunicação de agenets, que talvez coopere com outros

• mobilidade: a habilidade de um agente se mover numa rede eletrônica
• veracidade: um agente não comunica informações falsas
• benevolência: agentes não têm objetivos conflitantes e cada agente sempre tentará fazer aquilo para o qual foi requisitado

• racionalidade: um agente atua para atingir seus objetivos e nunca atuará de modo a evitar que seus objetivos sejam atingidos - pelo menos se suas crenças permitirem
• aprendizado/adaptação: agentes melhoram seu desempenho com o tempo

• São agentes apenas objetos com outro nome?
• Objetos:
  • encapsulam algum estado
  • comunicam-se via passagem de mensagens
  • têm métodos, correspondendo a operações que podem atuar no seu estado

Principais diferenças:

• agentes são autônomos: possuem uma noção mais forte de autonomia que objetos e, em particular, decidem por eles mesmos por fazer ou não uma ação pedida por outro agente
• Agentes são espertos: capazes de comportamento flexível (reativo, proativo, social) enquanto o modelo de objetos não diz nada sobre tal tipo de comportamento
• agentes são ativos: sistemas multi-agentes são inerentemente multi-thread, i.e. é assumido que cada agente tem ao menos um thread de controle ativo

• Agentes o fazem porque querem fazer
• agentes fazem isso por dinheiro ( Jennings)

• Não seriam agentes apenas um outro nome para sistemas especialistas?
• Sistemas especialistas tipicamente desencarnam uma “expertise” sobre algum domínio (abstrato) do discurso (ex. doenças do sangue)
• Exemplo: MYCIN tem conhecimento sobre doenças do sangue em humanos:
  • Tem conhecimento baseado em regras
  • Um médico pode obter um aconselhamento especialista dando fatos ao MYCIN, respondendo a questões e fazendo perguntas

Principais diferenças:

• Agentes estão situados em um ambiente. MYCIN está alheio ao mundo - a única informação obtida é aquela que veio de perguntas do usuário
• agentes atuam: MYCIN não opera pacientes
• Alguns sistemas especialistas de tempo real são agentes, tipicamente controle de processos

• Não seriam agentes inteligentes apenas um projeto em IA? Construir agentes não é o que IA se propõe?
• IA tem por objetivo construir sistemas que entendam a linguagem humana, reconheçam e entendam situações, usem o senso comum, pensem criativamente, etc. - tudo isso é muito difícil.
• Então, não precisamos resolver toda a IA para construir um agente…?

• Quando construímos agentes, simplesmente queremos um sistema que possa escolher a ação correta a fazer, tipicamente num domínio limitado
• Nós não temos que resolver todos os problemas de IA para construir um agente útil: uma inteligência mínima é um longo caminho.
• Oren Etzioni comentando sobre a experiência comercial do NETBOT, Inc: “Fizemos nossos agentes cada vez mais idiotas… até finalmente eles fazerem dinheiro”

• Um ambiente acessível é aquele do qual o agente pode obter informação completa, acurada, atualizada sobre o estado do ambiente
• A maior parte dos ambientes mesmo com moderada complexidade são inacessíveis (incluindo o mundo físico do dia-a-dia e a Internet)
• Quanto mais acessível um ambiente é, mais simples é construir agentes para ele

• Um ambiente determinístico é um em que qualquer ação tem um único e garantido efeito - não existe incertezas sobre o estado que irá resultar da ação
• O mundo físico pode, para todos objetivos e propósitos, ser considerado não-determinístico
• Ambientes não-determinísticos apresentam grandes problemas para um projetista de agentes

• Em um ambiente episódico, o desempenho de um agente depende do número de episódios discretos, sem ligação com o desempenho do agente em diferentes cenários
• Ambientes episódicos são mais simples da perspectiva do desenvolvedor de agentes porque o agente pode decidir qual ação tomar baseado apenas no episódio atual - ele não precisa pensar sobre as interações entre este os futuros episódios

• Um ambiente estático é um que podemos assumir permanece imutável, exceto pela ação de agentes
• Um ambiente dinâmico é um que tem outros processos atuando nele e que portanto muda fora do controle do agente
• Outros processos podem interferir com as ações dos agentes (como na teoria dos sistemas concorrentes)
• O mundo físico é um ambiente altamente dinâmico

• Um ambiente é discreto se existe um número fixo de ações e percepções nele
• Russel e Norvig dão o exemplo do jogo de xadrez como um ambiente discreto e a direção de um táxi como a de um contínuo
• Ambientes contínuos têm um certo nível de “descasamento” com sistemas computacionais
• Ambientes discretos poderiam, a princípio, serem manipulados por um tipo de “tabela de busca”

Quando explicamos uma atividade humana é frequente o uso de afirmações como as seguintes:

• Jane pegou sua sombrinha porque ela acredita que vai chover
• Marco trabalha pesado porque ele quer possuir um título PhD.

• Estas afirmacões usam a psicologia popular na qual o comportamento humano é predito e explicado pela atribuição de atitudes, tais como crença e desejo (como nos exemplos), esperança, etc.
• As atitudes em tal descrição da psicologia popular são chamadas noções intencionais

• O filósofo Daniel Dennet cunhou o termo “Sistema Intencional” para descrever entidades “cujo comportamento pode ser predito pelo método de atribuição de crenças, desejos e astúcia
• Dennet identifica diferentes graus de sistemas intencionais: “Um sistema intencional de primeira-ordem tem crenças e desejos (etc.) mas não crenças e desejos sobre crenças e desejos. … Um sistema intencional de segunda-ordem é mais sofisticado; ele tem crenças e desejos (e, sem dúvida, outros estados intencionais) sobre crenças e desejos(e outros estados intencionais) - ambos sobre aqueles outros e sobre si mesmos”

• É legítimo e útil atribuir crenças, desejos, e assim por diante, a sistemas computacionais?

Existem ocasiões onde posturas intencionais são apropriadas: “relacionar crenças,livre arbítrio, intenções, consciência, habilidades ou quereres para máquinas é legitimado quando tal relacionamento expressa a mesma informação sobre a máquina que se expressa sobre uma pessoa. É útil quando ajuda a entender a estrutura da máquina, seu comportamento passado ou futuro, ou como corrigi-la ou melhorá-la. Teorias de crenças, conhecimento e desejos podem ser construídas para máquinas mais facilmente que para humanos, e depois aplicados para humanos. Relacionamento de qualidades mentais é mais claro para máquinas de estrutura conhecida tais como termostatos e sistemas operacionais, mas é mais útil quando aplicada para entidades de qual a estrutura é incompletamente conhecida”.

• Quais objetos podem ser descritos por uma postura intencional?
• Grosso modo, tudo pode… considere um interruptor de luz: “É perfeitamente coerente tratar o interruptor de luz como um agente (muito colaborativo) com a capacidade de transmitir a corrente ao seu desejo, que invariavelmente transmite corrente quando ele acredita que nós queremos ela transmitida e não ao contrário; mudar a chave é simplesmente nosso meio de comunicar nossos desejos ” (Yoav Sholam)
• Mas muitos adultos acharão esta descrição absurda! Por que isto?

• A resposta parece ser que, mesmo sendo a postura intencional consistente, … ela não nos acrescenta nada pois nós entendemos o mecanismo suficientemente para ter uma descrição mais simples do comportamento do mecanismo
• Falando diretamente: quanto mais conhecemos sobre um sistema, menos precisamos nos basear numa explicação animista ou intencional do seu comportamento

• Porém, para sistemas muito complexos, uma explicação do seu comportamento pode ser impraticável
• Quando um sistema computacional fica mais complexo, necessitamos de abstrações mais potentes e metáforas que expliquem sua operação - explicações de baixo nível se tornam impraticável. A postura intencional é esta abstração

• Noções intencionais são, deste modo, ferramentas de abstração que nos dão um modo familiar e conveniente de descrever, explicar e prever o comportamento de sistemas complexos
• Lembre-se: Os maiores desenvolvimentos em computação foram baseados em novas abstrações:
  • abstração procedural
  • Tipos abstratos de dados
  • objetos

• Agentes e agentes como um sistema intencional representam uma abstração avançada, crescente e potente.
• Logo, teóricos de agentes começam de uma (forte) visão de agentes como sistemas intencionais: uma na qual a mais simples e consistente descrição necessita uma postura intencional.

• Esta postura intencional é uma ferramenta de abstração - um modo conveniente de falar com sistemas complexos, o qual nos permite predizer e explicar seu comportamento sem termos que entender como o mecanismo realmente trabalha
• Atualmente, desde que a Ciência da Computação se preocupa em procurar mecanismos de abstração (veja abstração procedural, objetos,…) por que não usar atitudes intencionais como uma ferramenta de abstração em computação, para explicar, entender e, crucialmente, programar sistemas complexos?
• Este é um argumento forte em favor de agentes

• Outros 3 pontos em favor desta ideia:
  1. Caracterizando agentes: nos fornece um forma não-técnica e familiar de entender e explicar agentes
  2. Representações aninhadas: Nos dá o potencial de especificar sistemas que incluem a representação de outros sistemas. É universalmente aceito que tal representação aninhada é essencial para agentes que devem cooperar com outros agentes
  3. Sistema Pós-declararativo : Esta visão de agentes nos leva a um tipo de programação pós-declarativa

• Na programação procedural, nós dizemos exatamente o que o sistema deveria fazer
• Na programação declarativa, nós afirmamos algo que queremos seja realizado, damos ao sistema informação geral sobre as relações entre os objetos e deixamos um mecanismo de controle construído descobrir como fazê-lo
• Com agentes, damos uma especificação bem abstrata do sistema e deixamos o mecanismo de controle descobrir o que fazer, sabendo que ele irá atuar de acordo com algumas teorias de solução

• outros pesquisadores de mais de uma linha principal de pesquisa na computação adotaram ideias semelhantes:
• Na teoria de sistemas distribuídos, lógica do conhecimento é usada para desenvolver protocolos baseados no conhecimento

• O raciocínio é que quando estamos construindo protocolos, algum deles vai encontrar raciocínios como:
  • SE processo i sabe que o processo j recebeu uma mensagem m1
  • ENTÃO processo i deveria enviar ao processo j a mensagem m2
• na teoria SD, o conhecimento é “pé-no-chão” - dando uma interpretação precisa em termos de estado de um processo. Examinaremos este ponto mais tarde.

• Vamos assumir que o ambiente pode estar em qualquer um dos estados de um conjunto finito E, de estados discretos e instantâneos:
  

• Assumindo que os agentes têm um conjunto de possíveis ações disponíveis para eles, que transformam o estado do ambiente. Faça:
  

• Um run (uma execução) r de um agente em um ambiente é portanto, uma sequência intercalada de estados e ações:

Faça:

• ℜ ser o conjunto de todas as possíveis sequências finitas (sobre E e Ac); (conjunto de runs possíveis)
• ℜ^Ac ser o subconjunto destas que terminam com uma ação; e
• ℜ^E ser o subconjunto destas que terminam com um estado do ambiente.

• Para representar o efeito que as ações do agente terão no ambiente, usamos a função de

transformação de estado:

• Note que os ambientes são:
  • dependentes do seu histórico
  • não determinísticos

• Se τ(r) = Ø (onde r é assumido terminar com uma ação), então não existe possibilidade de um estado sucessor para r. Dizemos, então, que o sistema terminou seu run.
• Formalmente dizemos que um ambiente Env é uma tripla Env = (E, ℯ₀, τ), onde E é um conjunto de estados do ambiente, ℯ₀ ∈ E é um estado inicial, e τ é uma função de transformação de estados.

• Um agente é uma função que mapeia runs para ações:

• Um agente faz uma decisão sobre qual ação realizar, baseado no histórico do sistema que ele tem testemunhado até o momento atual. Faça AG ser o conjunto de todos os agentes.

• Dizemos que um sistema é um par contendo um agente e um ambiente
• Qualquer sistema terá associado com ele um conjunto de possíveis runs; nós denotamos o conjunto de runs de um agente Ag no ambiente Env por ℜ(Ag, Env).
• Assumiremos que ℜ(Ag, Env) contém somente runs terminados

• Formalmente uma sequência (ℯ₀,α₀,ℯ₁,α₁,ℯ₂,…) representa um run de um agente Ag no ambiente Env = (E, ℯ₀, τ) se
  1. ℯ₀ for o estado inicial de Env;
  2. α₀ = Ag(ℯ₀); e
  3. para u > 0,
     • ℯ_u ∈ τ ((ℯ₀,α₀,…,α_u-1)) onde
     • α_u = Ag((ℯ₀,α₀,…,ℯ_u))

• Certos tipos de agente decidem o que fazer sem referenciar seu histórico. Suas decisões são baseadas apenas no presente.
• Estes são os chamados agentes puramente reativos

• Nosso termostato é um exemplo desses agentes

• Agora introduzimos o sistema de percepção:

• A função see captura a habilidade do agente de observar seu ambiente, enquanto a função action representa o processo de tomada de decisão do agente.
• A saída da função see é uma percepção – uma entrada perceptiva. see : E → Per que mapeia estados de ambientes para percepções, e action é uma função action : Per* → Ac

Consideraremos agora agentes que mantêm um estado:

• Agentes que mantém uma estrutura de dados para guardar um estado interno ou histórico. Faça I ser o conjunto de todos os estados internos do agente.
• A função see para este tipo de agente não é alterada. see : E → Per
• A função de seleção de ação é definida como um mapeamento. action : I → Ac, a partir de estados internos para ações. Uma função adicional next é introduzida, que mapeia um estado interno e uma percepção para um estado interno:next: I x Per → I

1. O agente inicia em algum estado interno inicial i₀.
2. Ele observa o estado ℯ de seu ambiente, e gera uma percepção see(ℯ).
3. O estado interno do agente é atualizado via função next como next(i₀, see(ℯ)).
4. A ação selecionada pelo agente é action(next(i₀,see(ℯ))).
5. Vá para 2.

• Construímos agentes para executar tarefas para nós
• A tarefa deve ser especificada por nós.
• Mas queremos dizer aos agentes o que fazer sem dizer como fazer.

• Uma utilidade é um valor numérico representando quão bom um estado é: o maior valor é o melhor. A tarefa do agente é trazer estados que maximizem a utilidade
• uma especificação de tarefa pode ser uma função: u: E → ℝ que associa um valor real a cada estado do ambiente.

• Mas o que é o valor de um run…
  • A pior utilidade do estado encontrado?
  • A melhor utilidade do estado encontrado?
  • A soma de utilidades dos estados encontrados?
  • a média?

• A principal desvantagem dessa proposta é que ela atribui utilidade para estados locais, o que torna difícil especificar visões de longo prazo.

• Para contornar estes problema, podemos especificar uma tarefa como uma função que atribui utilidade não para estados individuais, mas para runs:
  • u: ℜ → ℝ
• Tal enfoque tem uma visão de longo prazo inerente
• Outras variações incorporam a probabilidade de diferentes estados emergirem

• Dificuldades com enfoque de utilidade para runs:
  • De onde vêm os números?
  • nós não pensamos em termos de utilidade!
  • difícil de formular tarefas nestes termos.

• é um ambiente de duas dimensões onde existem agentes, azulejos, obstáculos e buracos.
• Um agente pode mover-se em quatro direções, e se ele está próximo a um azulejo, ele pode pegá-lo.
• Buracos devem ser preenchidos pelo agente com os azulejos. O agente ganha pontos a cada buraco preenchido.
• O ambiente é dinâmico, iniciando em um estado aleatório e muda durante o tempo, com aparecimento e desaparecimento aleatório de buracos.

• O desempenho de um agente em um run particular é definida como:

• De Goldman and Rosenschein, AAAI-94:

• Faça P(r | Ag, Env) denotar a probabilidade que um run r ocorra quando o agente Ag está localizado no ambiente Env como

• então um agente ótimo Ag_opt no ambiente Env é definido como:

• Alguns agentes não podem ser implementados em alguns computadores. Uma função Ag : ℜ^E → Ac pode exigir mais do que a memória disponível.
• Deixe-nos escrever AG_m para denotar o subconjunto de AG que podem ser implementados numa máquina m:
  • AG_m = { Ag | Ag ∈ AG e Ag possa ser implementado em m}
• Podemos substituir a equação 1 com a seguinte, que define mais precisamente as propriedades do agente desejado Ag_opt:

• Um caso especial de atribuição de utilidade é o de atribuir 0 (falso) e 1 (verdade) a um run
• Se o run tem atribuição 1, o agente teve sucesso, senão, falhou.
• Isto é o que chamamos de especificações de predicados de tarefas.
• Denotamos uma especificação de predicado de tarefas por ψ. Deste modo, ψ: ℜ → {0, 1}

• Um ambiente de tarefas é definido pelo par (Env, ψ), onde Env é um ambiente e ψ: ℜ –> {0, 1} é um predicado sobre runs. Faça ΤE ser o conjunto de todos os ambientes de tarefa.
• Um ambiente de tarefa especifica:
  • as propriedades do sistema que o agente irá habilitar (o ambiente Env);
  • o critério pelo qual um agente será julgado de ter sucesso ou falhar na sua tarefa (a especificação de ψ)

• Dado um ambiente de tarefa (Env, ψ), nós escrevemos ℜ_ψ(Ag, Env) para denotar o conjunto de todos os runs do agente Ag no ambiente Env que satisfazem ψ:

• Então dizemos que um agente Ag tem sucesso na tarefa (Env, ψ) se

• Faça P(r | Ag, Env) denotar a probabilidade do run r ocorrer se o agente Ag for colocado no ambiente Env.
• Então, a probabilidade P(ψ | Ag, Env) que ψ é satisfeita por Ag em Env poderia simplesmente ser

• As tarefas mais comuns são tarefas de realização e de manutenção

1. Tarefas de realização são aquelas da forma “atinja um estado do negócio φ”
2. Tarefas de manutenção são aquelas da forma “mantenha o estado do negócio ψ”

• Uma tarefa de realização é especificada por um conjunto G de estados “good” ou “goal”: G ⊆ E
• O agente tem sucesso se é garantido atingir um desses estados (Não importa qual - Todos são considerados igualmente bons)

• Uma tarefa de realização é especificada por um conjunto B de estados “bad” : B ⊆E
• O agente tem sucesso em um ambiente particular se ele manipula para evitar todos os estados em B - Se ele nunca faz uma ação que resulta na ocorrência de qualquer estado de B

• Síntese de agentes é programação automática: o objetivo é ter um programa que tomará como entrada um ambiente de tarefa, e gerará automaticamente um agente que terá sucesso nesse ambiente. (imagine ┴ como sendo o null de Java)

• Agora, nós dizemos que um algoritmo de síntese é
  • sound (sadio, válido) se, sempre que ele retorne um agente, este agente tem sucesso no ambiente de tarefa que é passado como entrada;
  • complete se for garantido retornar um agente, sempre que existir um agente possível, mas não garante que este agente fará seu trabalho corretamente.

• Formalmente, um algoritmo de síntese é sound se ele satisfaz a seguinte condição:

• e completo se