GRAPH-CONSTRAINED DIFFUSION FOR END-TO-END PATH PLANNING
Authors: Dingyuan Shi
Yongxin Tong
Zimu Zhou
Ke Xu
Zheng Wang
Jieping Ye
Venue: ICLR 2024 poster (2024)
Keywords: path planning
diffusion model
Primary area: applications to robotics, autonomy, planning
TL;DR: We integrate graph structure into diffusion process hence bypassing search framework for data-driven path planning.

Abstract: Path planning underpins various applications such as transportation, logistics, and robotics.
Conventionally, path planning is formulated with explicit optimization objectives such as distance or time.
However, real-world data reveals that user intentions are hard-to-model, suggesting a need for data-driven path planning that implicitly incorporates the complex user intentions.
In this paper, we propose GDP, a diffusion-based model for end-to-end data-driven path planning.
It effectively learns path patterns via a novel diffusion process that incorporates constraints from road networks, and plans paths as conditional path generation given the origin and destination as prior evidence.
GDP is the first solution that bypasses the traditional search-based frameworks, a long-standing performance bottleneck in path planning.
We validate the efficacy of GDP on two real-world datasets.
Our GDP beats strong baselines by 14.2% ~ 43.5% and achieves state-of-the-art performances.

Published as a conference paper at ICLR 2024
GRAPH-CONSTRAINED DIFFUSION FOR END-TO-END PATH PLANNING
Dingyuan Shi
Yongxin Tong Beihang University
Zimu Zhou
Beihang University chnsdy@buaa edw.yyeuaaaeeeu.ccmmmoo edu.cn
City University of Hong Kong z zimuzhou@ci tu edu hk
yxtong@buaa edu. cn
Ke Xu Beihang University kexu@buaa, edu. en
Zheng Wang
Jieping Ye
Independent Researcher wangzheng0 0 email com
University of Michigan jiepingegmat com jpye@ eeye@umich.oo edu
ABSTRACT
Path planning underpins various applications such as transportation, logistics, and robotics. Conventionally, path planning is formulated with explicit optimization objectives such as distance or time. However, real-world data reveals that user intentions hurd-to-model, suggesting need for data-driven path planning that implicitly incorporates the complex user intentions. In this paper, we propose GDP, diffusion-basee model for end-to-end data-driven path planning. It effectively learns path patterns via a novel diffusion process that incorporates constraints from road networks, and plans paths conditional path generation given the origin and destination as prior evidence. GDP is the first solution that bypasses the traditional search-based frameworks. long-standing performance bottleneck in path planning. We validate the efficacy of GDP on two real-world datasets. Our GDP beats strong basclines by 14.2% 43.5% and achieves state-of-thed ahet performances.
INTRODUCTION
Path planning identifies an optimal sequence of vertices that forms path between the given origin and destination in a road network graph. It underpins applications across a wide spectrum of fields, including transportation, logistics, emergency services, and robotics. Traditionally, path planning is framed combinatorial optimization problem with well-defined objectives, such as minimizing the total travel distance or time. Established search-based algorithms like A or Dijkstra's 's algorithm Hart et al. 19688) Dijkstra (1559) are then employed to search a path the road network graph, where each edge is assigned à specific cost that reflects the objective in question.
However, data from real-world applications reveals that many the shortest nor the fastest Quercia et al.] (2014). This divergence suggests the complexity to model the user intentions in path planning via the conventional search-based framework under explicit objectives. Such complexity is mainly because the objectives often incorporate numerous variables that are easily modeled in closed form. For example, users might prioritize scenic paths over shorter ones for leisure drives Ceikute & Jensen (2013). 3. Another possible reason is that the search- based algorithms estimates the cost of path as the summation of composed edges, known as the linearly accumulative cost assumption, which does not always hold. For example, since the discharge rate of an electric vehicle battery is non-linear Szumaanwskki & Chang (2008), the energy cost will be different even passing the same edge, leading to different total energy cost. Hence, there is need to re-examine the methodologies for path planning to better align with the complex, real-word world objectives observed in practice.
opt for paths that neither
One thread research tries to mine user intentions or objectives by generating paths as close to those in real-world applications possible. This has evolved from simple Markov models/ Baratchi cet al. (2014) to advanced sequence-to -oreenceet--eeuence neural networks Yu et al. (2017); /Wan et al. (2022b). These models adept at producing paths from learned distributions unconditionally However, their

---

Published as a conference paper at ICLR 2024
adaptability is limited in conditional settings.e.g. path planning with given origin and destination, since they are primarily tailored to capture the inherent distribution of path datasets.
Other efforts go beyond mere pattern recognition, leveraging these identified patterns to guide path planning Tian et al. (2023); Fu & Lee (202T); Jain et al. (202T); Wang et al. (2022a). A prevalent strategy is transform the learned patterns from path data into edge weights. These weights are then integrated into search-base based algorithms like A or Dijkstra's 's algorithm Wang et al. (2019); Kong et al.)
(2019); JJin et al. (202I); Wang al. (2022a) ; Liu & Jiang (022)) These methods adopt various edge weight designs Wang et al. (2022a) Jain el al. (202T): I): Liu et al. (2020); [Wang et al. (2019); Kong et al. (2019), yet their performance is limited by the search-based framework. Specifically, search-based algorithms assume that the path cost is linearly accumulative, which may not hold and could introduce bias, especially for long paths. A remedy is to avoid planning long paths exploiting key inter-relay vertices TTin et al. (2023); Fu & Lee (2021). but the reliance on the bearch-based framework remains a performance bottleneck.
In this work, we advocate an end-to-end approach to path planning. It underscores two aspects. (i) We directly plans on the road network graph, adhering to the distribution of existing path data, instead of relying on preset optimization goals that may fail to capture the complex, real-world user intentions. (ii) We bypass the traditional search-basee of linear accumulative properties, which would also provide potential benefit for planning. Our idea is to harness generative models to implicitly mine the complex user intentions from large-scale historical path data, and to directly plan paths from the learned user intentions sampling problem. Specifically, we opted for a diffusion-basel model for end-to-end path planning for its flexibility and superior performance as generative models Saharia et al./ (2022 ; Yi et al. (2023);
algorithms,, thus eliminating the probabilistic constraints
conditional
Ajay et al. 2023). However, designing such an end-to-end solution is non-trivial due to the following challenges. (i) How to design diffusion model for path generation under graph constraints? (ii) How to enable conditional generation for path planning with given origin and destination? The graph structure prohibits the adoption of traditional diffusion model in Euclidean space, and it also requires extra design for graph structure capturing.
In this work, we propose a new diffusion model, termed Graph-constrained Diffusion for Planning (GDP). It enables end-to-end path planning via conditional sampling and is also capable of uncondi- tional path generation. Inspired by the physics heat conduction, we devise novel diffusion-based unconditional path generation model that explicitly accounts for the constraints imposed by road networks. We then exploit a tailored self-attention mechanism to transform the destination and other spatiotemporal information into prior evidence for conditional sampling from the path generation model. Our main contributions are threefold.
We introduce a novel diffusion model for path generation. To the best of our knowledge, it is the first diffusion model for generating paths while complying with graph constraints imposed by road networks.
We design a conditional sampling scheme to enable path planning via our diffusion model. enables end-to-end data-driven path planning, which eliminates the performance bottleneck in conventional search-basee frameworks.
We validate the efficacy of our approach through experiments two real-world datasets. Our GDP beats strong baselines by 14.2% ~ 43.5% and achieves state-of-the-art performances.
PROBLEM DEFINITION
We define a path on road network as follows.
Definition 1 (Path). Consider an undirected graph = {V, F) with vertices V and edges F., If u V is adjacent, then (u, v) E E. A path x is defined as a sequence of vertices (vo, Ui. U|x)
where each pair of vertices are adjacent, i.e., Vi = 0, 1, |x| 1, (V;, Ut+1) E E.
We assume G is connected without self-loop parallel edges, which is reasonable for road network. Conventionally, path planning is formulated as the following optimization problem. Definition 2 (Path planning). Given weight we assigned to each edge and an origin digttndestination pair (OD pair) (ori, dst) which contains two vertices, path planning aims to find a path x = (vo. P|x))
such that vo ori and U|x] = dst, and the path minimizes _ ((o.))11)
2

---

