Relatório da Aula 05 (05/04/2013) SOAR - Tutoriais 4 e 5

3.  Experimentos e Resultados

3.1.  Atividade 1 - Tutorial 4 do Soar (More Simple Problem Solving)

3.1.1. Objetivos específicos

• Realizar as atividades propostas no Tutorial 4 do Soar;
• Criar um programa Soar que seja capaz de propor uma solução válida para o problema estudado no Tutorial 4 através da abordagem de busca em espaços do problema.

3.1.2. Desenvolvimento

Nesta atividade será explorado um problema bastante conhecimento da Inteligência Artificial Clássica chamado de "Missionários e Canibais". A solução deste problema deverá ser implementada usando produções do Soar baseada em uma estratégia de tentativa e erro que envolve a busca, por força bruta, através dos possíveis estados.

O problema é colocado como:

"Há três missionários e três canibais na margem de um rio. Há também um barco que pode levar uma ou duas pessoas por vez de uma margem à outra. O barco deve cruzar o rio de tal forma que número de canibais nunca seja maior que o número da missionários de um lado do rio (embora canibais possam ficar sozinhos). Como os missionários e canibais podem atravessar o rio com sucesso?"

Figura 1 - Jogo Missionários e Canibais. Fonte: <http://www.plastelina.net/game2.html>.

A abordagem adequada implementação da solução do problema consiste na sua decomposição em espaços do problema representados pelos operadores e pelos estados iniciais, intermediários e estado desejado (meta). Um detalhe interessante é que este problema também inclui estados de falha. A Figura 2 mostra o grafo parcial (não estão sendo mostrados os quatros últimos passos) que representa o espaço do problema com os estados inválidos marcados em vermelho.

Figura 2 - Grafo parcial que representa o espaço do problema Missionários e Canibais. Autor: Laird, 2012.

A implementação da solução no Soar deve levar em conta:

1. A representação do estado;
2. As regras para criação do estado inicial;
3. As regras de proposição de operadores;
4. As regras de aplicação dos operadores;
5. As regras de monitoramento de estados e operadores;
6. A regra de reconhecimento do estado desejado (meta);
7. As regras de reconhecimento de estados inválidos (falhas);
8. As regras de controle de busca.

As seções a seguir vão explorar cada um destes aspectos.

Representação do estado

A representação do estado tem o objetivo de capturar partes do problema a partir da sua observação e análise. A representação permite o tratamento do problema e a busca pela solução como uma sequência de alterações a partir de um estado inicial. As alterações são representadas por operadores que provocam, diretamente ou indiretamente, alterações nos estados. A solução em si é uma representação de um estado a ser atingido. Devido à estas características, a representação adequada do problema pode implicar diretamente na facilidade da sua manipulação e na eficiência da busca pela solução.

Para o problema dos Missionários e Canibais, a representação do estado pode ser feita contendo objetos para representar as duas margens do rio. A partir destes objetos, considerando o modelo de representação do Soar, podem ser admitidos subobjetos para os missionários, canibais e o barco. Esta representação é mais intuitiva por se aproximar das características físicas do problema. A Figura 3 mostra o digrafo a representação do estado inicial para o problema em questão. A Listagem 1 contempla a representação do mesmo estado no Soar.

Figura 3 - Representação do estado inicial para o problema dos Missionários e Canibais.

(state <s> ^left-bank <l>
           ^right-bank <r>)
(<l> ^missionaries 3
     ^cannibals 3
     ^boat 1
     ^other-bank <l>)
(<r> ^missionaries 0
     ^cannibals 0
     ^boat 0
     ^other-bank <r>)

Listagem 1 - Representação do estado inicial para o problema dos Missionários e Canibais no Soar (Laird, 2012, p.145).

É possível notar através da representação que o estado inicial contempla os três missionários, os três canibais e o barco, todos localizados na margem esquerda do rio.

Criação do estado inicial

A criação do estado inicial, conforme a recomendação do Soar, deve ser feita com a proposição do operador de inicialização. A aplicação deste operador cria elementos na memória de trabalho contendo o nome do problema sendo tratado e os elementos mencionados na seção anterior. A Listagem 2 mostra as regras de proposição e aplicacão do operador de inicialização.

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

sp {mac*apply*initialize
   (state <s> ^operator.name initialize-mac)
-->
   (<s> ^name mac
        ^left-bank <l>
        ^right-bank <r>
        ^desired <d>)
   (<l> ^missionaries 3
        ^cannibals 3
        ^boat 1
        ^other-bank <r>)
   (<r> ^missionaries 0
        ^cannibals 0
        ^boat 0
        ^other-bank <l>)
   (<d> ^right-bank <dl>)
   (<dl> ^missionaries 3
         ^cannibals 3
         ^boat 1)
}

Listagem 2 - Regras de proposição e aplicação do operador de inicialização (Laird, 2012, p.147).

Após a aplicação do operador initialize-mac cria WMEs o-supported na memória de trabalho represetando o estado inicial do problema.

Proposição de operadores

Os operadores que vão viabilizar a busca no espaço do problema são os operadores que representam a viagem do barco de uma margem à outra do rio. Esta viagem pode ser realizada por uma ou duas pessoas ao mesmo tempo. As possibilidades de movimentação do barco podem ser resumidas em:

• mover um missionário ou um canibal para a outra margem;
• mover dois missionários ou dois canibais para a outra margem;
• mover um missionário e um canibal para a outra margem.

A Listagem 3 mostra a implementação dos operadores que irão propor os movimentos possíveis para cada estado.

# If the name of the state is mac and there is one or 
# more cannibal or missionary on the same bank of the river as the boat, 
# then propose moving that cannibal or missionary across the river.

sp {mac*propose*operator*move-boat1
   "Moves either a single missionary or a cannibal."
   (state <s> ^name mac
              ^<< right-bank left-bank >> <bank>)
   (<bank> ^{ << cannibals missionaries >> <type> } > 0
           ^boat 1)
-->
   (<s> ^operator <o> + =)
   (<o> ^name move-boat
        ^bank <bank>
        ^<type> 1
        ^boat 1
        ^types 1)}

# If the name of the state is mac and there are two or 
# more cannibals or missionaries on the same bank of the river as the boat, 
# then propose moving two of that type across the river.

sp {mac*propose*operator*move-boat2
   "Moves two missionaries or two cannibals."
   (state <s> ^name mac
              ^ << right-bank left-bank >> <bank>)
   (<bank> ^{ << cannibals missionaries >> <type> } > 1
           ^boat 1)
-->
   (<s> ^operator <o> + =)
   (<o> ^name move-boat
        ^bank <bank>
        ^<type> 2
        ^boat 1
        ^types 1)}

# If the name of the state is mac and there is one or more cannibal and one or
# more missionaries on the same bank of the river as the boat,
# then propose moving one cannibal and one missionary across the river.

sp {mac*propose*operator*move-boat11
   (state <s> ^name mac
              ^ << right-bank left-bank >> <bank>)
   (<bank> ^missionaries > 0
           ^cannibals > 0
           ^boat 1)
-->
   (<s> ^operator <o> + =)
   (<o> ^name move-boat
        ^bank <bank>
        ^missionaries 1
        ^cannibals 1
        ^boat 1
        ^types 2)}

Listagem 3 - Regras de proposição de operadores de movimentação (Laird, 2012, p.150-151).

Os operadores de movimentação são propostos com preferência aceitável e indiferente. Isto significa que não há qualquer preferência por quais tipos de viagens devem ser feitas. A tarefa seguinte é a aplicação dos operadores propostos.

Aplicação de operadores

As regras de aplicação dos operadores alteram o estado para refletir o movimento do barco e o número de missionários e canibais em cada margem. Um detalhe particular é que não é necessário representar quais missionários e canibais estão sendo movimentados, e sim apenas o número de missionários e canibais que estão sendo movimentados.

As atividades do Tutorial propõem a criação passo-a-passo de regras de aplicação e um processo de refinamento para generalizar estas regras. É criada uma regra de aplicação para movimentação de uma pessoa de cada tipo (missionário ou canibal). Em seguida, a regra criada é generalizada para movimentação de uma ou duas pessoas. Por fim, a regra é alterada para generalizar  o tipo de pessoa. A Listagem 4 mostra a regra de aplicação dos operadores propostos.

sp {apply*move-boat
   (state <s> ^operator <o>)
   (<o> ^name move-boat
        ^{ << missionaries cannibals boat >> <type> } <num>
        ^bank <bank>)
   (<bank> ^<type> <bank-num>
           ^other-bank <obank>)
   (<obank> ^<type> <obank-num>)
-->
   (<bank> ^<type> <bank-num> -
                   (- <bank-num> <num>))
   (<obank> ^<type> <obank-num> -
                    (+ <obank-num> <num>))}

Listagem 4 - Regra de aplicação dos operadores de movimentação (Laird, 2012, p.152).

Esta regra tem como ação a remoção e adição de novos WMEs na memória de trabalho para representar o número de missionários e canibais em cada margem do rio após a aplicação do operador selecionado. Os operador selecionado é um dos operadores de movimentação propostos na seção anterior.

Monitoramento de estados e regras

O monitoramento da busca interna pela solução do problema pode ser implementada através de regras que imprimem o estado atual e a operação em execução. A Listagem 5 mostra a implementação das regras de monitoramento do estado, sendo uma regra para cada margem do rio e uma para o barco.

sp {monitor*move-boat
   (state <s> ^operator <o>)
   (<o> ^name move-boat
        ^{ << cannibals missionaries >>  <type> } <number>)
   -->
   (write (crlf) | Move | <number> | | <type>)}

sp {monitor*state*left
   (state <s> ^name mac
              ^left-bank <l>
              ^right-bank <r>)
   (<l> ^missionaries <ml>
        ^cannibals <cl>
        ^boat 1)
   (<r> ^missionaries <mr>
        ^cannibals <cr>
        ^boat 0)
   -->
   (write (crlf) | M: | <ml> |, C: | <cl> | B ~~~   | 
                 | M: | <mr> |, C: | <cr> |  |)}

