2D path planning based on Dijkstra`s algorithm and pseudo priority queues

Guivant J; Seton B; Whitty M, 2012, '2D path planning based on Dijkstra`s algorithm and pseudo priority queues', Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012, pp. 206 -, Canada



Abstract / Description

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 PPQDijkstra 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. Copyright © 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Page generated: Sunday 20 June, 2021