More Flexible Proximity Wildcards Path Planning with Compressed Path Databases

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-11-24 05:19:03

Abstract: Grid-based path planning is one of the familiar issues in AI, and a popular topic in application areas such as computer games and robotics. Compressed Path Databases (CPDs) are recognized as a state-of-the-art method for grid-based path planning. It is able to find an optimal path extremely fast without a state-space search. In recent years, researchers tend to focus on improving CPDs from reducing CPD size or improving lookup performance. Among various methods, proximity wildcards is one of the most proven improvements in reducing the size of CPD. However, its proximity area is significantly restricted by complex terrain, which has more significant impacts on pathfinding efficiency and generates more additional costs. In this paper we enhance CPDs from the perspective of improving search efficiency and reducing search costs. Our work is to break the limitation between length and width of the proximity area, and adopt more flexible approaches to avoid obstacles, so as to reduce its impact on the proximity area and improve the search efficiency. Experiments performed on the benchmarks from Grid-Based Path Planning Competition (GPPC) demonstrate that the two proposed methods can effectively improve search efficiency and reduce the search costs by 2-3 orders of magnitude. Remarkably, our methods can further reduce storage costs, and improve compression capability of CPDs simultaneously.

Main paper: 
 exploring a combination algorithm compatible with: 
 CPDs that has powerful search performance without causing internal interaction storage costs. 
