CN110975291B - Path extraction method and system - Google Patents

Abstract

The invention discloses a path extraction method and a system, wherein the method comprises the following steps: preprocessing the positions of grid points of collapsed jump points in the uniform grid map; acquiring a starting point and an end point; when an optimal composite main sequence path needs to be found between a starting point and a terminal point, generating a starting sub-node in the connecting process; reading the optimal direction and distance from each starting sub-node to the end point based on a compressed mode database in the path extraction process, and fusing the same parts among different paths to obtain a unique path from the start point to the end point through each starting sub-node; and comparing the path distances from the starting point to the end point through all the starting sub-nodes, and obtaining and storing the optimal path between the starting point and the end point. The method and the device are used for solving the problem that in the prior art, the search speed is limited under the condition that information is compressed in the preprocessing process to cause loss, and greatly improving the path planning speed.

Description

A path extraction method and system

Technical field

The invention relates to the technical field of artificial intelligence path planning, specifically a path extraction method and system for a compressed pattern database.

Background technique

In the field of artificial intelligence, robotics and computer game intelligence are regarded as comprehensive fields that model human perception, planning, decision-making and action capabilities in complex environments. In recent years, various types of robots have been widely used in production and life, and academia and industry have gradually paid more and more attention to computer game intelligence. Typical examples include the StarCraft game AI developed by the DeepMind team and the Dota game AI developed by OpenAI. As the basis of various technologies for robots and game non-player characters (NPC, Non-Player Characters), the shortest path planning technology based on uniform grids maps has been held with the GPPC (Grid-based Path Planning Competitions) competition and The industry's openness to typical map test sets has also made significant progress in the past decade. As a basic service, in the fields of classic heuristic search problem solving technology and map space topology extraction technology in artificial intelligence, limited computing resources in many scenarios need to respond to path planning requests of a large number of agents at the same time. Therefore, the rapid development of planning technology Responsiveness gets the most attention.

