GRAPH-CONSTRAINED DIFFUSION FOR END-TO-END PATH PLANNING

Response to W1 and Q1:

Thanks for your comments. Our dataset is a classic dataset for path planning in road network. In fact, our baselines NMLR and KS also choose this dataset for validation.

Honestly, it is difficult to directly show that a sufficient number of paths that don't follow the linearly accumulative cost assumption. This is because many implicit goals are complex to model, and our data is insufficient for comprehensive verification. However, we notice that in experiment (Sec. 6.2) Dijkstra's algorithm underperforms. This underperformance suggests a considerable discrepancy in the DTW and LCS when comparing the algorithm's shortest paths with the ground truth paths, attributable to Dijkstra's algorithm's inherent focus on finding the shortest path.

Response to W2:

We are sorry for the confusion caused.

The DTW value in the original manuscript is notably small because we calculate distances using the longitude and latitude coordinate system. A unit distance equates to approximately 110 kilometers. Consequently, a reduction of 0.001 signifies an improvement on the scale of hundred meters, which is significant in real-world planning. To address your concern, we have converted the distance unit to kilometers and altered the table contents to percentages for clarity. The original results are moved to App. F.2 of the revised manuscript.

Regarding your concern about robustness, we present the proportion of scenarios in which each algorithm outperforms Dijkstra's algorithm. Our algorithm surpasses Dijkstra's algorithm in 86.6% and 86.8% of all test cases for DTW and LCS, respectively, marking the highest performance among all compared baselines (see App. F.2 of the revised manuscript for details).

It is understandable that our improvement is modest compared to CSSRNN, as these recurrent neural network models are adept at capturing non-linear relationships in sequences. However, our primary focus is on planning (i.e., conditional sampling), not generation (i.e., unconditional sampling). CSSRNN cannot be applied to planning.

Please refer to Sec 6.2 and App. F.2 of the revised manuscript.

Response to W3 and Q2:

Thanks for your comments. We are sorry for the confusion.

Many modern navigation services are offered from the cloud, which spares users from the substantial storage and transmission costs associated with map data. Consequently, our method is not designed to run on users' local devices.

To provide more clarity on our computation cost, we have included additional experiments. Overall, Dijkstra's algorithm is the fastest due to its simplicity. The execution time of our method is $0.112 \pm 0.315$ seconds, quicker than the baseline Navi, which has an execution time of $0.339 \pm 0.133$ seconds. Given that Navi is a real world navigation api developed by AMap (https://lbs.amap.com/), one of the leader location service provider in China, it can support real-world applications, the latency of our method is also acceptable for real-world applications. We conducted our experiments on an Nvidia RTX 3090 with 24 GB memory, capable of supporting up to a 400 batch size. As the batch size increases, the memory cost grows linearly, while the time consumption per origin-destination (OD) pair decreases from $0.32$ to $0.12$ seconds.

We acknowledge that adapting our model to run on mobile devices is an intriguing challenge and consider it a subject for future work.

For detailed information, please refer to App. F.5 of the revised manuscript.

We are sorry for the confusion. Our main contribution is the diffusion process on graph space. Leveraging this, we are able to accomplish path planning via conditional sampling (ie. end-to-end planning).

The main difference between our end-to-end planning algorithm and current data-driven approach is that we avoid the searching framework. Traditional searching frameworks necessitate:

i) explicit modeling cost for each edge.

ii) finding the path with smallest summation of cost of edges.

These prerequisites are associated with two major limitations of the search-based framework:

i) Given that each edge's cost must be modeled, all planning objectives and their interconnections need to be explicit.

ii) As the total path cost is a linear sum of the individual edge costs, the method is inherently bound to linear accumulation.

Our model sidesteps the search-based framework by utilizing conditional sampling. The associated distribution is modeled by a U-net framework with convolutional and fully-connected strcuture. So it is reasonable that our model is capable of capturing non-linear and high order dependent between vertices and edges within a path. However, your concern regarding empirical testing is well-noted. We have restated non-linear accumulation as "another possible reason", "provide potential benefits for planning" to make the statement more rigorous. Please see Section 1 for additional details.