sp {monitor*state*right
   (state <s> ^name mac
              ^left-bank <l>
              ^right-bank <r>)
   (<l> ^missionaries <ml>
        ^cannibals <cl>
        ^boat 0)
   (<r> ^missionaries <mr>
        ^cannibals <cr>
        ^boat 1)
   -->
   (write (crlf) | M: | <ml> |, C: | <cl> |   ~~~ B | 
                 | M: | <mr> |, C: | <cr> |  |)}

Listagem 5 - Regras para monitoramento de estados (Laird, 2012, p.153).

Estas regras imprimem no log do SoarDebugger o número de missionários e canibais em cada margem do rio e o número de missionários e canibais dentro do barco.

A execução do programa neste ponto é possível, como pode ser visto na Figura 4. Entretanto, ele não tem um término definido.

Figura 4 - Execução sem término do programa Missionário e Canibais no SoarDebugger.

Além da execução sem término, o programa visita, ainda, estados inválidos, como pode ser visto marcado em vermelho na Figura 4. Neste caso, um estado inválido foi admitido contendo um missionário e dois canibais de um lado do rio, o que viola a especificação do problema.

Reconhecimento do estado desejado

Para fazer com que o programa resolva o problema em questão, é necessário uma regra que determine que o estado desejado foi atingido. Isto ocorre quando esta regra é satisfeita a partir da comparação do número de missionários e canibais na margem desejada do rio (oposta à margem do estado inicial). A Listagem 6 mostra a implementação desta regra.

# mac*detect*goal*achieved
# If the name of the state is mac and the number of missionaries and
# cannibals on one bank of the river in the desired state matches the number
# of missionaries and cannibals on the same bank in the current state, write
# that the problem has been solved and halt.

sp {mac*detect*state*success
   (state <s> ^desired <d>
              ^<side> <ls>)
   (<ls> ^missionaries <m>
         ^cannibals <c>)
   (<d> ^{ << right-bank left-bank >> <side> } <dls>)
   (<dls> ^missionaries <m>
          ^cannibals <c>)
-->
   (write (crlf) |The problem has been solved.|)
   (halt)}

Listagem 5 - Regras para monitoramento de estados (Laird, 2012, p.153).

Neste caso, a ação do programa caso ele encontre a solução para o problema é imprimir a mensagem e sair do programa. A execução do programa pode ser vista na Figura 5.

Figura 5 - Execução com término do programa Missionário e Canibais no SoarDebugger.

Note que ainda podem ser vistos estados inválidos. Para tratar este problema, é necessário a implementação de regras para detecção dos estados de falha.

Detecção dos estados de falha

A detecção dos estados de falha é feita por meio de uma regra que identifica os estados inválidos, imprime a notificação que a solução falhou e abandona a execução. A Listagem 6 mostra a implementação desta regra.

# mac*detect*goal*failure
# If the name of the state is mac and there are more cannibals than
# missionaries, and there is at least one missionary, on one bank of the
# river, then write that the problem has failed to be solved, and halt.

sp {mac*evaluate*state*failure*more*cannibals
   (state <s> ^desired <d>
              ^<< right-bank left-bank >> <bank>)
   (<bank> ^missionaries { <n> > 0 }
           ^cannibals > <n>)
-->
   (write (crlf) |The problem has failed.|)
   (halt)}

Listagem 6 - Regra para detecção de estados inválidos (Laird, 2012, p.155).

A execução do programa com esta regra pode ser vista na Figura 6

Figura 6 - Execução do programa Missionário e Canibais com deteção de estado inválido no SoarDebugger.

Como pode ser visto na Figura 6, ao detectar um estado inválido, o programa é abortado. Este comportamento pode ser tratado se implementado uma tática de controle de busca no espaço do problema, como será apresentado a seguir.

Controle de busca no espaço do problema

Até aqui, caso o programa encontre um estado inválido, que viola a especificação do problema, ele é abortado. Para evitar este comportamento, uma possibilidade é a fazer com que o programa seja reiniciado a partir do estado inicial. Neste caso, ainda é possível que o programa siga o mesmo caminho na busca pela solução e atinja o mesmo estado de falha que provocou a reinicialização. Desta forma, a reinicialização não se mostra uma abordagem muito eficiente.

A abordagem mais adequada é criar uma memória que permita anular a atuação do último operador selecionado e refazer a operação, quando um estado de falha é atingido. Esta abordagem pode ser implementada através de regras que gravam o último operador selecionado e, em caso de falha, revogue-o de modo retornar ao estado anterior. A Listagem 7 apresenta o código-fonte destas regras.

# mac*apply*move-mac-boat*record*last-operator*types*1
# If an operator is selected to move one type of entity, 
# then create an augmentation of the state (last-operator) with the bank of the boat, 
# the type of entity being moved, the number, and that there is one type being moved.

sp {mac*select*operator*prefer*inverse*failure*types*1
   (state <s> ^name mac
              ^operator <o> +
              ^failure <d>
              ^last-operator <lo>)
   (<o> ^name move-boat
        ^<type> <number>
        ^types 1)
   (<lo> ^types 1
         ^type <type>
         ^number <number>)
-->
   (<s> ^operator <o> >)}

# mac*apply*move-mac-boat*record*last-operator*types*2
# If an operator is selected to move two types of entity, 
# then create an augmentation of the state (last-operator) 
# with the bank of the boat and that there is two types being moved.

sp {mac*select*operator*prefer*inverse*failure*types*2
   (state <s> ^name mac
              ^operator <o> +
              ^failure <d>
              ^last-operator.types 2)
   (<o> ^types 2)
-->
   (<s> ^operator <o> >)}

Listagem 7 - Regras para controle de busca (Laird, 2012, p.156-157).

A implementação destas regras permitem que o programa, agora, resolva o problema adequadamente sem considerar os estados de falha. A Figura 7 mostra a execução do programa. Note que foram necessários 276 ciclos de decisão, neste caso, para determinação da solucão.

Figura 7 - Execução do programa Missionário e Canibais no SoarDebugger.

Uma heurística adicional pode ser colocada para melhorar o desempenho da busca. Ela estabelece que não deve ser proposto um operador de movimentação que seja o inverso do último selecionado. Em outras palavras, não deve ser admitida a movimentação do mesmo número de pessoas para a margem oposta imediatamente esta ter sido realizada (este comportamento anularia a movimentação realizada). A Listagem 8 mostra a implementação destas regras.

# mac*select*operator*avoid*inverse*not*failure
# If the name of the state is mac and the current state is not a failure
# state and the last operator is the inverse of a proposed operator, then
# avoid that operator.

sp {mac*select*operator*avoid*inverse*not*failure*1
   (state <s> ^name mac
              ^operator <o> +
             -^failure <d>
              ^last-operator <lo>)
   (<o> ^types 1
        ^<type> <number>)
   (<lo> ^types 1
         ^type <type>
         ^number <number>)
-->
   (<s> ^operator <o> < )}

sp {mac*select*operator*avoid*inverse*not*failure*2
   (state <s> ^name mac
              ^operator <o> +
             -^failure <d>
              ^last-operator.types 2)
   (<o> ^types 2)
-->
   (<s> ^operator <o> < )}

Listagem 8 - Regras adicionais para controle de busca (Laird, 2012, p.158).

A Figura 8 mostra a execução do programa com estas regras.

Figura 8 - Execução otimizada do programa Missionário e Canibais no SoarDebugger.

Como pode ser visto na Figura 8, para este caso, foram necessários 40 ciclos de decisão para obtenção da solução. Um número bem menor se comparado com os 276 ciclos quando estas regras não estão presentes.

3.1.3. Resultados

Nesta atividade foram estudadas as seções do Tutorial 4 do Soar. Estes estudos permitiram a exploração das etapas necessárias para uma abordagem de busca por soluções de problema adotada pelo Soar. O estudo de cada etapa permitiu:

• Entender como podem ser feitas representações do problema a partir de estados;
• Entender como podem ser concebidos estados e operadores para resolução do problema;
• Entender como devem ser estruturado o reconhecimento do estado desejado (meta);
• Entender como implementar regras para o controle de buscas tornando o programa mais eficiente.

Tais entendimentos permitem que as mesmas etapas sejam seguidas para o tratamento de outros problemas que envolvam a busca pelo espaços de problema. O aspecto mais crítico nestes casos é obter uma representação adequada do problema de forma que estados e operadores possam ser criados e a execução do programa por parte da arquitetura possa chegar a solução do problema.

3.2.  Atividade 2 - Tutorial 5 do Soar (Planning and Learning)

3.2.1 Objetivos específicos

• Realizar as atividades propostas no Tutorial 5 do Soar;
• Adaptar programas Soar que sejam capazes de propor uma solução válida para os problemas apresentados no Tutorial 5 através da abordagem que utiliza planejamento e aprendizado.

3.2.2. Desenvolvimento

Nesta aula serão explorados as técnicas e os mecanismos de planejamento e aprendizado disponíveis no Soar. O tipo de planejamento a ser estudado nesta Tutorial é o planejamento conhecido como look-ahead e o mecanismo de aprendizado é o aprendizado conhecido como chunking. Os detalhes serão apresentados durante o desenvolvimento dos experimentos.

Muitos sistemas de planejamento tem um ciclo de planejamento em dois estágios: planejamento e execução. Eles sempre criam um plano quando são apresentados a um novo problema e o executam passo-a-passo. No Soar, a abordagem é diferente. Cada decisão é tomada a partir do conhecimento disponível sendo que o planejamento é apenas mais uma fonte de conhecimento que pode ser codificada sob a forma de regras.

O planejamento no Soar não cria uma sequência passo-a-passo de operadores para aplicá-los em sequência. Ao invés disso, ele aprende um conjunto de regras dependentes de contexto que indicam preferência ou rejeição de operadores específicos para os estados. Desta forma, segundo Laird (2012), o planejamento no Soar é mais flexível não estando restrito a um único problema.

Planejamento no problema dos jarros d'água

