Robotic Indoor Path Planning Using Dijkstra's Algorithm with Multi-Layer Dictionaries

摘要

Dijkstra's algorithm is a classic algorithm for finding the shortest path between two points due to its optimisation capability. The adjacency matrix is the naive storage structure of the algorithm. This storage structure has limited the use of the algorithm as it expands large storage space. A multi-layer dictionary is proposed in this work to enhance the storage structure. Previously, the algorithm was used to optimise single parameter (such as distance, time and fuel) for movement between two places. The path computed using the classic Dijkstra's algorithm is the shortest; however, it may not be the most feasible. The algorithm needs to optimise other factors such as energy consumption and the degree of turns a robot need to take. Junction degree of difficulty function is introduced to further improve the output. It is defined as the degree of difficulty of the path between two points in an open environment. The experimental result shows that the proposed path planning method produced the most optimal path between two points when applied to a map of any indoor terrain.