Improving indoor path planning using Dijkstra's algorithm with multi-layer dictionary - Sani Iyal Abdulkadir
The need for optimal indoor path planners is an undoubtedly challenging due to the complexity of the problem. The solution to this problem should not only guarantee a collision-free path with minimum traveling distance but also provide an easy and feasible path with less rotational angles. The less rotational angles a user should take from source position to destination, the easier and feasible the path will be. Dijkstra algorithm is a classic algorithm for computing the shortest path between two points. Although Dijkstra's algorithm can provide the shortest path in term of length, the path provided may not necessarily be optimal in terms of easiness and feasibility for a mobile robot. The Global Positioning System (GPS) is the most commonly used space-based navigation system in path planning applications. However, GPS is not available in an indoor environment. Therefore, to solve the path planning problem in a static indoor environment, an Intelligent Graph (iGraph) of the indoor space using Radio-frequency identification (RFID) technology for locating and tracking is proposed. In addition, this study also proposes an Enhanced Dijkstra Algorithm Path Planner (EDAP), which uses multi-layer dictionary as a storage structure of the algorithm. The multi-layer dictionary provides an effective way of storing the indoor floor map and enables the system to acquire pertinent environmental information. An indoor navigational system has been developed in this study; it works in a structured indoor environment and requires prior information about the available paths. The path planning algorithm proposed optimizes distance and rotational turns of a mobile robot by considering the difficulty level of rotation at every junction in the environment, where each junction (i.e. intersection) connects two or more sub-paths. The experimental result shows that both traditional algorithm and EDAP produced shortest path in term of lengths. However EDAP paths are 50% more efficient in average in terms of total rotational angel. The algorithm can be apply to any static indoor environment to produce an optimal path from a start position to destination. It is concluded that the optimality of a mobile path depends on distance, easiness and feasibility of the path.