Algoritmo A*

 Nota: Se procura o conto de Arthur Charles Clarke, veja A estrela.

Algoritmo A* (Lê-se: A-estrela) é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final. Ele é a combinação de aproximações heurísticas como do algoritmo Breadth First Search (Busca em Largura) e da formalidade do Algoritmo de Dijkstra.

O algoritmo foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Na publicação deles, ele foi chamado de algoritmo A; usando este algoritmo com uma heurística apropriada atinge-se um comportamento ótimo, e passou a ser conhecido por A*.

Sua aplicação vai desde aplicativos para encontrar rotas de deslocamento entre localidades a resolução de problemas, como a resolução de um quebra-cabeças. Ele é muito usado em jogos.

Algoritmo

Sejam

Q = conjunto de nós a serem pesquisados;
S = o estado inicial da busca

Faça:

1. Inicialize Q com o nó de busca (S) como única entrada;
2. Se Q está vazio, interrompa. Se não, escolha o melhor elemento de Q;
3. Se o estado (n) é um objetivo, retorne n;
4. (De outro modo) Remova n de Q;
5. Encontre os descendentes do estado (n) que não estão em visitados e crie todas as extensões de n para cada descendente;
6. Adicione os caminhos estendidos a Q e vá ao passo 2;

caminhos expandidos;

Uma estimativa que sempre subestima o comprimento real do caminho ate o objetivo é chamada de admissível. O uso de uma estimativa admissível garante que a busca de custo-uniforme ainda encontrará o menor caminho.

História

Trata-se de um algoritmo inventado por pesquisadores que trabalham no pathfinding do Robô "Shakey the Robot"

O A* foi criado como parte do projeto Shakey, que tinha como objetivo construir um robô móvel que pudesse planejar suas próprias ações. Nils Nilsson propôs originalmente o uso do algoritmo Graph Traverser para encontrar caminhos para o Shakey percorrer. O Graph Traverser é guiado por uma função heurística h(n), a distância estimada do nó n ao nó objetivo: ele ignora totalmente g(n), a distância do nó inicial até n . Bertram Raphael sugeriu usar a soma g(n) + h(n) . Peter Hart inventou os conceitos que hoje chamamos de admissibilidade e consistência de funções heurísticas. O A* foi originalmente projetado para encontrar caminhos de menor custo quando o custo de um caminho é a soma de seus custos, mas foi demonstrado que também pode ser usado para encontrar caminhos ótimos para qualquer problema que satisfaça as condições de uma álgebra de custos.

O artigo científico original, de 1968, continha um teorema afirmando que nenhum algoritmo semelhante ao A* poderia expandir menos nós do que A* se a função heurística fosse consistente e a regra de desempate de A* fosse escolhida adequadamente. Uma "correção" foi publicada alguns anos depois alegando que a consistência não era necessária, mas esta afirmação foi refutada no estudo definitivo de Dechter e Pearl sobre a otimalidade do A* (agora chamada de eficiência ótima), que deu um exemplo do A* com uma heurística que era admissível, mas não consistente, expandindo arbitrariamente mais nós do que um algoritmo alternativo do tipo A*.

Descrição

O algoritmo de localização de caminhos A* navegando em um labirinto gerado aleatoriamente

Ilustração da pesquisa A* para encontrar um caminho entre dois pontos de um gráfico. Da esquerda para a direita, uma heurística que prefere pontos mais próximos do objetivo é cada vez mais utilizada

O A* é um algoritmo de busca informado, ou best-first search, o que significa que é formulado em termos de grafos ponderados: partindo de um nó inicial específico de um grafo, visa encontrar um caminho para o nó objetivo determinado com o menor custo (menor distância percorrida, menor tempo, etc.). Ele fá-lo mantendo uma árvore de caminhos originados no nó inicial e estendendo esses caminhos uma aresta de cada vez até que seu critério de término seja satisfeito.

A cada iteração do seu loop principal, o A* precisa determinar quais dos seus caminhos estender. Isso é feito com base no custo do caminho e em uma estimativa do custo necessário para estender o caminho até a meta. Especificamente, o A* seleciona o caminho que minimiza

