Que algoritmo posso usar para construir um mapa de uma área explorada usando vários sensores de ultrassom?

Atualmente, os sensores de ultrassom são incrivelmente baratos, o que os torna uma escolha popular para muitas aplicações robóticas amadores, e eu gostaria de usar vários deles (digamos 10) em torno de um robô com um algoritmo para construir um mapa aproximado de uma área (como o robô o explora.) Não estou interessado em lidar com objetos em movimento nesse estágio, apenas em apontar objetos fixos, e usarei o GPS para localização. Percebo que outros componentes, como um scanner a laser, produziriam resultados muito mais precisos; no entanto, esses dispositivos também são astronomicamente mais caros.

Existe um algoritmo para esse fim?

Os algoritmos são essencialmente os mesmos, independentemente de quais sensores você está usando.

A verdadeira questão, na qual Chris abordou , é que o SLAM é difícil, mesmo com sensores muito bons.

Eu consideraria o GPS, a odometria da roda e uma IMU necessários para tentar bater com o ultrassom.

Se você está apenas procurando uma localização barata, recomendo dar uma olhada no slam baseado em visão / kinect também. As webcams e o kinect são muito baratos e o visual slam percorreu um longo caminho.

O kinect é praticamente o santo graal em termos de desempenho / custo do sensor, desde que você esteja dentro de casa.

Aqui está um exemplo de Kinect em um robô, além de muita matemática: http://www.youtube.com/watch?v=9Y4RQVpp-BY

Há toda uma área de literatura sobre esse tópico. A idéia mais geral é a de Localização e Mapeamento Simultâneo ( SLAM ), onde o robô deve construir um mapa ao mesmo tempo em que se localiza nesse mapa. Dependendo da precisão que você deseja que seus mapas sejam, você pode tentar um problema mais simples de criar um mapa de grade de ocupação , que pressupõe que você saiba a localização do robô.

Em geral, o GPS é bastante horrível, portanto, gerar uma grade de ocupação usando apenas o GPS como sua principal fonte de localização gerará mapas bastante confusos. No entanto, é possível integrar o GPS com aceleração, giroscópios, bússolas, câmeras, codificadores de roda e outros sensores para aproximar uma boa posição no mundo. Caso contrário, você precisará procurar um sistema SLAM simples para lidar com seus problemas.

Um bom pacote de código-fonte aberto g2o , para o chamado GraphSLAM, permite impor restrições como GPS e posição relativa às paredes. Pode não ser um ajuste exato, mas é bastante geral.

Para fazer o SLAM, você precisará de uma estimativa relativamente boa da posição.

Os robôs que usam scanners a laser podem se contentar apenas com a odometria, porque os dados são relativamente precisos e os dados do scanner podem ser usados ​​para ajudar a localizar nas etapas subsequentes.

Os sensores de ultrassom são muito confusos, geralmente têm uma distorção de direção de mais de 20 graus e qualquer coisa na direção geral será detectada.

Assim, eles são de ajuda insignificante para ajudar a localizar (exceto em ambientes muito estruturados).

Uma combinação de GPS / IMU pode ser usada para obter uma localização razoável. Obviamente, isso depende da escala do robô e, se estiver dentro de casa, o GPS pode não ser prático.

Se você conseguir controlar cuidadosamente a derrapagem da roda, a odometria da roda poderá melhorar significativamente a localização a curto prazo (embora seja preferido um método absoluto de localização). Sem uma referência absoluta (por exemplo, GPS), mesmo com um scanner a laser, você precisará resolver o problema de "fechar o loop".

Ambientes estruturados podem ter um requisito de menor precisão. Por exemplo, um ambiente de labirinto com paredes a distâncias regulares da grade quadrada, onde é simples detectar a presença de uma parede em cada direção de uma célula da grade.