Abstract: This article explores the pathfinding problem of freight robots in

automated warehouses and compares the performance of the Dijkstra

algorithm and the A* algorithm in this regard. Several small warehouses were

simulated using matrixs, and the two algorithms were compared in terms of

running time, node expansion order, memory usage, and path smoothness.

Through experiments, it was found that the A* algorithm outperforms the

Dijkstra algorithm in the question. However, when applied to extremely large

and complex warehouses, it is difficult to find the optimal heuristic, which

becomes the main factor limiting the performance of the A* algorithm. In the

future, more indicators should be added or efforts should be made to let robots

choose algorithms based on actual situations.

Key words: Dijkstra algorithm, A* algorithm, pathfinding problem, automated

warehouses

1. Introduction

With the development of the modern society, the requirement of building smart

environment like automated warehouses is growing. At the same time, the use

of robotics in all facets of modern life is growing [1]. Therefore, introducing

automatic freight robots in warehouses is a feasible solution to achieve

automated warehouses. As Can Özbaran et al. said that Intelligent mobile

warehouse robots are quickly emerging as a vital component of systems for

storage and retrieval [7]. But how to enable freight robots to find the most

suitable path in the warehouse, so as to transport goods quickly and efficiently,

has become a hot and important issue. In fact, in this question, the key is path

planning. Path planning is the pathfinding issue that enables autonomous robot

obstacle avoidance [2]. The article will explore the use of path planning

algorithms in the field of artificial intelligence to solve the pathfinding problem

for freight robots in warehouses.

2. Methodology

2.1 Literature review and proposed solution

Path planning algorithms are applied to many scenarios of freight robots, for

example, the automated logistics vehicles in Wuhan use path planning

algorithms to find their way; Cainiao, a large logistics provider, uses path

planning algorithms to guide automated transport vehicles in warehouses.

Generally speaking, flexibility, local optimum, and computing complexity

present the biggest challenges for the robot-path-planning problem [5]. There

are many ways for path planning algorithms in the field of artificial intelligence.

For example, Vu Quang Huy et al. believe that genetic algorithms, ant colony,

and firefly algorithms can also be applied to pathfinding problems in this field

[9], Yu Song et al. proposed that the Dijkstra algorithm can be used to solve this

problem [2]. Chunyu Ju et al. believe that A* algorithm and Fast Random Tree

(RRT) are more effective in this problem [3]. For the Dijkstra algorithm, using a

single node as the "source" node, the algorithm determines the shortest path

between two nodes. It then finds the shortest paths from the source to every

other node in the graph, creating a shortest path tree [4]. In order to solve the

single-source shortest path issue optimally, it employs a greedy method [8].

For A* algorithm, Yonlin Huang and Shijie Guo believe that it will be used as the

parent node in path planning first, and the planning algorithm will then find the

next ideal node as the child node. After that, it will be used as the parent node

to identify the next child node, and so on, to define the robot's ultimate walking

path [6].

At the same time, Yoppy Sazaki thinks that A* algorithm is a fast search

algorithm [10].

This article believes that Dijkstra's algorithm or A * algorithm is a feasible

method for solving the routing problem of freight robots in automated

warehouses.

2.2 Experiment design

In the experiment, I use Python to run code on Pycharm and use the networkx

library to load the algorithm of A* search and Dijkstra. Also, the Pytorch library

are used to demonstrate the result likes line graph, bar graph and map. In the

experiment, by creating several small warehouses of different sizes using

random functions and the warehouses will be represented by matrices. In the

warehouses, also added some dead ends and random obstacles to maximize

the restoration of the warehouse situation in reality. Then the experience will

compare the A* algorithm in heuristic algorithms with the Dijkstra algorithm in

greedy algorithms based on node expansion, runtime, memory usage and

smoothness. Smoothness is usually measured by the angle change or

curvature between adjacent points in the path. Simply put, the higher the

smoothness of the path, the smoother the path and the fewer turns during

driving. The lower the smoothness, the more turns the path has. At the same

time, in order to minimize errors caused by factors such as memory allocation,

multiple experiments were conducted for each item in the experiment to

calculate the average.

2.3 Evaluation of Solutions

The results of the experiment are demonstrated in the following:

With figure 3 (left is the expand nodes of A* search, right is Dijkstra), it is clear

that the node expansion of the A* algorithm is smaller than that of the Dijkstra

algorithm, which means that the A* algorithm can better adapt to complex

warehouse environments compared to the Dijkstra algorithm and the node

expansion order of A* algorithm will have a more directional sense, tending to

search towards the target direction, while Dijkstra algorithm will relatively evenly

expand the entire graph.

In figure 4, it is obvious that as the size of the warehouse increases, the running

time of these two algorithms also increases. However, the increase in time

required for the A* algorithm is not significant, while the increase in time

required for the Dijkstra algorithm is significant, and the Dijkstra algorithm

requires much more time than the A* algorithm.

For figure 5, it is clear that the memory size used for A* search is much

smaller than that of Dijkstra's algorithm, and it does not change significantly

with the expansion of the warehouse size.

For Figure 6, we found that the path turning numbers of Dijkstra's algorithm are

smaller than those of A * algorithm, and this is more pronounced with the

increase of warehouse size. This means that in this case, Dijkstra's algorithm

has better path smoothness than A * algorithm.

Overall, in the metrics of this experiment (running time, memory usage, node

expansion order), A* search outperforms the Dijkstra algorithm. In terms of path

smoothness, Dijkstra's algorithm outperforms the A * search algorithm. Under

