Atividade 4

Criando um Agente para o Water Jug Problem

    Será criado um agente SOAR para resolver um problema de IA clássico: o Water Jug.

Definição do Problema Water Jug: São dados dois jarros vazios. Um suporta cinco galões de água, o outro suporta três galões. Há um poço que tem uma quantidade ilimitada de água, que pode ser usado para encher os jarros de água. É permitido esvaziar um jarro, ou, derramar a água de um jarro em outro. Os jarros não possuem marcações para níveis intermediários de galões de água. A meta é encher o jarro de três galões com apenas um galão de água.

    Para resolver esse problema, usando o SOAR, é preciso defini-lo de tal forma que seja possível representá-lo no SOAR. É preciso definir o espaço de estados do problema: existem dois jarros que podem ser cheios (de vazio até no máximo cinco galões). Supõe-se que o estado inicial do problema seja os dois jarros vazios. E o estado final desejado seja qualquer estado onde o jarro de três galões contenha apenas um galão de água. Será preciso definir operadores que serão usados para transformar um estado em outro. Assim, a partir do estado inicial, usando operadores, o estado final desejado será alcançado.

    No Problema Water Jug, serão definidos três operadores: fill, empty, pour. Que serão usados, respectivamente, para encher um jarro, esvaziar um jarro ou despejar o conteúdo de um jarro em outro. O conhecimento sobre o problema também é importante para solucioná-lo. O SOAR usa esse conhecimento para selecionar um operador, dentre vários propostos, que será aplicado. No SOAR, o conhecimento sobre  a formulação do problema fica separado do conhecimento que é usado nas tomadas de decisão do agente.

    A solução do problema começa com a criação de um estado inicial, seguido pela seleção e aplicação de operadores. Os estados, neste problema, serão representados pelo conteúdo (de água) dos dois jarros. Ou seja, os valores possíveis e desejados em cada jarro: vazio, um galão (desejado), três ou cinco galões.  Esses estados podem ser representados por: (5:0,3:0) os dois jarros estão vazios. Um solução, a partir do estado inicial, pode ser proposta:

(5:0,3:0) Encher o jarro de 3 galões.

(5:0,3:3) Despejar o jarro de 3 no de 5 galões.

(5:3,3:0) Encher o jarro de 3 galões.

(5:3,3:3) Despejar o jarro de 3 no de 5 galões.

(5:5,3:1) Solução

    Formalmente, os estados deste problema serão definidos por: quantidade de água que cada jarro contém (^contents) e a quantidade máxima de água que um jarro pode conter (^volume). Dessa forma, será possível escrever um conjunto de regras (para propor e aplicar operadores) específico para o jarro de 5 galões e outro conjunto de regras para o jarro de 3 galões. E a estrutura de dados da memória de trabalho conterá informações do tipo:

(state <s> ^jug <j1> ^jug <j2>)

(<j1> ^volume 5 ^contents 0)

(<j2> ^volume 3 ^contents 0)

    Também será necessário computar o espaço disponível em cada jarro (^empty) e definir mais um elemento da memória de trabalho, a tarefa que se está tentando aplicar (^name water-jug). Com a descrição da tarefa, as regras que serão criadas poderão ser específicas para aquela tarefa, e, facilmente combinadas com as regras de outras tarefas sem causar interferências.

Criando o Agente

    Neste exemplo, o estado inicial da memória de trabalho será criado por regras através de um operador (initialize-water-jug). O operador possui uma regra que propõe o seu uso, caso nenhuma tarefa tenha sido selecionada (-^name), conforme mostrado abaixo:

sp {water-jug*propose*initialize-water-jug
   (state <s> ^superstate nil -^name)
-->
   (<s> ^operator <o> +)
   (<o> ^name initialize-water-jug)}

    A regra que aplica o operador (initialize-water-jug) cria um jarro de 5 galões vazio (<j>) e outro jarro de 3 galões vazio (<i>) também, criando elementos na memória de trabalho:

sp {water-jug*apply*initialize-water-jug
   (state <s> ^operator.name initialize-water-jug)
-->
   (<s> ^name water-jug ^jug <i> <j>)
   (<i> ^volume 3 ^contents 0)
   (<j> ^volume 5^contents 0)}

