[go: up one dir, main page]

CN110975288A - Geometric container data compression method and system based on jumping point path search - Google Patents

Geometric container data compression method and system based on jumping point path search Download PDF

Info

Publication number
CN110975288A
CN110975288A CN201911138925.1A CN201911138925A CN110975288A CN 110975288 A CN110975288 A CN 110975288A CN 201911138925 A CN201911138925 A CN 201911138925A CN 110975288 A CN110975288 A CN 110975288A
Authority
CN
China
Prior art keywords
point
jumping
axial
diagonal
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201911138925.1A
Other languages
Chinese (zh)
Other versions
CN110975288B (en
Inventor
胡越
鞠儒生
许凯
秦龙
彭勇
焦鹏
杨妹
唐见兵
段红
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
National University of Defense Technology
Original Assignee
National University of Defense Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by National University of Defense Technology filed Critical National University of Defense Technology
Priority to CN201911138925.1A priority Critical patent/CN110975288B/en
Publication of CN110975288A publication Critical patent/CN110975288A/en
Application granted granted Critical
Publication of CN110975288B publication Critical patent/CN110975288B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • A—HUMAN NECESSITIES
    • A63—SPORTS; GAMES; AMUSEMENTS
    • A63F—CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
    • A63F13/00—Video games, i.e. games using an electronically generated display having two or more dimensions
    • A63F13/50—Controlling the output signals based on the game progress
    • A63F13/53—Controlling the output signals based on the game progress involving additional visual information provided to the game scene, e.g. by overlay to simulate a head-up display [HUD] or displaying a laser sight in a shooting game
    • A63F13/537—Controlling the output signals based on the game progress involving additional visual information provided to the game scene, e.g. by overlay to simulate a head-up display [HUD] or displaying a laser sight in a shooting game using indicators, e.g. showing the condition of a game character on screen
    • A63F13/5378—Controlling the output signals based on the game progress involving additional visual information provided to the game scene, e.g. by overlay to simulate a head-up display [HUD] or displaying a laser sight in a shooting game using indicators, e.g. showing the condition of a game character on screen for displaying an additional top view, e.g. radar screens or maps
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/20—Instruments for performing navigational calculations
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D30/00—Reducing energy consumption in communication networks
    • Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Optics & Photonics (AREA)
  • Automation & Control Theory (AREA)
  • General Physics & Mathematics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

一种基于跳点路径搜索的几何容器数据压缩方法，第一步：对均匀网格地图进行结构分析，识别出所有轴向跳点，生成轴向跳点集；第二步：根据轴向跳点集识别出所有有源对角跳点，生成有源对角跳点集；第三步：分别以生成的所有轴向跳点和所有有源对角跳点塌缩的位置为源节点搜索整个所述均匀网格地图，针对每个塌缩位置进行几何容器标识预处理，以完成任意两个可通行节点之间的最优路径搜索。一种基于本发明所述方法的系统：包括存储器和处理器，所述存储器存储有均匀网格地图和跳点路径搜索的几何容器数据压缩程序，所述处理器在运行所述跳点路径搜索的几何容器数据压缩程序时执行所述方法的步骤。

Figure 201911138925

A method for compressing geometric container data based on jump point path search. The first step is to analyze the structure of a uniform grid map, identify all axial jump points, and generate an axial jump point set; the second step: according to the axial jump points The point set identifies all active diagonal jump points, and generates an active diagonal jump point set; the third step: search for the source node with all the generated axial jump points and the collapsed positions of all active diagonal jump points respectively. For the entire uniform grid map, geometric container identification preprocessing is performed for each collapsed position, so as to complete the optimal path search between any two passable nodes. A system based on the method of the present invention: comprising a memory and a processor, the memory stores a uniform grid map and a geometric container data compression program for hop path search, the processor is running the hop path search The steps of the method are performed when a geometry container data compression program is used.

Figure 201911138925

Description

Geometric container data compression method and system based on jumping point path search
Technical Field
The invention has the basic application field of robot navigation and rapid path planning of an agent in game artificial intelligence, and mainly relates to the technical field of classical heuristic search problem solving technology, map space topological structure extraction technology and the like in artificial intelligence.
Background
As the basis of various technologies of robots and game non-player characters, limited computing resources in many scenarios need to simultaneously respond to path planning requests of a large number of agents, so that the rapid response capability of the planning technology is most concerned.
One of the most well-known algorithms is known as Jump Point Search (JPS). When the intelligent agent moves on the grid map, jumping points are searched in symmetrical paths with the same starting point and end point and the same length, the diagonal movement priority path is determined as a main partial sequence, and all other paths which do not meet the principle are removed out of a search space. When the jump point search applies the A-algorithm, intermediate nodes are not added into the Open table, and unless a node needing to expand the forward direction to other branches is encountered, the node is added into the Open table to be expanded. The jumping point search algorithm only needs on-line processing and does not relate to map preprocessing, and compared with a simple A-x algorithm, the speed is improved by one order of magnitude.
The main disadvantage of the skip point search is that a large amount of intermediate node scanning and judgment row by row and column by column is required when the node is expanded. An improvement as a skip point search is JPS +, JPS + calculating and storing, at the offline stage, for each passable direction of each passable node, the distance to the first skip point or obstacle reachable through that direction. This pre-stored information further increases the search speed. Furthermore, JPS + (P) adopts a transfer node pruning technology during searching, diagonal jump points are regarded as transition nodes, and the Open table is not added for processing, so that the operation times of the Open table are reduced to a certain extent compared with JPS +.
The performance of the jumping point search is further and greatly improved by combining with the pruning technology of the Geometric Containers (Geometric Containers). Geometric container pruning is a class of target-directed acceleration techniques used to prune edges that are unlikely to lead a current node to a target location via a shortest path during a search phase, where the simplest and most efficient version of geometric containers is called rectangular Bounding Boxes (Bounding Boxes). The jumping point searching method combined with the bounding box technology is called JPS + BB for short.
In the off-line stage, JPS + BB initializes a blank rectangular box for each edge in the graph, and then runs Dijkstra algorithm using diagonal shift-priority order from each passable node to cover all nodes passing through the Dijkstra algorithm. When the Dijkstra algorithm is extended to a certain node, it is added to the rectangular box of the corresponding edge of the source node. When all the nodes are preprocessed, a rectangular area surrounding all the nodes reachable through the optimal diagonal movement priority path is formed for each edge, although redundant nodes may be included because of the simple shape.
The pruning technology based on offline pre-calculation improves the performance improvement of about one order of magnitude for the JPS + algorithm, so that the average searching speed of tens of microseconds can be obtained under a classical test set. However, this significant improvement comes at the cost of having to invest a significant amount of CPU time and memory space in the preprocessing stage. JPS + BB requires a revised Dijkstra search to be performed between all pairs of accessible points. Assuming that a grid map contains n passable nodes, the time and space complexity of the algorithm is O (n)2) I.e. quadratic complexity. From experimental results, it usually takes about ten hours and hundreds of megabytes of memory to complete the computation of a 1024 x 1024 scale StarCraft map. Such a cost is unacceptable in applications where the CPU time and memory space specified for path planning is limited, as is typical in robotic navigation and gaming AIThe scene (2).
At present, no research result can realize ultra-fast search speed on the premise of acceptable preprocessing cost. Therefore, the invention aims to solve the problem of severe map preprocessing complexity faced by the JPS + BB algorithm by utilizing the map space structure analysis.
Disclosure of Invention
The present invention is based on the basic observation that only the number of all the waypoint locations in the map is much smaller than the number of all the passable nodes, so that if Dijkstra search is initiated from all the waypoints only, the overhead of preprocessing in both space and time will be greatly reduced.
A geometric container data compression method based on jumping point path search comprises the following specific steps:
s1, carrying out structural analysis on the uniform grid map, identifying all axial jumping points, and generating an axial jumping point set;
s2, identifying all active diagonal skip points according to the axial skip point set, and generating an active diagonal skip point set;
and S3, searching the whole uniform grid map by taking the generated grid positions where all axial jumping points and all active diagonal jumping points are collapsed as source nodes, and performing geometric container identification preprocessing on each collapsed position to complete the optimal path search between any two passable nodes.
The S1 axial jumping point identification step comprises the following steps:
s11, scanning all nodes in the uniform grid map, and identifying obstacle points in all nodes;
s12, obtaining feasible diagonal nodes of all barrier points;
s13, when two public neighborhood nodes including the obstacle point and the feasible diagonal node of the obstacle point are passable nodes, identifying the feasible diagonal node of the obstacle point as an axial jump point;
and S14, repeating the step S13 to obtain all axial jumping points in the uniform grid map.
In step S2, the active diagonal hop has an axial hop as its parent node, and the active diagonal hop is reached by the axial hop through barrier-free movement.
The active diagonal jumping point identification method comprises the following steps:
s21, calculating an axial jump distance table of all passable nodes on the uniform grid map, wherein the table shows the distance from each passable node to other axial jump points or obstacles in the axial direction;
s22, calculating a diagonal jump distance table of all passable nodes on the uniform grid map, wherein the table shows the distance from each passable node to other passable nodes in the diagonal direction;
and S23, traversing by taking each axial jumping point as a source, repeatedly reading the diagonal distance of the current node, wherein the diagonal distance is positive, which indicates that the diagonal movement can be converted into the axial movement at the position, so as to reach the axial jumping point, and then judging that the current node is the active diagonal jumping point.
The uniform grid map rectangular bounding box pre-calculation method in the S3 of the invention comprises the following steps:
s31, traversing the axial jumping point set and the active diagonal jumping point set, and initializing a rectangular bounding box for each edge of the grid position where the axial jumping points and the active diagonal jumping points are collapsed in the set;
s32, searching the full map by taking the current jump point as a source node, recording the initial edge of a path from the source jump point to the node every time a node is generated in the searching process, and pressing the node into an Open table;
s33, when the optimal path from the source jumping point to the node is found, the node is taken out from the Open table for expansion, and the node is added into the bounding box of the corresponding edge of the source node;
and S34, when the Open table is empty, ending the search of the current jump point, and entering the search of the grid position of the next axial jump point and the collapse of the active diagonal jump point.
In step S33 of the present invention:
a source node to a target node can correspond to a plurality of optimal paths, all the optimal paths are recorded, and finally the target node is added into all the rectangular bounding boxes meeting the conditions.
A system based on the method of the invention:
the method comprises a memory and a processor, wherein the memory stores a uniform grid map and a geometric container data compression program for jumping point path search, and the processor executes the steps of the method according to any one of claims 1 to 6 when the geometric container data compression program for jumping point path search is run.
The invention can achieve the following technical effects:
the invention solves the problem of severe map preprocessing complexity by carrying out structural analysis and geometric container identification pre-calculation on the uniform grid map. The uniform grid map is subjected to structural analysis to identify axial jumping points and active diagonal jumping points, geometric container pretreatment is carried out on grid positions where the axial jumping points and the active diagonal jumping points are collapsed, and pretreatment cost of the uniform grid map is greatly reduced. In an optimal path with prior diagonal movement, except for a starting point and an end point, other key nodes are axial jumping points and active diagonal jumping points. Therefore, only the positions are preprocessed, and when the route is searched, the starting point is connected to the adjacent axial jumping point, and the route searching can be successfully completed.
Drawings
FIG. 1 is a schematic diagram illustrating a principal sequence path classification of a geometric container data compression method and system based on a skip point path search according to the present invention;
FIG. 2 is an example of a geometric container data compression method and system distance table based on a jumping-point path search according to the present invention;
FIG. 3 is a schematic diagram of an equivalent main sequence path of a geometric container data compression method and system based on a jumping point path search according to the present invention;
fig. 4 is a view of the geometric container data compression method and system StarCraft map set therfrozenseamap map based on the skip point path search of the present invention.
Detailed Description
A geometric container data compression method based on jumping point path search comprises the following specific steps:
s1, carrying out structural analysis on the uniform grid map, identifying all axial jumping points, and generating an axial jumping point set;
the axial jump point can be regarded as a triad
Figure BDA0002280335900000061
Which contains one grid position n and two axial directions of movement. One grid position and two axial directions of movement satisfy: (1)
Figure BDA0002280335900000062
and
Figure BDA0002280335900000063
are two moves that can be moved in a row; (2)
Figure BDA0002280335900000064
(3)
Figure BDA0002280335900000065
is not accessible.
Grid position n is the corner of the obstacle and direction
Figure BDA0002280335900000066
The parent direction, called the hop point, is the direction of the search. Eligible n typically have more than two axial jumps attached, and therefore have more than two parent directions. Will be provided with
Figure BDA0002280335900000067
And
Figure BDA0002280335900000068
referred to as the main sequence spreading direction of the axial jump point.
S2, identifying all active diagonal skip points according to the axial skip point set, and generating an active diagonal skip point set;
a diagonal jump point can be represented as a doublet
Figure BDA0002280335900000071
Comprising a grid position n and a diagonal direction
Figure BDA0002280335900000072
Position n is derived from
Figure BDA0002280335900000073
The direction of movement reaches and can pass
Figure BDA0002280335900000074
Or
Figure BDA0002280335900000075
To arrive at a certain position
Figure BDA0002280335900000076
Or
Figure BDA0002280335900000077
Is an axial jump point in the parent direction, or reaches a target node. The same axial jump point can be reached by a plurality of diagonal jump points at the same time, even different diagonal jump points can be attached to the same position at the same time, and the same axial jump point can be reached by the same axial jump point.
An active diagonal jump point
Figure BDA0002280335900000078
Is provided with an axial jumping point
Figure BDA0002280335900000079
As its parent node, wherein
Figure BDA00022803359000000710
Is the extension direction of the diagonal main sequence of the axial jump point, and n can pass through s without obstacles
Figure BDA00022803359000000711
The direction movement arrives. The remaining diagonal hops that do not satisfy this condition are passive diagonal hops.
All paths that comply with the diagonal movement preference rules can be categorized into two categories. The first type, as shown in FIG. 1, is a simple main sequence path, as in FIG. 1<s1,t1>As shown, the search direction conversion at the jumping point position is not involved, and the optimal path can be judged through one-time depth-first search when being searched. The second type is called the composite main-order path and can be represented as<s,(ds),s1,(d1)x1,s2,(d2)x2,s3,…,sn,(dt),t>As in FIG. 1<s2,t2>As shown, it can be divided into three parts: (1) the initial part is as follows: from the starting point s to the first axial jump point s1Possibly including a passive diagonal jump ds(ii) a (2) The middle part: jumping from the first axial direction s1To the last axial jump point snWith x between two adjacentiActive diagonal skip points; (3) ending part: from snTo the end point t, a passive jump point may be included.
And S3, searching the whole uniform grid map by taking the generated grid positions where all axial jumping points and all active diagonal jumping points are collapsed as source nodes, and performing geometric container identification preprocessing aiming at each collapsed position to complete the optimal path search between any two passable nodes.
The reason for geometric container preprocessing for collapsed grid positions is: the total number of the collapse positions of the jumping points is far smaller than the total number of the passable nodes in the map, so that the preprocessing cost is greatly reduced; in an optimal path with prior diagonal movement, except for a starting point and an end point, other key nodes are axial jumping points and active diagonal jumping points. Therefore, only the positions are preprocessed, and when the route is searched, the starting point is connected to the adjacent axial jumping point, and the route searching can be successfully completed.
The S1 axial jumping point identification step comprises the following steps:
s11, scanning all nodes in the uniform grid map, and identifying obstacle points in all nodes;
s12, obtaining feasible diagonal nodes of all barrier points;
s13, when two public neighborhood nodes including the obstacle point and the feasible diagonal node of the obstacle point are passable nodes, identifying the feasible diagonal node of the obstacle point as an axial jump point;
and S14, repeating the step S13 to obtain all axial jumping points in the uniform grid map.
In step S2, the active diagonal hop has an axial hop as its parent node, and the active diagonal hop is reached by the axial hop through barrier-free movement.
The active diagonal jumping point identification method comprises the following steps:
the axial skip point and the active diagonal skip point are key positions forming a main sequence path, so the preprocessing cost mainly aims at the axial skip point and the active diagonal skip point. After all axial jumping points in the map are identified, the key point is to quickly extract active diagonal jumping points. The invention first calculates a jump distance table for all passable nodes on the map, as shown in fig. 2. This calculation is linear with the number of nodes, and more precisely, each node is not visited more than 8 times, at most once in each direction.
S21, calculating an axial jump distance table of all passable nodes on the uniform grid map, wherein the table shows the distance from each passable node to other axial jump points or obstacles in the axial direction;
s22, calculating a diagonal jump distance table of all passable nodes on the uniform grid map, wherein the table shows the distance from each passable node to other passable nodes in the diagonal direction;
and S23, traversing by taking each axial jumping point as a source, repeatedly reading the diagonal distance of the current node, wherein the diagonal distance is positive, which indicates that the diagonal movement can be converted into the axial movement at the position, so as to reach the axial jumping point, and then judging that the current node is the active diagonal jumping point.
The uniform grid map rectangular bounding box pre-calculation method in the S3 of the invention comprises the following steps:
the invention only takes two types of jumping points as source nodes to initiate Dijkstra search after main sequence thought correction. A plurality of jumping points of different types or the same type but with different tuple representations may be attached to the same grid position, and the invention does not need to repeatedly calculate according to the grid position in the tuple representation and the difference of the father direction, but only collapses the relevant jumping point at the position and pre-calculates aiming at the collapsed grid positions of different jumping points.
S31, traversing the axial jumping point set and the active diagonal jumping point set, and initializing a rectangular bounding box for each edge of the grid position where the axial jumping points and the active diagonal jumping points are collapsed in the set;
s32, searching the full map by taking the current jump point as a source node, recording the initial edge of a path from the source jump point to the node every time a node is generated in the searching process, and pressing the node into an Open table;
s33, when the optimal path from the source jumping point to the node is found, the node is taken out from the Open table for expansion, and the node is added into the bounding box of the corresponding edge of the source node;
and S34, when the Open table is empty, ending the search of the current jump point, and entering the search of the grid position of the next axial jump point and the collapse of the active diagonal jump point.
In step S33 of the present invention:
a source node to a target node can correspond to a plurality of optimal paths, all the optimal paths are recorded, and finally the target node is added into all the rectangular bounding boxes meeting the conditions.
The invention emphasizes that the mode of the Dijkstra algorithm for breaking the tie is consistent with the diagonal movement priority order-bias rule of the skip point search. This is not only because the main-order search can avoid consuming a lot of computing resources on the symmetric path, but also more importantly, the consistency between the offline computation and the online search is maintained, and the completeness and the optimality of the search result are ensured. If the Dijkstra algorithm does not adopt the main sequence, but breaks the tie at will, the target point may not be included in the main sequence expansion direction of the current node, because the target point can be reached by searching through other edges in the pre-calculation process.
In addition, when all hops of a certain grid position in different parent directions have a main sequence path to a certain target point, or more than one main sequence path exists under the same hop, we refer to the main sequence path as existence of an equivalent main sequence path. Two equivalent main sequence paths between the solid line and the dashed lines, i.e. s and t, are shown in fig. 3. If the preprocessing stage only stores t in the bounding box of one of the initial edges, it will cause a search failure starting from another jump point. Therefore, we store it in all reasonable bounding boxes simultaneously here, ensuring the completeness of the search.
A system based on the method of the invention:
the method comprises a memory and a processor, wherein the memory stores a uniform grid map and a geometric container data compression program for jumping point path search, and the processor executes the steps of the method according to any one of claims 1 to 6 when the geometric container data compression program for jumping point path search is run.
As mentioned above, the number of collapsed positions of the axial skip point and the active diagonal skip point in the general grid map is much smaller than the total number of all passable nodes. The invention thus provides a significant saving in the required pre-processing time and space. The invention takes a general test set as a map, and the basic information of the map is shown in table 1. Which contains both typical game maps and artificially synthesized rooms and labyrinths.
The results of the pretreatment experiments are shown in table 2. Wherein, each rectangular bounding box needs four coordinates of up, down, left and right to mark its position, and each coordinate uses 16 bytes to store. The result clearly shows that the pre-calculated Dijkstra search times required by the invention are 1-2 orders of magnitude less than that of JPS + BB on average, so that the time and space of 1-2 orders of magnitude are saved on average. Taking the most complex Starcraft map as an example, the preprocessing time of the original algorithm on the 75 maps is close to 8 days in total, and the storage space is consumed by 1 GB, which is more than necessary. By adopting the invention, only about one day and more than one hundred million spaces are needed, and the benefit is extremely obvious.
TABLE 1 map used in the experiment
Figure BDA0002280335900000111
Figure BDA0002280335900000121
Table 2 comparison of pretreatment results.
Figure BDA0002280335900000122
Dijk represents the total times of Dijkstra search performed by the algorithm, and the Dijkstra search corresponds to the total number of passable nodes in the JPS + BB algorithm and the total number of jumping point positions of the JPS + BB + in units of million; time represents the total Time required for pretreatment, and the unit is hour; mem represents the total memory space required to store the bounding box in units of MB.
As shown in fig. 4, a specific example is given, which is a set of the thermzenseaamap with a size of 1024 x 1024 for the system StarCraft map. The JPS + BB processes the distance table according to Dijkstra search in an APSP mode after the distance table is calculated, 754304 nodes are used as sources for calculation in total, the time is 11.5 hours, and the storage geometry container needs 44.4MB of memory. In contrast, JPS + BB + pre-processing performed 107624 searches according to the above steps, which took 2.7 hours and required 2.9MB of memory space.

