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

Primeira parte - Planejamento "look-ahead"

published by aluno2 on Wed, 04/17/2013 - 20:46
 
 
Esta atividade corresponde à execução do tutorial 5 do Soar.
 
Este tutorial é sobre o planejamento de ações a partir da técnica de OLHAR ADIANTE ("look-ahead") e está dividido em duas partes, correspondendo à aplicação de alterações nos programas do "water-jug" e "missionaries-and-cannibals" de forma a convertê-los ao uso dessa técnica de planejamento.
 
 
Esta técnica do "look-ahead" consiste em - dado um determinado estado de um problema - avaliar internamente as diversas alternativas de operadores propostos antes de aplicá-las de fato ao estado real do problema. Essa análise visa tentar definir quais operadores devem ser aplicados, tendo-so em vista atingir um resultado desejado.
 
Por fim, os resultados dessas análises internas podem ser armazenados em regras que passam então a fazer parte do conjunto que o Soar utilizar para resolver o problema em questão; essa operação é o aprendizado.
 
 
Característica do Soar: o planejamento é feito sob demanda, apenas quando o conhecimento diretamente descrito nas regras é insuficiente para a tomada de decisão. Neste ponto o Soar difere de muitos sistemas que aplicam o planejamento numa abordagem de 2 fases, onde primeiramente ocorre a etapa de planejamento e depois a etapa de execução do plano.
 
 

Planejamento via operadores de avaliação

 
A ideia básica da técnica de planejamento "look-ahead" é a seguinte: quanto um "tie impasse" ocorre, onde múltiplos operadores são propostos para um dado estado do problema e torna-se necessário Soar definir qual operador aplicar, um subestado é criado para que regras de preferência sejam avaliadas para cada um dos operadores que estão em impasse; à medida que essas regras de preferência são valiadas, no momento em que um operador passa a ser dominante (ter maior preferência) sob os demais, o impasse é resolvido, o subestado é destruído e o operador é aplicado no estado original.
 
A análise de preferência consiste em avaliar a distância de um hipotético novo estado atingido, caso o operador sendo avaliado seja aplicado ao problema. Dessa maneira, durante o processo de avaliação de um operador, pode ser necessária a aplicação de uma sequência de outros operadores até que se possa avaliar a distância do estado resultante para um estado final - o qual pode ser um estado de FALHA ou de SUCESSO.
 
O uso de subestados permite, então, que Soar utilize seu mecanismo regular de funcionamento para resolver "tie-impasses", simplesmente definindo um conjunto de regras para executar as seguintes tarefas:
 
  1. Uma vez surgido um "tie-impase", cada operador que o gerou está indicado numa extensão "^item"; nesse ponto, é preciso criar um subestado para avaliar cada um desses operadores e determinar sua preferência.
  2. Esse subestado deve ser uma CÓPIA do estado atual do problema (onde o impasse foi gerado) de forma que seja possível aplicar a ele o
  3. operador e avaliar a distância do resultado de um estado final.
Soar define um conjunto de regras de SELEÇÃO padrão, o qual é distribuído em conjunto; na distribuição utilizada, esse conjunto de regras é o seguinte:
 
.../SoarTutorial_9.3.2-Linux_64bit/Agents/default/selection.soar
 
 
Nesse conjunto são definidas 74 regras que implementam as operações  que sustentam esse mecanismo de planejamento look-ahead. Uma simples análise do nome das regras propostas permite a identificação das principais operações executadas:
 
  1. Cópia do estado original
evaluate-operator*elaborate*operator*add-attribute-to-duplicate-operator*nln 
evaluate-operator*elaborate*operator*add-duplicated-attribute-to-duplicate-operator 
evaluate-operator*elaborate*operator*add-attribute-to-duplicate-operator 
evaluate-operator*elaborate*state*create-duplicates-table-for-operator-only 
evaluate-operator*elaborate*operator*copy-default-operator-copy-from-problem-space 
evaluate-operator*elaborate*operator*default-operator-copy-is-yes 
duplicate-desired*replace-old-value 
duplicate-desired*copy-old-value 
 

 

  1. Aplicação do operador sendo avaliado
selection*elaborate*evaluate-operator*superstate 
selection*elaborate*evaluate-operator*superproblem-space 
selection*apply*state*evaluation 
selection*select*evaluate-operator*indifferent 
selection*propose*evaluate-operator 

 

 

  1. Avaliação do resultado obtido e sua conversão em regras de preferência
selection*compare*novalue-evaluation-always-worse 
selection*elaborate*state*found-value-true 
selection*elaborate*state*all-objects-evaluated 
selection*select*partial-failure-evaluation-becomes-worst-preference 
selection*select*indifferent-evaluation-becomes-indifferent-preference 
selection*select*prohibit-failure-evaluation-becomes-prohibit-preference 
selection*select*exhaustion-failure-evaluation-becomes-reject-preference 
selection*select*failure-evaluation-becomes-reject-preference 
selection*select*success-evaluation-becomes-best-preference 
selection*select*required-success-evaluation-becomes-required-preference 
selection*compare*partial-failure-evaluation-better-than-failure 
selection*compare*success-evaluation-better-than-partial-success 
selection*compare*same-symbolic-evaluations-are-indifferent*exhaustion-failure 
selection*compare*same-symbolic-evaluations-are-indifferent 
selection*compare*prefer-lower-evaluation 
selection*compare*higher-evaluation-better 
selection*compare*equal-evaluation-indifferent 

 

  1. Identificação de estados finais
top-goal*halt*failure 
top-goal*halt*success 
 
 

Descrição do mecanismo e modificações necessárias para sua utilização

 
Algumas características principais do mecanismo de avaliação de operadores, implementado pelo conjunto "selection.soar", está descrito a seguir.
 
 

