Aula 5

Relatório

Durante a aula 5 foram estudados os tutoriais 4 e 5, dessa maneira foi dividida a aula em duas partes: a primeira parte consiste no desenvolvimento para resolução do problema dos Missionários e a segunda na inclusão de aprendizado para a resolução do problema.

Figura1 - Configuração Inicial do problema

No problema dos canibais e missionários, três missionários e três canibais devem atravessar um rio com um barco que pode transportar no máximo duas pessoas, sob a restrição de que, para ambas as margens, se há missionários presentes naquela margem, eles não podem ser ultrapassados pelo número de canibais na mesma margem (se fossem, os canibais comeriam os missionários.) O barco não pode atravessar o rio por si só, sem pessoas a bordo.

Para a resolução do problema, precisamos mapear o espaço do problema e a representação dos estados.

A figura abaixo mostra uma representação simples do problema, incluindo os estados não aceitáveis para resolução (mais canibais do que missionários quando algum missionário esta presente), representados com um X e os estados válidos.

Figura2 - Espaço de estados do problema

Para a implementação em Soar, precisamos definir tambem como esse ambiente será representado no Soar. Dentre várias opções, a seguinte representação foi escolhida.

Figura3 - Representação dos elementos em forma de Grafo para ser mapeado no Soar.

No VisualSoar essa representação pode ser vista nos datamaps.

Figura4 - Datamap no VisualSoar

sp {mac*apply*initialize-mac
  (state <s> ^operator.name initialize-mac)
  -->
  (<s> ^name mac
          ^left-bank <l>             #>lado esquerdo do rio
          ^right-bank <r>           #>lado direito do rio
  (<r> ^missionaries 0           #>inicialização dos elementos do lado direito
         ^cannibals 0
         ^boat 0
         ^other-bank <l>)
  (<l> ^missionaries 3           #>inicialização dos elementos do lado esquerdo    
         ^cannibals 3
         ^boat 1
         ^other-bank <r>)}
 

A implementação dos operadores foram divididas em 3 tipos:

• Mover apenas uma pessoa (missionário ou canibal)

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

• Mover duas pessoas do mesmo tipo (missionários ou canibais)

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

• Mover uma pessoa de cada tipo (missionário ou canibal)

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

Com isso definimos as movimentações possíveis para a resolução do nosso problema.

A definição do objetivo do nosso programa é muito importante. Uma vez que chegamos na solução, devemos parar a aplicação. Para detecção do goal, usamos um elemento criado na memória de trabalho chamado ^desired que possui o lado do rio e a quantidade de cada elemento a ser satisfeita. Uma vez a condição é satisfeita, o programa é interrompido

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

Com esse desenvolvimento, pudemos ver a primeira execução da aplicação.

Figura5 - Primeira execução do desenvolvimento ainda incompleto - Falha

Nota-se que a falha se dá por que o Soar entrou em um dos estados proibidos para a resolução do problema (elementos marcados com X na Figura2) e isso foi apontado por um mecanismo de monitoramento, que checa por essas condições. Uma solução para esse impasse é a implementação do controle de busca para desfazer uma ação e seguir por outro caminho.

Figura6 - Execução da primeira parte. 198 decisões para a solução

Nessa primeira aplicação, o Soar toma decisões que nos levam a uma falha, a qual resolvemos com o controle de busca. Porém para determinados problemas, não podemos deixar transpassar para o ambiente externo esse tipo de situação. Com isso no Tutorial 5, fazemos uma implementação de planning, que planeja e testa os movimentos internamente antes de executa-lo externamente. Outra melhoria que estudamos foi o sistema de Chunking, que alimenta a inteligencia do Soar e melhora os resultados a cada execução.

Podemos ver nas figuras a seguir os Traces do Soar avaliando ações e tambem alguns aprendizados.

Figura7 - Avaliações de operadores

Figura8 - Aprendizados - operadores criados para ajudar na tomada de decisão

Após fazer a implementação da segunda parte da aula, alguns ajustes foram necessários no primeiro programa para lidar com aprendizagem e fazer com que o Soar trabalhasse com o Chunking. O resultado obtido na primeira rodada foi similar ao programa sem aprendizado, porém a partir da segunda rodada, houve notória melhoria.

Figura9 - Primeira execução de um programa com chunking

Figura10 - Segunda execução de um programa com chunking

O mecanismo de Chunk é automatico do Soar, bastando apenas habilitar a opção de aprendizado

• learn –-on

Durante o tutorial um problema com chunking foi analisado. Com a regra de aplicação do move-boat inicialmente implementada, o tipo do elemento sendo movido não estava sendo aprendido. Isso fazia com que em algumas rodadas o Soar nunca conseguisse chegar na solução do problema. Isso por que o Soar passava pela situação abaixo:

O operador aprendido diz que se o estado atual tem dois missionários e dois canibais e o barco, rejeite um operador que move um missionário e o barco para o outro lado.

Porém quando executamos a solução ótima, vemos que uma situação similar acontece e é um caminho obrigatório para a resolução do problema.

 M: 1, C: 1   ~~~ B  M: 2, C: 2  

Referencias

• Wikipedia - http://pt.wikipedia.org/wiki/Problema_dos_canibais_e_mission%C3%A1rios
• Tutorial 4, Tutorial 5, Códigos mac e mac-planning do pacote do Tutorial Soal
• Manual do Soar