introduction: 
 Path planning is one of the important problems in artificial intelligence which has been studied for many years and widely applied in real scenes such as robotics and computer games (Freund and Hoyer 1986; Cui and Shi 2011) . Grid-based path planning is one of the most active research directions on this problem. Over the years, numerous excellent algorithms have been proposed, and the Grid-Based Path Planning Competition (GPPC) (Sturtevant et al. 2015) is the cornerstone in the development of these novel pathplanning achievements. The impact of these advancements is essential and far-reaching, and they are poised to revolutionize path planning in the coming years (Botea 2011; Uras and Koenig 2014; Harabor and Grastien 2014; Rabin and Sturtevant 2016; Sturtevant and Rabin 2016; Uras and Koenig 2017; Goldenberg et al. 2017; Cohen et al. 2017; Harabor and Stuckey 2018; Salvetti et al. 2018; Hu et al. 2019 Hu et al. , 2021)) .The Compressed Path Databases (CPDs) (Botea 2011; Botea and Harabor 2013 ) known as a group of state-of-theart techniques for grid-based path planning, is designed to speed up the response and reduce the first move delay during the agent's path planning tasks (Zhao 2022) . Each CPD is a data structure that provides the optimal first move from any start cell s to any target cell t. The process of finding an optimal path is to iteratively search such a group of CPDs to find the optimal move directions to reach the target without any state space search. The main disadvantage of CPDs with ultra-fast pathfinding speed is the huge build cost. Each CPD needs to be encoded by all-pairs of precomputation, and then compressed with encodes and store the result. In recent years, researchers mainly tend to focus on reducing the size of the CPD such as single row compression (SRC) (Strasser, Harabor, and Botea 2014 ), heuristic redundant symbols (Chiari et al. 2019) , proximity wildcards (Chiari et al. 2019) , bidirectional wildcards (Salvetti et al. 2017) , or improving lookup performance such as two-oracle path planning algorithm (Topping) (Salvetti et al. 2018 ). Among them, the SRC performed best in GPPC 2014, and has become an important baseline for improving CPDs.The CPDs improved by proximity wildcards (CPDs PW), replaces the storage symbols of qualified nodes in the largest square centered on any node with wildcards to reduce the preprocessing memory on the basis of heuristic redundant symbols. Their experiments are mainly based on Dragon Age: Origins (DAO) (Sturtevant 2012) , which verifies the excellent compression capability of CPDs PW. It can achieve better on 99% of the maps, and can even compress the map size to 1/55 of SRC on the map AR0044SR.Despite the effectiveness of CPDs PW for compression is already advanced, there are still the following drawbacks: 1. Severely limited by complex terrain. Its area of concern is square in shape, which causes it to miss out on opportunities for expansion and incur more search costs when it encounters obstacles in any direction. 2. Inefficient search. The compression is not efficient enough, resulting in more binary searches to find the target from during pathfinding, leading to inefficient search.In this paper, our idea for the above problems is to expand the proximity area by breaking its shape limitation without weakening the compression capability. We propose the following two methods:1. Rectangular Proximity Wildcards (RPW): This method breaks the limitation of length and width, and expands the shape of proximity area to a rectangle, so that when obstacles are encountered in any direction of length or width, the other that does not encounter obstacles can continue to be expanded. 2. Coordinates Proximity Wildcards (CPW): This method breaks the limitations of traditional geometry. In order to avoid obstacles more flexibly and improve the expansion opportunities, four quadrants are divided with the current node as the center, and the largest rectangle is expanded in each quadrant. The areas drawn by the four quadrants are all proximity areas of the current node.We also expand the scale of the experiment, adding Baldurs Gate II (BGII) (Sturtevant 2012) and Starcraft (Sturtevant 2012) on the top of DAO, a total of 351 maps, and take SRC and CPDs PW as the experimental baselines. The experimental results show that the two methods we proposed can effectively improve the search efficiency and reduce search costs by 2-3 orders of magnitude. In addition, they can also improve compression capability of CPDs. Experiments demonstrate that the more flexible the method is to avoid obstacles, the less it is affected by complex terrain, and the more obvious the improvement in efficiency.The paper is structured as follows: First, we provide an overview of related work. Then, we introduce the fundamental principles of the CPDs and the key technologies utilized. After that, we present a detailed description of the RPW and CPW, along with description diagrams and algorithm pseudo codes. We also present the experimental results and analysis, and conclude the paper at the end.As a leading technique for optimal pathfinding, CPDs (Botea 2011) has received extensive attention since it was proposed. Its main idea is to achieve speedup through preprocessing and additional memory, which has shown excellent performance in solving speed, but its huge memory requirements seem to be a huge burden.Therefore, exploring better compression methods for CPDs has become a research hotspot. The Copa (Botea and Harabor 2013) , which combined list trimming, run length encoding, and sliding window compression to improve compression capabilities at the cost of lost time, is one of the best competitors in GPPC 2012. In 2014, SRC (Strasser, Harabor, and Botea 2014) , an algorithm combined with run length encoding (RLE) to compress rows, outperforms Copa in both compression and query time, and became one of the winners in GPPC 2014. Although SRC has excellent performance in compression ability and speed, it still requires huge memory overhead on large maps. In order to solve this practical bottleneck, wildcard substitutions (Salvetti et al. 2017 ) are introduced, which uses wildcards to replace part of the CPDencoded data, and can be combined with heuristics to reduce the size of CPD. Its main idea is that given any start node s and target t, as long as either route from s to t or t to s is feasible, a complete optimal path can be established. This method is proven to be effective, and the proximity wild-cards (Chiari et al. 2019 ) is its extension with a new concept of redundant symbols proposed at the same time. The proximity wildcards uses redundant symbols to define a square centered on the current node, which is called the proximity area, and all nodes in it can be optimally reached through the heuristic move. Experiments verified that proximity wildcards is one of the most effective methods to improve the compression capability of CPDs, but it is seriously affected by obstacles and therefore runs with limited efficiency. Our work is related to proximity wildcards, but we choose to reduce the impact of obstacles on efficiency in more flexible ways (e.g. rectangle, quadrants).The above works are all approaches to reduce the memory overhead of CPDs with the goal of finding optimal solutions, often accompanied by a significant loss of preprocessing time. In 2020, a centroid-based bounded suboptimal method (Zhao et al. 2020 ) reduces storage costs by only calculating the first-move data of selected nodes, which ensures that path costs within the fixed bound of the optimal solution. This approach innovatively reduces preprocessing time and storage costs by trading some suboptimality.There are also works focus on improving search performance, such as Topping (Salvetti et al. 2018) , which is a combination of SRC and Jump Point Search+ (JPS+) (Harabor and Grastien 2014). It first calls SRC to find the best move direction from the current node to the target, and then calls JPS+ to judge the feasible steps in this direction. In most cases, Topping can be more than an order of magnitude faster than SRC, but at the cost of nearly doubling memory consumption. To deal with the huge memory overhead, TOPS (Hu et al. 2021) and Topping+ (Hu et al. 2021) are proposed. The TOPS reduces preprocessing memory by calculating only the CPD data of the jump points. The Top-ping+ extracts a series of complete paths from the successor start nodes to the target. Their search performance are competitive with Topping, while having smaller space requirements and better time performance.Gridmap. A gridmap is a two-dimensional mobile agent operating environment, where each cell is either traversable (white squares) or obstacle (black squares). It has two common ways for defining neighboring relationships: 4-connected grids and 8-connected grids. In 4-connected grids, a traversable cell has at most four neighbors, and the movable directions are: East, South, West and North (symbolized as E, S, W, N), with a move cost of 1 per cell. As shown in Figure 1 , for any node n on the map, the 8-connected grid map allows diagonal movement, adding movable directions: Northwest, Northeast, Southwest, and Southeast (symbolized as NW, NE, SW, SE), the cost of linear movement ⃗ c is 1, and the cost of diagonal movement ⃗ d is √ 2 . A path planning problem on a gridmap starts at cell s called start node and ends with cell t called the target node. Its goal is to find the most efficient path with the minimum cost from the start node to the target node. The formula s ′ = s + k ⃗ d + m⃗ c (k and m are integers) indicates that moving from node s to node s ′ needs k times along the If k and m are negative integers, it means reverse movement. In this paper, we assume that diagonal movements are not allowed if they will touch an obstacle cell. Compressed Path Databases (CPDs). CPD is a data structure that encodes the optimal first move from any node s to a target node t on a map. It is the result of compressing the first move array using run length encoding (RLE). (Strasser, Harabor, and Botea 2014) . The first move array T (s) of node s stores the first move of the shortest path from node s to each reachable node t, which is calculated by Dijkstra. CPDs are constructed by computing a first move array for each node in the map in offline preprocessing. Run Length Encoding (RLE). RLE compresses the firstmove array by more compactly representing the substrings (called runs) composed of the repetition of the same symbol. It labels obstacles and source node with the wildcard "*", because they don't need to be searched. Taking Figure 2 as an example, the first row can be compressed into NNN*NNNNN. Usually we use a substring to represent the whole map, so the first row is represented as 1N, and this map is represented as 1N 15E 19W 23N 24E 28W 33E 37W 41S 42SE. Where the letters denote optimal first moves for moving the source node s to the corresponding position and the numbers are subscripts starting from 1 after reducing the 2D first-move array to a 1D array. Heuristic move. Heuristic move refers to the first move of node s to ignore obstacles and move towards the goal. It is determined by the shortest heuristic distance calculated by heuristic function F e (n, t), where ω(s, n) is the cost from source s to node n and f e (n, t) is the heuristic distance function from n to t. In this paper we use the Euclidean distance to calculate the heuristic move. We also use redundant symbol h to mark the nodes where the heuristic move coincides with the first move to improve efficiency. That is, if the F e (n, t) returns a first move belonging to the first move array T (s), add the redundant symbol h to T (s). f e (s, t) = (s.x -t.x) 2 + (s.y -t.y) 2(1)EQUATIONProximity Wildcards. Proximity wildcards computes the largest square proximity area centered on s, where traversable nodes must have the heuristic redundant symbol h. If the target node t is within the proximity area of s, the heuristic move can be applied directly, otherwise look for the first move.Typically, when using the proximity wildcards, nodes within the proximity area of node s can usually use heuristic moves as the first move to optimally reach. However, its proximity area is square, meaning that obstacles in either direction will cause the proximity area to stop expanding, so this method is not effective in complex terrain. In this section, we introduce a method called Rectangular Proximity Wildcard (RPW), whose region of interest is rectangular, its outstanding advantage is that when obstacles are encountered in either direction of length and width, the other direction is unaffected and can still continue to be expanded, as shown in Figure 3 . Definition 1: Given a node s and a function F x (s, t), the width of largest proximity rectangle R centered on s is expressed as rec(s).x and length is expressed as rec(s).y, for any node n ∈ R, there is f x (s, n) ∈ T (n), T is the firstmove array of s, and rec(s).x * rec(s).y is the maximum value d ∈ N . The cells in the proximity rectangle are all optimally reachable from s by heuristic moves, and we denote each such cell with the wildcard character "*". As depicted in Figure 3 , the compression result of the first move array with the proximity wildcards is 1N; 5h; 10N; 14h; 19W; 26h; 27E; 28h; 37W; 43h, a total of 10 RLE runs. On the other hand, the compression result of the first move array with RPW is 1N; 5h; 10N; 14h; 19W; 27E; 28h; 37W; 45h, a total of 9 RLE runs. end if 12: end if RPW has a larger proximity area than proximity wildcards, which typically leads to more efficient compression and more readable encoding due to the need for fewer RLE runs. This solid foundation for the improvement of search performance. In the online search, RPW is able to flexibly respond to complex terrain changes, and its larger proximity area can help to use more heuristic moves, which effectively improves search efficiency and reduces cost. Algorithm 1 presents the CPD search function CPDHRP(s, t) that utilizes the RPW and Algorithm 2 shows the improved CPDs algorithm CPDs RPW(s, t) with the CPDHRP(s, t).In the previous section, we introduced a flexible method to improve search performance, and it also has a certain effect on compression. Although RPW has effectively improved the search efficiency of CPDs, the use of traditional geometry as proximity areas still has significant limitations. When confronted with extremely complex and narrow maps (such as bridge maps), in more cases, the area of RPW would be very restricted, even as large as proximity wildcards. In this section, we propose a more flexible method called Coordinates Proximity Wildcards (CPW), as shown in Figure 4 . We replace the traditional geometry centered on the source node with quadrants centered on the source node, and expand the largest rectangle in each quadrant. For the sake of illustration, we use PW here to represent the proximity wildcard method. As shown in Figure 5 , a more flexible expansion method can make the proximity area larger. The area of the proximity area of CPW is three times larger than RPW, and six times larger than PW, which means more efficient search and compression. However, this method needs to store four times the size of auxiliary data, because each X.n ← rec(s) n .x.Y.n ← rec(s) n .y. (s, n) ←CPDHCP(s, t)4: p ← p + [(s, n)] 5:s ← n 6: end while 7: return pWe performed experiments on three game benchmarks from GPPC (Sturtevant et al. 2015) : BGII, DAO and Starcraft. The BGII has a total of 120 maps, mainly composed of small maps, with nodes distributed between 100 and 60,000. The DAO is mainly composed of medium-sized maps, and the number of nodes in its 156 maps is between 100 and 140,000. The Starcraft is a large map set with 75 members, ranging from 50,000 to 760,000 nodes. We use SRC and CPDs PW as experimental baselines, the former is our main improvement and the latter is essential reference. After applying our methods to SRC, the resulting algorithms are as follows:• CPDs RPW, improved by rectangular proximity wildcards (RPW).• CPDs CPW, implements the coordinates proximity wildcards (CPW).The experiments use runtime to measure search efficiency and the number of binary searches used to find the target during the search as the search costs. They are the two main metrics of the experiments. In addition, we also verify the compression costs through RLE runs and identify the compression capability with the first move array size. It is important to mention that the CPD for CPDs PW, CPDs RPW, and CPDs CPW are all composed of the first move array and the auxiliary data, where the first move array size can illustrate the strength of compression capability, and the auxiliary data stores the proximity areas' sides. Due to the large difference in map size, there is a huge difference in data distribution. Therefore, for other performance metrics except runtime, we use the "factor" to describe the algorithms' performance. The factor is the result of dividing the SRC running results for the same map by the running results of other CPDs variants. Our definition of "factor" is shown in Equa- EQUATIONmetric i represents the i-th metric, and realnum x (metric i ) represents the real value of the i-th metric of algorithm x. x can be assigned to CPDs PW, CPDs RPW, and CPDs CPW.All algorithms are implemented in C++, and the experimental environment is Ubuntu 20.04.3 LTS, with processor AMD R ⃝ Ryzen 9 5900*12core processer*24 and 31.4GiB RAM.Before searching online, each map needs to be preprocessed offline. The use of more flexible proximity wildcards in the preprocessing stage reduces compression costs and improves compression capability.The compression cost factor C RLE-runs is the quotient of RLE runs required by SRC and CPDs X to complete a compression task. Higher compression cost factor means fewer RLE runs, leading to lower compression costs. As shown in Figure 6 , our methods are effective in saving the compression cost, where CPDs CPW has the highest C RLE-runs and the best performance. This means they can yield leaner compression results and lower compression costs, and contribute to search efficiency due to more readable compressed results.Figure 7 (a), (b), (c) displays the distribution of compression capabilit C f irst-move . A higher C f irst-move implies a smaller first move array size, which results in better compression performance. We can visualize that both of our methods have improved compression capability, with CPDs CPW performing best. From Figure 7 (e), (d), (f), it can be seen that the memory factor C CP D of CPDs RPW is slightly higher than that of CPDs PW, while CPDs CPW has been at a disadvantage. It is due to the fact that the size of CPDs CPW's auxiliary data (proximity distance) is four times larger compared to CPDs PW and CPDs RPW, resulting in larger CPD sizes and more memory costs. Therefore, sometimes we may encounter a scenario where the memory gain is lower than the expenditure. We can also see that as the map sizes increase, the memory factor of CPDs CPW becomes higher and higher. It fully demonstrates the performance advantage of our methods in solving large-scale maps.The search efficiency increases with shorter runtime, as shown in Figure 8 . The runtime of our methods is significantly less than that of CPDs PW. Because they have larger proximity areas which effectively reduces binary searches and makes the search faster. We can also find that CPDs CPW takes more runtime than CPDs RPW. Since CPDs CPW's CPD lookup function is more complex, so each call takes more time. Both CPDs RPW and CPDs CPW's lookup functions are more complex than CPDs PW's, so each call to the find function takes more runtime, but both take less time than CPDs PW due to their huge search efficiency gains.The binary search factor C binary-search is the quotient of the binary searches required by SRC and each CPDs variant when performing the same search task. If a CPDs variant performs a search that requires fewer binary searches, it is equivalent to a higher binary search factor, implying less search cost. As shown in Figure 9 , we can intuitively see the improvement effect of the three CPDs variants on the binary search, in which the C binary-search of CPDs RPW and CPDs CPW are remarkably higher than CPDs PW. In both BGII and DAO, we experience remarkable effects that are magnified by hundreds or even thousands of times, despite taking place on small maps. Some of these exceptional cases are listed in Table 1 . We find C binary-search stable and concentrated as map size increases. For example, CPDs CPW has 14 (21-7) quartile distance in small map set BGII, 5 (10-5) in medium map set DAO, and less than 2 in large map set Starcraft. It is also evident that CPDs CPW performs better than CPDs RPW and CPDs RPW outperforms CPDs PW based on their median, mean, and quartiles. The average binary search factor C binary-search for CPDs PW on BGII is 5.3, while CPDs RPW's is 7.0 and CPDs CPW's is 15.2, which is twice that of CPDs RPW and three times that of CPDs PW. On DAO maps, CPDs CPW has an average binary search factor of 7.5, which is twice as much as that of CPDs PW and 1.7 times that of CPDs RPW. Even on Starcraft, the average binary search factor of CPDs CPW can reach 1.6 times that of CPDs PW and 1.4 times that of CPDs RPW.It is because a more flexible proximity wildcards method avoids more obstacles, further reduces the impact of complex terrain, and allows for a larger proximity area. In other words, CPDs CPW has the largest proximity area, while the area of CPDs RPW is at least as large as that of CPDs PW. A larger proximity area can enhance search performance from two different perspectives:1. More powerful heuristics. Both theory and intuition indicate a larger proximity area means that more heuristic information can be used to find the target during the search process. 2. More effective search preparation. A larger proximity area in the preprocessing stage makes compression more efficient, resulting in more compact RLE encoding and efficient search.Our methods have enhanced the search performance of CPDs based on reducing the size of CPD. We compare SRC, CPDs PW, CPDs RPW, and CPDs CPW, in terms of both search and compression. We also conduct comparative experiments with Topping, a representative algorithm in another research area, which significantly improves search performance but at the expense of huge memory and inefficient compression. Experiments verify the effectiveness of our methods, and CPDs CPW even is competitive with Topping in search costs. The pathfinding process of Topping is jointly conducted by the SRC oracle and the JPS+ oracle. What we compare is only the number of binary searches of the SRC oracle in Topping. Experiment result show that CPDs CPW performs best among variants, and has an absolute advantage in binary searches on 68% medium-sized maps and 96% small maps, and occupies a place in large maps. Noted that our methods utilize only half the storage cost used by Topping.As a leading technology for path planning, CPDs has the bottleneck of huge storage overhead. A method called proximity wildcards significantly enhances the compression capability of CPDs with surprising results in reducing storage costs. However, it is severely limited by complex terrain, making the search inefficient and and generating more costs.In this paper, we extend proximity wildcards and propose two methods RPW and CPW that can be more flexible in avoiding obstacles to compute larger proximity areas in response to complex terrain changes. Meanwhile, we extended the experiment scale to three full datasets. The experimental results demonstrate that rectangular proximity wildcards (RPW) and coordinates proximity wildcards (CPW) can flexibly deal with complex terrain, and significantly improve the search performance, and further improve its compression performance.Our future work mainly focus on the following directions:1. Exploring ways to reduce time while maintaining optimality, compression and search capability. Investigating new encoding alternatives to RLE is an interesting research direction. 
 
 Appendix:  