Response to W1:

Thanks for your question! We apologize for any confusion caused.

It seems the aspect that most concerns you is the Dynamic Time Warping (DTW) comparison, particularly because the numerical values are very small, ranging from 0.023 to 0.021. This is because we calculate distances using longitude and latitude coordinates. In such calculations, a unit distance corresponds to approximately 110 kilometers. Therefore, a reduction of 0.001 represents a significant improvement on a hundred-meter level, which is quite perceptible in real-world route planning. To address your concern, we have revised the distance unit to kilometers and modified the table to display improvement percentages for convenience. The original results can now be found in App.F.2. Please refer to Sec 6.2 of the revised manuscript for these updates.

Additionally, as introduced in Sec. 6.1 of the original manuscript, the Navi baseline uses the planning API from Amap (also known as Gaode Map), one of the largest mobile digital map providers in China, boasting over 100 million daily active users. Amap has invested considerable resources in enhancing navigation intelligence by developing a complex framework that integrates both rule-based and data-driven approaches, making it an exceptionally strong baseline for comparison.

Response to Q1:

Thanks for your question. We are sorry for the confusion. In fact we can choose any search-based planning algorithm as our fallback strategy (eg. the A* algorithm) to guarantee that our method always hits the goal. This will not significantly impact our performance, as our method maintains a high hit ratio of 98.6%, as illustrated in App. F.3 of the original manuscript.

Response to Q2:

Thanks for your question.

We have added an experiment on execution efficiency in App. F.5 of the revised manuscript. Dijkstra's algorithm is the fastest due to its simplicity. The execution time of our method is $0.112 \pm 0.315$ seconds, which is faster than the baseline Navi ($0.339 \pm 0.133$ seconds). Given that Navi is a real world navigation API developed by AMap (https://lbs.amap.com/), one of the leader location service providers in China, it can support real-world applications, the latency of our method is also acceptable for real-world applications. Our experiments were conducted on an Nvidia RTX 3090 with 24 GB of memory, accommodating up to a batch size of $400$. As the batch size increases, the memory cost rises linearly, but the time consumption per OD pair decreases from $0.32$ to $0.12$ seconds.

Please refer to App. F.5 of the revised manuscript for detailed information.

Response to Q3:

Thanks for your question.

Unconditional path generation is one of the solutions for trajectory data mining [1], serving as a building block for various intelligent transportation applications, such as road network planning, traffic light scheduling, and traffic bottleneck detection [2]. Recently, the success of generative models in image and text generation tasks has spurred interest in developing models capable of generating paths or trajectories, making it a compelling research topic [3]. Researchers hope that the capabilities of generative models will enhance the mining of implicit patterns from path data, enabling the creation of smarter transportation systems.

However, these methods are not suited for high-quality road map generation, primarily because they require the road network (i.e., graph structure) as an input.

[1] Yu Zheng. Trajectory data mining: an overview. ACM Transactions on Intelligent Systems and Technology (TIST), 2015.

