An Improved Dijkstra's Algorithm for Shortest Path Planning on 2D Grid Maps

摘要

Finding a shortest path from an arbitrarily selected initial position to a single goal position is very useful in some domains, such as in partially-known environments or control many robotics from different initial positions to move to the goal position. This paper analyzes a property on 2D eight-neighbor grid map and introduces an improved Dijkstra's algorithm (or IDA for short) to solve the problem. The property we analyzed ensures that each position only needs to calculate once to get the shortest distance to the goal position in IDA, so it can save much time with regard to the Dijkstra's algorithm. We test the performance of IDA on different sizes of 2D eight-neighbor gird maps, the results show that IDA can speed up the Dijkstra's algorithm by several orders of magnitude and more. Meanwhile, the results get by our algorithm can easily be used by the A* algorithm for partially-known environments as Path Adaptive A* and Tree Adaptive A* does.