# Warehouse-Oriented Optimal Path Planning for Autonomous Mobile Fire-Fighting Robots

Authors: Yong-tao Liu; Rui-zhi Sun; Tian-yi Zhang; Xiang-nan Zhang; Li Li; Guo-qing Shi
Journal: Security and Communication Networks
 (2020)

---

## Abstract

In order to achieve the fastest fire-fighting purpose, warehouse autonomous mobile fire-fighting robots need to make an overall optimal planning based on the principle of the shortest time for their traveling path. A∗ algorithm is considered as a very ideal shortest path planning algorithm, but the shortest path is not necessarily the optimal path for robots. Furthermore, the conventional A∗ algorithm is affected by the search neighborhood restriction and the theoretical characteristics, so there are many problems, which are closing to obstacles, more inflection points, more redundant points, larger total turning angle, etc. Therefore, A∗ algorithm is improved in eight ways, and the inflection point prior strategy is adopted to compromise Floyd algorithm and A∗ algorithm in this paper. According to the criterion of the inflection point in this paper, the path inflection point arrays are constructed and traveling all path nodes are replaced by traveling path inflection points for the conventional Floyd algorithm backtracking, so it greatly reduces the backtracking time of the smooth path. In addition, this paper adopts the method of the extended grid map obstacle space in path planning safety distance. According to the relationship between the actual scale of the warehouse grid map and the size of the robot body, the different safe distance between the planning path and the obstacles is obtained, so that the algorithm can be applied to the safe path planning of the different size robots in any map environments. Finally, compared with the conventional A∗ algorithm, the improved algorithm reduces by 7.846% for the path length, reduces by 71.429% for the number of the cumulative turns, and reduces by 75% for the cumulative turning angle through the experiment. The proposed method can ensure robots to move fast on the planning path and ultimately achieve the goal of reducing the number of inflection points, reducing the cumulative turning angle, and reducing the path planning time.


---

## Body

## 1. Introduction

One of the core technologies of autonomous mobile robots is the ability of real time path planning. Path planning refers to, under the premise of following an optimal index (such as the shortest time, the optimal path, and the lowest energy consumption), the optimal path without collision from origin to termination is planned in the usage scenario [1], and the second path planning can be planned in the process of the original path planning in real time.The premise of path planning needs to build environment map. There are generally two ways to build a map: one is that the robot automatically builds the map through SLAM; the other one is that the site CAD is manually imported into the robot system according to the specified format. Either way, the environmental layout is required to be as fixed as possible.The object of this paper, warehouse-oriented autonomous mobile fire-fighting robot, is just suitable for this scenario. In the environment, multiple flame detection probes with address codes are installed on the top. When a flame is detected by a certain probe, the probe code and alarm signal are sent to the robot through edge computing processing and wireless networking technology [2–7]. Here, we need to ensure the security and stability of wireless sensor network and reduce the network delay [8–11]. The robot completes autonomous path planning and reaches the ignition point in the shortest time, and it extinguishes fires early in the fire. The structural space in the scene is relatively stable. In order to adapt to the path planning of the fire-fighting robot, we should take the best rather than the shortest as the principle according to the optimization index path. Because the robot is limited by its own space structure, it is difficult to ensure high-speed travel when it is in a small space and the loss time is much longer than that of path planning. The optimal path is based on the principle of the shortest time, i.e., the robot can achieve the fastest traveling path, and the fire-fighting robot can reach the fire point in the shortest time to put out the fire. This requires that, under the premise of ensuring the shortest planning path, the path and obstacles (such as shelves) have enough safe distance, reserved robot turning action space, etc. And, the number of turning points is less; the total turning angle is lower.After years of development, the path planning algorithm has achieved good results, but there are still some problems in specific application scenarios. The proposed method of the artificial potential field by Khatib [12] in 1994 falls into local minimum and oscillate near obstacles easily. In genetic algorithm (GA) [13], the range of coding length is large and the convergence is bad. In the complex map mode, the convergence speed of the algorithm is slow and the computation is large. In artificial neural network (ANN) [14], when the initial feedback information of the algorithm is insufficient, it needs to adjust the weight in a long time to achieve the optimization effect of the project approval. The search speed of the ant colony algorithm is slow and falls into local optimality easily [15]. The Dijkstra algorithm is a classical breadth prior algorithm [16], and it can always find the optimal path and conduct the overall search directly. However, it does not consider the target point information, and it has a long search time and low search efficiency because it cannot meet the need of rapid path planning. BFS optimal prior algorithm can quickly guide the search to the target node and greatly improve the search efficiency but cannot often get the shortest path.A∗ algorithm, first proposed in 1968 by Hart et al. [17], is a heuristic search algorithm [18–20] combined with the advantages of the above algorithms. It uses heuristic information to guide the search direction, so as to reduce the search scope and improve the search efficiency. It is a typical heuristic path planning algorithm [21, 22], which has been successfully applied and verified in mobile robot path planning [23].However, due to the computational characteristic of A∗ algorithm, the planned path points generally have many problems, such as many broken lines and large cumulative turning angle, and easily discard some points to generate suboptimal problems [24]. Therefore, many researchers have proposed improved algorithms in computational time [25, 26]. Gao et al. [27] proposed a bidirectional time-effective A∗ algorithm to find the path and adopted a multineighborhood grid distance computational scheme to achieve the effect of improving efficiency and smoothing the path, but it is not suitable for large-scale complex maps. In [28], an improved search A∗ algorithm combined with skip points is proposed, the speed of the algorithm has been greatly improved, but there are still many inflection points and close to obstacles. In [29], the size of the robot is considered, and a neighborhood matrix is proposed to improve the path safety of obstacle search. However, the path smoothing and length are not improved, so there are still many problems including more turning angles and large total turning angle. In [30, 31], proposed expand search neighborhood and dispose of quadratic smoothing of quintic polynomial reduce the length of search path and turning angle and greatly improve path smoothing. However, there are still some problems, such as closing to obstacles, and safety distance is not considered.Aiming at the problems of usage scenarios of warehouse-oriented fire-fighting robots and the existing various optimizational A∗ algorithm, this paper proposes a comprehensive improved A∗ algorithm to achieve path smoothing and reduces broken lines and cumulative turning angle. And, according to the bulk of the robot and the scale of map, we set up safe distance with the obstacles to meet the path planning application of the robots.The paper is organized as follows. In Section2, we propose the improved A∗ algorithm and smoothen the optimal path. Then, we introduce the constraint conditions including robot’s safety traveling distance and compare with the effect of the current latest algorithm. Section 3 introduces the practical application effect of the complete algorithm in this paper and verifies a great impact of safety distance on the path. Section 4 concludes the paper.


## 2. Improved A∗ Algorithm

The planning effect of the conventional four-way search A∗ algorithm is shown in Figure 1(a). There are a lot of right-angle points in the route, and the length of the route is not the shortest. On this basis, eight-way search A∗ algorithms are proposed; the planning effect is shown in Figure 1(b). It can be seen that the eight-way search A∗ algorithm overcomes the problem of right-angle inflection point in the path and plans the shortest path length under the algorithm. However, the algorithm has the problems of closing to the obstacles and crossing the diagonal vertex of the obstacles (Figure 1(a)); this path cannot be used as the traveling path of the robot obviously. Therefore, the conventional eight-way search A∗ algorithm is not suitable for robot path planning and it needs to improve the basic safety distance and the constraint.Figure 1
The comparisons of A∗ algorithm comparison. (a) Conventional four-way A∗ algorithm. (b) Conventional eight-way A∗ algorithm. (c) Improved eight-way A∗ algorithm.
(a)(b)(c)


### 2.1. Improved Eight-Way A∗ Algorithm

