Futebol de Robos F180 » Inteligência

# Algoritmo A*

## Introdução

A* é um algoritmo para planejamento de trajetórias em um grid contendo o destino, caminhos livres e obstáculos. Sendo amplamente utilizado para encontrar o caminho mais curto (aproximação), de uma maneira rápida e inteligente. Antes de descrever o funcionamento do mesmo, começamos com o algoritmo de Dijkstra e depois como ele pode ser derivado no A*.

## Algoritmo de Dijkstra

Dado um grafo e um vértice de origem, como podemos achar a mínima distância dele para todos os outros vértices?

Começamos a implementação criando uma lista aberta e uma lista fechada:

* A lista fechada terá como objetivo simplesmente armazenar o estado que o vértice possui, se sua miníma distância foi calculada ou não (True/False), podendo ser simplesmente um vetor de booleans ou uma hash table. 

* A lista aberta conterá todos os outros vértices que já foram visitados e não estão na lista fechada, sendo composta de um par (distância, índice). Durante a execução do algoritmo, precisaremos várias vezes saber o vértice de menor distância na lista, por isso sendo de grande utilidade utilizar uma priority queue como lista aberta, pois os elementos ficarão ordenados e basta pegarmos o primeiro. 

Podemos descrever o algoritmo da seguinte forma:

```

1) Initialize distances of all vertices as infinite.

2) Create an empty set.  Every item of set is a pair

  (weight, vertex). Weight (or distance) is used used

  as first item  of pair as first item is by default 

  used to compare two pairs.

3) Insert source vertex into the set and make its

   distance as 0.

4) While Set doesn't become empty, do following

    a) Extract minimum distance vertex from Set. 

       Let the extracted vertex be u.

    b) Loop through all adjacent of u and do 

       following for every vertex v.

           // If there is a shorter path to v

           // through u. 

           If dist[v] > dist[u] + weight(u, v)

               (i) Update distance of v, i.e., do

                     dist[v] = dist[u] + weight(u, v)

               (i) If v is in set, update its distance

                   in set by removing it first, then

                   inserting with new distance

               (ii) If v is not in set, then insert

                    it in set with new distance

5) Print distance array dist[] to print all shortest

   paths. 

```

Vamos usar o grafo abaixo como exemplo do funcionamento:

![](exgrafo.png)

A primeira coisa a se fazer é setar todas as distâncias para +INFINITO, excetuando a origem (vértice v1), que será inserida na lista aberta e terá sua distância como 0.

| LISTA ABERTA |

|---           |

|   (0 , 1)    |   

| LISTA FECHADA |

|---            |

Após isso, retiraremos o vértice de menor valor da lista aberta e o inserimos na lista fechada, nesse caso o v1, e calculamos a distância de todos os vértices adjacentes ao recém retirado, os vértices v6, v3 e v2, respectivamente com distâncias 14, 9 e 7, inserindo-os na lista aberta.

![](grafoit1.png)

| LISTA ABERTA |

|---           |

|   (9 , 3)    | 

|   (13 , 2)   | 

|   (14 , 6)   |   

| LISTA FECHADA |

|---            |

|   1           | 

Agora devemos repetir o processo, retirando o vértice de menor valor da lista aberta e o inserindo na fechada, nesse caso o v3, e então atualizar as distâncias dos vértices adjacentes de v3. V5 não foi inicializado ainda, basta então adicioná-lo na lista aberta com a distância de 9 + 2 = 11. V2 tem, em relação a v3, distância 9 + 10 = 19, maior que o valor de 13 já existente, portanto mantemos a distância como 13. V6 tem, em relação a v3, distância 9 + 2 = 11, menor que o valor de 14 já existente, portanto substituímos o valor dele na lista aberta por 11.  

![](grafoit2.png)

| LISTA ABERTA |

|---           | 

|   (11 , 5)   | 

|   (11 , 6)   | 

|   (13 , 2)   | 

|   (20 , 4)   | 

| LISTA FECHADA |

|---            |

|   1           | 

|   3           | 

Repetimos o processo até a lista aberta estar vazia e todos os vértices estejam na lista fechada, assim encontrando as menores distâncias de cada vértice, se quisermos a menor distância até um vértice específico, basta pararmos de iterar quando ele sair da lista aberta. Veja que não encontramos o caminho específico que leva a menor distância, se quisermos fazer isso, basta criar um vetor com os índices dos vértices que sempre é atualizado quando o valor da distância também é atualizado.

## Derivando o A*

O A* é uma modificação do Dijkstra que é otimizado para apenas um destino. Enquanto o Dijkstra pode encontrar caminhos para todas, o A* encontra apenas para uma, priorizando os caminhos que estão levando mais próximo do objetivo, usando a distância do início e a distância estimada até o objetivo.

A grande diferença na implementação é que a lista aberta não conterá mais o par (distância, índice), e sim o par (f, índice), sendo o parâmetro f a soma de outros dois, o g e o h.

* g -> A distância percorrida até chegar aquele determinado vértice, exatamente igual à anterior.

* h -> A distância estimada para, a partir daquele vértice, chegar ao objetivo. Para isso podemos calcular a distância euclidiana entre os dois pontos ou usar outro tipo de métrica, como por exemplo a distância da geometria do taxista. Para fazer o cálculo, ignoramos a presença de obstáculos, por isso se tratando apenas de uma aproximação para privilegiar caminhos mais próximos do objetivo.

Segue abaixo a descrição do algoritmo:

```

// A* Search Algorithm

1.  Initialize the open list

2.  Initialize the closed list

    put the starting node on the open 

    list (you can leave its f at zero)

3.  while the open list is not empty

    a) find the node with the least f on 

       the open list, call it "q"

    b) pop q off the open list

    c) generate q's 8 successors and set their 

       parents to q

    d) for each successor

        i) if successor is the goal, stop search

          successor.g = q.g + distance between 

                              successor and q

          successor.h = distance from goal to 

          successor (This can be done using many 

          ways, we will discuss three heuristics- 

          Manhattan, Diagonal and Euclidean 

          Heuristics)

          successor.f = successor.g + successor.h

        ii) if a node with the same position as 

            successor is in the OPEN list which has a 

           lower f than successor, skip this successor

        iii) if a node with the same position as 

            successor  is in the CLOSED list which has

            a lower f than successor, skip this successor

            otherwise, add  the node to the open list

     end (for loop)

    e) push q on the closed list

    end (while loop) 

```

Abaixo está um caminho gerado pelo algoritmo, considerando a distância euclideana:

![](gridn.png)

Queremos partir da célula azul e chegar na vermelha. O grid acima pode ser considerado um grafo, no qual cada célula está conectada com sua vizinha, excetuando os casos em que esta é um obstáculo (pintadas de cinza), onde não há conexão das células livres do grid com as pintadas de cinza.

Considerando o custo de movimento como 1, ou seja, cada vértice possuirá g = g_pai + 1.0, se setarmos h = 0 para todo o vértice, não existiria diferença entre andar de (4,2) para (3,3) ou (4,3), e o algoritmo seria exatamente igual ao Dijkstra, porém sabemos que se mover para (3,3) leva ao destino mais rápido. 

Vamos quantizar o parâmetro f neste caso para determinar para onde devemos nos mover, como ambos os vértices são originados de (4,2), possuem mesmo valor de g. Para o valor de h, considerando o destino sendo (1,1), o vértice (3,3) possuirá menor distância euclideana, assim possuindo menor h e, consequentemente, menor valor de f, explicando a prioridade de movimentação para o mesmo. 

## Referências

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/

https://www.geeksforgeeks.org/a-search-algorithm/

https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html