You are here

Home » Aluno 10 » Aluno João Paulo Sims Baena

Aula 2 - Soar, Tutorial 1

published by aluno10 on Fri, 03/15/2013 - 02:34

Programa Hello-World

Na aula 2 a primeira atividade proposta foi o desenvolvimento de um programa hello-world, para o primeiro contato com a sintaxe, e o conceito de regras e ações do Soar.

O programa escrito a modo do Hello-world do tutorial ficou da seguinte maneira:
 

#Declaração de uma nova Soar Producion contendo uma regra chamada "escrevendo o nome"

sp {escrevendo-nome
#No caso de existir um estado nesse agente
   (state <s> ^type state)
-->
#Estando safisfeita a condição acima, as ações abaixo são executadas: Nome é printado e o SOAR para.
   (write |Primeiro programa SOAR de Joao Paulo|)
   (halt)
}
 
Carregando e executando o arquivo escrevendo-nome.soar no Soar Debugger tivemos o seguinte resultado:
 

 

 

Memória de Trabalho (Working Memory)

A mémoria de trabalho no Soar é a contém toda informação dinamica a respeito do mundo exterior além de sua lógica interna, o raciocínio de decisão. Ela está estruturada através de grafos a partir de estados, e seus elementos são compostos de um identificador de estado, um atributo e um valor.

Na figura abaixo, temos o exemplo da representação de um objeto na memória de trabalho. Um objeto é definido por um estado e todas suas augmentações. Augmentações são os elementos de mémoria que compõe um objeto.

No exemplo abaixo temos três desses elementos:

EstadoAtributoValor
B1nameA
B1colorblue
B1typeblock

No caso estudado, temos um objeto de tipo bloco, cor azul e nome A. Na representação do Soar essa descrição fica da seguinte maneira:

(B1 ^name A ^color blue ^type block)

Um valor pode ser de dois tipos: constante, como no exemplo acima, ou um identificador. No segundo caso, o valor é um sub-estado, podendo ter atributos e valores próprios, formando sub-estruturas na memória de trabalho.

Quando criamos um novo agente, o Soar o inicializa automaticamente a seguinte estrutura:

Essa estrutura contem o objeto I1, contendo os elementos (I1 ^output-link I2) e (I1 ^input-link I3). É através dessa estrutura que o agente do Soar irá interagir com o mundo externo, através de funções de entrada e saída.

As funções de entrada, processadas no inicio de cada ciclo de execução do Soar, vão adicionar ou apagar elementos na memória de trabalho em reação a mudanças captadas no mundo exterior. As funções de saída, processadas no final de cada ciclo de execução, vão tentar realizar mudanças ao mundo exterior.

 

Agentes simples utilizando operadores

Operadores são elementos incluídos na memória de trabalho para realizarem açoes que podem ser externas ou dentro da memória de trabalho do agente. Por realizarem ações, são através deles que o Soar tomará suas decisões.

Para criarmos esses elementos na memória de trabalho, utilizamos as regras de proposição. Estas testam propriedades do estado atual e criam uma representação do operador na memoria de trabalho. Os operadores criados viram candidatos a serem selecionados pelo Soar na fase chamada de procedimento de decisão. Tendo sido selecionado um operador com sucesso, passamos a fase de utilização do operador selecionado.

Esse processo é ilustrado pela figura abaixo:

 

Abaixo temos a implementação do programa Hello-World utilizando operadores, e não mais a execução simples de regras procedurais.

 

###########################################################################
# From Chapter 2 of the Soar Tutorial
#
# This operator writes "Hello World" and halts.
#
###########################################################################
 

# Aqui utiliza-se uma regra de proposição para o operador que utilizaremos.

sp {propose*hello-world
   (state <s> ^type state)
-->

# Aqui utilizamos o indicador de preferência aceitavel "+" para esse operador.

# Neste caso, como é o único operador proposto, o procedimento de decisão vai seleciona-lo.

   (<s> ^operator <o> +)
   (<o> ^name hello-world)
}
 

# Aqui temos a etapa de utilização do operador, tratando o caso do operador hello-world

# ter sido selecionado na etapa de decisão.

