You are here
Aula 05 - Soar
Resolução de Problemas, Planejamento e Aprendizado no SOAR
Soar is a general cognitive architecture for developing systems that exhibit intelligent behavior.
Resolução de Problemas: Missionários e Canibais no SOAR
Nesta seção exploramos o problema dos missionários e canibais, Tutorial 4, para tratar de uma das técnicas classicas da inteligência artificial: métodos de resolução por busca. Há diversas implementações do problema dos missionários e canibais: clique aqui para uma versão online do problema. A seguir fixamos o enunciado do problema:
Três canibais e três missionários em viagem chegam à margem de um rio. Eles desejam atravessar para a outra margem para poderem prosseguir em suas respectivas jornadas. O único meio de transporte disponível é um barco que comporta no máximo duas pessoas. Uma outra restrição envolve o número de canibais e missionários nas duas margens do rio: em nenhum momento o número de canibais pode ser superior ao número de missionários. Como efetuar a travessia?
Como nos problemas anteriores, é necessário expor o problema no formato apropriado do Soar: exibir uma representação da situação em termos de estados e operadores. Isto é, explicitar o estado inicial, o estado final, as operações que permitem a passagem de um estado para outro e os operadores de controle. Seguindo o esquema do Tutorial 4 (página 144), apresentamos uma lista das características (serve como especificação do problema) do espaço de problema e as dificuldades que definem o problema dos missionários e canibais.
- Representação: a escolha de uma representação (adequada) envolve a escolhas de quais são as informações relevantes para a resolução do problema. Neste caso, devemos representar os missionários, canibais, o barco e as margens do rio.
- A construção do espaço de estados: o estado inicial (ou a regra que cria o estado inicial). Neste caso, o estado inicial deve informar a posição dos três missionário, dos três canibais e do único barco. A posição refere-se à margem em que se encontram todos eles.
- Os operadores que permitem a transição entre estados: as regras que propõem os operadores de transição. Neste caso, os operadores devem respeitar a limitação do barco à dois passageiros no máximo.
- A aplicação dos operadores de transição: a regra que cuida da aplicação dos operadores de transição entre estados.
- As regras de controle: regras que monitoram os estados e os operadores criados no espaço de problema.
- A meta: a regra que reconhece se o objetivo foi alcançado. Neste caso, os três missionários, os três canibais e barco devem estar na margem oposta ao do início do problema.
- Ocorrências de ações não permitidas: regras que detectam se os estados criados violam as restrições estabelecidas. Neste caso, a restrição é a de que o número de canibais em qualquer uma das margens não deve ser maior que o número de missionários.
- Mecanismo de controle: as regras de controle.
A escolha de uma representação pode provocar o uso de diferentes recursos na resolução do problema.
Exemplo 1: Poder-se-ia adotar a seguinte representação: (m, m, m, c, c, c, b) tal que m, c e b são variáveis no domínio {e, d}. A variável m está associada aos missionários, c aos canibais, b ao barco, as constantes e à margem esquerda do rio e d à margem direita do rio. Nesse caso, (e, e, d, e, e, d, d) é uma instância da representação dada que diz: há dois missionários e dois canibais na margem esquerda do rio e um missionário, um canibal e um barco na margem direita do rio. Note-se que a posição dos elementos na 7-upla está embutido (previamente escolhida) na tradução (leitura) da representação estabelecida.
Exemplo 2: Outra forma de representação poderia ser: (m, c, b), tal que m e c são variáveis no domínio {0, 1, 2, 3} e b é variável no domínio {0, 1}. As variáveis m e c estão associadas à quantidade de missionários e canibais, respectivamente, em uma das margens. A variável b está associada à margem em que se encontra o barco (0 para margem esquerda e 1 para margem direita). Nesse caso, (2, 2, 1) é uma instância da representação dada que diz: há dois missionários e dois canibais na margem esquerda do rio e um missionário, um canibal e um barco na margem direita do rio. Novamente, como no exemplo anterior, a margem a que se refere a 3-upla está embutida (previamente escolhida) na leitura da representação fixada. Também observamos que a 3-upla exibe explicitamente os elementos em apenas uma das margens, os elementos da margem oposta são derivados do contexto fixado (no exemplo anterior, a 7-upla exibe todos os elementos envolvidos). A derivação ocorre por meio de aritmética simples (no exemplo anterior não está explícito a possibilidade de uso da operações aritméticas). Veja aqui um exemplo de resolução com essa notação.
Exemplo 3: Uma variante da representação do exemplo anterior. O uso de rótulos para os valores numéricos não necessita de uma estrutura ordenada (cada posição identifica um tipo de objeto). A seguinte lista pode ser usada para representar os estados: mM, cC, bB ~ (3-m)M, (3-c)C, (1-b)B. As variáveis m, c e b são como as do exemplo anterior, os rótulos M, C e B indicam respectivamente: missioários, canibais e barco. Os três itens à esquerda do separador "~" indicam o estado numa das margeens do rio e os três itens à direita de "~" o estado na margem oposta. A figura abaixo exibe a representação acima em forma de um grafo:
A árvore acima exibe alguns dos estados possíveis (não mostra todos os estados do espaço do problema) e os estados não permitidos.
Exemplo 4: A representação adotada no Tutorial 4 (página 145) é dada do seguinte modo: são definidas seis variáveis Me, Md, Ce, Cd, Be, Bd tais que Me, Md, Ce, Cd, estão associados à quantidade de missionários e canibais em cada uma das margens (esquerda e direita), respectivamente, e Be, Bd referem-se à posição do barco em relação à margem do rio (esquerda ou direita, respectivamente). O domínio das variáveis Me, Md, Ce, Cd é {0, 1, 2, 3} e o domínio das variáveis Be, Bd é {0, 1}. O código abaixo mostra como efetuar a representação acima no Soar:
# ------------------------------------------------------------------- (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)
As duas formas de representação dada pelas figuras abaixo são variantes dos exemplos acima
A estrutura do lado esquerdo da figura acima adota as margens dos rios como forma de rotular os estados, os sub-objetos são os elementos do problema (de fato, as quantidades referentes a cada classe de personagem): missionários, canibais e o barco (em cada uma das margens). Uma relação extra é destacada: a relação de margem oposta (serve para facilitar os matches). No Soar a estrutura teria a seguinte codificação:
# ------------------------------------------------------------------- (state <s> ^left-bank <l> ^right-bank <r>) (<l> ^missionaries 0-3 # Se o valor é x, temos 3-x na outra margem ^cannibals 0-3 # Idem. ^boat 0/1 # Se vale z, então vale 1-z na outra margem ^other-bank <l>) (<r> ^missionaries 0-3 # Cabe a observação acima. ^cannibals 0-3 # Idem ^boat 0/1 # Idem ^other-bank <r>)
Abaixo temos a codificação da estrutura do lado direito da figura acima. Note-se que esta representação não segue, digamos, a estrutura física (como a estrutura anterior) do problema.
# ------------------------------------------------------------------- (state <s> ^missionaries <m> ^cannibals <m> ^boat <b>) (<m> ^left 0-3 ^right 0-3) (<c> ^left 0-3 ^right 0-3) (<b> ^left 0/1 ^right 0/1)
Para o restante da codificação a seguir utilizamos a primeira estrutura, a que adota as margens como referência para a representação dos estados. Apresentamos a implementação como segue: criação dos estados iniciais, proposição dos operadores, aplicação dos operadores, monitoração dos operadores e estados (isso inclui uma forma de reconhecimento do estado desejado), detecção de falhas (estados não permitidos no jogo: número de canibais maior que o de missionários em uma dada margem) e controle de aplicação do último operador (para evitar re-trabalho: fazer e desfazer passos).
Regras de criação dos estados iniciais:
A situação aqui é similar ao caso do problema dos jarros, criamos uma regra que estabelece as condições iniciais na WM.
# -----------------------------------------------------------------------
sp { water-jug*propose*initialize-mac
(state <s> ^superstate nil # Estabelece a condição inicial
-^name) # Não há nada na WM.
-->
(<s> ^operator <o> + =)
(<o> ^name initialize-mac) # Ativa o estado para início da
} # simulação
# -----------------------------------------------------------------------
sp {mac*apply*initialize-mac
(state <s> ^operator.name initialize-mac)
-->
(<s> ^name mac ^left-bank <l> # Estabelece os elementos do problema
^right-bank <r>
^desired <d>)
(<r> ^missionaries 0 # A situação na margem direita
^cannibals 0
^boat 0
^other-bank <l>)
(<l> ^missionaries 3 # Situação complementar na outra margem
^cannibals 3
^boat 1
^other-bank <r>)
(<d> ^right-bank <dr>) # Relação entre as margens do rio
(<dr> ^missionaries 3
^cannibals 3
^boat 1)
}
Regras de proposição dos operadores:
Conforme descrição do problema, as operações se resumem a transportes missionários e/ou canibais de uma margem a outra do rio utilizando um barco, dado que o barco comporta no máximo dois passageiros (incluindo o condutor: missionário ou canibal). Desse modo, temos as seguintes possibilidades:
- somente um personagem (missionário ou canibal) no barco. Nesse caso, deve haver pelo menos um dos personagens na margem em que se encontra o barco.
- dois personagens do mesmo tipo (dois missionários ou dois canibais) no barco. A condição, nesse caso, é a existência de pelo menos dois personagens de um mesmo atipo na mesma margem em que está o barco.
- dois personagens de tipos distintos (um missionário e um canibal). Condição: deve haver pelo menos um personagem de cada tipo na mesma margem do barco.
# --------------------------------------------------------------------------- # Moves either a single missionary or a cannibal sp {mac*propose*operator*move-boat1 (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)} # --------------------------------------------------------------------------- # Moves two missionaries or two cannibals. sp {mac*propose*operator*move-boat2 (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) } # --------------------------------------------------------------------------- # Moves one missionary and one cannibal. 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) }
Regra de aplicação dos operadores:
A regra de aplicação dos operadores de movimentação reflete a ação de transporte: movimento do barco e seus passageiros de uma margem a outra do rio. Evidentemente, tudo segue de acordo com a representação adotada (a movimentação física do barco não ocorre, muito menos a representação dos passageiros no barco).
# ---------------------------------------------------------------------- # <type> Tipo do personagem (missionário ou canibal) que está no barco # <num> Quantidade de um dado tipo de persoangem no barco # sp {apply*move-boat (state <s> ^operator <o>) (<o> ^name move-boat ^{ << missionaries cannibals boat >> <type> } <num> # Tipo do ^bank <bank>) # personagem (<bank> ^<type> <bank-num> ^other-bank <obank>) (<obank> ^<type> <obank-num>) --> (<bank> ^<type> <bank-num> - (- <bank-num> <num>)) # Contas: <num> sai de uma (<obank> ^<type> <obank-num> - # margem <num> e chega noutra. (+ <obank-num> <num>)) }
Regras de monitoração dos operadores e estados:
As regras que fazem o monitoramento de operadores selecionados e estado (uma regra para cada margem em que o barco está). A monitoração não evita estados não permitidos (casos em que o número de missionários é menor que o de canibais em uma das margens).
# ----------------------------------------------------------------------
sp {monitor*move-boat
(state <s> ^operator <o>)
(<o> ^name move-boat
^{ << cannibals missionaries >> <type> } <number>)
-->
(write (crlf) | 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> | |)
}
Também é necessário verificar se o estado objetivo foi alcançado.
# ---------------------------------------------------------------------
# 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.
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)
}
Ou se a aplicação dos operadores conduziu a um estado não permitido.
# ----------------------------------------------------------------------
# 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.
sp {mac*evaluate*state*failure*more*cannibals
(state <s> ^desired <d>
^<< right-bank left-bank >> <bank>)
(<bank> ^missionaries { <n> > 0 } # Ocorrência de Falha.
^cannibals > <n>)
-->
(write (crlf) |Failure State.|)
(<s> ^failure <d>)
}
Regras de detecção de falhas:
As regras abaixo tratam de estados não permitidos no jogo: número de canibais maior que o de missionários em uma dada margem. Neste caso (o contexto permite), a solução é a de desfazer a última operação. Evidentemente, esse tipo de solução exige regras de controle sobre o último operador aplicado (subseção seguinte).
# ---------------------------------------------------------------------
# If failure, undo last opertor
sp {mac*select*operator*prefer*inverse*failure*types*1
(state <s> ^name mac
^operator <o> +
^failure <d>
^last-operator <lo>)
(<o> ^name move-boat
^<type> <number>
^types 1)
(<lo> ^types 1
^type <type>
^number <number>)
-->
(<s> ^operator <o> >)
}
# ----------------------------------------------------------------------
sp {mac*select*operator*prefer*inverse*failure*types*2
(state <s> ^name mac
^operator <o> +
^failure <d>
^last-operator.types 2)
(<o> ^types 2)
-->
(<s> ^operator <o> >)
}
# ---------------------------------------------------------------------
# If not failure, avoid last operator
sp {mac*select*operator*avoid*inverse*not*failure*1
(state <s> ^name mac
^operator <o> +
-^failure <d>
^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 <d>
^last-operator.types 2)
(<o> ^types 2)
-->
(<s> ^operator <o> < )
}
A figura abaixo mostra uma execução em que vemos a atuação dos operadores acima definidos.
Regras de controle de aplicação do último operador:
# ----------------------------------------------------------------------
# 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.
#
sp {mac*apply*move-boat*record*last-operator*types*1
(state <s> ^name mac
^operator <o>)
(<o> ^name move-boat
^bank <bank>
^{ << missionaries cannibals >> <type> } <n>
^types 1)
-->
(<s> ^last-operator <o1>)
(<o1> ^types 1
^bank <bank>
^type <type>
^number <n>)
}
# ----------------------------------------------------------------------
# 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-boat*record*last-operator*types*2
(state <s> ^name mac
^operator <o>)
(<o> ^name move-boat
^boat <bank>
^types 2)
-->
(<s> ^last-operator <o1>)
(<o1> ^types 2
^bank <bank>)
}
# ----------------------------------------------------------------------
sp {mac*apply*move-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> -)
}
Na seção seguinte veremos duas estratégias para aprimorar as soluções de problemas já abordados: dos missionários e canibais e dos jarros.
Planejamento e Aprendizado: Problema dos Jarros no SOAR
Nesta seção abordamos duas técnicas que podem auxiliar no design de implementações Soar: uma forma de planejamento chamada de look-ahead e um modo de aprendizado denominado chunk.
A idéia do planejamento look-ahead é avaliar o que ocorre após a conclusão do passo seguinte (ao estado atual), uma forma de perspectiva a médio prazo. No Soar, significa avaliar internamente os uso dos operadores antes de efetivamente aplicá-los às tarefas correspondentes. Todos os problemas abordados, com exceção dos referentes ao TankSoar, foram resolvidos internamente (em cenários representados internamente no "cérebro" do agente), o que permite "refazer" passos que levavam a estados não permitidos (como no caso do problema dos missionários e canibais). No entanto, os problemas referentes ao ambiente do TankSoar (problemas que envolvem interação com o ambiente) não permitem refazer ações (não é possível voltar no tempo). Por outro lado, é possível planejar uma seqüência de ações antes de executá-las: baseado nos possíveis estados gerados pelos operadores avaliados. Nesse contexto (do Soar), consideramos aprendizado a capacidade de um agente construir regras a partir de planos, isto é, o agente é capaz de resumir (chunk) o processo de deliberação de um plano para a realização de uma dada tarefa em processo direto de resolução (regra) de instâncias dessa mesma tarefa sem a necessidade de deliberar novo plano.
No Soar o planejamento é parte do conhecimento de um agente, desse modo não se trata de uma seqüência passo-a-passo de operadores a serem aplicados cegamente, mas de operadores que devem se submeter ao processo de seleção (com preferências de escolhas) usual a todos os operadores. Nas seções seguintes veremos como funcionam esses aspectos na prática.
Planejamento Look-Ahead (o caso dos jarros d'água)
No Soar, o processo de planejamento ocorre como um efeito colateral do método (de escolha padrão) aplicado para tratar situações onde ocorrem impasses (um impasse resulta da insuficiência de informação para selecionar uma ação, escolher um operador de acordo com as preferências de cada operador). São quatro tipos de impasses:
- tie: ocorre quando há uma coleção de objetos igualmente elegíveis competindo num contexto fixado. Por exemplo, no WJ onde o operador fill jug é escrito sem a preferência de indiferença (denotado pelo sinal de "=").
(o023 ^name fill-A +) (o023 ^name fill-B +)
- conflict: ocorrre quando dois ou mais objetos são os melhores entre si (sem um terceiro dominante). Por exemplo:
(o023 ^action fill-A > fill-B) (o023 ^action fill-B > fill-A)
- constraint-failure: ocorre quando um atributo recebe mais de um tipo de preferência: required e prohibit . Por exemplo:
(a023 ^action fill-A !) (a023 ^action fill-A ~)
ou
(a023 ^action fill-A !) (a023 ^action fill-B !)
- no-change: ocorre quando da passagem da fase de elaboração para o estado de quiescência (onde não há mais produções para disparo).
Para ilustrar o efeito de um impasse do tipo tie basta remover o sinal de "=" da regra abaixo (a regra é parte do programa do water jug, código [ aqui ]):
##############################################################################
# If the task is water-jug and there is a jug that is not full, then propose
# filling that jug.
##############################################################################
sp {water-jug*propose*fill
(state <s> ^name water-jug ^jug <j>)
(<j> ^empty > 0)
-->
(<s> ^operator <o> + =) # "=" preferência indiferente (escolha
(<o> ^name fill ^fill-jug <j>) # randômica)
}
A figura abaixo mostra os diferentes comportamentos dos dois programas: o quadro superior mostra os três primeiros passos do water jug (código sem modificação: aqui) e o quadro inferior os três primeiros passos do código com a modificação sugeria acima.
As duas figuras abaixo mostram maiores detalhes, a primeira detalha o quadro superior da figura acima e a segunda mostra elementos do quadro inferior da figura acima (as figuras foram maquiadas para fins didáticos):
Os pontos destacados (detalhes coloridos em vermelho e laranja) mostram os operadores criados, suas respectivas preferências e a escolha na fase de decisão. O mesmo processo ocorre na figura abaixo, porém a fase de decisão desemboca num tie impasse (o Soar gera automaticamente um novo subestado nos casos em que as preferências dos operadores são insuficientes para a escolha de um deles): note as augmentations do operador tie: ^choices multiple, ^impasse tie, and ^item (essas augmentations ocorrem em cada operador tie).
A figura abaixo mostra a dinâmica do Soar para tratar a ocorrência de um tie impasse. Suponha que para um dado estado S1, na fase de decisão temos um tie impasse em decorrência da preferência dos operadores O1 e O2. S1 é o estado top-level (denotado por superstate = nil) que ocorre durante a resolução da meta corrente a ser alcançada. Para a resolução do tie impasse entre O1 e O2 em S1 o Soar cria automaticamente um sub-goal S2 (o destaque em vermelho na figura abaixo).
Um sub-goal é definido como estado que carrega informações estruturais sobre a ocorrência do impasse. No esquema da figura acima, o sub-goal S2 pode ser definido como: (S2 ^type state ^superstate S1 ^impasse tie ^choices multiple ^attribute operator ^item O1 O2 ^quiescence t - compare com o exemplo (figura) do water-jug). Isto é, S2 é um estado, seu super-state é S1 e a ocorrência do tie impasse se deve aos múltiplos (no caso dois) operadores O1 e O2 após atingir a quiescência no ciclo de decisão para S1. A resolução (padrão) do tie impasse (como esquematizado na figura acima) tem início no estado S2 devido a existência (estamos assumindo tal existência: faz parte do selection problem space) de uma regra na LTM: "Se existe uma meta para a resolução do tie impasse no espaço de problema PS1, use o espaço de problema PS2 cujo estado inicial contém tied operators". Como mostra a figura, se houver novas ocorrências de impasses durante a resolução de S2, o Soar cria uma pilha de sub-goals que são processadas da mesma forma que o primeiro tie impasse (vide estado S3 na figura).
OBS.: Considere o esquem da figura acima. Se S2 for resolvido com sucesso pela determinação de um nova preferencia, digamos, PrefS2 que permite resolver o tie impasse entre O1 e O2 em S1, então uma nova regra é criada: IF (S1) THEN (PrefS2). Isto é um chunk e é armazenado na LTM. Se houver nova ocorrência de S1 no ciclo de decisão, o chunk pode ser usado ao invés da criação de um novo sub-goal. Desse modo, o processo de chunking é visto como uma forma de simplificar a resolução de problemas (ocorreu um aprendizado).
Esquema de resolução de um tie impasse (Selection Problem)
Para tratar as ocorrências dos tie impasse, o Soar utiliza como recurso o selection problem space. No escopo do Soar, o problema relacionado à resolução de tie impasse também é chamado de problema de seleção (selection problem). Como os elementos centrais no design do Soar são os estados e operadores (o estado é a representação atual do problema e operadores são modificadores que realizam alguma transformação no estado atual) e o processo de tomada de decisão é baseado na escolha de quais operadores podem ser aplicados a um determinado estado e qual, dentre os previamente selecionados, será o executor, logo não é de se estranhar que a resolução do tie impasse seja chamado de problema de seleção.
O Soar usa a seleção do espaço do problema para avaliar e comparar os operadores tie e com isso poder criar preferências que resolvam o tie. Para a avaliar os operadores o Soar cria múltiplas instâncias de um operador, chamado evaluate-object, cuja finalidade é avaliar a utilidade de um operador. Vamos tomar o water-jug para exemplificar como aplicar a seleção. As regras referentes ao problema de seleção estão no arquivo selection.soar. Este arquivo acompanha o pacote de instalação do Soar, vide pasta Agents/default/. Para carregar estas regras juntamente com as regras do water-jug basta adicionar os comandos abaixo (assumindo que o seu programa está num subdiretório da pasta Agents):
pushd ../default source selection.soar popd
Selection State Representation: há diferentes formas de valores (simbólicos, numéricos) que podem ser atribuídos por uma avaliação (por um operador evaluate-object). Logo, um modo de tratar (comparar) esses dados é que o objetos de avaliação tenham augmentations a serem comparados, por exemplo, uma estrutura como:
operator <o>-- serve para identificar o operador a ser avaliadosymbolic-value success/partial-success/partial-failure/failure/indifferent-- avaliação simbólica- numeric-value [number] -- avaliação numérica
- value true -- indica se o valor atribuído é simbólico ou numérico
- desired <d> -- identifica um estado desejado (se existir um) que satisfaça a avaliação
Evidentemente, é necessário criar regras para o manuseio de tais estruturas, inclusive para as devidas remoções da WM (quando necessário). Também é possível efetuar avaliações sobre estados, nesse caso eles são automaticamente removidos da WM após a reolução do tie impasse.
Selection Initial State Creation: no caso do selection problem não é necessário criar uma regra para gerar o estado inicial do problema (como no problema do water jug e no caso dos missionários e canibais), esse estado é criado automaticamente em resposta a um impasse. A regra abaixo nomeia um estado de elaboração inicial (a elemento sintático :default serve para indicar ao Soar que se trata de uma regra default: são regras como outras quaisquer (todas as regras rotuladas como default estão no selection.soar). Porém, o Soar, para fins estatísticos, faz registros separados de regras default e não-default.):
sp {default*selection*elaborate*name
:default
(state <s> ^type tie)
-->
(<s> ^name selection)
}
Selection Operator Proposal: O único operador no selection problem é o de avaliação: evaluate-operator.
# --------------------------------------------------------------------------------------
# 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.
#
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>)
}
A expressão (<s> ^evaluation <e>) refere-se a um objeto de avaliação, com o uso da "negação" ("-") é possível escrever um teste sobre a não existência de uma avaliação. A expressão (<e> ^value true) refere-se à existência de um valor atribuído à uma dada avaliação (supondo que ela ocorre em <e>). Para ligar o valor à avaliação (objeto de avaliação) existente criamos uma referência (<e> ^operator <i>). Satisfeitas as condições, o operador é selecionado e permanece nessa situação até uma avaliação apropriada (com um valor) ser criada. Note-se que apenas um único evaluate-operator será criado e aplicado para cada operador tie.
Selection Operator Application: a aplicação do operador de avaliação (evaluate-operator) consiste de duas partes. A primeira trata da criação da estrutura de dados (sem qualquer instância) referente à avaliação e da criação da estrutura da avaliação. A segunda efetua o cálculo da avaliação, que não pode ser feito diretamente via regras, é necessário sub-estados para a avaliação do problema. A codificação abaixo mostra as augmentations dos objetos que compõe uma 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>)
No caso do water jug, a augmentation que expressa o objeto desejado é: o galão de três litros com um litro d'água. E, no caso dos missionários e canibais: missionários, canibais e o barco na margem direita do rio. A descrição (augmentation) do superproblem-space é o problem-space object do super-estado. Isto é, o espaço do problema deixa de ser apenas um identificador (um name) e torna-se um objeto (o problem-space object), com isso propriedades (representação explícita das propriedades sobre o estado atual do espaço do problema) adicionais podem ser inclusas no espaço do problema.
Na segunda parte, referente ao cálculo da avaliação, o estado corrente é copiado para um sub-estado de avaliação. Note que a cópia é feita considerando-se as informações sobre os estados contidas na estrutura que engloba o espaço do problema. Aplica-se sobre o estado copiado o operador, o resultado da avaliação é adicionado a um objeto de avaliação (evaluation object) adequado (caso nenhuma avaliação seja possível, o processo de resolução do problema prossegue: podendo gerar outros tie impasses, subestados, etc.). As etapas do processo de avaliação são: 1. criar o estado inicial, 2. selecionar o operador a ser avaliado, 3. aplicar o operador selecionado e 4. avaliar o resultado.
Criando o estado inicial: o estado inicial deve ser uma cópia do estado que originou o tie impasse. Abaixo estão as descrições (augmentations) relativa a cópias:
default-state-copy
no: não efetua a cópia automática de qualquer augmentation.one-level-attributes: copia augmentations do estado e preserva o valores atribuídos
Exemplo:
(p1 ^one-level-attributes color) (s1 ^color c1) (c1 ^hue green) ->(s2 ^color c1)
- two-level-attributes: copia augmentations do estado e cria novos identificadores para os valores. Compartilha os identificadores substituídos com os novos identificadores.
Exemplo:
(p1 ^two-level-attributes color) (s1 ^color c1) (c1 ^hue green) -> (s2 ^color c5) (c5 ^hue green)
- all-attributes-at-level one: copia todos os atributos do state como one-level-attributes (exceto os que são não copiáveis e os criados pelo Soar tais como
impasse,operator,superstate)
Exemplo:
(p1 ^all-attributes-at-level one) (s1 ^color c1) (s1 ^size big) -> (s2 ^color c1) (s2 ^size big)
all-attributes-at-level two: copia todos os atributos do estado como two-level-attributes (exceto os que não são copiáveis e os criado pelo Soar comoimpasse,operator,superstate)- dont-copy: não copia um dado atributo.
Example:
(p1 ^dont-copy size)
- don’t-copy-anything: não copia nenhum atributo
Exemplo:
(p1 ^dont-copy-anything yes)
A augmentation padrão, caso nenhuma seja definida, é all-attributes-at-level one. No water jug, os estados tem uma estrutura de dois níveis: os jarros (um de três e outro de cinco) e seus conteúdos (contents, volume, e empty):
# ------------------------------------------------------------------------ (s1 ^jug j1 j2) (j1 ^volume 3 ^contents 0 ^empty 3) (j2 ^volume 5 ^contents 0 ^empty 5)
É suficiente copiar as augmentations do estado ou é necessário copiar os sub-objetos também? Antes de responder a esta pergunta, vejamos através de um exemplo como os operadores modificam o estado (na formulação do water jug os operadores modificam as augmentations contents e empty dos jarros). Considere a regra de aplicação do fill abaixo:
sp {water-jug*apply*fill
(state <s> ^operator <o> ^jug <j>)
(<o> ^name fill ^jug <j>)
(<j> ^volume <volume> ^contents 0 ^empty <volume>)
-->
(<j> ^contents <volume> 0 - ^empty 0 <volume> - ) # Remove a WME
}
Considere os seguinte WMEs: (j1 ^contents 0) e (j1 ^empty 3), a aplicação da regra ao jarro de três litros irá removê-los da WM e adicionar (j1 ^contents 3) e (j1 ^empty 0) a WM. Como conseqüência, tanto as cópias quanto os originais serão modificados. O que não é aceitável, pois isso não torna possível a aplicação de operadores aos subestados sem modificar os originais. Desse modo, há duas respostas possíveis para a pergunta. A primeira é fazer a cópia de dois níveis de atributos, do seguinte modo: adicionando as ações abaixo na regra de inicialização do water jug (de fato, a melhor opção é listar exatamente quais os atributos a serem copiados, a invés o ^all-attributes-at-level two.):
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)
}
Após a aplicação da regra, o sub-estado (digamos: s3) assume a seguinte formação:
(s3 ^jug j3 j4) (j3 ^volume 3 ^contents 0 ^empty 3) (j4 ^volume 5 ^contents 0 ^empty 5)
A segunda abordagem é modificar o operador de aplicação fill para criem novos objetos jarros, ao invés de alterar as augmentations dos jarros. Por exemplo, o código abaixo ilustra uma possível moficiação:
sp {water-jug*apply*fill
(state <s> ^operator <o> ^jug <i>)
(<o> ^name fill ^jug <i>)
(<i> ^volume <volume> ^contents 0 ^empty <volume>)
-->
(<s> ^jug <i> - ^jug <ni>)
(<ni> ^volume <volume> ^contents <volume> ^empty 0)
}
Essa última abordagem é menos natural (criar um novo jarro toda vez que seu conteúdo é modificado) e, apesar de poucos WMEs serem copiados durante a fase de criação do estado inicial, exige muito da WM. Desse modo, a primeira abordagem é a mais recomendada.
Seleção do operator a ser avaliado: uma vez criado o estado inicial do operador evaluate-operator, é necessário uma cópia do operador a ser selecionado (exceto se houver a opção: ^default-operator-copy no como augmentation sobre o problem space). Os motivos da necessidade de uma cópia do operador são: Primeiro, o operador original pode ter augmentations que se referem a objetos no estado original (não copiado). A cópia do operador deve conter os novos objetos, por exemplo, no caso do water jug, a augmentation para encher o jarro: (<o> ^name fill ^jug j1) do operador fill. Segundo, durante a aplicação do operador augmentations podem ser adicionados a ele, modificando o operador original antes de ser aplicado. Feita a cópia, regras adicionais rejeitam todos os outros operadores de propostas para que a cópia seja selecionada.
Aplicando o operador selecionado: após a seleção do operador, as regras para a aplicação irão dispará-lo e o estado copiado será modificado. Nos casos em que as ações do operador original atuam no ambiente, como no Eaters e TankSoar, é necessário escrever regras para simular os efeitos do operador selecionado. Por exemplo, no caso do Eater o efeito é o movimento do agente para uma nova posição (coordenada). A simulação é somente uma aproximação, já que o eater não tem acesso ao mapa completo do ambiente.
Avaliação do resultado: criado o novo estado, a avaliação pode ser efetuada. Uma augmentation é adicionada ao estado concomitante à aplicação do operador: ^tried-tied-operator <o>. Essa augmentation serve para garantir que a avaliação está sendo feita sobre estados que são resultados de operadores copiados. Um exemplo de avaliação é a de verificar se houve sucesso (a meta é atingida) ou falha (caso contrário). A avaliação está dividida em duas partes: o atributo é o tipo da avaliação e o valor deve identificar o estado desejado. O código abaixo ilustra uma regra para detectar sucesso:
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>)
}
Outros valores simbólicos além de sucesso e falha:
- success: estado desejado, traduzido como sendo a melhor preferência.
- partial-success: estado que indica estar no caminho para alcançar a meta, também traduzido como sendo a melhor preferência. Numa escolha de preferências entre success e partial-success a primeira será selecionada.
- indifferent: este estado indica nem sucesso nem falha, traduzido como preferência indiferente.
- failure: estado que indica que o estado de sucesso não pode ser alcançado a partir deste estado, traduzido como preferência de rejeição.
partial-failure: todo os caminhos gerados a partir deste estado levam a estados falhos, traduzido como preferência ruim (worst preference).
Avaliações também podem ser baseadas em valores numéricos, nesse caso é necessário criar a augmentadion ^numeric-value (esse tipo de avaliação é discutido mais adiante).
A inclusão das regras water-jug*evaluate*state*success e waterjug*elaborate*problem-space ao conjunto de regras do water jug é suficiente para o Soar executar a busca look-ahead (note-se que para cada operador seleção há um tie e uma pilha de recursão dos sub-estados). É possível que o sistema revisite o mesmo estado e gere um tie impasse idêntico aumentando a pilha de estados. Por outro lado, o uso da pilha permite avaliar um estado como falhos se esse já está na pilha. Também permite descartar regras lembrando do último operador.
As regras abaixo fazem com que o problem solving seja mais direto, apesar do excessivo número de decisões para resolver o problema.
# ---------------------------------------------------------------------------------
# It needs to test the following: that there is a duplicate of that state that is
# earlier in the state stack.
# There is nothing inherent in Soar that keeps track of all earlier states – only
# the superstate is readily available. We need to add rules that elaborate each
# state with all of its superstates (and their superstates). We will call this the
# superstate-set. Computing this requires only two rules – one that adds its
# superstate to the superstate-set and one that adds all of the superstate-set of
# the superstate to its superstate-set.
#
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>)
}
Abaixo a regra para detectar falhas:
# ---------------------------------------------------------------------------------
sp {water-jug*evaluate*state*failure*duplicate
(state <s2> ^name water-jug
^superstate-set <s1>
^jug <i1>
^jug <i2>
^tried-tied-operator) # That state exists after the operator has
(<i1> ^volume 5 ^contents <c1>) # been applied in an evaluation.
(<i2> ^volume 3 ^contents <c2>)
(<s1> ^name water-jug
^desired <d> # The desired state, which is used in the action
^jug <j1>
^jug <j2>)
(<j1> ^volume 5 ^contents <c1>)
(<j2> ^volume 3 ^contents <c2>)
-->
(<s2> ^failure <d>)
}
De fato, o problema do número excessivo de decisões está na "ausência de uma memória" que relacione o estado, o operador aplicado e o resultado obtido. No water jug com as regras acima, assim que um estado é produzido (p.ex., um estado que sob um certo operador leva à falha) ele é esquecido; se o estado ocorrer novamente a avaliação se repete. Para tratar esse tipo de problema o Soar conta com um mecanismo chamado chunking (assunto da próxima seção).
Chunking como forma de aprendizado (o caso dos missionários e canibais)
No Soar, o chunking é mecanismo associado ao processo de aprendizado, uma forma de explanation based learning. O chunking é uma forma de criar um novo conhecimento procedural: uma produção que sumariza o conhecimento aprendido na ocorrência de um impasse. No Soar, a ocorrência de um impasse se concretiza num sub-estado (que contém o tipo do impasse, quais e quantos são os operadores envolvidos no impasse, etc) cujo e objetivo, naquele momento, passa a ser a resolução do impasse. O processo de resolução gera um chunk (uma regra): se a resposta do ciclo de decisão for um supergoal, é criada uma nova produção tal que as condições são os elementos testados antes do impasse e as ações têm as preferências obtidas. Nessas condições, a regra gerada pelo chunking herda as mesmas características das regras que participaram de sua construção, por exemplo, se as regras envolvidas no impasse têm em seu bloco de condições testes desnecessários, então a regra gerada pelo chunking também terá em seu bloco de condições os mesmos testes desnecessários.
A ativação do chunking, no SJD, pode ser feita na linha de comando: escreva: learn –-on ou colocar esse mesmo comando no arquivo que contém as regras. Para ativar o trace sobre os chunks basta digitar na linha de comando: watch -–chunks (e/ou print -–chunks) e, na ocorrência de um chunk (com o da figura abaixo: chunk-1*d5*tie*1), se desejar visualizá-lo digite: print chunk-1*d5*tie*1. A figura abaixo mostra a ocorrência de chunks no problema do water jug ( código: aqui ):
A seguir exploramos o uso de avaliações baseadas em valores numéricos tomando como exemplo o problema dos missionários e canibais. O roteiro é o mesmo do water jug, desse modo a apresentação será mais curta. Novamente, adicionar os comandos abaixo (assumindo que o programa dos missionários e canibais está num subdiretório da pasta Agents):
pushd ../default source selection.soar popd
Em seguida, adicionamos a regra que define o problem space e declaramos a especificação para a cópia de estados referente a avaliação (neste caso, ^default-state-copy yes). Abaixo temos a regra que efetua as alterações necessárias (note que a regra modifica as augmentations de left-bank e right-bank, desse modo as cópias são di tipo two-level-attributes):
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)
}
Assim como no water jug, devemos modificar a regra de detecção do estado meta. Ao invés de efetuar a parada do programa a regra cria 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>)
}
Analogamente, mutatis mutandis, apesar de codificamos a regra de deteção de falhas. A regra cria uma avaliação simbólica de falha. Lembrando que no water jug não existe a ocorrência desse tipo de estado.
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>)
}
Adicionamos a regra de detecção de estados duplicados na pila de estados. A regra avalia o estado duplicado 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>)
}
Por conta do planejamento (look-ahead) a regra referente a remoção do último operador é desnecessária. Com essas alterações temos uma implementação que permite o uso de planning para a resolução do problema dos missionários e canibais. Porém, analogamente ao water jug, o número de decisões pode sere excessivamente grande. A seguir apresentamos duas soluções: uma que explora os recursos naturais da arquitetura Soar: o mecanismo de aprendizado via chunking e outra usando avaliações numéricas.
Chunking
Como já mencionamos anteriormente, o chunking é chamado na ocorrência de um impasse (como vimos são quatro os tipos de impasse). No caso do problema dos missionários e canibais toda solução que termina numa falha leva a um impasse o tipo no-change. Um aprendizado que decorre desse tipo de impasse é o de rejeitar o operador que não leva a estados pertencentes à solução (fora do caminho do estado meta). Por exemplo, o mecanismo de chunking pode gerar regras como:
# ---------------------------------------------------------------------------------------
If the current state has the boat on the right bank and two missionaries and two cannibals,
reject an operator that moves only one missionary and the boat to the left.
Para isso, incluímos a regra abaixo:
# ---------------------------------------------------------------------------------------
sp {mac*apply*move-mac-boat
(state <s> ^operator <o>)
(<o> ^name move-mac-boat
^{ << missionaries cannibals boat >> <type> } <num>
^bank <bank>
^types <types>) # Fixa os diferentes tipo de passageiro no bote
(<bank> ^<type> <bank-num> ^other-bank <obank>)
(<obank> ^<type> <obank-num>)
-->
(<bank> ^<type> <bank-num> - (- <bank-num> <num>))
(<obank> ^<type> <obank-num> - (+ <obank-num> <num>))
}
Com a inclusão da regra acima temos uma implementação (obtenha o código aqui) que resolve o problema dos missionários e canibais usando planejamento (look-ahead) e que retorna soluções com menor número de passos (menos tomadas de decisões). A figura abaixo mostra a ocorrência do chunk após a falha (provocando um impasse do tipo no-change) ocasionada pela movimentação de um único missionário.
Avaliações numéricas
Outra solução para diminuir o número de tomadas de decisões para a resolução do problema dos missionários e canibais é adotar a estratégia de avaliar estados que não são necessários para atingir a meta. Para isso é preciso implementar uma função de avaliação. Por exemplo, uma função de avaliação é a de dar preferência a estados que tenham mais missionarios e canibais na margem desejada. Isto é, quanto maior a soma dos missionários e canibais na margem desejada maior é a preferência dada ao estado.
O Soar fornece recursos via regras de seleção (independente do domínio) que comparam avaliações e criam preferências apropriadas, nessas condições basta adicionar uma regra que calcula a avaliação conforme descrito e estabelecer que quanto maior o valor numérico melhor é a avaliação (por exemplo):
# --------------------------------------------------------------------------------------
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) # New augmentation
(<dl> ^missionaries 3 ^cannibals 3 ^boat 1)
}
A regra abaixo avalia o estado desejado (^desired) e o operador aplicado (^tried-tied-operator). Ao final, cria uma augmentation sobre o estado atribuindo um valor numérico (a soma da quantidade de missionário e canibais).
# -------------------------------------------------------------------------------------
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>))
}
A inclusão dessas regras na implementação reduz drasticamente a quantidade de passos para encontrar uma solução. A execução deve ser feita sem a ativação do mecanismo de chunking.
Comentário: A ativação do mecanismo de chunking na implementação que contém as regras de avaliação numérica compromete o desempenho do programa. De fato, a avaliação numérica (como feita acima) é uma heurística que, em algumas situações, pode levar a caminhos errados. Como as regras geradas pelo mecanismo chunking herdam as características dos operadores originais (coisas boas e ruins), se houver regras "ruins" os chunks (o aprendizado) também serão "ruins".
Considerações sobre o chunking
A idéia do aprendizado via chunking é o de agilizar as tomada de decisão criando regras para os sub-objetivos, no entanto esse mecanismo pode criar um elevado número de produções compromentendo o desempenho do Soar no ciclo de decisão (pela elevada quantidade de condições a avaliar). De fato, a resolução de um sub-objetivo via chunking cria no Soar uma regra referente à ocorrência de um impasse ocorrido num dado estado da WM (o "estado corrente" da ocorrência do impasse), isto é, o chunking cria uma WME com um determinado valor. Se o valor associado à essa WME for alterado, então a regra deixa de ser aplicável. Logo, se o domínio de valores das WMEs criadas for "grande" (em termos computacionais) o mecanismo de chunking pode deixar de ser um processo de agilização para ser um fator complicador.
Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer