Projeto

Geral

Perfil

Planejamento de Tragetória » Histórico » Versão 3

Nicolas Oliveira, 05/03/2018 18:27 h

1 1 Nicolas Oliveira
# Planejamento de Tragetória
2
3 2 Nicolas Oliveira
Nos utilizamos do algoritmo RRT (Rapidly-Exploring Random Tree) para calcular nossa tragetória. Ele busca uma trajetória a partir de um estado inicial até o objetivo expandindo uma árvore de busca. 
4
Para isso necessitamos de 3 funções básicas:
5 1 Nicolas Oliveira
6
* Extend(env:enviroment,current:state,target:state,Step:real):state
7
8
Essa função dado um estado atual extende dando um passo em direção ao objetivo, ou em uma direção aleatória. Caso uma colisão ocorra ela retorna um estado vazio (EmptyState).
9
Pseudo código:
10
11 3 Nicolas Oliveira
```c
12
r = (Target - Current)/||Targe-Current|| ; //vetor unitário na direção do target
13
NewState = r*Step + Current ; 
14
if (Colision(NewState)) NewState = EmptyState; //confere se o novo estado vai colidir com algum obstáculo.
15
return NewState;
16
```
17 1 Nicolas Oliveira
18
* Distance(current:state,target:state):real
19
20
Calcula a distância do estado atual ao objetivo, utilizamos a euclidiana nessa implementação.
21
22
* RandomState():state
23
24
Retorna um novo estado uniformemente distribuído no ambiente.
25
26 3 Nicolas Oliveira
```c
27
float random_x;
28
float random_y;
29
random_x = fiel_length*(rand()-0.5); //Random gera um número aleatório uniformemente aleatório distribuído entre 0 e 1
30
random_y = fiel_length*(rand()-0.5); 
31
```
32 1 Nicolas Oliveira
33
Basicamente a função estender pode utilizar como target o objetivo ou um ponto aleátório, o que garante que o algoritmo pode encontrar um caminho sem colidir com nenhum obstáculo. Como na figura abaixo:
34
35
![](rrt.PNG)
36
37
A implementação seguiu o pseudo código abaixo:
38
39
![](pseudocódigo.PNG)
40
41
***A função Nearest garante que sempre extendemos a árvore do nó mais próximo do objetivo, porém ela também demanda muito processamento, já que tem q varrer a árvore toda a cada iteração. Vamos estudar um jeito para resolver isso.***
42
Definimos uma árvore de pontos como uma matriz de 4 colunas, onde a primeira é o id do ponto, a segunda a coordenada x, a terceira a coordenada y e a quarta o id do pai. Dessa forma os nós são adicionados com o id sendo incrementado de 1 a cada nó. O id do pai é o id do nó da onde aquale novo ramo foi gerado. Assim quando encontramos um solução podemos fazer o backtracking nessa árvore para reconstruir a tragetória.
43
44
O próximo passo foi implentar a extenção do RRT (ERRT), com memória da última tragetória. Assim na hora de escolhermos um target podemos ir em direção ao objetivo, em uma direção aleatória ou em direção a algum ponto da última tragetória, como na imagem e código abaixo.
45
46
![](errt.PNG)
47
![](choose.PNG)
48
49
Por último implementamos a suavização da tragetória que segue o algoritmo abaixo descrito. Ela auxilia muito na rapidez com que o robô será capaz de seguir a trajetóra.
50
51
![](suavização.png)
52
53
54
## Implementações futuras e problemas atuais
55
56
* Atualmente caso o robô entre numa área considerada obstáculo ele não consegue gerar um tragetória para sair de lá, já que a origem da árvore já é um EmptyState.
57
* Pensamos em aumentar a área de influencia do robô inimigo (obstáculo) proporcionalmente a sua distância, o que nos daria uma garantia maior de não colidir.
58
* E conforme a bola se aproxima de um obstáculo a área de influencia dele deve ficar cada vez menor, para que possamos ser capazes de roubar a bola.