You are here

Home » Courses » IA006 » Apresentação de Atividades » Apresentação de Atividades - Turma 2013 » Aluno 2 » Aula 5 - 05/04/2013 - Tutorial 4 e Tutorial 5 » Atividade 2 - execução do tutorial 5 - planejamento e aprendizagem - relatório em elaboração

Segunda parte - aprendizado via "chunking"

published by aluno2 on Wed, 04/17/2013 - 20:48
 
A segunda parte do tutorial 5 corresponde à alteração do programa "missionaries-and-cannibals" para utilizar planejamento e também maiores detalhes a respeito do processo de chunking, incluindo o uso de valores numéricos para permitir a comparação de estados intermediários entre o SUCESSO e FALHA.
 
 

Utilização do planejamento "look-ahead"

 
A conversão do programa "missionaries-and-cannibals" para utilizar planejamento é bastante simples, seguindo a mesma receita do que foi feito no programa "water-jug":
 
  • Adição da extensão "^problem-space", contendo detalhes para execução da cópia do estado original a ser utilizada no subestado de SELEÇÃO.
  • Modificação da detecção de objetivo final e falha, com a criação das extensões "^success <desired>" e "^failure <desired>" respectivamente.
  • Adição da regra para indicar falha no caso de estado duplicado durante o processo de SELEÇÃO.

 

Foi indicado no tutorial que com o planejamento as regras de armazenamento e seleção dos operadores inversos, no caso de atingir um estado com falha, poderiam ser removidas, uma vez que esses estados já serão evitados durante o planejamento.

Entretanto, sem essas regras e com a remoção do comando "halt" na regra de detecção do estado final, com o aprendizado (CHUNKING) desabilitado o programa simplesmente não parou no estado final, embora o atingisse diversas vezes durante as etapas de SELEÇÃO; não foi feita uma análise aprofundada, mas aparentemente o programa não conseguiu convergir para a solução no estado original, uma vez que permanecia aplicando operadores inversos e desfazendo os passos que haviam sido feitos.

 

Performance com planejamento e aprendizado

 
Sem planejamento, o programa "missionaries-and-cannibals" teve uma performance média de 86,77 ciclos Soar em 13 execuções, com melhor resultado de 24 ciclos e pior resultado de 256 ciclos.
 
Como indicado no tutorial, com o uso de planejamento e aprendizado, a performance da primeira resolução cai para uma média de 148,7 ciclos, com 135 ciclos de melhor resultado e 170 ciclos de pior resultado; entretanto, depois de resolvido o problema uma vez, a solução sempre é obtida em exatos 12 ciclos (11 ciclos da melhor solução mais 1 de inicialização). Durante a resolução do problema, o mecanismo de chunking criou em média 71,7 regras (47 mínimo 106 máximo) que depois são utilizadas para resolver o problema em tempo ótimo.
 
A explicação desse fenômeno é porque com o planejamento availando apenas estados de SUCESSO e FALHA o problema é resolvido várias vezes, em cada processo de SELEÇÃO.
 
 

Avaliação de estados intermediários entre SUCESSO e FALHA - uso de valores numéricos

 
Esta segunda parte do tutorial introduz o uso de valores numéricos para permitir a avaliação de estados intermediários entre o SUCESSO e FALHA. No problema em questão é considerado que é melhor o estado onde mais pessoas estão no lado final desejado do rio. Para isso, é preciso primeiramente indicar a condição para o conjunto de regras padrão "selection.soar", o que é feito com a extensão "^better higher". tal como abaixo:
 
 
É também necessário criar uma regra que calcule a extensão "^numeric-value" para cada estado:
 
 
Com o uso do valor numérico o programa passa a convergir a um resultado, não apresentando o problema descrito acima, mesmo com o aprendizado desabilitado. A performance média foi de 238,3 ciclos, com melhor resultado em 143 ciclos e pior em 341 ciclos.
 
