Projeto

Geral

Perfil

Algoritmo A* » Histórico » Versão 9

Antonio de Souza Gomes Pereira, 08/03/2020 19:58 h

1 1 Antonio de Souza Gomes Pereira
# Algoritmo A*
2
3 2 Antonio de Souza Gomes Pereira
## Introdução
4
5
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*.
6
7
## Algoritmo de Dijkstra
8
9
Dado um grafo e um vértice de origem, como podemos achar a mínima distância dele para todos os outros vértices?
10
Começamos a implementação criando uma lista aberta e uma lista fechada:
11
12
* 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. 
13
14 9 Antonio de Souza Gomes Pereira
* 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 para manter os elementos ordenados. 
15 2 Antonio de Souza Gomes Pereira
16
Podemos descrever o algoritmo da seguinte forma:
17
18
19
```
20
1) Initialize distances of all vertices as infinite.
21
22
2) Create an empty set.  Every item of set is a pair
23
  (weight, vertex). Weight (or distance) is used used
24
  as first item  of pair as first item is by default 
25
  used to compare two pairs.
26
27
3) Insert source vertex into the set and make its
28
   distance as 0.
29
30
4) While Set doesn't become empty, do following
31
    a) Extract minimum distance vertex from Set. 
32
       Let the extracted vertex be u.
33
    b) Loop through all adjacent of u and do 
34
       following for every vertex v.
35
36
           // If there is a shorter path to v
37
           // through u. 
38
           If dist[v] > dist[u] + weight(u, v)
39
40
               (i) Update distance of v, i.e., do
41
                     dist[v] = dist[u] + weight(u, v)
42
               (i) If v is in set, update its distance
43
                   in set by removing it first, then
44
                   inserting with new distance
45
               (ii) If v is not in set, then insert
46
                    it in set with new distance
47
               
48
5) Print distance array dist[] to print all shortest
49
   paths. 
50
```
51
52
53
54
Vamos usar o grafo abaixo como exemplo do funcionamento:
55
56
![](exgrafo.png)
57
58 9 Antonio de Souza Gomes Pereira
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.
59 2 Antonio de Souza Gomes Pereira
60
| LISTA ABERTA |
61
|---           |
62
|   (0 , 1)    |   
63
64
65
| LISTA FECHADA |
66
|---            |
67
68 9 Antonio de Souza Gomes Pereira
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.
69 3 Antonio de Souza Gomes Pereira
![](grafoit1.png)
70 2 Antonio de Souza Gomes Pereira
71 1 Antonio de Souza Gomes Pereira
| LISTA ABERTA |
72 2 Antonio de Souza Gomes Pereira
|---           |
73
|   (9 , 3)    | 
74 3 Antonio de Souza Gomes Pereira
|   (13 , 2)   | 
75 2 Antonio de Souza Gomes Pereira
|   (14 , 6)   |   
76
77
78
79
| LISTA FECHADA |
80
|---            |
81
|   1           | 
82
83
    
84
85 9 Antonio de Souza Gomes Pereira
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.  
86 2 Antonio de Souza Gomes Pereira
87 1 Antonio de Souza Gomes Pereira
88 3 Antonio de Souza Gomes Pereira
![](grafoit2.png)
89 2 Antonio de Souza Gomes Pereira
90 1 Antonio de Souza Gomes Pereira
| LISTA ABERTA |
91 2 Antonio de Souza Gomes Pereira
|---           | 
92 3 Antonio de Souza Gomes Pereira
|   (11 , 5)   | 
93
|   (11 , 6)   | 
94
|   (13 , 2)   | 
95
|   (20 , 4)   | 
96
 
97 2 Antonio de Souza Gomes Pereira
  
98 1 Antonio de Souza Gomes Pereira
| LISTA FECHADA |
99
|---            |
100
|   1           | 
101 3 Antonio de Souza Gomes Pereira
|   3           | 
102 1 Antonio de Souza Gomes Pereira
103 9 Antonio de Souza Gomes Pereira
Repetimos o processo até a lista aberta estar vazia e todos os vértices presentes 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, para fazer isso, basta criar um vetor com os índices dos vértices que sempre é atualizado quando o valor da distância também é atualizado.
104 1 Antonio de Souza Gomes Pereira
105
## Derivando o A*
106
107 8 Antonio de Souza Gomes Pereira
O A* é uma modificação do Dijkstra que é otimizado para apenas um destino. Enquanto o Dijkstra pode encontrar caminhos para todos, o A* encontra apenas para um, 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.
108 3 Antonio de Souza Gomes Pereira
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.
109 1 Antonio de Souza Gomes Pereira
110 8 Antonio de Souza Gomes Pereira
* g -> A distância percorrida até chegar aquele determinado vértice, exatamente igual à distância do Dijkstra.
111 3 Antonio de Souza Gomes Pereira
* 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.
112
113
Segue abaixo a descrição do algoritmo:
114
115
```
116
// A* Search Algorithm
117
1.  Initialize the open list
118
2.  Initialize the closed list
119
    put the starting node on the open 
120
    list (you can leave its f at zero)
121
122
3.  while the open list is not empty
123
    a) find the node with the least f on 
124
       the open list, call it "q"
125
126
    b) pop q off the open list
127
  
128
    c) generate q's 8 successors and set their 
129
       parents to q
130
   
131
    d) for each successor
132
        i) if successor is the goal, stop search
133
          successor.g = q.g + distance between 
134
                              successor and q
135
          successor.h = distance from goal to 
136
          successor (This can be done using many 
137
          ways, we will discuss three heuristics- 
138
          Manhattan, Diagonal and Euclidean 
139
          Heuristics)
140
          
141
          successor.f = successor.g + successor.h
142
143
        ii) if a node with the same position as 
144
            successor is in the OPEN list which has a 
145
           lower f than successor, skip this successor
146
147
        iii) if a node with the same position as 
148
            successor  is in the CLOSED list which has
149
            a lower f than successor, skip this successor
150
            otherwise, add  the node to the open list
151
     end (for loop)
152
  
153
    e) push q on the closed list
154
    end (while loop) 
155
156
```
157 4 Antonio de Souza Gomes Pereira
Abaixo está um caminho gerado pelo algoritmo, considerando a distância euclideana:
158 2 Antonio de Souza Gomes Pereira
159 5 Antonio de Souza Gomes Pereira
![](gridn.png)
160 1 Antonio de Souza Gomes Pereira
161
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 é um obstáculo (pintadas de cinza), onde não há conexão das células livres do grid com as pintadas de cinza.
162
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. 
163
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. 
164
165 9 Antonio de Souza Gomes Pereira
Vantagens e desvantagens do algoritmo:
166 1 Antonio de Souza Gomes Pereira
167 9 Antonio de Souza Gomes Pereira
**VANTAGENS**
168
169
* Gera uma trajetória otimizada, de distância reduzida
170
* É bastante eficiente, gerando poucos vértices no cálculo da trajetória
171
172
**Desvantagens**
173
174
* Necessidade de discretizar o campo 
175
* A velocidade de execução depende muito da precisão do método de cálculo do parâmetro h
176
 
177 5 Antonio de Souza Gomes Pereira
178 1 Antonio de Souza Gomes Pereira
## Referências
179 5 Antonio de Souza Gomes Pereira
180
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/
181
182
https://www.geeksforgeeks.org/a-search-algorithm/
183
184
https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2
185
186
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html