Atividade 1

Problemas de IA Clássica: Missionários e Canibais

    Problemas de IA Clássica envolvem buscas através dos espaços dos problemas a fim de encontrar uma solução. Resolver este tipo de problema requer selecionar um operador adequado, dentre vários operadores propostos, em cada etapa da solução do problema. Selecionar um operador adequado não é uma tarefa fácil, visto que apenas o conhecimento sobre a descrição do problema não é suficiente para direcionar os passos até sua solução. Esse tipo de problema será resolvido por meio de "tentativa e erro", envolvendo a busca através do espaço de estados do problema.

Definição do Problema:

    Três missionários e três canibais querem atravessar um rio. Há um bote na margem do rio que pode ser usado para transpô-lo. O bote comporta no máximo duas pessoas por travesia. Os missionários e os canibais devem ser levados até a outra margem evitando-se deixar mais canibais do que missionários numa mesma margem do rio a cada travesia.

    Para solucionar este problema, usando o SOAR, primeiro será necessário decompor o problema num espaço de estados e possíveis operadores aplicáveis a cada estado. Também define-se um estado inicial do problema e o estado final desejado. Este problema também incluirá estados falhos, ou seja, estados alcançados durante a solução do problema onde há mais canibais do que missionários numa mesma margem. A figura, abaixo, exibe um grafo parcial do espaço de estados do problema levando até uma solução (não são exibidos os quatro últimos passos da solução). É possível notar os espaços que devem ser evitados (em vermelho) para se chegar à solução do problema.

    Há alguns aspectos sobre este tipo de problema que devem ser considerados para se chegar a uma solução. Representação do estado, devem ser representadas as posições dos missionários, canibais e do bote em relação às duas margens do rio. Estado inicial, deve ser escrita uma regra para gerar este estado, no qual todos os missionários e os canibais, inclusive o bote, estão numa mesma margem. Regras de proposição de operadores, os operadores movem um ou dois missionários e/ou canibais, no máximo duas pessoas por vez, para a outra margem do rio (junto com o bote). Regras de aplicação dos operadores. Regras de monitoração de estados e operadores. Regra de reconhecimento da meta, verifica se o estado final desejado foi alcançado, ou seja, todos os missionários e canibais na outra margem do rio. Regra de reconhecimento de falhas, detecta quando um estado (falho) é criado, impedindo de se alcançar a solução do problema; neste caso, quando houver mais canibais do que missionários numa mesma margem do rio. Regras de controle de busca.

Representação dos Estados

    Os objetos manipulados neste problema (Missionários e Canibais) são os três missionários, os três canibais, o bote e o rio. Em todos os estados do problema devem ser representados o número de missionários e de canibais em cada margem do rio, além de, em qual margem se encontra o bote. Uma representação adequada para os estados do problema é a seguinte:

    O estado representa dois objetos, ^left-bank <l> e ^right-bank <r>, que são as duas margens do rio. Cada margem contém objetos do tipo missionários (^missionaries), canibais (^cannibals), bote (^boat) e uma referência à outra margem do rio (^other-bank). A figura acima representa o estado inicial do problema. São representados o número de missionários e de canibais em cada margem do rio, além de em qual margem se encontra o bote (<l> ^boat 1).

Criação do Estado Inicial

    A regra mac*propose*initialize (figura abaixo) nomeia o estado e propõe a aplicação do operador que cria o estado inicial (<o> ^name initialize-mac). A regra mac*apply*initialize é responsável pela aplicação desse operador. Essa regra cria as duas margens, no estado, e inicializa o estado com o barco e todos os missionários e canibais numa mesma margem do rio, neste caso, a margem esquerda (^left-bank <l>). Também é criado um atributo para armazenar o estado desejado (^desired <d>). Ou seja, o bote deve alcançar a margem direita (<d> ^right-bank <dl>) levando todos os missionários e canibais para lá (<dl> ^missionaries 3 ^cannibals 3 ^boat 1).