Claims (7)

1. A geometric container data compression method based on jumping point path search is characterized in that:
s1, carrying out structural analysis on the uniform grid map, identifying all axial jumping points, and generating an axial jumping point set;
s2, identifying all active diagonal skip points according to the axial skip point set, and generating an active diagonal skip point set;
and S3, searching the whole uniform grid map by taking the generated collapse positions of all axial jumping points and all active diagonal jumping points as source nodes, and performing geometric container identification preprocessing on each collapse position to complete the optimal path search between any two passable nodes.
2. The geometric container data compression method based on the jumping-point path search as claimed in claim 1, wherein the S1 axial jumping-point identifying step includes:
s11, scanning all nodes in the uniform grid map, and identifying the top points of the obstacles in all the nodes;
s12, obtaining feasible diagonal nodes of all the barrier vertexes;
s13, when two public neighborhood nodes including the barrier peak and the feasible diagonal node of the barrier point are passable nodes, identifying the feasible diagonal node of the barrier point as an axial jump point;
and S14, repeating the step S13 to obtain all axial jumping points in the uniform grid map.
3. The geometric container data compression method based on the jumping-point path search as claimed in claim 1, wherein the active diagonal jumping-point in step S2 has an axial jumping-point as its parent node, and is reached by the axial jumping-point through barrier-free movement.
4. The geometric container data compression method based on jumping-point path search of claim 3, wherein the active diagonal jumping-point identification step comprises:
s21, calculating an axial jump distance table of all passable nodes on the uniform grid map, wherein the table shows the distance from each passable node to other axial jump points or obstacles in the axial direction;
s22, calculating a diagonal jump distance table of all passable nodes on the uniform grid map, wherein the table shows the distance from each passable node to other passable nodes in the diagonal direction;
and S23, traversing by taking each axial jumping point as a source, repeatedly reading the diagonal distance of the current node, wherein the diagonal distance is positive, which indicates that the diagonal movement can be converted into the axial movement at the position, so as to reach the axial jumping point, and then judging that the current node is the active diagonal jumping point.
5. The geometric container data compression method based on the skip point path search as claimed in claim 1, wherein the uniform grid map geometric container identification pre-calculation method in S3 comprises:
s31, traversing the axial jumping point set and the diagonal jumping point set, and initializing a rectangular bounding box for each edge of the grid position where the axial jumping points and the active diagonal jumping points are collapsed in the set;
s32, searching the full map by taking the current jump point as a source node, recording the initial edge of a path from the source jump point to the node every time a node is generated in the searching process, and pressing the node into an Open table;
s33, when the optimal path from the source jumping point to the node is found, the node is taken out from the Open table for expansion, and the node is added into the bounding box of the corresponding edge of the source node;
and S34, when the Open table is empty, ending the search of the current jump point, and entering the search of the grid position of the next axial jump point and the collapse of the active diagonal jump point.
6. The geometric container data compression method based on the jumping-point path search as claimed in claim 5, wherein in step S33:
a source node to a target node can correspond to a plurality of optimal paths, all the optimal paths are recorded, and finally the target node is added into all the rectangular bounding boxes meeting the conditions.
7. A geometric container data compression system based on the jumping-point path search in claim 1, wherein:
the method comprises a memory and a processor, wherein the memory stores a uniform grid map and a geometric container data compression program for jumping point path search, and the processor executes the steps of the method according to any one of claims 1 to 6 when the geometric container data compression program for jumping point path search is run.
CN201911138925.1A 2019-11-20 2019-11-20 Geometric container data compression method and system based on jump point path search Active CN110975288B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201911138925.1A CN110975288B (en) 2019-11-20 2019-11-20 Geometric container data compression method and system based on jump point path search

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201911138925.1A CN110975288B (en) 2019-11-20 2019-11-20 Geometric container data compression method and system based on jump point path search