sp {apply*hello-world
   (state <s> ^operator <o>)
   (<o> ^name hello-world)
-->
   (write |Hello World|)
   (halt)
}
 
A execução do programa gera o seguinte resultado:
 
 
Neste exemplo existe apenas um operador, portanto a etapa de decisão é redundante. Porém a utilização de multiplos operadores no Soar nos permite propor diversas alternativas para serem escolhidas para cada estado no processo de solução de um problema. Através dos ciclos de proposição/decisão/utilização de operadores, o Soar vai interativamente alterando a memória de trabalho (manipulando e alterando objetos como no exemplo das jarras que veremos a seguir), até um objetivo desejado ser atingido
 

Examinando a memória de trabalho

Utilizando o comando "print s1" na caixa de comando do Soar Debugger, podemos ver todos os atributos e valores que o identificador s1 possui:

(S1 ^io I1 ^operator O1 + ^operator O1 ^superstate nil ^type state)

Conforme vimos no estudo da memória de trabalho, os atributos io, superstate e type são criados automaticamente para o agente.

Verifica-se também que existem dois elementos com atributo operator: O1+ e O1. A diferença entre eles é que o primeiro é o operador proposto, o segundo, sem o indicador de preferência "+", é o operador que foi escolhido na etapa de decisão.

Para o operador utilizado temos:

(O1 ^name hello-world)

Apenas um elemento de atributo name, e valor hello-world, conforme declaramos na criação do operador.

 

Criando um agente para o Water-Jug problem

O problema do water jug tem a seguinte formulação.

1. São dadas duas jarras vazias, uma de 5 galões e uma de 3 galões. 

2. É possivel enche-las completamente ou esvazia-las completamente com água.

3. É possivel passar a água de uma jarra para outra, até o ponto que a de origem esvazia ou a de destino enche completamente.

4. O objetivo final é obter exatamente 1 galão na jarra de 3 galões.

A partir desse conhecimento podemos determinar os possíveis estados no caminho da solução do problema.

 

Persistência dos elementos da memória de trabalho

Elementos utilizados para seleção e aplicação de operadores quando não são mais verificados, isto é, não correspondem mais a condições verdadeiras, são retirados da memória de trabalho.

Para atender diferentes necessidades de cada etapa dos ciclos de proposição, decisão e utilização, o Soar diferencia a persistência de elementos criados por operador de aplicação de regras e de elementos da memória de trabalho criados por outro tipo de regras.

O operador de aplicação precisa criar resultados não voláteis das mudanças realizadas pelo sistema, pois está altera efetivamente o estado atual. Já as outras regras são utilizadas para tarefas auxiliares que não modificam o estado atual e dessa forma devem ser retiradas quando não correspondem mais ao estado atual.

As os elementos da memória de trabalho criados por uma regra de aplicação são ditas terem suporte de operador (o-support). Essas devem ser removidas apenas por outros operadores de aplicação ou quando não fazem mais parte do estado.

Para outras regras de aplicação, seus elementos devem ser retirados quando tal regra não mais se verifica. Estas são ditas terem suporte de instanciação (i-support) pois só existem quando a instancia da regra ainda se verifica.

 

Elaboração de estados

Modelando esse problema a partir do ítem 1, nota-se que necessitamos 2 objetos do tipo jarra, possuindo 2 atributos, um para o volume total e outro para a quantidade atual de água. 

Além disso é necessario definir um estado inicial (ítem 1), onde ambas as jarras estão vazias, e um estado final (ítem 4), onde o objeto jarra de 3 galões vai possuir quantidade 1 galão. O código para esses objetos e estados iniciais e finais é descrito abaixo:

Cria dois objetos do tipo jarra e os inicializa com seus valores iniciais

(<s> ^name water-jug

   ^jug <j1>
   ^jug <j2>)
(<j1> ^volume 5
   ^contents 0)
(<j2> ^volume 3
   ^contents 0)
 
Define o estado final, onde a jarra de capacidade 3 contém 1 galão.

(state <s> ^name water-jug

   ^jug <j>)
(<j> ^volume 3
   ^contents 1)
 

Proposição de operadores