Com o aprendizado habilitado, no entando, a performance caiu, não atingindo mais a resolução ótima a toda execução, com uma performance final (após resolver uma vez o problema) média de 23 ciclos (12 ciclos melhor resultado, 48 ciclos pior resultado). A performance da primeira execução não alterou, ficando com uma média de 149,3 ciclos (145 ciclos melhor resultado, 159 pior resultado).
 
A explicação desse comportamento é o fato de que a aproximação feita pela avaliação númérica implementada na regra "mac*evaluate*state*number" não é exata: de fato, durante a solução do problema em alguns instantes é necessário diminuir o número de pessoas no lado final do rio, como por exemplo no ponto onde se deseja levar todos os canibais para o lado oposto.
 
A seguir está a sequência de resolução ótima do problema com os operadores executados e estados atingidos em negrito:
 
run
     1: O: O1 (initialize-missionaries-and-cannibals)
 
 Proposing move 1 cannibals from left
 Proposing move 1 missionaries from left
 Proposing move 2 cannibals(s) from left
 Proposing move 2 missionaries(s) from left
 Proposing move 1 missionary and 1 cannibal from left
 
     2: O: O6 (move)
 Move 1 cannibals(s) to right
 Move 1 missionaries(s) to right
 M:2, C:2 ~~~~~ B M:1, C:1
 
 Proposing move 1 missionary and 1 cannibal from right
 Proposing move 1 missionaries from right
 Proposing move 1 cannibals from right
 
     3: O: O8 (move)
 Move 1 missionaries(s) to left
 M:3, C:2 B ~~~~~ M:0, C:1
 
 Proposing move 1 missionary and 1 cannibal from left
 Proposing move 1 missionaries from left
 Proposing move 2 missionaries(s) from left
 Proposing move 1 cannibals from left
 Proposing move 2 cannibals(s) from left
 
     4: O: O14 (move)
 Move 2 cannibals(s) to right
 M:3, C:0 ~~~~~ B M:0, C:3
 
 Proposing move 1 cannibals from right
 Proposing move 2 cannibals(s) from right
 
     5: O: O15 (move)
 Move 1 cannibals(s) to left
 M:3, C:1 B ~~~~~ M:0, C:2
 
 Proposing move 1 missionaries from left
 Proposing move 1 cannibals from left
 Proposing move 2 missionaries(s) from left
 Proposing move 1 missionary and 1 cannibal from left
 
     6: O: O19 (move)
 Move 2 missionaries(s) to right
 M:1, C:1 ~~~~~ B M:2, C:2
 
 Proposing move 1 cannibals from right
 Proposing move 1 missionaries from right
 Proposing move 2 cannibals(s) from right
 Proposing move 2 missionaries(s) from right
 Proposing move 1 missionary and 1 cannibal from right
 
     7: O: O25 (move)
 Move 1 cannibals(s) to left
 Move 1 missionaries(s) to left
 M:2, C:2 B ~~~~~ M:1, C:1
 
 Proposing move 1 cannibals from left
 Proposing move 1 missionaries from left
 Proposing move 2 cannibals(s) from left
 Proposing move 2 missionaries(s) from left
 Proposing move 1 missionary and 1 cannibal from left
 
     8: O: O29 (move)
 Move 2 missionaries(s) to right
 M:0, C:2 ~~~~~ B M:3, C:1
 
 Proposing move 1 cannibals from right
 Proposing move 1 missionaries from right
 Proposing move 2 missionaries(s) from right
 Proposing move 1 missionary and 1 cannibal from right
 
     9: O: O31 (move)
 Move 1 cannibals(s) to left
 M:0, C:3 B ~~~~~ M:3, C:0
 
 Proposing move 1 cannibals from left
 Proposing move 2 cannibals(s) from left
 
    10: O: O36 (move)
 Move 2 cannibals(s) to right
 M:0, C:1 ~~~~~ B M:3, C:2
 
 Proposing move 1 missionaries from right
 Proposing move 1 cannibals from right
 Proposing move 2 missionaries(s) from right
 Proposing move 2 cannibals(s) from right
 Proposing move 1 missionary and 1 cannibal from right
 
    11: O: O37 (move)
 Move 1 missionaries(s) to left
 M:1, C:1 B ~~~~~ M:2, C:2
 
 Proposing move 1 cannibals from left
 Proposing move 1 missionaries from left
 Proposing move 1 missionary and 1 cannibal from left
 
    12: O: O44 (move)
 Move 1 cannibals(s) to right
 Move 1 missionaries(s) to right
 M:0, C:0 ~~~~~ B M:3, C:3
 
 Proposing move 1 cannibals from right
 Proposing move 1 missionaries from right
 Proposing move 2 cannibals(s) from right
 Proposing move 2 missionaries(s) from right
 Proposing move 1 missionary and 1 cannibal from right
 
 Problem solved. right has 3 missionaries, 3 cannibals and 1 boat.
 
