# Progress in Construction Robot Path-Planning Algorithms: Review
## 3 Global Path-Planning Algorithms
### Dijkstra  
The Dijkstra algorithm is a graph-based data structure algorithm primarily used to solve the shortest path problem in maps. It was proposed by Dutch computer scientist [PERSON] in 1959. The algorithm works by progressively expanding the node with the known shortest path. Through this process, it finds the shortest path from the starting node to all other nodes. In large-scale construction, the Dijkstra algorithm can assist construction robots in obtaining the shortest path from one construction point to another. For example, it can help mobile concrete robots quickly distribute concrete to various target points during large-scale construction projects.  
The Dijkstra algorithm often faces challenges in dynamic environments, primarily due to low efficiency, high computational resource consumption, and the inability to handle negative weight edges. To address these issues, experts have proposed numerous improvements.  
[PERSON] designed an optimal collision-free offline Dijkstra algorithm. In this approach, robots follow the algorithm to generate the shortest path from the starting point to the destination. At each node, the robot stops to test if there is an obstacle between the current node and the next node. If an obstacle is detected, the robot excludes the corresponding node and updates its directed graph. This process repeats until the target point is reached. The improved Dijkstra algorithm can effectively solve the optimal path-planning problem in environments with obstacles [28].  
[PERSON] proposed a method to reduce computational effort by considering the distance to the destination while calculating the shortest distance from a node to the starting point. This causes the exploration process to generally progress towards the destination. By comparing the computational complexity of traditional algorithms, the effectiveness of the improved method was proven, reducing the complexity of the Dijkstra algorithm [29].  
[PERSON] solved the problem of planning a collision-free and approximately optimal path for mobile robots in large-scale and densely obstacle-filled environments. This was achieved by combining the Dijkstra algorithm with four-neighborhood search, eight-neighborhood search, and reverse search algorithms [30].  
[PERSON] proposed a hybrid path-planning method based on the artificial bee colony algorithm and the Dijkstra algorithm. This method combines the advantages of offline global path optimization and online local path planning, successfully reducing the time for robot path planning while ensuring path quality [31].  
[PERSON] introduced an inertia weight to control the global and local search capabilities of the particle swarm, optimizing the path-planning problem. This method significantly enhanced various capabilities of the Dijkstra algorithm, such as obstacle avoidance, path-planning speed, and computation time [32].  
A system combining the Dijkstra algorithm and the Dynamic Window Approach (DWA) was proposed, enabling intelligent vehicle robots to navigate autonomously and avoid obstacles in unknown indoor environments [33].  
An improved Dijkstra algorithm was proposed for the path-planning of track-based logistics robots. This algorithm introduced a real-time node occupancy factor into the path weight function and established a time window model within the algorithm to improve computational efficiency. Additionally, the improved algorithm can solve the problem of robot conflicts in multi-robot systems [34].