# Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm
## 3 Improved Ant Colony Algorithm
### Path Optimization and Update  
The presence of unnecessary line segments and excessive bends in the explored path not only increases the overall length of the planned route but also requires the patrol robot to execute multiple turns and changes in direction during motion. This complexity is not conducive to fast and efficient navigation.  
The Total Triangle Pruning Algorithm is typically employed to optimize combinatorial problems, particularly in addressing specific graph or path issues. The core principle of this algorithm is to reduce the search space through pruning, thereby enhancing solving efficiency.  
1. Triangle relationship: This property utilizes the characteristics of triangles to determine that certain paths or combinations are redundant and can be pruned. For instance, if the cost from point A to point C exceeds the sum of the costs from A to B and from B to C, then the path from A to C can be eliminated.  
2. Pruning rules: Specific pruning rules are established to quickly identify which portions can be excluded during the search process. This is achieved by comparing the total cost of the current path with that of existing paths.  
3. Search algorithm: search strategies such as Depth-First Search (DFS) or Breadth-First Search (BFS) are combined with pruning techniques to systematically explore the effective solution space.  
4. Optimized results: by reducing unnecessary calculations through pruning, the algorithm increases the solving speed, ultimately yielding an optimized solution.  
The search rules of the ant colony algorithm on the grid map constrain the path search to directions that are multiples of \(\frac{\pi}{4}\), limiting the movement to either 1 or \(\sqrt{2}\) search steps, as illustrated by the solid black line in Figure 1. In this figure, the segment A-B-C-D, represented by the solid black line, indicates the most direct route found by the computational method, while the segments A-B (solid black line) and B-D (dashed blue line) depict the actual driving paths of the logistics robot. Consequently, the current approach has not yet identified the minimal distance path for the patrol robot. To address these issues, the triangle pruning method can effectively eliminate unnecessary turning points and line segments. The core concept involves connecting neighboring turning points of the initial path. If the connecting line does not intersect with any obstacles, the unnecessary turning points and segments between the two nodes are removed, and the path is updated accordingly.  
Let \(\varphi\) be the set of checkpoints, \(P=\{P_{1},P_{2},\ldots,P_{n}\}\) be the set of turning points in the path that requires optimization, R be the set of all points on the line connecting the turning point \(P_{i}\) of checkpoint \(\varphi_{i}\) to be checked, and T be the set of obstacles. The optimization process begins by adding the first turning point \(P_{1}\) to the checkpoint set \(\varphi\). The turning points in P are then sequentially connected to the first element in the set \(\varphi\), and the points on the connecting line are added to the set R. If \(T\cap R=\emptyset\), the connection is deemed valid; if \(T\cap R\
eq\emptyset\), the connection is discarded. This process continues as elements in the set P are added to the first position in \(\varphi\) for verification, until all elements in P have been incorporated into \(\varphi\) and the verification is complete. Upon evaluating all the turning nodes in sequence, the path optimization is concluded, resulting in the optimized path points, as illustrated in Figure 1, represented by A-B-D.  
The pseudocode for the triangle pruning algorithm is shown as Algorithm 2.  
Figure 1: The principle of triangle pruning method.