$f(n)=g(n)+h(n)$

onde n é o próximo nó no caminho, g(n) é o custo do caminho do nó inicial até n, e h(n) é uma função heurística que estima o custo do caminho mais barato de n até o objetivo. A* termina quando o caminho que ele escolhe estender for um caminho do início ao objetivo ou se não houver caminhos elegíveis para serem estendidos. A função heurística é específica do problema. Se a função heurística for admissível – o que significa que ela nunca superestima o custo real para atingir a meta – é garantido que o A* retornará um caminho de menor custo do início ao objetivo.

Tipicamente, as implementações deste algoritmo usam uma fila de prioridade para realizar a seleção repetida de nós de custo mínimo (estimado) para expansão. Esta fila de prioridade é conhecida como conjunto aberto, franja ou fronteira. A cada etapa do algoritmo, o nó com o menor valor f(x) é removido da fila, os valores de f e g de seus vizinhos são atualizados de acordo e esses vizinhos são adicionados à fila. O algoritmo continua até que um nó removido (portanto, o nó com o valor f mais baixo de todos os nós periféricos) seja um nó de meta. O valor f dessa meta é então também o custo do caminho mais curto, uma vez que h na meta é zero em uma heurística admissível.

O algoritmo descrito até agora nos dá apenas o comprimento do caminho mais curto. Para encontrar a sequência real de etapas, o algoritmo pode ser facilmente revisado para que cada nó no caminho acompanhe seu antecessor. Depois que esse algoritmo for executado, o nó final apontará para seu antecessor e assim por diante, até que o predecessor de algum nó seja o nó inicial.

Por exemplo, ao procurar a rota mais curta em um mapa, h(x) pode representar a distância em linha reta até o objetivo, uma vez que é fisicamente a menor distância possível entre dois pontos quaisquer. Para um mapa de grade de um jogo de vídeo, usar a distância de Manhattan ou a distância de Chebyshev torna-se melhor dependendo do conjunto de movimentos disponíveis (4 ou 8 direções).

Se a heurística h satisfazer a condição adicional h(x) ≤ d(x, y) + h(y) para cada aresta (x, y) do gráfico (onde d denota o comprimento dessa aresta), então h é chamado monótono, ou consistente . Com uma heurística consistente, o A* tem a garantia de encontrar um caminho ideal sem processar nenhum nó mais de uma vez e o A* é equivalente a executar o algoritmo de Dijkstra com o custo reduzido d'(x, y) = d(x, y) + h(y) − h(x) ^{[carece de fontes]}.

Pseudo-código

O pseudocódigo a seguir descreve o algoritmo:

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from the start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how cheap a path could be from start to finish if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := tentative_gScore + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

Observação: Neste pseudocódigo, se um nó for alcançado por um caminho, removido do openSet e posteriormente alcançado por um caminho mais barato, ele será adicionado ao openSet novamente. Isto é essencial para garantir que o caminho retornado seja ótimo se a função heurística for admissível, mas não consistente . Se a heurística for consistente, quando um nó é removido do openSet, o caminho para ele é garantido como ideal, portanto o teste ' tentative_gScore < gScore[neighbor] ' sempre falhará se o nó for alcançado novamente.

Ilustração da busca A* para encontrar o caminho de um nó inicial até um nó final em um problema de planeamento de movimento de robô . Os círculos vazios representam os nós do conjunto aberto, ou seja, aqueles que restam para serem explorados, e os preenchidos estão no conjunto fechado. A cor em cada nó fechado indica a distância do objetivo: quanto mais verde, mais próximo. Pode-se ver primeiro o A* se movendo em linha reta na direção do objetivo, depois ao atingir o obstáculo, ele explora rotas alternativas através dos nós do conjunto aberto.

Exemplo

Um exemplo de algoritmo A* em ação onde os nós são cidades conectadas a estradas e h(x) é a distância em linha reta até o ponto alvo:

Legenda: verde: início; azul: meta; laranja: visitado

O algoritmo A* também tem aplicações no mundo real. Neste exemplo, as arestas são ferrovias e h(x) é a distância do grande círculo (a distância mais curta possível em uma esfera) até o alvo. O algoritmo está procurando um caminho entre Washington, DC e Los Angeles.