In view of the existing problems of conventional eight-way search A∗ algorithm, we make a basic improvement, i.e., when the eight-way search area is expanded and if the path forward direction is a slash, the constraint term is added, for example, in Figure 1(c), when the path is planned according to a lower right slash, then we judge whether there is any obstacle on the right and bottom sides of the parent-node. If there is, the path is not feasible and the subnode needs to be selected again. When the path is planned according to upper left slash, then we judge whether there is any obstacle on the left and upper sides of the parent-node. If there is, the path is not feasible, the subnode needs to be selected again. The planning path according to this method is shown in Figure 1(c).The performance comparisons of the three algorithms in Figure1 are shown in Table 1. It can be seen that the conventional four-way search A∗ algorithm has the longest path length and the slowest operation time. The conventional eight-way search A∗ algorithm has the shortest path length and the fastest operation time, but the path has the problems of closing to the obstacle vertex and crossing the obstacle vertex angle, so the path cannot be used by robots. On this basis the eight-way search, the A∗ algorithm is improved in this paper and the shortest path is realized under the algorithm. Compared with the conventional four-way search A∗ algorithm, the path length reduces by 12.53%, the operation time reduces by 46.9%, and the situation closing to the obstacle vertex and crossing the corner is effectively avoided.Table 1
The comparisons of performance efficiency for A∗ algorithm.
Origin terminationAlgorithmThe length of the pathTurn times(18, 1)(2, 13)Four-way A∗28.000.0678Eight-way A∗22.140.0196Improved eight-way A∗24.490.036


### 2.2. Improved Floyd Path Smoothing Algorithm

In [30], traversing nodes are used for the smoothing process. In [32], Floyd algorithm is used for the smoothing process. These two methods need to trace back all path nodes one by one from the origin or termination to determine whether they intersect obstacles. If they do not intersect, the intermediate node will be discarded, and if they intersect, the previous node will be retained. These two methods can optimize the original path, but traversing all the path nodes significantly reduces the execution speed, and the straight path nodes in the original path can avoid traversing judgment completely. Therefore, this paper proposes the criterion of the prior inflection point, and Floyd algorithm is used to connect the backtracking method of the inflection point.


#### 2.2.1. Criterion of the Planning Route Inflection Point

Before path smoothing is completed, the eight-way A∗ algorithm path planning has to be improved. Inflection criteria are added after planning; path inflection array is generated. For example, let point D in Figure 2 be the current node n, according to the A∗ algorithm formula:(1)fn=gn+hn,where g(n) indicates the length of the actual path from the origin to the current node and h(n) is the distance of estimate cost function from the state node n to termination.Figure 2
The principle of improved A∗ algorithm.According to the eight-way extended A∗ algorithm, there are only two path lengths of adjacent nodes, i.e., L and 2L. If the distance from the current node n to its parent-node (n − 1) and sub-node (n + 1) is not equal, then the node in the planning path is the inflection point. The criteria are as follows:(2)LXn−1,Xn≠LXn,Xn+1.For example, ifL(C, D) ≠ L(D, E), then the planning path node D is the inflection point; if L(D, E) = L(E, F), then the planning path node E is a normal node. In the judgment, all the noninflection nodes in the planning path are expressed as (x, y, 0); the inflection nodes are expressed as (x, y, 1); the origin of the robot path is defined as a common node; the termination is defined as an inflection. All the nodes are saved in the file-list array. In the last path backtracking, simply priorly connecting the inflection points can get the path smooth optimization.


#### 2.2.2. Design of Floyd Algorithm

We combine Floyd algorithm and the improved A∗ algorithm; the length of the original planning path can be shorter; the number of inflection points can be less; the cumulative turning angle can be less; the path can be smoother.In the smooth process, firstly, we need to get the file list of the inflection points of the planning path and directly connect the second inflection point in the backtracking path when backtracking from the termination. If it does not intersect the obstacle, then the third inflection point should be connected. If the connection encounters the obstacle, all nodes between the third inflection point and the second inflection point are traced back in turn until the node that does not intersect the obstacle is found, and the intermediate node is discarded.In Figure2, if points A and B are adjacent inflection points, then they can be connected directly. The distance is written as L(A, B). Judge A ⟶ C and A ⟶ D in turn; if they do not intersect obstacles when they are connecting, the original path can be changed to A ⟶ D. But, when A ⟶ G, they intersect obstacles, so the path length L(A, G) = +∞:(3)LA,C<LA,B+LB,C.Then, the array of pointsA and C are retained, and the array of point B is deleted:(4)LA,D<LA,C+LC,D.Then, the array of pointsA and D are retained, and the array of point C is deleted.BecauseL(A, G) = +∞,(5)LA,G=LA,D+LD,G.At this time, assume the coordinate of pointG is G(i, j, 1), then the original path node between D and G will be traced back from point G, G1(i − 1, j, 0), G2(i − 2, j, 0), G3(i − 3, j, 0), and G4(i − 4, j, 0), where G3 = F and G4 = E. When connected with point A, L(A, G1) = +∞, L(A, G2) = +∞, and L(A, F) = +∞ are abandoned:(6)LA,E+LE,G<LA,D+LD,G.Then, the array of pointsA and E are retained, and the array of point D is deleted. The original path A ⟶ B ⟶ C ⟶ D ⟶ G is optimized as A ⟶ E ⟶ G, so far, this section of path optimization is completed, and the next path optimization is carried out accordingly.The specific implementation steps of the path smoothing algorithm are as follows:(i)
Step 1: take out the processed nodes of the above improved eight-way A∗ algorithm and carry out the secondary backtracking analysis from the termination.(ii)
Step 2: start the termination to connect all the inflection points one by one,B ⟶ C ⟶ D, and then the nodes of noninflection points, such as the points between B ⟶ C, are ignored during the connection process.(iii)
Step 3: when pointsA and D are directly connected, continue to search backward inflection point G. At this time, there will be a conflict between search path A ⟶ G and obstacles. Then, search the nodes of noninflection point between G ⟶ D.(iv)
Step 4: if there is still a conflict with the obstacle when searching to nodeF, then continue to Step 3 until node E, that is, no conflict with the obstacle is found.(v)
Step 5: at this time, take the direct connection pathA ⟶ E as the fixed path and repeat step 2 ⟶ 3 ⟶ 4 from node E until reaching the origin.The flowchart of the algorithm is given in Figure3.Figure 3
Algorithm flowchart.Compared with [33], the method only makes redundant judgments for inflection points; it adds the backtracking function of common nodes between obstacle inflection nodes and makes the path distance shorter. Compared with [30, 32], the traversal connection judgment time of the smoothing path algorithm is significantly reduced. In the method, all node connection judgments are no longer performed, and only the inflection nodes in the eight-way A∗ algorithm planning nodes are preferentially connected twice. There is a conflict with obstacles, and then node by node from the inflection node back is connected; the number of connection judgments is reduced greatly; the path smoothing processing time becomes shorter.An array of once planned path nodeint a [3] [6] is shown as(7)0,0,0,2,2,1,2,3,0,2,4,0,2,5,0,2,6,0,2,7,1,3,8,1,4,8,0,5,8,0,6,8,0,7,8,0,8,8,1,9,7,1,9,6,0,9,5,1.It can be seen that there are five inflection nodes besides origin [0, 0, 0] and termination [1, 5, 9] in once planned path, and the following five inflection nodes are used as the prior traversal point:(8)2,7,1,3,8,1,8,8,1,9,7,1,9,5,1.After executing the optimized algorithm based on Floyd algorithm, the final path contains only 3 nodes and the noninflection points in the once path. The optimal path node arrayint a [3] [3] is shown as follows:(9)4,8,0,8,8,1,9,5,1..


#### 2.2.3. Simulation Analysis of the Confluent Improved Algorithm