O planejamento no Soar começa com o mecanismo de detecção de impasses e criação de substados. Esta situação ocorre quando não há progresso devido a insuficiência de conhecimentos sobre a preferência dos operadores para aplicá-los ao estado atual. Para resolver esta situação, basta alterar a preferência dos operadores propostos ou marcá-los todos com a preferência de indiferença. Esta última solução deve ser considerada apenas quando houver convicção de que um operador não é, de fato, melhor que outro, ao invés de quando se souber que operador é melhor.

Transformaremos, nesta atividade, a implementação do problema dos jarros d'água realizada em atividades anteriores em um agente planejador, que explora os conceitos envolvidos com o planejamento.

O primeiro passo é a remoção da preferência de indiferença da regra que propõe o operador de preenchimento do jarro. A Listagem 9 mostra a regra com esta remoção.

sp {water-jug*propose*fill
   (state <s> ^name water-jug
              ^jug <j>)
   (<j> ^empty > 0)
-->
   (<s> ^operator <o> +) # a preferência "=" (indiferente) foi removida
   (<o> ^name fill
        ^jug <j>)}

Listagem 9 - Regra de proposição do operador sem a preferência indiferente.

A execução do programa water-jug sem a preferência indiferente faz com que o Soar gere um novo subestado assim que detectado um impasse. Este impasse é do tipo empate de operador (operator tie) e significa que dois ou mais operadores foram propostos e não há como determinar qual deles deve ser selecionado para aplicação. A Figura 9 mostra a ocorrência do impasse no SoarDebugger.

Figura 9 - Ocorrência do impasse de empate de operador no SoarDebugger.

O novo subestado criado a partir do impasse de empate de operador é similar aquele criado a partir do impasse de estado sem alteração. A diferença está nos aitrbutos do objeto que representa o operador empatado: ^choices multiple, ^impasse tie e ^item. A Listagem 10 mostra a estrutura do subestado obtido a partir do comando print --depth 2 S3 no SoarDebugger.

print --depth 2 S3
(S3 ^attribute operator ^epmem E2 ^choices multiple ^impasse tie ^item O3
       ^item O2 ^item-count 2 ^non-numeric O2 ^non-numeric O3
       ^non-numeric-count 2 ^quiescence t ^reward-link R4 ^smem S4
       ^superstate S1 ^type state)
  (E2 ^command C3 ^present-id 1 ^result R5)
  (O3 ^fill-jug J1 ^name fill)
  (O2 ^fill-jug I4 ^name fill)
  (S4 ^command C4 ^result R6)
  (S1 ^count 0 ^epmem E1 ^io I1 ^jug J1 ^jug I4 ^name water-jug ^operator O2 +
         ^operator O3 + ^reward-link R1 ^smem S2 ^steps S1 ^superstate nil
         ^type state)

Listagem 10 - Estrutura do subestado criado a partir do impasse de empate de operador.

Para o impasse de empate, o objetivo é determinar que operador de tarefa é melhor para ser aplicado no estado atual. Isto é obtido pela seleção e aplicação de operadores de avaliação nos subestados criados. O propósito destes operadores é criar uma avaliação dos operadores de tarefa. Esta avaliação pode ser um valor simbólico, tais como sucesso ou falha, ou um valor numérico que representa a probabilidade de sucesso. Estas avaliações, chamadas de resultado, são convertidas em preferências para os operadores de tarefa. Uma vez que as preferências de operadores foram criadas para os operadores de tarefa, um deles será selecionado e os subestados criados serão automaticamente removidos da memória de trabalho e o ciclo de decisão pode ser concluído.

O problema da solução de um impasse de empate é chamado de problema da Seleção. Embora obter boas funções de avaliação do estado para um problema específico seja difícil, a abordagem genérica pode ser adotada de tal forma que apenas algumas informações específicas do domínio sejam necessárias. O Soar já vem munido de um conjunto de regras e operadores que realizam avaliações e comparações entre operadores usando esta abordagem. Estas regras podem ser carregadas por qualquer programa que venham a fazer uso dos mecanismos de planejamento. A Listagem 11 mostra o fragmento de código a ser inserido nos programas Soar para inclusão das regras e operadores para o problema da seleção (assumindo que o programa está no subdiretório Agents do diretório padrão de instalação do Soar).

pushd ../default
source selection.soar
popd

Listagem 11 - Inclusão das regras genéricas para o problema da seleção.

Da mesma forma que a atividade anterior, deve ser considerado para o devido o tratamento do problema da seleção:

1. A representação do estado: inclui a representação dos objetos de avaliação que ligam as avaliações realizadas aos operadores;
2. A regra de criação do estado inicial: uma vez que o problema de seleção cria um subestado, o estado inicial é gerado automaticamente;
3. As regras de proposição do operador: o único operador é o operador-avaliar e deve ser proposto para cada operador empatado;
4. As regras de aplicação de operador: o operador-avaliar é implementado hierarquicamente, portanto, a aplicação do operador envolve um subestado e operadores de subestado;
5. As regras de monitoramento de estados e operadores: não há regras especiais para o problema da seleção;
6. As regras de reconhecimento do estado desejado: o reconhecimento do estado desejado é automático. Quando há preferências suficientes, o processo de decisão seleciona um operador, o impasse é resolvido e o subestado é removido da memória de trabalho;
7. A regra de detecção de falhas: não há estados de falha para este problema;
8. As regras de controle de busca: estas regras auxiliam quais operadores devem ser avaliadas primeiro.

Representação do Eatado Inicial

Para o problema da seleção, os operadores terão que criar e comparar avaliações. Se as avaliações tem um um único valor, chamado de avaliação, ele podem ser representados como um simples aumento no estado, tal como: ^evaluation success. Porém, as avaliações devem estar relacionados a um operador de tarefa ao qual a avaliação se refere. Além disso, é provável que seja necessário representar outros valores de comparação, sejam eles simbólicos (success, failure) ou numéricos (valores dentro de um intervalo ordenado). Para que a avaliação seja realizada, o estado deve conter uma série de aumentos. O objeto de avaliação criado para um dos operadores de tarefa pode conter a seguinte estrutura:

• ^operator <o>, o identificador do operador de tarefa sendo avaliado;
• ^symbolic-value success/partial-success/partial-failure/failure/indifferent;
• ^numeric-value [number]
• value true, indica se há um valor simbólico ou numérico;
• desired <d>, o identificador do estado desejado.

Um objeto com esta estrutura é criado para cada operador de tarefa do subestado criado para o problema da seleção. A partir da avaliação dos valores dados como resultado é o impasse é resolvido e o plano pode ser então estabelecido.

Criação do Estado Inicial de Seleção

Para o problema da seleção, um estado inicial é automaticamente criado em resposta a um impasse de empate. Portanto, os objetos de avaliação serão criados pela aplicação dos operadores de avaliação. Uma regra de elaboração é sugerida para nomear o estado de seleção, embora não seja necessária. A Listagem 12 mostra esta regra de elaboração.

sp {default*selection*elaborate*name
   :default
   (state <s> ^type tie)
-->
   (<s> ^name selection)}

Listagem 12 - Regra de elaboração do nome do estado de seleção.

Esta regra utiliza uma sintaxe que inclui a flag :default. Esta flag especifica que esta produção é uma produção padrão, o que significa que o Soar mantém estatísticas separadas para este tipo de regra.

Proposição do Operador de Seleção

Há um único operador para o problema da seleção: o operador de avaliação operador-avaliar. Ele é proposto para o problema da seleção se houver um item que não tem uma avaliação com valor. O operador primeiro criará uma avaliação e depois irá computá-la. A Listagem 13 mostra a implementação da proposição do operador de avaliação.

sp {selection*propose*evaluate-operator
   :default
   (state <s> ^name selection
              ^item <i>)
 -{(state <s> ^evaluation <e>)
   (<e> ^operator <i>
        ^value true)}
-->
   (<s> ^operator <o> +, =)
   (<o> ^name evaluate-operator
        ^operator <i>)}

Listagem 13 - Regra de proposição do operador-avaliar.

Uma vez satisfeitas as condições, este operador é selecionado e permanecerá selecionado até que uma avaliação apropriada seja criada com o valor. Portanto, um e somente um operador-avaliar será criado e aplicado para cada operador de tarefa empatado.

Aplicação do Operador de Seleção

A aplicação do operador de avaliação é feita em duas partes. A primeira parte é a criação da estrutura de avaliação mas ainda sem qualquer valor. Em paralelo com esta criação, o operador é elaborado com estruturas adicionais para tornar a aplicação mais simples. O resultado é mostrado na Listagem 14.

(<s> ^evaluation <e>
     ^operator <o>)
(<e> ^superoperator <so>
     ^desired <d>)
(<o> ^name evaluate-operator
     ^superoperator <so>
     ^evaluation <e>
     ^superstate <ss>
     ^superproblem-space <sp>)

Listagem 14 - Estrutura da avaliação.

O atributo ^desired do objeto representa o estado desejado a tarefa original. A estrutura do estado desejado é incluída para que o operador de avaliação possa basear-se durante a sua execução. Já o atributo ^superproblem-space é o espaço do problema do superestado, ou seja, é a representação explícita do estado de propriedades do espaço de problema atual e pode ser usado como uma dica para o disparo de regras relevantes para a solução do problema.

A segunda parte é o cálculo da avaliação, que não pode ser feita diretamente com regras e requer um subestado próprio. O subestado é chamado de problema da avaliação. O estado da tarefa original é copiado para o subestado da avaliação. Então, o operador de tarefa sendo avaliado é aplicado neste estado. Se o novo estado pode ser avaliado, então a avaliação é retornada como resultado e adicionado ao objeto de avaliação apropriado. Se a avaliação não puder ser realizada, então a solução do problema da avaliação contina até que a avaliação possa ser feita. Este fato leva a um outro impasse de empate que, por sua vez, cria novos subestados, etc. As computações a serem realizadas são:

1. Criação do estado inicial;
2. Seleção do operador sendo avaliado;
3. Aplicação do operador selecionado;
4. Avaliação do resultado.

As seções a seguir apresentam cada uma destas etapas considerando o problema dos jarros d'água (Water jug).

Water jug: criação do estado inicial

