Saltar para: Post [1], Pesquisa e Arquivos [2]

Mapas de navegabilidade para condução autónoma no Campus UA

Mapas de navegabilidade para condução autónoma no Campus UA

Planeamento de Caminhos

Após a obtenção da informação do espaço do campus da Universidade de Aveiro (obstáculos positivos e negativos), a mesma tem de ser analisada e avaliada para ser determinado o melhor caminho para o robô percorrer.

Entre os variados métodos e técnicas existendes, só alguns resolvem situações genéricas. Sendo necessário que o espaço de trabalho seja de duas dimensões e que os objetos sejam considerados polígonos.

Irão ser abordados principalmente 3 métodos:

  1. Decomposição em células
  2. Mapa de estradas
  3. Campos de potencial

 

Método de Decomposição em Células

Consiste na divisão do espaço livre à volta do robô em regiões simples, chamadas de células, de forma que um caminho entre quaisquer dois pontos na mesma célula possa ser facilmente obtido.

Como já foi referido os obstáculos são sempre considerados corpos 2D. Será necessario construir um grafo representante das células, para mostrar os caminhos possiveis.

Este método ainda pode ser dividido em dois sub-grupos:

  1. Métodos exatos de decomposição em células, que decompôem o espaço livre num conjunto de células cuja união cobre exatamente todo os espaço livre.

MetodoExactoDC.PNG

  1. Métodos aproximados de decomposição em células, que dividem o espaço livre num conjunto de células de forma predefinida cuja união pode não cobrir inteiramente o espaço livre.

MetodoAproxDC.PNG

Método de mapa de estradas (Roadmap)

Consiste em capturar a conetividade do espaço livre, numa rede unidimensional de curvas, denominado de “roadmap”. A rede de curvas obtida representa a conetividade entre espaços livres do meio em análise.

Após a sua construção esta é definida como um conjunto de percursos estandardizados, reduzindo o planeamento de trajetórias à ligação entre pontos de interesse. Se construida, a trajetória é definida em três subcaminhos:

  • O subcaminho a ligar o ponto inicial ao mapa de estradas
  • O subcaminho do próprio mapa de estradas
  • O subcaminho que liga o mapa de estradas ao ponto final

 

As técnicas usadas para o processamento de busca para este método são:

  1. Grafo de visibilidade, que é composto por todos os segmentos de reta que unem os vertices de obstáculos e os pontos de partida e chegada, sem atravessar nenhum deles.

     

    A escolha do caminho é feita pelo percurso mais curto, ou seja, com menor segmentos e depois é realizado processamento extra para afastar as trajetórias dos obstáculos. Usualmente é realizada uma ampliação dos obstáculos antes da obtenção final do grafo, que poupa no processamento extra no final,em que resulta no afastamento das trajetórias das esquinas dos mesmos.

GrafoVisibilidadeRM.PNG

  1. Diagrama de Voronoi, representa a interseção dos meios-espaços de todos os pontos que delimitam os obstáculos e o meio, originando uma divisão em células, denominadas de células de voronoi. Os segmentos de reta do diagrama representam todos os pontos, num plano, que estejam equidistantes a dois pontos delimitadores dos obstáculos ou do meio.

     

    Este método apresenta desvantagens sendo as mais relevantes a dificuldade de processar a informação para problemas de dimensões de maior escala ou quando os obstáculos não são considerados polígonos. Ainda se pode tornar num sistema instável, dado que uma pequena mudança na configuração dos obstáculos pode levar a uma grande mudança no diagrama final.

DiagramaVoronoiRM.PNG

Método dos Campos de Potencial

O método dos campos de pontencial consiste numa função definida sobre a região livre do espaço, onde o robô é repelido pelos obstáculos e atraído pelo objetivo.

Primeiro é necessario discretizar o espaço numa grelha de valores e depois pesquisar um caminho sobre a mesma usando um campo potencial.

CamposPotencial.PNG

Este método tem a vantagem de ser de fácil visualização e implementação mas também bastante eficiente.

A desvantagem deste método é que como é baseado em um algoritmo de pesquisa heurístico (método rápido de otimização), pode levar o robô a um ponto que seja um mínimo local da função potencial e não o mínimo global (objetivo final). Neste caso o robô é repelido pelos obstáculos com uma força resultante igual à força atrativa do destino.

MinimoLocalCP.PNG

 

 

 

Mais sobre mim

Subscrever por e-mail

A subscrição é anónima e gera, no máximo, um e-mail por dia.

Arquivo

  1. 2015
  2. J
  3. F
  4. M
  5. A
  6. M
  7. J
  8. J
  9. A
  10. S
  11. O
  12. N
  13. D