To verify the effect of the proposed confluent improved Floyd and improved A∗ algorithms in this paper, comparisons are made between the basic improved A∗ algorithm and the proposed prior moving route algorithm in [34]. The optimized path in [34] is shown in the red path in Figure 4(a). The length of the path is actually 21.4852 grids, but the path has the problem of closing to the apexes of the obstacles and the possibility of crossing the top angle of the obstacles, so the path is not suitable as a robot planning path.Figure 4
The improved path smoothing algorithm process. (a) The improved algorithm in [34]. (b) The improved algorithm in this paper. (c) The confluent path smoothing algorithm.
(a)(b)(c)This paper basically improves the path planning of the A∗ algorithm and adds grid constraints to avoid closing to obstacle paths. The planned path is shown in Figure 4(b).Finally, path smoothing process is added based on the path planning of the improved A∗ algorithm, and the processing effect is shown in the blue path in Figure 4(c).In the case that the initial orientation of the robot is not considered in the three paths in Figure4, the obtained data graph by the experimental simulation is shown in Table 2. Compared with the improved eight-way A∗ algorithm, in this paper, the path length of the confluent algorithm reduces by 7.846%, the number of cumulative turns reduces by 71.429%, and the cumulative turning angle reduces by 75%. Compared with the improved A∗ algorithm in [34], in this paper, the path length of the smoothing algorithm reduces by 0.02%; the length optimization is not obvious. But the number of the cumulative turns reduces by 66.67%, and the cumulative turning angle reduces by 57.91%. The advantage of the part is obvious, the path is more conducive to the execution of the robot.Table 2
Comparisons of key parameters for the algorithmic effectiveness.
AlgorithmThe length of pathInflection pointsCumulative turning point (°)Improved eight-way A∗23.317360.00Algorithms in [25]21.48526213.84Smoothing algorithm in this paper21.4809290.00So far, although the proposed confluent algorithm in this paper has obvious advantages in cumulative turning points and cumulative turning angles, there are still cases crossing the vertices of obstacles, so it needs to further optimize the path safety distance considering the actual situation of the robot body space.


### 2.3. Optimization Algorithm of the Path Planning Safety Distance

For the reasonable traveling path of the robot, we should fully consider its own space structure and a sufficient safe distance from the obstacles should be reserved in the path planning. In this way, the robots can reduce the detection and processing time required to avoid obstacles when it actually follows the path in the later stage. Although this paper achieves the goal of the smoothing path by improving the Floyd algorithm, the optimized path still has the situation closing to the obstacles. Therefore, this paper continues to lead into the concept of path safety space in the design for algorithm optimization.


#### 2.3.1. Optimization Algorithm of the Safety Distance Based on Extended Obstacle Boundary

In order to ensure the space safety distance of the path, there are generally two methods. One is to expand the pixels occupied by the robot body within the map pixels and make the robot body space consistent with the actual map pixel ratio. The cross-obstacle search algorithm and them-shaped obstacle search algorithm are given in [29]. The algorithm obtains different safety distances by changing the size of the search matrix to ensure the safety of the different robots in different map environments. The other one is the method that is to extend the obstacle boundary. This method combining with the size of the robot can set the safety distance arbitrarily and intuitively without increasing the difficulty of the algorithm, and it can effectively reduce the number of traversal grids in the search area and the search time.Note: in the following path planning diagrams, the red path is the planned path of the basic improved eight-way A∗ algorithm; the blue path is the smoothed planned path, which is the final path; the colored grid is all the traversal grids in the path planning process.The planned route is the planned route obtained in [29] using the 12-neighborhood search algorithm in Figure 5(a). The method can improve the search efficiency, and it also leads to the increase of the path length. The algorithm is designed with the path length as the primary priority and the search time as the secondary priority. In Figure 5(b), the red path is the improved eight-way A∗ algorithm planned path in this paper. The path is linked by the grid center point. The planned path can also achieve a safety distance to a certain degree. However, it is not flexible enough and cannot be set arbitrarily according to the robot map ratio.Figure 5
The comparison of the safety distance solutions. (a) Cross barrier search in [29]. (b) Extended obstacle boundary method in this paper.
(a)(b)It can be seen in Table3 that the improved A∗ smoothing algorithm adopts the search method of expanding obstacle boundary in this paper; compared with [29], the path length is shorter and the number of traversed grids is smaller. The number of the path inflection points that is a key indicator for evaluating the robot’s traveling path has also decreased 44.4%; the corresponding cumulative turning angle has decreased significantly; the path smoothness advantage is very obvious.Table 3
The comparisons of two safety distance search methods.
AlgorithmThe length of pathInflection pointsErgodic grid number12 neighborhood cross search algorithms in [29]224187957Extended barrier boundary method169.81103739


#### 2.3.2. Impact Analysis of the Path Safety Distance

Although the constraint condition of safety distance is required in path planning, the design path is more suitable for robot walking. On the surface, the path designed by the algorithm should be as far away from the obstacles as possible, but when this safety distance is set too large, the path cannot be planned. As shown in Figure6, this paper has tested and analyzed the situations of the different safety distances.Figure 6
The effect of path planning at different safety distances. (a) No safety distance. (b) Safety distance 0.6 grid. (c) Safety distance 1 grid.
(a)(b)(c)In Figure6, the path planning test was performed on a map of 25×25 grid pixels for each without safety distance constraint, 0.6 grid safety distance, and 1.0 grid safety distance.According to the analysis in Table4, it can be found that when there is no safety distance, the planned path is the shortest; the number of inflection points is centered; the number of traversed grids is the largest; and the planning time is the longest. At 0.6 grid safety distance, the path length is 1.2% longer than the shortest path; the number of inflection points reduces by 50%; the number of traversal grids reduces by 62.6%; and the planned time reduces by 37.79%. 1.0 grid safety distance has the longest path length, the largest number of inflection points, and the shortest planned time. If the safety distance grid is set to 2.0, path planning cannot be completed.Table 4
Effect analysis of path planning for different safe distances.
AlgorithmThe length of pathDiscount pointsErgodic grid numberPlanning time (S)No safe distance37.1743610.44240.6 grid safe distance37.6221350.27491.0 grid safe distance39.9851350.2272Under the condition that the robot path planning guarantees a safe distance, the time spent in path planning can be ignored compared with the time saved by robot turning and fast passing. Therefore, it can be ensured that the second shortest path with the least number of inflection points and the smallest cumulative turning angle of the robot is the optimal path of the robot.


## 2.1. Improved Eight-Way A∗ Algorithm

In view of the existing problems of conventional eight-way search A∗ algorithm, we make a basic improvement, i.e., when the eight-way search area is expanded and if the path forward direction is a slash, the constraint term is added, for example, in Figure 1(c), when the path is planned according to a lower right slash, then we judge whether there is any obstacle on the right and bottom sides of the parent-node. If there is, the path is not feasible and the subnode needs to be selected again. When the path is planned according to upper left slash, then we judge whether there is any obstacle on the left and upper sides of the parent-node. If there is, the path is not feasible, the subnode needs to be selected again. The planning path according to this method is shown in Figure 1(c).The performance comparisons of the three algorithms in Figure1 are shown in Table 1. It can be seen that the conventional four-way search A∗ algorithm has the longest path length and the slowest operation time. The conventional eight-way search A∗ algorithm has the shortest path length and the fastest operation time, but the path has the problems of closing to the obstacle vertex and crossing the obstacle vertex angle, so the path cannot be used by robots. On this basis the eight-way search, the A∗ algorithm is improved in this paper and the shortest path is realized under the algorithm. Compared with the conventional four-way search A∗ algorithm, the path length reduces by 12.53%, the operation time reduces by 46.9%, and the situation closing to the obstacle vertex and crossing the corner is effectively avoided.Table 1
The comparisons of performance efficiency for A∗ algorithm.
Origin terminationAlgorithmThe length of the pathTurn times(18, 1)(2, 13)Four-way A∗28.000.0678Eight-way A∗22.140.0196Improved eight-way A∗24.490.036


## 2.2. Improved Floyd Path Smoothing Algorithm

