Planning and Learning

Neste capítulo vai-se estudar uma forma de planejamento chamada chunking ela permite fazer um planejamento simples de mirar-na-frente. Este tipo de planejamentos podem aumentar a velocidade de resolução de problemas como o Water Jug e o de Missionários e Canibais.

Neste planejamento o programa vai tentar utilizar operadores internamente para avaliá-los antes de que eles sejam aplicados.

1. The Water Jug Problem

O primeiro passo para que o SOAR possa utilizar o planejamento é eliminar as preferências de aleatoriedade em la proposição dos operadores. A preferência de aleatoriedade deve ser usada só quando é sabido que um operador não é melhor do que outro, e não quando não é sabido qual operador é melhor.

A saído do SOAR com a preferência aleatória é a seguinte  

O programa resolve o problema corretamente, mas quando é eliminada a condição de aleatoriedade na proposta do operador fill a saída do SOAR é:

O SOAR cria automaticamente um novo subestado em situações onde as preferências dos operadores são insuficientes para selecionar somente um. Esto é chamado de tie impasse. Para solucionar o tie impasse deve-se determinar qual regra de aplicação de que operador é o melhor aplicar no estado atual. Esto será logrado selecionado e aplicando operadores de avaliação no subespaço. O objetivo de estos operadores é avaliar as tarefas e converter os dados em preferencias para a tarefa do operador. Quando um número suficiente de preferências foram criadas para selecionar uma, ela será selecionada, e el subestado será removido automaticamente do working memory.

O problema de resolver um tie impasse é chamado de problema de Seleção (Selection problem). SOAR vem um com conjunto de operadores e regras de avaliação e comparação de operadores em um tie impasse.

1.1 Selection State Representation

Para o problema da seleção cada estado deve conter uma série de augmentations, que serão uteis mais na frente, assim cada estado terá a seguente estrutura:

• Operador <o> que será o identificador do operador na tarefa a ser evaluado

• valor simbólico success/partial-success/partial-failure/failure/indifferent

• valor numérico [number]

• value true indicará se existe um valor numerico ou simbolico

• desired <d> identificador do estado desejado para ser usado na avaliação

1.2 Selection Initial State Creation

A primeira regra será a regra de inicialização:

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

1.3 Selection Operator Proposal

O único operado no problema se Seleção é o operador de avaliação (evaluate-operator) Ele deve ser proposto se existe um item que não tenha uma avaliação com valor. O operador criara primeiro uma avaliação e depois calcular o valor.

Em inglês a regra é:

##Selection*propose*evaluate-operator
#If the state is named selection and there is an item that does not have an evaluation with a value, then
#propose the evaluate-operator for that item.

No SOAR ela é:

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

1.4 Selection Operator Application

A aplicação dos operadores de evaluate-operator tem duas partes, a primeira parte é a criação da estrutura de dados de avaliação, mas sem valor nenhum. Em paralelo são criadas estruturas adicionais para fazer a aplicação mais simples.

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

A desired augmentation é um objeto que descreve o estado desejado da tarefa original. A estrutura do estado desejado é incluída para que a avaliação do operador se possa basear em quanto esse operador ajuda a obter o estado desejado.

O superproblem-space augmentation é o espaço de problema do objeto do superestado.

A segunda parte da aplicação do operador é o calculo da avaliação. Este subestado é chamado de problema de avaliação.

Os aspectos que tem que realizar são:

1. Criar o estado inicial.

2. Selecionar o operador a ser avaliado.

3. Aplicar o operador selecionado.

4. Avaliar os resultados

1.4.1 Creating the Initial State

O estado inicial deve ser uma copia do estado onde foi gerado o tie impasse. Foram criadas uma seria de regras gerais que podem copiar todas as estruturas do estado.

Neste caso a regra pode ser:

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

1.4.2 Selecting the operator being evaluated

Uma vez que o estado inicial é criado, é necessária uma copia do operador que será avaliado. A copia do estado é feita automaticamente pelo SOAR.

1.4.3 Applying the selected operator

Uma vez que o operador seja selecionado, as regras para aplicá-lo serão executadas e modificará a copia do estado. Não é necessário criar o modificar nenhuma regra existente

1.4.4 Evaluating the result

Uma vez que o novo estado é criado pode-se fazer a avaliação dele. A avaliação mais simples de calcular é se o novo estado tem sucesso ou não. Sucesso é quando o objetivo é atingido.

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

Além de Sucesso e Falha a regra de avaliação podem processar outros tipos de avaliações simbólicas ou numéricas.

As preferências simbólicas são:

• Sucesso: O estado é o estado desejado. Esto é traduzido como a melhor preferência

• Sucesso-Parcial: Este estado está no caminho do estado desejado. Esto é traduzido como uma melhor preferência.

• Indiferente: O estado não é nem de sucesso nem de falha, neste caso ele é traduzido como uma preferência indiferente.

• Falha-Parcial: Todos os caminhos deste estado levam à falha. Esto é traduzido como uma pior preferência.

Para as avaliações numéricas será criado um atributo chamado ^numeric-value

As duas regras necessárias para a avaliação são:

sp {Impasse__Operator_Tie*elaborate*superstate-set
(state <s> ^superstate <ss>)
-->
(<s> ^superstate-set <ss>)}

sp {Impasse__Operator_Tie*elaborate*superstate-set2
(state <s> ^superstate.superstate-set <ss>)
-->
(<s> ^superstate-set <ss>)}

e

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

1.4.5 Chunking

Chunking é executado quando um resultado é produzido em um subestado. Chunking examina os elementos na working memory que foram utilizados pela regra que crio o resultado.

Para utilizar Chunking só tem que colocar learn --on no VisualSoar ou como uma linha no arquivo que contem as regras. Para ver quando Chunking é criado e executado só tem que por watch --chunks --print.

A saída do VisualSoar é:

2. The Missionaries and Cannibals Problem

Nesta seção se falará sobre as modificações e novas regras para adicionar o uso de planejamento para o problema de missionários e canibais.

2.1 Conversion to Planning and Learning

2.1.1 Add selection rules

O primeiro passo é adicionar a linha que inclui as regras de seleção:

pushd ../default
source selection.soar
popd

2.1.2 Add problem space and state copying information

O segundo passo é agregar a regra que define o espaço de problema e especifica como deve ser feita a copia do estado. Para este problema é necessária a copia de dois níveis:

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

2.1.3 Modify goal detection

A terceira parte é modificar a regra de detecção do objetivo que criara uma avaliação simbólica de sucesso.

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

2.1.4 Modify failure detection

Neste problema tem-se que modificar a regra de falha para que crie um valor simbólico de falha.

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

2.1.5 Add duplicate state detection rule

O quinto passo é agregar uma regra que detecte quando existem estados duplicados no stack e avaliar o mais recente como falha.

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

2.1.6 Remove last-operator rules

A regra de last-operator não é mais necessária porque as regras anteriores detectam, trcam e melhoram o processamento.

Com estas seis mudanças o programa deve ser capais de resolver o problema com planejamento.

A saída do SOAR é apresentada a seguir:

2.3 Numeric Evaluations

Sem chunking, o soar toma muito tempo em resolver o problema porque ele não leva em conta nenhuma informação de avaliação hasta que o problema seja resulto. Para que o SOAR não demore tanto tempo é agregar uma função de avaliação numérica. Por exemplo pode-se preferir operadores que levem maior número de missionários e canibais à borda do rio desejada. Assim a regra de inizialização será modificada para:

sp {mac*apply*initialize-mac
   (state <s> ^operator.name initialize-mac)
-->
   (<s> ^right-bank <r>
        ^left-bank <l>
        ^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 <dl>
        ^better higher)
   (<dl> ^missionaries 3
         ^cannibals 3
         ^boat 1)}

A regra que calcula o número de canibais e missionários é:

sp {mac*evaluate*state*number
   (state <s> ^desired <d>
              ^tried-tied-operator
              ^<bank> <ls>)
   (<ls> ^missionaries <m>
         ^cannibals <c>)
   (<d> ^{ << right-bank left-bank >> <bank> } <dls>)
-->
   (<s> ^numeric-value (+ <m> <c>))}