Decision: The paper proposes two flexible proximity wildcard methods to improve the compression of CPDs.

Strengths of the paper: New ideas on this relatively not-very-explored of compressed path databases. Significant experimental results.

Weaknesses: The main concern of the reviewers was the quality of the writing. If the paper is accepted we strongly urge the authors to revise their paper.

Reviews: review: strength_weakness: strength_weakness: I think that Algorithm 3 does not match the textual description provided. 
Also, the first-move metric is not properly described. 
Minors:
There are some typos in the paper 
Figure 4 is not clear. I would suggest to divide the representation of each quadrant in a separate grid.
questions: questions: 1) In my understanding, Algorithm 3 returns true for any node within the largest X.n and Y.n independently of the quadrant. For instance, if we consider the first quadrant (i.e. north-east quadrant), the value dx<0 where dx = S.x - T.x means that the target is outside the considered quadrant. The absolute value in line 4 prevents dx from being <0. Can you please clarify this? Also, I think the for loop can be avoided as you always know which quadrant(s) the target belongs to. I hope I didn’t miss anything.  
2) What is the first-move metric? As it is defined in Figure 2, the first move array is the list of first optimal moves from the source to any possible target that is then compressed through RLE. If this is the case, I would expect its length to be the same for all considered approaches.
3) Is the runtime reported in Figure 8 in nanoseconds? I would expect that the runtime to compute a path would increase as the maps grow and the CPD gets larger. However, from the plots, I can read that the time to compute a path for the small maps (BGII) is at least 10x the time to compute the path for medium maps. Can you please comment on this?
strength_weakness: strength_weakness: Weaknesses:
1. The writing in the paper requires significant improvement.
2. The presentation of experimental results needs enhancement.
3. A more comprehensive comparison with recent developments in Euclidean pathfinding should be considered.