Publications (2)

Publication Number Publication Date
CN110975288A true CN110975288A (en) 2020-04-10
CN110975288B CN110975288B (en) 2023-08-29

Family

ID=70085252

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911138925.1A Active CN110975288B (en) 2019-11-20 2019-11-20 Geometric container data compression method and system based on jump point path search

Country Status (1)

Country Link
CN (1) CN110975288B (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112697161A (en) * 2020-12-15 2021-04-23 上海电机学院 AGV path planning method, storage medium and terminal
CN115845381A (en) * 2023-02-07 2023-03-28 广州三七极耀网络科技有限公司 Bounding box-based rapid path finding method, device, equipment and medium

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
RU2069317C1 (en) * 1992-09-03 1996-11-20 Ганеев Ранас Мударисович Process of measurement of geometric parameters of vessel and device for its realization
CN105955280A (en) * 2016-07-19 2016-09-21 Tcl集团股份有限公司 Mobile robot path planning and obstacle avoidance method and system
CN106774347A (en) * 2017-02-24 2017-05-31 安科智慧城市技术（中国）有限公司 Robot path planning method, device and robot under indoor dynamic environment
CN109115226A (en) * 2018-09-01 2019-01-01 哈尔滨工程大学 The paths planning method of multirobot conflict avoidance based on jump point search
US20190178842A1 (en) * 2015-04-21 2019-06-13 Battelle Memorial Institute Collection, Release, and Detection of Analytes with Polymer Composite Sampling Materials
US20190195639A1 (en) * 2017-12-21 2019-06-27 Grzegorz Malewicz Method and a Computer System for Providing a Route or a Route Duration for a Journey from a Source Location to a Target Location
CN110006429A (en) * 2019-03-20 2019-07-12 智慧航海（青岛）科技有限公司 A kind of unmanned boat path planning method based on depth optimization
CN110319837A (en) * 2019-07-09 2019-10-11 北方工业大学 A path planning method for indoor complex conditions of a service robot

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
RU2069317C1 (en) * 1992-09-03 1996-11-20 Ганеев Ранас Мударисович Process of measurement of geometric parameters of vessel and device for its realization
US20190178842A1 (en) * 2015-04-21 2019-06-13 Battelle Memorial Institute Collection, Release, and Detection of Analytes with Polymer Composite Sampling Materials
CN105955280A (en) * 2016-07-19 2016-09-21 Tcl集团股份有限公司 Mobile robot path planning and obstacle avoidance method and system
CN106774347A (en) * 2017-02-24 2017-05-31 安科智慧城市技术（中国）有限公司 Robot path planning method, device and robot under indoor dynamic environment
US20190195639A1 (en) * 2017-12-21 2019-06-27 Grzegorz Malewicz Method and a Computer System for Providing a Route or a Route Duration for a Journey from a Source Location to a Target Location
CN109115226A (en) * 2018-09-01 2019-01-01 哈尔滨工程大学 The paths planning method of multirobot conflict avoidance based on jump point search
CN110006429A (en) * 2019-03-20 2019-07-12 智慧航海（青岛）科技有限公司 A kind of unmanned boat path planning method based on depth optimization
CN110319837A (en) * 2019-07-09 2019-10-11 北方工业大学 A path planning method for indoor complex conditions of a service robot

Non-Patent Citations (6)

* Cited by examiner, † Cited by third party
Title
MIN WANG;HANG ZHANG;FENG ZHU;FENG PENG;XIN WANG;MING SHEN;REN-YI QIN;: "Pancreaticoduodenectomy for borderline resectable pancreatic head cancer with a modified artery-first approach technique" *
MIN WANG;HANG ZHANG;FENG ZHU;FENG PENG;XIN WANG;MING SHEN;REN-YI QIN;: "Pancreaticoduodenectomy for borderline resectable pancreatic head cancer with a modified artery-first approach technique", HEPATOBILIARY & PANCREATIC DISEASES INTERNATIONAL, no. 02 *
YUE HU: "Improving the Combination of JPS and Geometric Containers", vol. 29, pages 209 - 213 *
张海燕;林志贤;郭太良;: "机器人避障路径规划优化控制仿真", 计算机仿真, no. 09 *
赵德群;段建英;陈鹏宇;苏晋海;: "基于A~＊算法的三维地图最优路径规划" *
赵德群;段建英;陈鹏宇;苏晋海;: "基于A~＊算法的三维地图最优路径规划", 计算机系统应用, no. 07 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112697161A (en) * 2020-12-15 2021-04-23 上海电机学院 AGV path planning method, storage medium and terminal
CN115845381A (en) * 2023-02-07 2023-03-28 广州三七极耀网络科技有限公司 Bounding box-based rapid path finding method, device, equipment and medium

Also Published As

Publication number Publication date
CN110975288B (en) 2023-08-29

Similar Documents

Publication Publication Date Title
CN109115226B (en) Route planning method for avoiding multi-robot conflict based on jumping point search
CN113485369B (en) Improved A* algorithm for indoor mobile robot path planning and path optimization
Wang et al. Mobile robot path planning based on an improved A* algorithm
CN113515129B (en) Bidirectional skip point search unmanned vehicle path planning method based on boundary search
CN110967015B (en) Path planning method and system
CN111080786B (en) BIM-based indoor map model construction method and device
CN111104471B (en) Mode database information compression method and system based on jumping point path search
CN110909961B (en) BIM-based indoor path query method and device
CN110487290B (en) Unmanned vehicle local path planning method based on variable step size A star search
CA2418756A1 (en) Dual dijkstra search for planning multiple paths
CN115167474A (en) Mobile robot path planning optimization method
CN112229419A (en) Dynamic path planning navigation method and system
CN109855640B (en) A Path Planning Method Based on Free Space and Artificial Bee Colony Algorithm
US7755628B2 (en) Method and apparatus for multi-level ray tracing
CN110975288A (en) Geometric container data compression method and system based on jumping point path search
CN110975290A (en) Path planning method and system based on pattern database
CN109432776A (en) A kind of free method for searching in space
Garcia et al. GPU-based dynamic search on adaptive resolution grids
Hallgarten et al. Stay on track: A frenet wrapper to overcome off-road trajectories in vehicle motion prediction
CN111427341B (en) Robot shortest expected time target searching method based on probability map
Soni et al. Multi-robot unknown area exploration using frontier trees
Eraghi et al. Path length comparison in grid maps of planning algorithms: HCTNav, A* and Dijkstra
CN112965500B (en) Path planning method and device with must-pass point set and additional hard constraints
CN110975291B (en) Path extraction method and system
CN115167466B (en) Mobile robot standard control set local path planning method and system

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant