Path planning that takes kinodynamic constraints into account is a crucial part of critical missions where autonomous vehicles must function independently without communication from an operator as this ensures that the vehicle will be able to follow the planned path. In this thesis, an algorithm is presented that can plan kinodynamically feasible paths through large scale continuous costmap environments for different constraints on the maximum allowed acceleration and jerk along the path. The algorithm begins by taking a small stochastic sample of the costmap, with a higher probability to keep more information from the cheaper, interesting areas of the map. This random sample is turned into a graph to which Dijkstra's algorithm is applied in order to obtain an initial guess of a path. Simulated annealing is then used to first smooth this initial guess to obey the kinodynamic constraints and then optimize the path with respect to cost while keeping the kinodynamics below the set limits. The majority of the simulated annealing iterations utilize a GPU to significantly reduce the computational time needed. The performance of the algorithm was evaluated by studying the paths generated from a large number of different start and end points in a complex continuous costmap with a high resolution of 2551×2216 pixels. To evaluate the robustness of the algorithm a large number of paths were generated, both with the same and with different start and end points, and the paths were inspected both visually, and the spread of the cost of the different paths was studied. It was concluded that the algorithm is able to generate paths of high quality for different limits on the allowed acceleration and jerk as well as achieving a low spread in cost when generating multiple paths between the same pair of points. The utilization of a GPU to improve computational performance proved successful as the GPU executed between 2.4 and 2.8 times more simulated annealing iterations in a given time compared to the CPU. This result hopefully ...


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    A GPU Implementation of Kinodynamic Path Planning in Large Continuous Costmap Environments : Using Dijkstra's Algorithm and Simulated Annealing


    Beteiligte:
    Larsson, Robin (Autor:in)

    Erscheinungsdatum :

    2023-01-01


    Medientyp :

    Hochschulschrift


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Costmap generation for use in planning a path through an environment

    BORGES PAULO / LOWE THOMAS / BANDYOPADHYAY TIRTHANKAR et al. | Europäisches Patentamt | 2023

    Freier Zugriff

    Kinodynamic Motion Planning Using Multi-Objective optimization

    Hart, Patrick / Knoll, Alois | IEEE | 2018



    Kinodynamic planning on constraint manifolds

    Bordalba Llaberia, Ricard / Porta Pleite, Josep Maria / Ros Giralt, Lluís | BASE | 2017

    Freier Zugriff

    Randomized kinodynamic planning for constrained systems

    Bordalba Llaberia, Ricard / Ros Giralt, Lluís / Porta Pleite, Josep Maria | BASE | 2018

    Freier Zugriff