Local Path Planning Algorithm for Autonomous Vehicle Based on Multi-objective Trajectory Optimization in State Lattice

The paper presents an algorithm for constructing a local path for a vehicle with nonholonomic kinematics of an automobile type. A local path is a sequence of transitions in the graph of possible maneuvers that minimizes a given cost function. The graph is constructed by duplicating along the global path pre-calculated in a curvilinear coordinate system set of kinematically feasible motion primitives. The use of pre-computed motion primitives significantly reduces the time of graph construction. The weight of each maneuver - the edge of the transition graph - is calculated as a weighted sum of costs based on several criteria. The specified cost function minimizes maneuvering and maintains a safe distance to static obstacles. The information about obstacles is extracted from an occupancy grid map. Dijkstra`s algorithm is used to search a path in the weighted directed graph. The algorithm was tested on a dataset containing real road scenes. Each scene represents a given global path and a static environment model where a safe local path must be found. Local path search is performed in real-time. Experiments have shown that safe local paths have been found in all scenes where it was physically possible. At the same time, the obtained local paths were on average only on 1:3% longer than the given global paths which demonstrate the high applicability of the proposed algorithm.