Problem-Solving Agentes
Problem-solving agents, ao contrário de agentes mais simples, precisam considerar ações futuras e suas consequências. Dado um objetivo definido com base no estado final desejado e em medidas de desempenho, encontrar a melhor forma de alcançá-lo pode ser complexo, exigindo estratégias de busca adequadas à situação. Em resumo, essa "forma ótima" refere-se à sequência de ações que o agente deve seguir para atingir o objetivo.
Arad-Bucareste
Uma procura relativamente simples, a olho, levar-nos-ia à conclusão que o caminho com menor custo que liga Arad a Bucareste é o caminho
\[Arad→Sibiu→Rimnicu Vilcea→Pilesti→Bucareste\]
Um agente não pode fazer "pesquisas a olho" e precisa de uma estratégia de procura apropriada para encontrar a sequência de ações correta (estratégias que serão discutidas mais adiante). Após identificar essa sequência, o agente a executa na ordem definida. Como nota, podemos dizer que o ambiente em questão é estático, completamente observável, discreto e determinístico.
Tipos de problemas
Determinista e completamente observável → problema com estado único: O agente sabe exatamente em que estado se encontra, e a solução é uma sequência fixa de ações. Não observável → problema de conformidade: O agente pode não saber exatamente onde está, mas, se existir uma solução, ela será uma sequência de ações. Não determinista e/ou parcialmente observável → problema de contingência: O agente recebe nova informação através das perceções sobre o estado atual. A solução é representada como uma árvore de ações ou um plano, normalmente alternando entre busca e execução. Espaço de estados desconhecido → problema de exploração (executado "online"): O agente descobre o ambiente à medida que interage com ele.
Procura cega
Um estado é uma (representação de uma) configuração física. Um nó é uma estrutura de dados constituinte da árvore de procura incluindo o pai, o estado, e outros detalhes relevantes para o algoritmo
Antes de referir algumas estratégias de procura cega, vamos precisar de definir um par de noções bastante importantes quanto à classificação das mesmas:
- uma estratégia de procura diz-se completa caso encontre sempre uma solução para o problema proposto, caso exista (e caso não exista, diz que não há solução).
- uma estratégia de procura diz-se ótima caso encontre a solução ótima (de menor custo).
Para nos ajudar a calcular as noções de complexidade temporal e espacial vamos utilizar variaveis que nos vão ajudar a descrever as mesmas:
- fator máximo de ramificação da árvore de procura, b , vulgo branching factor, que corresponde ao número máximo de sucessores de um dado nó;
- profundidade da solução de menor custo, d , vulgo depth of the shallowest node
- profundidade máxima do espaço de estados, m , que corresponde à quantidade máxima de espaços entre um qualquer par de estados
Procura em Largura Primeiro (PLP) / Breadth-First Search (BFS)
A procura em largura primeiro expande o nó de menor profundidade na fronteira - visita os nós de uma dada profundidade e expande-os, gerando os nós da próxima profundidade, que apenas serão visitados assim que todos os da atual tiverem sido visitados.
- Completa: Sim, se b for finito.
- Complexidade Temporal: \(O(b^{d})\) (se em teste na geração) ou \(O(b^{d+1})\) (se em teste na expansão)
- Complexidade Espacial: \(O(b^{d})\) (se em teste na geração) ou \(O(b^{d+1})\) (se em teste na expansão)
- Ótima: Sim, se o custo do caminho não diminuir ao aumentar a profundidade* - em geral, não podemos afirmar que é ótima, já que tal não é sempre garantido.
Implementação: frontier é uma fila FIFO; novos sucessores vão para o fim
Note-se que a BFS deve realizar o teste objetivo assim que o nó é gerado, para evitar processamento desnecessário. Numa BFS, sabemos que no nó do primeiro teste objetivo passado com sucesso vamos ter a solução com menor profundidade, já que todos os nós que existem a uma profundidade menor - com menor custo - já foram exploradas e não passaram no teste.
É, aqui, clara a diferença temporal e espacial entre realizar o teste na geração e na expansão dos nós: com o teste na geração, exploramos completamente apenas 2 níveis da árvore (já que G ao ser gerado passa logo o teste objetivo e acabamos), poupando aí a expansão de todo um nível da árvore.
Procura de Custo Uniforme
A procura de custo uniforme é equivalente ao algoritmo de Dijkstra, que expande sempre o nó da fronteira com o menor custo de caminho. O teste objetivo deve ser realizado durante a expansão do nó, e não na sua geração, pois o primeiro nó a passar o teste pode não ser o de menor custo total. Por exemplo, se gerarmos dois nós, A e B, com custos de 88 e 66, respectivamente, e ambos forem nós-objetivo, B representa o caminho ótimo. Se o teste fosse feito na geração e A fosse considerado primeiro, ele seria erroneamente incluído no caminho ótimo em vez de B.
- Completa: Sim, se o custo do caminho não diminuir ao aumentar a profundidade.
- Complexidade Temporal: \(O(b^{1+⌊C^{*}/ε⌋})\), onde \(C^{*}\) é o custo da solução ótima e ε é o menor custo de qualquer ação.
- Complexidade Espacial: \(O(b^{1+⌊C^{*}/ε⌋})\)
- Ótima: Sim, se o custo do caminho não diminuir ao aumentar a profundidade.
Implementação: fila ordenada pelo custo do caminho acumulado
Procura em Profundidade Primeiro (PDP) / Depth-First Search (DFS)
A procura em profundidade expande sempre o nó com a maior profundidade na fronteira, explorando um caminho até o fim e recuando quando não há mais opções de progresso.
- Completa: Não, se o espaço de estados for infinito.
- Complexidade Temporal: \(O(b^{m})\), onde m é a profundidade máxima do espaço de estados.
- Complexidade Espacial: \(O(bm)\) se for implementada recursivamente, \(O(m)\) se for implementada iterativamente.
- Ótima: Não, em geral.
- Completa: Não, a solução pode estar além do limite.
- Complexidade Temporal: \(O(b^{l})\), onde l é o limite de profundidade.
- Complexidade Espacial: \(O(bm)\) com implementação recursiva, \(O(l)\) com implementação iterativa.
- Ótima: Não, em geral.
- Completa: Sim, se o espaço de estados for finito.
- Complexidade Temporal: \(O(b^{d})\)
- Complexidade Espacial: \(O(bd)\)
- Ótima: Sim, se o custo do caminho não diminuir ao aumentar a profundidade.
- Completa: Sim, se a procura unidirecional for completa.
- Complexidade Temporal: \(O(b^{d/2})\)
- Complexidade Espacial: \(O(b^{d/2})\)
- Ótima: Sim, se a procura unidirecional for ótima.
Procura em Profundidade Limitada / DFS Limitada (Depth-Limited Search)
A busca em profundidade limitada (DFS limitada) impõe um limite à profundidade, onde nós além desse ponto são ignorados, evitando o problema da profundidade infinita. No entanto, isso pode impedir a descoberta de soluções se o nó-objetivo estiver além do limite. Assim, além de sucesso ou fracasso, a DFS limitada pode retornar "cut-off" quando não encontra a solução, mas sabe que o limite imposto não é o da profundidade máxima da árvore. Aplicar um limite faz sentido em cenários como o problema de Arad-Bucareste, onde há 20 cidades e um máximo de 9 passos entre qualquer par de cidades. Definir um limite de 9 elimina a profundidade infinita e mantém a solução ótima acessível. Esse "número máximo de passos" é chamado de diâmetro do espaço de estados.
Procura em Profundidade Iterativa / DFS Iterativa (Iterative Deepening Search)
A procura em profundidade iterativa (DFS iterativa) é uma combinação da DFS limitada e da BFS. A ideia é realizar uma DFS limitada com um limite de 1, depois 2, depois 3, e assim por diante, até encontrar a solução. Isso garante que a solução ótima seja encontrada, mesmo que a profundidade máxima seja desconhecida.
Procura Bidirecional
A procura bidirecional é uma estratégia que, como o nome indica, procura a solução a partir do estado inicial e do estado final, encontrando-se no meio. A ideia é reduzir a complexidade temporal e espacial, já que a procura bidirecional é mais eficiente que a procura unidirecional. No entanto, a procura bidirecional é mais complexa e requer um teste objetivo mais complexo.
- mauricio
10/09/2024
< Return to home