Solução de um problema de busca.

Agentes de busca usam representação atômica. Sem estrutura interna visível.

→ Em um ambiente determinístico, totalmente observável e conhecido, a solução para qualquer problema é uma sequência de ações.

Descrição do ambiente do problema da cidade Romania.

• Totalmente observável
• Discreto (número finito de ações que podem ser tomadas)
• Conhecido (sabe-se o resultado de cada ação)
• Determinístico (apenas um resultado é possível para cada ação executada).

Dado que temos um problema, queremos encontrar uma solução para ele.

Queremos chegar em Bucharest! E estamos saindo de Arad. Com estas informações, podemos começar a formular.

A formulação do objetivo: é que queremos chegar a Bucareste!

A formulação do problema: É criada uma abstração de um modelo, com as partes relevantes do mundo.

Busca: O agente irá simular as sequências de ações neste modelo. Irá buscar até que encontre uma sequência de ações que alcance o objetivo. Essa sequência é chamada de solução. Pode ocorrer de não encontrar nenhuma solução pra dado problema.

Execução: O agente irá executar as ações na solução (sequência de ações).

A formulação do problema de busca requer abstração.

[File: ba4bf281-1d00-46da-9b92-9ca6d18bc717]

[File: 979fd1db-62c7-46db-83ba-deb55a05b9f2]

Formulação de um problema de busca

[File: cd7bdab2-e16d-46c1-b70e-1bebc08266ac]

• Estados: cidades;
• Estado inicial: Arad;
• Teste objetivo (define os estados meta): {Bucharest}
• Ações (ações disponíveis):
  • ações(Arad) = {Arad→Zerind, Arad→Sibiu,Arad→Timisoara}
• Modelo de transição (descreve o que cada ação faz):
  • resultado(Arad, Arad→Zerind) = Zerind
• Função de custo (custo de cada ação):
  • c(estadoX, ação, estadoY)

Solução é a sequência de ações que leva do estado inicial ao objetivo.

Estratégias de busca

Busca genérica (busca em árvore):

• inicializa fronteira com o estado inicial (raiz da árvore)
• Loop:
  • Se a fronteira é vazia, retorne falha;
  • Escolha nó folha e remova da fronteira;
  • Verifica se o nó escolhido representa um estado meta;
    • Se sim, retorna sucesso e a solução;
  • Expande o nó selecionado e adiciona os novos nós à fronteira.

Buscas em árvore pode ocorrer ciclos! Para evitar este tipo de problema utilizamos a busca em GRAFO.

• inicializa fronteira com o estado inicial;
• Loop:
  • Se a fronteira é vazia, retorne falha;
  • Escolha nó folha e remova da fronteira;
  • Verifica se o nó escolhido representa um estado meta;
    • Se sim, retorna sucesso e a solução;
  • Expande o nó selecionado e adiciona os novos nós à fronteira (somente adicione nós que não estão na fronteira ou não foram expandidos)

Com este novo passo ao expandir os nós seguintes, evitamos o problema de ocorrência de ciclos.

O que é estratégia de busca?

→ Define a ordem em que os nós/estados são expandidos na fronteira;

→ Dois tipos principais de estratégia de busca:

• Busca não informada: utilizam apenas as informações da formulação do problema;
• Busca informada (heurística): utilizam também uma função heurística, que estima o custo mínimo de um dado estado até um estado meta.

Busca não informada (cega)

• Estratégias de busca não-informada:
  • Busca em largura;
  • Busca em profundidade:
    • Limitada;
    • Iterativa.
  • Busca de custo uniforme.

Busca em largura

→ Expande os nós mais rasos (de menor nível) primeiro.
→ A fronteira da busca em largura é uma fila (FIFO)

→ Os requisitos de memória são um grande problema para a busca em largura. Consome muito recurso de memória.

→ Mesmo que tenha uma memória infinita, se a árvore for muito profunda, o tempo também será um gargalo.

[File: 56e1b88f-4e22-4494-afa4-959ff349b7eb]

Busca em profundidade

→ Expande o nó mais profundo (de maior nível) primeiro

→ A fronteira da busca em profundidade é uma pilha (LIFO).

→ Consome menos memória.

[File: 70b0bd9e-24f4-40a1-a57a-3746ccde2c85]