Representação do subestado de seleção

 
O subestado de seleção, criado quando ocorre um "tie-impasse", possui as seguintes extensões principais:
 
  • "^operator": operador sendo avaliado
  • "^symbolic-value": resultado simbólico da avaliação - "success/partial-success/partial-failure/failure/indifferent"
  • "^numeric-value": resultado numérico da avaliação
  • "^value == true": indica se o operador já foi avaliado, tendo ou um resultado simbólico ou numérico
  • "^desired": identificador que contém o estado final desejado, que será comparado para determinar a distância do objetivo final.
 
O mecanismo propõe apenas o operador "evaluate-operator", criado com preferência indiferente para cada um dos operadores que estavam em impasse.
 
Durante o processo de aplicação do operador "evaluate-operator", são criadas extensões contendo a seguinte estrutura de dados para a avaliação:
 
(<s> ^evaluation <e>
     ^operator <o>)
(<e> ^superoperator <so>
     ^desired <d>)
(<o> ^name evaluate-operator
     ^superoperator <so>
     ^evaluation <e>
     ^superstate <ss>
     ^superproblem-space <sp>)
 
 
O atributo "superproblem-space": deve conter a representação do estado atual do problema, utilizado durante as etapas de avaliação.
 
 

Avaliação de um operador

 
O processo de avaliação de um operador, dentro do mecanismo de SELEÇÃO pode ser descrito da seguinte forma:
 
  • A avaliação é realizada em um novo subestado, criado a partir da cópia do estado da tarefa original; as regras padrão "selection.soar" se encarregam de fazer essa cópia.
  • Uma vez criado esse novo subestado, o operador sendo avaliado é então aplicado a ela.
  • Se o estado final desse subestado, após a aplicação do operador, puder ser avaliado a partir da comparação com o estado desejado (extensão "^desired"), essa avaliação é retornada e o subestado destruído.
  • Caso o estado final não possa ser avaliado, a tarefa original continua a ser executada nesse estado cópia, até que se atinja um estado que possa ser avaliado; esse processo corresponde então à execução normal da tarefa, porém sobre uma cópia dos dados: novos operadores podem ser propostos e novos "tie-impasses" podem ocorrer o que termina por criar uma cascata de estados de SELEÇÃO.
 
 

Regras para cópias das extensões

 
Conforme visto acima, durante o processo de avaliação do operador, é preciso copiar tanto as extensões do estado original (da tarefa em execução que está em "tie-impasse") quanto o próprio operador a ser testado. Isso porque não se deseja alterar as extensões originais.
 
Essa cópia é realizada por regras definidas pelo conjunto padrão "selection.soar"; essas regras podem ter seu comportamento configurado a partir de extensões criadas no estado original da tarefa:
 
  • "default-state-copy == no": não copia nada automaticamente
  • "one-level-attributes |<object>|": copia apenas o primeiro nível de extensões do atributo parâmetro
  • "two-level-attributes |<object>|": copia dois níveis de extensões do atributo parâmetro
  • "all-attributes-at-level one"
  • "all-attributes-at-level two"
  • "dont-copt <object>": indicação para não copiar o objeto "<object>"
  • "dont-copy-anything"
  • "default-operator-copy no" : indicação explícita para que não seja realizada a cópia automática do operador.
 
Essas definições podem ser criadas como descrição do espaço do problema, no estado original da tarefa:
 
 
 
 
Quando a solução do problema original envolve interface com um componente externo, deverão ser criadas regras para simulação - muitas vezes imprecisas - do resultado para o mundo exterior da aplicação do operador.
 
 
 

Modificação do programa Water-Jug

 
  1. Tal como diretamente proposto pelo tutorial, ocorre um problema com o cálculo da extensão "^empty": durante a cópia, o valor original de "^empty" é copiado, criando um objeto "^jug" onde essa extensão não foi gerada por uma elaboração. Dessa forma, o valor originalmente copiado nunca é apagado e a jarra fica com duas extensões "^empty", o que altera o funcionamento das regras de proposição e aplicação dos operadores. Com esse acúmulo de valores, são criados alguns cenários impossíveis no problema original.

 

 

Para resolver esse problema é preciso acrescentar a regra "^dont-copy empty" de configuração do mecanismo de cópia; assim, no estado cópia a extensão passa a ser criada apenas pela elaboração.

 
 
  1. Apenas com o uso do planejamento "look-ahead" o programa "water-jug" passou a resolver o problema numa média de 48,9 ciclos Soar, sendo que o melhor resultado foi obtido com 20 ciclos e o pior com 70. Na média existe um ganho de performance, quando comparado com o programa original, que teve a média de 64,6 ciclos; entretanto, o programa original obteve o melhor resultado de 15 ciclos, mas com o pior de 218 ciclos.
 
  1. Mesmo utilizando o mecanismo de aprendizagem via CHUNKING (veja maiores detalhes sobre o processo de aprendizagem na segunda parte deste relatório, sobre as modificações no programa "missionaries-and-cannibals deste mesmo tutorial), se for deixado o comando "halt"  na regra original que verifica se atingiu ou não a solução do problema, a performance máxima não é atingida, ficando a impressão de que o processo de aprendizagem não se completa: o programa demorou uma média de 21,7 ciclos para resolver o problema (em 10 execuções), sendo que o melhor resultado foi 18 ciclos e o pior 32 ciclos (primeira execução).

Exemplo de execução mantendo-se o comando "halt" na regra de detecção de objetivo final

 

Se o comando "halt" for removido, deixando que as próprias regras do conjunto padrão "selection.soar" detectem o estado final, o programa chega a aprender a resolver da melhor maneira possível, em apenas 5 ciclos logo na segunda execução, sendo que na primeira foram necessários 53 ciclos.:

 

 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer