Efficient parallel path planning for autonomous cars in unstructured environments

Abstract

Planejar trajetórias em ambientes pouco estruturados, onde as condições de condução podem mudar repentinamente, constitui um grande desafio na navegação veicular autônoma. Este estudo visa investigar a possibilidade de realização de planejamento local de trajetórias em carros autônomos em ambientes não estruturados, em tempo real, garantindo completude. Inicialmente, foram analisados os últimos 10 anos do estado da arte em planejamento de trajetórias para carros autônomos operando nesse tipo de cenário, onde se constatou que muitas soluções de planejamento local utilizam heurísticas para aumentar o desempenho, mas o planejamento local em tempo real para cenários genéricos ainda é um problema em aberto. Neste contexto, este trabalho propõe uma nova abordagem capaz de encontrar caminhos viáveis e livres de colisão de forma eficiente, utilizando GPU. Demonstrou-se em teste que essa abordagem pode ser executada muito mais rapidamente do que algoritmos de referência e é capaz de encontrar um caminho local em menos de 50 ms em hardwares embarcados comuns, como o Jetson Orin Nano. Além disso, uma metodologia que utiliza múltiplos núcleos de CPU para executar um conjunto de algoritmos de planejamento local em paralelo foi proposta, para oferecer adaptabilidade e limitação de tempo de execução. Essa metodologia permite que o veículo selecione a melhor resposta para cenários, baseada em métricas de custo de execução de caminho, e permite que condições de contorno sejam tratadas com aumento mínimo da complexidade do sistema. Demonstrou-se em simulação que o conjunto paralelo de planejadores de trajetória é capaz de reduzir o custo médio de trajetória e tempo de execução médio através da utilização de planejadores locais especializados em cenários livres de colisão, trabalhando em conjunto com soluções genéricas. Finalmente, a navegação de caminhos globais em ambientes desconhecidos é tratada de forma eficiente utilizando um conjunto de algoritmos capazes de utilizar paralelismo de GPU para permitir que o conjunto de planejadores locais selecione automaticamente o melhor objetivo local, de forma que a cadeia de eventos de planejamento seja integrada, permitindo navegação contínua de longo prazo.

Abstract: Planning feasible trajectories in unstructured environments, where planning conditions can change abruptly, is a key challenge for autonomous ground vehicle navigation. This study aims to investigate the possibility of performing local planning for autonomous nonholonomic car-like vehicles in unstructured environments in real-time. Initially, the last 10 years representing the state-of-the-art in trajectory planning for autonomous cars driving in such scenarios were analyzed. In this context, many local planning solutions use heuristics to increase performance, but real-time local planning that can handle generic scenarios remains an open problem. In this context, a new local path planning approach is proposed to efficiently find a collision-free traversable path. Our testing shows that this approach can execute much faster than the reference and is capable of finding local paths in less than 50 ms in commodity embedded hardware, such as the Jetson Orin Nano. Moreover, a new methodology is proposed to offer graceful adaptation and strict execution time restrictions, executing an ensemble of preemptive local planning algorithms in parallel, and selecting the best scenario response based on path cost metrics. This allows the system to scale for boundary scenarios without necessarily increasing the local complexity, which can be achieved by adding new specialized local planners to the execution ensemble. Our simulation shows that adopting simple interpolation-based planners as specialized solutions for collision-free scenarios can reduce mean path cost and execution time. Furthermore, the ensemble uses parallelism to efficiently define local goals based on sparse global goals, which allows the planner to navigate unknown scenarios.