{'fraction_non_alphanumeric': 0.029543754674644727, 'fraction_numerical': 0.009473946646721515, 'mean_word_length': 4.498629198080877, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Path planning of intelligent mobile robot based on Dijkstra algorithm

Under the premise of grid environment modeling method, a relaxed Dijkstra algorithm is proposed to solve the problem of real-time path planning for mobile robot in large-scale and obstacle intensive working environment. Firstly, four neighborhood search is used to construct the Manhattan distance potential field from the source point to the global point in linear time, and then eight neighborhood search is performed from the target point to the source point to return a collision free and approximately optimal path. Matlab simulation results show that the algorithm is 10 times faster than dijksta algorithm and A-star algorithm, and the error of path length is within a reasonable range compared with the shortest path.


Introduction
Mobile robot path planning [1] is to determine a collision free path for the robot from the starting point to the end point according to certain optimization criteria (usually using distance), such as distance, time and energy. Under constraints such as large working space and dense barriers, path planning problem has been proved to be NP problem [2].
Usually, path planning begins with modeling the working environment of mobile robots, namely map construction. Map construction [3] is divided into road marking method and grid method. The former is to construct a feasible path diagram of the robot composed of marks and connecting edges, such as viewable method and tangent method. The construction process is complex, the accuracy is low, and it is not suitable for the environment with large working space and dense obstacles. The latter is mainly to discretize the environment into regular basic units. Its discrete property is convenient for map construction, but it is difficult to complete real-time and high precision path planning on raster maps with large grid scale and dense obstacles.
Based on the grid environment modeling method, there are many methods for mobile robot path planning. The classical graph search algorithms include Dijkstra algorithm, a * algorithm and so on. This kind of algorithm is accurate and can get the optimal solution, but with the expansion of the grid size, the computational efficiency is low. Harabor et al. [6] proposed the jump point search method to speed up a * algorithm, but the speed increase degree will depend on the landform of the basic grid map. If these maps are characterized by large open areas, this method can make the speed increase of a * algorithm higher, if not, the speed increase is moderate [7]. The relaxed Dijkstra algorithm proposed by  [8] Based on the structural characteristics of raster map has the possibility of many unnecessary broken lines and large error in the worst case. In addition, artificial intelligence path planning technology represented by evolutionary computing has also been developed rapidly. Evolutionary computing is a kind of self-adaptive optimization probability search algorithm which simulates the theory of biological evolution. It mainly includes genetic algorithm [9], ant colony algorithm [10], particle swarm optimization algorithm [11], artificial bee colony algorithm [12], etc. but the research of this kind of algorithm is mostly limited to small-scale working environment, and it is difficult to carry out real-time and effective path planning in large-scale working environment. Alajla et al. [13] proved the effectiveness of genetic algorithm for global path planning in large-scale grid environment when distance was used as the evaluation criterion, but the computational efficiency was not considered.
In order to solve the problem of real-time path planning for mobile robot in large-scale and obstacle intensive working environment, a new relaxed Dijkstra algorithm (rdj algorithm) is proposed in this paper. Firstly, the grid method is used to model the working environment, and then the rationality of rdj algorithm is elaborated and analyzed. Finally, the experimental comparison and analysis results are given to verify its effectiveness.

Grid modeling
Grid method was first proposed by W.E. Howden in 1968. Its core idea is to transform the working environment of mobile robot into a binary matrix, in which the basic element values of the matrix are only 0 and 1. 0 represents the area that the mobile robot can pass through, and 1 represents the obstacle area. In Matlab environment, you can see the working environment represented by grid method more intuitively, as shown in Figure 1, s represents the starting point, e represents the end point. The search of collision free path from s to e needs to follow certain search rules. The algorithm used in this paper needs to use four neighborhood search ( Fig. 2 (a)), and the cost of moving from s point to all directions is 1. After traversing the whole region, eight neighborhood search ( Fig. 2 (b)) is used to get the path. The horizontal and vertical moving cost is 1, and the diagonal moving cost is √2. When using eight neighborhood search to obtain the path, in order to ensure the shortest path and the safety and reliability of the path, there are three cases in diagonal path selection, as shown in Fig. 3, in which the solid line is passable and the dotted line is not passable.

RDJ algorithm and its implementation
In graph theory, DJ algorithm is one of the classic algorithms to find the shortest path. For a connected weighted graph with n vertices, the time complexity of single source shortest path algorithm is O (n 2 ), which can reduce the time complexity of DJ algorithm by using more efficient data structure. Barbehen et al. [14] used heap sorting algorithm to reduce the time complexity of DJ algorithm to ( + ( )), but it is still difficult to meet the requirements of real-time path planning. Bucket sorting [15] can sort uniform data in linear time, but if the data is not uniform, it will not only reduce the efficiency of the algorithm, but also cause a great waste of storage space.

Design of node expansion mechanism
DJ algorithm belongs to the algorithm of finding the shortest path from a single source point, and the final result is the shortest path from each node to the source point. In the process of node expansion, there are two important operations: one is to relax each node; the other is to find a node with the smallest distance from the source point from the OPEN list as a new expansion node in each iteration, and delete it from the OPEN list as an expanded node and insert it into the CLOSE list. In this process, it is the most time-consuming to extract the node with the smallest distance from the OPEN list to the source point. In order to reduce the time consumption of DJ algorithm, we can design a new node expansion mechanism to avoid the above two operations.
On the basis of environment modeling based on grid method, the algorithm adopts four neighborhood search ( Fig. 2 (a)). Assuming that point s is the starting point, we can see that the distance from the four nodes extending from point s to s is 1, and then add the four nodes to the OPEN list respectively. Then, select a node from the OPEN list with the smallest distance to s point. At this point, it can be found that each node can be used as the next expansion node, so it will be redundant to select the node with the smallest distance to s point from the OPEN list. Therefore, four nodes can be regarded as the next expansion nodes in a certain order, that is, the breadth first search algorithm can be used to expand the nodes. The algorithm idea of the extension mechanism is described as follows: Input:binary matrix (working environment); Starting point s Output: L(x) (Manhattan distance from each node x to s) 1) L(x) = 0, the obstacle node set is O; 2) All nodes and x ≠ s, L(x) = ∞; 3) Insert s point into the end of Q queue; 4) When Q is not empty, get the team head node v of Q; 5) For all four nodes x, x ∉ Q and x ∉ O adjacent to v, find L(x) = L(V) + 1, insert x into the end of queue Q, and return 4).
According to the algorithm described above, the Manhattan distance potential field from each vertex x to s in Figure 1 can be obtained, as shown in Fig. 4. In addition, this algorithm is different from DJ algorithm in that it does not consider marking the parent node of the node to be extended when extending the node. When the traversal of all extensible nodes is completed, the shortest path from each point to  Fig. 4 that if e point is taken as the target point and Manhattan distance is taken as the path evaluation standard, there are many possible shortest paths from e point to s point (line in Fig. 4), so this method can not meet the requirements of actual path planning.  Fig. 4 is 2. When the change rate of the path along the diagonal direction is 2, it means that the path in this direction is closer to the starting point, and in the actual moving process, if the robot moves along the diagonal direction, its moving cost is 2 − √2 times lower than that along the horizontal or vertical direction. According to the Manhattan distance potential field, a more effective reverse eight neighborhood search algorithm is obtained. The algorithm is described as follows Input: Manhattan distance potential field from source point to each point Output: approximate shortest path from point e to s 1) v = e; 2) When v ≠ s, find all the eight adjacent nodes x of v; 3) Compare 8 nodes L(x), get the smallest node x and store x; 4) v = x, returns 2). In essence, the algorithm uses the principle of greedy algorithm to construct the global optimal solution by selecting the local optimal solution. It can be seen from Figure 5 that a shortest path can be obtained from point e to point s, and its length is about 10 + 10√2. Compared with the path in Fig. 4, its length is reduced by 20 − 10√2. If the Manhattan distance from the source point to the target point is p, the path length returned by the algorithm is in the following range: (1)  Figure 5. Eight neighborhood reverse search path