In [30], traversing nodes are used for the smoothing process. In [32], Floyd algorithm is used for the smoothing process. These two methods need to trace back all path nodes one by one from the origin or termination to determine whether they intersect obstacles. If they do not intersect, the intermediate node will be discarded, and if they intersect, the previous node will be retained. These two methods can optimize the original path, but traversing all the path nodes significantly reduces the execution speed, and the straight path nodes in the original path can avoid traversing judgment completely. Therefore, this paper proposes the criterion of the prior inflection point, and Floyd algorithm is used to connect the backtracking method of the inflection point.


### 2.2.1. Criterion of the Planning Route Inflection Point

Before path smoothing is completed, the eight-way A∗ algorithm path planning has to be improved. Inflection criteria are added after planning; path inflection array is generated. For example, let point D in Figure 2 be the current node n, according to the A∗ algorithm formula:(1)fn=gn+hn,where g(n) indicates the length of the actual path from the origin to the current node and h(n) is the distance of estimate cost function from the state node n to termination.Figure 2
The principle of improved A∗ algorithm.According to the eight-way extended A∗ algorithm, there are only two path lengths of adjacent nodes, i.e., L and 2L. If the distance from the current node n to its parent-node (n − 1) and sub-node (n + 1) is not equal, then the node in the planning path is the inflection point. The criteria are as follows:(2)LXn−1,Xn≠LXn,Xn+1.For example, ifL(C, D) ≠ L(D, E), then the planning path node D is the inflection point; if L(D, E) = L(E, F), then the planning path node E is a normal node. In the judgment, all the noninflection nodes in the planning path are expressed as (x, y, 0); the inflection nodes are expressed as (x, y, 1); the origin of the robot path is defined as a common node; the termination is defined as an inflection. All the nodes are saved in the file-list array. In the last path backtracking, simply priorly connecting the inflection points can get the path smooth optimization.


### 2.2.2. Design of Floyd Algorithm

We combine Floyd algorithm and the improved A∗ algorithm; the length of the original planning path can be shorter; the number of inflection points can be less; the cumulative turning angle can be less; the path can be smoother.In the smooth process, firstly, we need to get the file list of the inflection points of the planning path and directly connect the second inflection point in the backtracking path when backtracking from the termination. If it does not intersect the obstacle, then the third inflection point should be connected. If the connection encounters the obstacle, all nodes between the third inflection point and the second inflection point are traced back in turn until the node that does not intersect the obstacle is found, and the intermediate node is discarded.In Figure2, if points A and B are adjacent inflection points, then they can be connected directly. The distance is written as L(A, B). Judge A ⟶ C and A ⟶ D in turn; if they do not intersect obstacles when they are connecting, the original path can be changed to A ⟶ D. But, when A ⟶ G, they intersect obstacles, so the path length L(A, G) = +∞:(3)LA,C<LA,B+LB,C.Then, the array of pointsA and C are retained, and the array of point B is deleted:(4)LA,D<LA,C+LC,D.Then, the array of pointsA and D are retained, and the array of point C is deleted.BecauseL(A, G) = +∞,(5)LA,G=LA,D+LD,G.At this time, assume the coordinate of pointG is G(i, j, 1), then the original path node between D and G will be traced back from point G, G1(i − 1, j, 0), G2(i − 2, j, 0), G3(i − 3, j, 0), and G4(i − 4, j, 0), where G3 = F and G4 = E. When connected with point A, L(A, G1) = +∞, L(A, G2) = +∞, and L(A, F) = +∞ are abandoned:(6)LA,E+LE,G<LA,D+LD,G.Then, the array of pointsA and E are retained, and the array of point D is deleted. The original path A ⟶ B ⟶ C ⟶ D ⟶ G is optimized as A ⟶ E ⟶ G, so far, this section of path optimization is completed, and the next path optimization is carried out accordingly.The specific implementation steps of the path smoothing algorithm are as follows:(i)
Step 1: take out the processed nodes of the above improved eight-way A∗ algorithm and carry out the secondary backtracking analysis from the termination.(ii)
Step 2: start the termination to connect all the inflection points one by one,B ⟶ C ⟶ D, and then the nodes of noninflection points, such as the points between B ⟶ C, are ignored during the connection process.(iii)
Step 3: when pointsA and D are directly connected, continue to search backward inflection point G. At this time, there will be a conflict between search path A ⟶ G and obstacles. Then, search the nodes of noninflection point between G ⟶ D.(iv)
Step 4: if there is still a conflict with the obstacle when searching to nodeF, then continue to Step 3 until node E, that is, no conflict with the obstacle is found.(v)
Step 5: at this time, take the direct connection pathA ⟶ E as the fixed path and repeat step 2 ⟶ 3 ⟶ 4 from node E until reaching the origin.The flowchart of the algorithm is given in Figure3.Figure 3
Algorithm flowchart.Compared with [33], the method only makes redundant judgments for inflection points; it adds the backtracking function of common nodes between obstacle inflection nodes and makes the path distance shorter. Compared with [30, 32], the traversal connection judgment time of the smoothing path algorithm is significantly reduced. In the method, all node connection judgments are no longer performed, and only the inflection nodes in the eight-way A∗ algorithm planning nodes are preferentially connected twice. There is a conflict with obstacles, and then node by node from the inflection node back is connected; the number of connection judgments is reduced greatly; the path smoothing processing time becomes shorter.An array of once planned path nodeint a [3] [6] is shown as(7)0,0,0,2,2,1,2,3,0,2,4,0,2,5,0,2,6,0,2,7,1,3,8,1,4,8,0,5,8,0,6,8,0,7,8,0,8,8,1,9,7,1,9,6,0,9,5,1.It can be seen that there are five inflection nodes besides origin [0, 0, 0] and termination [1, 5, 9] in once planned path, and the following five inflection nodes are used as the prior traversal point:(8)2,7,1,3,8,1,8,8,1,9,7,1,9,5,1.After executing the optimized algorithm based on Floyd algorithm, the final path contains only 3 nodes and the noninflection points in the once path. The optimal path node arrayint a [3] [3] is shown as follows:(9)4,8,0,8,8,1,9,5,1..


### 2.2.3. Simulation Analysis of the Confluent Improved Algorithm

To verify the effect of the proposed confluent improved Floyd and improved A∗ algorithms in this paper, comparisons are made between the basic improved A∗ algorithm and the proposed prior moving route algorithm in [34]. The optimized path in [34] is shown in the red path in Figure 4(a). The length of the path is actually 21.4852 grids, but the path has the problem of closing to the apexes of the obstacles and the possibility of crossing the top angle of the obstacles, so the path is not suitable as a robot planning path.Figure 4
The improved path smoothing algorithm process. (a) The improved algorithm in [34]. (b) The improved algorithm in this paper. (c) The confluent path smoothing algorithm.
(a)(b)(c)This paper basically improves the path planning of the A∗ algorithm and adds grid constraints to avoid closing to obstacle paths. The planned path is shown in Figure 4(b).Finally, path smoothing process is added based on the path planning of the improved A∗ algorithm, and the processing effect is shown in the blue path in Figure 4(c).In the case that the initial orientation of the robot is not considered in the three paths in Figure4, the obtained data graph by the experimental simulation is shown in Table 2. Compared with the improved eight-way A∗ algorithm, in this paper, the path length of the confluent algorithm reduces by 7.846%, the number of cumulative turns reduces by 71.429%, and the cumulative turning angle reduces by 75%. Compared with the improved A∗ algorithm in [34], in this paper, the path length of the smoothing algorithm reduces by 0.02%; the length optimization is not obvious. But the number of the cumulative turns reduces by 66.67%, and the cumulative turning angle reduces by 57.91%. The advantage of the part is obvious, the path is more conducive to the execution of the robot.Table 2
Comparisons of key parameters for the algorithmic effectiveness.
AlgorithmThe length of pathInflection pointsCumulative turning point (°)Improved eight-way A∗23.317360.00Algorithms in [25]21.48526213.84Smoothing algorithm in this paper21.4809290.00So far, although the proposed confluent algorithm in this paper has obvious advantages in cumulative turning points and cumulative turning angles, there are still cases crossing the vertices of obstacles, so it needs to further optimize the path safety distance considering the actual situation of the robot body space.


