# Real-time Photorealistic Dynamic Scene Representation and Rendering with 4D
Gaussian Splatting

Zeyu Yang1, Hongye Yang1, Zijie Pan1, Xiatian Zhu2, Li Zhang1
1Fudan University 2University of Surrey
https://github.com/fudan-zvg/4d-gaussian-splatting
Li Zhang<EMAIL_ADDRESS>is the corresponding author with School of
Data Science, Fudan University.

###### Abstract

Reconstructing dynamic 3D scenes from 2D images and generating diverse views
over time is challenging due to scene complexity and temporal dynamics.
Despite advancements in neural implicit models, limitations persist: (i)
Inadequate Scene Structure: Existing methods struggle to reveal the spatial
and temporal structure of dynamic scenes from directly learning the complex 6D
plenoptic function. (ii) Scaling Deformation Modeling: Explicitly modeling
scene element deformation becomes impractical for complex dynamics. To address
these issues, we consider the spacetime as an entirety and propose to
approximate the underlying spatio-temporal 4D volume of a dynamic scene by
optimizing a collection of 4D primitives, with explicit geometry and
appearance modeling. Learning to optimize the 4D primitives enables us to
synthesize novel views at any desired time with our tailored rendering
routine. Our model is conceptually simple, consisting of a 4D Gaussian
parameterized by anisotropic ellipses that can rotate arbitrarily in space and
time, as well as view-dependent and time-evolved appearance represented by the
coefficient of 4D spherindrical harmonics. This approach offers simplicity,
flexibility for variable-length video and end-to-end training, and efficient
real-time rendering, making it suitable for capturing complex dynamic scene
motions. Experiments across various benchmarks, including monocular and multi-
view scenarios, demonstrate our 4DGS model’s superior visual quality and
efficiency.

##  1 Introduction

Modeling dynamic scenes from 2D images and rendering photorealistic novel
views in real-time is crucial in computer vision and graphics. This task has
been receiving increasing attention from both industry and academia because of
its potential value in a wide range of AR/VR applications. Recent
breakthroughs, such as NeRF (Mildenhall et al., 2020), have achieved
photorealistic static scene rendering (Barron et al., 2021; Verbin et al.,
2022). However, adapting these techniques to dynamic scenes is challenging due
to several factors. Object motion complicates reconstruction, and temporal
scene dynamics add significant complexity. Moreover, real-world applications
often capture dynamic scenes as monocular videos, making it impractical to
train separate static scene representations for each frame and then combine
them into a dynamic scene model. The central challenge is preserving intrinsic
correlations and sharing relevant information across different time steps
while minimizing interference between unrelated spacetime locations.

Figure 1:  Schematic illustration of the proposed 4DGS. This diagram
illustrates why our 4D primitive is naturally suitable for representing
dynamic scenes. Within our framework, the transition from 4D Gaussian to 2D
Planar Gaussian can conceptually correspond to the process where a dynamic
scene transforms into a 2D image through a temporal orthogonal projection and
a spatial perspective projection.

Dynamic novel view synthesis methods can be categorized into two groups. The
first group employs structures such as MLPs (Li et al., 2022b) or grids (Wang
et al., 2023), including their low-rank decompositions (Fridovich-Keil et al.,
2023; Cao & Johnson, 2023; Attal et al., 2023), to learn a 6D plenoptic
function without explicitly modeling scene motion. The effectiveness of these
methods in capturing correlations across different spatial-temporal locations
depends on the inherent characteristics of the chosen data structure. However,
they lack flexibility in adapting to the underlying scene motion.
Consequently, these methods either suffer from parameter sharing across
spatial-temporal locations, leading to potential interference, or they operate
too independently, struggling to harness the inherent correlations resulting
from object motion.

In contrast, another group suggests that scene dynamics are induced by the
motion or deformation of a consistent underlying representation (Pumarola et
al., 2020; Song et al., 2023; Abou-Chakra et al., 2022; Luiten et al., 2023).
These methods explicitly learn scene motion, providing the potential for
better utilization of correlations across space and time. Nevertheless, they
exhibit reduced flexibility and scalability in complex real-world scenes
compared to the first group of methods

To overcome these limitations, this study reformulates the task by
approximating a scene’s underlying spatio-temporal 4D volume by a set of 4D
Gaussians. Notably, 4D rotations enable the Gaussian to fit the 4D manifold
and capture scene intrinsic motion. Furthermore, we introduce Spherindrical
Harmonics as a generalization of Spherical Harmonics for dynamic scenes to
model time evolution of appearance in dynamic scenes. This approach marks the
first-ever model supporting end-to-end training and real-time rendering of
high-resolution, photorealistic novel views in complex dynamic scenes with
volumetric effects and varying lighting conditions. Additionally, our proposed
representation is interpretable, highly scalable, and adaptable in both
spatial and temporal dimensions.

Our contributions are as follows: (i) We propose coherent integrated modeling
of the space and time dimensions for dynamic scenes by formulating unbiased 4D
Gaussian primitives along with a dedicated splatting-based rendering pipeline.
(ii) The 4D Spherindrical Harmonics of our method is useful and interpretable
to model the time evolution of view-dependent color in dynamic scenes. (iii)
Extensive experiments on various datasets, including synthetic and real,
monocular, and multi-view, demonstrate that our method outperforms all
previous methods in terms of visual quality and efficiency. Notably, our
method can produce photo-realistic, high-resolution video at speeds far beyond
real-time.

##  2 Related work

##### Novel view synthesis for static scenes

In recent years, the field of novel view synthesis has received widespread
attention. Mildenhall et al. (2020) is the pioneering work that initiated this
trend, suggesting using an MLP to learn the radiance field and employing
volumetric rendering to synthesize images for any viewpoint. However, vanilla
NeRF requires querying the MLP for hundreds of points each ray, significantly
constraining its training and rendering speed. Some subsequent works have
attempted to improve the speed, such as employing well-tailored data
structures (Chen et al., 2022; Sun et al., 2022; Hu et al., 2022; Chen et al.,
2023), discarding large MLP (Fridovich-Keil et al., 2022), or adopting hash
encodings (Müller et al., 2022). Other works (Zhang et al., 2020; Verbin et
al., 2022; Barron et al., 2021; 2022; 2023) aim to enhance rendering quality
by addressing existing issues in the vanilla NeRF, such as aliasing and
reflection. Yet, these methods remain confined to the nuances of
differentiable volume rendering. In contrast, Kerbl et al. (2023) introduced
3D Gaussian Splatting, a novel framework that possesses the advantages of
volumetric rendering approaches—offering high-fidelity view synthesis for
complex scenes, while also benefiting from the merits of rasterization
approaches, enabling real-time rendering for large-scale scenes. Inspired by
this work, in this paper, we further demonstrate that Gaussian primitives are
also an excellent representation of dynamic scenes.

##### Novel view synthesis for dynamic scenes

Synthesizing novel views of a dynamic scene at a desired time from a series of
2D captures is a more challenging task. The intricacy lies in capturing the
intrinsic correlation across different timesteps. This task cannot be
trivially regarded as an accumulation of novel view synthesis for the static
scene of each frame, as such an approach is prohibitively expensive, scales
poorly for synthesizing new views at a time beyond training data, and
inevitably fails when observations at a single frame are insufficient to
reconstruct the entire scene. Inspired by the success of NeRF, one research
line attempts to learn a 6D plenoptic function represented by a well-tailored
implicit or explicit structure without direct modeling for the underlying
motion to address this challenge (Li et al., 2022b; Fridovich-Keil et al.,
2023; Cao & Johnson, 2023; Wang et al., 2023; Attal et al., 2023). However,
these methods struggle with the coupling between parameters. An alternative
approach explicitly models continuous motion or deformation, presuming the
dynamics of the scene result from the movement or deformation of particular
static structures, like particle or canonical fields (Pumarola et al., 2020;
Song et al., 2023; Abou-Chakra et al., 2022; Luiten et al., 2023). Among them,
point-based approaches have consistently been deemed promising. Recently,
drawing inspiration from 3D Gaussian Splatting, Luiten et al. (2023)
represented dynamic scenes with a set of simplified 3D Gaussians shared across
timesteps and optimized them frame-by-frame. With the physically-based priors
encoded in its regularizations, dynamic 3D Gaussians can be optimized to
represent dynamic scenes faithfully given its multi-view captures, and achieve
long-term tracking by exploiting dense correspondences across timesteps.

##### Dynamic 3D Gaussians

Our method is also inspired by Kerbl et al. (2023). Critically, going beyond
3D Gaussians, we formulate a scene primitive, termed 4D Gaussians, to
represent the dynamic scenes. This is more than the baseline extension that
assumes dynamic scenes are generated by a fixed set of 3D Gaussians. This
design allows us to end-to-end optimize the model, instead of otherwise the
inefficient and less effective frame-by-frame training, in addition to the
merit of eliminating the need for any prior regularization. Consequently, our
approach is able to flexibly deal with the new object entering the scene,
which is difficult to handle by the dynamic 3D Gaussians. Moreover, while
dynamic 3D Gaussians omit view-dependent colors to avoid the interference for
tracking relationships, this compromises their ability to model non-Lambertian
effects. In contrast, our method not only allows the appearance of Gaussian
representations to vary with the view direction but also permits their view-
dependent colors to evolve over time. Thus, our approach is more general and
versatile to handle complex scenes and challenging monocular videos in the
real world applications.

##  3 Method