Path length error analysis
From point e to point s, the shortest path obtained by using DJ algorithm for eight neighborhood search is consistent with the length of the path obtained in Fig. 5, but this does not prove that the path obtained by using RDJ algorithm is the shortest path. In fact, RDJ algorithm is defective. In the process of eight neighborhood reverse search, the change rate of the algorithm will be equal in two directions, as shown in Fig. 6(a). At this time, the change rate of the direction from point e to the left or down is the same, but in fact, the distance from the left to point s is shorter than that from the down to point s, which is also the case of the largest error. In Fig. 6(a), the Manhattan distance of the target point is p = 10, and the maximum error between the path length obtained by RDJ algorithm and the shortest path length is as follows: (2) In order to avoid the maximum error, it is necessary to improve the algorithm. When the change rates of the two directions are equal, the algorithm accepts either direction with equal probability, which avoids the situation of large error to a certain extent. However, when the case in Fig. 6(b) (P = 10) occurs, the error cannot be avoided. In this case, the maximum error is: The two cases in Fig. 6 are special cases when errors occur. Equations (2) and (3) are error analysis for the above two special cases, which are not general. In the actual working environment of mobile robot, the global environment as shown in Fig. 6 is rare, and the simulation experiment also proves that the errors caused by these two situations are in a reasonable range.