Comments:
1. Abstract,  “In this paper we enhance“, typo “In this paper,”
2. Abstract, “improve search efficiency and reduce the search costs by 2-3 orders of magnitude.” This seems to be inconsistent with experimental results. Do you mean by average, or only for some of maps. Please make the claim clear.  
3. Related work, there are many other works that utilise CPD for pathfinding in Euclidean space, road network, traffic management. For completeness, please consider including those. 
4. Background - Heuristic move. Equation 2.  Should argmax be argmin?  Also, (s,n) \in E,  E is not defined. 
5. Background - Proximity Wildcards. You should explained why proximity wildcards need to be centred on s. Also, please use the toy-dataset to give an example for heuristic move and proximity wildcards.
6. Rectangular ProximityWildcards,  the algorithm 1-2 looks trivial, perhaps it is better to explain them in text or using running example. 
7. Coordinates Proximity Wildcards, similarly the algorithm 3-5 are not interesting,  also the figure 5 needs to be better explained to clarify how the proposed algorithm achieve such compression. 
8. After reading the two proposed method, my biggest question is why the wildcard must centre/corner on s. Also, why we have to use rectangle or square shaped container, can we associate with other type of geo-entity? such as circle or polygon. 
9. Experiments, instead of defining a metric, why not show the original results, e.g., the actual memory cost in MB for CPD. This is important as it can provide a guidance for user when using these suggest techniques. Similar, for others type of measurement. 
10. Figure 8 “Runtime (unit: ns). Runtime is the time taken to perform an online search task, and we use it to measure search efficiency”, when you say runtime, is this per first move extraction, or per complete path extraction. Also, the reported performance looks weird to me. To the best of my knowledge so far, I have not aware any existing solver could achieve nano seconds query runtime, including previous CPD works (see https://gppc.search-conference.org/grid). Please investigate carefully.  
11. Table 2. Why not simply include TOPPING in Figure 8 ? 
12. The authors should consider to compare with more recent works on euclidean pathfinding, such as EPS (Euclidean pathfinding with compressed path databases) and EHL (Efficient object search in game maps). To make it clear, the proposed algorithm doesn’t has to outperform these algorithms, but it would be good to show some comparison so that the reader can refer the performance accordingly. Alternatively, the author should consider to submit the results to GPPC2 (https://gppc.search-conference.org/grid).


---- post rebuttal comments ------ 

Please make sure you have updated the experiments section accordingly. Also, please carefully proofread the paper and fix these minor comments including C3.
questions: questions: Please address the  Comments (C) C2, C4, C8, C10 and C12.
strength_weakness: strength_weakness: The weaknesses of this work can be viewed from two aspects: method and presentation.

From a methodological perspective, while RPW and CPW improve the compression of CPDs, they require significantly more auxiliary data
to store wildcard information. This results in no significant reduction in CPD size.

In terms of presentation, in the experiment section, the author highlighted the reduction in the number of binary searches. However, a
decrease in binary searches doesn't necessarily equate to an improvement in processing time. Figure 8 presents the runtime
distribution, but the specific improvements are not clear.

It should also be noted that CPDs are already an "ultra-fast" path planning method—improving the processing time by several
percentages doesn't make a strong impact. What the authors should demonstrate in their experiment would be concepts like a "smaller
CPD size with no worse processing time" or a "significant CPD size reduction with slightly worse processing time"."

What's more, there are several claims that seem overstated or potentially misleading:

 1 In the 'preprocessing' section, the text states, 'It fully demonstrates the performance advantage of our methods in solving
   large-scale maps.' This is unclear, as only three map sets are referenced. There is no apparent trend correlating with map size.
 2 In the 'online search' section, it's stated that 'The runtime of our method is significantly less than that of CPDs_PW.' It can be
   argued that the runtime improvement seen in Figure 8 isn't notable enough to be classed as 'significant.'
 3 In the 'abstract', there is a claim that '...the two proposed methods can effectively improve search efficiency and reduce the
   search costs by 2-3 orders of magnitude.' Firstly, it's debatable whether the improvement actually reaches 2-3 orders of magnitude.
   Secondly, the number of binary searches is not synonymous with 'search cost.'

In summary, I perceive this work as an incremental work that has a limited impact.
---
Revision:
After reading the rebuttal and revisiting the paper, I finally realized that the major point the authors attempt to emphasize is
'a method that improves query processing without hurting memory consumption (and sometimes even benefits from it)'. 
Thus I decide to remove 'method' from the weaknesses.

The writing still needs additional work to improve, more specifically:

1. Highlight the contribution. While the abstract does mention it, the emphasis seems to fade as one reads through the paper. The
   message that comes across is more 'we developed a novel wildcard method to reduce memory...' than the intended one. 

2. Author should consider to change the order of experiment section - e.g., move the size comparison after speed/search comparison.

3. Add the result on elapsed time in experiment and discuss the impact of reducing number of binary search. E.g., concept like "cheaper CPUs get more benefit from less binary search..." can be useful.

In conclusion, these weaknesses can be fixed with some effort, therefore I change my decision to 'weak accept'.
questions: questions: What's the total query processing time of CPD_PW, CPD_RPW and CPD_CPW?