Figure 2:  Rendering pipeline of our 4DGS. Given a time $t$ and view
$\mathcal{I}$, each 4D Gaussian is first decomposed into a conditional 3D
Gaussian and a marginal 1D Gaussian. Subsequently, the conditional 3D Gaussian
is projected to a 2D splat. Finally, we integrate the planar conditional
Gaussian, 1D marginal Gaussian, and time-evolving view-dependent color to
render the view $\mathcal{I}$.

We propose a novel photorealistic scene representation tailored for modeling
general dynamic scenes. In this section, we will delineate each component of
it and the corresponding optimization process. In Section 3.1, we will begin
by reviewing 3D Gaussian Splatting (Kerbl et al., 2023) from which our method
inspired. In Section 3.2, we detail how our 4D Gaussian represents dynamic
scenes and synthesizes novel views. An overview is shown in Figure 2. The
optimization framework will be introduced in Section 3.3.

###  3.1 Preliminary: 3D Gaussian slatting

3D Gaussian Splatting (Kerbl et al., 2023) employs anisotropic Gaussian to
represent static 3D scenes. Facilitated by a well-tailored GPU-friendly
rasterizer, this representation enables real-time synthesis of high-fidelity
novel views.

##### Representation of 3D Gaussians

In 3D Gaussian Splatting, a scene is represented as a cloud of 3D Gaussians.
Each Gaussian has a theoretically infinite scope and its influence on a given
spatial position $x\in\mathbb{R}^{3}$ defined by an unnormalized Gaussian
function:

$p(x|\mu,\Sigma)=e^{-\frac{1}{2}\left(x-\mu\right)^{T}\Sigma^{-1}\left(x-\mu\right)},$
(1)

where $\mu\in\mathbb{R}^{3}$ is its mean vector, and
$\Sigma\in\mathbb{R}^{3\times 3}$ is an anisotropic covariance matrix. In the
Appendix, we will show that it holds desired properties of normalized Gaussian
probability density function critical for our methodology, i.e., the
unnormalized Gaussian function of a multivariate Gaussian can be factorized as
the production of the unnormalized Gaussian functions of its condition and
margin distributions. Hence, for brevity and without causing misconceptions,
we do not specifically distinguish between equation 1 and its normalized
version in subsequent sections.

In Kerbl et al. (2023), the mean vector $\mu$ of a 3D Gaussian is
parameterized as $\mu=(\mu_{x},\mu_{y},\mu_{z})$, and the covariance matrix
$\Sigma$ is factorized into a scaling matrix $S$ and a rotation matrix $R$ as
$\Sigma=RSS^{T}R^{T}$. Here $S$ is summarized by its diagonal elements
$S=\mathrm{diag}(s_{x},s_{y},s_{z})$, whilst $R$ is constructed from a unit
quaternion $q$. Moreover, a 3D Gaussian also includes a set of coefficients of
spherical harmonics (SH) for representing view-dependent color, along with an
opacity $\alpha$.

All of the above parameters can be optimized under the supervision of the
rendering loss. During the optimization process, 3D Gaussian Splatting also
periodically performs densification and pruning on the collection of Gaussians
to further improve the geometry and the rendering quality.

##### Differentiable rasterization via Gaussian splatting

In rendering, given a pixel $(u,v)$ in view $\mathcal{I}$ with extrinsic
matrix $E$ and intrinsic matrix $K$, its color $\mathcal{I}(u,v)$ can be
computed by blending visible 3D Gaussians that have been sorted according to
their depth, as described below:

$\mathcal{I}(u,v)=\sum^{N}_{i=1}p_{i}(u,v;\mu_{i}^{2d},\Sigma_{i}^{2d})\alpha_{i}c_{i}(d_{i})\prod^{i-1}_{j=1}(1-p_{i}(u,v;\mu_{i}^{2d},\Sigma_{i}^{2d})\alpha_{j}),$
(2)

where $c_{i}$ denotes the color of the $i$-th visible Gaussian from the
viewing direction $d_{i}$, $\alpha_{i}$ represents its opacity, and
$p_{i}(u,v)$ is the probability density of the $i$-th Gaussian at pixel
$(u,v)$.

To compute $p_{i}(u,v)$ in the image space, we linearize the perspective
transformation as in Zwicker et al. (2002); Kerbl et al. (2023). Then, the
projected 3D Gaussian can be approximated by a 2D Gaussian. The mean of the
derived 2D Gaussian is obtained as:

$\mu_{i}^{2d}=\mathrm{Proj}\left(\mu_{i}|E,K\right)_{1:2},$ (3)

where $\mathrm{Proj}\left(\cdot|E,K\right)$ denotes the transformation from
the world space to the image space given the intrinsic $K$ and extrinsic $E$.
The covariance matrix is given by

$\Sigma_{i}^{2d}=(JE\Sigma E^{T}J^{T})_{1:2,1:2},$ (4)

where $J$ is the Jacobian matrix of the perspective projection.

###  3.2 4D Gaussian for dynamic scenes

##### Problem formulation and 4D Gaussian splatting

To extend the formulation of Kerbl et al. (2023) for modeling dynamic scenes,
reformulation is necessary. In dynamic scenes, a pixel under view
$\mathcal{I}$ can no longer be indexed solely by a pair of spatial coordinates
$(u,v)$ in the image plane; But an additional timestamp $t$ comes into play
and intervenes. Formally this is formulated by extending equation 2 as:

$\mathcal{I}(u,v,t)=\sum^{N}_{i=1}p_{i}(u,v,t)\alpha_{i}c_{i}(d)\prod^{i-1}_{j=1}(1-p_{j}(u,v,t)\alpha_{j}).$
(5)

Note that $p_{i}(u,v,t)$ can be further factorized as a product of a
conditional probability $p_{i}(u,v|t)$ and a marginal probability $p_{i}(t)$
at time $t$, yielding:

$\mathcal{I}(u,v,t)=\sum^{N}_{i=1}p_{i}(t)p_{i}(u,v|t)\alpha_{i}c_{i}(d)\prod^{i-1}_{j=1}(1-p_{j}(t)p_{j}(u,v|t)\alpha_{j}).$
(6)

Let the underlying $p_{i}(x,y,z,t)$ be a 4D Gaussian. As the conditional
distribution $p(x,y,z|t)$ is also a 3D Gaussian, we can similarly derive
$p(u,v|t)$ as a planar Gaussian whose mean and covariance matrix are
parameterized by equation 3 and equation 4, respectively.

Subsequently, it comes to the question of how to represent a 4D Gaussian. A
natural solution is that we adopt a distinct perspective for space and time,
that is, considering $(x,y,z)$ and $t$ are independent of each other, i.e.,
$p_{i}(x,y,z|t)=p_{i}(x,y,z)$. Under this assumption, equation 6 can be
implemented by adding an extra 1D Gaussian $p_{i}(t)$ into the original 3D
Gaussians (Kerbl et al., 2023). This design can be viewed as imbuing a 3D
Gaussian with temporal extension, or weighting down its opacity when the
rendering timestep is away from the expectation of $p_{i}(t)$. However, we
show later on that this approach can achieve a reasonable fitting of 4D
manifold but is difficult to capture the underlying motion of the scene (see
“No-4DRot” in Table 3).

##### Representation of 4D Gaussian

To address the mentioned challenge, we suggest to treat time and space
dimensions equally by formulating a coherent integrated 4D Gaussian model.
Similar to Kerbl et al. (2023), we parameterize its covariance matrix $\Sigma$
as the configuration of a 4D ellipsoid for easing model optimization:

$\Sigma=RSS^{T}R^{T},$ (7)

where $S$ is a scaling matrix and $R$ is a 4D rotation matrix. Since $S$ is
diagonal, it can be completely inscribed by its diagonal elements as
$S=\mathrm{diag}(s_{x},s_{y},s_{z},s_{t})$. On the other hand, a rotation in
4D Euclidean space can be decomposed into a pair of isotropic rotations, each
of which can be represented by a quaternion.

Specifically, given $q_{l}=(a,b,c,d)$ and $q_{r}=(p,q,r,s)$ denoting the left
and right isotropic rotations respectively, $R$ can be constructed by:

$R=L(q_{l})R(q_{r})=\left(\begin{array}[]{rrrr}a&-b&-c&-d\\\ b&a&-d&c\\\
c&d&a&-b\\\ d&-c&b&a\end{array}\right)\left(\begin{array}[]{rrrr}p&-q&-r&-s\\\
q&p&s&-r\\\ r&-s&p&q\\\ s&r&-q&p\end{array}\right).$ (8)

The mean of a 4D Gaussian can be represented by four scalars as
$\mu=(\mu_{x},\mu_{y},\mu_{z},\mu_{t})$. Thus far we arrive at a complete
representation of the general 4D Gaussian.

Subsequently, the conditional 3D Gaussian can be derived from the properties
of the multivariate Gaussian with:

$\displaystyle\mu_{xyz|t}$
$\displaystyle=\mu_{1:3}+\Sigma_{1:3,4}\Sigma_{4,4}^{-1}(t-\mu_{t}),$ (9)
$\displaystyle\Sigma_{xyz|t}$
$\displaystyle=\Sigma_{1:3,1:3}-\Sigma_{1:3,4}\Sigma_{4,4}^{-1}\Sigma_{4,1:3}$

Since $p_{i}(x,y,z|t)$ is a 3D Gaussian, $p_{i}(u,v|t)$ in equation 6 can be
derived in the same way as in equation 3 and equation 4. Moreover, the
marginal $p_{i}(t)$ is also a Gaussian in one-dimension:

$p(t)=\mathcal{N}\left(t;\mu_{4},\Sigma_{4,4}\right)$ (10)

So far we have a comprehensive implementation of equation 6. Subsequently, we
can adapt the highly efficient tile-based rasterizer proposed in Kerbl et al.
(2023) to approximate this process, through considering the marginal
distribution $p_{i}(t)$ when accumulating colors and opacities.

