Hybrid PSO-PWL-Dijkstra approach for path planning of non holonomic platforms in dense contexts

摘要

Planning is an essential capability for autonomous robots. Many applications impose a diversity of constraints and traversing costs in addition to the usually considered requirement of obstacle avoidance. In applications such as route planning, the use of dense properties is convenient as these describe the terrain and other aspects of the context of operation more rigorously and are usually the result of a concurrent mapping and learning process. Unfortunately, planning for a platform with more than three degrees of freedom can be computationally expensive, particularly if the application requires the platform to optimally deal with a thorough description of the terrain.The objective of this thesis is to develop and demonstrate an efficient path planning algorithm based on dynamic programming. The goal is to compute paths for ground vehicles with and without trailers, that minimise a specified cost-to-go while taking into account dynamic constraints of the vehicle and dense properties of the environment. The proposed approach utilises a Quadtree Piece-Wise Linear (QT-PWL) approximation to describe the environment in a low dimensional subspace and later uses a particle approach to introduce the dynamic constraints of the vehicle and to smooth the path in the full dimensional configuration space. This implies that the optimisation process can exploit the QT-PWL partition. Many usual contexts of operation of autonomous platforms have cluttered spaces and large regions where the dense properties are smooth; therefore, the QT-PWL partition is able to represent the context in a fraction of cells that would be needed by a homogeneous grid. The proposed methodology includes adaptations to both algorithms to achieve higher efficiency of the computational cost and optimality of the planned path.In order to demonstrate the capabilities of the algorithm, an idealized test case is presented and discussed. The case for a car and a tractor with multiple trailers is presented. A real path planning example is presented in addition to the synthetic experiments. Finally, the experiments and results are analysed and conclusions and directions for possible future work are presented.