O conhecimento necessário para a tomada de decisões, por onde devemos projetar nossos operadores, está definido nos ítens 2 e 3. Percebe-se que a partir das ações que podem ser tomadas, devemos modelar 3 operadores: Um para encher a jarra, outro para esvazia-la e um terceiro para passar o conteúdo de uma jarra para a outra: fill/empty/pour.

Desta forma o exemplo faz da seguinte maneira:

 

Fill:

sp {water-jug*propose*fill

# Condição para a proposição do operador é que exista a jarra <j> e que ela não esteja cheia

   (state <s> ^name water-jug
        ^jug <j>)
   (<j> ^empty > 0)
-->

# Operador <o> com atributo ^name "fill" é proposto 

   (<s> ^operator <o> + =)
   (<o> ^name fill
        ^fill-jug <j>)}

 

Empty:

sp {water-jug*propose*empty
# Condição para a proposição do operador é que exista a jarra <j> e que ela não esteja vazia
   (state <s> ^name water-jug
        ^jug <j>)
   (<j> ^contents > 0)
-->
# Operador <o> com atributo ^name "empty" é proposto 
   (<s> ^operator <o> + =)
   (<o> ^name empty
        ^empty-jug <j>)}
 
 
Pour:
 
sp {water-jug*propose*pour
# Condição para a proposição do operador é que existam as jarras <j> e <i> e que sejam distintas
   (state <s> ^name water-jug
        ^jug <i>
        ^jug { <j> <> <i> })

# Alem disso a jarra <i> não pode estar vazia, e a j não deve estar cheia

   (<i> ^contents > 0)
   (<j> ^empty > 0)
-->
# Operador <o> com atributo ^name "pour" é proposto. Operador também possue os atributos
# ^empty-jug com valor <i> e ^fill-jug com valor <j>
   (<s> ^operator <o> +=)
   (<o> ^name pour
        ^empty-jug <i>
        ^fill-jug <j>)}

 

A partir da proposta de criação desses operadores, as açoes descritas nos ítens 2 e 3 necessárias para resolução do problema estão definidas. O próximo passo vai ser definir a aplicação desses operadores, ou seja, quais ações vão ser executadas quando forem escolhidos.

Aplicação de operadores

A aplicação dos operadores vai depender do estado em que o agente se encontra.

Exemplificando, após a inicialização através da aplicação operador initialize-water-jug (código abaixo), temos criados dois objetos water-jug na memória de trabalho. Isso satisfaz a primeira condição da proposição dos operadores fill/empty/pour: (state <s> ^name water-jug ^jug <j>)

 

# Alteração na memória de trabalho na aplicação do operador initialize-water-jug

(<s> ^name water-jug
     ^jug <i> <j>)
(<i> ^volume 3
     ^contents 0)
(<j> ^volume 5
     ^contents 0)}

Além disso o atributo ^content de ambas tem valor 0. Isso faz com que a condição (<i> ^contents > 0) dos operadores empty e pour não seja satisfeito. Desta forma o único operador proposto vai ser fill. 

Quando executamos o programa e observamos a memória de trabalho temos:

--- Firing Productions (IE) For State At Depth 1 ---

Firing water-jug*propose*fill
--> 
(O2 ^fill-jug I4 +)
(O2 ^name fill +)
(S1 ^operator O2 =)
(S1 ^operator O2 +)
Firing water-jug*propose*fill
--> 
(O3 ^fill-jug J1 +)
(O3 ^name fill +)
(S1 ^operator O3 =)
(S1 ^operator O3 +)
--- Change Working Memory (IE) ---
=>WM: (31: S1 ^operator O3 +)
=>WM: (30: S1 ^operator O2 +)

=>WM: (29: O3 ^fill-jug J1)

=>WM: (28: O3 ^name fill)

=>WM: (27: O2 ^fill-jug I4)

=>WM: (26: O2 ^name fill)
 
O único operador que é proposto é fill, uma vez utilizando cada objeto. Propostos os operadores, passamos a etapa de decisao.
 
--- decision phase ---

=>WM: (32: S1 ^operator O3)

     2: O: O3 (fill)
--- apply phase ---
 