Detalhes de implementação

Há uma série de otimizações simples ou detalhes de implementação que podem afetar significativamente o desempenho de uma implementação A*. O primeiro detalhe a ser observado é que a forma como a fila de prioridade trata os empates pode ter um efeito significativo no desempenho em algumas situações. Se os empates forem quebrados e a fila se comportar de maneira LIFO, A* se comportará como uma busca em profundidade entre caminhos de custos iguais (evitando explorar mais de uma solução igualmente ótima).

Quando um caminho é requerido no final da busca, é comum manter com cada nó uma referência ao pai daquele nó. Ao final da busca, essas referências podem ser utilizadas para recuperar o caminho ótimo. Se estas referências forem mantidas então pode ser importante que o mesmo nó não apareça na fila de prioridade mais de uma vez (cada entrada corresponde a um caminho diferente para o nó, e cada uma com um custo diferente). Uma abordagem padrão aqui é verificar se um nó prestes a ser adicionado já aparece na fila de prioridade. Se isso acontecer, então a prioridade e os ponteiros pai serão alterados para corresponder ao caminho de custo mais baixo. Uma fila de prioridade baseada em heap binário padrão não suporta diretamente a operação de busca por um de seus elementos, mas pode ser aumentada com uma tabela hash que mapeia os elementos para sua posição no heap, permitindo que esta operação de diminuição de prioridade seja executada em tempo logarítmico. Alternativamente, um heap de Fibonacci pode realizar as mesmas operações de prioridade decrescente em tempo amortizado constante.

Casos especiais

O algoritmo de Dijkstra, como outro exemplo de algoritmo de busca de custo uniforme, pode ser visto como um caso especial de A* onde<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $h(x)=0$</mi><mo stretchy="false"> $h(x)=0$</mo><mi> $h(x)=0$</mi><mo stretchy="false"> $h(x)=0$</mo><mo> $h(x)=0$</mo><mn> $h(x)=0$</mn></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics></math>$h(x)=0$ para todo x . A busca geral em profundidade pode ser implementada usando A* considerando que existe um contador global C inicializado com um valor muito grande. Cada vez que processamos um nó, atribuímos C a todos os seus vizinhos recém-descobertos. Após cada atribuição, diminuímos o contador C em um. Assim, quanto mais cedo um nó for descoberto, maior será seu valor $h(x)$. Tanto o algoritmo de Dijkstra quanto a busca em profundidade podem ser implementados de forma mais eficiente sem incluir um valor $h(x)$ em cada nó.

Propriedades

Término e integralidade

Em grafos finitos com pesos de aresta não negativos, é garantido que o A* termine e seja completo, ou seja, que encontre sempre uma solução (um caminho do início à meta), se existir. Em gráficos infinitos com um fator de ramificação finito e custos de borda limitados a zero (${\textstyle d(x,y)>\varepsilon >0}$ para alguns $\varepsilon$ fixos), é garantido que A* terminará apenas se existir uma solução.

Admissibilidade

Um algoritmo de busca é considerado admissível se for garantido que ele retornará uma solução ótima. Se a função heurística usada por A* for admissível, então A* é admissível. Uma “prova” intuitiva disso é a seguinte:

Quando A* termina sua busca, ele encontrou um caminho do início ao objetivo cujo custo real é menor que o custo estimado de qualquer caminho do início ao objetivo através de qualquer nó aberto (o valor $f$ do nó). Quando a heurística é admissível, essas estimativas são otimistas (não exatamente – veja o próximo parágrafo), então o A* pode ignorar com segurança esses nós porque eles não podem levar a uma solução mais barata do que aquela que já possui. Em outras palavras, A* nunca ignorará a possibilidade de um caminho de custo mais baixo do início ao objetivo e, portanto, continuará a procurar até que tais possibilidades não existam.

A prova real é um pouco mais complicada porque os valores<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f$</mi></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics></math>$f$ não são garantidos que sejam os valores dos nós abertos sejam otimistas, mesmo que a heurística seja admissível. Isso ocorre porque os valores <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $g$</mi></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics></math>$g$ de nós abertos não são garantidos como óptimos, então a soma<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $g+h$</mi><mo> $g+h$</mo><mi> $g+h$</mi></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics></math>$g+h$não é garantido que seja otimista.

Otimização e consistência

O algoritmo A é otimamente eficiente em relação a um conjunto de algoritmos alternativos Alts em um conjunto de problemas P se para cada problema P em P e cada algoritmo A′ em Alts, o conjunto de nós expandidos por A na resolução de P é um subconjunto (possivelmente igual) do conjunto de nós expandidos por A′ na resolução de P. O estudo definitivo da eficiência ótima de A* deve-se a Rina Dechter e Judea Pearl. Elas consideraram uma variedade de definições de Alts e P em combinação com a heurística de A* sendo meramente admissível ou sendo consistente e admissível. O resultado positivo mais interessante que eles provaram é que A*, com uma heurística consistente, é otimamente eficiente em relação a todos os algoritmos de busca admissíveis do tipo A* em todos os problemas de busca "não patológicos". De grosso modo, a sua noção de problema não patológico é o que hoje entendemos por “até ao desempate”. Este resultado não é válido se a heurística de A* for admissível, mas não consistente. Nesse caso, Dechter e Pearl mostraram que existem algoritmos admissíveis do tipo A* que podem expandir arbitrariamente menos nós do que A* em alguns problemas não patológicos.

A eficiência óptima diz respeito ao conjunto de nós expandidos, não ao número de expansões de nós (o número de iterações do loop principal de A*). Quando a heurística utilizada é admissível, mas não consistente, é possível que um nó seja expandido por A* muitas vezes, um número exponencial de vezes no pior caso. Nessas circunstâncias, o algoritmo de Dijkstra poderia superar A* por uma grande margem. No entanto, pesquisas mais recentes descobriram que este caso patológico só ocorre em certas situações inventadas onde o peso da aresta do grafo de busca é exponencial no tamanho do grafo e que certas heurísticas inconsistentes (mas admissíveis) podem levar a um número reduzido de expansões de nós em pesquisas A*.

Relaxamento limitado

Uma pesquisa A* que usa uma heurística que é 5,0(=ε) vezes uma heurística consistente e obtém um caminho abaixo do ideal

Embora o critério de admissibilidade garanta um caminho de solução óptimo, também significa que A* deve examinar todos os caminhos igualmente meritórios para encontrar o caminho óptimo. Para calcular caminhos mais curtos aproximados, é possível acelerar a busca em detrimento da otimalidade, relaxando o critério de admissibilidade. Muitas vezes queremos limitar esta relaxação, para que possamos garantir que o caminho da solução não é pior que (1 + ε ) vezes o caminho da solução ideal. Esta nova garantia é referida como ε-admissível.

Existem vários algoritmos ε-admissíveis:

• Ponderação A*/Ponderação Estática. Se _ha ( n ) é uma função heurística admissível, na versão ponderada da busca A* utiliza-se h_w(n) = ε h_a(n), ε > 1 como função heurística, e realiza-se a busca A* como de costume (o que eventualmente acontece mais rápido do que usar h_a, pois menos nós são expandidos). O caminho, portanto, encontrado pelo algoritmo de busca pode ter um custo no máximo ε vezes maior que o caminho de menor custo no gráfico.
• A Ponderação Dinâmica usa a função de custo $f(n)=g(n)+(1+\varepsilon w(n))h(n)$, onde $w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{em caso contrário}}\end{cases}}$, e onde $d(n)$ é a profundidade da pesquisa e N é o comprimento previsto do caminho da solução.
• A ponderação dinâmica amostrada usa amostragem de nós para melhor estimar e reduzir o erro heurístico.
• $A_{\varepsilon }^{*}$ . usa duas funções heurísticas. A primeira é a lista FOCAL, que é usada para selecionar os nós candidatos, e a segunda h _F é usada para selecionar o nó mais promissor da lista FOCAL.
• A_ε seleciona nós com a função $Af(n)+Bh_{F}(n)$, onde A e B são constantes. Se nenhum nó puder ser selecionado, o algoritmo retrocederá com a função $Cf(n)+Dh_{F}(n)$, onde C e D são constantes.
• AlphA* tenta promover a exploração em profundidade, preferindo nós recentemente expandidos. AlphA* usa a função de custo $f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)$, onde $w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{em caso contrário}}\end{cases}}$, onde λ e Λ são constantes com $\lambda \leq \Lambda$, π ( n ) é o pai de n e ñ é o nó expandido mais recentemente.

Complexidade

A complexidade de A* depende da heurística. No pior caso de um espaço de busca ilimitado, o número de nós expandidos é exponencial na profundidade da solução (o caminho mais curto) d : O(b^d), onde b é o fator de ramificação (o número médio de sucessores por estado ). Isso pressupõe que existe um estado objetivo e é alcançável a partir do estado inicial; se não for, e o espaço de estados for infinito, o algoritmo não terminará.

A função heurística tem um efeito importante no desempenho prático da busca A*, uma vez que uma boa heurística permite que A* remova muitos dos nós b^d que uma busca desinformada expandiria. Sua qualidade pode ser expressa em termos do fator de ramificação efetivo b*, que pode ser determinado empiricamente para uma instância do problema medindo o número de nós gerados pela expansão, N, e a profundidade da solução, resolvendo então

$N+1=1+b^{*}+(b^{*})^{2}+\dots +(b^{*})^{d}.$

Boas heurísticas são aquelas com baixo fator de ramificação efetivo (sendo o ideal b* = 1 ).

A complexidade do tempo é polinomial quando o espaço de busca é uma árvore, existe um único estado objetivo e a função heurística h atende à seguinte condição:

$|h(x)-h^{*}(x)|=O(\log h^{*}(x))$

onde h^* é a heurística ótima, o custo exato para ir de x até a meta. Em outras palavras, o erro de h não crescerá mais rápido que o logaritmo da “heurística perfeita” h^* que retorna a distância real de x até o objetivo.

A complexidade espacial de A* é aproximadamente a mesma de todos os outros algoritmos de busca de grafos, pois mantém todos os nós gerados na memória. Na prática, esta acaba sendo a maior desvantagem da pesquisa A*, levando ao desenvolvimento de pesquisas heurísticas limitadas por memória, como A* por aprofundamento interativo, A* limitado por memória e SMA* .

Aplicações

A* é frequentemente usado para o problema comum de localização de caminhos em aplicações como jogos de vídeo, mas foi originalmente projetado como um algoritmo geral de travessia de gráfico. Encontra aplicações em diversos problemas, incluindo o problema de análise sintática usando gramáticas estocásticas em PNL . Outros casos incluem uma busca informativa com aprendizagem online.

Relações com outros algoritmos

O que diferencia A* de um algoritmo ganancioso de busca do melhor primeiro é que ele leva em consideração o custo/distância já percorrida, g(n) .

Algumas variantes comuns do algoritmo de Dijkstra podem ser vistas como um caso especial de A* onde a heurística $h(n)=0$ para todos os nós; por sua vez, tanto Dijkstra quanto A* são casos especiais de programação dinâmica . O próprio A* é um caso especial de generalização do branch and bound.

O A* é semelhante à busca por feixe, exceto que a busca por feixe mantém um limite no número de caminhos que deve explorar.

Variantes

• Anytime A*
• Block A*
• D*
• Field D*
• Fringe
• Fringe Saving A* (FSA*)
• Generalized Adaptive A* (GAA*)
• Incremental heuristic search
• Reduced A*
• Iterative deepening A* (IDA*)
• Jump point search
• Lifelong Planning A* (LPA*)
• New Bidirectional A* (NBA*)
• Simplified Memory bounded A* (SMA*)
• Theta*

O A* também pode ser adaptado a um algoritmo de busca bidirecional . Cuidados especiais devem ser tomados com o critério de parada.

Notas e referências

Ligações externas

• (em português) A* Pathfinding para Iniciantes
• (em português) Projeto de Pesquisa de Algoritmos de Busca
• (em inglês) Amit's A* Pages -- Path finding Texto bastante completo sobre busca de caminhos (Path finding) usando o Algoritmo A*