> Success state reached. S1
Interrupt received.
This Agent halted.
 
 
 

Análise das regras criadas a partir do CHUNKING

 
Nesta seção será feita uma breve análise das regras de CHUNKING que são disparadas na resolução do problema, depois que ele já foi resolvido uma vez e Soar aprendeu as regras de resolução. Estão analisados os primeiros 2 passos.
 
PRIMEIRO PASSO
 
Estado inicial:  
 
M:3, C:3 B ~~~~~ M:0, C:0
 
São propostas os seguntes operadores:
 
 Proposing move 1 cannibals from left
 Proposing move 1 missionaries from left
 Proposing move 2 cannibals(s) from left
 Proposing move 2 missionaries(s) from left
 Proposing move 1 missionary and 1 cannibal from left
 
Esses operadores disparam os seguintes CHUNKS:
 
print chunk-96*d5*tie*2
sp {chunk-96*d5*tie*2
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 3 ^cannibals 3 ^other <o1>)
    (<o1> ^missionaries 0)
    (<o2> ^from <l1> ^types 1 ^missionaries 2 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> -)
}
 
print chunk-183*d122*tie*2
sp {chunk-183*d122*tie*2
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^boat 1 ^missionaries 3 ^cannibals 3 ^other <o1>)
    (<o1> ^boat 0 ^other <l1> ^missionaries 0 ^cannibals 0)
    (<o2> ^boat 1 ^from <l1> ^types 2 ^missionaries 1 ^cannibals 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    (<d1> ^right <r1>)
    (<r1> ^missionaries 3 ^cannibals 3)
    -->
    (<s1> ^operator <o2> >)
}
 
print chunk-150*d72*tie*2
sp {chunk-150*d72*tie*2
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^operator <o3> + ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 2 ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^cannibals 2 ^name move)
    (<o3> ^from <l1> ^types 1 ^missionaries 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> = <o3>)
}
 
print chunk-151*d72*tie*3
sp {chunk-151*d72*tie*3
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^operator <o3> + ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 2 ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^missionaries 1 ^name move)
    (<o3> ^from <l1> ^types 1 ^cannibals 2 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> = <o3>)
}
 
print chunk-162*d78*tie*3
sp {chunk-162*d78*tie*3
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^operator <o3> + ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 2 ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^missionaries 1 ^name move)
    (<o3> ^from <l1> ^types 1 ^cannibals 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> = <o3>)
}
 
print chunk-165*d78*tie*6
sp {chunk-165*d78*tie*6
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^operator <o3> + ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 2 ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^cannibals 1 ^name move)
    (<o3> ^from <l1> ^types 1 ^missionaries 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> = <o3>)
}
 
print chunk-152*d72*tie*4
sp {chunk-152*d72*tie*4
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 2 ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1)
    (<o2> ^from <l1> ^types 1 ^missionaries 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> -)
}
 