appropriate heuristics, the A* search algorithm can enable transportation robots

in the warehouse to complete delivery tasks at a lower cost and in a shorter

time, and the advantages of the A* search algorithm will become more apparent

as the warehouse size expands. Hence, A* search algorithm can become the

solution of this problem.

3. Discussion

This experiment objectively compared the performance of the A* search

algorithm in heuristic algorithms and the Dijkstra algorithm in greedy algorithms

in guiding freight robots to find paths in automated warehouses through

theoretical and technical means, in terms of running time, memory usage, node

expansion order, and path smoothness. However, this experiment still has

certain shortcomings in certain aspects. Firstly, in terms of warehouse size, due

to limitations such as equipment, computing resources, and costs, this

experiment can only simulate some small two-dimensional warehouses, the

experimental results may have certain deviations for large and structurally

complex warehouses. Secondly, the number of indicators used in this

experiment is still limited and has not taken into account more real-world factors,

such as friction, the impact of dynamic friction coefficient on freight robots, and

the influence of other external factors such as memory allocation. Furthermore,

the heuristic functions of the A * algorithm in this experiment are all optimal, but

in reality, it is difficult to find a heuristic function that is completely suitable for

the warehouse situation. Therefore, the performance of the A * algorithm in this

experiment may be affected by its performance in a real warehouse.

4. Conclusion

The purpose of this study is to determine which algorithm is more suitable for

path planning of freight robots in automated warehouses by comparing the A *

search algorithm with the Dijkstra algorithm. By simulating and reproducing the

situation of logistics warehouses in reality as much as possible and comparing

four indicators, this study found that in small-scale warehouses, the

performance of the A * algorithm is generally better than that of the Dijkstra

algorithm, but for larger warehouses, the results may be biased. However, in

summary, this study still believes that the A * algorithm is an effective algorithm

for handling robot pathfinding problems in automated warehouses.

This study has contributed to the construction of an increasing number of

automated warehouses. Automated warehouses not only liberate more labor,

but also improve people's quality of life. Choosing appropriate algorithms can

help robots transport goods more efficiently and at a lower cost. In the future,

we will try to compare more indicators or let robots combine these two

algorithms to choose according to the situation.

Reference

[1] A. Figueras, J. L. De La Rosa, S. Esteva and X. Cufí, "Robot team in the

improvement of the neighborhood," 2018 IEEE International Smart Cities

Conference (ISC2), Kansas City, MO, USA, 2018, pp. 1-6, doi:

10.1109/ISC2.2018.8656874.

[2] Y. Song and P. Ma, "Research on Mobile Robot Path Planning Based on

Improved A-star Algorithm," 2021 International Conference on Electronic

Information Engineering and Computer Science (EIECS), Changchun, China,

2021, pp. 683-687, doi: 10.1109/EIECS53707.2021.9588002.

[3] C. Ju, Q. Luo and X. Yan, "Path Planning Using an Improved A-star

Algorithm," 2020 11th International Conference on Prognostics and System

Health Management (PHM-2020 Jinan), Jinan, China, 2020, pp. 23-26, doi:

10.1109/PHM-Jinan48558.2020.00012.

[4] A. Alyasin, E. I. Abbas and S. D. Hasan, "An Efficient Optimal Path Finding

for Mobile Robot Based on Dijkstra Method," 2019 4th Scientific International

Conference Najaf (SICN), Al-Najef, Iraq, 2019, pp. 11-14, doi:

10.1109/SICN47020.2019.9019345.

[5] Yanrong Hu and S. X. Yang, "A knowledge based genetic algorithm for path

planning of a mobile robot," IEEE International Conference on Robotics and

Automation, 2004. Proceedings. ICRA '04. 2004, New Orleans, LA, USA, 2004,

pp. 4350-4355 Vol.5, doi: 10.1109/ROBOT.2004.1302402.

[6] Y. Huang and S. Guo, "Path planning of mobile robots based on improved

A* algorithm," 2022 Asia Conference on Advanced Robotics, Automation, and

Control Engineering (ARACE), Qingdao, China, 2022, pp. 133-137, doi:

10.1109/ARACE56528.2022.00031.

[7] C. Özbaran, S. Dilibal and G. Sungur, "Mechatronic System Design of A

Smart Mobile Warehouse Robot for Automated Storage/Retrieval

Systems," 2020 Innovations in Intelligent Systems and Applications

Conference (ASYU), Istanbul, Turkey, 2020, pp. 1-6, doi:

10.1109/ASYU50717.2020.9259882.

[8] D. Verma, D. Messon, M. Rastogi and A. Singh, "Comparative Study Of

Various Approaches Of Dijkstra Algorithm," 2021 International Conference on

Computing, Communication, and Intelligent Systems (ICCCIS), Greater Noida,

India, 2021, pp. 328-336, doi: 10.1109/ICCCIS51004.2021.9397200.

[9] V. Q. Huy, N. T. Huy, P. B. Duong and N. T. Ngoc Hai, "Design and Develop

Optimal Pathfinding Algorithm Applied in Book Accessing and Returning for

Autonomous Mobile Robot in Library," 2022 6th International Conference on

Green Technology and Sustainable Development (GTSD), Nha Trang City,

Vietnam, 2022, pp. 350-354, doi: 10.1109/GTSD54989.2022.9989272.

[10] Y. Sazaki, A. Primanita and M. Syahroyni, "Pathfinding car racing game

using dynamic pathfinding algorithm and algorithm A*," 2017 3rd International

Conference on Wireless and Telematics (ICWT), Palembang, Indonesia, 2017,