O estado inicial é a cópia do estado no qual o impasse ocorreu. A cópia é feita utilizando um conjunto de regras pré-definidas no Soar para cópia de atributos entre estados. Estas regras são automaticamente disparadas quando detectado um impasse e tem ações definidas conforme o valor de determinados atributos que regulam esta cópia:

• ^default-state-copy no: não copia qualquer aumento de estado automaticamente;
• ^two-levels-attributes: copia aumentos do estado e cria novos identificadores para os valores copiados. Identificadores compartilhados são substituídos pelos mesmos identificadores recém-criados.
• ^all-atributes-at-level two: copia todos os atributos do estado da mesma forma que o anterior, exceto pelo fato que ele não copia atributos de nível um;
• dont-copy: não copia um determinado atributo especificado;
• dont-copy-anything: não copia nenhum atributo se especificado o valor booleano yes.

A Listagem 15 mostra a regra de elaboração que realiza a cópia dos atributos do estado original para o subestado de avaliação.

sp {water-jug*elaborate*problem-space
   (state <s> ^name water-jug)
-->
   (<s> ^problem-space <p>)
   (<p> ^name water-jug
        ^default-state-copy yes
        ^two-level-attributes jug)}

Listagem 15 - Regra de elaboração do subestado de avaliação para o problema Water Jug.

Note que o atributo ^two-level-attributes informa o valor jug. Isto representa que os aumentos de dois níveis do objeto jug serão copiados do estado original para o subestado de avaliação para que o operador de avaliação possa realizar avaliações a partir dos valores contidos neste objeto. A Listagem 16 mostram os objetos do estado original e o subestado de avaliação depois da cópia.

# Estado Original (s1)
(s1 ^jug j1 j2)
(j1 ^volume 3
    ^contents 0
    ^empty 3)
(j2 ^volume 5
    ^contents 0
    ^empty 5)

# Subestado de avaliação (s3)
(s3 ^jug j3 j4)
(j3 ^volume 3
    ^contents 0
    ^empty 3)
(j4 ^volume 5
    ^contents 0
    ^empty 5)

Listagem 16 - Estruturas do estado original e do subestado de avaliação depois da cópia.

Novos identificadores foram criados no subestado durante a cópia (j3 e j4) com os mesmos valores do estado original (j1 e j2).

Water jug: seleção do operador sob avaliação

Uma vez que o estado inicial do operador de avaliação é criado, uma cópia do operador que está sob avaliação precisa ser selecionada. Uma cópia do operador é necessária porque ele pode ter referência a objetos que do estado original que não foram copiados ou então simplesmente porque ele criou novos objetos, e estes devem ser refletidos no estado original.

A cópia substitui quaisquer identificadores da estrutura do operador que foi alterada durante a cópia do estado original (no caso j1 e j2 foram substituídos por j3 e j4, respectivamente). Uma vez que ela é concluída, regras adicionais rejeitam os outros operadores propostos de forma que o operador copiado é selecionado.

Water jug: aplicação do operador sob avaliação

Uma vez que o operador é selecionado, as regras de aplicação serão disparadas e modificam o estado copiado. Estas regras já estão implementadas no Soar e tornaram-se disponível pela inclusão do programa selection.soar no programa atual.

Water jug: avaliação do resultado

Uma vez que o novo estado foi criado, a avaliação pode ser realizada. Um aumento é adicionado ao estado em paralelo ao operador sendo aplicado: ^tried-tied-operador <o>. Este aumento pode ser testado pelas regras para assegurar que eles estão avaliando o resultado da aplicação do operador.

As avaliações mais simples para serem computadas são success e failure. A primeira representa que o objetivo foi atingido. A segunda, por sua vez, que a busca pela meta falhou. A Listagem 17 mostra a alteração feita no programa Water Jug para detectar o sucesso na busca pela solução.

sp {water-jug*evaluate*state*success
   (state <s> ^desired <d>
              ^problem-space.name water-jug
              ^jug <j>)
   (<d> ^jug <dj>)
   (<dj> ^volume <v> ^contents <c>)
   (<j> ^volume <v> ^contents <c>)
-->
   (<s> ^success <d>)}

Listagem 17 - Regra para detecção de sucesso na busca pela solução do programa Water Jug.

A regra de seleção processará automaticamente a avaliação em um subestado. Esta avaliação tem duas partes: (i) o atributo, que é o tipo da avaliação, e (ii) o valor, que o identificador do estado desejado.

Além da indicação de sucesso ou falha, as regras de seleção podem processar outros valores simbólicos e também valores numéricos. Os valores simbólicos que podem ser processador são:

• success: Este é o estado desejado. Ele é traduzido na preferência do tipo best. Ele pode ser também traduzido em uma preferência do tipo better caso outro operador tenha um resultado com avaliação de sucesso parcial (partial-success).
• partial-success: Este estado indica que se está caminhando em direção ao sucesso. Ele é traduzido em uma preferência do tipo best.
• indifferent: Este estado não indica nem sucesso nem falha. É traduzido em preferência do tipo indifferent.
• failure: O estado desejado não pode ser atingido a partir deste estado. É traduzido em uma preferência do tipo reject.
• partial-failure: Todos os caminhos deste estado levam à falha. É traduzido em preferência do tipo worst.

Para avaliações numéricas, um aumento chamado ^numeric-value deve ser criado para avaliação do operador.

A implementação destas regras juntamente com as regras originais do programa Water Jug permitem que o programa faça uma busca do tipo look-ahead (backtracking). A Listagem 18 mostra a execução do programa.

source {C:\dev\Soar\Agents\water-jug-look-ahead\water-jug-look-ahead.soar}
***********************************************************************************
Total: 93 productions sourced.
run
     1: O: O1 (initialize-water-jug-look-ahead)
 5:0 3:0
     2: ==>S: S3 (operator tie)
  O2: fill(3)
  O3: fill(5)
     3:    O: O4 (evaluate-operator)
     4:    ==>S: S5 (operator no-change)
 5:0 3:0
     5:       O: C7 (fill)
  FILL(3)
 5:0 3:3
     6:       ==>S: S7 (operator tie)
  O8: pour(3:3,5:0)
  O9: empty(3)
  O7: fill(5)
     7:          O: O12 (evaluate-operator)
     8:          ==>S: S9 (operator no-change)
 5:0 3:3
     9:             O: C12 (fill)
  FILL(5)
 5:5 3:3
    10:             ==>S: S11 (operator tie)
  O16: empty(5)
  O13: empty(3)
    11:                O: O18 (evaluate-operator)
    12:                ==>S: S13 (operator no-change)
 5:5 3:3
    13:                   O: C17 (empty)
  EMPTY(3)
 5:5 3:0
    14:                   ==>S: S15 (operator tie)
  O21: fill(3)
  O22: pour(5:5,3:0)
  O20: empty(5)
    15:                      O: O25 (evaluate-operator)
    16:                      ==>S: S17 (operator no-change)
 5:5 3:0
    17:                         O: C22 (empty)
  EMPTY(5)
 5:0 3:0
    18:                         ==>S: S19 (operator tie)
  O29: fill(5)
  O27: fill(3)
    19:                            O: O30 (evaluate-operator)
    20:                            ==>S: S21 (operator no-change)
 5:0 3:0
    21:                               O: C27 (fill)
  FILL(5)
 5:5 3:0
    22:                               ==>S: S23 (operator tie)
  O34: pour(5:5,3:0)
  O35: empty(5)
  O32: fill(3)
    23:                                  O: O38 (evaluate-operator)
    24:                                  ==>S: S25 (operator no-change)
 5:5 3:0
    25:                                     O: C32 (fill)
  FILL(3)
 5:5 3:3
    26:                                     ==>S: S27 (operator tie)
  O42: empty(3)
  O39: empty(5)
    27:                                        O: O44 (evaluate-operator)
    28:                                        ==>S: S29 (operator no-change)
 5:5 3:3
    29:                                           O: C37 (empty)
  EMPTY(5)
 5:0 3:3
    30:                                           ==>S: S31 (operator tie)
  O47: fill(5)
  O48: pour(3:3,5:0)
  O45: empty(3)
    31:                                              O: O50 (evaluate-operator)
    32:                                              ==>S: S33 (operator no-change)
 5:0 3:3
    33:                                                 O: C42 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    34:                                                 ==>S: S35 (operator tie)
  O56: fill(5)
  O57: fill(3)
  O58: pour(5:3,3:0)
  O55: empty(5)
    35:                                                    O: O61 (evaluate-operator)
    36:                                                    ==>S: S37 (operator no-change)
 5:3 3:0
    37:                                                       O: C47 (pour)
  POUR(5:3,3:0)
  POUR(5:0,3:3)
 5:0 3:3
    38:                                                       ==>S: S39 (operator tie)
  O69: fill(5)
  O70: pour(3:3,5:0)
  O68: empty(3)
    39:                                                          O: O73 (evaluate-operator)
    40:                                                          ==>S: S41 (operator no-change)
 5:0 3:3
    41:                                                             O: C52 (empty)
  EMPTY(3)
 5:0 3:0
    42:                                                             ==>S: S43 (operator tie)
  O77: fill(3)
  O75: fill(5)
    43:                                                                O: O79 (evaluate-operator)
    44:                                                                ==>S: S45 (operator no-change)
 5:0 3:0
    45:                                                                   O: C57 (fill)
  FILL(5)
 5:5 3:0
    46:                                                                   ==>S: S47 (operator tie)
  O82: pour(5:5,3:0)
  O83: empty(5)
  O80: fill(3)
    47:                                                                      O: O84 (evaluate-operator)
    48:                                                                      ==>S: S49 (operator no-change)
 5:5 3:0
    49:                                                                         O: C62 (pour)
  POUR(5:5,3:0)
  POUR(5:2,3:3)
 5:2 3:3
    50:                                                                         ==>S: S51 (operator tie)
  O93: fill(5)
  O94: pour(3:3,5:2)
  O90: empty(3)
  O92: empty(5)
    51:                                                                            O: O96 (evaluate-operator)
    52:                                                                            ==>S: S53 (operator no-change)
 5:2 3:3
    53:                                                                               O: C67 (pour)
  POUR(3:3,5:2)
  POUR(3:0,5:5)
 5:5 3:0
    54:                                                                               ==>S: S55 (operator tie)
  O104: fill(3)
  O105: pour(5:5,3:0)
  O103: empty(5)
    55:                                                                                  O: O108 (evaluate-operator)
    56:                                                                                  ==>S: S57 (operator no-change)
 5:5 3:0
    57:                                                                                     O: C72 (empty)
  EMPTY(5)
 5:0 3:0
    58:                                                                                     ==>S: S59 (operator tie)
  O112: fill(5)
  O110: fill(3)
    59:                                                                                        O: O114 (evaluate-operator)
    60:                                                                                        ==>S: S61 (operator no-change)
 5:0 3:0
    61:                                                                                           O: C77 (fill)
  FILL(3)
 5:0 3:3
    62:                                                                                           ==>S: S63 (operator tie)
  O117: pour(3:3,5:0)
  O118: empty(3)
  O116: fill(5)
    63:                                                                                              O: O119 (evaluate-operator)
    64:                                                                                              ==>S: S65 (operator no-change)
 5:0 3:3
    65:                                                                                                 O: C82 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    66:                                                                                                 ==>S: S67 (operator tie)
  O126: fill(5)
  O127: fill(3)
  O128: pour(5:3,3:0)
  O125: empty(5)
    67:                                                                                                    O: O130 (evaluate-operator)
    68:                                                                                                    ==>S: S69 (operator no-change)
 5:3 3:0
    69:                                                                                                      O: C87 (fill)
  FILL(3)
 5:3 3:3
    70:                                                                                                      ==>S: S71 (operator tie)
  O137: pour(3:3,5:3)
  O138: empty(3)
  O136: fill(5)
  O133: empty(5)
    71:                                                                                                         O: O141 (evaluate-operator)
    72:                                                                                                         ==>S: S73 (operator no-change)
 5:3 3:3
    73:                                                                                                            O: C92 (fill)
  FILL(5)
 5:5 3:3
    74:                                                                                                            ==>S: S75 (operator tie)
  O147: empty(5)
  O143: empty(3)
    75:                                                                                                               O: O148 (evaluate-operator)
    76:                                                                                                               ==>S: S77 (operator no-change)
 5:5 3:3
    77:                                                                                                                  O: C97 (empty)
  EMPTY(5)
 5:0 3:3
    78:                                                                                                                  ==>S: S79 (operator tie)
  O152: fill(5)
  O153: pour(3:3,5:0)
  O150: empty(3)
    79:                                                                                                                     O: O154 (evaluate-operator)
    80:                                                                                                                     ==>S: S81 (operator no-change)
 5:0 3:3
    81:                                                                                                                        O: C102 (fill)
  FILL(5)
 5:5 3:3
    82:                                                                                                                        ==>S: S83 (operator tie)
  O160: empty(5)
  O157: empty(3)
    83:                                                                                                                           O: O162 (evaluate-operator)
    84:                                                                                                                           ==>S: S85 (operator no-change)
 5:5 3:3
    85:                                                                                                                              O: C107 (empty)
  EMPTY(3)
 5:5 3:0
    86:                                                                                                                              ==>S: S87 (operator tie)
  O165: fill(3)
  O166: pour(5:5,3:0)
  O164: empty(5)
    87:                                                                                                                                 O: O167 (evaluate-operator)
    88:                                                                                                                                 ==>S: S89 (operator no-change)
 5:5 3:0
    89:                                                                                                                                    O: C112 (fill)
  FILL(3)
 5:5 3:3
    90:                                                                                                                                    ==>S: S91 (operator tie)
  O173: empty(3)
  O170: empty(5)
    91:                                                                                                                                       O: O175 (evaluate-operator)
    92:                                                                                                                                       ==>S: S93 (operator no-change)
 5:5 3:3
    93:                                                                                                                                          O: C117 (empty)
  EMPTY(5)
 5:0 3:3
    94:                                                                                                                                          ==>S: S95 (operator tie)
  O178: fill(5)
  O179: pour(3:3,5:0)
  O176: empty(3)
    95:                                                                                                                                             O: O182 (evaluate-operator)
    96:                                                                                                                                             ==>S: S97 (operator no-change)
 5:0 3:3
    97:                                                                                                                                                O: C122 (empty)
  EMPTY(3)
 5:0 3:0
    98:                                                                                                                                                ==>S: S99 (operator tie)
  O186: fill(3)
  O184: fill(5)
    99:                                                                                                                                                   O: O187 (evaluate-operator)
   100:                                                                                                                                                   ==>S: S101 (operator no-change)
 5:0 3:0
   101:                                                                                                                                                      O: C127 (fill)
  FILL(3)
 5:0 3:3
   102:                                                                                                                                                      ==>S: S103 (operator tie)
  O191: pour(3:3,5:0)
  O192: empty(3)
  O190: fill(5)
   103:                                                                                                                                                         O: O195 (evaluate-operator)
   104:                                                                                                                                                         ==>S: S105 (operator no-change)
 5:0 3:3
   105:                                                                                                                                                            O: C132 (fill)
  FILL(5)
 5:5 3:3
   106:                                                                                                                                                            ==>S: S107 (operator tie)
  O199: empty(5)
  O196: empty(3)
   107:                                                                                                                                                               O: O200 (evaluate-operator)
   108:                                                                                                                                                               ==>S: S109 (operator no-change)
 5:5 3:3
   109:                                                                                                                                                                  O: C137 (empty)
  EMPTY(5)
 5:0 3:3
   110:                                                                                                                                                                  ==>S: S111 (operator tie)
  O204: fill(5)
  O205: pour(3:3,5:0)
  O202: empty(3)
   111:                                                                                                                                                                     O: O207 (evaluate-operator)
   112:                                                                                                                                                                     ==>S: S113 (operator no-change)
 5:0 3:3
   113:                                                                                                                                                                        O: C142 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
   114:                                                                                                                                                                        ==>S: S115 (operator tie)
  O213: fill(5)
  O214: fill(3)
  O215: pour(5:3,3:0)
  O212: empty(5)
   115:                                                                                                                                                                           O: O217 (evaluate-operator)
   116:                                                                                                                                                                           ==>S: S117 (operator no-change)
 5:3 3:0
   117:                                                                                                                                                                              O: C147 (fill)
  FILL(3)
 5:3 3:3
   118:                                                                                                                                                                              ==>S: S119 (operator tie)
  O224: pour(3:3,5:3)
  O225: empty(3)
  O223: fill(5)
  O220: empty(5)
   119:                                                                                                                                                                                 O: O226 (evaluate-operator)
   120:                                                                                                                                                                                 ==>S: S121 (operator no-change)
 5:3 3:3
   121:                                                                                                                                                                                    O: C152 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
   122:                                                                                                      O: O137 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
   123:                                                 O: O57 (fill)
  FILL(3)
 5:3 3:3
   124:                                                 O: O244 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
   125:       O: O8 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
   126:       O: O253 (fill)
  FILL(3)
 5:3 3:3
   127:       O: O255 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
   128: O: O2 (fill)
  FILL(3)
 5:0 3:3
   129: O: O262 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
   130: O: O266 (fill)
  FILL(3)
 5:3 3:3
   131: O: O268 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
Interrupt received.
This Agent halted.

An agent halted during the run.

Listagem 18 - Resultado da execução do programa water-jug-look-ahead.soar.

Há dois efeitos colaterais que podem ser percebidos na implementação desta estratégia de planejamento. Um deles é que para cada operador de seleção há um impasse de empate e a criação de uma pilha de subestados para processamento do impasse. Se a solução foi encontrada, ela é usada apenas localmente para selecionar o operador do impasse de empate mais recente. Como resultado, será necessário redescobrir a solução retornando na hierarquia de subestados (backtracking). Outro problema é que o sistema frequentemente revisitará o mesmo estado e gerando um impasse de empate idêntico em um nível adicional na hierarquia de estados.

O primeiro problema deve ser resolvido utilizando-se um mecanismo de aprendizado, chamado chunking. O segundo, pode ser resolvido por uma heurística envolvendo a avaliação de estados que já estão na pilha marcados como falha. Isso significa que se um operador está sendo avaliado e caso ele produza um estado duplicado de um estado anterior (que está na pilha), então ele pode ser considerado uma falha. A regra que detecta a falha é mostrada na Listagem 19.

sp {water-jug*evaluate*state*failure*duplicate
   (state <s2> ^name water-jug
               ^superstate-set <s1>
               ^jug <i1>
               ^jug <i2>
               ^tried-tied-operator)
   (<i1> ^volume 5 ^contents <c1>)
   (<i2> ^volume 3 ^contents <c2>)
   (<s1> ^name water-jug
         ^desired <d>
         ^jug <j1>
         ^jug <j2>)
   (<j1> ^volume 5 ^contents <c1>)
   (<j2> ^volume 3 ^contents <c2>)
-->
   (<s2> ^failure <d>)}

Listagem 19 - Regra para deteção de estados com falha no do programa water-jug-look-ahead.soar.

Com a implementação desta regra e mais duas que tratam da elaboração do conjunto de superestados do operador de impasse de empate, é possível reduzir consideravelmente a revisitação aos estados de falha. O programa, desta forma, chega a solução do problema com maior rapidez. A Figura 10 mostra o resultado da execução do programa water-jug-look-ahead.soar no SoarDebugger. A Listagem 20 expande o resultado mostrado na Figura 10 exibindo a saída por completo.

Figura 10 - Execução do programa water-jug-look-ahead.soar no SoarDebugger.

source {C:\dev\Soar\Agents\water-jug-look-ahead\water-jug-look-ahead.soar}
**************************************************************************************
Total: 96 productions sourced.
run
     1: O: O1 (initialize-water-jug-look-ahead)
 5:0 3:0
     2: ==>S: S3 (operator tie)
  O2: fill(3)
  O3: fill(5)
     3:    O: O5 (evaluate-operator)
     4:    ==>S: S5 (operator no-change)
 5:0 3:0
     5:       O: C7 (fill)
  FILL(5)
 5:5 3:0
     6:       ==>S: S7 (operator tie)
  O8: pour(5:5,3:0)
  O9: empty(5)
  O6: fill(3)
     7:          O: O12 (evaluate-operator)
     8:          ==>S: S9 (operator no-change)
 5:5 3:0
     9:             O: C12 (fill)
  FILL(3)
 5:5 3:3
    10:             ==>S: S11 (operator tie)
  O16: empty(3)
  O13: empty(5)
    11:                O: O18 (evaluate-operator)
    12:                ==>S: S13 (operator no-change)
 5:5 3:3
    13:                   O: C17 (empty)
  EMPTY(5)
 5:0 3:3
    14:                   ==>S: S15 (operator tie)
  O21: fill(5)
  O22: pour(3:3,5:0)
  O19: empty(3)
    15:                      O: O23 (evaluate-operator)
    16:                      ==>S: S17 (operator no-change)
 5:0 3:3
    17:                         O: C22 (fill)
  FILL(5)
 5:5 3:3
    18:                      O: O24 (evaluate-operator)
    19:                      ==>S: S19 (operator no-change)
 5:0 3:3
    20:                         O: C25 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    21:                         ==>S: S21 (operator tie)
  O34: fill(5)
  O35: fill(3)
  O36: pour(5:3,3:0)
  O33: empty(5)
    22:                            O: O37 (evaluate-operator)
    23:                            ==>S: S23 (operator no-change)
 5:3 3:0
    24:                               O: C30 (fill)
  FILL(5)
 5:5 3:0
    25:                            O: O39 (evaluate-operator)
    26:                            ==>S: S25 (operator no-change)
 5:3 3:0
    27:                               O: C33 (pour)
  POUR(5:3,3:0)
  POUR(5:0,3:3)
 5:0 3:3
    28:                            O: O38 (evaluate-operator)
    29:                            ==>S: S27 (operator no-change)
 5:3 3:0
    30:                               O: C36 (fill)
  FILL(3)
 5:3 3:3
    31:                               ==>S: S29 (operator tie)
  O59: pour(3:3,5:3)
  O60: empty(3)
  O58: fill(5)
  O55: empty(5)
    32:                                  O: O62 (evaluate-operator)
    33:                                  ==>S: S31 (operator no-change)
 5:3 3:3
    34:                                     O: C41 (empty)
  EMPTY(3)
 5:3 3:0
    35:                                  O: O64 (evaluate-operator)
    36:                                  ==>S: S33 (operator no-change)
 5:3 3:3
    37:                                     O: C44 (empty)
  EMPTY(5)
 5:0 3:3
    38:                                  O: O61 (evaluate-operator)
    39:                                  ==>S: S35 (operator no-change)
 5:3 3:3
    40:                                     O: C47 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
    41:                               O: O59 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
    42:                         O: O35 (fill)
  FILL(3)
 5:3 3:3
    43:                         O: O91 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
    44:                   O: O22 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    45:                   O: O100 (fill)
  FILL(3)
 5:3 3:3
    46:                   O: O102 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
    47:             O: O13 (empty)
  EMPTY(5)
 5:0 3:3
    48:             O: O110 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    49:             O: O113 (fill)
  FILL(3)
 5:3 3:3
    50:             O: O115 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
    51:       O: O6 (fill)
  FILL(3)
 5:5 3:3
    52:       O: O9 (empty)
  EMPTY(5)
 5:0 3:3
    53:       O: O124 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    54:       O: O127 (fill)
  FILL(3)
 5:3 3:3
    55:       O: O129 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
    56: O: O3 (fill)
  FILL(5)
 5:5 3:0
    57: O: O2 (fill)
  FILL(3)
 5:5 3:3
    58: O: O137 (empty)
  EMPTY(5)
 5:0 3:3
    59: O: O140 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
    60: O: O143 (fill)
  FILL(3)
 5:3 3:3
    61: O: O145 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
Interrupt received.
This Agent halted.

An agent halted during the run.

Listagem 20 - Resultado da execução do programa water-jug-look-ahead.soar com heurística para detecção de falhas.

Na próxima seção será apresentado o mecanismo de aprendizado implementado no Soar.

Chunking

O chunking é invocado quando um resultado é produzido em um subestado. Este resultado dará origem a uma regra implícita criada a partir do estado atual, dos elementos da memória de trabalho e do resultado produzido. Se os WMEs envolvidos no processamento do subestado de avaliação estiverem ligados ao superestado, eles tornam-se as condições desta nova regra e o resultado é dado como a ação.

Este processo requer que o Soar mantenha uma cópia de cada disparo de regra instanciada no subestado. Uma vez que todos as condições da regra foram satisfeitas, o Soar converte todos os identificadores que estavam na memória de trabalho em variáveis e adiciona a regra na memória de produção. A regra passa a estar disponível imediatamente.

Devido ao fato do chunking ser baseado na resolução do problema em um subestado, a generalidade de toda regra é determinada pelo que foi testado pelas regras que participaram do produção do resultado. Se as regras originais testaram elementos da memória de trabalho que não eram necessários para a produção do resultado, então o chunk também as testará e nova regra será bem específica.

Para fazer uso do chunking, é necessário indicar no programa ou digitar no SoarDebugger o comando: learn --on. A Figura 11 mostra a execução do programa water-jug-look-ahead.soar com o aprendizado habilitado no SoarDebugger. A Listagem 21 mostra o resultado completo da execução.

Figura 11 - Execução do programa water-jug-look-ahead.soar com o comando learn --on no SoarDebugger.

source {C:\dev\Soar\Agents\water-jug-look-ahead\water-jug-look-ahead.soar}
learning is on
**************************************************************************************
Total: 96 productions sourced.

run
     1: O: O1 (initialize-water-jug-look-ahead)
 5:0 3:0
     2: O: O3 (fill)
  FILL(5)
 5:5 3:0
     3: O: O2 (fill)
  FILL(3)
 5:5 3:3
     4: O: O5 (empty)
  EMPTY(5)
 5:0 3:3
     5: O: O8 (pour)
  POUR(3:3,5:0)
  POUR(3:0,5:3)
 5:3 3:0
     6: O: O11 (fill)
  FILL(3)
 5:3 3:3
     7: O: O13 (pour)
  POUR(3:3,5:3)
  POUR(3:1,5:5)
 5:5 3:1
Interrupt received.
This Agent halted.

An agent halted during the run.

print --chunks

chunk-68*d51*tie*2 
chunk-67*d51*opnochange*1 
chunk-66*d47*tie*2 
chunk-65*d47*opnochange*1 
chunk-64*d39*tie*2 
chunk-63*d39*opnochange*1 
chunk-62*d36*tie*2 
chunk-61*d36*opnochange*1 
chunk-60*d34*tie*2 
chunk-59*d34*opnochange*1 
chunk-58*d33*tie*2 
chunk-57*d33*opnochange*1 
chunk-56*d30*tie*2 
chunk-55*d30*opnochange*1 
chunk-54*d19*tie*2 
chunk-53*d19*opnochange*1 
chunk-52*d13*tie*2 
chunk-51*d13*opnochange*1 

Listagem 21 - Resultado da execução do programa water-jug-look-ahead.soar com o uso do chunking.

O comando print --chunks mostra os chunks criados durante a execução do programa. Eles representam o aprendizado obtido durante a busca pela solução do problema.

A Listagem 22 mostra duas das regras criadas na memória de produção pelo mecanismo de chunking do Soar (chunk-68*d51*tie*2 e chunk-67*d51*opnochange*1).

sp {chunk-68*d51*tie*2
   :chunk
    (state <s1> ^name water-jug ^operator <o1> + ^problem-space <p1>
                ^desired <d1> ^jug <j1> ^jug <j2>)
    (<o1> ^name fill ^jug <j2>)
    (<p1> ^name water-jug)
    (<j1> ^contents 0 ^volume 3)
    (<j2> ^contents 0 ^volume 5)
    (<d1> ^jug <j3>)
    (<j3> ^contents 1 ^volume 3)
-->
    (<s1> ^operator <o1> >)}

sp {chunk-67*d51*opnochange*1
   :chunk
    (state <s1> ^operator <o1> ^evaluation <e1>)
    (<o1> -^default-desired-copy yes ^name evaluate-operator
          ^superproblem-space <s2> ^superoperator <s3> ^evaluation <e1>
          ^superstate <s4>)
    (<s2> ^name water-jug)
    (<s3> ^name fill ^jug <j2>)
    (<s4> ^name water-jug ^jug <j1> ^jug <j2>)
    (<e1> ^desired <d1>)
    (<j1> ^contents 0 ^volume 3)
    (<j2> ^contents 0 ^volume 5)
    (<d1> ^jug <j3>)
    (<j3> ^contents 1 ^volume 3)
-->
    (<e1> ^symbolic-value success +)}

Listagem 21 - Regras criadas automaticamente pelo mecanismo de chunking do Soar.

A regra acima foi criada pelo mecanismo de aprendizado. Esta regra, por exemplo, indica que o operador que propõe transferências de um litro de água para o jarro que cabem três quando este estiver está vazio, levará a um estado que está na rota de sucesso na busca pela solução.

Planejamento e Apredizado no problema dos Missionários e Canibais

Neste experimento serão implementadas as estratégias de planejamento e aprendizado para o problema dos Missionários e Canibais discutido anteriormente a partir da adaptação do código-fonte do programa existente. Os passos listados a seguir realizam esta implementação:

1. Adição das regras pré-definidas de seleção;
2. Adição as instruções para cópia de informações do estado e espaço de problema;
3. Modificação da regra de detecção de alcance do objetivo;
4. Modificação da regra de deteção de falhas;
5. Adição da regra de detecção de estado duplicado;
6. Remoção das regras envolvidas com a memorização do último operador.

A Listagem 22 mostra a implementação destes passos:

# Passo 1 -------------------------------------------

pushd ../default
source selection.soar
popd

# Passo 2 -------------------------------------------