Variações da busca em profundidade

• Profundidade limitada;
• Profundidade iterativa.

A profundidade limitada tu define um limite até aonde vai descer na busca.

Já a iterativa, vai fazer um loop, no caso abaixo foi de 0 a 3.

[File: b4322a87-3f34-474a-a373-c07b52faaab4]

Busca de custo uniforme

→ Expande o nó com menor custo de caminho até o momento.

→ A fronteira da busca de custo uniforme é uma fila ordenada pelo custo.

→ Busca de custo uniforme se comporta como busca em largura quando os custos de todas as ações são iguais.

Avaliação de estratégias de busca

• Completo?: sempre encontra uma solução?
• Solução ótima?: a solução encontrada é ótima?
• Complexidade de tempo: número de nós avaliados;
• Complexidade de espaço: número de nós armazenados.

[File: c24b4328-7b87-4b8c-b9b8-7bdc3163b306]

• **Profundidade:* pode ser completo com remoção de ciclos em espaço finito (fazer em grafos?)
• ***Profundidade limitada:* somente é completo se a profundidade escolhida for >= a profundidade de um estado meta;
• ****Custo uniforme:* requer que os custos sejam todos positivos para ser completo.

[File: 28b11290-c6a2-4d92-b3b6-fcba3b4958b5]

• **Largura/Profundidade iterativa:* apenas quando os custos são todos iguais;

[File: 8512100d-3134-4c8a-b882-5be00178f280]

Busca informada Heurística

• Tipos de busca informada:
  • Busca gulosa
  • A*

Buscas heurísticas usa dicas específicas do domínio sobre a localização dos objetivos. Pode ser mais eficiente do que a busca não informada (cega).

Existe a função heurística, ela que dá essas informações;

h(x) = custo mínimo estimado de um nó até a solução.

• É uma forma comum de incorporar conhecimento do problema no algoritmo de busca.

No problema da Romenia foram definidos valores de distância de um ponto a outro, utilizando uma linha reta.

Esses valores abaixo, é o valor da heurística.

[File: e9a1814a-d165-4b84-85d5-c98b170a65f5]

→ Distância de Manhattan

h(x) = 0 em um nó que seja solução.
h(x) é sempre <= custo real; não superestima o valor.
f(x) não diminuem em qualquer caminho;
- f(x) = g(x) + h(x)
- g(x): soma do custo real até chegar ao nó
- h(x): soma do custo estimado do menor caminho do nó até o estado meta.

Portanto:
- h(A) <= g(C) + h(C)

Busca gulosa

→ Expande o nó com menor valor de h(x);

→ A fronteira da busca gulosa é uma fila ordenada por h(x).

[File: 6b4a1870-862a-4140-92a6-bf3db8ecedac]

O custo da busca gulosa nem sempre é otimizada, pois ele vai tentar achar a "qualquer custo", mesmo que o caminho que tenha percorrido seja maior. Este trajeto que ele fez acima percorreu uma distância maior do que na solução encontrada pelo algoritmo A* (A estrela)

A imagem abaixo mostra o custo pra chegar a cada cidade. Este valor será usado no algoritmo A*.

[File: 28c1ba51-af32-4b8d-9fed-38c08468c232]

Busca A*

→ Expande o nó com menor valor de custo total estimado (soma do custo até chegar ao nó g(x) + h(x))

→ É completo se todos os valores forem positivos. (Encontra uma solução)

→ O algoritmo é eficiente pois poda/elimina nós que não são necessários para encontrar uma solução ótima.

→ Usa bastante memória

→ Obtém solução ótima:

- Versão com busca em árvore: se h(x) é admissível
- Versão com busca em grafo: se h(x) é consistente

[File: 41273543-7b54-4693-80c0-eb8f8a404be4]

Variantes do A*

• Iterative Deepening A* (IDA*)
  • Aumenta o valor máximo de f(x) a cada iteração.
• Memory-bounded A* (MA*)
• Simplified Memory-bounded A* (SMA*):
  • Limita a quantidade de nós mantidos na fronteira;
  • Elimina o nó com maior f(x) quando atinge o limite.

A performance dos algoritmos heurísticos depende muito da qualidade da função heurística.