New algorithm for digital way-finding map

International Conference on Informatics, Engineering, Science and Technology

计算机科学;工业技术

Aria, M.^1

Electrical Engineering Department, Faculty of Engineering and Computer Science, Universitas Komputer Indonesia, Jalan Dipati Ukur No 112-116, Bandung, Indonesia^1

关键词: Adjacency matrices;    Bi-directional search;    Breadth-first search;    Computation time;    Memory algorithms;    Memory resources;    Path-finding algorithms;    Standard algorithms;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/407/1/012074/pdf
DOI  :  10.1088/1757-899X/407/1/012074

来源: IOP

【 摘 要 】

The purpose of this research was to develop a new algorithm to find the shortest pathfinding that can be implemented on a digital way-finding map. The standard algorithm used for pathfinding is Dijkstra and A∗. But for a large search space, the A∗ and Dijkstra need a large amount of CPU and memory resources. Whereas pathfinding algorithm is usually embedded in devices with limited memory. So, we make the algorithm which requires less memory. In order to make a less memory algorithm, we modify the Breadth First Search (BFS) and Bidirectional Search (BS) algorithm and use the cost graph and modify adjacency matrix. We have tried to reduce the runtime of our algorithm using the modify adjacenvy matrix. The proposed algorithm is then tested for path finding at the institution that has several buildings with many floors where staircase position is not uniform on each floor. The test results were then compared with Djikstra, A∗, IDA∗, and HPA∗. The experiment results showed that our algorithm is faster than the A∗, IDA∗ and Djikstra algorithm. This is because the algorithm that we designed only need to make modify adjacenvy matrix once, so it can reduce the computation time. However, for cases involving multiple floors, our algorithm is not faster than HPA ∗, but approached. From the test results can be concluded that our algorithm can be implemented in the case of searching the route on buildings that have many floors.