Project

General

Profile

Atividade #1247

Determinar implementação do Path Planning

Added by Antonio de Souza Gomes Pereira about 1 year ago. Updated 7 months ago.

Status:
Fechada
Priority:
Normal
Target version:
-
Start date:
03/16/2020
Due date:
03/20/2020

Description

Esta tarefa tem por objetivo estudar e determinar as funções a serem implementadas do algoritmo de Path Planning escolhido.

enviroment.png (5.63 KB) Preview Antonio de Souza Gomes Pereira, 03/17/2020 12:39 PM

collision.png (6.05 KB) Preview Antonio de Souza Gomes Pereira, 03/20/2020 04:45 PM

backtrack.png (9.76 KB) Preview Antonio de Souza Gomes Pereira, 04/14/2020 03:26 AM

RRT.png (23 KB) Preview Antonio de Souza Gomes Pereira, 04/14/2020 03:26 AM

RRT-cmdragons (3).pdf (379 KB) Preview Antonio de Souza Gomes Pereira, 04/17/2020 09:04 PM

ERRT(1)BT.png (9.75 KB) Preview Antonio de Souza Gomes Pereira, 04/17/2020 09:04 PM

ERRT(1).png (15.8 KB) Preview Antonio de Souza Gomes Pereira, 04/17/2020 09:04 PM

ERRTpseudocode.png (54.5 KB) Preview Antonio de Souza Gomes Pereira, 04/17/2020 09:10 PM

Enviroment Collision Backtrack Rrt Errt(1)bt Errt(1) Errtpseudocode

History

#1 Updated by Nicolas Oliveira about 1 year ago

Quando for orientado a objeto?

#2 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Nicolas Oliveira escreveu:

Quando for orientado a objeto?

Sim, será a próxima tarefa depois de planejarmos como vamos fazer a implementação.

#3 Updated by Antonio de Souza Gomes Pereira about 1 year ago

A principio determinamos os atributos da enviroment, descrita no algoritmo. No código atual, ela compõe um conjunto de atributos do IA State:

Para fazer o cálculo, a princípio, só usamos o field length e field width, bem como apenas as coordenadas x e y dos robôs e da bola.
Há outros parâmetros sendo utilizados como o defense_stretch e o defense_radius, mas esses não são usados no RRT de fato, e sim em casos especiais, onde o algoritmo não é usado.

#4 Updated by Gabriel Borges da Conceição about 1 year ago

  • Assignee set to Antonio de Souza Gomes Pereira

#5 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Acabei de adicionar a primeira versão no github. Link(https://github.com/roboime/SSL_RRT)

O que foi feito até agora:

  • util.hpp
    Definindo classe Point e operações(soma, produto interno, subtração e módulo)

  • Environment
    Apenas o método distance da classe environment

  • Tree
    Classe Node

Não sei se essa foi a menor maneira de fazer essas coisas, estava pensando em fazer direto as operações de produto interno e soma direto na classe node.

#6 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Acabei de adicionar o sistema de colisão na classe ObstacleGrid, cujo atributo é um vetor de Pairs, com o primeiro elemento sendo o raio do obstáculo e o segundo sua posição.

Basicamente o que eu fiz foi calcular se existe intercessão entre o segmento de reta que liga os pontos A e B e a circunferência.

Podemos esrever um ponto da reta como: P = A + t(B - A), com t entre 0 e 1.
Para a circunferência P = C + r(cos a, sin a).
Igualando as duas, para ter colisão, na equação do segundo grau, delta >= 0 e as soluções devem estar entre 0 e 1.

#7 Updated by Gabriel Borges da Conceição about 1 year ago

A cada nova função criada, elabore um teste básico para garantir que foi feito corretamente. No RRT temos muitas funções, se deixar pra testar tudo quando estiver pronto, vai ficar mais difícil de identificar os possíveis erros.

#8 Updated by Gabriel Borges da Conceição about 1 year ago

  • Status changed from Não Iniciada to Em andamento

#9 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Acabei de adicionar a função extend como membro da classe Tree, ainda não está implementado a parte do ERRT. Estou tendo um pequeno problema com os números aleatórios do c++, falta resolver isso ainda, mas fora isso, as outras funções básicas já foram implementadas:

  • randomState()
  • extend()
  • distance()
  • colisão com a parede e obstáculos

#10 Updated by Nicolas Oliveira about 1 year ago

Antonio de Souza Gomes Pereira escreveu:

Acabei de adicionar a função extend como membro da classe Tree, ainda não está implementado a parte do ERRT. Estou tendo um pequeno problema com os números aleatórios do c++, falta resolver isso ainda, mas fora isso, as outras funções básicas já foram implementadas:

Está criando a semente pros números aleatórios? se n vai dar ruim

#11 Updated by Nicolas Oliveira about 1 year ago

Faz o RRT normal, mudar pra ERRT é relativamente simples depois, foi oq eu fiz.

Já adiantando aqui, o ideal é criar uma outra tarefa pra que agt possa utilizar algumas bibliotecas prontas úteis ao RRT. E aprender como inserir isso dentro da nossa dll. Assim poderíamos utilizar a biblioteca do k-nearest neighbors no nosso RRT. Pra isso é importante pensar bem nas estruturas de dados que vão ser utilizadas pra representar os nós e a árvore, pra que tudo seja compatível.

#12 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Nicolas Oliveira escreveu:

Faz o RRT normal, mudar pra ERRT é relativamente simples depois, foi oq eu fiz.

Já adiantando aqui, o ideal é criar uma outra tarefa pra que agt possa utilizar algumas bibliotecas prontas úteis ao RRT. E aprender como inserir isso dentro da nossa dll. Assim poderíamos utilizar a biblioteca do k-nearest neighbors no nosso RRT. Pra isso é importante pensar bem nas estruturas de dados que vão ser utilizadas pra representar os nós e a árvore, pra que tudo seja compatível.

Estava discutindo com a Carla isso, chegamos a conclusão de usar a biblioteca FLANN(https://github.com/mariusmuja/flann) que já é bem famosa para calcular os KNN e tem várias features úteis, como possuir vários parâmetros de busca e usar multithreading(não sei se vai ser útil no nosso caso, pois a dimensão é só 2). No caso da instalação, a biblioteca foi instalada no pc mesmo, não precisando de nenhum arquivo no diretório do código, mas não sei como vai se comportar como dll.

#13 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Acabei de fazer a primeira implementação usando a biblioteca FLANN. A instalação é feita no pc mesmo e há intruções na página do github(https://github.com/mariusmuja/flann), um único problema que eu tive foi a ausência da biblioteca LZ4(https://github.com/lz4/lz4), que é requerida e não vem junto. Além disso, para compilar, é necessário botar a flag -llz4.

Basicamente o que eu fiz foi colocar os métodos de inserir e pesquisar na kdtree, tive que pesquisar alguns exemplos pois não está muito bem explicitado a implementação na documentação da biblioteca(https://usermanual.wiki/Document/flannmanual184.1650808969/).

Porém houve o problema que só havia como inserir o vetor das coordenadas do ponto e não os outros atributos da classe Node(como o _parent, por exemplo), assim o resultado do knnSearch era só um vetor e não tinha como saber diretamente os outros atributos.
Procurei na internet e achei uma solução de criar um hash map dos nodes, com as coordenadas como key, assim mantemos a kdtree com as coordenadas e o hash map com os objetos em si. Não sei se é uma boa solução, mas foi o utilizado em outras implementações do FLANN.

#14 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Acabei de debugar e implementar o backtrack. Para fazer ele, basta acessar o ponteiro parent, atributo da classe Node que aponta para o vértice que está conectado na árvore, em um for, gerando no final uma lista que começa no objetivo e termina no inicio.

Fiz alguns testes, gerando os pontos em um arquivo e exibindo eles em um gráfico.

Inicio = (0,0)
Fim = (100,100)
Obstáculo = (50,50). Raio 20
probGoal = 0.8
step = 8cm

Agora fazendo o backtrack, usando os mesmos parâmetros:

#15 Updated by Antonio de Souza Gomes Pereira about 1 year ago

Para fazer a implementação do ERRT, segui o seguinte pseudocódigo, presente em um artigo da tarefa da primeira implementação (link em anexo na tarefa):

Para a primeira árvore gerada, na qual não possui um waypointCache, usei a soma GoalProb + WayPointProb como probabilidade para usar o objetivo como target, mas não sei se isso é o ideal, como é só na primeira iteração que ocorre esse problema acho que não há tanto problema em usar só o GoalProb.

O artigo fala sobre gerar um número constante de pontos(N = 500) e usar um número constante de waypoints(n = 50), ao invés de prosseguir o cálculo até achar o primeiro caminho até o objetivo.

Para gerar o caminho, usei os mesmos dados que estão acima e as probabilidades recomendadas pelo artigo(ProbGoal = 0.1, ProbWayPoint = 0.6)

Após o backtrack:

#16 Updated by Antonio de Souza Gomes Pereira 7 months ago

  • Status changed from Em andamento to Fechada

Also available in: Atom PDF

Go to top
Add picture from clipboard (Maximum size: 500 MB)