## 2.2.1. Criterion of the Planning Route Inflection Point

Before path smoothing is completed, the eight-way A∗ algorithm path planning has to be improved. Inflection criteria are added after planning; path inflection array is generated. For example, let point D in Figure 2 be the current node n, according to the A∗ algorithm formula:(1)fn=gn+hn,where g(n) indicates the length of the actual path from the origin to the current node and h(n) is the distance of estimate cost function from the state node n to termination.Figure 2
The principle of improved A∗ algorithm.According to the eight-way extended A∗ algorithm, there are only two path lengths of adjacent nodes, i.e., L and 2L. If the distance from the current node n to its parent-node (n − 1) and sub-node (n + 1) is not equal, then the node in the planning path is the inflection point. The criteria are as follows:(2)LXn−1,Xn≠LXn,Xn+1.For example, ifL(C, D) ≠ L(D, E), then the planning path node D is the inflection point; if L(D, E) = L(E, F), then the planning path node E is a normal node. In the judgment, all the noninflection nodes in the planning path are expressed as (x, y, 0); the inflection nodes are expressed as (x, y, 1); the origin of the robot path is defined as a common node; the termination is defined as an inflection. All the nodes are saved in the file-list array. In the last path backtracking, simply priorly connecting the inflection points can get the path smooth optimization.


## 2.2.2. Design of Floyd Algorithm

We combine Floyd algorithm and the improved A∗ algorithm; the length of the original planning path can be shorter; the number of inflection points can be less; the cumulative turning angle can be less; the path can be smoother.In the smooth process, firstly, we need to get the file list of the inflection points of the planning path and directly connect the second inflection point in the backtracking path when backtracking from the termination. If it does not intersect the obstacle, then the third inflection point should be connected. If the connection encounters the obstacle, all nodes between the third inflection point and the second inflection point are traced back in turn until the node that does not intersect the obstacle is found, and the intermediate node is discarded.In Figure2, if points A and B are adjacent inflection points, then they can be connected directly. The distance is written as L(A, B). Judge A ⟶ C and A ⟶ D in turn; if they do not intersect obstacles when they are connecting, the original path can be changed to A ⟶ D. But, when A ⟶ G, they intersect obstacles, so the path length L(A, G) = +∞:(3)LA,C<LA,B+LB,C.Then, the array of pointsA and C are retained, and the array of point B is deleted:(4)LA,D<LA,C+LC,D.Then, the array of pointsA and D are retained, and the array of point C is deleted.BecauseL(A, G) = +∞,(5)LA,G=LA,D+LD,G.At this time, assume the coordinate of pointG is G(i, j, 1), then the original path node between D and G will be traced back from point G, G1(i − 1, j, 0), G2(i − 2, j, 0), G3(i − 3, j, 0), and G4(i − 4, j, 0), where G3 = F and G4 = E. When connected with point A, L(A, G1) = +∞, L(A, G2) = +∞, and L(A, F) = +∞ are abandoned:(6)LA,E+LE,G<LA,D+LD,G.Then, the array of pointsA and E are retained, and the array of point D is deleted. The original path A ⟶ B ⟶ C ⟶ D ⟶ G is optimized as A ⟶ E ⟶ G, so far, this section of path optimization is completed, and the next path optimization is carried out accordingly.The specific implementation steps of the path smoothing algorithm are as follows:(i)
Step 1: take out the processed nodes of the above improved eight-way A∗ algorithm and carry out the secondary backtracking analysis from the termination.(ii)
Step 2: start the termination to connect all the inflection points one by one,B ⟶ C ⟶ D, and then the nodes of noninflection points, such as the points between B ⟶ C, are ignored during the connection process.(iii)
Step 3: when pointsA and D are directly connected, continue to search backward inflection point G. At this time, there will be a conflict between search path A ⟶ G and obstacles. Then, search the nodes of noninflection point between G ⟶ D.(iv)
Step 4: if there is still a conflict with the obstacle when searching to nodeF, then continue to Step 3 until node E, that is, no conflict with the obstacle is found.(v)
Step 5: at this time, take the direct connection pathA ⟶ E as the fixed path and repeat step 2 ⟶ 3 ⟶ 4 from node E until reaching the origin.The flowchart of the algorithm is given in Figure3.Figure 3
Algorithm flowchart.Compared with [33], the method only makes redundant judgments for inflection points; it adds the backtracking function of common nodes between obstacle inflection nodes and makes the path distance shorter. Compared with [30, 32], the traversal connection judgment time of the smoothing path algorithm is significantly reduced. In the method, all node connection judgments are no longer performed, and only the inflection nodes in the eight-way A∗ algorithm planning nodes are preferentially connected twice. There is a conflict with obstacles, and then node by node from the inflection node back is connected; the number of connection judgments is reduced greatly; the path smoothing processing time becomes shorter.An array of once planned path nodeint a [3] [6] is shown as(7)0,0,0,2,2,1,2,3,0,2,4,0,2,5,0,2,6,0,2,7,1,3,8,1,4,8,0,5,8,0,6,8,0,7,8,0,8,8,1,9,7,1,9,6,0,9,5,1.It can be seen that there are five inflection nodes besides origin [0, 0, 0] and termination [1, 5, 9] in once planned path, and the following five inflection nodes are used as the prior traversal point:(8)2,7,1,3,8,1,8,8,1,9,7,1,9,5,1.After executing the optimized algorithm based on Floyd algorithm, the final path contains only 3 nodes and the noninflection points in the once path. The optimal path node arrayint a [3] [3] is shown as follows:(9)4,8,0,8,8,1,9,5,1..


## 2.2.3. Simulation Analysis of the Confluent Improved Algorithm

To verify the effect of the proposed confluent improved Floyd and improved A∗ algorithms in this paper, comparisons are made between the basic improved A∗ algorithm and the proposed prior moving route algorithm in [34]. The optimized path in [34] is shown in the red path in Figure 4(a). The length of the path is actually 21.4852 grids, but the path has the problem of closing to the apexes of the obstacles and the possibility of crossing the top angle of the obstacles, so the path is not suitable as a robot planning path.Figure 4
The improved path smoothing algorithm process. (a) The improved algorithm in [34]. (b) The improved algorithm in this paper. (c) The confluent path smoothing algorithm.
(a)(b)(c)This paper basically improves the path planning of the A∗ algorithm and adds grid constraints to avoid closing to obstacle paths. The planned path is shown in Figure 4(b).Finally, path smoothing process is added based on the path planning of the improved A∗ algorithm, and the processing effect is shown in the blue path in Figure 4(c).In the case that the initial orientation of the robot is not considered in the three paths in Figure4, the obtained data graph by the experimental simulation is shown in Table 2. Compared with the improved eight-way A∗ algorithm, in this paper, the path length of the confluent algorithm reduces by 7.846%, the number of cumulative turns reduces by 71.429%, and the cumulative turning angle reduces by 75%. Compared with the improved A∗ algorithm in [34], in this paper, the path length of the smoothing algorithm reduces by 0.02%; the length optimization is not obvious. But the number of the cumulative turns reduces by 66.67%, and the cumulative turning angle reduces by 57.91%. The advantage of the part is obvious, the path is more conducive to the execution of the robot.Table 2
Comparisons of key parameters for the algorithmic effectiveness.
AlgorithmThe length of pathInflection pointsCumulative turning point (°)Improved eight-way A∗23.317360.00Algorithms in [25]21.48526213.84Smoothing algorithm in this paper21.4809290.00So far, although the proposed confluent algorithm in this paper has obvious advantages in cumulative turning points and cumulative turning angles, there are still cases crossing the vertices of obstacles, so it needs to further optimize the path safety distance considering the actual situation of the robot body space.


## 2.3. Optimization Algorithm of the Path Planning Safety Distance

