Path planning for unstructured environments in the IARA self-driving car

Abstract

We present a path planner for unstructured urban environments (PPUE) for the IARA autonomous car. PPUE receives an initial and final pose as inputs, as well as the maps of the environment. It employs a hybrid-state A* algorithm, which is a variant of the A* algorithm, to choose the best path between the initial and final pose. To decide which path is best, the algorithm uses two combined heuristics to estimate the cost of the current pose for the final pose: a holonomic, which considers map obstacles while ignoring vehicle motion limitations, and a nonholonomic heuristic, which ignores obstacles but considers the vehicle's movement limitations. Once the path is found, it undergoes an optimization using Conjugated Gradient to make the path smoother and more comfortable for the passenger. Different from previous works, the PPUE uses: (i) an obstacle distance grid-map, instead of an occupancy grid-map, for representing the environment; and (ii) a more accurate but simple collision model for the car. We examined the performance of the PPUE experimentally in simulations in the parking lot of the UFES main campus to evaluate the execution time, the number of nodes expanded by the A* search, and the path length found by the path planner. We also compared the use of a combination of the holonomic and nonholonomic heuristics with the Euclidean distance heuristic to assess the benefits of using them. In additional simulations, we compared the number of nodes expanded by A* using each of the heuristics mentioned separately, plus the combination of the nonholonomic and holonomic heuristics, resulting in four situations that were evaluated in a maze scenario. We also verified how the algorithm execution time is affected when using different types of open list. Finally, we carried out real-world experiments in the UFES parking lot. Our results show that PPUE computes smooth and safe paths, which follow the kinematic constraints of the vehicle, fast enough for suitable real-world operation.