|
Para compararmos o desempenho de diferentes
soluções de agentes para o Mundo do Wumpus, implementamos
um algoritmo que fornece a pontuação do melhor caminho, considerando
uma variação do problema proposto: o agente possui percepção
global do mundo (o ambiente é totalmente conhecido).
O melhor caminho é aquele que faz com que o agente atinja pontuação
máxima, dada às regras de pontuação definida
pelo problema, a saber:
-
Perde 1 ponto para cada ação executada;
-
Ganha 1.000 pontos para cada moeda de ouro conquistada;
-
Ganha 10.000 pontos por matar o Wumpus;
-
Perde 10.000 pontos se cair no abismo ou for pego pelo Wumpus;
-
Ganha 1.000 pontos se sair da caverna.
Para calcular o limite superior da pontuação do agente em
cada Mundo do Wumpus gerado, consideramos um agente com percepção
global do ambiente, ou seja, ele o agente sabe exatamente onde está
localizado cada perigo dentro do ambiente, cada parede e as posições
de ouro. A seguir, fazemos uma descrição do algoritmo de
busca em largura exaustiva implementado.
-
Os nós representam o estado do agente, ou seja, a posição
do agente no mundo do wumpus (Agente-em(pos(i,j)));
-
As arestas representam os movimentos possíves (move(pos(i,j),
pos(k,l)), com i-1 £ k £
i+1 e j-1 £ l £
j+1 ). Movimentos possíveis são aqueles que evitam as
posições de perigo e desviam das paredes;
-
Uma vez que o custo de movimentação é constante (-1),
em uma mesma profundidade da árvore, todos os estados possuem a
mesma pontuação;
-
Estados objetivos são aqueles que aumentam a pontuação
do agente;
-
Uma vez que a solução do problema requer que o agente alcance
vários objetivos (pegar o ouro em várias posições,
matar o wumpus e sair da caverna), a busca é dividida em etapas.
Assim, uma nova busca em largura é realizada a partir de cada objetivo
atingido, considerando está posição como a raiz da
nova árvore de busca. A busca por objetivos continua até
que todos os objetivos sejam alcançados ou se o agente, em sua última
busca não encontrou mais objetivos acessíveis (uma posição
contendo ouro pode estar cercada por 4 paredes);
-
O algoritmo termina com uma busca pela posição se saída
da caverna, determinando o caminho mais curto de saida.
Como o agente não sabe a quantidade de ouro que está disponível,
ou seja, se existe ouro totalmente isolado por paredes ou abismos, temos
que estabelecer um critério para que a busca não entre em
loop
infinito, então consideramos uma movimentação
válida na busca, somente para campos onde o agente ainda não
visitou, assim para a execução de cada nova etapa precisamos
reiniciar o ambiente considerando ele totalmente inexplorado. Quando percebemos
que todos os objetos de pontuação acessíveis já
foram recolhidos partimos para a busca do melhor caminho para sair da caverna.
|
