Futebol de Robos F180 » Inteligência

Colocar resumo na tarefa sobre o funcionamento.

Encontrei [esta](https://www.geeksforgeeks.org/k-dimensional-tree/) referência muito boa do GeeksForGeeks.

A ideia é utilizar a subrotina de inserção da árvore, pois se construíssemos a KD-Tree (nesse caso, 2D-Tree) toda vez que formos buscar pelo nearest, teríamos uma complexidade maior até que a atual, o que não é interessante já que queremos otimizar o processo. Dado que sabemos montar, inserir e buscar na KD-Tree (depois discutimos como implementar as subrotinas no LabView), minha sugestão de algoritmo, em alto nível, é:

- inicializa a 2D-Tree ``2Dtree``
- insere ``starting_point``

No loop de expansão do ``RRT``, para cada nó aleatório ``random_node``, fazemos:

- busca pelo vizinho ``neighbour`` mais próximo de ``random_node`` na ``2DTree``, utilizando rotina de busca
- gera nó auxiliar ``candidate`` na direção de ``neighbour`` a um passo ``r`` (expansão do ``RRT``). Note que estamos usando r como passo espacial, uma sugestão futura é utilizar um passo de tempo pela lógica do perfil bang-bang.

- checa se ``candidate`` está dentro de algum obstáculo
- se não
- expande ``RRT`` colocando ``candidate`` no RRT como filho de ``neighbour``
- expande ``2DTree`` inserindo ``candidate`` a partir de ``neighbour`` (não é necessário inserir a partir da raíz da ``2DTree``, uma vez que esta insersão resultaria em inserir a partir do ``neighbour``), consoante lógica de inserção da kd-tree
- se sim, continua
- checa se ``candidate`` está a uma distância ``d`` do ``goal_point`` (isso também pode ser levemente otimizado comparando as somas dos quadrados das diferenças das coordenadas, em vez de as raízes quadradas disto, mas isso é superotimizar).
- se sim
- insere ``goal_point`` no RRT como filho de ``candidate`` e termina o processo

A ideia de utilizar os indices sempre como 2k e 2k+1, comum na construção de árvores binárias, foi abandonada pois necessitáriamos alocar muita memória desnecessária. Dessa maneira implementada n corremos risco nenhum de estouro de memória.

[este](https://forums.ni.com/t5/Example-Program-Drafts/Advanced-Data-Structures-in-LabVIEW/ta-p/3519662) link, tirado do submundo dos fóruns da NI, pode ajudar. Tem várias implementações abstraídas de árvore, fila, lista encadeada e grafos.

Dei uma olhada nas VIs que vem junto com essas implementações. Mas elas são bem complexas, porque mexem com o labview de uma forma que não estamos acostumados. Existe até um de shortest path, mas o tempo de execução me pareceu bem longo.
Talvez o ideal seja continuar usando nossos algoritmos já implementados porém mudar as estruturas para as dessa "biblioteca".

Nicolas Oliveira escreveu:

Dei uma olhada nas VIs que vem junto com essas implementações. Mas elas são bem complexas, porque mexem com o labview de uma forma que não estamos acostumados. Existe até um de shortest path, mas o tempo de execução me pareceu bem longo.
Talvez o ideal seja continuar usando nossos algoritmos já implementados porém mudar as estruturas para as dessa "biblioteca".

A ideia não é necessariamente usar essas VIs, mas usar as soluções de implementações delas em nossas soluções. São bibliotecas de desenvolvedores da NI, pelo que eu entendi.

Estou tendo problemas também para atualizar as variáveis globais.

Implementei as VIs para cálculo da distância a BoundingBox e para decidir através desse resultado se é essa subTree é promissora ou não.

A VI do nearest está pronta, porém estou tendo problemas nas variáveis globais do código. A VI é recursiva, porém elas só estão sendo atualizadas na primeira iteração. E estou com muita dificuldade em debbugar isso. Resolvendo isso, tecnicamente, a busca do nearest point pela KD-tree vai estar pronta.

Nicolas Oliveira escreveu:

A implementação do Nearest Neighbor está sendo feita utilizando este [link](https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf) como referência. Pseudo código do NN:


Onde uma da principais vantagens é o cálculo da BoundingBox (BB), de acordo com o desenho abaixo. Isso garante que sub-árvores irrelevantes não sejam visitadas.


Para o cálculo da BB foram implementadas as VIs de findMin e findMax, para achar os nós com as menores ou maiores coordenadas, respectivamente, tanto em x ou em y. Assim temos as fronteiras da BB. Caso a distância do Target a BB seja maior do que a Best_dist não existirá nenhum ponto promissor nessa BB. O que preciso ajeitar é como calcular a distância um ponto a um retângulo.

Caso eu esteja em uma sub-árvore promissora eu visitarei o melhor lado primeiro, o que também dá mais velocidade ao algoritmo.

Massa. Diferente de outras árvores, não basta pesquisar pelo elemento na KD-Tree e inserir onde ele "estaria". Mesmo assim, como explica no link, o caso médio fica O(altura da árvore).

Próximos passos:

- revisão da implementação, testes com o debugger visual. Testar com várias configurações diferentes, observando a trajetória no debugger visual. Testar uma unidade dessas é meio complicado, não consegui pensar numa forma melhor.
- benchmarking da VI. Podemos medir o quão melhorou. Dado um frame de jogo, qual o tempo de execução da VI, tanto usando o performance tools (tempo de execução de um frame) do LabView quando usando um FPS counter que nos retorne a frequência obtida, rodando apenas a VI do cálculo da trajetória em loop com um frame dummy. Imagino que o FPS counter seja uma medida mais confiável pois há o bias do waypoint cache no cálculo do RRT, que estaria vazio em uma única execução.
- teste em jogo simulado (mesmo sem navegação ainda, dá pra visualizar a trajetória e medir se a performance está pesando em um jogo dinâmico)

E após a implementação da navegação:
- teste com 1 robô real
- teste com vários robôs reais

Lucas Germano escreveu:

Ontem eu e o Nicolas conseguimos debugar a KD-tree imprimindo vários valores num arquivo .txt...

Parabéns. Mas o que seriam esses "vários valores" ?? Qual era o problema ?

Valores impressos no .txt (usar como referência o pseudo código na tarefa):

• ditancia(Q,BB)
• best_dist
• NóAtual
• ditancia(Q,NóAtual)>best_dist
• best
• Q
• deepth

Percebemos que distancia de Q ao nóAtual era sempre um NaN e os problemas nos outros valores eram devidos a isso. O erro era q o Q (chamado de target na VI) não era uma variável global nem uma entrada, então n estava sendo passado seu valor certo para as chamadas recursivas.

O desempenho pode chegar muito perto.

De que tipo de recursão está falando.

Hoje não temos nenhuma preocupação de desempenho. Por exemplo, a depuração está habilitada em todas as VIs.
VIs críticas podem ser implementadas como Inline, evitando chamadas desnecessárias e troca de contexto.

Recursão normal, como a do código acima. Não conheço outros tipos rs. Já que li aqui que não podemos transformar VIs recursivas em inline ou subrotina. Acho q seria bom desligar o debug nessas VIs também para aumentar o desempenho.

O que ficou estranho pra mim foi que o desempenho caiu MUITO para algo que deveria melhorar.

Acho que começarmos a nos preocupar com o desempenho e fazer um levantamento das VIs críticas. Talvez diminuindo o consumo delas consigamos utilizar o RRT sem kD-tree por enquanto.

Eu escondi os controls para não mostrar no painel frontal e tentar melhorar o desempenho. Mas segundo esse [link](http://zone.ni.com/reference/en-XX/help/371361H-01/lvconcepts/vi_execution_speed/) mesmo escondidos os controls ainda vão sendo atualizados. Vou pesquisar mais formas de melhorar a performance de VIs recursivas.