Analysis of algorithm time complexity
The RDJ algorithm in this paper is different from the DJ algorithm in two aspects. First of all, in the expansion mode of search node, the relaxation operation and optimization are abandoned, and the expansion is carried out according to the order of inserting the OPEN table, in which the OPEN table is implemented by circular queue. The basic operation of OPEN table is only insert and delete. In the circular queue, the time complexity of insert and delete is O(1). Therefore, RDJ algorithm only needs O(n) time to traverse the whole search space. Secondly, DJ returns a shortest path along the marked parent-child node, while RDJ uses the idea of greedy algorithm to search for the node with the shortest distance from the starting point in the range potential field. The time complexity of this process is less than O(n). In conclusion, the time complexity of RDJ algorithm is O(n).

Experimental comparison and analysis
In order to verify the effectiveness of RGJ algorithm, it is compared with the classic DJ algorithm and A* algorithm in terms of running time and path length. The simulation tools are: Visual Studio 2010, Matlab2010b, the algorithm running platform is Windows 7 system, Intel Core I3 processor (2.53 GHz), memory is 2 GB. The map environment of the algorithm is random distribution of obstacles (hereinafter referred to as random, with 30% obstacle coverage), maze and warehouse, as shown in Fig. 7. The map scale is divided into 25 × 25, 50 × 50, 100 × 100 grid. Among them, in order to speed up the program running speed, in the data structure, the open table of classic DJ algorithm and A* algorithm is based on binary heap priority queue, and is implemented by mixed programming of C++ and MATLAB. In the process of the experiment, the three algorithms are run 100 times on each map, in which the starting point of each map is selected at the bottom left, and the ending point is selected at the top right.   table 1 illustrates the environment, no matter in what kind of map RDJ algorithm in minimum time, maximum time consuming, the average time on the value is the smallest, the average speed is higher than DJ algorithm and A* algorithm for at least 10 times, especially with the expansion of map RDJ computational efficiency, the more obvious advantages, This fully proves the rationality of the algorithm in computational efficiency.
As for the path length, the RDJ algorithm has its own defects in searching the shortest path, which leads to the instability of the path length obtained in the process of searching the path. Therefore, the minimum length, maximum length and average length of the experimental results are listed respectively and compared with the shortest path obtained by DJ and A* algorithm. It can be seen from Table 2 that on relatively small scale maps (grid size 25 × 25, 50 × 50), the error of RDJ algorithm in the minimum, maximum and average path length is small, and the maximum error is only 1.27%.On a relatively large scale map (grid size 100 × 100), the error of path length obtained by RDJ algorithm is small in labyrinth and warehouse maps, but large in random environment, with the maximum error of 9.14%.From the perspective of the minimum error of different maps, RDJ algorithm can find the shortest path in the experimental map environment. Overall, the RDJ algorithm performed best in warehouses and mazes.
To sum up, compared with DJ and A* algorithm, RDJ algorithm has A qualitative improvement in operation time. Although the RDJ algorithm has errors in the path length, it is also within the acceptable range.

Concluding remarks
Based on the raster modeling method and the structural characteristics of raster map, this paper proposes a RDJ algorithm. The simulation experiment proves that the algorithm can effectively realize the realtime path planning of mobile robot in the working environment with large scale and dense obstacles. On the basis of this method, there are two aspects that need to be done in the next step: 1) to further improve the algorithm to maximize the error control of the shortest path;2) At present, the research on this algorithm is only in the software simulation stage. Next, it is necessary to use Pioneer robot [16] to run this algorithm in the actual working environment (such as warehouse) to verify its effectiveness.