Published as a conference paper at ICLR 2024
As explained in the introduction, explicitly assigned edge weights and preset optimization objectives may fail to capture the complex user intentions in real-world path planning applications. Accordingly, we formulate path planning as the following generation problem.
Definition (End-to-end path planning). Given path dataset P that contains [P] paths, we aim to
plan paths for given OD pairs, such that the planned paths follow the distribution P.
We focus on generic path planning Jain al. (2021) Tian al. (2023) and will extend personalized path planning by integrating user profile data in future work.
Table T summarizes the important notations that will be used throughout this paper.
Table 1: Notations
NOTATIONS
DESCRIPTION
G= (V.E) x, P
A graph and its vertices and edges
A path and path dataset
(VD, UI, .... U/))
A vertex sequence of path P origin and destination of path planning task The i-th vertex of path The diffused path time step
ori, dst
x², 04
X3
Q
[V] x [V] transition probability matrix Adjacent matrix and degree matrix of a graph The i-th row and j-th column element of matrix M
A.D
M
M M/MM,
The i-th row / j-th column of matrix M Transition probability matrix for diffusion process Row vectors with length [V] indicating a categorical distribution One-hot row vector with length [V] indicating vertex Row vector indicating the estimated distribution for a vertex A categorical random variable with distribution p Hyper parameters that control the diffusion scale
C
p.g(.)
V Cat(-Ip) City 31
3 SOLUTION OVERVIEW
We solve the end-to-end path planning problem by converting it into a conditional sampling task. Its objective is to determine the probability distribution of paths given origin and destination, represented as pxx). Then drawing a sample from this distribution yields planned path. Following Janner al. 20022) the conditional sampling probability can be expressed as: dst)
p(x) Pe
where po (x) denotes the unconditional probability and h(xlori, dst) represents the prior evidence. Consequently, our solution focuses on two designs.
How to determine the unconditional path probability, i.e., px())
How to incorporate the origin and destination data as prior evidence, ie., h(xlori, dstt?
We elaborate on the corresponding designs in the next two sections, respectively.
4 DIFFUSION-BASED UNCONDITIONAL PATH DISTRIBUTION MODELING
As mentioned Section 3] we start with a generative model that models the path distribution, independent of the origin and destination. Despite studies Baratchi et al. (2014); Yu et al.) (2017); Wu et al. (2017); Wang et al. (2022b) that explored various sequence-to-see to-seuunce models for path pattern mining, opt for the diffusion model modee[Sohl--ickeeee Sohl-Dicksten al. (2015). The reasons are two-fold. (i) Diffusion models demonstrate superior performances in complex generation tasks Saharia et al. (2022); ; Ajay al. 2023);; Yi et al. (2023). (ii) Diffusion models are more flexible to incorporate categorical constraints such as those imposed by road networks than conventional sequence-to- sequence models.
3

---