[2] Zheng Y, Capra L, Wolfson O, et al. Urban computing: concepts, methodologies, and applications[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2014, 5(3): 1-55.

[3] Generative Adversarial Networks for Spatio-temporal Data: A Survey

Response to Q4:

Thanks for your question. The paper you mentioned is indeed interesting.

The primary distinction between our method and that work lies in the space where the diffusion process occurs: our method operates in graph space, while the other work functions in high-dimensional Euclidean space. As mentioned in Sec. 1 of our original manuscript, this difference renders the adoption of a Gaussian-based diffusion model formidable and necessitates the development of a new diffusion process. To address this, we drew inspiration from the heat conduction process on graphs and devised a novel diffusion model capable of diffusing distribution across graph space, thereby enabling us to capture the graph structure effectively.

We have added discussion of this paper into Related work, please refer to Sec. 7 of the revised manuscript.

Response to Q3:

We are sorry for the confusion.

The Algorithm 1 is designed for unconditional path generation, so it does not require any OD pairs' information.

The line 2 of Algorithm 1 simply denotes sampling raw path data from dataset under the real data distribution. The $\mathbf{x}_0$ represents a raw path data, which contains a sequence of one-hot vectors. Each represents a vertex of a path.

The U-net structure is worked as $nn_\theta$ in algorithms and equations, it takes the diffused path (during training) or random sampled vertex sequences (during evaluating) as input and outputs denoised sequences as generated path. It only requires the sequences and diffusion step $t$ as input.

We have revised the end of Sec. 4 and Algorithm 1 of the revised manuscript for better understanding.

Response to Q4:

Thanks for your comments. We are sorry for the confusion.

Regarding your concern about robustness, we present the proportion of scenarios in which each algorithm outperforms Dijkstra's algorithm. Our algorithm surpasses Dijkstra's algorithm in 86.6% and 86.8% of all test cases for DTW and LCS, respectively, marking the highest performance among all compared baselines (see App. F.2 of the revised manuscript for details).

It is not suitable to use mean $\pm$ std for the performance robustness, since the trajectory length are range from 10 vertices to hundreds of vertices (As shown in Fig. 8 of the original manuscript). So it is understandable the performances will have a large variance.

Please refer to Sec 6.2 and App. F.2 of the revised manuscript.

Response to W1:

Thanks for your comment. We are sorry for the confusion.

In the beginning of Sec. 4 and Sec. 4.1 of the original manuscript, we have highlighted the idea or reasons to follow the heat conduction. Specifically, our goal is to design a diffusion model for categorical values (i.e., vertices) that can effectively capture the graph structure, making it more suitable for graph space tasks such as path planning. While existing literature has explored diffusion models for categorical values, these studies do not focus on designing a process that captures the graph structure. However, recent research has highlighted the potential of tailoring diffusion processes to different categorical values. For instance, Austin et al. in their paper stated,"We argue that for most real-world discrete data, including images and text, it makes sense to add domain-dependent structure to the transition matrices $Q_t$ as a way of controlling the forward corruption process and the learnable reverse denoising process."

To further clarify our motivation, we have made modifications to Sec. 1 in the revised manuscript.

Response to W2 and Q2:

Thanks for your comments and we are sorry for making you confused.

The primary distinction between these two approaches stems from specific task requirements. For path planning in a road network, the output must be a connected path on the graph. This is because vital metadata such as the number of lanes, traffic lights, traffic signs, and speed limits are typically organized based on road segments rather than longitudinal or latitudinal coordinates [1]. As a result, a path on a graph is more suitable for the post-processing of navigation applications. Conversely, for certain trajectory analysis applications, the focus is more on understanding the relationships among spatial locations and areas. In these cases, generating coordinates is more practical.

Moreover, since the road network graph also includes longitude and latitude information for vertices, converting connected paths into sequences of points with these coordinates is straightforward. However, models that generate coordinate sequences face challenges in converting these into paths on a graph. This difficulty arises because the coordinate sequence generation process does not account for structural constraints. Such models may need to use map-matching techniques [2] to align the coordinate sequence with the road network.

These differences and their implications are further discussed and clarified in Sec. 7 of the revised manuscript.

[1] Zheng Wang, Kun Fu, Jieping Ye. Learning to Estimate the Travel Time. KDD 2018: 858-866

[2] Paul Newson, John Krumm. Hidden Markov map matching through noise and sparseness. GIS 2009: 336-343

Response to W3 and Q1:

Yes. In Sec. 6.1 of the original manuscript, we explained our experiment detail and put other settings in App. F.1. We are sorry for making you confused. Due to the page limit, we have to put some details in the appendix. We have thoroughly revised the paper to ensure that all detailed information provided in the appendix is appropriately referenced in the main content.

Response to W1 and Q2:

We apologize for any confusion caused. We have explained how beam search is used to maintain connectivity in App.C.2 of the revised manuscript. Specifically, the beam search is conducted after the reverse process when we have obtained the final estimated distribution $\mathbf{\hat{x}}_0$. Ideally, beam search operates in a breadth-first search manner. We start by sampling $n$ vertices from the distribution of $\mathbf{\hat{x}}_0^0$ (with replacement). Subsequently, we sample (up to $n$) neighbors of each vertex from the distribution $\mathbf{\hat{x}}_0^1$. This process continues, and we always keep (up to) $n$ sequences with the highest probability in a queue. Finally, we sample from these $n$ sequences to get the final path. In practice, however, setting $n$ to 1 suffices for good performance and efficient execution.

Without beam search, path legality is not guaranteed. If our model fails to generate an ``almost legal'' path without beam search, it suggests that the model does not accurately capture the path pattern. To address this concern, we discuss illegal cases (i.e., disconnections and loops) in App. F.3 of the revised manuscript, alongside the original hit ratio discussion. In summary, our model maintains a low ratio (less than 5%) of illegal vertices in each path, indicating its proficiency in capturing the path pattern.

Response to W2 and Q3:

We are sorry for the confusion. The Gaussian mixture model is detailed in the appendix primarily because it is utilized for unconditional path generation. In other words, the Gaussian mixture model takes only the path length as input, without additional information such as origin and destination. In practice, a Gaussian mixture model with four components effectively models the path length distribution.

The process of unconditional path generation can be summarized as follows: i) Sample from the Gaussian mixture model to determine the path length (denoted as $l$); ii) Generate a random vertex sequence of length $l$; iii) Perform the reverse process to denoise the random vertex sequence, obtaining the estimated distribution of $\mathbf{\hat{x}}_0$; and iv) Apply beam search to ensure connectivity.

For conditional path generation, we employ an exponentially increasing window size strategy, negating the need for a Gaussian mixture model for a predefined path length. We adopt this approach instead of directly sampling a long random sequence because we hope a progressive manner will better inform the network $nn_\theta$ about the path prefix, which results in more effective planning. The detailed process is outlined in Algorithm 3 in App.E. of the original manuscript. It begins with the origin as the initial path sequence, which is then diffused and concatenated with one randomly sampled vertex, yielding a (diffused) path of length two. This path is then denoised through a reverse process. Next, the path sequence is diffused again and concatenated with two new randomly sampled vertices, followed by another reverse process. This results in a path of length four. This iterative process continues until the goal is reached or the maximum length limit is hit. The exponential increasing strategy eliminates the need to predefine the path length before planning and enhances efficiency by avoiding a one-by-one diffusion process.

Response to Q1:

We are sorry for the confusion. Yes, the trivial uniform diffusion means ``generic categorical diffusion''. We have modified the description for unification in Sec. 6 of the revised manuscript.

Response to Q4:

Thanks for your comments. We have added an experiment on execution efficiency in App. F.5 of the revised manuscript. Dijkstra's algorithm is the fastest due to its simplicity. The execution time of our method is $0.112 \pm 0.315$ seconds, which is faster than the baseline Navi ($0.339 \pm 0.133$ seconds). Given that Navi is a real world navigation API developed by AMap (https://lbs.amap.com/), one of the leader location service providers in China, it can support real-world applications, the latency of our method is also acceptable for real-world applications. Our experiments were conducted on an Nvidia RTX 3090 with 24 GB of memory, accommodating up to a batch size of $400$. As the batch size increases, the memory cost rises linearly, but the time consumption per OD pair decreases from $0.32$ to $0.12$ seconds.

Please refer to App. F.5 of the revised manuscript for detailed information.

Response to Q5:

Thanks for your comments. We apologize for any confusion caused.

The forward process operates independently. However, in the reverse process, the estimation of $\mathbf{\hat{x_0}}$ is not independent because the network $nn_\theta$ adopts a U-net structure. This structure includes convolutional and fully connected layers, causing the outputs of each vertex to be interdependent. As a result, each $\mathbf{\hat{x}}_0^{i}$ is not independent. The ``mask'' you mentioned is used to prevent the sampling of unconnected vertices; it refers to the beam search.

We have revised the end of Sec. 4 of the revised manuscript for better understanding.

Response to Q6:

Thanks for your comments. Yes, we need to retrain for each city. We think the generalization is an interesting problem and consider it as future work. Also, we think that retrain for each city is acceptable. If we hope to get a model that can genralize to orher cities, we may need to train the model with various cities' data with a larger model, which would incur larger computation cost.

Response to Q7:

We have revised the typos accordingly.