Persistência de WMEs

    Após o operador initialize-water-jug ter sido aplicado, não há mais necessidade desse operador continuar na memória de trabalho. Ele deve ser removido para que outros operadores possam ser selecionados. O SOAR remove, de fato, esse operador da memória de trabalho, visto que as condições da regra que propõe este operador não podem mais ser satisfeitas. A persistência de elementos da memória de trabalho (WME's - Working Memory Elements) é resolvida pelo SOAR por meio de uma estratégia. O SOAR faz uma distinção entre WME's gerados por regras que aplicam um operador, e, aqueles WME's que foram gerados por outros tipos de regras.

    Quando operadores são aplicados, as alterações que estes causam na memória de trabalho devem persistir. Isso porque, os operadores estão intimamente relacionados ao próprio sistema para o qual foram criados, ou seja, apenas a aplicação de outros operadores deve causar mudanças nos elementos da memória de trabalho gerados pelo operador aplicado anteriormente. Mas, no caso de outros tipos de regras, estas computam cálculos sobre os WME's atuais sem, de fato, alterá-los. Ou seja, não é necessário persistir essas regras na memória de trabalho. Essas regras devem ser removidas da memória de trabalho, tão logo não se enquadrem no estado corrente da memória de trabalho.

    O SOAR distingue o conhecimento que modifica o estado corrente (gerado pela aplicação de operadores) do conhecimento que apenas computa sobre o estado corrente da memória de trabalho. O SOAR faz isso automaticamente, ou seja, classifica as regras como sendo parte da aplicação de um operador ou não. Uma regra é uma regra de aplicação de operadores se ela testa o operador selecionado e modifica o estado da memória de trabalho. Os WME's criados por tal regra persistem. Esses WME's só podem ser removidos por outras regras que também aplicam operadores, ou, se esses elementos se tornarem desconectados do estado atual (devido a remoção de outros WME's).

    Os WME's criados por outros tipos de regras são removidos da memória de trabalho tão logo as condições da regra não se apliquem mais ao estado corrente da memória de trabalho. Essas regras são aquelas que não aplicam operadores, incluindo aquelas regras que apenas propõe um operador, regras que comparam operadores, regras que elaboram operadores, ou, regras que elaboram o estado corrente da memória de trabalho.

Elaboração de Estado

    Com o intuito de tornar as regras mais simples, o SOAR dispõe de um tipo de regra chamada Regra de Elaboração de Estado. No caso do Problema Water Jug, o operador de inicialização cria jarros que possuem apenas dois argumentos, volume e conteúdo. Seria útil criar um novo tipo de argumento que define o espaço disponível (^empty) em cada jarro. Uma regra, regra de elaboração de estado, será usada para computar o volume disponível em cada jarro, no estado corrente da memória de trabalho. Essa regra testará o estado corrente e criará uma nova estrutura naquele estado. Regras de elaboração de estados criam abstrações úteis combinando outros WME's e representando-as no estado corrente como um novo argumento. Esse novo argumento pode ser testado por outras regras, simplificando a elaboração de regras e tornando mais claro o significado dos WME's na memória de trabalho.

    Uma regra de elaboração será criada para computar o volume disponível em cada jarro. Essa regra pode ser visualizada abaixo:

sp {water-jug*elaborate*empty
   (state <s> ^name water-jug ^jug <j>)
   (<j> ^contents <c> ^volume <v>)
-->
   (<j> ^empty (- <v> <c>))}

    A primeira condição (state <s> ^name water-jug ^jug <j>) testa se o nome do estado é water-jug, ou seja, esta elaboração será aplicada apenas ao Problema Water Jug. Também testa se existe um jarro (^jug <j>) e lhe atribui um atributo ^empty. A ação desta elaboração é criar o argumento e atribuir-lhe um valor correto, por meio da computação de um cálculo (<j> ^empty (- <v> <c>)). Sempre que o conteúdo de um jarro for alterado, pela aplicação de um operador, essa elaboração irá computar um novo valor para o argumento ^empty, substituindo o valor antigo.

Proposição de Operadores

    Para solucionar o Problema Water Jug, são definidos três operadores. Também é necessário definir as regras que propõem esses operadores. O SOAR separa as regras de proposição de operadores, que criam preferências para o uso dos operadores, das regras de controle de busca, que criam outros tipos de preferências. As condições para o uso (proposição) dos três operadores estão listadas abaixo:

Operador fill : Encher um jarro com água da fonte, se o jarro não está cheio.

Operador empty : Esvaziar a água do jarro na fonte, se há água no jarro.

Operador pour : Derramar a água de um jarro no outro, se o primeiro tem água e o outro não está cheio.

    Para definir cada um desses operadores, de forma simplificada, será necessário criar parâmetros para esses operadores. Os parâmetros desses operadores são: nome do operador (^name fill/empty/pour), jarro que está sendo cheio (^fill-jug <j>), jarro que está sendo esvaziado (^empty-jug <j>), jarro que está sendo derramado (^empty-jug <j1>) e jarro que está recebendo essa água (^fill-jug <j2>). As regras para propor esses operadores são descritas a seguir.

Operador fill :

sp {water-jug*propose*fill
   (state <s> ^name water-jug ^jug <j>)
   (<j> ^empty > 0)
-->
   (<s> ^operator <o> + =)
   (<o> ^name fill ^fill-jug <j>)}

    Esta regra testa se o jarro não está cheio (<j> ^empty > 0).

Operador empty :

sp {water-jug*propose*empty
   (state <s> ^name water-jug ^jug <j>)
   (<j> ^contents > 0)
-->
   (<s> ^operator <o> + =)
   (<o> ^name empty ^empty-jug <j>)}

    Esta regra testa se o jarro não está vazio (<j> ^contents > 0).

Operador pour :

sp {water-jug*propose*pour
   (state <s> ^name water-jug ^jug <i> { <> <i> <j> })
   (<i> ^contents > 0 )
   (<j> ^empty > 0)
-->
   (<s> ^operator <o> + =)
   (<o> ^name pour ^empty-jug <i> ^fill-jug <j>)}

    Esta regra testa se um jarro não está vazio (<i> ^contents > 0) e se o outro jarro não está cheio (<j> ^empty > 0).

    Ao rodar o agente, com essas regras para proposição de operadores, apenas a regra que propõe o uso do operador fill terá suas condições iniciais satisfeitas. Pois, os jarros inicialmente criados (pelo operador de inicialização) estão ambos vazios. Isso pode ser um empecilho para encontrar uma solução para um problema, ou seja, a tendência em preferir propor sempre um mesmo operador (naquelas mesmas circunstâncias). O SOAR resolve isso atribuindo uma preferência indiferente (<s> ^operator <o> + =) para todos os operadores. Assim, um operador será selecionado aleatóriamente e evitará que ocorram impasses na solução de um problema pelo agente.

Aplicação de Operadores

    A aplicação dos operadores adiciona ou remove elementos da memória de trabalho, refletindo o estado atual do problema. Sua aplicação também pode causar alterações indiretamente na memória de trabalho, mudando o mundo do agente que será percebido pelos seus sensores. Tais mudanças alteram as preferências pela seleção dos operadores. Assim, isso impede que um mesmo operador seja sempre constantemente aplicado. E outros operadores podem ser propostos para aplicação. As regras para aplicar os operadores do Problema Water Jug são descritas a seguir.

Operador fill :

sp {water-jug*apply*fill
   (state <s> ^name water-jug ^operator <o> ^jug <j>)
   (<o> ^name fill ^fill-jug <j>)
   (<j> ^volume <volume> ^contents <contents>)
-->
   (<j> ^contents <volume> <contents> -)}

    Esta regra substitui o conteúdo, anterior, do jarro pelo valor do seu volume (<j> ^contents <volume> <contents> -). Para isso, é necessário remover o WME anterior da memória de trabalho e criar um novo. Isso porque, não é possível modificar um WME depois dele ter sido criado.

Operador empty :

sp {water-jug*apply*empty
   (state <s> ^name water-jug ^operator <o> ^jug <j>)
   (<o> ^name empty ^empty-jug <j>)
   (<j> ^volume <volume> ^contents <contents>)
-->
   (<j> ^contents 0 ^contents <contents> - )}

    Esta regra altera o conteúdo do jarro, de seu valor anterior, para um valor vazio (<j> ^contents 0 ^contents <contents> -). Também é necessário remover o WME anteriormente criado.

Operador pour :

sp {water-jug*apply*pour*not-empty-source
   (state <s> ^name water-jug ^operator <o>)
   (<o> ^name pour ^empty-jug <i> ^fill-jug <j>)
   (<j> ^volume <jvol> ^contents <jcon> ^empty <jempty>)
   (<i> ^volume <ivol> ^contents { <icon> <= <jempty> })
-->
   (<i> ^contents 0 <icon> -)
   (<j> ^contents (+ <jcon> <icon>) <jcon> - )}

sp {water-jug*apply*pour*empty-source
   (state <s> ^name water-jug ^operator <o>)
   (<o> ^name pour ^empty-jug <i> ^fill-jug <j>)
   (<i> ^volume <ivol> ^contents { <icon> > <jempty> })
   (<j> ^volume <jvol> ^contents <jcon> ^empty <jempty>)
-->
   (<i> ^contents (- <icon> <jempty>) <icon> - )
   (<j> ^contents <jvol> <jcon> -)}

    Esta regra necessita de duas partes para atender a todas as situações possíveis. Que são, despejar a água num jarro que pode contê-la, ou, tentar despejar a água num jarro que não a suporta.

Monitoramento de Estados e Operadores

    O SOAR permite usar regras para monitorar, imprimir, detalhes sobre os operadores que estão sendo aplicados e os conteúdos de cada estado. As regras de monitoramento disparam em paralelo, junto com as outras regras de solução dos problemas, sem interferir com a própria solução do problema pelo agente. Para o Problema Water Jug são definidas quatro regras, três para monitorar cada operador selecionado, e uma para monitorar os estados da memória de trabalho, conforme segue.

sp {water-jug*monitor*state
   (state <s> ^name water-jug ^jug <j> <i>)
   (<j> ^volume 5 ^contents <jcon>)
   (<i> ^volume 3 ^contents <icon>)
   -->
   (write (crlf) | 5:| <jcon> | 3:| <icon> )}

sp {water-jug*monitor*operator-application*empty
   (state <s> ^name water-jug ^operator <o>)
   (<o> ^name empty ^empty-jug.volume <volume>)
   -->
   (write (crlf) |  EMPTY(| <volume> |)|)}

sp {water-jug*monitor*operator-application*fill
   (state <s> ^name water-jug ^operator <o>)
   (<o> ^name fill ^fill-jug.volume <volume>)
   -->
   (write (crlf) |  FILL(| <volume> |)|)}

sp {water-jug*monitor*operator-application*pour
   (state <s> ^name water-jug ^operator <o>)
   (<o> ^name pour ^empty-jug <i> ^fill-jug <j>)
   (<i> ^volume <ivol> ^contents <icon>)
   (<j> ^volume <jvol> ^contents <jcon>)
   -->
   (write (crlf) |  POUR(| <ivol> |:| <icon> |,| <jvol> |:| <jcon> |)|)}

    O comando write é responsável por imprimir as informações sobre os estados e os operadores selecionados.

Reconhecimento do Estado Desejado

    Para reconhecer que o estado desejado, que é a solução do problema, foi alcançado, o SOAR utiliza uma regra para testar se esse estado foi alcançado. No caso do Problema Water Jug, essa regra reconhece quando o jarro de 3 galões contém apenas 1 galão de água. Essa regra imprime uma mensagem, relatando que a solução foi alcançada, e suspende o agente, conforme descrito a seguir.

sp {water-jug*detect*goal*achieved
   (state <s> ^name water-jug ^jug <j>)
   (<j> ^volume 3 ^contents 1)
-->
   (write (crlf) |The problem has been solved.|) (halt)}

Controle de Busca

    O controle de busca da solução de um problema é feito por meio da criação de regras de preferência pelo uso de operadores. Assim, haverá uma maior chance do agente encontrar uma solução para o problema, e fazê-lo de forma rápida, ao invés de uma busca "cega". Criar tais regras pode ser um processo complicado, mesmo para um problema tão simples como este do Water Jug. Para este problema exemplo, a heurística de preferência por operadores será bastante simples. Basicamente: evitar usar novamente o último operador selecionado; evitar esvaziar um jarro que acabou de ser cheio; evitar encher um jarro que acabou de ser esvaziado; evitar derramar, de volta, no outro jarro, a água que acabou de ser derramada num jarro pelo outro jarro. Essas regras estão descritas a seguir.

sp {water-jug*record*operator
   (state <s> ^name water-jug ^operator.name <name>)
-->
   (<s> ^last-operator <name>)}

sp {water-jug*remove*last-operator
   (state <s> ^name water-jug ^last-operator <name> ^operator.name <> <name>)
-->
   (<s> ^last-operator <name> -)}

sp {water-jug*select*fill*empty*worst
   (state <s> ^name water-jug ^last-operator fill ^operator <o> +)
   (<o> ^name empty)
-->
   (<s> ^operator <o> <)}

sp {water-jug*select*empty*fill*worst
   (state <s> ^name water-jug ^last-operator empty ^operator <o> +)
   (<o> ^name fill)
-->
   (<s> ^operator <o> <)}

sp {water-jug*select*pour*pour*worst
   (state <s> ^name water-jug ^last-operator pour ^operator <o> +)
   (<o> ^name pour)
-->
   (<s> ^operator <o> <)}

sp {water-jug*select*fill*pour*after*fill-empty
   (state <s> ^name water-jug ^last-operator << fill empty >> ^operator <o> +)
   (<o> ^name pour)
-->
   (<s> ^operator <o> >)}

    O SOAR não memoriza qual o último operador que foi aplicado. Portanto, deve-se escrever uma regra que grave essa informação. Para gravar essa informação, é necessário criar uma estrutura para armazená-la (water-jug*record*operator), e, remover a antiga estrutura que gravou o último operador selecionado (water-jug*remove*last-operator).

Execução do Water Jug

    A figura abaixo mostra a tela do SOAR Debugger após rodar as produções do agente que soluciona o Problema Water Jug:

    A figura mostra que o problema foi solucionado e que foram selecionados e aplicados alguns operadores na solução deste problema. A última linha antes da mensagem "The problem has been solved" exibe a situação final dos dois jarros (5:5 3:1), ou seja, o jarro de 5 galões está cheio e o jarro de 3 galões contém apenas 1 galão de água. Pode-se observar que, em certa altura, perto do final da solução do problema, o operador empty (262: O: O337 (empty)) foi selecionado e aplicado ao jarro de 5 galões (EMPTY(5)) resultando no jarro de 5 galões vazio (5:0 3:3). Mais adiante, no final da solução do problema, o operador pour foi selecionado (265: O: O346 (pour)) e aplicado ao jarro de 3 galões (POUR(3:3,5:3)), despejando seu conteúdo no jarro de 5 galões e alcançando o estado final (POUR(3:1,5:5)) que soluciona o problema. Expandindo-se as linhas (símbolo "+") é possível analisar as fases de proposição e de aplicação dos operadores. Também é possível visualizar as regras que foram disparadas, ou seja, que tiveram suas condições satisfeitas.

Conclusão

    O SOAR é uma arquitetura para a criação de agentes de uso geral. Conhecendo-se bem o problema que necessita ser solucionado, e formulando-o adequadamente, pode-se criar um agente SOAR capaz de buscar uma solução para este problema. O SOAR utiliza regras (do tipo if-then), no entanto, a principal característica do SOAR é o uso de operadores. As regras são usadas para propor e aplicar operadores. Nisso, o SOAR difere dos sistemas de regras convencionais, que funcionam apenas analisando as condições de uma regra e disparando-a caso suas condições sejam satisfeitas. Além disso, o SOAR trabalha com o conceito de preferência de uso de operadores. Alguns operadores podem ter uma maior preferência de uso numa determinada situação, durante a busca pela solução do problema. O SOAR também possui um mecanismo de aprendizado que atualiza a preferência por certos operadores. Dentre estas e outras características, o SOAR difere bastante da maioria dos sistemas especialistas.