For the reasonable traveling path of the robot, we should fully consider its own space structure and a sufficient safe distance from the obstacles should be reserved in the path planning. In this way, the robots can reduce the detection and processing time required to avoid obstacles when it actually follows the path in the later stage. Although this paper achieves the goal of the smoothing path by improving the Floyd algorithm, the optimized path still has the situation closing to the obstacles. Therefore, this paper continues to lead into the concept of path safety space in the design for algorithm optimization.


### 2.3.1. Optimization Algorithm of the Safety Distance Based on Extended Obstacle Boundary

In order to ensure the space safety distance of the path, there are generally two methods. One is to expand the pixels occupied by the robot body within the map pixels and make the robot body space consistent with the actual map pixel ratio. The cross-obstacle search algorithm and them-shaped obstacle search algorithm are given in [29]. The algorithm obtains different safety distances by changing the size of the search matrix to ensure the safety of the different robots in different map environments. The other one is the method that is to extend the obstacle boundary. This method combining with the size of the robot can set the safety distance arbitrarily and intuitively without increasing the difficulty of the algorithm, and it can effectively reduce the number of traversal grids in the search area and the search time.Note: in the following path planning diagrams, the red path is the planned path of the basic improved eight-way A∗ algorithm; the blue path is the smoothed planned path, which is the final path; the colored grid is all the traversal grids in the path planning process.The planned route is the planned route obtained in [29] using the 12-neighborhood search algorithm in Figure 5(a). The method can improve the search efficiency, and it also leads to the increase of the path length. The algorithm is designed with the path length as the primary priority and the search time as the secondary priority. In Figure 5(b), the red path is the improved eight-way A∗ algorithm planned path in this paper. The path is linked by the grid center point. The planned path can also achieve a safety distance to a certain degree. However, it is not flexible enough and cannot be set arbitrarily according to the robot map ratio.Figure 5
The comparison of the safety distance solutions. (a) Cross barrier search in [29]. (b) Extended obstacle boundary method in this paper.
(a)(b)It can be seen in Table3 that the improved A∗ smoothing algorithm adopts the search method of expanding obstacle boundary in this paper; compared with [29], the path length is shorter and the number of traversed grids is smaller. The number of the path inflection points that is a key indicator for evaluating the robot’s traveling path has also decreased 44.4%; the corresponding cumulative turning angle has decreased significantly; the path smoothness advantage is very obvious.Table 3
The comparisons of two safety distance search methods.
AlgorithmThe length of pathInflection pointsErgodic grid number12 neighborhood cross search algorithms in [29]224187957Extended barrier boundary method169.81103739


### 2.3.2. Impact Analysis of the Path Safety Distance

Although the constraint condition of safety distance is required in path planning, the design path is more suitable for robot walking. On the surface, the path designed by the algorithm should be as far away from the obstacles as possible, but when this safety distance is set too large, the path cannot be planned. As shown in Figure6, this paper has tested and analyzed the situations of the different safety distances.Figure 6
The effect of path planning at different safety distances. (a) No safety distance. (b) Safety distance 0.6 grid. (c) Safety distance 1 grid.
(a)(b)(c)In Figure6, the path planning test was performed on a map of 25×25 grid pixels for each without safety distance constraint, 0.6 grid safety distance, and 1.0 grid safety distance.According to the analysis in Table4, it can be found that when there is no safety distance, the planned path is the shortest; the number of inflection points is centered; the number of traversed grids is the largest; and the planning time is the longest. At 0.6 grid safety distance, the path length is 1.2% longer than the shortest path; the number of inflection points reduces by 50%; the number of traversal grids reduces by 62.6%; and the planned time reduces by 37.79%. 1.0 grid safety distance has the longest path length, the largest number of inflection points, and the shortest planned time. If the safety distance grid is set to 2.0, path planning cannot be completed.Table 4
Effect analysis of path planning for different safe distances.
AlgorithmThe length of pathDiscount pointsErgodic grid numberPlanning time (S)No safe distance37.1743610.44240.6 grid safe distance37.6221350.27491.0 grid safe distance39.9851350.2272Under the condition that the robot path planning guarantees a safe distance, the time spent in path planning can be ignored compared with the time saved by robot turning and fast passing. Therefore, it can be ensured that the second shortest path with the least number of inflection points and the smallest cumulative turning angle of the robot is the optimal path of the robot.


## 2.3.1. Optimization Algorithm of the Safety Distance Based on Extended Obstacle Boundary

In order to ensure the space safety distance of the path, there are generally two methods. One is to expand the pixels occupied by the robot body within the map pixels and make the robot body space consistent with the actual map pixel ratio. The cross-obstacle search algorithm and them-shaped obstacle search algorithm are given in [29]. The algorithm obtains different safety distances by changing the size of the search matrix to ensure the safety of the different robots in different map environments. The other one is the method that is to extend the obstacle boundary. This method combining with the size of the robot can set the safety distance arbitrarily and intuitively without increasing the difficulty of the algorithm, and it can effectively reduce the number of traversal grids in the search area and the search time.Note: in the following path planning diagrams, the red path is the planned path of the basic improved eight-way A∗ algorithm; the blue path is the smoothed planned path, which is the final path; the colored grid is all the traversal grids in the path planning process.The planned route is the planned route obtained in [29] using the 12-neighborhood search algorithm in Figure 5(a). The method can improve the search efficiency, and it also leads to the increase of the path length. The algorithm is designed with the path length as the primary priority and the search time as the secondary priority. In Figure 5(b), the red path is the improved eight-way A∗ algorithm planned path in this paper. The path is linked by the grid center point. The planned path can also achieve a safety distance to a certain degree. However, it is not flexible enough and cannot be set arbitrarily according to the robot map ratio.Figure 5
The comparison of the safety distance solutions. (a) Cross barrier search in [29]. (b) Extended obstacle boundary method in this paper.
(a)(b)It can be seen in Table3 that the improved A∗ smoothing algorithm adopts the search method of expanding obstacle boundary in this paper; compared with [29], the path length is shorter and the number of traversed grids is smaller. The number of the path inflection points that is a key indicator for evaluating the robot’s traveling path has also decreased 44.4%; the corresponding cumulative turning angle has decreased significantly; the path smoothness advantage is very obvious.Table 3
The comparisons of two safety distance search methods.
AlgorithmThe length of pathInflection pointsErgodic grid number12 neighborhood cross search algorithms in [29]224187957Extended barrier boundary method169.81103739


## 2.3.2. Impact Analysis of the Path Safety Distance

Although the constraint condition of safety distance is required in path planning, the design path is more suitable for robot walking. On the surface, the path designed by the algorithm should be as far away from the obstacles as possible, but when this safety distance is set too large, the path cannot be planned. As shown in Figure6, this paper has tested and analyzed the situations of the different safety distances.Figure 6
The effect of path planning at different safety distances. (a) No safety distance. (b) Safety distance 0.6 grid. (c) Safety distance 1 grid.
(a)(b)(c)In Figure6, the path planning test was performed on a map of 25×25 grid pixels for each without safety distance constraint, 0.6 grid safety distance, and 1.0 grid safety distance.According to the analysis in Table4, it can be found that when there is no safety distance, the planned path is the shortest; the number of inflection points is centered; the number of traversed grids is the largest; and the planning time is the longest. At 0.6 grid safety distance, the path length is 1.2% longer than the shortest path; the number of inflection points reduces by 50%; the number of traversal grids reduces by 62.6%; and the planned time reduces by 37.79%. 1.0 grid safety distance has the longest path length, the largest number of inflection points, and the shortest planned time. If the safety distance grid is set to 2.0, path planning cannot be completed.Table 4
Effect analysis of path planning for different safe distances.
AlgorithmThe length of pathDiscount pointsErgodic grid numberPlanning time (S)No safe distance37.1743610.44240.6 grid safe distance37.6221350.27491.0 grid safe distance39.9851350.2272Under the condition that the robot path planning guarantees a safe distance, the time spent in path planning can be ignored compared with the time saved by robot turning and fast passing. Therefore, it can be ensured that the second shortest path with the least number of inflection points and the smallest cumulative turning angle of the robot is the optimal path of the robot.