One of the most famous algorithms is called Jump Point Search (JPS), which was mainly proposed by Dr. Daniel Harabor of Monash University in Australia (Harabor D, Grastien A. Online GraphPruning for Pathfinding on Grid Maps[C]// National Conference on Artificial Intelligence.2011:1114–1119.Harabor D,Grastien A.Improving Jump Point Search[C]//International Conference on Automated Planning and Scheduling.2014.). When the agent moves on the grid map, JPS determines the diagonal movement priority path as the main partial ordering (diagonal-first canonical ordering) in the symmetrical path with the same starting point and end point and equal length, which will not satisfy this principle. All other paths are excluded from the search space. The theory proves that there is at least one shortest path that satisfies this rule between any two accessible locations. As shown in Figure 1, the child nodes eliminated by this partial ordering rule (shown in gray) can usually be reached by the parent node of the current node from a shorter path or a path of the same length but with earlier diagonal movement. Usually, such recursive use of pruning can leave only 1 or 0 child nodes of a node, which not only reduces the branching factor of the node being expanded, but also reduces the branching factor of the child node.

In addition, when JPS applies the A* algorithm, it does not add intermediate nodes to the Open table. Unless it encounters a node in Figure 1(c) that needs to extend the forward direction to other branches, such nodes are added to the Open table for later use. Extension. All intermediate nodes will be skipped, so the special nodes in Figure 1(c) are called "jump points".

The JPS algorithm only requires online processing and does not involve map preprocessing. Compared with the simple A* algorithm, the speed is increased by an order of magnitude. But one of its main disadvantages is that when expanding nodes, a large number of row-by-row and column-by-column scanning and judgment of intermediate nodes are required. Based on this, JPS+ calculates and stores the distance to the first jump point or obstacle reachable in that direction for each traversable direction of each traversable node in the offline stage. This pre-stored information further speeds up searches. Furthermore, JPS+(P) uses intermediate pruning technology during search, treating diagonal jump points as transition nodes and not adding them to the Open table for processing. Compared with JPS+, the number of Open table operations is reduced to a certain extent.

Through the combination with Compressed Pattern Databases (CPD) technology, the performance of JPS has been further greatly improved. CPD technology is a path planning technology based on preprocessing that trades space for time. In the offline stage, it initiates a Dijkstra search with each accessible node as the source, and finds outgoing edges for the current node that can reach all other connected nodes in the shortest path ( outgoing edge). If the data obtained by this preprocessing is represented by a matrix M, then M[i,j] represents the first edge originating from node i on the shortest path from the i-th node to the j-th node. In order to compress the storage space of this matrix, the SRC (Single-Row Compression) algorithm uses the RLE (Run-Length Encoding) method for data compression on each row (corresponding to each source node). Generally, a compression ratio of 300-400 can be obtained. (Strasser B, Harabor D, Botea A. Fast First-Move Queries through Run-LengthEncoding[C]//the Seventh Annual Symposium on Combinatorial Search.2014(SoCS):157–165.Strasser B, Botea A, Harabor D. Compressing Optimal Paths with RunLength Encoding[J].Journal of Artificial Intelligence Research,2015,54:593–629.). When performing path planning online, SRC searches the CPD for each current node from the starting point to its optimal movement to a given target point, thereby iteratively obtaining the complete shortest path. Each of these searches requires a binary search in the corresponding row of compressed data. SRC has become one of the fastest algorithms in the GPPC-2014 competition because it does not require online search of the A* algorithm at all.

The combination of JPS and SRC produces the Topping (Two-Oracle Path Planning) algorithm. The principle is to perform a binary search of CPD only on key nodes (such as starting points and jump points) to obtain the optimal direction, and at the same time access the distance table of JPS to obtain the corresponding The number of steps that can be repeated in the direction, thus eliminating redundant binary queries on intermediate nodes (Salvetti M, Botea A, Gerevini A, et al.Two-Oracle Optimal Path Planning on Grid Maps[C]//International Conference on Automated Planning and Scheduling. 2018(Sturtevant2012):227–231.). Because access to the JPS distance table is constant, the Topping algorithm improves path planning efficiency several times compared to SRC. It should be noted that, unlike SRC, the Dijkstra search in the preprocessing stage uses the diagonal-first partial order consistent with JPS to ensure the maximum benefit of the combination of the two, that is, to minimize the number of CPD queries. This pruning technology based on offline pre-computation improves the performance of the JPS+ and SRC algorithms by about an order of magnitude and several times respectively, enabling it to achieve microsecond-level search speeds under the classic test set. However, this significant improvement comes at the cost of investing a lot of CPU time and storage space in the pre-processing stage.

To reduce this cost, only the jump point locations need to be preprocessed. This processing will result in a certain degree of loss of algorithm preprocessing information. The main reason is that if the starting point is an ordinary node rather than a jump point, the algorithm cannot directly retrieve the first step moving direction on the optimal path from the starting point to the end point, so iteration cannot be used. Retrieval method. However, searching simply according to the JPS mode will significantly affect the search speed of the Topping algorithm.

Contents of the invention

The present invention provides a path extraction method and system based on compressed mode database pruning, which is used to overcome the shortcomings of the existing technology such as limited search speed when information is lost due to compression during the preprocessing process, and expands the starting point and During the exploration process, local exploration is achieved by merging and sharing the same paths, thereby eliminating the need for repeated exploration and extraction of the same paths, thus achieving a significant increase in search speed compared to existing technologies.

In order to achieve the above objectives, the present invention provides a path extraction method based on a compressed mode database, including:

Preprocess the grid point locations of the collapse jump points in the uniform grid map to generate a compression pattern database;

Get the starting and ending positions;

When it is necessary to find the optimal composite main sequence path between the starting point and the end point, the starting child node is generated during the connection process;

During the path extraction process, the optimal direction and distance from each starting sub-node to the end point are read based on the compression mode database, and the unique path from the starting point to the end point via each starting sub-node is extracted;

The overlapping parts of the paths from the starting point to the end point via all starting sub-nodes are fused to avoid repeated extraction. Finally, the optimal path between the starting point and the end point is obtained and stored through comparison between different paths.

In order to achieve the above object, the present invention also provides a path extraction system based on a compressed pattern database, including a memory and a processor. The memory stores a path extraction program based on the pattern database, and the processor runs the path extraction program based on the pattern database. The path extraction program executes the steps of the path extraction method based on the pattern database.

The present invention provides a path extraction method and system based on a compressed pattern database. The Topping+PEx (Path Extraction) algorithm of the present invention makes full use of the pattern database saved in the preprocessing stage at the jump point position. First, the starting point is found during the connection process. Node, in order to improve the efficiency of path extraction, the child nodes of the starting point (when generating the starting child node) can also be pruned to reduce the number of nodes that can be explored. On this basis, by extracting the path of each sub-node of the starting point according to the Topping method, a path to the target point can be obtained. In this process, the same parts (also called subpaths) between different paths are fused to reduce the search cost and obtain the only shortest path. Finally, by comparing the path lengths from the starting point to the end point via different starting sub-nodes, the shortest one is selected as the optimal path. The present invention will solve the problem of slow search speed in the prior art from the perspective of making full use of sparse preprocessed data and improve the path planning speed.

Description of the drawings

Figure 1(a) is a schematic diagram of pruning during diagonal movement in the non-hop scenario in the existing JPS technology;

Figure 1(b) is a schematic diagram of pruning during axial movement in the non-jump scenario in the existing JPS technology;

Figure 1(c) is a schematic diagram of pruning at the jump point position in the existing JPS technology;

Figure 2(a) is a schematic diagram of axial jump points in the path planning method provided in Embodiment 1 of the present invention;

Figure 2(b) is a schematic diagram of diagonal jump points in the path planning method provided in Embodiment 1 of the present invention;

Figure 3 is a schematic diagram of main sequence path classification in Embodiment 1;

Figure 4 is a flow chart of the main algorithm for CBD path planning in Embodiment 1;

Figure 5 shows the main process of path extraction by Topping+PEx in Embodiment 1;

Figure 6 is a flow chart for detecting the same path in Embodiment 1;

Figure 7 is an example diagram of pruning when the connection process generates a starting child node in Embodiment 1;

Figure 8 is an example diagram of the path extraction process in a scenario in Embodiment 1;

Figure 9 is an example diagram of the path extraction process in another scenario in Embodiment 1.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, rather than all the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without making creative efforts fall within the scope of protection of the present invention.

In addition, the technical solutions between the various embodiments of the present invention can be combined with each other, but it must be based on what a person of ordinary skill in the art can implement. When the combination of technical solutions is contradictory or cannot be realized, it should be considered that such a combination of technical solutions is possible. It does not exist and is not within the protection scope required by the present invention.

Embodiment 1

As shown in Figure 1, an embodiment of the present invention provides a path extraction method based on a compressed mode database, including:

S1 preprocesses the grid point locations of the collapse jump points in the uniform grid map to generate a compression mode database;

Jump points include axial jump points and diagonal jump points, which are defined as follows:

The axial jump point is: a passable point in the diagonal direction of the obstacle in the uniform grid map; it can move at least in the horizontal and vertical directions; an axial jump point (straight jump point) can be regarded as a triplet It contains a grid position n and two axial movement directions. They satisfy: (1)/> and/> are two passable moves; (2)/> (3)/> Impassable.

Intuitively, the grid position n in definition 1 is the corner of the obstacle, and the direction It is called the parent direction of the jump point and is the direction from which the search is coming. Take Figure 2(a) as an example. The solid circle and arrow represent the position and direction respectively. All axial jump points and corresponding parent directions are marked in the figure. It can be seen that n that meets the conditions generally has more than two attached axial jump point. Also, add/> and/> It is called the main sequence expansion direction of this jump point.

A diagonal jump point can be represented as a tuple It contains a grid position n and a diagonal direction/> Position n is determined by from/> direction of movement to reach and pass/> or/> Arrive at a certain location/> or/> It is the axial jump point in the parent direction, or reaches the target point.

Figure 2(b) shows the positional relationship between the diagonal jump point and the axial jump point. The hollow circle and gray arrow represent the position and direction respectively. It should be noted that the same axial jump point can be reached by multiple diagonal jump points at the same time, and even the same position may be reached by different diagonal jump points reaching a certain axial jump point at the same time. position, such as (D1/D2/D3,SW/SE).

The meaning of the grid point of the collapsed jump point here refers to: the same grid point position has at least parent nodes from two directions, the two directions come from: up, down, left, right, right up, right Any two of the bottom, upper left, and lower left, the jump point here can be an axial jump point, a diagonal jump point, or both an axial jump point and a diagonal jump point at the same time; if the same grid point collapses If the multi-directional jump point is reduced, the position will only be searched and calculated once, without repeated calculations;

As mentioned above, the position of the axial jump point can be quickly identified by scanning all grid points simply based on its relative position to the obstacle. However, we do not need to identify all diagonal jump points and perform bounding box calculations on them. Here, a distinction is made between two types of diagonal jump points.

An active diagonal jump point (active diagonal jump point) has an axial jump point As its parent node, where/> is the diagonal main sequence expansion direction of the axial jump point, n can have s passing through the barrier-free /> Mobile arrived. The remaining locations that do not meet this condition are passive diagonal jump points. For example, (F5, SE) in Figure 2(b) has (D3, E, S) as a parent node and is an active diagonal jump point. It can reach another axial jump point by moving eastward. (I5,E,N). And (E5,SE) is the passive diagonal jump point.

All paths that comply with the diagonal-first rule can be classified into two categories, as shown in Figure 3. The first category, which we call Simple Canonical Paths, does not involve search direction conversion at the jump point. The conversion here is from its parent direction to one of the canonical paths at an axial jump point. The sequence expansion direction, as shown in <s1,t1> in the figure, can be determined by a depth-first search during pathfinding. The second type is called Compound Canonical Paths, which can be expressed as <s,(d _s ),s ₁ ,(d ₁ ) _x1 ,s ₂ ,(d ₂ ) _x2 ,s ₃ ,…,s _n ,(d _t ),t>, as shown in the figure <s ₂ ,t ₂ >. This type of path can be divided into three parts: (1) The starting part: from the starting point s to the first axial jump point s ₁ , which may include a passive diagonal jump point d _s ; (2) The middle part: From the first axial jump point s ₁ to the last axial jump point s _n , there are x _i active diagonal jump points between two adjacent ones; (3) Ending part: from s _n to the end point t, May contain a passive hop.

It should be noted that some grid points have both axial and diagonal jump points attached;

The method of obtaining the axial jump point and the diagonal jump point can be implemented by a program according to the above definition, and the specific method is not limited. In one embodiment of the present invention, for example, the axial jump point is obtained by identifying the inflection point of the obstacle, that is, by identifying the positional relationship with the obstacle; the diagonal jump point can be obtained by identifying the positional relationship with the axial jump point. ;

The preprocessing search algorithm can be a compressed mode database search algorithm for preprocessing;

S2 obtains the starting and ending positions;

In one embodiment of the present invention, the grid point position where the intelligent robot is located or the grid point position where the movable object in the smart game is located forms the starting point here, and the specified grid point position input by the operator or player forms the end point.

When S3 needs to find the optimal composite main sequence path between the starting point and the end point, it generates a starting sub-node during the connection process; the meaning of the starting sub-node here refers to the axial jump from the starting point that complies with the diagonal priority principle. point; in the process of generating the starting sub-node, there may be more than one axial node that meets the starting sub-node requirements, and the above-mentioned axial sub-nodes can be used as the starting sub-node; in order to reduce unnecessary path planning, improve the path Planning speed, pruning is performed when generating the starting child node:

The starting child nodes are filtered according to the main sequence expansion direction of the data stored in the compression mode database and the starting child node, and the starting child node is only generated on the local path that is likely to reach the end position; for the impossible to reach the end position The path is pruned.

During the path extraction process, S4 reads the optimal direction and distance from each starting sub-node to the end point based on the compression mode database, and fuses the same parts between different paths to obtain the unique path from the starting point to the end point via each starting sub-node. path;

The different paths here refer to: there are multiple paths from different starting sub-nodes to the end point; for example, starting from different starting sub-nodes to explore the optimal path, if they meet at a certain sub-node, then the node after the meeting The path (the path from the encounter child node to the end point) is the same, then only the first path explored to the starting child node of the encounter child node is recorded, and later other starting child nodes are recorded from the encounter child node to the end point. Paths are no longer explored repeatedly; through the integration and sharing of the same paths, exploration space and time are reduced, and path planning speed is improved.

S5 compares the path distance from the starting point to the end point via all starting sub-nodes, obtains and stores the optimal path between the starting point and the end point.

Through distance comparison, we can determine which path is the optimal path. The distance can be calculated using methods such as coordinate difference or jump distance table.

Preferably, the step of preprocessing S1 with the grid position of the collapse jump point in the uniform grid map includes:

S01, perform structural analysis on the uniform grid map, identify all axial jump points based on the positional relationship between passable points and obstacle points; calculate jump distance tables for all passable directions of all passable nodes on the uniform grid map, and Record the distance to the next jump point or obstacle in that direction;

S02, identify all diagonal jump points according to the jump distance table of the axial jump point in the diagonal direction;

S03, use the collapsed position of each hop as the source node to conduct a Dijkstra search for the entire map to obtain the optimal starting edge for all reachable nodes; store and generate the optimal starting edge for all reachable nodes. Compressed mode database. The meaning of the optimal starting edge here is the optimal direction from the starting point to a certain end point. For any end point position, the optimal direction may be unique, or there may be two or three equivalent directions.

A collapsed position is a grid point that has at least two axial jump points and/or diagonal jump points attached to it. The starting edge here refers to the starting direction, and the eight directions in the eight-neighbor grid are used as the starting direction selection.

Preferably, the step of S3 generating a starting child node during the connection process includes:

When S30 generates the starting child node during the connection process, it prunes the path that is impossible to reach the end point by reading the compression mode database.

The step of S30 to prune the path that is impossible to reach the end point by reading the compression mode database when generating the starting child node during the connection process includes:

S301: Obtain all axial jump point child nodes of the starting point that comply with the diagonal priority principle according to the jump distance table;

S302: When all main sequence expansion directions of the axial jump sub-node do not intersect with the optimal direction of the node stored in the compression mode database, delete the legal axial jump sub-node;

S303: Traverse all the axial jump sub-nodes and obtain all pruned starting sub-nodes.

Although sparse preprocessing means that it is difficult to use the compressed mode database to prune from the starting point to reduce the number of child nodes at the starting point, once all legal child nodes are found, since they are all axial jump points, they can be used Existing schema database information undergoes deferred pruning. The algorithm flow is shown in Algorithm 1 in Figure 4.

The inputs to the algorithm are the starting point s, the end point t and the jump distance table T, with symbols Indicates that node n is in the direction /> distance value on. The algorithm traverses all eight directions and quickly obtains all possible child nodes through distance values (lines 3 and 13), of which the diagonal direction requires an iterative process (line 9). For these nodes that are not pruned through the schema database of the starting point, they can be pruned to a certain extent through their own schema database and main sequence expansion direction (lines 4-6, 14-16). If the set of all main order directions of a node does not intersect with the set of optimal directions retrieved by CPD, it can be safely removed from the search space and not added to the list to be explored; otherwise, the node should be considered. After this pruning process, only 1-2 child nodes can be left, which greatly reduces the search burden and is closer to Topping with complete information.

Preferably, the S4 reads the optimal direction and distance from each starting sub-node to the end point based on the compression mode database during the search process, and fuses the same parts between different paths to obtain the starting point through each starting sub-node. Among the steps of the only path to the end:

S41 When all main sequence expansion directions of the starting child node intersect with the optimal direction of the node stored in the compression mode database;

S42 reads the distance moved in the optimal direction to the next child node from the jump distance table of the node;

S43: When the current child node has not been explored; update the next node and return to the previous step S42 until the end is reached;

S44 extracts and obtains the unique path from the starting point to the end point via the starting sub-node;

S45 repeats the path exploration of all starting sub-nodes, and extracts the unique path from the starting point to the end point via each starting sub-node.

Refer to Algorithm 2 in Figure 5, which shows the main process of path extraction using Topping+PEx. It takes the starting point set of a small number of child nodes obtained in Algorithm 1 and the sparse pattern database obtained by preprocessing as input. It first initializes the data structure of the node: including setting the parent node and child node of all nodes to empty, and setting a Boolean flag bit. Indicates that the node has not been explored yet (line 1). Then set a global Boolean flag to indicate whether a path has been found. The algorithm traverses all starting point sub-nodes. If any branch can reach the target point, the flag pathFound is set to true (lines 13-14). In the extraction of each branch, the optimal direction of the current node to reach the target is retrieved from the CPD (line 6). If it is not empty, child nodes are generated according to the Topping mode (lines 7-9). In order to prevent the same subpath from being repeatedly explored and wasting algorithm running time, it needs to be detected (line 10).

Preferably, the step of S42 reading the distance to move to the next child node in the optimal direction from the jump distance table further includes;

S421 When the current child node is explored, compare the current path to the current child node with the explored path;

S422a When the explored path is better than the current path to the current child node, stop exploring the branch direction; and record the path from the starting point to the current node.

Preferably, when the current child node is explored, S421 further includes: after the step of comparing the current path to the current node with the explored path:

S422b When reaching the current child node is better than the explored path, modify the predecessor relationship and record the distance between the current node and the starting point;

The predecessor relationship here refers to changing the parent node that reaches the current child node in the explored path to the parent node that currently reaches the current child node, or that the parent node that reaches the current child node in the current exploration path is paid to the parent node in the explored path. Reaching the parent node of the current child node, that is, modifying the predecessor relationship of the current child node;

S423 and propagate the above information to subsequent nodes;

In S424a, when the subsequent path of the subsequent node has not been explored, the current branch direction returns to S42 and continues extraction until the end point is reached.

S424b ends the program when the subsequent node is the end point or reaches the end point directly.

Referring to Figure 6, this detection process is given in Algorithm 3, which is used to determine whether the extraction of the current branch should continue, in case the subsequent path has been explored in other branches or will be explored at a smaller path cost. This information is recorded in the identification variable subpathMeet. If the current child node c has not been explored by other branches, the algorithm updates it to the next node and returns (lines 1-5). On the contrary, if the current path to the node is not better than the path that has been explored, the current branch can be stopped (lines 7-10). If the current path is better, the relevant predecessor relationship and f-value need to be rewritten (lines 12-13, record the distance from the current child node to the starting point). The algorithm will also propagate this information to subsequent nodes (lines 26-27) until the following three situations occur: (1) The path from a subsequent node has not yet been explored, and the current branch needs to return to continue extraction (line 26-27). Lines 19-20); (2) If a subsequent node has been explored by another branch with a smaller cost path, the propagation should be stopped and the extraction of the current branch should be stopped (Lines 22-25); (3) The target point is reached (Line 28). In short, if subpathMeet is true after Algorithm3 runs, Algorithm 2 should stop path extraction of the current branch; otherwise, it should continue.

Figure 7 shows an example of the present invention implementing connection process pruning. The starting point and end point are F2 and J1 respectively. By extracting the effective distance values (shown in bold), all unpruned child nodes B0, F5 and H5 are quickly found. In the figure, their respective main sequence expansion directions and the optimal directions stored in the CPD are marked with gray and black short arrows respectively. It can be seen that only the main sequence expansion direction of H5 to the right coincides with the optimal direction, so both B0 and F5 are eliminated, and only one node, H5, is added to the Open table.

Figure 8 shows an example of the path extraction process in a scenario where none of the current child nodes have been explored (the same partial sub-path does not exist in the path), where the starting point and end point are A0 and A5 respectively. Through the connection process, the unique starting point child node B0 is generated. When extracting this branch, first read that the best direction to reach the target point from B0 is the lower right, and then read the distance table to know that the movement in this direction can take 2 steps to reach the diagonal jump point D2. At this time, the optimal direction to read from D2 to the target point is downward, and the number of steps is 3. By analogy, only one path can be extracted.

Figure 9 shows an example of the path extraction process in the scenario where paths starting from two different starting sub-nodes meet at a certain sub-node (the same part exists in the path, that is, the sub-path between the meeting sub-node and the end point). The two paths correspond to the two starting child nodes s ₁ and s ₁ ' respectively. If the branch represented by s ₁ ' is extracted first, when exploring the branch s ₁ , it will be found that the node has been explored at s ₂ . The comparison shows that the cost of branch s ₁ reaching s ₂ is smaller, so the parent node of s ₂ is updated from s ₁ ' to s ₁ , and the cost is propagated backward until the end point. No unexplored nodes are found in between.

As mentioned before, the number of two types of jump point collapse locations in a general grid map is much smaller than the total number of all accessible nodes. Therefore, the present invention will greatly save the required preprocessing time and space. Here, the general test set taken from https://movingai.com is used as the map, and its basic information is shown in Table 1. It contains both typical game maps and synthetic rooms and mazes. There are also a number of path planning test questions included with each map.

The experimental results are shown in Table 2. Among them, SRC and Topping are the original algorithms, and Topping+PEx is the present invention. We also added variations of Topping+WSSP and Topping+. The first one does not use starting child node pruning, and uses A* search for path finding instead of path extraction; the second one uses starting child node pruning but Still no path extraction is used. From the experimental results showing this deformation, it can be clearly seen that the two technologies of the present invention respectively improve the search speed. The results show that when the preprocessing information is relatively sparse, through the starting point sub-node pruning and partial expansion technology proposed by the present invention, the search speed of the Topping+PEx algorithm is improved several times compared with SRC, and is quite close to Topping. Basically On an order of magnitude. At the same time, through comparison with the two deformations of Topping+WSSP and Topping+, it can be seen that the adoption of starting sub-node pruning and path extraction methods significantly helps improve the path search efficiency. The former helps reduce the number of branches to be explored, and the latter reduces the frequent reordering of the Open table.

Table 1 Maps used in experiments

Table 2 Comparison of path search results. The metric is average search time in microseconds.

StarCraft DAO BG Warcraft Rooms Mazes SRC 42.0 16.5 15.8 22.4 37.3 52.1 Topping 16.2 5.8 5.0 6.0 15.5 44.9 Topping+WSSP 25.5 10.7 5.1 7.7 15.2 73.1 Topping+ 19.5 9.2 4.5 6.6 14.9 72.9 Topping+PEx 18.0 6.7 3.9 6.6 12.0 49.6

Embodiment 2

On the basis of Embodiment 1, this embodiment of the present invention provides a path extraction system based on a pattern database, including a memory and a processor. The memory stores a path extraction program based on the pattern database. When the processor runs the The steps of the method in any of the above embodiments are executed when the path extraction program is based on the pattern database.

The above are only preferred embodiments of the present invention, and do not limit the patent scope of the present invention. Under the inventive concept of the present invention, equivalent structural transformations can be made using the contents of the description and drawings of the present invention, or direct/indirect applications. Other related technical fields are included in the patent protection scope of the present invention.

Claims (7)

1. A path extraction method, comprising:

preprocessing the positions of grid points of collapsed jump points in the uniform grid map to generate a compressed mode database;

acquiring a starting point and an end point;

when an optimal composite main sequence path needs to be found between a starting point and a terminal point, generating a starting sub-node in the connecting process;

reading the optimal direction and distance from each starting sub-node to the end point based on a compressed mode database in the path extraction process, and fusing the same parts among different paths to obtain a unique path from the start point to the end point through each starting sub-node;

comparing the path distances from the starting point to the end point through all the starting sub-nodes, obtaining and storing the optimal path between the starting point and the end point;

the step of preprocessing the grid positions of the collapsed jump points in the uniform grid map comprises the following steps:

carrying out structural analysis on the uniform grid map, and identifying all axial jump points according to the position relation between the passable nodes and the barrier points;

calculating a jump distance table for all passable directions of all passable nodes on the uniform grid map, and recording the distance between the jump point and the next jump point or between the jump point and an obstacle in the direction;

identifying all diagonal jumping points by utilizing a jumping distance table in the diagonal direction according to the axial jumping points;

taking each jump point collapse position as a source node to perform Dijkstra search facing the full map, and acquiring the optimal initial edges, namely the optimal directions, of all reachable nodes; storing the optimal directions of all the reachable nodes to generate a compression mode database;

the step of reading the optimal direction and distance from each starting sub-node to the end point based on the compressed mode database in the path extraction process, and fusing the same parts among different paths to obtain a unique path from the starting point to the end point through each starting sub-node:

when the intersection exists between all main sequence expansion directions of the initial sub-node and the optimal direction of the node stored in the compressed mode database;

reading the distance of the next sub-node in the optimal direction from the jump distance table of the node;

when the current child node is not explored; updating the next node and returning to the previous step until reaching the end point;

extracting to obtain a unique path from the starting point to the end point through the starting sub-node;

and repeating the path exploration of all the initiator nodes, and extracting the unique path from the starting point to the end point through each initiator node.

2. The path extraction method of claim 1, wherein the step of generating the initiator node during the connection process comprises:

and when the initiator node is generated in the connection process, pruning paths which cannot reach the end point by reading the compressed mode database.

3. The path extraction method as claimed in claim 2, wherein the step of pruning paths unlikely to reach the end point by reading the compressed mode database when generating the initiator node in the connection process comprises:

obtaining all axial jump point child nodes of the starting point according with the diagonal priority principle according to the jump distance table;

deleting the axial jump point sub-node when the intersection does not exist between all main sequence expansion directions of the axial jump point sub-node and the optimal direction of the node stored in the compressed mode database;

and traversing all the axial jump point sub-nodes to obtain an initial sub-node.

4. The path extraction method as claimed in claim 1, further comprising, after the step of reading the distance moved in the optimal direction to reach the next child node from the jump distance table;

comparing the path reaching the current child node with the explored path when the current child node is explored;

stopping the optimal direction exploration when the explored path is better than the path reaching the current child node currently; and records the path from the start point to the current node.

5. The path extraction method of claim 4, wherein the step of comparing the current arrival current node path with the explored path when the current child node is explored further comprises:

when the current node reaches the child node and is better than the explored path, modifying the precursor relation and recording the distance between the current node and the starting point;

and the modified precursor relation and the distance between the current node and the starting point are transmitted to the subsequent nodes;

and when the subsequent path of the subsequent node is not explored, returning the current branch direction to the step of reading the moving distance reaching the next child node in the optimal direction from the jump distance table of the node, and continuing to extract until reaching the end point.

6. The path extraction method as claimed in claim 5, wherein said step of propagating said modified precursor relationship and a current node distance from a start point to a subsequent node further comprises:

and when the subsequent node is the end point, ending the extraction of the current branch.

7. A path extraction system comprising a memory and a processor, the memory storing a pattern database based path extraction program, the processor executing the steps of the method of any one of claims 1 to 6 when running the pattern database based path extraction program.