Missionaries and Cannibals

1. Missionaries and Cannibals Definition

A definição do problema é:

Três missionários e três canibais chegar a um rio. Há um barco na margem do rio que pode ser usado por uma ou duas pessoas de cada vez. Este barco deve ser usado para atravessar o rio de tal forma que nunca tenham mais canibais do que missionários em cada margem do rio (embora canibais podem estar sozinhos em uma margem do rio). Como podem os missionários e os canibais atravessar o rio com sucesso?

O primeiro passo para resolver o problema é decompor ele em duas partes: os estados do problema (problem space) que em SOAR são a representação de estados e operadores, e o problema (problem) que em SOAR representam o estado inicial e o estado desejado.  

O estado inicial do problema são três canibais, três missionários e um barco em um lado do rio:

O estado desejado são os três missionários e os três canibais do outro lado do rio.

Assim o espacio inicial de estados do problema pode começar assim:

Do gráfico anterior é importante lembrar que não é permitido que o número de canibais seja maior do que o número de missionários, por isso os dois primeiros estados da esquerda não são permitidos. E será necessária a criação de estados de falha (failure states).

Pode-se realizar uma lista dos aspectos importantes do problema e do espacio do problema que ajudarão na resolução dele.

1. A representação de estado: Para este problema o estado incluirá a posição dos missionários, dos canibais e do barco em relação ao rio.

2. A regra de criação do estado inicial: Neste problema todos os missionários, canibais e o barco estão no mesmo lado do rio.

3. As regras de proposição de operador: Para este problema os operadores moverão dois dos missionários e/ou canibais a traves do rio com o barco.

4. As regras de aplicação dos operadores.

5. As regras de monitoramento e de estados e operadores.

6. A regra que reconhece o estado desejado. Neste problema o estado desejado é alcançado quando todos os canibais e todos os missionários estejam do outro lado do rio.

7. A regra de falha: estas são regras que detectam quando um estado é criado no qual o objetivo não pode ser alcançado. Neste problema os estados de falha são aqueles onde o número de canibais é maior ao número de missionários em qualquer lado do rio.

8. As regras de controle de procura.

2. State Representation

Aqui são discutidos os aspectos que devem ser representados em cada estado. Neste problema todos os elementos são importantes, os missionários, os canibais, o rio e o barco são elementos que devem ser representados no estado.

É importante notar que não é necessário representar cada canibal ou cada missionário de forma individual, só é importante o número de eles em cada lado do rio. Também é importante notar que não é necessário ter um estado que represente o momento em que o barco tem canibais ou missionários, o que é importante do barco é saber em qual lado do rio ele está.

Assim os aspectos importantes nos estados são:

• O número de missionários em cada lado do rio

• O número de canibais em cada lado do rio

• O lado do rio onde o barco está.

Uma possível representação do estado poderia ser:

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

Mas, para ter operadores mais gerais é possível criar uma estrutura de estados diferentes, como por exemplo:

Estrutura de estados	Em Soar
	(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>)
	(state <s> ^missionaries <m> ^cannibals <c> ^boat <b>) (<m> ^left 3 ^right 0) (<c> ^left 3 ^right 0) (<b> ^left 1 ^right 0)

Durante o resto do tutorial vai-se utilizar a primeira estrutura de dados.

3. Initial State Creation: Initialize-mac

Nesta parte será proposto o operador de inicialização do estado. Do mesmo modo que foi feito com o Eaters, aqui é proposto um operador chamado initialize-mac e sua regra de aplicação:

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

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

4. Operator Proposal

Os operadores para esta tarefa deve mover 1 ou 2 indivíduos (missionários ou canibais) através do rio. Os operadores se podem dividir em 3 tarefas:

• Mover um missionário ou canibal para a outra margem

  • Teste que existe no mínimo um indivíduos do tipo dado na margem com o barco.

• Mover dois missionários ou dois canibais

  • Teste que existe no mínimo dois indivíduos do tipo dado na margem com o barco.

• Mover um missionário e um caniba

  • Teste que existe um de cada tipo dado na margem com o barco.

Estas regras em inglês são:

## mac*propose*move-mac-boat*1
# 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.

## mac*propose*move-mac-boat*2
# If the name of the state is mac
# and there are two or more cannibal or missionaries
# on the same bank of the river as the boat,
# then propose movingtwo of that type
# across the river.

## mac*propose*move-mac-boat*3
# 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.

Agora é necessário decidir nos parâmetros que devem levar em conta os operadores. Neste exemplo os parâmetros a levar em conta são:

• O nome do operador: move-mac-boat.

• O tipo de indivíduo a ser movido: canibal ou missionário

• O número de indivíduos a serem movidos: 1 ou 2

As regras de proposição podem aumentar os atributos do estado incluindo informação útil. Por exemplo se podem incluir as informações de que tipo de indivíduo está no barco e que número, etc. Para incluir está informação as propostas do operador vai ter a seguinte forma:

(<o> ^name move-mac-boat
     ^cannibal 1
     ^boat 1
     ^bank l3
     ^types 1)

Assim, os três operadores em Soar são:

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


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


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

5. Operator Application

As regras de aplicação dos operadores devem cambiar o estado para refletir o transporte de missionários e canibais de uma margem à outra. Graças à estrutura de estado estar definida do modo que ela está é possível criar só uma regra de aplicação que vai servir para as três regas de proposição.

A regra de aplicação em inglês é:

## mac*apply*move-mac-boat
# If there is a move-mac-boat operator selected for a type and number, then
# subtract the values of that type on the current bank and add those values
# to the other bank.

Está regra é um poco complexa de escrever em SOAR devido ao grande número de variáveis, então vai-se tentar escrever primeiro um casso especial para um canibal.

## mac*apply*move-mac-boat*one*cannibal
# If there is a move-mac-boat operator selected for one cannibal, then
# subtract one from cannibal object on the left bank and add one to the
# cannibal object on the other bank.

No SOAR está regra é:

sp {apply*move-mac-boat*one*cannibal
   (state <s> ^operator <o>)
   (<o> ^name move-mac-boat
        ^cannibal 1
        ^bank <bank>)
   (<bank> ^cannibal <bank-num>
           ^other-bank <obank>)
   (<obank> ^cannibal <obank-num>)
-->
   (<bank> ^cannibal <bank-num> -     // Primeiro é eliminado o valor
   (- <bank-num> 1))                  // e depois é criado novamente
   (<obank> ^cannibal <obank-num> -
   (+ <obank-num> 1))}

Agora é possível modificar a regra para que ela possa trasladar 1 ou 2 canibais. A regra modificada é:

Finalmente é aplicada a ultima generalização para que a regra posso mover missionários, canibais e o barco:

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

6. State and Operator Monitoring

A seguir são apresentadas três regras que monitoram o operador selecionado e o estado

sp {monitor*move-mac-boat
   (state <s> ^operator <o>)
   (<o> ^name move-mac-boat
        ^{ << cannibals missionaries >> <type> } <number>)
-->
   (write | 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> | |)}

A saída do VisualSoar até o momento é:

O programa vai rodar indefinidamente e ainda não reconhece o estado desejado.

7. Desired State Recognition

O seguinte passo é criar uma regra que reconheça quando o programa chegou a estado desejado. Esta regra escrita em inglês é:

# 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.

Em SOAR é:

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)}

Apos rodar o programa ele para quando seja alcançada a condição desejada.

8. State Failure Detection

Até agora o programa não reconhece os estados de falha, aqueles onde tem maior número de canibais do que missionários.

A regra em inglês é:

# 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.

No SOAR é:

sp {mac*evaluate*state*failure*more*cannibals
   (state <s> ^name mac
              ^<< right-bank left-bank >> <bank>)
   (<bank> ^missionaries {<ms> > 1}
           ^cannibals {<cn> > <ms>})
-->
   (write (crlf) |The problem has failed.|)
   (halt)}

A saída no Soar é:

9. Search Control: Undoing the Last Operator

Quando o programa encontra um estado de falha, é possível desfazer o último operador e tentar que o SOAR procure outra solução. Para poder desfazer o último operador é necessário lembrar qual foi. Para isso é aumentada a estrutura do estado atual por médio de duas 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.

No SOAR:

sp {mac*apply*move-mac-boat*record*last-operator*types*1
   (state <s> ^name mac
              ^operator <o>)
   (<o> ^name move-mac-boat
        ^types 1
        ^bank <bank>
        ^{ << missionaries cannibals >> <type> } <num>)
-->
   (<s> ^last-operator <lp>)
   (<lp> ^bank <bank>
         ^type <type>
         ^numerber <num>
         ^types 1)}

#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*apply*move-mac-boat*record*last-operator*types*2
   (state <s> ^name mac
              ^operator <o>)
   (<o> ^name move-mac-boat
        ^bank <bank>
        ^types 2)
-->
   (<s> ^last-operator <lp>)
   (<lp> ^bank <bank>
         ^types 2)}

A regra para eliminar antigos registros só é necessário testar si a margem do barco no registro do último operador não coincide com a margem onde atualmente está o barco, porque cada vez que o operador é aplicado o barco muda de margem.

#mac*apply*move-mac-boat*remove*old*last-operator
#If the move-mac-boat operator is selected
# and the boat in the last-operator is not equal
# to the bank of the current boat,
# then remove the last-operator structure.

No SOAR é

sp {mac*apply*move-mac-boat*remove*old*last-operator
   (state <s> ^name mac
              ^operator <o>
              ^<lr-bank>.other-bank <o-bank>
              ^last-operator <lo>)
   (<lo> ^bank <obank>)
-->
   (<s> ^last-operator <lo> -)}

Agora se deve modificar a regra de falha para que no detenha a execução do programa mas crie um atributo de falha:

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

Agora vão se criar regras de preferência para que o SOAR prefira aplicar a regra de desfazer quando o programa falhe. De novo são necessárias duas regras:

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

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


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

Para evitar que o operador desfaza um estado valido são propostas as seguentes 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 true
              ^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 true
              ^last-operator <lo>)
   (<o> ^types 2)
   (<lo> ^types 2)
-->
   (<s> ^operator <o> < )}

Finalmente o programa está completo e a saída do SOAR é:  

Da anterior imagem pode-se ver a aplicação da regra de desfazer quando o estado é o estado de falha.