print chunk-148*d69*tie*2
sp {chunk-148*d69*tie*2
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^cannibals 2 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> -)
}
 
print chunk-161*d78*tie*2
sp {chunk-161*d78*tie*2
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^operator <o3> + ^problem-space <p1> ^desired <d1>)
    (<l1> ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^cannibals 2 ^name move)
    (<o3> ^from <l1> ^types 1 ^cannibals 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> = <o3>)
}
 
print chunk-166*d78*tie*7
sp {chunk-166*d78*tie*7
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^operator <o3> + ^problem-space <p1> ^desired <d1>)
    (<l1> ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^cannibals 1 ^name move)
    (<o3> ^from <l1> ^types 1 ^cannibals 2 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> = <o3>)
}
 
print chunk-167*d78*tie*8
sp {chunk-167*d78*tie*8
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^cannibals 2 ^other <o1>)
    (<o1> ^missionaries 1 ^cannibals 1)
    (<o2> ^from <l1> ^types 1 ^cannibals 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o2> -)
}
 
 
Cada uma dessas regras de chunk captura o estado atual e um dos operadores propostos, definindo uma preferência para a sua aplicação. Dessa maneira, Soar executa o operador que foi definido como o melhor pelo "chunk-183*d122*tie*2", que corresponde justamente ao primeiro movimento da solução ótima:
 
     2: O: O6 (move)
 Move 1 cannibals(s) to right
 Move 1 missionaries(s) to right
 
 
SEGUNDO PASSO
 
Agora, o estado resultante é:
 
[VALID STATE] M:2, C:2 ~~~~~ B M:1, C:1
 
Neste estado são propostos os seguintes operadores:
 
 Proposing move 1 missionary and 1 cannibal from right
 Proposing move 1 missionaries from right
 Proposing move 1 cannibals from right
 
 
Eles, por sua vez, disparam as seguintes regras de CHUNKING:
 
print chunk-187*d148*tie*2
sp {chunk-187*d148*tie*2
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <o1> ^operator <o2> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^boat 0 ^missionaries 2 ^cannibals 2 ^other <o1>)
    (<o1> ^boat 1 ^other <l1> ^missionaries 1 ^cannibals 1)
    (<o2> ^boat 1 ^from <o1> ^types 1 ^missionaries 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    (<d1> ^right <r1>)
    (<r1> ^missionaries 3 ^cannibals 3)
    -->
    (<s1> ^operator <o2> >)
}
 
print chunk-103*d15*tie*4
sp {chunk-103*d15*tie*4
    :chunk
    (state <s1> ^name mac ^left <l1> ^right <r1> ^operator <o1> +
          ^problem-space <p1> ^desired <d1>)
    (<l1> ^missionaries 2 ^cannibals 2)
    (<r1> ^other <l1> ^cannibals 1)
    (<o1> ^from <r1> ^types 1 ^cannibals 1 ^name move)
    (<p1> ^name missionaries-and-cannibals)
    -->
    (<s1> ^operator <o1> -)
}
 
 
Mais uma vez Soar executa operador que foi definido como o melhor, neste passo pelo "chunk-187*d148*tie*2":
 
    3: O: O8 (move)
 Move 1 missionaries(s) to left
 
 M:3, C:2 B ~~~~~ M:0, C:1
 
 
 

Comentários

 
 
  • O comando "watch --chunk --print"  não foi encontrado, sendo apenas possível usar "watch --chunk", o qual foi utilizado em conjunto com o comando "watch --learning print" para visualizar os chunks à medida que era criados e utilizados.
  • Por erro de codificação, durante o processo de modificação do programa para a utilização do planejamento não foi retirado o operador de preferência INDIFERENTE de algum dos operadores; com essa indicação de indiferença o problema não era resolvido, pois o mecanismo de SELEÇÃO não era utilizado em todos os momentos, o que não permitia a exploração de todos os caminhos.
 

 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer