Atividade #1247
FechadaDeterminar implementação do Path Planning
Descrição
Esta tarefa tem por objetivo estudar e determinar as funções a serem implementadas do algoritmo de Path Planning escolhido.
Arquivos
BT.png){kind=link}
.png){kind=link}
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
Nicolas Oliveira escreveu:
Quando for orientado a objeto?
Sim, será a próxima tarefa depois de planejarmos como vamos fazer a implementação.
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
- Arquivo enviroment.png enviroment.png adicionado
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.
Atualizado por Gabriel Borges da Conceição há mais de 4 anos
- Atribuído para ajustado para Antonio de Souza Gomes Pereira
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
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.
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
- Arquivo collision.png collision.png adicionado
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.
Atualizado por Gabriel Borges da Conceição há mais de 4 anos
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.
Atualizado por Gabriel Borges da Conceição há mais de 4 anos
- Situação alterado de Não Iniciada para Em andamento
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
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
Atualizado por Nicolas Oliveira há mais de 4 anos
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
Atualizado por Nicolas Oliveira há mais de 4 anos
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.
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
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.
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
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.
Atualizado por Antonio de Souza Gomes Pereira há mais de 4 anos
- Arquivo backtrack.png backtrack.png adicionado
- Arquivo RRT.png RRT.png adicionado
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:
Atualizado por Antonio de Souza Gomes Pereira há aproximadamente 4 anos
- Arquivo RRT-cmdragons (3).pdf RRT-cmdragons (3).pdf adicionado
- Arquivo ERRT(1)BT.png ERRT(1)BT.png adicionado
- Arquivo ERRT(1).png ERRT(1).png adicionado
- Arquivo ERRTpseudocode.png ERRTpseudocode.png adicionado
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:
Atualizado por Antonio de Souza Gomes Pereira há quase 4 anos
- Situação alterado de Em andamento para Fechada