##### 4D spherindrical harmonics

The view-dependent color $c_{i}(d)$ in equation 6 is represented by a series
of SH coefficients in the original 3D Gaussian Splatting (Kerbl et al., 2023).
To more faithfully model the dynamic scenes of real world, we must enable
appearance variation with varying viewpoints and also their colors to evolve
over time.

Leveraging the flexibility of our framework, a straightforward solution is to
directly use different Gaussians to represent the same point at different
times. However, this approach leads to duplicated and redundant representation
of identical objects, making it challenging to optimize. Instead we choose to
exploit 4D extension of the spherical harmonics (SH) that directly represents
the time evolution of appearance of each Gaussian. The color in equation 6
could then be manipulated with $c_{i}(d,t)$, where $d=(\theta,\phi)$ is the
normalized view direction under spherical coordinates and $t$ is the time
difference between the expectation of the given Gaussian and the viewpoint.

Inspired by studies on head-related transfer function, we propose to represent
$c_{i}(d,t)$ as the combination of a series of 4D spherindrical harmonics
(4DSH) which are constructed by merging SH with different 1D-basis functions.
For computational convenience, we use the Fourier series as the adopted
1D-basis functions. Consequently, 4DSH can be expressed as:

$Z_{nl}^{m}(t,\theta,\phi)=\cos\left(\frac{2\pi
n}{T}t\right)Y_{l}^{m}(\theta,\phi),$ (11)

where $Y^{m}_{l}$ is the 3D spherical harmonics. The index $l\geq 0$ denotes
its degree, and $m$ is the order satisfying $-l\leq m\leq l$. The index $n$ is
the order of the Fourier series. The 4D spherindrical harmonics form an
orthonormal basis in the spherindrical coordinate system.

###  3.3 Training

Following 3D Gaussian Splatting (Kerbl et al., 2023), we conduct interleaved
optimization and density control during training. It is worth highlighting
that our optimization process is entirely end-to-end, capable of processing
entire videos, with the ability to sample at any time and view, as opposed to
the traditional frame-by-frame or multi-stage training approaches.

##### Optimization

In optimization, we only use the rendering loss as supervision. In most
scenes, combining the representation introduced above with the default
training schedule as in Kerbl et al. (2023) is sufficient to yield
satisfactory results. However, in some scenes with more dramatic changes, we
observe issues such as temporal flickering and jitter. We consider this may
arise from suboptimal sampling techniques. Rather than adopting the prior
regularization, we discover that straightforward batch sampling in time turns
out to be superior, resulting in more seamless and visually pleasing
appearance of dynamic visual contents.

##### Densification in spacetime

In terms of density control, simply considering the average magnitude of view
space position gradients is insufficient to assess under-reconstruction and
over-reconstruction over time. To address this, we incorporate the average
gradients of $\mu_{t}$ as an additional density control indicator.
Furthermore, in regions prone to over-reconstruction, we employ joint spatial
and temporal position sampling during Gaussian splitting.

##  4 Experiments

In this section, we present comparisons with state-of-the-art methods on two
well-established datasets for dynamic scene novel view synthesis: Plenoptic
Video dataset (Li et al., 2022b) and D-NeRF dataset (Pumarola et al., 2020).
Additionally, we perform ablation studies to gain insights into our method and
illustrate the efficacy of key design decisions. Video results and more use
cases can be found in our supplementary material.

###  4.1 Experimental setup

####  4.1.1 Datasets

##### Plenoptic Video dataset (Li et al., 2022b)

comprises six real-world scenes, each lasting ten seconds. For each scene, one
view is reserved for testing while other views are used for training. To
initialize the Guassians for this dataset, we utilize the colored point cloud
generated by COLMAP from the first frame of each scene. The timestamps of each
point are uniformly distributed across the scene’s duration.

##### D-NeRF dataset (Pumarola et al., 2020)

is a monocular video dataset comprising eight videos of synthetic scenes.
Notably, during each time step, only a single training image from a specific
viewpoint is accessible. To assess model performance, we employ standard test
views that originate from novel camera positions not encountered during the
training process. These test views are taken within the time range covered by
the training video. In this dataset, we utilize 100,000 randomly selected
points, evenly distributed within the cubic volume defined by
$[-1.2,1.2]^{3}$, and set their initial mean as the scene’s time duration.

###  4.2 Implementation details

To assess the versatility of our approach, we did not extensively fine-tune
the training schedule across different datasets. By default, we conducted
training with a total of 30,000 iterations, a batch size of 8, and halted
densification at the midpoint of the schedule. We adopted the settings of
Kerbl et al. (2023) for hyperparameters such as loss weight, learning rate,
and threshold. At the outset of training, we initialized both $q_{l}$ and
$q_{r}$ as unit quaternions to establish identity rotations and set the
initial time scaling to half of the scene’s duration. While the 4D Gaussian
theoretically extends infinitely, we applied a Gaussian filter with marginal
$p(t)<0.05$ when rendering the view at time $t$. For scenes in the Plenoptic
Video dataset, we introduced an additional initialization step. We initialized
the Gaussian with 100,000 extra points distributed uniformly on the sphere
encompassing the entire scene. This step aimed to accommodate the distant
background, which was not successfully reconstructed by colmap. We then
terminated the optimization process after 10,000 iterations.

###  4.3 Results of dynamic novel view synthesis

Table 1:  Comparison with the state-of-the-art methods on the Plenoptic Video benchmark. 1: Only report the result on the scene flames salmon. 2: Only report SSIM instead of MS-SSIM like others. 3 Measured by ourselves using their official released code.  Method | PSNR $\uparrow$ | DSSIM $\downarrow$ | FPS $\uparrow$
---|---|---|---
\- Plenoptic Video (real, multi-view)
Neural Volumes (Lombardi et al., 2019)1 | 22.80 | 0.062 | -
LLFF (Mildenhall et al., 2019)1 | 23.24 | 0.076 | -
DyNeRF (Li et al., 2022b)1 | 29.58 | 0.020 | 0.015
HexPlane (Cao & Johnson, 2023) | 31.70 | 0.014 | 0.563
K-Planes-explicit (Fridovich-Keil et al., 2023) | 30.88 | 0.020 | 0.233
K-Planes-hybrid (Fridovich-Keil et al., 2023) | 31.63 | 0.018 | -
MixVoxels-L (Wang et al., 2023) | 30.80 | 0.020 | 16.7
StreamRF (Li et al., 2022a)1 | 29.58 | - | 8.3
NeRFPlayer (Song et al., 2023) | 30.69 | 0.0352 | 0.045
HyperReel (Attal et al., 2023) | 31.1 | 0.0372 | 2.00
4DGS | 32.01 | 0.014 | 114

##### Results on the multi-view real scenes

Table 1 presents a quantitative evaluation on the Plenoptic Video dataset. Our
approach not only significantly surpasses previous methods in terms of
rendering quality but also achieves substantial speed improvements. Notably,
it stands out as the sole method capable of real-time rendering while
delivering high-quality dynamic novel view synthesis within this benchmark. To
complement this quantitative assessment, we also offer qualitative comparisons
on the “flame salmon” scene, as illustrated in Figure 3. The quality of
synthesis in dynamic regions notably excels when compared to other methods.
Several intricate details, including the black bars on the flame gun, the fine
features of the right-hand fingers, and the texture of the salmon, are
faithfully reconstructed, demonstrating the strength of our approach.

##### Results on the monocular synthetic videos

We also evaluate our approach on monocular dynamic scenes, a task known for
its inherent complexities. Previous successful methods often rely on
architectural priors to handle the underlying topology, but we refrain from
introducing such assumptions when applying our 4D Gaussian model to monocular
videos. Remarkably, our method surpasses all competing methods, as illustrated
in Table 2. This outcome underscores the ability of our 4D Gaussian model to
efficiently exchange information across various time steps.

Table 2:  Qualitative comparison on monocular dynamic scenes. The results are averaged over all scenes in the D-NeRF dataset.  Method | PSNR $\uparrow$ | SSIM $\uparrow$
---|---|---
\- D-NeRF (synthetic, monocular) |
T-NeRF (Pumarola et al., 2021) | 29.51 | 0.95
D-NeRF (Pumarola et al., 2021) | 29.67 | 0.95
TiNeuVox (Fang et al., 2022) | 32.67 | 0.97
HexPlanes (Cao & Johnson, 2023) | 31.04 | 0.97
K-Planes-explicit (Fridovich-Keil et al., 2023) | 31.05 | 0.97
K-Planes-hybrid (Fridovich-Keil et al., 2023) | 31.61 | 0.97
V4D (Gan et al., 2023) | 33.72 | 0.98
4DGS | 34.09 | 0.98
|  |  |  |
---|---|---|---|---
Ours (114 fps) | DyNeRF (0.015 fps) | K-Planes (0.23 fps) | NeRFPlayer (0.045 fps) | HyperReel (2.00 fps)
- | (Li et al., 2022b) | (Fridovich-Keil et al., 2023) | (Song et al., 2023) | (Attal et al., 2023)
|  |  |  |
Ground truth | Neural Volumes | LLFF | HexPlane (0.56 fps) | MixVoxels (16.7 fps)
- | (Lombardi et al., 2019) | (Mildenhall et al., 2019) | (Cao & Johnson, 2023) | (Wang et al., 2023)
Figure 3: Qualitative result on the flame salmon. It can be clearly seen that
the visual quality is higher than other methods in the region from the moving
hands and flame gun to the static salmon.

###  4.4 Ablation and analysis

Table 3: Ablation studies. We ablate our framework on two representative real scenes, flame salmon and cut roasted beef, which have volumetric effects, non-Lambertian surfaces, and different lighting conditions. “No-4DRot” denotes restricting the space and time independent of each other.  | Flame Salmon | Cut Roasted Beef | Average
---|---|---|---
| PSNR $\uparrow$ | SSIM $\uparrow$ | PSNR $\uparrow$ | SSIM $\uparrow$ | PSNR $\uparrow$ | SSIM $\uparrow$
No-4DRot | 28.78 | 0.95 | 32.81 | 0.971 | 30.79 | 0.96
No-4DSH | 29.05 | 0.96 | 33.71 | 0.97 | 31.38 | 0.97
No-Time split | 28.89 | 0.96 | 32.86 | 0.97 | 30.25 | 0.97
Full | 29.38 | 0.96 | 33.85 | 0.98 | 31.62 | 0.97

##### Coherent comprehensive 4D Gaussian

Our novel approach involves treating 4D Gaussian distributions without strict
separation of temporal and spatial elements. In Section 3.2, we discussed an
intuitive method to extend 3D Gaussians to 4D Gaussians, as expressed in
equation 6. This method assumes independence between the spatial $(x,y,z)$ and
temporal variable $t$, resulting in a block diagonal covariance matrix. The
first three rows and columns of the covariance matrix can be processed
similarly to 3D Gaussian splatting. We further additionally incorporate 1D
Gaussian to account for the time dimension.

To compare our unconstrained 4D Gaussian with this baseline, we conduct
experiments on two representative scenes, as shown in the Table 3. We can
observe the clear superiority of our unconstrained 4D Gaussian over the
constrained baseline. This underscores the significance of our unbiased and
coherent treatment of both space and time aspects in dynamic scenes.

##### 4D Gaussian is capable of capturing the underlying 3D movement

| Coffee Martini | Cook Spinach | Cut Beef | Flame Salmon | Sear Steak | Flame Steak
---|---|---|---|---|---|---
Render Flow |  |  |  |  |  |
GT Flow |  |  |  |  |  |
Render Image |  |  |  |  |  |
GT Image |  |  |  |  |  |
Figure 4: Visualization of the emerged dynamics of our 4D Gaussian  The
displayed views are selected from the test view of the Plenoptic Video
dataset. The ground truth optical flows are extracted by VideoFlow (Shi et
al., 2023) for reference.

Incorporation of 4D rotation to our 4D Gaussian equips it with the ability to
model the motion. Note that 4D rotation can result in a 3D displacement. To
assess this scene motion capture ability, we conduct a thorough evaluation.
For each Gaussian, we test the trajectory in space formed by the expectation
of its conditional distribution $\mu_{xyz|t}$. Then, we project its 3D
displacement between consecutive two frames to the image plane and render it
using equation 6 as the estimated optical flow. In Figure 4, we select one
frame from each scene in the Plenoptic Video dataset to exhibit the rendered
optical flow. The result reveals that without explicit motion supervision or
regularization, optimizing the rendering loss alone can lead to emergence of
coarse scene dynamics.

##### More ablations

To examine whether modeling the spatiotemporal evolution of Gaussian’s
appearance is helpful, we ablate 4DSH in the second row of Table 3. Compared
to the result of our default setting, we can find there is indeed a decline in
the rendering quality. Moreover, when turning our attention to 4D spacetime,
we realize that over-reconstruction may occur in more than just space. Thus,
we allow the Gaussian to split in time by sampling new positions using
complete 4D Gaussian as PDF. The last two rows in Table 3 verified the
effectiveness of the densification in time.

##  5 Conclusion

We introduce a novel approach to represent dynamic scenes, aligning the
rendering process with the imaging of such scenes. Our central idea involves
redefining dynamic novel view synthesis by approximating the underlying
spatio-temporal 4D volume of a dynamic scene using a collection of 4D
Gaussians. Experimental results across diverse scenes highlight the remarkable
superiority of our proposed representation, not only achieving state-of-the-
art rendering quality but also delivering substantial speed improvement over
existing alternatives. To the best of our knowledge, this work stands as the
first ever method capable of real-time, high-fidelity video synthesis for
complex, real-world dynamic scenes.

## References

  * Abou-Chakra et al. (2022) Jad Abou-Chakra, Feras Dayoub, and Niko Sünderhauf.  Particlenerf: Particle based encoding for online neural radiance fields in dynamic scenes.  _arXiv preprint_ , 2022.
  * Attal et al. (2023) Benjamin Attal, Jia-Bin Huang, Christian Richardt, Michael Zollhoefer, Johannes Kopf, Matthew O’Toole, and Changil Kim.  HyperReel: High-fidelity 6-DoF video with ray-conditioned sampling.  In _CVPR_ , 2023.
  * Barron et al. (2021) Jonathan T Barron, Ben Mildenhall, Matthew Tancik, Peter Hedman, Ricardo Martin-Brualla, and Pratul P Srinivasan.  Mip-nerf: A multiscale representation for anti-aliasing neural radiance fields.  In _ICCV_ , 2021.
  * Barron et al. (2022) Jonathan T Barron, Ben Mildenhall, Dor Verbin, Pratul P Srinivasan, and Peter Hedman.  Mip-nerf 360: Unbounded anti-aliased neural radiance fields.  In _CVPR_ , 2022.
  * Barron et al. (2023) Jonathan T Barron, Ben Mildenhall, Dor Verbin, Pratul P Srinivasan, and Peter Hedman.  Zip-nerf: Anti-aliased grid-based neural radiance fields.  _arXiv preprint_ , 2023.
  * Cao & Johnson (2023) Ang Cao and Justin Johnson.  Hexplane: A fast representation for dynamic scenes.  In _CVPR_ , 2023.
  * Chen et al. (2022) Anpei Chen, Zexiang Xu, Andreas Geiger, Jingyi Yu, and Hao Su.  Tensorf: Tensorial radiance fields.  In _ECCV_ , 2022.
  * Chen et al. (2023) Anpei Chen, Zexiang Xu, Xinyue Wei, Siyu Tang, Hao Su, and Andreas Geiger.  Factor fields: A unified framework for neural fields and beyond.  _arXiv preprint_ , 2023.
  * Fang et al. (2022) Jiemin Fang, Taoran Yi, Xinggang Wang, Lingxi Xie, Xiaopeng Zhang, Wenyu Liu, Matthias Nießner, and Qi Tian.  Fast dynamic radiance fields with time-aware neural voxels.  In _SIGGRAPH Asia Conference Papers_ , 2022.
  * Fridovich-Keil et al. (2022) Sara Fridovich-Keil, Alex Yu, Matthew Tancik, Qinhong Chen, Benjamin Recht, and Angjoo Kanazawa.  Plenoxels: Radiance fields without neural networks.  In _CVPR_ , 2022.
  * Fridovich-Keil et al. (2023) Sara Fridovich-Keil, Giacomo Meanti, Frederik Rahbæk Warburg, Benjamin Recht, and Angjoo Kanazawa.  K-planes: Explicit radiance fields in space, time, and appearance.  In _CVPR_ , 2023.
  * Gan et al. (2023) Wanshui Gan, Hongbin Xu, Yi Huang, Shifeng Chen, and Naoto Yokoya.  V4d: Voxel for 4d novel view synthesis.  _IEEE TVCG_ , 2023.
  * Hu et al. (2022) Tao Hu, Shu Liu, Yilun Chen, Tiancheng Shen, and Jiaya Jia.  Efficientnerf efficient neural radiance fields.  In _CVPR_ , 2022.
  * Kerbl et al. (2023) Bernhard Kerbl, Georgios Kopanas, Thomas Leimkühler, and George Drettakis.  3d gaussian splatting for real-time radiance field rendering.  _ACM Transactions on Graphics (TOG)_ , 2023.
  * Li et al. (2022a) Lingzhi Li, Zhen Shen, Zhongshu Wang, Li Shen, and Ping Tan.  Streaming radiance fields for 3d video synthesis.  In _NeurIPS_ , 2022a.
  * Li et al. (2022b) Tianye Li, Mira Slavcheva, Michael Zollhoefer, Simon Green, Christoph Lassner, Changil Kim, Tanner Schmidt, Steven Lovegrove, Michael Goesele, Richard Newcombe, et al.  Neural 3d video synthesis from multi-view video.  In _CVPR_ , 2022b.
  * Lombardi et al. (2019) Stephen Lombardi, Tomas Simon, Jason Saragih, Gabriel Schwartz, Andreas Lehrmann, and Yaser Sheikh.  Neural volumes: learning dynamic renderable volumes from images.  _ACM Transactions on Graphics (TOG)_ , 2019.
  * Luiten et al. (2023) Jonathon Luiten, Georgios Kopanas, Bastian Leibe, and Deva Ramanan.  Dynamic 3d gaussians: Tracking by persistent dynamic view synthesis.  _arXiv preprint_ , 2023.
  * Mildenhall et al. (2019) Ben Mildenhall, Pratul P Srinivasan, Rodrigo Ortiz-Cayon, Nima Khademi Kalantari, Ravi Ramamoorthi, Ren Ng, and Abhishek Kar.  Local light field fusion: Practical view synthesis with prescriptive sampling guidelines.  _ACM Transactions on Graphics (TOG)_ , 2019.
  * Mildenhall et al. (2020) Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  In _ECCV_ , 2020.
  * Müller et al. (2022) Thomas Müller, Alex Evans, Christoph Schied, and Alexander Keller.  Instant neural graphics primitives with a multiresolution hash encoding.  _ACM Transactions on Graphics (TOG)_ , 2022.
  * Pumarola et al. (2020) Albert Pumarola, Enric Corona, Gerard Pons-Moll, and Francesc Moreno-Noguer.  D-NeRF: Neural Radiance Fields for Dynamic Scenes.  In _CVPR_ , 2020.
  * Pumarola et al. (2021) Albert Pumarola, Enric Corona, Gerard Pons-Moll, and Francesc Moreno-Noguer.  D-nerf: Neural radiance fields for dynamic scenes.  In _CVPR_ , 2021.
  * Shi et al. (2023) Xiaoyu Shi, Zhaoyang Huang, Weikang Bian, Dasong Li, Manyuan Zhang, Ka Chun Cheung, Simon See, Hongwei Qin, Jifeng Dai, and Hongsheng Li.  Videoflow: Exploiting temporal cues for multi-frame optical flow estimation.  _arXiv preprint_ , 2023.
  * Song et al. (2023) Liangchen Song, Anpei Chen, Zhong Li, Zhang Chen, Lele Chen, Junsong Yuan, Yi Xu, and Andreas Geiger.  Nerfplayer: A streamable dynamic scene representation with decomposed neural radiance fields.  _IEEE TVCG_ , 2023.
  * Sun et al. (2022) Cheng Sun, Min Sun, and Hwann-Tzong Chen.  Direct voxel grid optimization: Super-fast convergence for radiance fields reconstruction.  In _CVPR_ , 2022.
  * Verbin et al. (2022) Dor Verbin, Peter Hedman, Ben Mildenhall, Todd Zickler, Jonathan T Barron, and Pratul P Srinivasan.  Ref-nerf: Structured view-dependent appearance for neural radiance fields.  In _CVPR_ , 2022.
  * Wang et al. (2023) Feng Wang, Sinan Tan, Xinghang Li, Zeyue Tian, and Huaping Liu.  Mixed neural voxels for fast multi-view video synthesis.  In _ICCV_ , 2023.
  * Zhang et al. (2020) Kai Zhang, Gernot Riegler, Noah Snavely, and Vladlen Koltun.  Nerf++: Analyzing and improving neural radiance fields.  _arXiv preprint_ , 2020.
  * Zwicker et al. (2002) Matthias Zwicker, Hanspeter Pfister, Jeroen Van Baar, and Markus Gross.  Ewa splatting.  _IEEE TVCG_ , 2002.

## Appendix

##  Appendix A Limitations

While the first row of Figure 5 reveals that the 4D Gaussian can adeptly
recover subsequent time steps exhibiting significant geometric deviations from
the first frame via densification and optimization, using point clouds
extracted from only the first frame, and achieves high fidelity in the
foreground dynamic regions. Nevertheless, in the absence of initial points,
our approach is difficult to capture distant background areas, even they are
static. Although some techniques such as spherical initialization that we
employed can mitigate this to an extent (for comparison, we turn off spherical
initialization in the scene coffee martini in Figure 5, where it is evident
that the exterior background was not successfully synthesized compared to the
scene flame salmon), it does not suggest that we get the correct geometry -
only a background map represented by a sphere of Gaussians is learned. These
issues might constrain the convenience of our method in some scenes.

##  Appendix B Proofs

In this chapter, we will prove the properties on which the main text relies
when treating the unnormalized Gaussian defined in Eq. equation 1 as a special
probability distribution.

First we will prove Gaussian conditional probability formula also holds in
equation 5 and equation 6, i.e.

$p(u,v,t)=p(t)p(u,v|t),$ (12)

where

$\displaystyle p(u,v,t)$
$\displaystyle=(2\pi)^{-\frac{3}{2}}\det{(\Sigma)}^{-\frac{1}{2}}\mathcal{N}(u,v,t|\mu,\Sigma)$
(13) $\displaystyle p(t)$
$\displaystyle=(2\pi)^{-\frac{1}{2}}\det{(\Sigma_{t})}^{-\frac{1}{2}}\mathcal{N}(t|\mu_{t},\Sigma_{t})$
(14) $\displaystyle p(u,v|t)$
$\displaystyle=(2\pi)^{-1}\det{(\Sigma_{uv|t})}^{-\frac{1}{2}}\mathcal{N}(u,v|\mu_{uv|t},\Sigma_{uv|t}).$
(15)

To prove equation 12, since Gaussian conditional probability formula holds for
normalized version:
$\mathcal{N}(u,v,t|\mu,\Sigma)=\mathcal{N}(t|\mu_{t},\Sigma_{t})\mathcal{N}(u,v|\mu_{uv|t},\Sigma_{uv|t})$,
we only need to prove

$\det{(\Sigma)}=\det{(\Sigma_{t})}\det{(\Sigma_{uv|t})}.$ (16)

From Gaussian property, we know that
$\Sigma_{uv|t}=\Sigma_{uv}-\Sigma_{uv,t}\Sigma_{t}^{-1}\Sigma_{t,uv}$. Then
from the decomposition of $\Sigma$ by

$\displaystyle\Sigma$
$\displaystyle=\begin{bmatrix}\Sigma_{uv}&\Sigma_{uv,t}\\\
\Sigma_{uv,t}&\Sigma_{t}\end{bmatrix}$ (17)
$\displaystyle=\begin{bmatrix}I&-\Sigma_{uv,t}\Sigma_{t}^{-1}\\\
0&I\end{bmatrix}\begin{bmatrix}\Sigma_{uv}-\Sigma_{uv,t}\Sigma_{t}^{-1}\Sigma_{t,uv}&0\\\
0&\Sigma_{t}\end{bmatrix}\begin{bmatrix}I&0\\\
-\Sigma_{t}^{-1}\Sigma_{t,uv}&I\end{bmatrix},$ (18)

equation 16 holds immediately. The proof can be easily extended onto
$p(x,y,z,t)=p(t)p(x,y,z|t)$.

##  Appendix C Additional quantitative results and visualizations

In Table 4, we provide the PSNR breakdown on different scenes. Figure 5 shows
more synthesis results at different timesteps for each scene in the Plenoptic
dataset. The quanlitative results clearly show that our 4DGS is capable to
faithfully capture the subtle movement of cookware. From the result in Cut
Roasted Beef, we can find that even though we only use the point cloud
extracted from the first frame as the initialization of the Gaussians, it is
still able to fit the body after a large movement with high fidelity.

| Coffee Martini | Spinach | Cut Beef | Flame Salmon | Flame Steak | Sear Steak | Mean
---|---|---|---|---|---|---|---
HexPlane | - | 32.04 | 32.55 | 29.47 | 32.08 | 32.39 | 31.70
K-Planes-explicit | 28.74 | 32.19 | 31.93 | 28.71 | 31.80 | 31.89 | 30.88
K-Planes-hybrid | 29.99 | 32.60 | 31.82 | 30.44 | 32.38 | 32.52 | 31.63
MixVoxels | 29.36 | 31.61 | 31.30 | 29.92 | 31.21 | 31.43 | 30.80
NeRFPlayer | 31.53 | 30.56 | 29.353 | 31.65 | 31.93 | 29.12 | 30.69
HyperReel | 28.37 | 32.30 | 32.922 | 28.26 | 32.20 | 32.57 | 31.10
Ours | 28.33 | 32.93 | 33.85 | 29.38 | 34.03 | 33.51 | 32.01
Table 4:  Per-scenes results on the Plenoptic Video dataset. we colored the Best, Second and Third results in each scene.  Cut beef |  |  |  |
---|---|---|---|---
Flame Salmon |  |  |  |
Sear steak |  |  |  |
Cook spinach |  |  |  |
Coffee martini |  |  |  |
Flame steak |  |  |  |
Figure 5:  View synthesis results at different times.


# Reachability-based Safe Planning for Multi-Vehicle Systems with Multiple
Targets

Jennifer C. Shih, Laurent El Ghaoui Jennifer Shih and Laurent El Ghaoui are
with the Department of Electrical Engineering and Computer Sciences,
University of California, Berkeley. {cshih<EMAIL_ADDRESS>
###### Abstract

Recently there have been a lot of interests in introducing UAVs for a wide
range of applications, making ensuring safety of multi-vehicle systems a
highly crucial problem. Hamilton-Jacobi (HJ) reachability is a promising tool
for analyzing safety of vehicles for low-dimensional systems. However,
reachability suffers from the curse of dimensionality, making its direct
application to more than two vehicles intractable. Recent works have made it
tractable to guarantee safety for 3 and 4 vehicles with reachability. However,
the number of vehicles safety can be guaranteed for remains small. In this
paper, we propose a novel reachability-based approach that guarantees safety
for any number of vehicles while vehicles complete their objectives of
visiting multiple targets efficiently, given any $K$-vehicle collision
avoidance algorithm where $K$ can in general be a small number. We achieve
this by developing an approach to group vehicles into clusters efficiently and
a control strategy that guarantees safety for any in-cluster and cross-cluster
pair of vehicles for all time. Our proposed method is scalable to large number
of vehicles with little computation overhead. We demonstrate our proposed
approach with a simulation on 15 vehicles. In addition, we contribute a more
general solution to the 3-vehicle collision avoidance problem from a past
recent work, show that the prior work is a special case of our proposed
generalization, and prove its validity.

##  I Introduction

In recent years, there have been vast interests from commercial companies to
government agencies in introducing unmanned aerial vehicles (UAVs) into the
airspace. For example, Google X [Google2020], Amazon [Amazon20], and UPS
[UPS2020] have all been developing drone technology for goods transport and
delivery. Companies such as Zipline Inc. [Zipline2020] and Vayu Inc.
[Vayu2020] utilize drones for delivery of critical medical supplies. The
government is also tapping into UAVs for disaster response [DSLRPros2020],
[Humanitarion2020], [AUVSI16] and military operations [Military2020]. With the
burgeoning enthusiasm for this emerging technology, the Federal Aviation
Administration recently devised guidelines specifically for UAVs [FAA2020].
Ensuring the safety of UAVs is thus an imminent and highly impactful problem.
A central problem in UAVs is to have them visit multiple targets for purposes
such as delivery of supplies or inspection at different locations. Thus the
problem of efficiently enabling all vehicles to accomplish their objectives of
visiting multiple targets while maintaining safety at all times is of
paramount importance.

The problem of collision avoidance among multi-agent systems has been studied
through various methods. For example, [Fiorini98, Vandenberg08] assume that
vehicles employ specific simple control strategies to induce velocity
obstacles that must be avoided by other vehicles to maintain safety. There
have also been approaches that use potential functions to tackle safety while
multiple agents travel along pre-determined trajectories [Saber02, Chuang07].
While these approaches offer insights into tackling multi-agent problems, they
do not offer the safety guarantees that are highly desirable for safety-
critical systems with general dynamical systems.

Differential game concerns the model and analysis of conflicts in dynamical
systems and is a promising tool for safety-critical problems for multi-vehicle
systems due to the strong theoretical guarantees it can provide. One such
technique is Hamilton-Jacobi (HJ) reachability [Mitchell05]. HJ reachability
has been successfully used to guarantee safety for small-scale problems that
concern one or two vehicles [Fisac15, Mitchell05]. Despite its favorable
theoretical guarantees and applicability to systems with general dynamics, it
suffers from the curse of dimensionality because the computation of reachable
sets grows exponentially with the number of states in the system and hence the
number of vehicles, making its direct application to systems of more than two
vehicles intractable.

There have been many attempts in using differential games to analyze three-
player differential games with varying-degree of assumptions on each agent in
non-cooperative settings [Tanimoto78, Su14, Fisac15b]. [Shih16] is the first
work built on reachability that guarantees safety for three vehicles while
vehicles are allowed to execute any control when the safe controller does not
need to be applied, which endows vehicles more flexibility and is thus
preferable in certain scenarios. [Chen17] further builds on [Shih16] to
guarantee safety for four vehicles in unstructured settings. However, [Chen17]
assumes that vehicles can remove themselves from the environment when
conflicts cannot be resolved for all vehicles, which is not always possible
and could be undesirable in some situations. In contrast, we propose a control
strategy to guarantee safety for four and more number of vehicles without
assuming the ability to remove any vehicle during conflict resolution.

Works such as [Chen15, Chen15b] have proposed controllers that guarantee
safety for larger number of vehicles by imposing varying degrees of structure
on the vehicles, including strong assumptions such as vehicles traveling in a
single line of platoon [Chen15b] or vehicles determining their trajectories a
priori [Chen15]. In general, there is a trade-off between the number of
vehicles safety can be guaranteed for and how strong the assumption on the
structure of the multi-vehicle system is. In this paper, we provide a novel
approach based on reachability that guarantees safety for any number of
vehicles by using less structure than those of [Chen15, Chen15b] for a class
of dynamical systems. Although our proposed method adopts more structure than
that of [Shih16] and [Chen17], our approach can guarantee safety for any
number of vehicles while avoiding having to remove vehicles from the
environment when conflict cannot be resolved and retaining some level of
unstructuredness.

Our main contribution is a novel approach to guarantee safety while any number
of vehicles are tasked with visiting multiple targets for a class of dynamical
systems. We first propose a method that assigns vehicles into “teams” and
induces the behavior that vehicles with similar objectives are assigned to the
same team for efficiency. We then propose a control strategy to guarantee
safety for any pair of vehicles within a team and across different teams,
effectively guaranteeing safety for all vehicles. Furthermore, we provide a
more general optimization problem that renders three-vehicle collision
avoidance safe than that of [Shih16] by establishing a general way of
selecting the objective function in the optimization problem in [Shih16] and
providing a general proof for this new guideline.

##  II Background

In this paper, we propose to divide vehicles into teams and present a
cooperative control method that guarantees safety for any $N$ vehicles while
they complete their objectives by building on any $K$-vehicle collision
avoidance algorithm where $N$ can in general be much larger than $K$. Our
proposed method builds on Hamilton-Jacobi (HJ) reachability. In this section,
we provide an overview of HJ reachability and the three-vehicle collision
avoidance strategy proposed in [Shih16].

###  II-A Hamilton-Jacobi (HJ) Reachability

HJ reachability is a promising method for ensuring safety. We give a brief
overview of how HJ reachability is used to guarantee safety for a pair of
vehicles as presented in [Mitchell05]. For any two vehicles $Q_{i}$ and
$Q_{j}$ with dynamics describe by the following ordinary differential equation
(ODE)

$\dot{x}_{m}=f(x_{m},u_{m}),\quad u_{m}\in\mathcal{U},m=i,j,\\\ $ (1)

their relative dynamics can be specified by an ODE

$\displaystyle\dot{\bar{x}}_{ij}$
$\displaystyle=g_{ij}(\bar{x}_{ij},u_{i},u_{j}),u_{i},u_{j}\in\mathcal{U}$ (2)

where $\bar{x}_{ij}$ is a relative state representation between $x_{i}$ and
$x_{j}$ that doesn’t necessarily have to be $x_{i}-x_{j}$. Note that we are
using $\bar{x}_{ij}$ here because we will use $x_{ij}\equiv x_{i}-x_{j}$
throughout the paper. We assume there is a bijection between $x_{ij}$ and
$\bar{x}_{ij}$.

In the reachability problem, for any pair of vehicles $Q_{i}$ and $Q_{j}$, we
are interested in determining the backwards reachable set (BRS)
$\mathcal{V}_{ij}(T)$, the set of states from which there exists no control
for $Q_{i}$, in the worst case non-anticipative control strategy by $Q_{j}$,
that can keep the system from entering some final set $\bar{\mathcal{Z}}_{ij}$
within a time horizon $T$. Note we will use the notation $\mathcal{Z}_{ij}$
such that
$x_{ij}\in\mathcal{Z}_{ij}\Leftrightarrow\bar{x}_{ij}\in\bar{\mathcal{Z}}_{ij}$.
For safety purpose, $\bar{\mathcal{Z}}_{ij}$ represents dangerous
configurations between $Q_{i}$ and $Q_{j}$.

BRS $\mathcal{V}_{ij}$ can be mathematically described as

$\displaystyle\mathcal{V}_{ij}(t)=\\{\bar{x}_{ij}:\forall
u_{i}\in\mathbb{U},\exists u_{j}\in\mathbb{U},$ (3)
$\displaystyle\bar{x}_{ij}(\cdot)\text{ satisfies \eqref{eq:rdyn}},\exists
s\in[0,t],\bar{x}_{ij}(s)\in\bar{\mathcal{Z}}_{ij}\\},$

and obtained by $\mathcal{V}_{ij}(t)=\bar{x}_{ij}:V_{ij}(t,\bar{x}_{ij})\leq
0\\}$ where the details of how to obtain the value function
$V_{ij}(t,\bar{x}_{ij})$ is in [Mitchell05]. In this paper, we assume
$t\rightarrow\infty$ and write
$V_{ij}(\bar{x}_{ij})=\lim_{t\rightarrow\infty}V_{ij}(t,\bar{x}_{ij})$. If the
relative state $\bar{x}_{ij}$ of $Q_{i}$ and $Q_{j}$ is outside of
$\mathcal{V}_{ij}$, then $Q_{i}$ is safe from $Q_{j}$. If $\bar{x}_{ij}$ is at
the boundary of $\mathcal{V}_{ij}$, [Mitchell05] shows that as long as the
optimal control

$u_{ij}^{*}=\arg\max_{u_{i}\in\mathcal{U}}\min_{u_{j}\in\mathcal{U}}D_{\bar{x}_{ij}}V(\bar{x}_{ij})\cdot
g_{ij}(\bar{x}_{ij},u_{i},u_{j})$ (4)

is applied immediately, $Q_{i}$ is guaranteed to be able to avoid collision
with $Q_{j}$ over an infinite time horizon.

With the above in mind, we formally define the terms safety level and
potential conflict:

###### Definition 1

Safety level: the safety level of vehicle $Q_{i}$ with respect to vehicle
$Q_{j}$ given their relative state $\bar{x}_{ij}$ is defined as $s_{ij}\equiv
V_{ij}(\bar{x}_{ij})$.

###### Definition 2

Potential conflict: We say vehicle $Q_{i}$ is in potential conflict with
vehicle $Q_{j}$ if the safety level $s_{ij}\leq l$ for some safety threshold
$l>0$. The potential conflict is resolved when $s_{ij}>l$.

###  II-B Three-vehicle collision avoidance integer linear program (ILP)

HJ reachability described in Section II-A guarantees safety for $N=2$ vehicle
but applying the method directly to $N=3$ vehicles is an intractable task.
[Shih16] proposes an integer linear program that provides higher level control
logic to guarantee safety for $N=3$ vehicles. Although our proposed method in
this paper can be used with any $K$-vehicle collision avoidance algorithm that
resolves potential conflicts while remaining safe, we give a brief overview of
the method proposed in [Shih16] because we also contribute a generalization to
the approach in [Shih16] in this paper.

At each time step, based on the safety value $s_{ij}\equiv
V_{ij}(\bar{x}_{ij})$’s of all pairs of vehicles, [Shih16] designs an integer
optimization problem that solves for binary decision variables $\hat{u}_{ij}$
where $\hat{u}_{ij}=1$ indicates that vehicle $Q_{i}$ should use the optimal
avoidance control $u_{ij}^{*}$ in Equation (4) to avoid $Q_{j}$; if
$\hat{u}_{ij}=0$, vehicle $Q_{i}$ does not need to avoid $Q_{j}$ and can
perform any action. The optimization problem has the following form

$\displaystyle\max_{\hat{u}_{ij}}$ $\displaystyle\sum_{i,j}c_{ij}\hat{u}_{ij}$
(5) subject to $\displaystyle\hat{u}_{ij}+\hat{u}_{ji}\leq 1$
$\displaystyle\forall i,j,i\neq j$ $\displaystyle\quad(\ref{eq:baseMIP}a)$
$\displaystyle\sum_{j}\hat{u}_{ij}\leq 1$ $\displaystyle\forall i$
$\displaystyle\quad(\ref{eq:baseMIP}b)$
$\displaystyle\hat{u}_{ij}\in\\{0,1\\}$ $\displaystyle\forall i,j,i\neq j$
$\displaystyle\quad(\ref{eq:baseMIP}c).$

The objective function is linear in the variables $\hat{u}_{ij}$’s with
coefficients $c_{ij}$’s. The constraints (5a) and (5b) enforce only one
vehicle in any pair of vehicles should employ avoidance control and each
vehicle avoids a maximum of one other vehicle respectively. [Shih16] presents
a specific numeric choice of $c_{ij}$’s to guarantee three-vehicle safety.

In this paper, we further present a general guideline for choosing the
$c_{ij}$’s in the objective function of the integer program (5) and show that
as long as $c_{ij}$’s satisfy the criteria we proposed, safety for three
vehicles can be guaranteed. This enables a much more general and elegant proof
compared to that presented in [Shih16].

##  III Problem Formulation

Consider $N$ vehicles, denoted $Q_{i},i=1,2,\ldots,N$, with identical dynamics
described by the following ordinary differential equation (ODE)

$\dot{x}_{i}=f(x_{i},u_{i}),\quad u_{i}\in\mathcal{U},\quad i=1,\ldots,N$ (6)

where $x_{i}\in\mathbb{R}^{n}$ is the state of the $i$th vehicle $Q_{i}$, and
$u_{i}$ is the control of $Q_{i}$. In this paper, we work with a class of
dynamical systems such that the dynamics $f$ can be described completely by a
subset of the state and the control input, i.e., we can write
$x_{i}=[x_{i,a}\text{ }x_{i,b}]$ where
$x_{i,a}\in\mathbb{R}^{n_{a}},x_{i,b}\in\mathbb{R}^{n_{b}}$, $n_{a}\geq
1,n_{b}\geq 0$, such that

$\dot{x}_{i}=f(x_{i},u_{i})=f_{b}(x_{i,b},u_{i}),\quad
u_{i}\in\mathcal{U},\quad i=1,\ldots,N$ (7)

for some function $f_{b}$. Note that we will use the subscript ”a” or ”b” to
denote the components of a given state based on the definition above
throughout the paper.

Each of the $N$ vehicles is tasked with visiting a set of targets
$\mathcal{G}_{i}$, in no particular order, out of a set of $M$ targets
$\\{\mathcal{T}_{1},\dots,\mathcal{T}_{M}\\}$, i.e.,
$\mathcal{G}_{i}\subseteq\\{\mathcal{T}_{1},\dots,\mathcal{T}_{M}\\}$. Note
that the exact location of each target need not to be known a priori. Each
vehicle $Q_{i}$ must reach all of its targets while at all times avoid the
danger zone $\mathcal{Z}_{ij}$ with respect to any other vehicle
$Q_{j},j=1,\ldots,N,j\neq i$. The danger zone $\mathcal{Z}_{ij}$ represents
relative configuration between $Q_{i}$ and $Q_{j}$ that are considered
undesirable, such as collision. In this paper, we assume the danger zone
$\mathcal{Z}_{ij}$ for each pair of vehicles can be identically defined by a
norm function on the $x_{ij,a}$ component of the relative state $x_{ij}$,
$d(x_{ij,a}):\mathbb{R}^{n_{a}}\rightarrow\mathcal{R}^{+}$ where
$x_{ij,a}\equiv x_{i,a}-x_{j,a}$. In particular, the danger zone
$\mathcal{Z}_{ij}$ is defined such that
$x_{ij}\in\mathcal{Z}_{ij}\Leftrightarrow d(x_{ij,a})\leq R_{ij}$ where
$R_{ij}$ is some positive real number. Note that in this paper, we assume
$R_{ij}=R_{ji}$ for any pair of vehicles $Q_{i},Q_{j}$.

###### Remark 1

Many practical and common dynamical systems have dynamics structures outlined
in Equation (7), such as the 2D point system [Royo19], 3D Dubins Car [Shih16],
6D Quadrotor [Royo19], 6D Acrobatic Quadrotor [Gillula11], 7D Quadrotor
[Royo19], and 10D near-hover quadrotor [Bouffard12]. In addition, for all
these dynamical systems, defining the danger zone based on the $x_{a}$
component of the state $x$ makes intuitive sense as the $x_{a}$ components
represent the x, y, z translational coordinates of these systems, which is
what we generally use to define collisions among vehicles.

Given the vehicle dynamics in (6), the derived relative dynamics in (2), the
danger zones $\mathcal{Z}_{ij},i,j=1,\ldots,N,i\neq j$, and the sets of
targets each vehicle $Q_{i}$ needs to go through
$\mathcal{G}_{i},i=1,\dots,N$, we propose a cooperative planning and control
strategy that:

  1. 1.

assigns vehicles to clusters (teams) based on their objectives;

  2. 2.

determines the initial states of all vehicles;

  3. 3.

guarantees safety for all vehicles for all time.

###### Remark 2

In this paper, we will use the terms “cluster” and “team” interchangeably.

Our proposed method guarantees that all vehicles will be able to stay out of
the danger zone with respect to any other vehicle regardless of the number of
vehicles $N$ in the environment. Additionally our method guarantees safety for
all vehicles without vehicles having to remove themselves from the environment
when conflicts cannot be resolved, as assumed in [Chen17]. For all initial
configurations, target locations, and objectives of each vehicle in our
simulations, all vehicles also complete their objectives of visiting all their
targets successfully.

##  IV Methodology

Our proposed method consists of two phases: first, we develop the notion of
teams (clusters) of vehicles and present a method to assign vehicles to teams
based on their targets, with the goal of minimizing the time it takes for all
vehicles to complete their objectives. Second, we propose the idea of
augmented danger zone for each pair of teams. Based on this, we propose a
control strategy to ensure safety for any pair vehicles on the same team and
across different teams, which in combination guarantees safety for all
vehicles.

###  IV-A Assignment of vehicles to clusters

We first propose an optimization problem that assigns the $N$ vehicles to $K$
teams, $\mathcal{H}_{1},\dots,\mathcal{H}_{K}$. Each vehicle should be
assigned to exactly one cluster and the objective of each cluster is then to
visit, in no particular order, the union of the sets of targets of the
vehicles in this cluster. Since we aim to have our approach be applicable to
scenarios where the location of each target is not known a priori, we assume
that the amount of time a cluster takes to complete its objective is
proportional to the number of targets each cluster needs to visit and we don’t
consider the order in which each cluster visits its targets during the
planning process in this paper. With this in mind, we formulate the objective
function of the proposed optimization problem to minimize the maximum number
of targets each cluster needs to visit, which load-balances the number of
targets each cluster should visit by grouping vehicles with similar objectives
into the same cluster. Furthermore, we show that the proposed optimization
problem can be converted into an integer linear program and thus solved
efficiently with standard integer program solvers.

Recall that each vehicle $Q_{i}$’s objective is to visit a set of targets
$\mathcal{G}_{i}$ where
$\mathcal{G}_{i}\subseteq\\{\mathcal{T}_{1},\dots,\mathcal{T}_{M}\\}$. Based
on this, we define binary variables $e_{ij}$,
$i\in\\{1,\dots,N\\},j\in\\{1,\dots,M\\}$, such that
$e_{ij}=\mathds{1}\\{\mathcal{T}_{j}\in\mathcal{G}_{i}\\}$
111$\mathds{1}(\mathcal{A})$ is an indicator function on event $\mathcal{A}$
such that $\mathds{1}(\mathcal{A})=1$ if $\mathcal{A}$ is true and
$\mathds{1}(\mathcal{A})=0$ otherwise.. Next we define optimization variables
$y_{ik}$, $i\in\\{1,\dots,N\\},k\in\\{1,\dots,K\\}$, which are also binary
variables. $y_{ik}=1$ means that vehicle $Q_{i}$ is assigned to cluster
$\mathcal{H}_{k}$, and $y_{ik}=0$ otherwise. Based on the goal of minimizing
the maximum number of targets each cluster needs to visit as described in the
previous paragraph, we propose the following optimization problem to solve for
$y_{ik}$’s:

$\displaystyle\underset{y_{ik}}{\text{min}}$
$\displaystyle\underset{k}{\text{max}}\left(\sum_{j=1}^{M}\underset{i}{max}\\{e_{ij}y_{ik}\\}\right)$
(8) subject to $\displaystyle\sum_{k=1}^{K}y_{ik}=1,\forall
i\in\\{1,\dots,N\\}$ $\displaystyle y_{ik}\in\\{0,1\\},\forall
i\in\\{1,\dots,N\\},\forall k\in\\{1,\dots,K\\}$

