Parallel Best-First Heuristic Search applied to Cooperative Planning for Automated Vehicles

Abstract

This paper studies the utilization of multi-core processors for path planning algorithms. A* best-first heuristic search algorithm is used for path finding, where the state space is a search tree that is built from discrete trajectory paths (motion primitives). Particularity of the given search problem is computationally expensive expansion step and large branching factor of the tree. Most recent parallelization techniques has been evaluated to identify which one fits best for the existing planning problem (considering significant differences between A* parallelization approaches). Finally, two schemes were chosen to be tested in real life scenarios - PA* and PRA* (HDA*). These algorithms represent two basic strategies of the best-first search parallelization that are shared OPEN list (PA*) and private OPEN lists (PRA*, HDA*). Both approaches has been tested for execution time and memory usage, and eventually compared head to head. Experiments were conducted for different road scenarios with various complexity. The main goal of this work was to show that multi-core machines can be successfully applied to path finding (planning) problems for automated vehicles. The thesis was funded and supported by Deutsches Zentrum für Luft- und Raumfahrt (DLR), Institut für Verkehrssystemtechnik. All implemented algorithms were embedded into DLR’s simulation environment where real car models and road scenarios are being tested.