2D Path Planning Based on Dijkstra’s Algorithm and Pseudo Priority Queues

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Grid-Based Path Planning Competition

This paper presents the application of the PPQ Dijkstra approach for solving 2D path planning problems. The approach is a Dijkstra process whose priority queue (PQ) is implemented through a Pseudo Priority Queue (PPQ) also known as Untidy PQ. The performance of the optimization process is dramatically improved by the application of the PPQ. This modification can be used for a family of problems. The path planning problem belongs to the family of feasible problems that can be solved by considering PPQ-Dijkstra approach. The solution provided by the PPQ-Dijkstra algorithm is optimal, i.e. it is identical to the solution obtained through the standard Dijkstra algorithm. The PPQ-Dijkstra algorithm can be also applied for higher dimensionality problems such as non-holonomic planning processes, e.g. involving configuration spaces of higher dimension.

10.1609/socs.v3i1.18255