A linha em vermelho indica o operador selecionado (uma vez que não possui mais o simbolo de preferência "+". A partir dai passamos novamente a etapa de aplicação do operador selecionado.
 

Monitoramento de estados e operadores

No Soar é possivel monitorar os estados e operadores que estão sendo manipulados pelo sistema através da criação de regras disparadas quando determinados operadores e entram na memória de trabalho.

No exemplo do water-jug, isso é feito da seguinte maneira:

 

sp {water-jug*monitor*operator-application*empty

# Quando estado o operador selecionado tiver atributo ^name empty o print é disparado. 

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

Reconhecimento do estado desejado

Conforme mostramos no ítem 4 da descrição do sistema, o estado definido para fim do problema é quando a jarra de 3 galões tiver com conteúdo 1. Para isso cria-se uma regra de monitoramento da seguinte forma:

sp {water-jug*detect*goal*achieved

   (state <s> ^name water-jug
              ^jug <j>)

# Esta condição verifica se a jarra de tamanho 3 está com um galão, neste caso, o programa é encerrado.

   (<j> ^volume 3 ^contents 1)
-->
   (write (crlf) |The problem has been solved.|)
   (halt)}
 

Controle de busca

O conhecimento utilizado pelos operadores que atuam no sistema tratam qualquer ação dentre as especificadas nos ítens 2 e 3 da formulação do problema como tendo a mesma preferência. Isso leva a comportamentos contra-produtivos, do tipo esvaziar a jarra que no estado anterior havia sido enchida.

Para esses casos é possivel implementar outros operadores que melhoram a performance da realização da tarefa. As implementações alternativas incluída nos exemplos agregam conhecimento em novos operadores, melhorando a performance do sistema.

A figura acima mostra uma execução da implementação simples descrita nas secções anteriores que leva centenas de operações para finalizar o problema.

Utilizando uma implementação com operadores que expandem o conhecimento de como resolver o sistema, a performance melhora sensivelmente conforme vemos na execução abaixo, que chega a solução em apenas 22 ações:

 

A segunda implementação utiliza um operador que grava qual era o último estado, e assim cria operadores que evitam esvaziar uma jarra recém enchida e vice-versa, atribuindo a marcação de preferência "<" (worse) que só utilizara tal operador caso não haja nenhuma outra opção disponível.:

 

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

# Elemento criado onde o valor <name> é o último operador selecionado

   (<s> ^last-operator <name>)}
 
sp {water-jug*select*fill*empty*worst
# Verifica se o último operador foi fill
   (state <s> ^name water-jug
              ^last-operator fill
              ^operator <o> +)
   (<o> ^name empty)
-->

# Caso último operador seja fill, atribui "<" ao operador empty para evitar esvaziar logo em seguida

   (<s> ^operator <o> <)}
 
sp {water-jug*select*empty*fill*worst
# Elemento criado onde o valor <name> é o último operador selecionado

   (state <s> ^name water-jug

              ^last-operator empty
              ^operator <o> +)
   (<o> ^name fill)
-->

# Caso último operador seja empty, atribui "<" ao operador fill para evitar encher logo em seguida.

   (<s> ^operator <o> <)}
 

Conclusão

O experimento de hoje nos permitiu entender os conceitos básicos do Soar, como implementar ações através de operadores e modelar um sistema para a solução de problemas "abertos", que podem não ter uma solução conhecida.

Conhecendo o problema e possíveis soluções é possível construir novos operadores para agregar conhecimento de como chegar ao objetivo final de forma mais eficaz. Foi possivel verificar que existe um compromisso entre o grau de especialização de um sistema, adicionando novos operadores para situações mais especificas, e a eficiência do mesmo na resolução do problema.

Nos próximos experimentos será interessante entender como o sistema do Soar pode utilizar o aprendizado adquirido em resoluções anteriores do mesmo problema para resolve-lo com mais eficiência.

 

Referências

 

Laird, John E. (2012). The Soar 9 Tutorial. Universidade de Michigan, Michigan. Disponível em: <http://web.eecs.umich.edu/~soar/downloads/Documentation/SoarTutorial/Soar%20Tutorial%20Part%201.pdf>.

Laird, John E. e Congdon, Clare B. (2012). The Soar User's Manual Version 9.3.2. Universidade de Michigan, Michigan. Disponível em: <http://web.eecs.umich.edu/~soar/downloads/Documentation/SoarManual.pdf>.

 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer