Robotic Indoor Path Planning Using Dijkstra's Algorithm with Multi-Layer Dictionaries
- 1 December 2015
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2015 2nd International Conference on Information Science and Security (ICISS)
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- Topological Indoor Localization and Navigation for Autonomous Mobile RobotIEEE Transactions on Automation Science and Engineering, 2014
- Research on path planning algorithm of indoor mobile robotPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Path Planning of an Indoor Mobile Robot Navigated by InfraredPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- An improved Dijkstra’s shortest path algorithm for sparse networkApplied Mathematics and Computation, 2007