Proposição de Operadores

    Os operadores deste problema devem mover 1 ou 2 indivíduos, missionários e/ou canibais, para a outra margem do rio. São possíveis três situações distintas: mover apenas 1 indivíduo (missionário ou canibal) para a outra margem; mover 2 indivíduos (missionários ou canibais) para a outra margem do rio; ou, mover 1 missíonário e 1 canibal até a outra margem. A figura abaixo exibe as regras de proposição dos operadores:

    Todas as três regras podem ser aplicadas a qualquer uma das duas margens do rio (^ << right-bank left-bank >> <bank>). As regras testam o número de missionários e/ou canibais na margem em que será proposto o operador, além de testar se existe um bote (<bank> ^boat 1) nessa margem. As regras mac*propose*operator*move-boat1 e mac*propose*operator*move-boat2 testam se há pelo menos um (<bank> ^{ << cannibals missionaries >> <type> } > 0) ou dois (<bank> ^{ << cannibals missionaries >> <type> } > 1) missionários ou canibais, numa margem, respectivamente, movendo um ou dois indivíduos para a outra margem. A regra mac*propose*operator*move-boat11 move um missionário e um canibal até a margem oposta do rio. Essa regra testa se há pelo menos um indivíduo de cada categoria (<bank> ^missionaries > 0 ^cannibals > 0). As três regras também configuram o atributo ^types definindo se o operador transporta indivíduos da mesma categoria (<o> ^types 1) ou de categorias distintas (<o> ^types 2).

Aplicação de Operadores

    Ao ser aplicado um operador, o estado do problema deve ser alterado para refletir o movimento do bote e dos missionários e/ou canibais através do rio. Ou seja, o número de missionários e/ou canibais deve ser decrementado na margem onde o bote está, e o seu número deve ser incrementado na margem oposta. O bote também deve ser atribuído a outra margem do rio. A figura, a seguir, exibe a regra responsável pela aplicação dos operadores deste problema.

    Essa regra dispara várias vezes até mover o bote e os missionários e/ou canibais. A regra testa o tipo de objeto e seu número (^{ << missionaries cannibals boat >> <type> } <num>) numa mesma margem do rio (^bank <bank>). Isso garante que esta regra dispara somente na margem do rio que possui o bote. Então, são testados o número de objetos de cada um desses tipos (<bank> ^<type> <bank-num>) numa mesma margem. Também deve ser verificado o número de objetos desse tipo (<obank> ^<type> <obank-num>) na outra margem (<bank> ^other-bank <obank>). Tendo sido satisfeitas todas as condições, o transporte dos indivíduos e do bote será efetuado. Ou seja, o número de objetos numa margem será decrementado (<bank> ^<type> <bank-num> - (- <bank-num> <num>)) e, na margem oposta, será incrementado (<obank> ^<type> <obank-num> - (+ <obank-num> <num>)).

Monitorando Estados e Operadores

    As regras seguintes, na figura abaixo, monitoram o operador selecionado e o estado. A regra monitor*move-boat imprime as informações sobre o número de missionários e/ou canibais transportados pela aplicação do operador (state <s> ^operator <o>). As outras duas regras imprimem o número de missionários e canibais na margem onde o bote está (^boat 1).

Reconhecimento do Estado Desejado

    A regra mac*detect*state*success detecta se o estado final desejado foi alcançado, e suspende o agente (halt) após imprimir a mensagem "The problem has been solved". Essa regra verifica o número de missionários e canibais (<ls> ^missionaries <m> ^cannibals <c>) numa margem (<s> ^<side> <ls>) e compara-o com o seu número (<dls> ^missionaries <m> ^cannibals <c>) na margem desejada (state <s> ^desired <d>, <d> ^{ << right-bank left-bank >> <side> } <dls>).

Detecção do Estado Falho

    A figura anterior exibe a regra responsável pela detecção de um estado falho, durante a solução do problema. De acordo com o problema (Missionários e Canibais), um estado falho ocorre quando um das margens do rio tem mais canibais do que missionários. A regra testa essa condição (<bank> ^missionaries { <n> > 0 } ^cannibals > <n>), testando também se o número de missionários, naquela margem (^<< right-bank left-bank >> <bank>), é maior do que zero. Caso dispare, essa regra imprime a mensagem "Failure State.", indicando que a solução do problema alcançou um estado falho. A regra também criará um atributo (<s> ^failure <d>) gravando a ocorrência de um estado falho.

