Pergunta

Estou procurando um algoritmo e não tenho idéia de por onde começar!

Estou tentando ir do ponto A ao ponto B em um gráfico cartesiano. O movimento é restrito ao de um carro RC: para trás, para a frente, para a frente e para a frente (o raio de torneamento constante; o carro está girando completamente, ou não está girando).

Como eu construiria um algoritmo que leva o seguinte:

turningRadius, initialPosition, initialOrientation, finalPosition

E produz um conjunto ordenado de etapas para chegar à Finalposition?

Observe que não me importo com qual é a orientação final.

Obrigado!

EDITAR: Observe que isso não está em um gráfico com nós discretos, mas um sistema de coordenadas contínuas

Foi útil?

Solução

A maneira como o seu problema é descrito, o algoritmo é direto e requer apenas duas etapas simples: 1) Avance enquanto gira (esquerda ou direita) até que o carro seja apontado diretamente para B, 2) Avance para frente até chegar a B. feito.

A única parte relativamente complicada é o primeiro passo. Se B está à esquerda do eixo longitudinal do carro em sua posição inicial, a abordagem natural seria começar girando deixei. Isso funcionará, a menos que o ponto B esteja dentro da trajetória circular produzida por uma curva à esquerda (de raio turningRadius). Neste último caso, o carro será executado em círculos, mas nunca será capaz de mirar diretamente para B. nesses casos, a estratégia adequada é realmente começar com um certo Vire e continue girando até mirar o carro para B.

Portanto, se você não tiver nenhum requisito de otimização para sua trajetória, o algoritmo mais simples para o primeiro passo seria se afastar incondicionalmente " certo Se B está no deixei do eixo longitudinal do carro e vire deixei Se B está no certo. Continue girando até que o carro seja direcionado diretamente para B. Isso soa um pouco antinatural, mas sempre funciona, ou seja, você sempre será capaz de apontar o carro.

Se você cuida de uma trajetória mais ideal (mais curta), precisa analisar a localização de B em relação à posição/orientação inicial do carro ("está b dentro do círculo de giro ou fora?") E escolha a direção da direção da a primeira vez de acordo.

Outras dicas

Em geral, isso não é um problema fácil. Ele se enquadra na categoria de "planejamento sob restrições diferenciais". Os últimos três capítulos do livro de Lavalle (disponíveis online aqui) lidar com isso. Em particular, observe a seção 14.4.2., Que lida com um "carro de Dubins", que é como o seu carro RC, exceto que ele não se move para trás.

Pesquise também "Planejamento de Caminho de Carros de Dubins". Você encontrará muitos papéis.

Você já tentou um* (A-Star)? Também é bom quando você fornece um mapa de terreno. Você pode atribuir pesos a diferentes partes do terreno, o que resultará em um caminho diferente. Acredito que o algoritmo por padrão não fornece direções diagonais, mas você pode adicioná -lo com bastante facilidade.

Além disso, por padrão, não é um acordo com "girar", mas o A-Star dará o caminho completo. O que você poderia fazer é calcular o raio de curva com base em 2 pontos. A posição atual e a próxima posição calculada, ou a última posição e a posição atual. Você pode adicionar ou subtrair a direção voltada para a alteração no ângulo. Você pode precisar ajustar isso alguns.

Parece um projeto interessante e divertido! Para obter uma recomendação específica de algoritmo, você provavelmente deve fornecer mais detalhes ... como se você estivesse esperando literalmente executar isso em algum tipo de controlador incorporado conectado a um carro RC? Ou o algoritmo deve ser executado em uma estação de trabalho e controlar o carro remotamente? (Ou isso é puramente um exercício abstrato e não há carro ... awwww.)

Minha recomendação genérica para controlar por onde começar seria Construindo solucionadores de problemas, que é uma ótima introdução ao mundo das técnicas de solução de problemas "AI". Pode ser um pouco datado hoje em dia ... mas espere, o que estou dizendo! Provavelmente não. :-)

Ok, devo explicar esse último comentário: a maioria "moderna" técnicas de IA que eu já vi na prática realmente datam de idéias muitos anos ... eles acabaram de se tornar prático Agora, graças ao avanço implacável da lei de Moore. Portanto, um livro escrito em 1993 ainda está discutindo técnicas razoavelmente de ponta, pelo que vi pessoalmente. Eu adoraria ser apontado para um contra-exemplo!

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top