Atividade 4

Criando um Agente para o Water Jug Problem

O Water-Jug problem é um clássico problema computacional na área da Inteligência Artificial que tem como objetivo encher e esvaziar Jarros (jugs) de forma que em um determinado momento os jagos possuam alguma configuração específica no que diz respeito ao volume de líquido que contém. No caso do tutorial, é proposto um problema com dois jarros: um com capacidade de 3 e outro de 5 litros. Os jarros não possuem medida e só existem três operações possíveis de serem feitas:

1. Encher um Jarro até seu volume total
2. Esvaziar completamente um Jarro
3. Passar o conteúdo de um jarro para outro até que o Jarro origem esteja vazio ou que o Jarro destino esteja cheio.

Assim, nosso problema a princípio necessitará de objetos que representem os jarros e operadores que representem as três possíveis ações.A idéia é que a cada passo de execução uma das três ações seja executada de forma a mudar o estado atual do problema até que a situação final desejada seja encontrada. 

Persistência de WMEs

Para que a execução de um agente não consuma toda a memória do ambiente onde está sendo executado, SOAR utiliza mecanismos de remoção automática de working memory elements segundo regras próprias. Esta capacidade facilita nosso trabalho, uma vez que devemos nos preocupar apenas na manutenção de elementos que adicionamos na working memory para alteração do estado real (semântico) do problema.

Desenvolvemos nosso sistema de forma que, quando uma determinada condição for alcançada, um operador seja adicionado na working memory para que possa ser selecionado e aplicado. Uma vez que o estado do sistema muda pela aplicação de algum operador, SOAR retira de sua workning memory todos os operadores cujas regras de aplicação não sejam mais satisfeitas. 

Se, contudo, um operador alterar a memória de trabalho em sua aplicação, este elemento não será automaticamente removido pela lógica automática do SOAR. 

No geral, working memory elements criados a partir da aplicação de operadores (operator-support) não serão removidos pelo SOAR, enquanto aqueles que não o são (instantiation-support) são removidos uma vez que deixam de ser válidos quando comparados ao estado atual.

Elaboração de Estado

Para facilitar a manutenção de código e desenvolvimento existe em SOAR o conceito de Elaboração de Estado. Elaborações são conceitos abstratos deduzidos a partir do estado atual do problema. No exemplo do Water Jug Problem, é criada uma elaboração que reprezenta a quantidade de volume não ocupado que um jarro possui. Dados um volume máximo e volume ocupado atualmente, a elaboração empty nos fornece o volume não ocupado do jarro. Isso é útil porque evita que necessitemos a todo momento atualizar o valor de um atributo que pode ser deduzido a partir de um estado, diminuindo o código necessário e facilitando a legibilidade do mesmo. Teoricamente tudo o que se faz com elaborações poderia ser feito sem elas, mas seu uso é uma praticidade bem-vinda. A seguir a imagem no Visual Soar da criação de uma elaboração e seu efeito na execução através do Soar Debug.

_{clique nas imagens para melhor visualização}

Proposição de Operadores

Cada ciclo de execução possui um passo especificamente para proposição de operadores.Neste passo, regras de proposição de operadores serão ativadas caso suas condições condizam com o estado atual do sistema. A seguir, imagens que representam

Aplicação de Operadores

À fase de proposição dos operadores se segue a fase de decisão. Nesta fase, as preferências dos operadores que existem na memória de trabalho são avaliadas e um dos operadores é selecionado e aplicado. Se não há preferência de um operador sobre outro, a escolha entre os dois será aleatória. Cabe ao desenvolvedor induzir seu agente a aumentar ou diminuir preferências a operadores conforme o estado da memória de trabalho é alterado.

A seguir uma imagem que apresenta código no Visual Soar com proposições e aplicações de operadores para o Water Jug Problem.

_{clique na imagem para melhor visualização}

Monitoramento de Estados e Operadores

