Simulation of path optimisation algorithms
Loading...
Date
2017-06
Authors
Sim Choon Yee
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The main concern is to find and calculate the shortest distance from one node to another in the most efficient way. 3 algorithms (A* algorithm, Dijkstra algorithm and Greedy algorithm) and 2 concepts (Bidirectional Searching and Replanning) are explored and simulated. The benchmark for comparing the effectiveness of each algorithm are thoroughly defined with the intention of finding the best algorithm in the designed environment. All Matlab simulations are done in a 2D, 300x300 image pixel with only a fixed start and an end node. For the Bidirectional Searching method, it is set to stop when the searching area from starting point and the searching area of end point are met. Next, for the purposes of simulating using Replanning concept, the original map is introduced with 4 walls and 39 whitespaces. A total of 4 experiments are done to compare whether the 2 concepts combined do actually improve the searching performance of the 3 algorithms, namely, Unidirectional Searching without Replanning, Unidirectional Searching with Replanning, Bidirectional Searching without Replanning and Bidirectional Searching with Replanning. Each result of the simulations is included with a discussion of the similarities and difference of the results of each algorithm. In summary, the total Nodes Searched of Bidirectional Searching with Replanning has an overall reduction (28%, 37% and 51%) when compared to total Nodes Searched of Bidirectional Searching without Replanning. In addition, the algorithm total time is shown to have decrement of 73.69%, 64% and 4.62% based on the second map simulations. Likewise, when comparing between Bidirectional Searching with Replanning and Unidirectional Searching with Replanning, a decrease of 41.08%, 25.57% and 14.41% on algorithm total time can be seen. Thus, in this final year project, the optimum algorithm to use is A* algorithm with Bidirectional Searching method and Replanning method included during the searching process. The complete code is included in Appendix for reproducibility purposes.