Published as a conference paper at ICLR 2024
4.1 PRINCIPLES AND REQUIREMENTS FOR DIFFUSION PROCESS DESIGN
To generate high-quality paths, our diffusion model directly operates on road networks by explicitly
incorporating the connectivity constraints imposed by the graph G. We draw insights from categorical diffusion models Austin et al. (202T): [Hoogeboom et al. (202T), since vertices are categorical
variables. The general framework as below:
q (t-1) = Cat(e; P (((--))..))
(2)
where Uy denotes categorical value at diffusion step L, q(+) a row vector of categorical distribution and Q₂ represents the transition probability matrix. Cat(-) denotes a categorical distribution. The i-th row and j-th column value of Q is the transition probability from category to j.
In generic categorical diffusion, a prevalent choice for Q₁ is az vi + B,11 /IV|, where L is an identity matrix with |V] rows and columns and 1 is a column vector with all elements set to 1 Austin al. (202T); D); Hoogeboom et al. (202I); Yi et al. (2023). The hyperparameters a and 3, I ar modulate the forward diffusion process's 's scale. Essentially, Q2 slightly perturbs the original vertex's 's probability and uniformly redistributes it across other vertices. As goes to infinity, the distribution of ((v) will ultimately converge to uniform distribution.
Notably, Austin et al. (202T) highlighted the significance of designing a domain-speeiife transition probability matrix. Yet, a tailored transition probability matrix for graph topology remains elusive in existing literature, a void our research seeks to fill. In our graph-constrained situation, where all vertices are situated in graph space, a generic categorical diffusion process fails to capture this structure, In fact, we hope the forward diffusion process should exhibit locality. This locality property will condense the probability around the original vertex with smaller diffusion step t, hence the process will capture the graph structure. Analogous to image generation, smaller values yield reduced covariance, keeping pixel values close to their origin. As grows, pixel values trend towards a normal distribution. Similarly, in our context, each "pixel" corresponds to a vertex, and we desire the diffusion process to reflect this locality, especially for smaller t. Our goal is for the diffusion process to spread probabilities across neighboring vertices, converging to uniformity as f approaches infinity.
Together with commonly properties sought after in diffusion models Yi al. 20233, the requirements are: (i) offers a closed form for forward process, (ii) ensures a computationally feasible posterior q(v2_1/0, p,, vo). (iii) makes ((T) independent of g(vo) for uninformed sample generation, and (iv) exhibits locality for smaller values.
To address these, we employ the heat conduction partial differential equation, detailed in next sections. We first design diffusion process for vertices in graph space, then extend it to path, i.e., a sequence of vertices.
4.2 DIFFUSION PROCESS FOR A SINGLE VERTEX
We incorporate heat conduction process to construct our diffusion process. Specifically, we view probability as heat graph, then use conduction process to change probability for diffusion process.
Heat Conduction on Graph. Considering each vertex point heat source, heat diffuses uniformly across all vertices. While "diffuse" typically has a different connotation in diffusion models, in this context, it pertains to heat conduction the graph. Henceforth, we use "heat conduction" to avoid confusion. The heat conduction equation is given by:
Oh Ot
Ah
where h is row vector of size (V), indicating each vertex's 's heat. The Laplacian operator, A, for vertex is the sum of differences between it and its neighbors. This equation suggests a vertex's 's heat change rate depends on its heat difference with neighbors. Using the adjacency matrix A and degree Oh h(A - D), where A is the adjacency matrix and D is a
matrix D, we can express this as at diagonal matrix with D/i, i] representing vertex's 's degree. Solving this equation yields Chamberlain cet al. (202T):
h C.
4

---

Published as a conference paper at ICLR 2024
with transition matrix C, = ((A-D); This represents heat conduction graph over time t.
Forward Diffusion Process. By substituting the heat of each vertex with probabilities Equation we can derive our diffusion process follows
((v)(et-1) Cat(v:lq(n--1)C,,
(5)
The matrix C has several beneficial properties: (i) C- is a symmetric matrix L.e, C C,. (ii) C. C, Cr Ckr = (C,)*. (iii) C, C, - I as - O. (v) Summation of each row or column for C, is VT > 0, if graph is connected. The proof for these properties is provided in (App. AD.
11"/IV
oo if graph is connected. (iv)
By incorporating a series of hyper parameters 3r, we can derive the closed form of forward process q(v, ub) = Cat(v:lp = voC+) where C C.C2...CC Cg. C 8, Vo one-hot row vector indicating the vertex.
(6)
Note that property (i) simplifies notation by omitting the transpose superscript. Property (ii) provides closed form for the forward process (see (p) which fulfills requirement (i). Property (iii) satisfies requirement (iii) because it ensures the final probability q(vr) is uniform distribution independent of ((vo). Property (iv) captures the desired locality (requirement (iv)). Property (v) guarantees p(v;)
remains a valid probability distribution since the sum of v is 1, A visual representation of probability diffusion graph is shown in Figure where probability initially centered one vertex disperses across others over time.
Figure 1: Illustration for forward process of single vertex. Warmer color means larger probabilities.
Our forward process meet the requirements (i).(i) and (iv) as we have mentioned above. Next we design the reverse process meet requirement (ii). Le., the posterior (12-1//0 Un) is tractable.
Reverse Process. To derive the reverse process, our goal is to find a tractable posterior probability distribution q(v,- [u,, vg). Utilizing the Bayesian rule, the Markov property and symmetry property (property (i)) of the diffusion process, we have q(1/-1/14 | 0n) = Cat(#--1 x v,C, O vo C.-)). where @ denotes element- wise multiplication. When caleulating the posterior ((1,11/0, Ug), however, we do not have the original Vo- Hence we can only use the estimated Vo which is the estimated distributions of Up. Thus we have
qV6-1l0 0o) Cat(u v VV.C.-1)
The detailed derivation is provided in (App. B
4.3 DIFFUSION PROCESS FOR A PATH
We have detailed the diffusion process for individual vertices. Now, we address paths, sequences of vertices. We differentiate between "time" in diffusion steps (subscripts) and vertex order in paths (superscripts). For instance, x denotes the i-th vertex in path x at diffusion step t. At 0, Xo x is the initial path.
For path diffusion, we can either strictly maintain vertex connectivity or treat as contextual. We opt against strict connectivity for two reasons. (i) Preserving connectivity without information loss is complex. It introduces conditional probabilities like p(x xx ), complicating reverse processes and conflicting with diffusion models' non rege-segres nature Janner et al. (2022). (iii) In real road networks, many vertices have limited adjacency. Strict connectivity restricts diffusion space, making g(xx) overly reliant on (xxo). violating requirement (ii).
Thus, diffuse each vertex independently. While individual vertices retain their locality in paths, the entire path's 's vertices stay close to their original positions for small t. For large t, vertices become random, aiding sample generation.
5

---

Published as a conference paper at ICLR 2024
The forward closed form process therefore can be represented
(x, Xn)
I1 x [xx
@ Cat(x:/p= -x
(8)
As for reverse process, can be represented as follows.
( ko)
x ;=1 Cat /p x
(9)
where & indicates Cartesian product and |x| denotes the lengths of path x.
Note that in reverse process, each vertex distribution is not independent with each others. This because when estimating Xo. build neural network nig. It takes the x; and diffusion time step t as input (i.e., Ten t) = Po( (x)o)x)),, x))), then output the estimate q(x:-1|xx, 8o) by Eq. This nng adopts U-net structure RRoneebrrger al. (2013), and its convolution together with fully connected layers help model dependency among vertices. The detailed design is shown in (App. C.T).
To ensure the final path connectivity, we do not directly sample on &n- Instead, we view Xn as proposal and conduct beam search. The detailed sampling process can be found (App. C.2).
PATH PLANNING AS CONDITIONAL SAMPLING
As mentioned in Section we are required to devise model to calculate h(xlori, dst). A trivial method is simply adding the source and destination vertex information as condition to guide the generation process. However, this method can hardly work, mainly because path planning has a strong spatial property. So we need to build features for spatial property for better generation. Specifically, we need to (i) build spatial features as prior evidence and (ii) integrate the prior evidence into our unconditional sampling.
Make Spatial Features as Prior Evidence. To build spatial features as prior evidence, we design an attention-ban based model seqs (see F)gure It takes the origin, destination and prefix of the current path input, then outputs the probability of the next vertex. Please refer to (App. D for detailed structure.
Sampling Process. Together with the diffusion model, we can now conduct path planning as conditional generation (see Algorithm (App. ED) The overall steps can be summarized as below: it (i) gets the next vertex probability based on prefix path (which contains only origins initially) by Eq.() based on model nen and seqs. And (ii) samples from the probability to get the next vertex and (fii) appends it to the prefix for next prediction till we hit the destination reach the maximum length restriction. The core of the above steps is the calculation of Eq. (T). The prior evidence term 1(-Jori, ds() can be calculated based seqa- While for the unconditional probability term p(-), we need to bring in the current prefix information for generation. So we first diffuse the prefix by (q.48) and concatenate with uniformly sampled sequence, then diffusion model mmg conduct reverse process to denoise the whole sequence, hence get the estimated &g. To avoid frequent call of the forward and reverse diffusion process, we double the length of uniformly sampled sequence for concatenation in each iteration, hence the length of planned path will increase exponentially.
6 EXPERIMENTS
6.1 EXPERIMENTAL SETTING
Dataset. We use two real datasets city and city B from Didi Gaia Please refer (App. preprocess, parameter setting and other implementation detail.
F. for
Baselines. For path planning, we choose four below algorithms as our baselines. Dijkstra's algorithm (DA (DA Dijjktta (1959) searches the shortest distance path for given OD pairs. NMLR Jain al. (02T)) learns the distributions based on Markov property assumption and search the paths with the largest probabilities each step. Key Segment (KS) Tian et al. (2023) detects the relay vertex for
https://gati didi chuxi com

---

Published as a conference paper at ICLR 2024
the given OD pairs, then plan paths from origin to relay and then to the destination. Navigation API from Amap (Navi) calls the planning API from Amap to get the path.
Also, compare with path generation algorithms to directly justify the effectiveness of our generative model. N-gram directly estimates the transition probability p( 1h.-...... ( by counting the frequency. HMM Yin et al. (2018) is hidden Markov model based algorithm which reduces state numbers. CSSRNN Wu et al. (2017) ) and MTNet Wang et al. (2022b) both adopt an LSTM-basee model for better capturing long sequence pattern.
Evaluation Metrics. For planning, we use Dynamic Time Wrapping (DTW) Müller (007) and Longest Common Subsequence (LCS) LLLCS/Beegrott et al. (2000) to measure the similarity between planned paths and the ground truth paths. A smaller DTW or larger LCS indicates better performance.
For generation, the most commonly used metrics is Neg-Log--Likelhhood (NLL) Wu et al. (0177): Wang et al.] (20226). Apart from that, we also use Kullback-Leible divergence w.r.t. Edge Visit distribution (KLEV). KLEV indicates a first-order transition similarity between two datasets. By replacing Kullback-Leible divergence with Jensen-Shannow divergence, we analogously define ISEV. NLL and KLEV/ISEV evaluate the performance from perspective of high-order and first-order transition, respectively. The specific definition can be found in (App. F.I
6.2 EVALUATION RESULTS
Table 2: Evaluations for path planning. Smaller DTW larger LCS means better performance.
Methods
City Metrics
DA
NMLR
KS
Navi
GDP (Ours)
DTW
274.2%
-1.2%
-11.1%
-30.9%
A
LCS
5.59%
24.1%
45.9%
80.8%
DTW
250.8%
1.8%
-3.16%
-15.9%
B
LCS
9.02%
32.2%
55.9%
82.6%
Path planning evaluation. For path planning evaluation, sample 1000 number of paths uniformly from test datasets. Then we conduct path planning and compare the similaritics(Ser SSe Table 2). For convenience we take Dijkstra's 's algorithm represented by the percentage improvement relative to Dijkstra's 's algorithm. Please refer (App. F2) to for the raw results. Our GDP performs best among all other baselines (e.g., improves LCS by 80.8% and reduces DTW by 30.9% with regard to Dijkstra's 's method in City A). We notice that, the most compatible baseline is Navi, which indicating that the algorithm deployed in real industry also adopts data-driven approaches. Also, the most recent existing method KS achieves second best in baselines. We also find some existing methods do not out perform naive Dijkstra's 's methods well. This is probably because NMLR still adopts the Markov Property which confines the capture of higher order relationship underlying path data.
benchmark, and the performance of other algorithms is
Another important question is how our method can ensure to hit the destination. We use both test and shuffled OD pairs for validation. The test OD pairs are directly sampled from the test dataset our model has never seen. To generate the shuffled OD pairs, we first sample OD pairs from the test dataset and then shuffle them. Shuffle operation adds more difficulty to our model for planning tasks, since the shuffled OD pair distribution is different from the original test dataset, forcing model to use sub-level patterns for generalization. Overall, our method keeps the hit ratio from 94.2% to 99% average, indicating its availability. Please refer (App. F.3) for detailed discussion.
Next we present some cases of City A for illustration. Again, we use test and shuffled OD pairs. For test dataset ground truth. For shuffled OD pairs, can not get ground truth
test OD pairs, from dataset so we call the Navi for comparison. Figure 2 provides illustrations of the planned paths look like.
Unconditional generation evaluation. The generation comparison among all methods with respect all metrics are shown in Table 3 Our GDP algorithm outperforms all baselines overall datasets. For NLL, it is shown that neural network based model (CSSRNN, MTNet and our GDP) perform significantly better than count based model (N-gram, HMM). This is because NLL evaluates high order
httpss///bbs http:/.sssaaa.....mmmm amap. com
7

---

Published as a conference paper at ICLR 2024
(a) OD Pairs, Real (b) Test OD Pairs, GDP (c)
Shuffled
Pairs, (d) Shuffled OD Pairs, GDP
Navi
Figure 2: Blue/red lines indicates the ground truth/planned paths.
Table 3: Evaluations for unconditional generation. Lower values means better performance.
Methods
City Metrics
N-gram
HMM
CSSRNN
MTNet
GDP (Ours)
GDP-
NLL
300.144
278.23
27.742
69.859
24.697
43.582
KLEV
7.300
6.804
7.348
6.274
5.724
7.273
JSEV
3.309
3.061
3.3325
2.795
2.518
3.295
NLL 319.662
302.506
27.890
83.679
23.740
47.418
B
KLEV 7.719
6.863
7.356
6.419
6.128
7.678
JSEV
3.521
3.092
3.337
2.869
2.724
3.500
transition probability and nerual network models are designed capture this sequence information.
Those count-based models, however, are based on Markov property assumption, can hardly capture high order information, leading KLEV and JSEV), however, neural network models only slightly outperform count based baselines. This indicates that our models can capture the long sequence information those sequence model, which is mainly attributed to the attention module of temporal U-net. For ablation study, we adopt GDP-, which built by replacing our heat conduction diffusion method with a generic categorical diffusion (with transition probability matrix Q |xIivv + B 3,117/[VVD. The degradation of performances testify the effectiveness our diffusion method. Other comparison between generated and real paths can be shown in (App.
poor performance. As for first order evaluation metrics (i.e.,
Forward and reverse process. Now we provide a case study to illustrate how our diffusion process working (See 3). We randomly pick 5000 paths from city B. In the forward process, each vertex gradually perturbed to other vertices. Because of the locality property our process, when small the vertices tend to stay close original vertices. As t increases, all vertices tend to uniformly distributed, hence the paths become out of order. In the reverse process, the estimated & gradually reverse back the original paths.
Forward Process
10
Reverse Process
t=0
t=4
c=
t= 99
Figure 3: The forward and reverse process for paths in city B
Other experiments such as execution efficiency are put into (App. Fb due to the page limit.
7 RELATED WORK
Path Generation for Pattern Mining, Path pattern mining dates back to the 1990s, where locations modeled as states in Markov chain models Sutton & Barto (998). Hierarchical hidden states
8

---

Published as a conference paper at ICLR 2024
be used mitigate the sparsity in the vast state space Baratchi et al. (2014). while contextual data e.g. weather can be integrated to enhance path generation accuracy Yin et al. (2018).
To capture complex patterns, the recent approach is to combine Markov Decision Process (MDP) with reinforcement learning. For example, location transitions can be exploited as routing actions to optimize the MDP via value iteration ZZeng & Ni (2014). A Generative Adversarial Network (GAN) can be integrated as the reward function for further refinement Yu et al. (2017): Choi et al. (2021).
To model long paths,
soreenee-to-squeneee (seq2seq) models have been employed. As seq2seq models are primarily devised for language processing, the challenge is to comply with the topological constraints of road networks. Some studies introduced "lookup" operation, enabling recurrent neural networks for path generation Wu et al. (2017). Others masked the final output of the probability distribution to prevent invalid vertices Wang et al. (2022b). The status quo adopts an encoder-decoder structure: encode the path sequence into a latent space, train generative model on the latent vectors, and decode the latent vectors back to paths Rao et al.] (202T): Huang et al. (2019); |Fnn et al. (2020).
Despite extensive path generation studies for pattern mining, they generate paths unconditionally, and are not easily extendable to conditional generation, thus limiting their applicability to path planning.
Data-driven Path Planning. Data-driven approaches can be employed to capture the hard-to-model user intentions to improve path planning QQercia et al. (2014). Due to the difficulty to ensuring connectivity and reaching the destination in a pure data-driven solution, existing solutions halt at incorporating data-driven insights with traditional search-based algorithms. They differ in the edge weight designs, e.g., negative log-likelihood Wang et al. (2022a): Jain et al. (2021). heuristics from inverse reinforcement lcarning Liu et al. (2020), and neural network informed weights Wang et al. (2019); Kong et al. (2019). Yet the search-baser framework fundamentally limits the ability to capture the non- non-linear, high-order dependencies in paths, especially in long paths. One remedy is to identify key inter-relay vertices to reduce the path lengths in planning Tian al. (2023); Fu & Lee (2021). However, the search-base based framework remains the primary performance bottleneck.
Our work falls into this thread of research, but completely breaks free from the search-based frame- work, thus enabling an end-to-end data-driven path planning solution.
Categorical Diffusion Models. Diffusion models
al. (015)) prove effective in complex generation tasks across various domains, including computer vision Saharia et al. (2022),
chemistry Yi et al. (2023), , and roboties planning Ajay et al. (2023). ). Many interesting diffusion-basee planner such as Carvalho et al. (2023)) happens in Euclidean space and are not suitable in our graph space. Our work inspired by the advances in categorical diffusion models Austin et al. (2021): ));
Hoogeboom et al. (2021). where they enables diffusion process for categorical values. However, they do not easily adapt to graph constraints.
Our work is most related to Zhu et al. (222)). where a diffusion model is applied to generate GPS- coordinate trajectories. Since the GPS coordinates represent numerical values in a two-dimensional Euclidean space rather than graph space. In planning task, however, we are required to output path on road network graph since the post-process of navigation will integrate other information like lanes, traffic lights and speed limitation into the path. These information is usually organized by road segments (rather than coordinates) Wang et al. (2018) and a path on graph will help easily fetch them.
To the best of our knowledge, we are the first to generate paths with explicit graph constraints using diffusion models.
8 CONCLUSION
This paper introduces GDP, a novel diffusion- based model tailored for end-to-end path planning. We conceptualize the path planning problem as conditional sampling task. To effectively capture the graph topology structure, we designed a unique diffusion process. Furthermore, by employing a self-attention mechanism, we integrate OD pair information as conditions into the probability space, bypassing the traditional search framework. Evaluations demonstrate GDP's proficiency in discerning the distributions inherent in the provided path dataset. Moreover, it can plan paths whose distributions align closely with existing paths. We envision our approach will facilitate the path planning smarter for modern intelligent transportation system. Besides, the post process for path legality will slightly change the sampling distributions provided by our diffusion model. Designing an algorithm without any post process is interesting and remains open problem.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers for their suggestions. This work was partially sup- ported by National Science Foundation of China (NSFC) (Grant Nos. U21A20516, 6233000216) and Beijing Natural Science Foundation (Z230001), the Basic Research Funding in Beihang University No. - and Didi Collaborative Research Program NO2231 122-00047. Zimu Zhou's research is supported by Chow Sang Sang Group Research Fund No. 9229139. Yongxin Tong is the corresponding author in this paper.
REFERENCES
Anurag Ajay, Yilun Du, Abhi Gupta, Joshua B. Tenenbaum, Tommi S. Jaakkola, and Pulkit Agrawal. Is conditional generative modeling all you need for decision making? In The Eleventh Inter- national Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023.
OpenReview.net, 2023.
Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 17981-17993, 2021.
Mitra Baratchi, Nirvana Meratnia, Paul J. M. Havinga, Andrew K. Skidmore, and Bert A. G. Toxopeus. hierarchical hidden semi-markov model for modeling mobility data. In A. Brush, Adrian Friday, Julie A. Kientz, James Scott, and Junehwa Song (eds.), The 2014 ACM Conference Ubiquitous Computing, UbiComp 14, Seattle, WA, USA, September 13-17, 2014, pp. 401-412. ACM, 2014.
Lasse Bergroth, Harri Hakonen, and Timo Raita. A survey of longest common subsequence algorithms. In Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000, pp. 39-48. IEEE, 2000.
João Carvalho, An T. Le, Mark Baierl, Dorothea Koert, and Jan Peters. Motion planning diffusion: Learning and planning of robot motions with diffusion models. CORR, abx/2308.01557, 2023. doi: 10.48550/ARXI1223088000
URL https: wtt.d/d...rg.......1... 1 http://0..5550/xxxv....o
01557
Vaida Ceikute and Christian S. Jensen. Routing service quality - local driver behavior versus routing services. In 2013 IEEE 14th International Conference on Mobile Data Management, Milan, Italy, June 3-6, 2013 Volume 1, pp. 97-106. IEEE Computer Society, 2013.
Ben Chamberlain, James Rowbottom, Maria I. Gorinova, Michael M. Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: graph neural diffusion. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 1407-1418, PMLR, 2021.
Seongjin Choi, Jiwon Kim, and Hwasoo Yeo. Trajgail: Generating urban vehicle trajectories using generative adversarial imitation learning. Transportation Research Part C: Emerging Technologies, 103:9, 2021.
Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 269-271, 1959.
Jie Feng, Zeyu Yang, Fengli Xu, Haisu Yu, Mudan Wang, and Yong Li. Learning to simulate human mobility. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash (eds.), KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, ACM, 2020.
USA, August 23-27, 2020, pp.
Tao- Yang Fu and Wang- Chinn Lee. Progrpgan: Progressive GAN for route planning. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 393-403, ACM, 2021.
10

---

Published as a conference paper at ICLR 2024
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pp. 855-864 ACM, 2016.
Peter E. Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., 4(2):100-100) 1968.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021,
NeurIPS 2021, December 6-14, 2021, virtual, pp. 12454-12665, 2021.
Dou Huang, Xuan Song, Zipei Fan, Renhe Jiang, Ryosuke Shibasaki, Yu Zhang, Haizhong Wang, and Yugo Kato. variational autoencoder based generative model of urban human mobility. In 2nd IEEE Conference on Multimedia Information Processing and Retrieval, MIPR 2019, San Jose, CA. USA, March 28-30, 2019, pp. 425 -25. IEEE, 2019.
Jayant Jain, Vrittika Bagadia, Sahil Manchanda, and Sayan Ranu. Neuromlr: Robust reliable route recommendation on road networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp.
2021.
Michael Janner, Yilun Du, Joshua B. Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp.
PMLR, 2022.
Jiangtao Kong, Jian Huang, Hongkai Yu, Hanqiang Deng, Jianxing Gong, and Hao Chen. Rnn-based default logic for route planning in urban environments. Neurocomputing. 338:307-320, 2019.
Shan Liu and Hai Jiang. Personalized route recommendation for ride-hailing with deep inverse reinforcement learning and real-time traffic conditions. Transportation Research Part E: Logisties and Transportation Review, 164: 102780, 2022.
Shan Liu, Hai Jiang, Shuiping Chen, Jing Yc, Renqing He, and Zhizhao Sun. Integrating dijkstra's algorithm into deep inverse reinforcement learning for food delivery route planning. Transportation Research Part E: Logistics and Transportation Review, 142:102070, 2020.
Wannes Meert and Mathias Verbeke. Hmm with non-emitting states for map matching. In European Conference on Data Analysis (ECDA), 2018.
Meinard Müller. Dynamic time warping. Information retrieval for music and motion, pp. 69-84, 2007.
Daniele Quercia, Rossano Schifanella, and Luca Maria Aiello. The shortest path happiness: recommending beautiful, quiet, and happy routes in the city. In 25th ACM Conference on Hypertext and Social Media, HT 14, Santiago, Chile, September 1-4, 2014, pp. 116-125. ACM, 2014.
Jinmeng Rao, Song Gao, Yuhao Kang, and Qunying Huang. Lstm-trajgan: A deep learning approach to trajectory privacy protection. In Krzysztof Janowiez and Judith Anne Verstegen (eds.), 11th International Conference on Geographic Information Science, GlScience 2021, September 27- 30, 2021, Poznań, Poland Part 1, volume 177 of LIPIcs, pp. 12:1-12:17. Schloss Dagstuhl Leibniz--Zentrum für Informatik, 2021.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assi Assistee Intervention MICCAI 2015 18th International Conference Munich, Germany, October 5 9, 2015, Proceedings. Part III, volume 9351 of Lecture Notes Computer Science, pp. 234 241. Springer, 2015.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L. Denton, Seyed Kam- yar Seyed Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet. and Mohammad Norouzi. Photorealistic text-to-image diffusion models with deep language understanding. In NewrlPS, 2022.

---

Published as a conference paper at ICLR 2024
Jascha Sohl-Dickstein. Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference Machine Learning. ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp- 2256-2265. JorR.org. 2015.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning an introduction. computation and machine learning. MIT Press, 1998.
Adaptive
Antoni Szumanowski and Yuhua Chang. Battery management system based on battery nonlinear dynamics modeling. IEEE Trans. Veh. Technol., 57(3):1425-1432, 2008.
Wei Tian, Jieming Shi, Siqiang Luo, Hui Li, Xike Xie, and Yuanhang Zou. Effective and efficient route planning using historical trajectories on road networks. Proceedings of the VLDB Endowment, 16(10):251222524 2023.
Jingyuan Wang. Ning Wu, Wayne Xin Zhao, Fanzhang Peng, and Xin Lin. Empowering a search algorithms with neural networks for personalized route recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 539-5479997. ACM, 2019.
Jingyuan Wang, Ning Wu, and Wayne Xin Zhao. Personalized route recommendation with neural network enhanced search algorithm. IEEE Trans. Knowl. Data Eng., 34(12):5910-5924 2022a.
Yong Wang, Guoliang Li, Kaiyu Li, and Haitao Yuan. A deep generative model for trajectory modeling and utilization. Proc. VLDB Endow., 16(4):973-985, 2022b.
Zheng Wang, Kun Fu, and Jieping Ye. Learning estimate the travel time. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 858-866. ACM, 2018.
Hao Wu, Ziyang Chen, Weiwei Sun, Baíhua Zheng, and Wei Wang. Modeling trajectories with recurrent neural networks. In Carles Sierra (ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 3083-3090. ijcai.org, 2017.
Kai Yi, Bingxin Zhou, Yiqing Shen, Pietro Liò, and Yu Guang Wang. Graph denoising diffusion for inverse protein folding. CoRR, abs/2306.16819, 2023. doi: 10.48550aarXiv.2266.18811 URL 481500..4555aaa0
16819
Mogeng Yin, Madeleine Shechan, Sidney Feygin, Jean-François Paiement, and Alexei Pozdnoukhov. A generative model of urban activities from cellular data. IEEE Trans. Intell. Transp, Syst., 19(6); 1682-1696, 2018
Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu. Seggan: Sequence generative adversarial nets with policy gradient. Satinder Singh and Shaul Markovitch (eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pp. 1852-2855 AAAI Press, 2017.
Jangehuan Zheng and Lionel M. Ni. Modeling heterogeneous routing decisions in trajectories for driving experience learning. In A. J. Brush, Adrian Friday, Julie A. Kientz, James Scott, and Junehwa Song (eds.), The 2014 ACM Conference on Ubiquitous Computing, UbiComp '14, Seattle, WA, USA, September 13-17, 2014, pp. 951-961. ACM, 2014.
Yuanshao Zhu, Yongchao Ye, Xiangyu Zhao, and James J. Q. Yu. Diffusion model for GPS trajectory generation. CoRR, abs/2304. 1 1582, 2023. doi: 10.488550/arxiv.234.. 11582, URL https://doi.org/11 (tl.or///1.....///.. 2304. 11582
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A PROOF FOR PROPERTIES OF MATRIX C,
(i) C, is symmetric matrix i.e., C Cr.
(A-D)*+* Because both and is symmetric, so Proof. we have C, = c(A-D)r I Ex=1 &
(A - D) x is symmetric for any k. Thus we have C, is symmetric.
(ii) Cr Cn Cr2y Ckr = (C,)
Proof. By letting X (A - DDTT, Y (A-D) (D-D) we have
(X +Y
x
C T1-22 =xx+
n!
n!
n=0
n=0 k=0
(10)
Xkyn-k
kl(n k)!
==0 k=0
also have
X y
C. =xx
n=
X2
y2
= (11+ X + ...
+Y + +..) =
+ XY YX + 2 ) +... (11)
Xkyn-k
k!(n k))!
where in the second line we rearrange all terms based on there orders, and the coefficient is same as the binomial coefficient. By letting Ji 72 and mathematical induction, have Ckr (C,)**
(iii) C, + 11m / as t + co if graph is connected.
Proof. We use the heat conduction equation for proof. From the physical process, the heat will eventually evenly distributed to all vertex, so it will become 11 /|V] whatever the initial values.
(iv) C, Ias 0.
Proof. When т + O, due to the continuity, C, - Cg. i.e., I.
(v) Summation of each row column for C, is Vr > 0, if graph is connected.
Note that based on the physical meaning, we have 1 ITC,, Vr 0. Thus, for each column j. we have ['] [:.j] + E. [i,j 1, Vj. Based on the symmetric property, we get the summation for each row or column always 1.
Proof.
B DERIVATION FOR REVERSE PROCESS
Utilizing the Bayesian rule and the Markov property of the diffusion process, we have
vo) g(velv,11, v)) g(ve-1luo) = q(v1/1z-1) g(v2-1/20)
((v)11))
(12)
x g(vu|u:-))((
CCt(ut-1/p v.C, O voC,-1)
where @ denotes element-wiss multiplication. Note that the original (u)/)))1)) for any category value & should be v.C. where is one-hot row vector with ey [k] 1. This is because ( is the probability from vertex i to j and v, C, [i. j] will be the probability into category We leverage
the symmetry property (property (i)) and omit the transpose for convenience. When calculating
13

---

Published as a conference paper at ICLR 2024
the posterior q(vt-1| vo), however, do not have the original Vo. hence can only the estimated Vo which the estimated distributions uy- Thus we have
(vr-11/0,, 00) = Cat(v: 1p & vyCr O Vo CI))
(13)
C DIFFUSION MODEL DESIGN
C.I MODEL STRUCTURE
Instead of 2-D convolutional neural network (CNN), we employ a 1-D CNN for the temporal dimension. We have omitted the samn-sampling and ua-sampling blocks from U-net, as they risk significant information loss. Each path vertex is crucial, holding more significance than an image pixel. Down-sampling and up-sampling can also misalign horizons, and typical solutions like linear interpolation not fit for categorical path data. We use the Node2Vec algorithm Grover & Leskoved (2016) to obtain pre-trained vertex embeddings, which feed into our neural network. Our architecture depicted in Figure
embelding
x [PL--PPp
Nock2Net
horizon:
Postsoonll
Finbedding
Time emaedding
Former outpul
Concert
Attantion
Verius embosking
Time embodding
Figure 4: Our neural network design.
We use Kullback-Leibler divergence between pa (x,- |xe, &o) and q(x:-1 Xo) as our training
loss function.
Our training algorithm is shown in Algorithm path generation.
Next we discuss how to use our trained model for
Algorithm 1: Training
Algorithm Sampling
Input: Dataset P, model nng Output: model nng
Input: na
Output: generated path
for training_stee steps + 1, do Xn (Xa)
Sample length from Gaussian mixture model
Xy 8/,4[1, [V]]
t t~ [[1
for | + T,.., do
X1 ~ (x) by Eq.
& nno (x.,)) sample x,-1 by Eq.
pa(8o (x)) = nno Xx, JJ
calculate loss and update ning
end
end
Xg <- return
apply beam search via Xy
return mng
Loss function design. In general, we are required to estimate Po (x+- 1x,, &n) q(x,11/x, 2o) (x).. We can minimize the Kullback-Leible divergence between mp(xx-1|Xe.. &o) and q(xx-1 (xe, Xo), so we have
LKI Ex (- (D (DxI((Xx- xx)1
(14)
14

---

Published as a conference paper at ICLR 2024
Some existing work Austin al. (2021) also adds an auxiliary cross entropy loss for training.
Lox E (x2)))0 pol (&n xx)]
(15)
Apart from that, we need the generated path to be connected, so we design loss term punish disconnected path as below
x
CCN -Exo~g(x))
Σ 1=1
Σ
Σ
(o(()) log (0 [xx)]
(16)
E (%6.% )ER
For the i-th vertex, the estimated probability is po xo). If the probability is large for some vertex order i, we hope the model concentrates the probabilities of next (i+1)-th vertex around the neighboring vertices of i/j. i.e. E(og,et*) Po (0)) xx) log Pogro(tt) [x,).
Therefore, our total loss can be defined as
CKL + ALCE + WLON
(17)
C.2 UNCONDITIONAL SAMPLING FOR PATH GENERATION
Our model mng take random sampled vertex sequence as input and get estimated denoised vertices distributions &g, based on which we can sample path. There are two issues we need to handle before utilizing the estimated Xo for path sampling: (i) How specified the path sequence length? (ii) How to maintain the path connectivity? To handle the first issue, we build an extra Gaussian mixture model. This simple model which models the path length distribution. In practice, a Gaussian mixture model with 4 components can model the length distribution well (see Figure X in (App. F.40) To handle the second issue, we adopt beam search. Specifically, the beam search conducted after the reverse process when we have obtained the final estimated distribution xg- Ideally, beam search operates in a breadth-firs first search manner. We start by sampling vertices from the distribution of X (with replacement). Subsequently,
sample (up to neighbors of each vertex from the distribution &1. This process continues, and we always keep (up to) n sequences with the highest probability in queue. Finally, sample from these sequences to get the final path. In practice, however, setting n to suffices for good performance and efficient execution.
After handling the above two issues, the whole unconditional sampling process be summarized as follows (See Algorithm D): (i) Sample from the Gaussian mixture model to determine the path length (denoted as I); (ii) Generate random vertex sequence of length I; (iii Perform the reverse process to denoise the random vertex sequence, obtaining the estimated distribution of &o; and (iv) Apply beam search ensure connectivity.
D PRIOR EVIDENCE MODEL DESIGN
Specifically, first convert the origins and destinations into embeddings via Node2Vec Grover Leskoved (2016), then apply a multi-head self-attention to capture the sequence information. Besides, since the planning process has strong spatial property, we add cooooooorinationns the vertices' properties, based on which we build two extra spatial features: distance feature and direction feature. For distance feature, we calculate the distance from the current vertex the destination based on coordinates. For direction feature, we calculate the cosine of angles between directions towards destination from the current vertex and from its adjacent vertices. Both two features will be fed into a fully connected layer and the output will be concatenated together with the output of self-attention blocks. Another fully connected layer will take all hidden features as input and output the probabilities for the next vertex. We simply adopt a cross- cross-entropy loss to train our model and it works well.
After get the prior evidence h(xlori, dst) soqs,ori, dst), we add the prior evidence into our conditional sampling by Eq.
E PSEUDOCODE FOR PLANNING ALGORITHM
The Pseudocode for our planning algorithm is shown in algorithm
15

---

Published as a conference paper at ICLR 2024
Multi head
Sell-attention
vertex embedking
[ort, pl-1]
Nede2Vec
FC
concal
FC
soflmax
dst
destinatinn embeddligg
veriex probability of h(x (ort, dst)
FC
property
(distance, direction....)
Figure 5: Our attention- based sequence model for planning.
Algorithm 3: Planning
Input:
n,g, sequ, ori, dst
Output: A generated planned path x.
f [[oii] window e-
ådr &- window
while x| MAX LEN
LEN do
lteg sego (ori, dst, x)
// get evidence priori by sequence model
idæ = window then
X1 q(xx (x) by Eq.8
// diffuse prefix sequence // random sequence with window size concat prefix and random sampled sequence Pun + mno(xxx (x'r, - :] // get probabilities for later use
@piinoo (1,
x'r + xr|/w
11
idæ +
12
window + window end
// increase window size exponentially
14
Pnezt t- heeg ② Pnn [idx] idæ idx +1
15
16 Enezt ~ Pnext t x.append(nnen)
11 sample next vertex
17
if Enezt = dst then break;
end
20
return X
F EXTENDED EXPERIMENTS
F.1 IMPLEMENTATION DETAIL
Dataset. The raw datasets contains GPS trajectories from two cities, namely city A and B. We fetch the road network data from open street map 3| The road network is undirected graph. Then apply a map matching algorithm Meert & Verbeke (2018) to bind the gps points of trajectories to the road network. Hence we convert the gps-trajectories into path data on graph. For city A/B, the graph of road network has 2717/219 vertices. The number of paths are 118, 535/ 89, 339 with average length of 26.76 76. 28.61.
Parameter Setting. For diffusion process, we set 7' to 100 and the 8 linearly increase from 0.0001 10. As for the training process, we choose the batch size as 16 and set the learning rate to 0.005. As for the Gaussian mixture model, we set components. We train our model for 20
16

---

Published as a conference paper at ICLR 2024
epochs Nvidia GeForee RTX 3090 with 24 GiB memory. Our source code can be found at ht ctwp/ sdycodes http:///aayccaccaaaaaaaaaaaaaaaa
Evaluation Metries, NLL is defined as
X
NLL(x, 0) 0)= =-
Σ
log po (u 011,.., 03)
(18)
KLEV is calculated as below
KLEV(P, P)) Dr [Dxx(freeeii (e.e 0i4
(h,, 0441)) (19)
where the ['ee(()) calculates the visiting frequencies of all edges.
F.2 PLANNING EXPERIMENT DETAIL.
Table 4 provides detailed information about performances. The unit of DTW is kilometer, which indicates the difference between planed paths and ground truth path. Smaller value indicates the planed path is more close to the ground truth path. For example, 2.434 indicates that the algorithm planned paths averagely have a difference to the ground truth of 2.434 kilometers. Our method can outperform the strongest baseline (i.e., Navi) by 480 and 366 meters City A and B respectively, indicating a perceivable difference in real road network.
Besides average performance, also concern about the robustness of performances, i.e., how steadily can we beat baselines? Table provides the proportion cases in which an algorithm can outperform Dijkstra's algorithm baseline. For instance, in city A, our GDP can beat Dijkstra's algorithm in 86.6% and 86.8% out of all test cases in terms of DTW and LCS, respectively. It achieves the best among all other methods.
Table 4: Evaluations for path planning. Less DTW or larger LCS means better performance.
Methods
City
Metrics
DA
NMLR
KS
Navi
GDP (Ours)
DTW
2.434
9.109
2.405
2.164
1.683
A
LCS
9.254
9.772
11.485
13.505
16.730
DTW
2.883
10.114
2.936
2.792
2.426
B
LCS
9.233
10.066
12.207
14.390
16.856
Table 5: Proportion of test cases that can beat Dijkstra's baselines.
Methods
City
Metrics
DA
NMLR
KS
Navi
GDP (Ours)
DTW
13.3
82.3
81.3
86.6
LCS
70.3
83.8
79.0
86.8
DTW
11.1
76.9
78.7
81.3
LCS
72.3
84.2
83.7
87.3
F.3 ILLEGAL CASES DISCUSSION
Hit ratio discussion. adopt the hit ratio (HR), which is the ratio between planned path hitting the destination to all paths. Intuitively the hit ratio is affected by the distance, paths evenly into three groups based on their lengths and calculate the HR. Also, though our OD pairs is sampled from test data, also shuffled the OD pairs to add the difficulty of planning. The HR comparison is illustrated in Figure)) 7 We found that for existing OD pairs from test data, the HR remains steadily around 98.6% / 99.0% city A/B, respectively. As for shuffled OD pairs, the HR slightly drop to 94.2% 96.8%. This results indicates that our GDP ensures to reach the destination high success rate.
split the sampled
Disconnection and loop discussion. When we sample vertices directly based on the estimated distribution without help of post process like beam search. The model would generate illegal cases,
17

---

Published as a conference paper at ICLR 2024
like disconnected vertices loops. We switch off post process and calculate the proportion of illegal cases (see Table (). Specifically, we randomly sampled 1000 OD pairs to plan paths. For each planned path, calculate the ratio between number of disconnected vertices loops the length of planed paths. It can he shown that illegal cases happens very rarely (no more than 5% averagely in each path), which indicates that our model captures the graph structure.
Table 6: Proportion of illegal cases (mean = std). Disconnection
Dataset
Loop 0.0123 0.0788
City City B
0.0479 = 0.0294 0.0473 = 0.0309 0.0203 + 0.107
F.4 COMPARISON BETWEEN GENERATED AND REAL PATHI
The generated and real paths on map are illustrated in figure 6 Some main roads are covered by more paths (red lines more wide), which intuitively indicates generated paths follows real paths distributions.
(a) Real paths
(b) Generated paths
(c) Real paths
(d) Generated paths
Figure 6: Comparisons of real and generated paths on city A (Figure 6(a) and Figure 6(b) and B
(Figure ((c) and Figure b(d).
Next we show our path lengths distributions to show the effectiveness of our Gaussian mixture model for path lengths. The Jensen-Shannon divergences of path length distributions are 0.0173, 0.0238 on City A and B, respectively. The histogram are illustrated in Figure can be shown that the length distribution of generated paths are very close to that of real paths, which validates the effectiveness of our Gaussian mixture model.
18
shuf
88
Stuttel
0.64
genernns
0:03
naal generited
0.02
5.2
20
42
20
(a)
(b)
City A
(b) City B
Figure 7: Hit Ratio (HR) of Planned paths on city Figure 8: Histograms of path lengths of City A and A (left) and B (right)
B.
F.5 SCALABILITY AND EFFICIENCY
We random sample 1000 OD pairs from City A and B for execution efficiency validation with batch size 200 (see Table 7b. It not surprising that Dijkstra's Algorithm runs fastest. Other baselines such NMLR and KS also run fast since they have relatively simple neural network structure. Our method run faster than the strong baseline Navi. Considering Navi can support real-world application, the delay of our method is also acceptable.
18

---

Published as a conference paper at ICLR 2024
Table 7: Execution time comparison in seconds (mean + std).
Dataset
DA
NMLR
KS
Navi
GDP (Ours)
City
0.0016 + 0.003
0.024 0.003
0.0187 0.0166
0.347 0.205
0.149 + 0.550
City B
0.0015 + 0.002
0.025 + 0.003
0.0169 + 0.0176
0.339 0.133
0.112 = 0.315
Next we discuss the scalability. In an Nvidia RTX 3090 with 24 GB memory. our method can support batch up to 400 (See figure We test time and memory consumption under different batch sizes from 10 to 400 on City B. As batch size increases, the memory consumption increases linearly, while execution time for each planning task correspondingly reduces from 0.316 to 0.115 seconds.
20267
20000
p:31 Memory
Execution Time
18000
0.30
66511
16000
Execution Timels
Memory/MIB
0.25
14000
0.215
22893
12000
0.20
20671
10000
9937
0.160
8487
0.15
8000
6000
9673
8.9.60.115
0.114
0.115
100
200
300
400
Batch Size
Figure 9: Memory and time consumption
19


Reviews:
[{"review_id": "ZjayhBkgng", "reviewer": "Reviewer_YKA1", "summary": "The authors consider the problem of sampling paths on a graph. Their approach makes use of recent developments on argmax flows, that allow for the definition of diffusion with categorical variables. \nTheir insight is that they can use a heat equation to model the transition probability matrix of a specific graph, with the heat transfer defined by the adjacency, balanced by the degree.\nThey then use this to define their forward diffusion process. They use a sequence of conditionally independent nodes to model a path, and use post processing to ensure connectivity. They demonstrate the value of their approach on a series of datasets, outperforming baselines.", "questions": "Overall I enjoyed reading this paper. I think the core of the method is good, interesting, and useful. I do have some questions:\n\n - In Table 3, the authors present an ablation as \"trivial uniform diffusion\". Do the authors mean the \"generic categorical diffusion\" with Q = $\\alpha_t I + \\beta_t 1 1^T / V$? If this is the case, the authors should make that more clear so that readers may enjoy the significant improvement their work brings. If this is not the case, and the authors mean something else, they should run another ablation using \"generic categorical diffusion\" as a baseline, since that seems like the relevant benchmark to beat.\n - Can the authors elaborate on the beam search aspect, and how often a sampled path is actually invalid (i.e., disconnected, or with loops, etc), and what heuristics are used to fix those sampled paths?\n - Can the authors discuss their Guassian mixture model for path lengths in some more detail? While some metrics are provided in the appendix, it is not clear what information this model takes, if any. It seems to me that path length is highly dependent on origin and destination, so I assume their mixture model takes these as input. Can the authors elaborate exactly what the structure of this model is?\n - What is the scaling of the algorithm? Especially compared to Dijkstra? Both in terms of path length, and number of graph vertices.\n - Can the authors elaborate on how they generalize to paths without learning a joint distribution across time? Sampling nodes independently certainly would not yield a sensible path. I could imagine this would work if the reverse process was conditionally independent (i.e. $x^i_{t-1} | x_t$, the latter $x_t$ being _all_ nodes instead of $x_t^i$), but eqn 9 does not actually seem to suggest that. The text touches on this (end of paragraph 3 in 4.3, \"masking $\\hat{x_0}$\"), but to me this statement is quite uninformative, and seems like a very essential point of the paper.\n - Does it generalize to different graphs? i.e. do you need to retrain for each city?\n\nMinor points:\nThe text is generally well written, but it seems like a few paragraphs were missed during the proof reading stage.\nA non-exhaustive list:\n - first paragraph of 4.2 \n - first paragraph of sec 5\n - App. D\n - 6.2 paragraph 2\n - typo in Fig 2. \"Pais\", it is also confusing for 3rd panel to say \"Real\", since the text says these were generated using Navi", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Algorithms on graphs are very useful in practical applications\n - The heat conduction approach is elegant, and I think quite clever", "weaknesses": "- The work seems to cut some corners when it comes to sampling connected paths, post-hoc processing is required\n - The path length seems like an integral part of the problem, but is only discussed very briefly in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h8rBCkDVCz", "reviewer": "Reviewer_nmfg", "summary": "The paper tackled the problem of building a novel conditioned sampling method to mimic user historical paths on a graph. To implement the sampling process in the manner of diffusion models, the authors reviewed requirements based on previous work. They formulated the forward and backward process following the heat conduction on the graph. Experimental comparisons with the proposed method and existing methods show the promising performance of the diffusion-based method for the task.", "questions": "- Do we have any discussions on the parameters of diffusion processes: examples are the length of diffusion time (i.e., t=100 in Fig. 3 in city B).\n- Related to the 2nd point of the weakness above, I'm curious about the relation between the diffusion models among those for continuous spaces and those for discrete spaces (i.e., this paper). I found that DiffTraj in NeurIPS'23 tacked a similar problem, but they seem to focus on the continuous space. Therefore, please clarify the difficulty of discrete spaces or the similarity between the two models. (Of course, if such a paper overlaps with the submission of ICLR, you can refer to other papers used as baselines of DiffTraj). To clarify the difference, your contributions are expected to be clarified and explained well.\n- I cannot completely follow the discussion of introducing U-net for the purpose of $\\mathbf{x}_0$: Could you give some additional explanations? (In experiments, for example, they are static (OD-pairs seem to be known), but some probabilistic characterization as a distribution p(x0) is required for the diffusion process; is this right? In Line 2 of Alg1, $\\mathbf{x}_0$ is sampled from $p(\\mathbf{x}_0)$, but I'm confused that $\\mathbf{x}_0$ is already known?)\n- As the dataset contains multiple OD pairs, I’m curious about the std. of the metrics (DTW, LCS): Does the GDP show good performance for almost all OD pairs? Are there any specifically difficult trajectories according to their conditions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear explanations of the motivation and background concept (of conditioned samples through diffusion models) for the targeting task (i.e., end-to-end path planning).\n- Mathematically solid contribution through the heat conduction on graphs to build diffusion models.\n- Good experimental performance for the end-to-end path planning.", "weaknesses": "- Following the existing literature (e.g., Austin et al. 2021 and Yi et al. 2023), the novelty of the contribution is less explained (the background idea and reasons to follow the heat conduction on graphs, although the performance is good).\n- Possibly, the discussion between the continuous space (i.e., latitude-longitude vectors) and discrete space (i.e., the sequence of nodes on a graph) is not included in the paper (e.g., NeurIPS'23 DiffTraj.); the difficulty of discrete spaces or similarity between the two models are better to be explained.\n- Many details are included in the appendix, making the main paper hard to read and follow the details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hWmfhciifj", "reviewer": "Reviewer_j9CR", "summary": "This work propose a GDP, a diffusion model on graphs, which is able to conduct path planning in an end-to-end manner. The experiments are conducted on two real city datasets and compared against four baseline planners, showing that GDP is able to generate paths very close to the groundtruth.", "questions": "1. How do you deal with the unsuccessful planning tasks? \n2. Have the authors compared the latency of GDP with other models, because latency is also crucial in giving real-time path solution, and I am concerned that diffusion model can be slow due to many iterations of run.\n3. What is the motivation for unconditional path generation? Is it for preparing a high-quality roadmap for the following specific tasks?\n4. How do you compare your method/contributions with Motion Planning Diffusion [R]?\n\nI hope the authors can address my questions and I will be glad to adjust the score afterwards. \n\n[R] Carvalho, Joao, et al. \"Motion planning diffusion: Learning and planning of robot motions with diffusion models.\" arXiv preprint arXiv:2308.01557 (2023).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The technical part is solid and using diffusion model to address the path planning is interesting.\n2. The performance is evaluated on big and real city datasets and promising results are shown.", "weaknesses": "I can not accurately tell the weakness of this paper. Please see my questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ccl3IMdJRq", "reviewer": "Reviewer_GtR8", "summary": "This paper proposes a diffusion-based model for end-to-end data-driven path planning, called GDP. GDP models path planning as a conditional sampling task. Its objective is to determine the probability distribution of paths given an origin and destination. To solve this task, GDP uses a diffusion-based architecture.\n\nThe authors evaluated the GDP model using two real datasets, City A and City B. They compared against traditional optimization methods as their baselines, including Dijkstra's algorithm, NMLR, Key Segment, and Navigation API from Amap. The result shows that the paths generated by GDP are closer to the ground-truth paths than those baselines.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper proposes a sound diffusion-based model for path planning. The proposed model achieves better performance than the traditional methods on public datasets.\n\n* The paper is very well-written. The structure is clear, and the evaluation is thorough.", "weaknesses": "* The improvement from the GDP model over the Navi baseline is relatively small.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YRDroB4l9K", "reviewer": "Reviewer_opqU", "summary": "This paper introduces a new technique for path planning, specifically path generation, on graphs such as road networks. \n\nThe key innovation is a diffusion model over a graph, capable of learning a probability distribution of paths from a set of expert demonstrations. Initially, a diffusion model for vertices is defined using the graph Laplacian, which is then extended to create a diffusion model for paths. Once learned, the model can be used for path generation through conditional sampling given a pair of origin and destination vertices. A significant advantage of this approach is its capacity to learn expert paths without assuming that they minimize linearly accumulative costs, a departure from standard search-based path planning.\n\nThe proposed method is evaluated on real-world road network datasets and is shown to outperform several existing methods.", "questions": "- Does the dataset contain a sufficient number of paths that don't follow the linearly accumulative cost assumption? At least the standard deviation or confidence intervals should also be reported in each table, but I wonder if the proposed method's strength could have been demonstrated more systematically using synthetic data that simulate paths that existing methods cannot plan or imitate from demonstrations? Such controlled experiments can be as important as real-world data evaluations.\n- How does the proposed method compare to other baselines in terms of computational costs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "**Originality**: Although previous work has leveraged diffusion models for path or motion planning, the use of diffusion models on a graph for path generation tasks seems novel. The ability of the proposed model to generate paths without assuming linearly accumulative costs is intriguing.\n\n**Quality**: The overall quality of the work is high. The proposed method is well-designed and technically sound.\n\n**Clarity**: The paper is well-written, with clear statements of the work's motivation and contribution.\n\n**Significance**: The significance of the proposed method is evaluated on a real road network dataset, a strong point of this work, although I have some concerns about the dataset itself, as shown below.", "weaknesses": "While the proposed method's ability to bypass the linearly accumulative cost assumption is appealing, it's unclear if the path planning tasks for the collected datasets used in the experiment require such assumptions. In other words, I'm not sure if the dataset is fully suited to demonstrate the proposed method's significance.\n\nIn fact, the performance improvements over Dijkstra search are not very significant in terms of the DTW metric. With only average scores reported, it's unclear whether the proposed method demonstrates overall small improvements or if there are a few samples in the dataset where baselines completely failed to work. Similarly, the performance difference between the proposed method and CSSRNN is relatively small in Table 3. Does this suggest that path planning on the new dataset can be mostly solved by existing approaches that assume linearly accumulative costs?\n\nAnother concern is the computational cost. Classical path planners like Dijkstra are appealing because they can run quickly even on CPUs. In practical situations, people use path planning (e.g., route search on a map app) on mobile devices that don't always have sufficient GPU resources. It's not clear how much computation resources are required by the proposed method and other baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)