Todo desenvolvimento de software é consideravelmente facilitado quando se aplicam métodos para monitoração do fluxo de execução. Felizmente, SOAR nos permite, através de regras simples, exibir informações customizadas a respeito do estado do agente durante sua execução. Segue um exemplo baseado no Water Jug Problem de como regras deste tipo podem ser formadas. No exmplo, foi criada uma regra que será executada sempre que houver o estado com nome water-jug e ele imprimirá o valor do conteúdo de cada Jarro neste momento. As regras seguintes disparam quando seu operador relacionado estiver selecionado, imprimindo informações a respeito do que está sendo feito.

_{clique na imagem para melhor visualização}

Reconhecimento do Estado Desejado

Como estamos tratando da resolução de um probema, é necessário que o agente consiga identificar que o problema foi resolvido. Isto deve ser feito através da análize do estado atual. No caso do Water Jug Problem, o estado alvo é aquele em que o Jarro de capacidade 3 litros contenha exatamente 1 litro de líquido.

Em questão de código, poderíamos criar uma regra que verifica exatamente esta condição. Contudo, para que haja uma maior generalização, é melhor que seja criado na memória de trabalho um elemento que represente este estado final. Desta forma, podemos 'mudar o rumo' de nosso agente alterando o estado final em uma situação onde isso faça sentido.

Segue uma imagem que apresenta para o problema do Water Jug a definição do estado almejado (em initialize-waterjug) e a regra que verifica se a condição foi alcançada, além do Data Map atualizado para suportar as alterações.

_{clique na imagem para melhor visualização}

Controle de Busca

Para o Water Jug Problem uma execução completamente aleatória de operadores tem capacidade de encontrar um resultado em poucos segundos. Contudo, teoricamente, esta execução poderia durar eternamente. Se apenas os operadores de encher e esvaziar jarros fossem aplicados, este cenário indesejado aconteceria.

Para evitar este cenário e obter resultados em tempos menores, devemos controlar a busca usando mecanismos de preferência por operadores. Um exemplo rudimentar desta aplicação, utilizado no tutorial, consiste evitar que uma operação desfaça o que a anterior fez. Isso inclui não esvaizar um Jarro que na operação anterior forB a cheio, não encher um jarro que na operação anterior fora esvaziado e não derramar de um Jarro A para um Jarro B se a operação anterior consistiu em derramar de para A.

Para isso foi necessário criar um mecanismo, também rudimentar, de armazenamento da operação aplicada anteriormente. Para isso, foram criadas regras de registro e remoção da operação utilizada anteriormente para cada uma das operações. A figura a seguir ilustra o código utilizado.

Com o conhecimento da última operação realizada pelo agente, foi possível criar regras que diminuissem a preferência de operadores indesejados. A seguir, o código de tais regras e o Data Map atualizado:

Com a aplicação destas regras muito simples foi possível verificar uma boa melhora no tempo para se encontrar o estado desejado. A figura a seguir ilustra este fato. Note que foram necessários apenas 13 ciclos de busca para encontrar o resultado enquanto na última execução foram necessários 90.

Conclusão

O tutorial 1 do SOAR permitiu um primeiro contato com o ambiente de desenvolvimento e as idéias fundamentais por trás do paradigma. Foi possível entender também que SOAR é muito versátil e capaz de resolver problemas de busca genéricos. Seria possível, contudo não sem um grande esforço, desenvolver um agente que seja capaz de, por exemplo, aprender a jogar diferentes jogos de tabuleiros e progressivamente melhorar seu desempenho. Esta é uma característica que supera sistemas especialistas como aqueles programados para jogar um jogo específico, como xadrez. Por outro lado, a generalização de uma tarefa como aprender a jogar um jogo de tabuleiro e aplicar esta lição num jogo deverá resultar em um jogador menos eficiente do que aquele sistema especialista desenvolvido com conhecimento previo específico do jogo (considerando-se que o tempo de desenvolvimento para ambos os sistemas tenha sido o mesmo).

De uma forma ou de outra, SOAR é um sistema com um leque infinito de possibilidades para resolução de problemas dos mais diferentes tipos e com possivelmente pouca codificação.

Para fazer o download de um arquivo zip com screenshots do passo a passo da execução do tutorial clique aqui. 
Para fazer o download de um arquivo zip com o projeto criado através do tutorial clique aqui.