sp {mac*elaborate*problem-space
   (state <s> ^name mac)
-->
   (<s> ^problem-space <p>)
   (<p> ^name missionaries-and-cannibals
        ^default-state-copy yes
        ^two-level-attributes right-bank left-bank)}

# Passo 3 -------------------------------------------

sp {mac*detect*state*success
   (state <s> ^desired <d>
              ^<bank> <ls>)
   (<ls> ^missionaries <m>
         ^cannibals <c>)
   (<d> ^{ << right-bank left-bank >> <bank> } <dls>)
   (<dls> ^missionaries <m>
          ^cannibals <c>)
-->
   (<s> ^success <d>)}

# Passo 4 -------------------------------------------

sp {mac*evaluate*state*failure*more*cannibals
   (state <s> ^desired <d>
              ^<< right-bank left-bank >> <bank>)
   (<bank> ^missionaries { <n> > 0 }
           ^cannibals > <n>)
-->
   (<s> ^failure <d>)}

# Passo 5 -------------------------------------------

sp {mac*evaluate*state*failure*duplicate
   (state <s1> ^desired <d>
               ^right-bank <rb>
               ^left-bank <lb>)
   (<rb> ^missionaries <rbm> ^cannibals <rbc> ^boat <rbb>)
   (<lb> ^missionaries <lbm> ^cannibals <lbc> ^boat <lbb>)
   (state { <> <s1> <s2> }
          ^right-bank <rb2>
          ^left-bank <lb2>
          ^tried-tied-operator)
   (<rb2> ^missionaries <rbm> ^cannibals <rbc> ^boat <rbb>)
   (<lb2> ^missionaries <lbm> ^cannibals <lbc> ^boat <lbb>)
  -(state <s3> ^superstate <s2>)
-->
   (<s2> ^failure <d>)}

Listagem 22 - Adaptação do programa mac.soar para implementação de planejamento e aprendizado.

Depois destas alterações, a execução do programa é mostrada na Figura 12 no SoarDebugger com a opção de aprendizado desligada. A Listagem 23 contém a saída completa da execução.

Figura 12 - Execução do programa mac-planning.soar (learn --off) no SoarDebugger.

run
     1: O: O1 (initialize-mac-planning)
 M: 3, C: 3 B ~~~    M: 0, C: 0  
     2: ==>S: S3 (operator tie)
     3:    O: O7 (evaluate-operator)
     4:    ==>S: S5 (operator no-change)
 M: 3, C: 3 B ~~~    M: 0, C: 0  
     5:       O: C7 (move-boat)
 Move 1 cannibals
 M: 3, C: 2   ~~~ B  M: 0, C: 1  
     6:       O: O17 (move-boat)
 Move 1 cannibals
 M: 3, C: 3 B ~~~    M: 0, C: 0  
Duplicate State Detected.
     7:    O: O11 (evaluate-operator)
     8:    ==>S: S7 (operator no-change)
 M: 3, C: 3 B ~~~    M: 0, C: 0  
     9:       O: C10 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
 M: 2, C: 2   ~~~ B  M: 1, C: 1  
    10:       ==>S: S9 (operator tie)
    11:          O: O31 (evaluate-operator)
    12:          ==>S: S11 (operator no-change)
 M: 2, C: 2   ~~~ B  M: 1, C: 1  
    13:             O: C15 (move-boat)
 Move 1 missionaries
 M: 3, C: 2 B ~~~    M: 0, C: 1  
    14:             ==>S: S13 (operator tie)
    15:                O: O42 (evaluate-operator)
    16:                ==>S: S15 (operator no-change)
 M: 3, C: 2 B ~~~    M: 0, C: 1  
    17:                   O: C20 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
 M: 2, C: 1   ~~~ B  M: 1, C: 2  
Failure!
    18:                O: O43 (evaluate-operator)
    19:                ==>S: S17 (operator no-change)
 M: 3, C: 2 B ~~~    M: 0, C: 1  
    20:                   O: C23 (move-boat)
 Move 1 missionaries
Duplicate State Detected.
 M: 2, C: 2   ~~~ B  M: 1, C: 1  
    21:                O: O44 (evaluate-operator)
    22:                ==>S: S19 (operator no-change)
 M: 3, C: 2 B ~~~    M: 0, C: 1  
    23:                   O: C26 (move-boat)
 Move 2 missionaries
 M: 1, C: 2   ~~~ B  M: 2, C: 1  
Failure!
    24:                O: O46 (evaluate-operator)
    25:                ==>S: S21 (operator no-change)
 M: 3, C: 2 B ~~~    M: 0, C: 1  
    26:                   O: C29 (move-boat)
 Move 2 cannibals
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
    27:                   ==>S: S23 (operator tie)
    28:                      O: O81 (evaluate-operator)
    29:                      ==>S: S25 (operator no-change)
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
    30:                         O: C34 (move-boat)
 Move 2 cannibals
Duplicate State Detected.
 M: 3, C: 2 B ~~~    M: 0, C: 1  
    31:                   O: O78 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
    32:                   ==>S: S27 (operator tie)
    33:                      O: O94 (evaluate-operator)
    34:                      ==>S: S29 (operator no-change)
 M: 3, C: 1 B ~~~    M: 0, C: 2  
    35:                         O: C39 (move-boat)
 Move 1 cannibals
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
    36:                         O: O101 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
Duplicate State Detected.
    37:                      O: O93 (evaluate-operator)
    38:                      ==>S: S31 (operator no-change)
 M: 3, C: 1 B ~~~    M: 0, C: 2  
    39:                         O: C42 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
 M: 2, C: 0   ~~~ B  M: 1, C: 3  
Failure!
    40:                      O: O96 (evaluate-operator)
    41:                      ==>S: S33 (operator no-change)
 M: 3, C: 1 B ~~~    M: 0, C: 2  
    42:                         O: C45 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
    43:                         ==>S: S35 (operator tie)
    44:                            O: O128 (evaluate-operator)
    45:                            ==>S: S37 (operator no-change)
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
    46:                               O: C50 (move-boat)
 Move 2 cannibals
 M: 1, C: 3 B ~~~    M: 2, C: 0  
Failure!
    47:                            O: O126 (evaluate-operator)
    48:                            ==>S: S39 (operator no-change)
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
    49:                               O: C53 (move-boat)
 Move 2 missionaries
Duplicate State Detected.
 M: 3, C: 1 B ~~~    M: 0, C: 2  
    50:                            O: O125 (evaluate-operator)
    51:                            ==>S: S41 (operator no-change)
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
    52:                               O: C56 (move-boat)
 Move 1 missionaries
 M: 2, C: 1 B ~~~    M: 1, C: 2  
Failure!
    53:                            O: O124 (evaluate-operator)
    54:                            ==>S: S43 (operator no-change)
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
    55:                               O: C59 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
 M: 2, C: 2 B ~~~    M: 1, C: 1  
    56:                               ==>S: S45 (operator tie)
    57:                                  O: O169 (evaluate-operator)
    58:                                  ==>S: S47 (operator no-change)
 M: 2, C: 2 B ~~~    M: 1, C: 1  
    59:                                     O: C64 (move-boat)
 Move 1 missionaries
 M: 1, C: 2   ~~~ B  M: 2, C: 1  
Failure!
    60:                                  O: O168 (evaluate-operator)
    61:                                  ==>S: S49 (operator no-change)
 M: 2, C: 2 B ~~~    M: 1, C: 1  
    62:                                     O: C67 (move-boat)
 Move 2 cannibals
 M: 2, C: 0   ~~~ B  M: 1, C: 3  
Failure!
    63:                                  O: O166 (evaluate-operator)
    64:                                  ==>S: S51 (operator no-change)
 M: 2, C: 2 B ~~~    M: 1, C: 1  
    65:                                     O: C70 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
Duplicate State Detected.
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
    66:                                  O: O167 (evaluate-operator)
    67:                                  ==>S: S53 (operator no-change)
 M: 2, C: 2 B ~~~    M: 1, C: 1  
    68:                                     O: C73 (move-boat)
 Move 1 cannibals
 M: 2, C: 1   ~~~ B  M: 1, C: 2  
Failure!
    69:                               O: O165 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
    70:                               ==>S: S55 (operator tie)
    71:                                  O: O215 (evaluate-operator)
    72:                                  ==>S: S57 (operator no-change)
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
    73:                                     O: C78 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
 M: 1, C: 3 B ~~~    M: 2, C: 0  
Failure!
    74:                                  O: O214 (evaluate-operator)
    75:                                  ==>S: S59 (operator no-change)
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
    76:                                     O: C81 (move-boat)
 Move 2 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
    77:                                     O: O230 (move-boat)
 Move 2 missionaries
Duplicate State Detected.
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
    78:                                  O: O212 (evaluate-operator)
    79:                                  ==>S: S61 (operator no-change)
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
    80:                                     O: C84 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
    81:                                     ==>S: S63 (operator tie)
    82:                                        O: O243 (evaluate-operator)
    83:                                        ==>S: S65 (operator no-change)
 M: 0, C: 3 B ~~~    M: 3, C: 0  
    84:                                           O: C89 (move-boat)
 Move 1 cannibals
Duplicate State Detected.
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
    85:                                     O: O242 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
    86:                                     ==>S: S67 (operator tie)
    87:                                        O: O256 (evaluate-operator)
    88:                                        ==>S: S69 (operator no-change)
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
    89:                                           O: C94 (move-boat)
 Move 1 missionaries
 Move 1 cannibals
 M: 1, C: 2 B ~~~    M: 2, C: 1  
Failure!
    90:                                        O: O258 (evaluate-operator)
    91:                                        ==>S: S71 (operator no-change)
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
    92:                                           O: C97 (move-boat)
 Move 2 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
    93:                                           O: O276 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
Duplicate State Detected.
    94:                                        O: O259 (evaluate-operator)
    95:                                        ==>S: S73 (operator no-change)
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
    96:                                           O: C100 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
    97:                                           ==>S: S75 (operator tie)
    98:                                              O: O291 (evaluate-operator)
    99:                                              ==>S: S77 (operator no-change)
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   100:                                                 O: C105 (move-boat)
 Move 1 missionaries
