Inteligencia Artificial

Algoritmo de busca on-line

O problema de busca pode ser resolvido por um ou mais agentes.

Um agente é uma entidade com certo grau de autonomia que recebe informações do ambiente através de sensores e produz ações que afetam esse ambiente.

“Um agente é um sistema computadorizado autônomo que esta situado em algum ambiente e é capaz de executar ações para atingir seus objetivos”

Quando temos mais de um agente no ambiente e os mesmos se comunicam e dividem objetivos em comum, podemos dizer que temos um sistema multiagente.

Os sistemas multiagentes podem ter a decisão centralizada ou deliberativa.

Centralizada: A decisão do conjunto é realizada por um único agente.

Deliberativo: A decisão é realizada por todos os agentes.

Em alguns casos a decisão é hidrida-> centralizada e deliberada

A complexidade dos algoritmos de busca esta relacionada ao tamanho do espaço de busca.

Nos algoritmos off-line, a fase de planejamento antecede a fase de execução, o que pode gerar um tempo de resposta não aplicável em jogos ou aplicativos de tempo real.

Os algoritmos on-line a fase de planejamento é intercalada com a execução e a memoria do agente é local.

LRTA*

Learning Real Time A* (KORF, 90)

 Qualquer caminho

 Informado

 1 Agente

 On-line

No LRTA* o agente inicia no vértice inicial e através da função de custo o agente escolhe o vizinho mais promissor.

O algoritmo termina quando o agente encontra o vértice objetivo.

Função de custo:

F(J,K) = H(*) + C(J,K) onde J é o vértice corrente e K são os vizinhos de J.

Sendo assim temos que H(K) é a heurística do vizinho e que C(J,K) o custo da aresta de J para K.

Considere MinF(J) o menor valor entre as funções de custo de cada vizinho de J.

Sucessor (J) representa o vizinho de menor valor de função de custo.

Exemplo:

Iteração 1

F(A,B) = H(B) + C(A,B)

F(A,B) = 15 + 10

F(A,B) = 25

MinF(A) = 25

Sucessor (A) = B

H(A) = 25

O agente esta em A e se desloca para B

Iteração 2

O agente está em B

F(B,A) = 35

F(B,D) = 28

F(B,C) = 15

MinF(B) = 15

Sucessor(B) = C

B->C

H(B) = 15

Iteração 3

O agente está em C

F (C,B) = 25

F (C,D) = 10

MinF(C) = 10

Sucessor (C) = D

C->D

H(C) = 10

Iteração 4

O agente encontrou o objetivo

------------------------------------------------------------------------------------------------------------------------------

Iteração 1

O Agente esta em A

F(A,B) = 45

F(A,D) = 50

F(A,E) = 35

MinF(A) = 35

Sucessor (A) = E

A->E

H(A) = 35

Iteração 2

O Agente esta em E

F(E,A) = 45

F(E,F) = 25

MinF(E) = 35

Sucessor (E) = F

E->F

H(E) = 25

Iteração 3

O Agente esta em F

F(F,E) = 30

F(F,D) = 20

F(F,C) = 50

MinF(F) = 20

Sucessor (F) = D

F->D

H(F) = 20

Iteração 4

O agente encontrou o objetivo

------------------------------------------------------------------------------------------------------------------------------

RTA*

Real Time A* (KORF - 90)

Idêntico ao LRTA*, sendo a única diferença que a heurística do vértice corrente é atualizada com o segundo menor valor da função de custo entre os vizinhos.

Iteração 1

O agente esta em A

F(A,B) = 25

Segundo MinF(A) = 25

MinF(A) = 25

Sucessor (A) = B

H(A) = 25

A->B