## 3. Autonomous Mobile Robot Warehouse Center Path Planning

After the algorithm design is completed, it needs to be verified in the actual map environment. Because the robot application environment is a structural layout space, the verification uses the warehouse center as the verification object, and the warehouse map is derived from Baidu Gallery. Robot path planning must first establish an accurate two-dimensional map of the environment space and then perform path planning.


### 3.1. Construction of Environmental Map for Warehouse Center

The map construction in the normal A∗ algorithm uses the method that directly creates a two-dimensional array in the program, as shown in Figure 7(a), and the produced grid map is shown in Figure 7(b). “0” in the array indicates that the open grid is in white, and “1” indicates that the obstacle is in black. Each “0” or “1” represents a grid, and the number of rows and columns of the two-dimensional array corresponds to the number of rows and columns of the grid map.Figure 7
The grid map creation. (a) Map array. (b) Corresponding grid map.
(a)(b)This representation method is flexible to change the map and is suitable for low-resolution map construction. For large-space and high-resolution maps, the two-dimensional array is huge and it is difficult to accurately match the actual space. For institutional spaces such as warehouse centers, accurate CAD drawings are generally available during construction, as shown in Figure8 (The Figure 8 from the Internet, the website is: http://www.51w2c.com/details_id_1347.html). The actual positions and absolute coordinates of various items are accurately marked on the drawings, and the positions will not basically change easily. Low-resolution grid maps in this scenario will cause large errors and cannot accurately reflect the precise coordinate positions of obstacles and feasible paths, and it is easy to make the planned path deviates from the actual path, causing the robot to excessively rely on obstacle avoidance function when it is traveling.Figure 8
Actual layout of a warehouse center.Aiming at the above problems, in order to improve the practicability of the system, this paper designs a drawing program by using Matlab’s composition conversion function. When the software is imported, we must first draw the warehouse center (Figure8) into one of the three formats bmp, jpg, and png according to the size proportion and position, as shown in Figure 9. Select the imported image in the GUI interface designed by Matlab, set the required horizontal axis resolution of the grid image, and complete the conversion according to the horizontal and vertical proportions of the original image.Figure 9
Binary map for warehouse center CAD.According to this step, the actual warehouse center shown in Figure8 is converted into the binary map of Figure 9 for the application scenario and imported into Matlab R2017a for experimental verification.In the scenario, the actual space of the CAD drawing of the warehouse center is 4476× 4000 cm. The two-dimensional space of the robot is 60 × 70 cm. The two-dimensional size of a single shelf is 60 × 200 cm. The road width between the shelves is 150 cm.The higher the resolution during the construction of the grid map, the smaller the error will be, but the time consumption with the system path planning will increase greatly. Therefore, there are three preliminary methods for setting the resolution:(1)
Take the two-dimensional space of the robot as the grid point size. The robot adopted a two-wheel differential turning method, and the width of the forward direction needs to be 60 cm. Taking this as the minimum resolution of the grid map, the resolution of the warehouse center grid map is 43× 48.(2)
Use shelf width as a reference and consider most path widths. It can be seen from the CAD drawing that the width of most of the auxiliary passages between the shelves is 150 cm, so the grid size of the storage center is considered to be 30 cm, and the resolution of the warehouse center grid map is 132× 149.(3)
According to the CAD map, the grid is drawn according to a certain proportion and the grid size is determined by the path planning time.The Matlab image conversion program design process is shown in Figure10.Figure 10
Grid map creation process.


### 3.2. Path Planning Verification

#### 3.2.1. Impact of Different Resolutions on Planning Time

Path planning experiments were performed on the grid maps designed to be constructed at multiple resolutions. The obtained data are shown in Table5.Table 5
Path planning time at different grid resolutions.
Safe distancePlanning time/(S)The length of pathDiscount pointsErgodic grid numberBody width0.4976194.4457780715 cm0.2711205.522846034It can be seen that the larger the number of grids on the same map, the higher the resolution, the smaller the spatial error of the map expression, but the longer the path planning time. When the number of grids is 132, the grid map can basically and accurately express the spatial layout of shelves and aisles in the warehouse center, and the planning time can be completed within 0.5S.


#### 3.2.2. Impact of Different Safety Distances on Planned Paths

At the same grid resolution, different safety distance settings will have a greater impact on path planning.The warehouse maps are set at different security distances and at the same 132 grid resolution, the obtained path planning results are shown in Figures11(a) and 11(b), and the specific experimental data are shown in Table 6.Figure 11
132 grid maps with different safety distance paths. (a) No safety space path. (b) 10 cm safety space path.
(a)(b)Table 6
Effects of different safety distances on grid path planning.
AlgorithmGrid size (cm)Safe distancePlanning time (S)6660.0Body width0.097513230.010 cm0.342120020.010 cm0.642940010.010 cm8.17728005.010 cm103.3154Figure11(a) shows the path planning without the safety distance. There are many cases where the path is close to the obstacles. The path planning passed the narrow section. The road width is only 2 grids, and the actual width is 60 cm; it is shown in the enlarged path of Figure 11(a); it is exactly the same as the width of the robot body. Obviously, the section of the robot is very difficult to pass or even unable to pass. The path planning has 7 inflection points, and the robot needs to perform steering actions multiple times. Both of these problems greatly affect the traveling time of robot.In Figure11(b), a grid closing to the obstacle is placed in the closed-list by expanding the obstacle area, and it is set to prohibit traversal. The method reserves a 15 cm safety distance between the robot path and the obstacles. Due to the introduction of the safety distance, the planned path has changed greatly compared with that in Figure 11(a). Because it is difficult for the robot to travel at high speeds in narrow sections, increasing the safety distance ensures that the robot travels on the secondary shortest path, but it ensures that the robot can travel at full speed and reduces turns. Compared with the path without safety distance, the number of turns of the path reduces by 42.8% and the planning time reduces by 44.91%.It can be seen that the correct and reasonable safety distance setting not only determines whether the algorithm can plan the correct path, but also can greatly improves the path optimization. Therefore, the path planning safe distance must be considered in practical applications.


## 3.1. Construction of Environmental Map for Warehouse Center

The map construction in the normal A∗ algorithm uses the method that directly creates a two-dimensional array in the program, as shown in Figure 7(a), and the produced grid map is shown in Figure 7(b). “0” in the array indicates that the open grid is in white, and “1” indicates that the obstacle is in black. Each “0” or “1” represents a grid, and the number of rows and columns of the two-dimensional array corresponds to the number of rows and columns of the grid map.Figure 7
The grid map creation. (a) Map array. (b) Corresponding grid map.
(a)(b)This representation method is flexible to change the map and is suitable for low-resolution map construction. For large-space and high-resolution maps, the two-dimensional array is huge and it is difficult to accurately match the actual space. For institutional spaces such as warehouse centers, accurate CAD drawings are generally available during construction, as shown in Figure8 (The Figure 8 from the Internet, the website is: http://www.51w2c.com/details_id_1347.html). The actual positions and absolute coordinates of various items are accurately marked on the drawings, and the positions will not basically change easily. Low-resolution grid maps in this scenario will cause large errors and cannot accurately reflect the precise coordinate positions of obstacles and feasible paths, and it is easy to make the planned path deviates from the actual path, causing the robot to excessively rely on obstacle avoidance function when it is traveling.Figure 8
Actual layout of a warehouse center.Aiming at the above problems, in order to improve the practicability of the system, this paper designs a drawing program by using Matlab’s composition conversion function. When the software is imported, we must first draw the warehouse center (Figure8) into one of the three formats bmp, jpg, and png according to the size proportion and position, as shown in Figure 9. Select the imported image in the GUI interface designed by Matlab, set the required horizontal axis resolution of the grid image, and complete the conversion according to the horizontal and vertical proportions of the original image.Figure 9
Binary map for warehouse center CAD.According to this step, the actual warehouse center shown in Figure8 is converted into the binary map of Figure 9 for the application scenario and imported into Matlab R2017a for experimental verification.In the scenario, the actual space of the CAD drawing of the warehouse center is 4476× 4000 cm. The two-dimensional space of the robot is 60 × 70 cm. The two-dimensional size of a single shelf is 60 × 200 cm. The road width between the shelves is 150 cm.The higher the resolution during the construction of the grid map, the smaller the error will be, but the time consumption with the system path planning will increase greatly. Therefore, there are three preliminary methods for setting the resolution:(1)
Take the two-dimensional space of the robot as the grid point size. The robot adopted a two-wheel differential turning method, and the width of the forward direction needs to be 60 cm. Taking this as the minimum resolution of the grid map, the resolution of the warehouse center grid map is 43× 48.(2)
Use shelf width as a reference and consider most path widths. It can be seen from the CAD drawing that the width of most of the auxiliary passages between the shelves is 150 cm, so the grid size of the storage center is considered to be 30 cm, and the resolution of the warehouse center grid map is 132× 149.(3)
According to the CAD map, the grid is drawn according to a certain proportion and the grid size is determined by the path planning time.The Matlab image conversion program design process is shown in Figure10.Figure 10
Grid map creation process.


## 3.2. Path Planning Verification

### 3.2.1. Impact of Different Resolutions on Planning Time

Path planning experiments were performed on the grid maps designed to be constructed at multiple resolutions. The obtained data are shown in Table5.Table 5
Path planning time at different grid resolutions.
Safe distancePlanning time/(S)The length of pathDiscount pointsErgodic grid numberBody width0.4976194.4457780715 cm0.2711205.522846034It can be seen that the larger the number of grids on the same map, the higher the resolution, the smaller the spatial error of the map expression, but the longer the path planning time. When the number of grids is 132, the grid map can basically and accurately express the spatial layout of shelves and aisles in the warehouse center, and the planning time can be completed within 0.5S.


### 3.2.2. Impact of Different Safety Distances on Planned Paths

At the same grid resolution, different safety distance settings will have a greater impact on path planning.The warehouse maps are set at different security distances and at the same 132 grid resolution, the obtained path planning results are shown in Figures11(a) and 11(b), and the specific experimental data are shown in Table 6.Figure 11
132 grid maps with different safety distance paths. (a) No safety space path. (b) 10 cm safety space path.
(a)(b)Table 6
Effects of different safety distances on grid path planning.
AlgorithmGrid size (cm)Safe distancePlanning time (S)6660.0Body width0.097513230.010 cm0.342120020.010 cm0.642940010.010 cm8.17728005.010 cm103.3154Figure11(a) shows the path planning without the safety distance. There are many cases where the path is close to the obstacles. The path planning passed the narrow section. The road width is only 2 grids, and the actual width is 60 cm; it is shown in the enlarged path of Figure 11(a); it is exactly the same as the width of the robot body. Obviously, the section of the robot is very difficult to pass or even unable to pass. The path planning has 7 inflection points, and the robot needs to perform steering actions multiple times. Both of these problems greatly affect the traveling time of robot.In Figure11(b), a grid closing to the obstacle is placed in the closed-list by expanding the obstacle area, and it is set to prohibit traversal. The method reserves a 15 cm safety distance between the robot path and the obstacles. Due to the introduction of the safety distance, the planned path has changed greatly compared with that in Figure 11(a). Because it is difficult for the robot to travel at high speeds in narrow sections, increasing the safety distance ensures that the robot travels on the secondary shortest path, but it ensures that the robot can travel at full speed and reduces turns. Compared with the path without safety distance, the number of turns of the path reduces by 42.8% and the planning time reduces by 44.91%.It can be seen that the correct and reasonable safety distance setting not only determines whether the algorithm can plan the correct path, but also can greatly improves the path optimization. Therefore, the path planning safe distance must be considered in practical applications.


## 3.2.1. Impact of Different Resolutions on Planning Time

Path planning experiments were performed on the grid maps designed to be constructed at multiple resolutions. The obtained data are shown in Table5.Table 5
Path planning time at different grid resolutions.
Safe distancePlanning time/(S)The length of pathDiscount pointsErgodic grid numberBody width0.4976194.4457780715 cm0.2711205.522846034It can be seen that the larger the number of grids on the same map, the higher the resolution, the smaller the spatial error of the map expression, but the longer the path planning time. When the number of grids is 132, the grid map can basically and accurately express the spatial layout of shelves and aisles in the warehouse center, and the planning time can be completed within 0.5S.


## 3.2.2. Impact of Different Safety Distances on Planned Paths

At the same grid resolution, different safety distance settings will have a greater impact on path planning.The warehouse maps are set at different security distances and at the same 132 grid resolution, the obtained path planning results are shown in Figures11(a) and 11(b), and the specific experimental data are shown in Table 6.Figure 11
132 grid maps with different safety distance paths. (a) No safety space path. (b) 10 cm safety space path.
(a)(b)Table 6
Effects of different safety distances on grid path planning.
AlgorithmGrid size (cm)Safe distancePlanning time (S)6660.0Body width0.097513230.010 cm0.342120020.010 cm0.642940010.010 cm8.17728005.010 cm103.3154Figure11(a) shows the path planning without the safety distance. There are many cases where the path is close to the obstacles. The path planning passed the narrow section. The road width is only 2 grids, and the actual width is 60 cm; it is shown in the enlarged path of Figure 11(a); it is exactly the same as the width of the robot body. Obviously, the section of the robot is very difficult to pass or even unable to pass. The path planning has 7 inflection points, and the robot needs to perform steering actions multiple times. Both of these problems greatly affect the traveling time of robot.In Figure11(b), a grid closing to the obstacle is placed in the closed-list by expanding the obstacle area, and it is set to prohibit traversal. The method reserves a 15 cm safety distance between the robot path and the obstacles. Due to the introduction of the safety distance, the planned path has changed greatly compared with that in Figure 11(a). Because it is difficult for the robot to travel at high speeds in narrow sections, increasing the safety distance ensures that the robot travels on the secondary shortest path, but it ensures that the robot can travel at full speed and reduces turns. Compared with the path without safety distance, the number of turns of the path reduces by 42.8% and the planning time reduces by 44.91%.It can be seen that the correct and reasonable safety distance setting not only determines whether the algorithm can plan the correct path, but also can greatly improves the path optimization. Therefore, the path planning safe distance must be considered in practical applications.


## 4. Conclusions

The shortest path cannot be as the judgment that the path is optimal for warehouse autonomous mobile fire-fighting robots in indoor structure space. It should also be based on the safety distance between the path and the obstacle to make the robot move at high speed, and the executive time is the shortest. Therefore, this paper improves the problems of the conventional A∗ algorithm in the path planning of autonomous mobile robots.In the design, Floyd algorithm and A∗ algorithm are fused by the inflection point priority strategy. Experiments show that the method can reduce the path optimization time and significantly reduces the total number of the path of the inflection points and the cumulative turning angle and thus shortens the path length and increases the smoothness of the path. Finally, the problem of safe path of all kinds of robots in different space is solved by expanded obstacles; the time of the path planning is reduced greatly; the path is optimized in many aspects; the planning efficiency and the algorithm practicability are improved.Although the method of the path planning has achieved good experimental results, there is still a long planning time in the process of high-resolution map path planning. In the next research, we will consider how to add new search heuristic functions and constraints, so as to improve the search efficiency of high-resolution grid map in complex environment and ensure the algorithm has better applicability.In the future, the fire-fighting ability of a single robot will not meet the demand for a large indoor space or a flammable environment. Therefore, we will also consider the cooperation and game of multirobots in this environment [35] and study the wireless mobile networking and anticollision theory of multirobots [36].



---

*Source: 6371814-2020-06-20.xml*