Duplicate State Detected.
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   101:                                              O: O292 (evaluate-operator)
   102:                                              ==>S: S79 (operator no-change)
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   103:                                                 O: C108 (move-boat)
 Move 1 cannibals
 M: 1, C: 0   ~~~ B  M: 2, C: 3  
Failure!
   104:                                           O: O287 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
Success!
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
   105:                                     O: O254 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   106:                                     ==>S: S81 (operator tie)
   107:                                        O: O317 (evaluate-operator)
   108:                                     O: O316 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   109:                               O: O208 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   110:                               ==>S: S83 (operator tie)
   111:                                  O: O326 (evaluate-operator)
   112:                               O: O325 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   113:                               O: O328 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   114:                               O: O335 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   115:                         O: O119 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   116:                         ==>S: S85 (operator tie)
   117:                            O: O347 (evaluate-operator)
   118:                            ==>S: S87 (operator no-change)
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   119:                               O: C117 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   120:                               O: O353 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0
   121:                               O: O358 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   122:                               O: O359 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   123:                               O: O366 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   124:                         O: O343 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   125:                         O: O375 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   126:                         O: O377 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   127:                         O: O378 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   128:                         O: O385 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   129:                   O: O92 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
   130:                   O: O395 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   131:                   O: O399 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   132:                   O: O401 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   133:                   O: O406 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   134:                   O: O407 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2
   135:                   O: O414 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3
Success!
   136:             O: O41 (move-boat)
 Move 2 cannibals
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
   137:             ==>S: S89 (operator tie)
   138:                O: O422 (evaluate-operator)
   139:                ==>S: S91 (operator no-change)
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
   140:                   O: C122 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
   141:                   O: O429 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
   142:                   O: O434 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   143:                   O: O438 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   144:                   O: O440 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   145:                   O: O445 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   146:                   O: O446 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   147:                   O: O453 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   148:             O: O420 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
   149:             O: O461 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
   150:             O: O467 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   151:             O: O471 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   152:             O: O473 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   153:             O: O478 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   154:             O: O479 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   155:             O: O486 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   156:       O: O28 (move-boat)
 Move 1 missionaries
 M: 3, C: 2 B ~~~    M: 0, C: 1  
   157:       O: O494 (move-boat)
 Move 2 cannibals
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
   158:       O: O497 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
   159:       O: O501 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
   160:       O: O507 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   161:       O: O511 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   162:       O: O513 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   163:       O: O518 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   164:       O: O519 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2
   165:       O: O526 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
   166: O: O6 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2   ~~~ B  M: 1, C: 1  
   167: O: O533 (move-boat)
 Move 1 missionaries
 M: 3, C: 2 B ~~~    M: 0, C: 1  
   168: O: O539 (move-boat)
 Move 2 cannibals
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
   169: O: O540 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
   170: O: O544 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
   171: O: O550 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
   172: O: O554 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
   173: O: O556 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
   174: O: O561 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
   175: O: O562 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
   176: O: O569 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
Interrupt received.
This Agent halted.

An agent halted during the run.

Listagem 23 - Resultado da execução do programa mac-planning.soar sem aprendizado.

A execução do programa sem o mecanismo de aprendizado levou o equivalente a 176 ciclos de decisão para esta simulação. Tentativas subsequentes levarão a números bem próximos.

Veremos o resultado da execução com o mecanismo de aprendizado ativado. A Figura 13 mostra o resultado da execução no SoarDebugger. A Listagem 24 traz a saída completa da execução.

Figura 13 - Execução do programa mac-planning.soar (learn --on) no SoarDebugger.

run
     1: O: O1 (initialize-mac-planning)
 M: 3, C: 3 B ~~~    M: 0, C: 0  
     2: O: O6 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2   ~~~ B  M: 1, C: 1  
     3: O: O8 (move-boat)
 Move 1 missionaries
 M: 3, C: 2 B ~~~    M: 0, C: 1  
     4: O: O14 (move-boat)
 Move 2 cannibals
 M: 3, C: 0   ~~~ B  M: 0, C: 3  
     5: O: O15 (move-boat)
 Move 1 cannibals
 M: 3, C: 1 B ~~~    M: 0, C: 2  
     6: O: O19 (move-boat)
 Move 2 missionaries
 M: 1, C: 1   ~~~ B  M: 2, C: 2  
     7: O: O25 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 2, C: 2 B ~~~    M: 1, C: 1  
     8: O: O29 (move-boat)
 Move 2 missionaries
 M: 0, C: 2   ~~~ B  M: 3, C: 1  
     9: O: O31 (move-boat)
 Move 1 cannibals
 M: 0, C: 3 B ~~~    M: 3, C: 0  
    10: O: O36 (move-boat)
 Move 2 cannibals
 M: 0, C: 1   ~~~ B  M: 3, C: 2  
    11: O: O37 (move-boat)
 Move 1 missionaries
 M: 1, C: 1 B ~~~    M: 2, C: 2  
    12: O: O44 (move-boat)
 Move 1 cannibals
 Move 1 missionaries
 M: 0, C: 0   ~~~ B  M: 3, C: 3  
Success!
Interrupt received.
This Agent halted.

Listagem 24 - Resultado da execução do programa mac-planning.soar com aprendizado.

Para a execução do programa considerando o mecanismo de aprendizado foram necessários 12 ciclos de decisão. Este número é consideravelmente menor que os 176 ciclos obtidos sem o uso do mecanismo de aprendizado. Pode-se notar que as regras criadas pelo mecanismo de chuncking contribui decisivamente para a eficiência na busca pelo espaço do problema.

3.2.3. Resultados

Nesta atividade foram alguns realizados experimentos que exploraram os mecanismos de planejamento e aprendizado disponíveis no Soar. No primeiro experimento, foi realizada a adaptação do programa existente para o problema dos jarros d'água (Water Jug problem) utilizando estratégias de planejamento. Neste caso particular, o tipo de planejamento estudado foi o planejamento olhar-adiante (look-ahead planning). No segundo experimento, foi realizada a adaptação do programa existente para o problema dos missionários e canibais (Missionaries and Canibals problem) também utilizando estratégias de planejamento. Neste caso particular, foi explorado também o mecanismo de aprendizado chamado chunking.

Os estudos e experimentos realizados nesta atividade permitiram:

• o entendimento da estratégia de planejamento look-ahead;
• o entendimento de como esta estratégia deve ser realizada em um programa Soar;
• o entendimento sobre a manipulação do impasse de empate de operador e do problema da seleção;
• o entendimento do mecanismo de aprendizado conhecido como chunking;
• o entendimento de como depurar a execução de um programa Soar que utiliza planejamento e aprendizado.

Os resultados obtidos durante as simulações envolvendo aprendizagem permitiram comprovar a eficiência deste mecanismo na busca pela solução do problema. O número de ciclos de decisão necessários para atingir o estado desejado quando o aprendizado é ativado é bem menor se comparado ao número de ciclos quando ele está desativado. Esta fato é justificado pela criação de regras internas que representam o aprendizado de situações que não contribuem para a solução do problema.

4.  Conclusão

Nesta aula foram contemplados importantes aspectos da arquitetura Soar: o planejamento e o aprendizado. Sabendo que o Soar é uma arquitetura com foco na resolução de problemas, estes aspectos são de extrema relevância. Com a exploração de dois problemas bastante conhecidos da Inteligência Artificial Clássica (o problema dos jarros d'água e o problema dos missionários e canibais), foi possível compreender como devem ser concebidas as etapas para a implementação de estratégias de planejamento e, em seguida, como ativar o aprendizado para obter uma maior eficiência na busca pela solução.

O planejamento é importante porque permite que o agente explore os cenários possíveis para chegar à solução através da busca pelo espaço do problema. A representação do problema na mente do agente é feita pela criação de elementos na memória de trabalho que representam o estado inicial. Da mesma forma, é realizada a representação do estado desejado, aquele que, quando atingido, assume-se que o problema está resolvido. Através do impasse de empate de operador, novos subestados são criados caracterizando o problema da seleção. A solução deste subproblema através de avaliações realizadas por regras e operadores específicos geram resultados. Tais resultados revelam se as manipulações realizadas nos subestados conduziram à solução do problema ou, pelo menos, que permitiu uma aproximação deste. A comparação entre as várias avaliações realizadas e resultados gerados permitem estabelecer a obtenção da meta. A vantagem desta abordagem é que ela viabiliza que o agente possa planejar suas ações antes de atuar no ambiente, o que configura um comportamento esperado em sistemas inteligentes.

O aprendizado é importante porque permite que o agente otimize a exploração pelo espaço do problema aproveitando-se de um conhecimento obtido previamente. Este conhecimento é gerado e armazenado na memória do agente a partir de generalizações feitas a partir da explanação de uma situação sob avaliação. Esta situação é uma variação do estado original que é avaliado a partir da comparação com o estado desejado. O aprendizado é implementado através de regras criadas internamente com base no estado atual, nos elementos da memória de trabalho envolvidos na análise do subproblema e do resultado gerado por este análise. Estas regras tornam-se disponíveis imediatamente após o aprendizado garantindo que situações equivalentes não exijam uma nova análise por parte do agente, uma vez que o resultado já é conhecido. A vantagem desta abordagem é a agilidade com que a busca pelo espaço do problema é conduzida já que, a partir do que foi aprendido, o agente conhece previamente o resultado de operações que, sem o aprendizado, teriam que ser processadas a cada execução. A eficiência é facilmente notada quando o mecanismo de aprendizado é ativado. Os cuidados a ser tomados em relação à aprendizagem dizem respeito ao uso de avaliações, que são apenas heurísticas e podem prejudicar a captura de aspectos relacionados ao sucesso ou falha.

Por fim, estes dois mecanismos permitem que os agentes, agora, apresentem um comportamento mais sofisticado pela possibilidade de planejar suas ações ou propor soluções a partir de informações obtidas sobre o problema a ser resolvido e da possibilidade de expandir seus conhecimentos a partir do aprendizado obtido durante a exploração do problema e da descoberta da solução.