Controle de Busca: Desfazendo o Último Operador

    Normalmente, quando a solução de um problema alcança um estado falho, o programa trava, ficando suspenso (halt). Neste caso, seria preciso reiniciar a solução a partir do estado inicial. Para se evitar isso, pode-se gravar o último operador selecionado (que levou ao estado falho), e desfazer as alterações causadas pela aplicação deste operador. Gravando qual foi o operador selecionado, na última etapa da solução do problema, pode-se alterar a sua preferência, impedindo que este seja selecionado novamente. A preferência será pela seleção de outros operadores. A figura abaixo exibe as regras responsáveis pela gravação e pela remoção do último operador aplicado:

    A regra mac*apply*move-boat*record*last-operator*types*1 grava o número e o tipo (^{ << missionaries cannibals >> <type> } <n>) dos indivíduos que foram movidos para a outra margem. Ou seja, se os indivíduos são missionários ou canibais, e quantos foram (1 ou 2 indivíduos). Essa regra também grava (<s> ^last-operator <o1>) o tipo de operador aplicado (<o1> ^types 1) e a margem onde o operador foi aplicado (<o1> ^bank <bank>). A outra regra apenas armazena o tipo de operador aplicado (<o1> ^types 2), além de em qual margem (<o1> ^bank <bank>). Ou seja, essa regra indica que o último operador aplicado moveu um missionário e um canibal, além do bote, para a outra margem. A regra mac*apply*move-boat*remove*old*last-operator remove o último operador aplicado que foi gravado. Essa regra testa se a margem na qual o bote se encontra é a mesma margem que está gravada no último operador que foi aplicado. Caso as margens não sejam as mesmas (<lo> ^bank <obank>), a regra remove o último operador gravado (<s> ^last-operator <lo> -).

    As regras da figura abaixo desfazem as alterações provocadas pelo último operador aplicado, quando este leva a um estado falho.

    As duas primeiras regras exibidas na figura acima (mac*select*operator*prefer*inverse*failure*types*1 e mac*select*operator*prefer*inverse*failure*types*2) disparam quando um estado falho for detectado (^failure <d>). Essas regras aumentam a preferência dos operadores (<s> ^operator <o> >) que desfazem as alterações causadas pelo último operador aplicado (^last-operator). A primeira regra verifica o tipo e o número de indivíduos (<lo> ^types 1 ^type <type> ^number <number>) que foram movidos para a outra margem, e aumenta a preferência dos operadores que executam essa mesma operação (<o> ^name move-boat ^<type> <number> ^types 1), só que agora na margem oposta, desfazendo o último operador aplicado. A outra regra executa a mesma operação para o operador (<o> ^types 2) que move um canibal e um missionário para a margem oposta.

    As demais regras exibidas na figura anterior (mac*select*operator*avoid*inverse*not*failure*1 e mac*select*operator*avoid*inverse*not*failure*2) verificam se não ocorreu um estado falho (-^failure <d>) e diminuem a preferência (<s> ^operator <o> <) pela seleção do último operador aplicado (^last-operator). Assim, o disparo dessas regras evita que operadores aplicados sejam desfeitos desnecessáriamente. Dessa forma, essas regras ajudam na tomada de decisões inteligentes durante a solução do problema.

    Mesmo com o uso de todas essas regras, o programa ainda demonstrará alguma ineficiência. Por exemplo, no estado inicial, ainda é possível que um operador que causou um estado falho seja aplicado novamente. Isso pode ocorrer porque apenas o último operador aplicado é gravado. Caso haja dois operadores, no estado inicial (por exemplo), que levam a um estado falho, apenas um será evitado por vez. Ou seja, poderão ser tomadas algumas decisões ineficientes até que seja tomada, de fato, uma boa decisão. Posteriormente, será proposta uma solução para este inconveniente. Será abordado o uso de impasses e sub-estados para auxiliar na solução dos problemas, implementando o planejamento da solução do problema.

Solucionando o Problema

    A figura abaixo exibe a tela do SOAR Debugger rodando a produção mac.soar. O estado inicial do problema começa com três missionários e três canibais, além do bote, na margem esquerda do rio ( M: 3, C: 3 B ~~~). A solução do problema foi alcançada, isto é, todos os missionários e os canibais, mais o bote, foram movidos para a margem direita do rio (~~~ B  M: 3, C: 3).

    Pode-se ver também, na figura acima, a ocorrência de um estado falho ("Failure State."). A próxima figura exibe alguns estados falhos alcançados durante a solução do problema. No início da figura, pode-se observar que foram movidos 1 missionário e 1 canibal para a margem direita do rio; porém, o número de canibais, nessa margem, tornou-se superior ao número de missionários (~~~ B  M: 1, C: 2), acarretando um estado falho. Na sequência, o mesmo operador (Move 1 cannibals Move 1 missionaries) foi aplicado, novamente, na margem oposta, desfazendo o operador aplicado anteriormente (M: 3, C: 2 B ~~~). Dessa vez, aplicou-se um operador que move apenas um canibal (Move 1 cannibals) para a outra margem do rio; agora, o resultado alcançado foi satisfatório (~~~ B  M: 0, C: 2).