Note that due to space constraints under the $min,max$ notations in the
objective, we omit that we’re optimizing over $y_{ik},\forall
i\in\\{1,\dots,N\\},\forall k\in\\{1,\dots,K\\}$ for the minimization and
$k,\forall k\in\\{1,\dots,K\\}$ and $i,\forall i\in\\{1,\dots,N\\}$ for the
maximization in the above optimization problem.

The summation $\sum_{j=1}^{M}\underset{i}{max}\\{e_{ij}y_{ik}\\}$ is
equivalent to the total number of targets that cluster $\mathcal{H}_{k}$ needs
to visit. To see this, for a given target $\mathcal{T}_{j}$, the term
$e_{ij}y_{ik}$ in the summation equals to $1$ if vehicle $Q_{i}$ needs to
visit target $\mathcal{T}_{j}$ and $Q_{i}$ is assigned to cluster
$\mathcal{H}_{k}$. $e_{ij}y_{ik}=0$ otherwise. Hence
$\underset{i}{max}\\{e_{ij}y_{ik}\\}$ equals to $1$ if at least one vehicle
assigned to cluster $\mathcal{H}_{k}$ needs to visit target $\mathcal{T}_{j}$.
$\underset{i}{max}\\{e_{ij}y_{ik}\\}=0$ otherwise. Summing
$\underset{i}{max}\\{e_{ij}y_{ik}\\}$ over all targets gives the total number
of targets cluster $\mathcal{H}_{k}$ needs to visit.

Next we show that the optimization problem (8) can be converted into a
standard integer linear program by introducing a slack variable and an
inequality constraint for each of the maximization operations in the
objective.

$\displaystyle\underset{y_{ik},o_{kj},O}{\text{min}}$ $\displaystyle O$
subject to $\displaystyle\sum_{k=1}^{K}y_{ik}=1,\forall i\in\\{1,\dots,N\\}$
$\displaystyle y_{ik}\in\\{0,1\\},\forall i\in\\{1,\dots,N\\},\forall
k\in\\{1,\dots,K\\}$ $\displaystyle e_{ij}y_{ik}\leq o_{kj},\forall
i\in\\{1,\dots,N\\},\forall k\in\\{1,\dots,K\\},$ $\displaystyle\forall
j\in\\{1,\dots,M\\}$ $\displaystyle\sum_{j=1}^{M}o_{kj}\leq O,\forall
k\in\\{1,\dots,K\\}.$

The above integer linear problem can be solved efficiently by off-the-shelf
integer program solvers. Once solved, the values of $y_{ik}$’s are the
solution to the team assignment problem. This completes the first step of the
planning process.

###  IV-B Collision Avoidance Protocol Design

In this section, we present our proposed control strategy that ensure all
vehicles remain safe when completing their objectives after the vehicles have
been assigned to teams. Specifically, given any $K$-vehicle collision
avoidance algorithm that guarantees safety when resolving potential conflicts
among $K$ vehicles, we propose a general way to initialize vehicle locations
and a safe control strategy such that the following always hold for $N$
vehicles where $N$ can be much larger than $K$:

  * •

Any vehicle is safe from any other vehicle within the same cluster.

  * •

Any vehicle in a cluster is safe from any vehicle in any other cluster.

####  IV-B1 Guaranteed safety for all vehicles within the same cluster

We first prove a theorem that motivates the control strategy that enables any
pair of vehicles in the same cluster to remain safe from each other.

###### Theorem 1

Give the structure of the dynamics and the danger zone defined in Section III,
for any two vehicles $Q_{i}$ and $Q_{j}$, if the initial states
$x_{i}(t_{0}),x_{j}(t_{0})$ of the two vehicles satisfy
$d(x_{ij,a}(t_{0}))>R_{ij}$ and $x_{i,b}(t_{0})=x_{j,b}(t_{0})$ and the
controls of the vehicles satisfy $u_{i}(t)=u_{j}(t)\text{ }\forall t\geq
t_{0}$, then vehicles $Q_{i}$ and $Q_{j}$ will remain safe from each other for
all $t>t_{0}$.

###### Proof:

Given that $x_{i,b}(t_{0})=x_{j,b}(t_{0})$ and $u_{i}(t)=u_{j}(t)\text{
}\forall t\geq t_{0}$, we have that at any time $t\geq t_{0}$,
$\dot{x}_{i}(t)=f(x_{i}(t),u_{i}(t))=f_{b}(x_{i,b}(t),u_{i}(t))=f_{b}(x_{j,b}(t),u_{j}(t))=f(x_{j}(t),u_{j}(t))=\dot{x}_{j}(t)$.
Because $\dot{x}_{ij,a}(t)=0\text{ }\forall t\geq t_{0}$,
$x_{ij,a}(t)=x_{ij,b}(t_{0})\text{ }\forall t>t_{0}$. Thus,
$d(x_{ij,a}(t))=d(x_{ij,a}(t_{0}))>R_{ij}\text{ }\forall t>t_{0}$. Since
$R_{ij}=R_{ji}$ and $x_{ij}(t)=-x_{ji}(t)$, we have
$d(x_{ij,a}(t))=d(x_{ji,a}(t))>R_{ij}=R_{ji}\text{ }\forall t\geq t_{0}$,
which proves that $Q_{i}$ and $Q_{j}$ will remain safe from each other for all
$t>t_{0}$. ∎ The above shows that if we initialize any pair of vehicles
$Q_{i},Q_{j}$ in the same cluster such that $x_{i,b}(t_{0})=x_{j,b}(t_{0})$,
vehicles $Q_{i},Q_{j}$ start out safe from each other, and that they employ
the same control at any time, the two vehicles will continue to remain outside
of each other’s danger zone for all time. We can directly use this insight to
initialize all vehicles in the same cluster such that any pair of vehicles in
the same cluster satisfies the above conditions and have all vehicles in the
same cluster employ the same control to guarantee safety for all vehicles in
the same cluster for all time.

####  IV-B2 Guaranteed safety of any vehicle with respect to any other vehicle
in a different cluster

The key idea of our proposed method is that we can think of each cluster
$\mathcal{H}_{k}$ as an imaginary vehicle with state $x_{\mathcal{H}_{k}}$ and
dynamics identical to that of the individual vehicle’s dynamics. We propose
the concept of augmented danger zone between any pair of clusters, which
allows us to guarantee that any vehicle in a cluster will remain safe from any
vehicle in any other cluster.

Before we proceed to describe our approach, we first define a few essential
terms:

###### Definition 3

Maximum vehicle distance to cluster center for cluster $\mathcal{H}_{k}$ is
defined as
$R_{\mathcal{H}_{k}}\equiv\underset{i:Q_{i}\in\mathcal{H}_{k}}{max}\text{
}d(x_{\mathcal{H}_{k},a}-x_{i,a})$ where $x_{\mathcal{H}_{k}}$ is the state of
the imaginary vehicle representing cluster $\mathcal{H}_{k}$.

###### Definition 4

Augmented danger zone $\mathcal{Z}_{\mathcal{H}_{k}\mathcal{H}_{l}}$ of
cluster $\mathcal{H}_{k}$ with respect to $\mathcal{H}_{l}$ is defined as
$x_{\mathcal{H}_{k}\mathcal{H}_{l}}\in\mathcal{Z}_{\mathcal{H}_{k}\mathcal{H}_{l}}\Leftrightarrow
d(x_{\mathcal{H}_{k}\mathcal{H}_{l},a})\leq
R_{\mathcal{H}_{k}\mathcal{H}_{l}}$ where
$x_{\mathcal{H}_{k}\mathcal{H}_{l}}=x_{\mathcal{H}_{k}}-x_{\mathcal{H}_{l}}$
and
$R_{\mathcal{H}_{k}\mathcal{H}_{l}}=R_{\mathcal{H}_{k}}+R_{\mathcal{H}_{l}}+\underset{Q_{i}\in\mathcal{H}_{k},Q_{j}\in\mathcal{H}_{l}}{max}\text{
}R_{ij}$. And note that
$x_{\mathcal{H}_{k}\mathcal{H}_{l}}\in\mathcal{Z}_{\mathcal{H}_{k}\mathcal{H}_{l}}\Leftrightarrow\bar{x}_{\mathcal{H}_{k}\mathcal{H}_{l}}\in\bar{\mathcal{Z}}_{\mathcal{H}_{k}\mathcal{H}_{l}}$.

###### Definition 5

Safety level of cluster $\mathcal{H}_{k}$ with respect to $\mathcal{H}_{l}$ is
defined as $s_{\mathcal{H}_{k}\mathcal{H}_{l}}\equiv
V_{\mathcal{H}_{k}\mathcal{H}_{l}}(\bar{x}_{\mathcal{H}_{k}\mathcal{H}_{l}})$
where
$V_{\mathcal{H}_{k}\mathcal{H}_{l}}(\bar{x}_{\mathcal{H}_{k}\mathcal{H}_{l}})$
is computed based on reachability computation described in Section II-A with
dynamics identical to that of the vehicle dynamics and danger zone
$\bar{\mathcal{Z}}_{\mathcal{H}_{k}\mathcal{H}_{l}}$.

Now we prove a result that relates the danger zone of the imaginary vehicles
representing the clusters and the danger zone of the actual vehicles.

###### Theorem 2

If
$x_{\mathcal{H}_{k}\mathcal{H}_{l}}\notin\mathcal{Z}_{\mathcal{H}_{k}\mathcal{H}_{l}}$,
then $x_{ij}\notin\mathcal{Z}_{ij}$ for any pair of vehicles $Q_{i},Q_{j}$
such that $Q_{i}\in\mathcal{H}_{k}$ and $Q_{j}\in\mathcal{H}_{l}$.