# The ultrametric backbone is the union of all minimum spanning forests

Jordan C. Rozum, Luis M. Rocha
Department of Systems Science and Industrial Engineering
Binghamton University (State University of New York)
Binghamton, NY
<EMAIL_ADDRESS>

###### Abstract

Minimum spanning trees and forests are powerful sparsification techniques that
remove cycles from weighted graphs to minimize total edge weight while
preserving node reachability, with applications in computer science, network
science, and graph theory. Despite their utility and ubiquity, they have
several limitations, including that they are only defined for undirected
networks, they significantly alter dynamics on networks, and they do not
generally preserve important network features such as shortest distances,
shortest path distribution, and community structure. In contrast, distance
backbones, which are subgraphs formed by all edges that obey a generalized
triangle inequality, are well defined in directed and undirected graphs and
preserve those and other important network features. The backbone of a graph
is defined with respect to a specified path-length operator that aggregates
weights along a path to define its length, thereby associating a cost to
indirect connections. The backbone is the union of all shortest paths between
each pair of nodes according to the specified operator. One such operator, the
$\max$ function, computes the length of a path as the largest weight of the
edges that compose it (a weakest link criterion). It is the only operator that
yields an algebraic structure for computing shortest paths that is consistent
with De Morgan’s laws. Applying this operator yields the ultrametric backbone
of a graph in that (semi-triangular) edges whose weights are larger than the
length of an indirect path connecting the same nodes (i.e., those that break
the generalized triangle inequality based on $\max$ as a path-length operator)
are removed. We show that the ultrametric backbone is the union of minimum
spanning forests in undirected graphs and provides a new generalization of
minimum spanning trees to directed graphs that, unlike minimum equivalent
graphs and minimum spanning arborescences, preserves all $\max-\min$ shortest
paths and De Morgan’s law consistency.

##  1 Introduction and background

Many problems in network science and graph theory, such as predicting links
[1], optimizing traversal [2, 3], identifying primary transmission modes in
spreading dynamics [4], locating central (or redundant) nodes and edges [3],
defining community structure [4], or predicting the size of cascades when
nodes or edges are attacked, depend strongly on the structure of shortest
paths [5]. Often the length of a path is computed as the sum of its edge
weights but the underlying system or process may suggest other choices, such
as multiplying the edge weights or taking only the largest edge weight. The
method of aggregating edge weights determines the distances between nodes and
which paths are shortest in the context of a specific optimization problem.
The aggregation operation encodes the cost of indirect associations or
interactions. Moreover, other methods beyond shortest paths, such as diffusion
and resistance distances, are possible to aggregate indirect associations in
networks [6, 7]. A unifying framework to study families of algebraically
consistent edge weighting and path aggregation that quantifies node-to-node
distance in weighted graphs is provided by the distance closure [8] (see
appendix for details).

The distance closure applies to distance-weighted graphs $G=(X,D)$ with node
set $X$ and edge set $D$. In $G$, $d_{i,j}$ takes values in the extended real
numbers $[0,\infty]$ and denotes the weight of an edge $(x_{i},x_{j})$ from
$x_{i}\in X$ to $x_{j}\in X$ when it is finite, and the absence of an edge
when it is infinite. When it is clear from context, $D=D(X,X)$ may also refer
to the weighted adjacency matrix with entries $d_{i,j}$ (where non-edges take
on the value $\infty$). Similarly, when context allows, $d_{i,j}$ may refer to
the edge $(x_{i},x_{j})$ itself (when $d_{i,j}$ is finite) or to the absence
of such an edge (when $d_{i,j}=\infty$). 111We make no distinction between an
edge of weight $\infty$ and a non-edge. In particular, this means that all
edges have finite weight, and thus a path cannot contain edges with infinite
weight. Similarly, the weight of a graph, which refers to the sum of its
edges, is the sum over only the finite entries of its adjacency matrix.
Removing an edge $(x_{i},x_{j})$ is equivalent to setting $d_{i,j}=\infty$,
and similarly, adding an edge $(x_{i},x_{j})$ is equivalent to setting
$d_{i,j}$ to a finite (non-negative) value. Comparisons or binary operations
on edges are to be understood as operating on the edge weights.

In this framework, applying triangular metric space operations [9, 10] leads
to general algebraic definitions of network distances including shortest path
distance, diffusion distance, and resistance as the closure of an algebraic
structure [8]. Specifically, one defines a non-decreasing, commutative, and
associative operation
$\otimes:[0,\infty]\times[0,\infty]\rightarrow[0,\infty]$ with identity $0$
for accumulating edge weights along a path to determine path length (e.g., the
sum of edge weights), and a decreasing, commutative, and associative operation
$\oplus:[0,\infty]\times[0,\infty]\rightarrow[0,\infty]$ with identity
$\infty$ for aggregating path lengths to determine the distance between nodes
(e.g., the minimum of path lengths). These two operations form monoids on
$[0,\infty]$, and as a pair $\mathcal{D}=(\oplus,\otimes,[0,\infty])$ they
determine how node-to-node distances are computed. The _distance closure_ with
respect to $\mathcal{D}$ is $G^{\mathcal{D}}=(X,D^{\mathcal{D}})$ with edge
weights $d^{\mathcal{D}}_{i,j}$ given by the distances between nodes as
determined by the operators of $\mathcal{D}$ (and infinite between the nodes
where no path exists in $G$).

As a concrete example, the traditional distance closure used in network
science is formed using $\oplus\equiv\min$ and $\otimes\equiv+$ (i.e.,
$\mathcal{D}=(\min,+,[0,\infty])$), so that the length of a path is the sum of
its edge weights, and the distance from node $x_{i}$ to node $x_{j}$ is the
smallest length among all paths from $x_{i}$ to $x_{j}$. In this case, the
closure $G^{\mathcal{D}}$ is the traditional graph of node-to-node distances.

In the usual case of shortest-path distances ($\oplus\equiv\min$), the
distance between nodes is the length of the shortest path between them for
some choice of edge-weight aggregation operator. In this case, a generalized
triangle inequality provides a transitivity criterion that separates edges
into two categories: triangular edges that obey it, and semi-triangular edges
that do not. Triangular edges are necessary and sufficient to compute all
shortest paths, while semi-triangular edges are redundant for this purpose.
The shortest distance between two nodes connected by a semi-triangular edge is
not along the direct path; a shortcut via an indirect path composed of
triangular edges must exist. The subgraph composed of only the triangular
edges, the distance backbone, thus captures all shortest-path phenomena on the
network [3, 4, 11]. Moreover, the distance backbone of a weighted (directed or
undirected) graph with positive edge weights is the smallest subgraph that
preserves all paths of minimal length between every pair of nodes [1, 3]
222Triangular edges are sufficient to compute all shortest distances, but when
there are multiple paths of equal length between a pair of nodes, it is
possible to remove some backbone edges or paths and still preserve all
shortest distances (but not all shortest paths) in what is known as a
transitive reduction [3]. To preserve all possible paths of minimal length,
the entire distance backbone is strictly necessary..

Because there are various possibilities for how to aggregate edge weights to
compute a path length, there are various corresponding distance backbones [8,
3, 11]. The most straightforward of these computes path length as the sum of
edge weights. In the distance closure framework, it is called the _metric_
backbone because it derives from the standard triangle inequality of metric
spaces [1, 4]: an edge of weight $d_{i,j}$ between nodes $x_{i}$ and $x_{j}$
is removed in the graph’s metric backbone if and only if it violates the
standard triangle inequality for some intermediary node $x_{k}$, that is, if
and only if $d_{i,j}>d^{\mathcal{D}}_{i,k}+d^{\mathcal{D}}_{k,j}$, where
$d^{\mathcal{D}}_{i,k}$ and $d^{\mathcal{D}}_{k,j}$ are edge weights in the
distance closure with respect to $\mathcal{D}=(\min,+,[0,\infty])$ (cf.
equation 3.2 of [3]).

The metric backbone as a sparsification technique has been shown to preserve
spreading dynamics and community structure in various application domains
including social networks [4], brain networks [12, 13, 14], protein-protein
interaction networks in disease [15], epidemic spread [4], and many others
[3]. The backbone generalizes the union of all shortest paths graph (which has
the same graph structure as the metric backbone) studied in [2, 5, 16] and
provides additional algebraic grounding for redundancy analysis in networks.
Indeed, the backbone framework, as discussed above, introduces the concept of
semi-triangular edges [1] that is useful in characterizing the redundancy and
robustness of shortest paths [3]. Semi-triangular edges can be ranked by their
distortion, or the ratio between the direct and shortest paths between the
nodes they connect. These edges and their properties are useful for
recommendation and link prediction [8] and can be used to improve epidemic
spread predictions [17]. Furthermore, by framing shortest-path distances as a
result of generalized triangle inequalities in metric spaces, the methodology
of distance closures and backbones provides a unifying framework for studying
different ways to compute distances on networks, that is, ways to quantify
indirect multivariate associations, such as the $\max$ measure of path length,
considered next.

Aggregating edge weights along a path using the $\max$ function instead of
summation results in the sparser ultrametric backbone [3]. In this case, a
path’s length is determined solely by the weight of its most costly edge, and
the shortest distance from one node to another is, as always, given by the
smallest length of all the paths that connect them [3, 11]. Thus the
ultrametric backbone removes an edge if its endpoints are connected by a path
composed of smaller edges.

Following [8, 11], we define the ultrametric backbone in Definition 1.1. The
general formulation of distance backbones, of which this is a special case, is
provided in the appendix.

######  Definition 1.1 (ultrametric backbone).

The _ultrametric backbone_ $U=(X,B^{\max})$ of a distance graph $G=(X,D)$ is
the subgraph formed by the edges of $G$ that have invariant weight under
ultrametric closure $G^{\mathcal{U}}$ where
$\mathcal{U}=(\min,\max,[0,\infty])$.

From the definition of the ultrametric closure [8], the edges retained in the
ultrametric backbone are precisely the edges $(x_{i},x_{j})$ satisfying
$d_{i,j}=d^{\mathcal{U}}_{i,j}$ where

$d^{\mathcal{U}}_{i,j}=\min_{\begin{subarray}{c}\pi\text{ is a path from}\\\
\text{$x_{i}$ to $x_{j}$ in
}G_{D}\end{subarray}}\quad\max_{(x_{k},x_{l})\in\pi}d_{k,l}.$ (1)

In other words, the ultrametric backbone $U=(X,B^{\max})$ of $G=(X,D)$ is the
subgraph obtained by removing an edge $d_{i,j}$ from $G$ (i.e., setting
$b^{\text{max}}_{i,j}=\infty$) if and only if there exists a path $\pi$ in $G$
from $x_{i}$ to $x_{j}$ in which every edge of $\pi$ has weight strictly less
than $d_{i,j}$.

Because the maximum edge weight along a path is never more than the sum of
edge weights along that path (assuming positive edge weights), a graph’s
ultrametric backbone is always a subgraph of its metric backbone [11].
Compared to the metric backbone, the ultrametric backbone places more emphasis
on the highest cost edges in a path. As such, its most natural applications
concern processes in which bottlenecks dominate. For example, in package
delivery, the maximum number of items that can be delivered in one trip along
a given route is determined by the leg of the journey on which the fewest
number of items can be taken. In this example, the cost is inversely related
to the maximum item capacity. Indeed it is often the case that transforming
edge weights between a distance space (cost) and a proximity space (e.g.,
normalized item capacity) is conceptually and analytically beneficial333For
instance, the minimum distance path length operator and the maximum distance
edge weight operator in distance space correspond to the maximum proximity
path length operator and minimum proximity edge weight operators in proximity
space, respectively. When using the maximum proximity path length operator,
the minimum proximity edge weight operator is the only operator consistent
with De Morgan’s laws, meaning it is the only complementary operator that can
be used to form a fuzzy logic[8]. Thus, in distance space, taking a path’s
length to be the maximum of its edge weights yields the only algebraic
structure for computing shortest paths that admits a consistent notion of
logical negation.. We have formally described this connection in previous work
[8, 3], which we briefly review in the appendix.

It is important to emphasize that neither the metric backbone nor the
ultrametric backbone of a connected undirected graph is equivalent to a
minimum spanning tree (MST), which is a minimum-weight subgraph that connects
all vertices. This is easily verified by considering the complete graph on
three vertices with equal edge weights. In this case, both the metric and
ultrametric backbones are equal to the original graph, and hence are not
trees. In contrast, any MST of this graph is a two-path. In the directed case,
MSTs are not defined, though two prominent generalizations exist: minimum
equivalent graphs, and minimum spanning arborescences (see, e.g., [18, 19, 20,
21, 22]). A minimum equivalent graph is a reachability-preserving subgraph of
minimum (summed) weight, and a minimum spanning arborescence (at a root node
$x_{r}$) is a directed acyclic graph rooted at $x_{r}$ that preserves
reachability from $x_{r}$ to all other nodes (except $x_{r}$ itself) and is of
minimal weight444We note that here, reachability refers to whether or not a
path exists between two nodes and does not consider the length of that path.
Thus, a subgraph may preserve reachability but not distances.. Neither
subgraph is equal to the metric or ultrametric backbone, in general, as is
easily verified by, again, considering the complete directed graph on three
vertices with equal edge weights.

Nevertheless, there are similarities between the concept of a graph backbone
and various minimum spanning subgraphs. The results presented here formalizes
the connection between the ultrametric backbone and MSTs in undirected graphs.
Further, we demonstrate that the ultrametric backbone provides a distinct
approach to generalizing the concept of an MST to directed graphs.

##  2 Results

###  2.1 Undirected graphs

The main result of this section is that the ultrametric backbone of a
positively edge-weighted undirected graph is the union of all minimal spanning
forests. This result follows immediately from the special case of connected
graphs, which is formalized in Theorem 2.4. This theorem relies on a few
Lemmas, the first of which is a well-known property of MSTs.

######  Lemma 2.1 (Cycle Property of MSTs).

Let $G$ be a connected, distance-weighted, undirected graph. For any cycle
$\sigma$ in $G$, if $\sigma$ has an edge $d_{i,j}$ larger than all other edges
in $\sigma$, then $d_{i,j}$ is not part of any MST of $G$.

Lemma 2.1 is a standard result in introductory graph theory. A simple proof by
contradiction is given here.

###### Proof of Lemma 2.1.

Assume, by way of contradiction, that a cycle $\sigma$ of edges in $G=(X,D)$
has an edge $d_{i,j}$ larger than the weight of any other edge in $\sigma$ and
that $T=(X,D_{T})$ is an MST of $G$ in which the edge $(d_{T})_{i,j}$ of $T$
corresponds to an edge $d_{i,j}$. Removing $d_{i,j}$ from $T$ yields two
disconnected trees covering the node set $X$: $T_{1}=(X_{1},D_{1})$ and
$T_{2}=(X_{2},D_{2})$ with $x_{i}$ in $X_{1}$ and $x_{j}$ in $X_{2}$. The path
obtained from the cycle $\sigma$ by removing the edge $d_{i,j}$ connects
$x_{i}$ and $x_{j}$ in $G$. Because this path connects $x_{i}\in X_{1}$ and
$x_{j}\in X_{2}$, it must contain an edge $d_{k.l}$ that is strictly smaller
than $d_{i,j}$ (by the contradiction assumption) with $x_{k}$ in $X_{1}$ and
$x_{l}$ in $X_{2}$. Therefore, the graph $T^{\prime}$ on $X$ with edges
$(d_{T^{\prime}})_{i,j}=\min\\{(d_{1})_{i,j},(d_{2})_{i,j}\\}$ for
$(i,j)\neq(k,l)$ and $(d_{T^{\prime}})_{k,l}=d_{k,l}$ is a spanning tree of
$G$ with weight strictly less than the weight of $T$, contradicting the
assumption that $T$ is an MST. ∎

From this result and elementary facts about the ultrametric backbone, it
follows that every MST is a subgraph of the ultrametric backbone, as stated in
Lemma 2.2.

######  Lemma 2.2.

Let $G=(X,D)$ be a connected, weighted, undirected graph with positive edge
weights and ultrametric backbone $U=(X,B^{\max})$. Any MST $T$ is a subgraph
of $U$.

###### Proof of Lemma 2.2.

It suffices to show that every edge removed in $U$ is also removed in any MST.
Consider $(i,j)$ such that $d_{i,j}<\infty$ is an edge (of $G$), but
$b^{\max}_{i,j}=\infty$ is not an edge of $U$ (in the case $G=U$, the result
holds trivially). Because $b^{\max}_{i,j}=\infty$, it follows immediately from
Definition 1.1 that $d_{i,j}$ belongs to a cycle in $G$ whose other edges are
strictly smaller. By Lemma 2.1 this edge does not belong to any MST. ∎

The counterpart to Lemma 2.2 is Lemma 2.3, which states that every edge of the
ultrametric backbone belongs to at least one MST. Essentially, the result
follows from two facts. The first fact is that for any edge $d_{i,j}$
belonging to the ultrametric backbone and any path $\pi$ connecting $x_{i}$ to
$x_{j}$ that does not contain $d_{i,j}$, there is at least one edge $d_{k,l}$
in $\pi$ with $d_{i,j}\leq d_{k,l}$. The second fact is is that $\pi$ and
$d_{i,j}$ together form a cycle, so replacing $d_{k,l}$ with $d_{i,j}$ results
in an alternate path connecting the nodes in $\pi$ (with an equal or lesser
edge weight sum). Such an operation cannot introduce cycles if $\pi$ is
contained in an MST because removal of any edge participating in the
introduced cycles would produce a strictly lower-weight connected graph. The
formalization of this reasoning gives rise to the proof of Lemma 2.3.

######  Lemma 2.3.

Let $G=(X,D)$ be a connected, weighted, undirected graph with positive edge
weights and ultrametric backbone $U=(X,B^{\max})$. For any edge
$b^{\max}_{i,j}$ of the ultrametric backbone, there exists an MST of $G$
containing the corresponding edge $d_{i,j}$.

###### Proof of Lemma 2.3.

Consider an arbitrary MST $T=(X,D_{T})$ of $G$ and an arbitrary edge
$b^{\max}_{i,j}<\infty$ of the ultrametric backbone $U$ of $G$. If
$(d_{T})_{i,j}$ is an edge of $T$, then the Lemma holds in this case.
Otherwise, we seek to construct an alternate MST $T^{\prime}$ that contains
$(d_{T^{\prime}})_{i,j}$ as an edge. In this case, $x_{i}$ must be connected
to $x_{j}$ in $T$ via a path $\pi$ that does not contain $d_{i,j}$. Because
$b^{\max}_{i,j}$ is an edge of $U$, $\pi$ must not be composed of edges whose
weights are all strictly smaller than $d_{i,j}$. That is, $\pi$ contains an
edge $d_{k,l}$ with $d_{k,l}\geq d_{i,j}$. We construct the graph
$T^{\prime}\equiv(X,D_{T^{\prime}})$ from $T$ by removing the edge between
$x_{k}$ and $x_{l}$ and inserting the edge between $x_{i}$ and $x_{j}$. The
altered graph $T^{\prime}$ remains connected because the path $\pi^{\prime}$
formed by replacing $d_{k,l}$ by $d_{i,j}$ in $\pi$ connects $x_{k}$ to
$x_{l}$ in $T^{\prime}$. Furthermore, because $d_{k,l}\geq d_{i,j}$, the
weight of $T^{\prime}$ is not larger than that of $T$. From this fact and the
connectedness of $T^{\prime}$, it follows that $T^{\prime}$ must be a tree of
weight equal to the weight of $T$ (i.e., $d_{k,l}=d_{i,j}$); otherwise
$T^{\prime}$ provides a counterexample to the assumption that $T$ is an MST.
Therefore, either $T$ or $T^{\prime}$ is an MST of $G$ with edge $d_{i,j}$. ∎

The main result of this section, which follows immediately from Lemmas 2.2 and
2.3, is that the ultrametric backbone of a connected undirected graph with
positive edge weights is the exactly equal to the (non-disjoint) union of that
graph’s MSTs. This result is formally stated as Theorem 2.4.

######  Theorem 2.4.

Let $G=(X,D)$ be a connected, weighted, undirected graph with positive edge
weights and ultrametric backbone $U=(X,B^{\max})$, and let $\mathcal{T}$ be
the set of all MSTs of $G$. Then $U=\bigcup_{T\in\mathcal{T}}T$ is the (non-
disjoint) graph union of all MSTs.

Theorem 2.4 extends in a straightforward way to unconnected graphs by
considering minimum spanning forests (a minimum spanning forest of a graph $G$
consists of one MST from each component of $G$). Applying Theorem 2.4 to each
component of a disconnected graph immediately gives rise to Corollary 2.4.1.

######  Corollary 2.4.1.

Let $G$ be a weighted undirected graph with positive edge weights and
ultrametric backbone $U$, and let $\mathcal{F}$ be the set of all minimum
spanning forests of $G$. Then $U=\bigcup_{F\in\mathcal{F}}F$ is the (non-
disjoint) graph union of all minimum spanning forests.

Corollary 2.4.1 is analogous to the fact that the metric backbone is the union
of all shortest path trees as described in the introduction [2, 3].

###  2.2 Directed graphs

This section demonstrates, by way of counterexample, that Theorem 2.4 does not
generalize to the case of directed graphs, suggesting that the directed
ultrametric backbone extends the concept of MSTs to directed graphs in a
manner distinct from traditional constructions.

######  Remark 2.5.

There exists a weighted directed graph $G$ with positive edge weights and
ultrametric backbone $U$ such that the union $\mathcal{S}$ of all minimum
equivalent graphs of $G$ satisfies i) $\mathcal{S}$ lacks an edge belonging to
$U$ and ii) $\mathcal{S}$ has an edge not in $U$.

######  Remark 2.6.

There exists a weighted directed graph $G$ with positive edge weights and
ultrametric backbone $U$ such that the union $\mathcal{A}$ of all minimum
spanning arborescences of $G$ satisfies i) that $\mathcal{A}$ lacks an edge
belonging to $U$ and ii) that $\mathcal{A}$ has an edge not in $U$.

These remarks are demonstrated in Figure 1. The original graph, $G$, is
depicted in Figure 1a. The ultrametric backbone, $U$, of this graph is
depicted in Figure 1b. In this example, $G$ has a unique minimum equivalent
graph, depicted in Figure 1c. The edge $d_{2,3}=5$ is required to preserve
$\max-\min$ shortest paths and thus is included in the ultrametric backbone.
This edge, however, is absent in the minimum equivalent graph. On the other
hand, the edge $d_{2,4}=6$ is present in the minimum equivalent graph but is
redundant for $\max-\min$ shortest paths and therefore not present in the
ultrametric backbone. Thus, the relationship between these two graphs is as
described in Remark 2.5. This same example network demonstrates the
correctness of Remark 2.6 as well, as shown in Figure 1d, which depicts the
minimum spanning arborescences rooted at each node. The edge $d_{2,3}$ is
absent in all minimum spanning arborescences, but is required in the
ultrametric backbone to preserve $\max-\min$ shortest paths; on the other
hand, the edge $d_{2,4}$ is not in the ultrametric backbone (it is redundant
for $\max-\min$ shortest paths), but it is present in two of the minimum
spanning arborescences.

Figure 1: The ultrametric backbone is distinct from unions of MST analogs in
directed graphs. (a) An example distance graph with thicker edges
corresponding to smaller distance weights. (b) The ultrametric backbone is
shown with edge weights omitted for visual clarity. Edge $d_{2,4}$ is removed,
as indicated by the red dashes; it is redundant for $\max-\min$ shortest paths
because it breaks the $\max-\min$ transitivity. (c) A minimum equivalent graph
is shown, which in this example is unique. Note that it is distinct from the
ultrametric backbone and does not preserve the shortest $\max-\min$ path from
$x_{2}$ to $x_{4}$. (d) Five (in this case, unique) minimum spanning
arborescences with the root node filled in with black are shown. The red
dashed line indicates an edge, $d_{2,3}$, that is not in any minimum spanning
arborescence, but is in the ultrametric backbone and required for $\max-\min$
shortest paths (its weight increases from $5$ to $6$). The blue edge,
$d_{2,4}$, is present in the union of these five graphs, but is redundant for
$\max-\min$ shortest paths and therefore is not in the ultrametric backbone.

A crucial property of the ultrametric backbone that gives rise to Lemma 2.2 in
the undirected case is that every edge removed in the undirected ultrametric
backbone belongs to a cycle. Notably, this property does not hold in directed
graphs, where the removed edges need not participate in a cycle. Rather, all
that is required is that an alternate path exists between the parent and child
nodes of the removed directed edge. The failure of this property to
generalize, however, is not sufficient to explain the counterexample of Figure
1: The edge $d_{2,3}$ participates in a cycle in which its weight is strictly
larger than that of all others (i.e., $x_{1}\rightarrow x_{2}\rightarrow
x_{3}$). Rather, because $d_{2,3}$ is maximal in the cycle $x_{1}\rightarrow
x_{2}\rightarrow x_{3}$, this counterexample illustrates the failure of Lemma
2.1 to generalize to minimum equivalent graphs and minimum spanning
arborescences.

We note that the metric backbone is equivalent to the union of of all minimum
spanning arborescences because it can be constructed as the union of all
shortest paths [11].

##  3 Discussion

The main result of this work, Theorem 2.4 and its corollary, is that the
ultrametric backbone of any positively weighted undirected graph is the union
of all MSTs (or forests, if the graph is not connected). This is surprising
because the weight of a spanning tree is defined to be the sum of its edges,
but the ultrametric backbone can be defined and computed without any
summation. The result is all the more surprising because it does not
generalize to natural analogs of MSTs for directed graphs. This suggests that
the ultrametric backbone provides a new way to extend the concept of an MST to
directed graphs.

The ultrametric backbone may be especially useful when considering MSTs of
graphs in which edge weights have relatively high uncertainty. By binning or
coarse-graining edge weights and computing the ultrametric backbone, the
“true” MST is guaranteed to be retained as a subgraph. Furthermore,
potentially relevant edges that are marginally excluded in an MST are not
forcibly discarded in a coarse-grained ultrametric backbone approach. This is
because one is not forced to differentiate between edges with statistically
equal weights when computing the ultrametric backbone.

The correspondence between the ultrametric backbone and the MSTs suggests an
approach to finding MSTs that may offer computational advantages when edge
summation is numerically difficult, for example when edge weights span many
orders of magnitude or when differences between edge weights are small but
significant. In particular, any MST of a graph is also an MST of that graph’s
ultrametric backbone, which may be computed without summing edges, using edge
ranks only. Indeed, this property of MSTs is exploited in Kruskal’s algorithm
for finding minimum spanning forests [23]. In the special case when the MST is
unique (for example, if all edge weights are distinct), it is equal to the
ultrametric backbone.

Theorem 2.4 emphasizes the similarities between the ultrametric backbone and
MSTs in undirected weighted graphs. By extension, this comparison underscores
the differences between other distance backbones (most notably the metric
backbone) and MSTs. The metric backbone of an undirected graph necessarily
contains its ultrametric backbone as a subgraph, which in turn contains all
minimum spanning forests. Thus, the metric backbone is a subgraph that
contains all MSTs, and which may, in general, contain additional edges in
order to preserve all geodesics. In directed graphs, this difference becomes
even more dramatically evident.

In directed graphs, the ultrametric backbone provides a natural extension of
MSTs that is distinct from minimum equivalent graphs, minimum spanning
arborescences, and their unions. The ultrametric backbone is computationally
simple to compute and has the advantage of avoiding technical difficulties
surrounding reachability or requirements of strong connectedness that other
generalizations must contend with. Intuitively, it generalizes MSTs to
directed graphs in a manner that emphasizes the removal of weakest links that
occurs in the undirected case. The results presented here suggest that the
ultrametric backbone (of a directed or undirected graph) may serve as an
alternative or supplement to various minimum spanning subgraphs when analyzing
network structure. This conclusion motivates further study regarding the
dynamical properties of the ultrametric backbone in various contexts.

## Acknowledgments

This was was funded by the NIH National Library of Medicine Program grant
01LM011945-01 and the Fundação para a Ciência e a Tecnologia grant
2022.09122.PTDC (https: //doi.org/10.54499/2022.09122.PTDC) to LMR.

##  4 Conflicts of Interest

The authors declare no conflicts of interest.

##  Appendix A General distance closure and backbone

This section provides a summary of the distance closure framework of [8] and
the distance backbone framework of [11].

We begin with preliminary definitions from fuzzy logic, which motivated the
work of [8].

######  Definition A.1 (T-norm).

A _triangular norm_ (abbreviated T-norm)
$\wedge:[0,1]\times[0,1]\rightarrow[0,1]$ is an associative, commutative, and
non-decreasing binary operation on the closed unit interval that has identity
$1$, i.e., $x\wedge 1=x$ for all $x\in[0,1]$.

######  Definition A.2 (T-conorm).

A _triangular conorm_ (abbreviated T-conorm)
$\vee:[0,1]\times[0,1]\rightarrow[0,1]$ is an associative, commutative, and
non-decreasing binary operation on the closed unit interval that has identity
$0$, i.e., $x\vee 0=x$ for all $x\in[0,1]$.

If, for a T-norm $\wedge$ and T-conorm $\vee$, there exists a bijective
involution $\neg$ on $[0,1]$ that satisfies the De Morgan property $a\vee
b=\neg(\neg a\wedge\neg b)$ for all $a,b\in[0,1]$, then $\wedge$ and $\vee$
are dual and form a fuzzy logic.

Note that every T-norm and T-conorm (whether dual or not) form a monoid on
$[0,1]$ (i.e., $(\wedge,[0,1])$ and $(\vee,[0,1])$ are monoids). Pairs of
monoids on the same underlying set, and isomorphisms between these pairs, play
an important role in [8], so we define them carefully here:

######  Definition A.3 (monoid pair).

A _monoid pair_ is an ordered pair of monoids that share the same underlying
set, written $(*,+,M)$. An _isomorphism of monoid pairs_ from $(*,+,M)$ to
$(\cdot,\star,N)$ is a function $\varphi:M\rightarrow N$ that is an
isomorphism from $(*,M)$ to $(\cdot,N)$ and from $(+,M)$ to $(\star,N)$.

Note that a monoid pair is quite general, as the two operations need not share
anything in common other than their underlying set.

The special case of a monoid pair formed from a T-norm and T-conorm is of
particular interest.

######  Definition A.4 (proximity structure).

A monoid pair $(\wedge,\vee,M)$ with first operation ($\wedge$) a T-norm,
second operation $\vee$ a T-conorm, and underlying set $M=[0,1]$ is called a
_proximity structure_. (This is called algebraic structure $I$ in [8].)

We now define analogous structures for distance spaces, rather than for
proximity spaces.

######  Definition A.5 (TD-norm).

A _triangular distance norm_ (abbreviated TD-norm)
$\oplus:[0,\infty]\times[0,\infty]\rightarrow[0,\infty]$ is an associative,
commutative, and non-decreasing binary operation on the closed unit interval
that has identity $0$, i.e., $x\oplus 0=x$ for all $x\in[0,\infty]$.

######  Definition A.6 (TD-conorm).

A _triangular distance conorm_ (abbreviated TD-conorm)
$\otimes:[0,\infty]\times[0,\infty]\rightarrow[0,\infty]$ is an associative,
commutative, and non-decreasing binary operation on the closed unit interval
that has identity $\infty$, i.e., $x\otimes\infty=x$ for all $x\in[0,\infty]$.

Note that in [8], the functions $f$ and $g$ are introduced to define TD-norms
and TD-conorms. In our notation, $f(a,b)=a\oplus b$ and $g(a,b)=a\otimes b$.

######  Definition A.7 (distance structure).

A monoid pair $(\oplus,\otimes,M)$ with first operation $\oplus$ a TD-norm,
second operation $\otimes$ a TD-conorm, and underlying set $M=[0,\infty]$ is
called a _distance structure_. (This is called algebraic structure $II$ in
[8].)

In [8], it is highlighted that for any proximity structure $\mathcal{P}$, any
monotonically decreasing bijection $\varphi:[0,1]\rightarrow[0,\infty]$ can be
interpreted as an isomorphism of monoid pairs, thereby inducing a
corresponding distance structure $\mathcal{D}$. This allows for convenient
extension of earlier results on proximity spaces and fuzzy logic relations
(e.g., from [10]) to distance graphs. In particular, [8] focuses on the
construction of graph closures.

A proximity graph $G_{P}=(X,P)$ is a weighted graph with edge weights
$p_{i,j}$ taken from $[0,1]$, while a distance graph $G_{D}$ is a weighted
graph with edge weights $d_{i,j}$ taken from $[0,\infty]$. The proximity
closure $G_{P}^{\mathcal{P}}$ of a proximity graph of $G_{P}$ with respect to
a proximity structure $\mathcal{P}=(\wedge,\vee,[0,1]$ has the same node set
and is a complete graph. The edge weight of the edge $(x_{i},x_{j})$ in
$G_{P}^{\mathcal{P}}$ is denoted $p^{\mathcal{P}}_{i,j}$ given by

$p^{\mathcal{P}}_{i,j}=\bigwedge_{\begin{subarray}{c}\pi\text{ is a path
from}\\\ \text{$x_{i}$ to $x_{j}$ in
}G_{P}\end{subarray}}\quad\bigvee_{(x_{k},x_{l})\in\pi}p_{k,l}.$ (2)

If no path exists between $x_{i}$ and $x_{j}$ in $G_{P}$, the weight of the
corresponding edge is $0$ in $G_{P}^{\mathcal{P}}$.

By application of any monotonically decreasing bijection
$\varphi:[0,1]\rightarrow[0,\infty]$, and imposition of the homomorphism
property, an analogous structure, the distance closure $G_{D}^{\mathcal{D}}$
of the distance graph $G_{D}$ with respect to
$\mathcal{D}=(\otimes,\oplus,[0,\infty])$ corresponding to $G_{\mathcal{P}}$
under $\varphi$ can be constructed. The edge weight of the edge
$(x_{i},x_{j})$ in $G_{D}^{\mathcal{D}}$ is given by

$d^{\mathcal{D}}_{i,j}=\bigoplus_{\begin{subarray}{c}\pi\text{ is a path
from}\\\ \text{$x_{i}$ to $x_{j}$ in
}G_{D}\end{subarray}}\quad\bigotimes_{(x_{k},x_{l})\in\pi}d_{k,l}.$ (3)

If no path exists between $x_{i}$ and $x_{j}$ in $G_{\mathcal{D}}$, the weight
of the corresponding edge is $\infty$ in $G_{D}^{\mathcal{D}}$.

As proved in [8] for the case of undirected graphs and in [11] for the case of
directed graphs, the computation of the closure graph commutes with
application of $\varphi$ to the edge weights.

In this framework, the distance backbone of a distance graph $G_{D}$ with
respect to $\mathcal{D}$ is defined for $a\oplus b=\min(a,b)$ according to [3,
4, 11].

######  Definition A.8 (distance backbone).

The _distance backbone_ of $G_{D}=(X,D)$ with respect to a distance structure
$\mathcal{D}=(\min,\otimes,[0,\infty])$ is the subgraph $(X,B^{\otimes})$
formed by the edges of $G_{D}$ that have invariant weight under closure, i.e.,
edges $(x_{i},x_{j})$ satisfying $d_{i,j}=d^{\mathcal{D}}_{i,j}$.

For example, in the case of the metric backbone, $a\oplus b=\min(a,b)$ and
$a\otimes b=a+b$, while in the case of the ultrametric backbone, $a\oplus
b=\min(a,b)$ and $a\otimes b=\max(a,b)$.

##  Appendix B Summary of notation used in main text

In this appendix, we present Table 1, which summarizes the mathematical
notation used in the main text.

Symbol |  Description
---|---
$G=(X,D)$ |  A distance graph with positive edge weights, which may be directed or not, depending on context.
$X$ |  The vertex set of a graph.
$x_{i}$ |  A vertex in a distance graph.
$D$ |  The edges of a distance graph. When clear from context, $D=D(X,X)$ refers to the adjacency matrix of the graph, with non-edges represented by infinite entries.
$d_{i,j}$ |  An edge of a distance graph represented by its indexed value in the adjacency matrix. Writing $d_{i,j}=\infty$ is equivalent to noting that the graph does not have an edge between $x_{i}$ and $x_{j}$ (or from $x_{i}$ to $x_{j}$ in the directed case).
$\pi$ |  Indicates a path in a graph.
$T$, $T^{\prime}$, etc. |  Distance graphs; the letter $T$ is used to indicate that the graph has been shown (or will be shown) to be a tree.
$\mathcal{T}$ |  The set of all minimum spanning trees of a distance graph.
$F$ |  A distance graph; the letter $F$ is used to indicate that the graph is a minimum spanning forest.
$\mathcal{F}$ |  The set of all minimum spanning forests of a distance graph.
$\mathcal{S}$ |  The union of all minimum equivalent graphs of a directed distance graph.
$\mathcal{A}$ |  The union of all minimum spanning arboresceences (at all roots) of a directed distance graph.
$\mathcal{D}$ |  A distance structure; an algebraic structure that determines how distances between nodes in a distance graph are computed. It consists two monoid operations, $\oplus$ and $\otimes$, on the extended real numbers (see below).
$\oplus$ |  The TD-norm operator used to aggregates edge weights to compute a path length. $\oplus:[0,\infty]\times[0,\infty]\rightarrow[0,\infty]$ must be associative, commutative, and non-decreasing with identity element $0$.
$\otimes$ |  The TD-conorm operator used to aggregate path lengths to compute node-to-node distance. Here, set as $\otimes\equiv\min$ except when noted otherwise. $\otimes:[0,\infty]\times[0,\infty]\rightarrow[0,\infty]$ must be associative, commutative, and non-decreasing with identity element $\infty$.
$\mathcal{U}$ |  The ultrametric distance structure with $\oplus=\max$ and $\otimes=\min$ computes the distance between nodes as the length of the shortest path (or paths), where the length of a path is given by the weight of its largest edge.
$G^{\mathcal{D}}$ |  The distance closure of the graph $G$ with respect to the distance structure $\mathcal{D}$. Every (strongly) connected component of $G$ is a complete graph in $G^{\mathcal{D}}$ with an edge weight $d^{\mathcal{D}}_{i,j}$ equal to the distance between $x_{i}$ and $x_{j}$ in $G$ computed using $\mathcal{D}$.
$U=(X,B^{\max})$ |  The ultrametric backbone of a graph $G$. This graph consists of exactly those edges $d_{i,j}$ whose weight is conserved in the distance closure constructed using the distance structure $\mathcal{U}$ (see above). That is, its edges are shortest paths in $G$ where a path’s length equals the weight of its largest edge. Edges are denoted using $b^{\max}_{i,j}$.
Table 1: Key notation used in the main text. Additional notation is used and
defined in Appendix A.

## References

  * [1] Luis Rocha.  Semi-metric behavior in document networks and its application to recommendation systems.  Soft Computing Agents: A New Perspective for Dynamic Information Systems, pages 137–163, 10 2003.
  * [2] Piet Van Mieghem and Stijn van Langen.  Influence of the link weight structure on the shortest path.  Phys. Rev. E, 71:056113, May 2005.
  * [3] Tiago Simas, Rion Brattig Correia, and Luis M Rocha.  The distance backbone of complex networks.  Journal of Complex Networks, 9(6):cnab021, December 2021.
  * [4] Rion Brattig Correia, Alain Barrat, and Luis M. Rocha.  Contact networks have small metric backbones that maintain community structure and are primary transmission subgraphs.  PLOS Computational Biology, 19(2):1–23, 02 2023.
  * [5] Piet Van Mieghem and Serena M. Magdalena.  Phase transition in the link weight structure of networks.  Phys. Rev. E, 72:056138, Nov 2005.
  * [6] Ernesto Estrada and Naomichi Hatano.  Resistance distance, information centrality, node vulnerability and vibrations in complex networks.  In Network science, pages 13–29. Springer, 2010.
  * [7] Grant Silver, Meisam Akbarzadeh, and Ernesto Estrada.  Tuned communicability metrics in networks. the case of alternative routes for urban traffic.  Chaos, Solitons & Fractals, 116:402–413, 2018.
  * [8] Tiago Simas and Luis M. Rocha.  Distance closures on complex networks.  Network Science, 3(2):227–268, June 2015.  Publisher: Cambridge University Press.
  * [9] K. Menger.  Statistical metrics.  PNAS, 28, 1942.
  * [10] G.J. Klir and B. Yuan.  Fuzzy sets and fuzzy logic, theory and applications.  Prentice Hall PTR, 1995.
  * [11] Felipe Xavier Costa, Rion Brattig Correia, and Luis M. Rocha.  The distance backbone of directed networks.  In Hocine Cherifi, Rosario Nunzio Mantegna, Luis M. Rocha, Chantal Cherifi, and Salvatore Micciche, editors, Complex Networks and Their Applications XI, pages 135–147, Cham, 2023. Springer International Publishing.
  * [12] Tiago Manuel Louro Machado Simas.  STOCHASTIC MODELS AND TRANSITIVITY IN COMPLEX NETWORKS.  PhD thesis, Indiana University, 2012.
  * [13] John Suckling, Tiago Simas, Shayanti Chattopadhyay, Roger Tait, Li Su, Guy Williams, James B Rowe, and John T O’Brien.  A winding road: Alzheimer’s disease increases circuitous functional connectivity pathways.  Frontiers in Computational Neuroscience, 9:140, 2015.
  * [14] Tiago Simas, Shayanti Chattopadhyay, Cindy Hagan, Prantik Kundu, Ameera Patel, Rosemary Holt, Dorothea Floris, Julia Graham, Cinly Ooi, Roger Tait, et al.  Semi-metric topology of the human connectome: sensitivity and specificity to autism and major depressive disorder.  PLoS One, 10(8):e0136388, 2015.
  * [15] Rion Brattig Correia, Joana M Almeida, Margot J Wyrwoll, Irene Julca, Daniel Sobral, Chandra Shekhar Misra, Leonardo G Guilgur, Hans-Christian Schuppe, Neide Silva, Pedro Prudêncio, et al.  The conserved transcriptional program of metazoan male germ cells uncovers ancient origins of human infertility.  bioRxiv, pages 2022–03, 2022.
  * [16] Piet Van Mieghem and Huijuan Wang.  The observable part of a network.  IEEE/ACM Transactions on Networking, 17(1):93–105, 2009.
  * [17] David Soriano Paños, Felipe Xavier Costa, and Luis M. Rocha.  Semi-metric topology characterizes epidemic spreading on complex networks, November 2023.  arXiv:2311.14817 [physics].
  * [18] A. V. Aho, M. R. Garey, and J. D. Ullman.  The Transitive Reduction of a Directed Graph.  SIAM Journal on Computing, 1(2):131–137, June 1972.  Publisher: Society for Industrial and Applied Mathematics.
  * [19] Harry T. Hsu.  An Algorithm for Finding a Minimal Equivalent Graph of a Digraph.  Journal of the ACM, 22(1):11–16, January 1975.
  * [20] Jørgen Bang-Jensen and Anders Yeo.  The minimum spanning strong subdigraph problem is fixed parameter tractable.  Discrete Applied Mathematics, 156(15):2924–2929, August 2008.
  * [21] P. M. Camerini.  The min-max spanning tree problem and some extensions.  Information Processing Letters, 7(1):10–14, January 1978.
  * [22] Bernhard Korte and Jens Vygen.  Spanning Trees and Arborescences.  In Bernhard Korte and Jens Vygen, editors, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, pages 133–157. Springer, Berlin, Heidelberg, 2018.
  * [23] Joseph B. Kruskal.  On the shortest spanning subtree of a graph and the traveling salesman problem.  Proceedings of the American Mathematical Society, 7(1):48–50, 1956.


# Control of Vehicle Platoons with Collision Avoidance Using Noncooperative
Differential Games*

Hossein B. Jond1 *This work was supported by SGS, VŠB - Technical University
of Ostrava, Czech Republic, under grant No. SP2023/012 “Parallel processing of
Big Data X”.1Hossein B. Jond is with the Department of Computer Science, VŠB-
Technical University of Ostrava, 708 00 Ostrava-Poruba, Czech Republic
<EMAIL_ADDRESS>
###### Abstract

This paper considers a differential game approach to the predecessor-following
vehicle platoon control problem without and with collision avoidance. In this
approach, each vehicle tries to minimize the performance index (PI) of its
control objective, which is reaching consensual velocity with the predecessor
vehicle while maintaining a small inter-vehicle distance from it. Two
differential games were formulated. The differential game problem for platoon
control without collision avoidance is solved for the open-loop Nash
equilibrium and its associated state trajectories. The second differential
game problem for platoon control with collision avoidance has a non-quadratic
PI, which poses a greater challenge to obtaining its open-loop Nash
equilibrium. Since the exact solution is unavailable, we propose an estimated
Nash strategy approach that is greatly simplified for implementation. An
illustrative example of a vehicle platoon control problem was solved under
both the without and with collision avoidance scenarios. The results showed
the effectiveness of the models and their solutions for both scenarios.

###### Index Terms:

collision avoidance, differential game, Nash equilibrium, vehicle platoon

##  I Introduction

Convoy and platoon group driving are the salient collective behaviors of
connected and automated vehicles on the road [1, 2]. Vehicles in a platoon or
convoy drive at a consensual speed in the direction of the flow of traffic
while maintaining a small inter-vehicle distance from their adjacent vehicles.
In a platoon, we are concerned only with the longitudinally coordinated
control of vehicles moving in the same lane of the road or highway [3, 4]. In
a convoy, both longitudinal and lateral coordination of vehicles over
different lanes is necessary [5, 6].

Platooning is the most studied group behavior of connected and automated
vehicles [7, 8]. Such coordination is achieved by exchanging local information
among the vehicles [9]. Vehicle platoons offer remarkable benefits, as listed
in [1, 10, 8]. Platooning boosts road capacity and decreases fuel consumption
and emissions of pollutants due to the decrease in gaps between vehicles and
the elimination of dispensable changes in speed and aerodynamic drag on the
following vehicles, respectively. Besides, driving safety and passenger
satisfaction are enhanced since detection and actuation times are shorter, and
the small inter-vehicle gaps between vehicles prevent cut-ins by other
vehicles. The most common platooning methods are the Leader-Follower approach
[11], the Behavior-Based Approach [12, 13], and the Virtual Structure approach
[14, 15]. Several other methods were also researched [16, 17, 18].

In the classical optimal control framework, vehicles attempt to acquire a
platoon formation by optimizing a team objective [19]. This framework,
however, is incompatible with automated and autonomous vehicles, which are
supposed to make independent and selfish operational decisions without the
need for human intervention. Game theory provides tools and concepts for
determining the best strategy or action choices for each vehicle with self-
interests and acting selfishly. A vehicle’s interest in a platoon could be to
penalize its relative displacement, velocity, and acceleration errors, taking
its fuel amount into account [20]. The strategic interactions among vehicles
acting independently and selfishly naturally portray a noncooperative game.
Nash equilibrium allows for self-enforcing strategic interactions in a
noncooperative game [21]. Platooning emerges as a result of a Nash equilibrium
[4].

Game-theoretic platoon control has recently attracted increasing interest in
the control community. Some recent reports include platooning at the hubs in a
transportation network as a noncooperative coordination game [22], attacker-
detector game for improving the security of platoons against cyber attacks
[23], platoon formation as a coalitional game [24], and complete and
incomplete information behavioral decision-making in a platoon using
noncooperative game theory [25].

Differential games have been extensively used to address multi-robot systems
formation control [26, 20, 27, 28]. A platoon is a line formation. However,
only a few research studies have utilized differential games for platooning.
In [4], differential games for platooning under the predecessor-following and
two-predecessor-following topologies for platoon control problems with
vehicles governed by single integrator dynamics were solved analytically, and
the closed-form expressions for the open-loop Nash equilibrium were derived.

As the main contribution with respect to [4], this paper considers $i$) a
linearized dynamics model that approximates the longitudinal dynamics of car-
like vehicles and $ii$), collision avoidance. It is shown that a closed-form
solution for the platoon control problem without collision avoidance in the
context of a noncooperative differential game exists. Realizing that a closed-
form solution for the game problem with collision avoidance is not available,
we propose an estimated Nash strategy that is greatly simplified for
implementation under an open-loop information structure. Both solutions’
effectiveness is shown by the simulation studies.

The paper is organized as follows. Section II presents a differential game
model of the platoon control problem without collision avoidance. In Section
III, we derive the open-loop Nash equilibrium and its associated opinion
trajectories. The platoon control problem with collision avoidance is studied
in Section IV. In Section V, the results from previous sections are verified
by simulations. Conclusions and future works are discussed in Section VI.

##  II Differential Game Formulation

We consider a homogeneous platoon of vehicles with the predecessor-following
information topology as depicted in Fig. 1. Each vehicle follows its
predecessor by maintaining a predefined fixed inter-vehicle distance using
unidirectional information acquired directly from onboard sensors or via
vehicle-to-vehicle connections in connected environments. The vehicles are
equipped with cameras that detect their immediate preceding vehicle and laser
scanners for measuring the distances. Suppose that there are $N+1$ vehicles in
the platoon, indexed by $0$ through $N$ where $0$ corresponds to the lead
vehicle and the rest to the following vehicles. The lead vehicle, or simply
the leader, is at the front of the platoon and has a constant velocity. The
following vehicles, or followers, adjust their control input to maintain their
predefined distances from their predecessors.

Figure 1: A homogeneous vehicle platoon with predecessor-following topology.
The corresponding information topology shows that each follower vehicle has
the information of only its predecessor vehicle.

Vehicle dynamics is a nonlinear function of tire friction, rolling resistance,
aerodynamic drag, gravitational force, the engine, the brake system, etc.,
fundamentally challenging theoretical analysis. Simplified nonlinear vehicle
dynamics models have commonly been used to model vehicle longitudinal dynamics
in a platoon. These nonlinear dynamics models govern the engine dynamics,
brake system, and aerodynamic drag of each vehicle. By using the feedback
linearization technique, as shown in [29, 30], these nonlinear dynamics become
linearized, which eases further theoretical analysis.

Let $p_{i}(t)$, $v_{i}(t)$, $a_{i}(t)$, and $u_{i}(t)$ denote the position,
velocity, acceleration, and control input of the $i$th vehicle in the platoon,
respectively. The engine time constant $\tau$ (also called the inertial time-
lag) encompassed by the feedback linearized dynamics is, in reality, different
even for identical vehicles. However, in this work, we consider a homogeneous
platoon of follower vehicles with identical $\tau$. This assumption ensures
that the platoon control problem that will be defined in this paper can be
solved analytically with a closed-form solution. Each follower vehicle
$i\in\\{1,\ldots,N\\}$’s feedback linearized dynamics is given by

$\displaystyle\left\\{\begin{array}[]{lll}\dot{p}_{i}(t)=v_{i}(t)&\\\
\dot{v}_{i}(t)=a_{i}(t)&\\\ \tau\dot{a}_{i}(t)+a_{i}(t)=u_{i}(t)\\\
\end{array}\right.$

or, equivalently, in the following state-space form

$\dot{x}_{i}(t)=Ax_{i}(t)+Bu_{i}(t)$ (1)

where $x_{i}(t)=\begin{bmatrix}p_{i}(t)\\\ v_{i}(t)\\\ a_{i}(t)\end{bmatrix}$,
$A=\begin{bmatrix}0&1&0\\\ 0&0&1\\\ 0&0&-\frac{1}{\tau}\end{bmatrix}$, and
$B=\begin{bmatrix}0\\\ 0\\\ \frac{1}{\tau}\end{bmatrix}$. Note that the leader
is supposed to move with constant velocity, i.e.,
$x_{0}=[p_{0}(t),v_{0},0]^{\top}$, under the steady-state condition, i.e.,
$u_{0}(t)=0$.

Follower vehicles try to maintain the inter-vehicular spacing $d_{i}$ between
themselves and their immediate predecessors. Note that $d_{i}$ can be regarded
as the length of each vehicle appended to it. The control objective is to
ensure all the following vehicles reach consensual velocity with the lead
vehicle while maintaining the predefined constant inter-vehicular spacing from
their predecessors. In other words, the vehicle platoon shown in Fig. 1 for
any given bounded initial states $x_{0}(0)>x_{1}(0)>\cdots>x_{N}(0)$ achieves
the desired platoon if control objectives

$\displaystyle\|x_{i-1}(T)-x_{i}(T)-\hat{d}_{i}\|^{2}\rightarrow 0$ (2)

for all $i\in\\{1,\ldots,N\\}$ are satisfied for a sufficiently large finite
time horizon $T$ and $\hat{d}_{i}=[d_{i},0,0]^{\top}$. Note that although a
homogeneous platoon of vehicles with identical dynamics is considered, the
individual vehicles do not have to necessarily commit to an identical inter-
vehicular spacing policy and can choose their own spacing policies according
to their specifications.

In the context of a differential game, the control objectives (2) are
transformed into PIs, each of which is supposed to be optimized by an
individual vehicle in the platoon or a player in the game. The PI for each
following vehicle $i\in\\{1,\ldots,N\\}$ is defined as

$\displaystyle
J_{i}=\omega_{i}\|x_{i-1}(T)-x_{i}(T)-\hat{d}_{i}\|^{2}+\int_{0}^{T}u_{i}^{2}(t)~{}\mathrm{dt}$
(3)

where $\omega_{i}>0$ is a weighting parameter that penalizes the inter-vehicle
displacement, and vehicles can adjust this parameter taking their personal
interests or other personal factors such as their fuel amount in the tank into
account.

In this paper, we consider the platoon control problem (1) and (3) in the
context of a noncooperative scenario differential game, where the notion of
optimality is Nash equilibrium. A Nash equilibrium is a strategy combination
of all players in a noncooperative game with the property that no one can gain
a lower cost by unilaterally deviating from it.

##  III Open-Loop Nash Equilibrium

In the following theorem, we show the existence of a unique open-loop Nash
equilibrium and then we present closed-form expressions for the equilibrium
actions and their associated state trajectories for the underlying platoon
control problem.

######  Theorem 1.

Consider a platoon of vehicles with the feedback linearized dynamics (1) and
PIs (3). The platoon control problem as a noncooperative differential game
admits a unique open-loop Nash equilibrium given by

$u_{i}(t)=-\sum_{j=1}^{i}\xi_{j}(t)$ (4)

where

$\displaystyle\xi_{i}(t)=-\omega_{i}B^{\top}\mathrm{e}^{(T-t)A^{\top}}\left(I+\omega_{i}\Psi(T)\right)^{-1}\mathrm{e}^{TA}y_{i}(0),$
(5)
$\displaystyle\Psi(t)=\int_{0}^{t}\mathrm{e}^{(t-s)A}BB^{\top}\mathrm{e}^{(t-s)A^{\top}}\mathrm{ds}.$
(6)

The state trajectories associated with the equilibrium actions are given by

$x_{i}(t)=x_{0}(t)-\sum_{j=1}^{i}(y_{j}(t)+\hat{d}_{j})$ (7)

where

$\displaystyle
y_{i}(t)=\left(\mathrm{e}^{tA}-\omega_{i}\Psi(t)\left(I+\omega_{i}\Psi(T)\right)^{-1}\mathrm{e}^{TA}\right)y_{i}(0).$
(8)

###### Proof.

Let $y_{i}(t)=x_{i-1}(t)-x_{i}(t)-\hat{d}_{i}$ and
$\xi_{i}(t)=u_{i-1}(t)-u_{i}(t)$ for all $i\in\\{1,\ldots,N\\}$ where (7) and
(4) are easily verified, respectively.

Vehicle dynamics (1) is then expressed in terms of the new state vector
$y_{i}(t)$ and new control input $\xi_{i}(t)$ as

$\dot{y}_{i}(t)=Ay_{i}(t)+B\xi_{i}(t).$ (9)

Therefore, the platoon control problem as the noncooperative differential game
(1) and (3) reduces to the following optimization

$\displaystyle\min_{\xi_{i}}\mathcal{J}_{i}=\omega_{i}y_{i}^{\top}(T)y_{i}(T)+\int_{0}^{T}\xi_{i}^{2}(t)~{}\mathrm{dt}$

subject to (9).

Define the Hamiltonian for the above minimization

$\displaystyle
H_{i}=\xi_{i}^{2}(t)+\lambda_{i}^{\top}(t)(Ay_{i}(t)+B\xi_{i}(t))$ (10)

for all $i\in\\{1,\ldots,N\\}$ where $\lambda_{i}(t)$ is the costate.
According to Pontryagin’s minimum principle, the necessary conditions for
optimality are $\frac{\partial H_{i}}{\partial\xi_{i}}=0$ and
$\dot{\lambda}_{i}(t)=-\frac{\partial H_{i}}{\partial y_{i}}$. Applying the
necessary conditions on (10) yield

$\displaystyle\xi_{i}(t)=-B^{\top}\lambda_{i}(t),$ (11)
$\displaystyle\dot{\lambda}_{i}(t)=-A^{\top}\lambda_{i}(t),\quad\lambda_{i}(T)=\omega_{i}y_{i}(T)$
(12)

for $i\in\\{1,\ldots,N\\}$.

The solution of (12) is given by

$\displaystyle\lambda_{i}(t)=\mathrm{e}^{(T-t)A^{\top}}\lambda_{i}(T)=\omega_{i}\mathrm{e}^{(T-t)A^{\top}}y_{i}(T).$
(13)

Substituting (11) into (9) and using (13), we have

$\displaystyle\dot{y}_{i}(t)$
$\displaystyle=Ay_{i}(t)-BB^{\top}\lambda_{i}(t)$
$\displaystyle=Ay_{i}(t)-\omega_{i}BB^{\top}\mathrm{e}^{(T-t)A^{\top}}y_{i}(T)$

where its solution is given by

$y_{i}(t)=\mathrm{e}^{tA}y_{i}(0)-\omega_{i}\Psi(t)y_{i}(T)$ (14)

where $\Psi(t)$ is defined in (6). Consider (14) at $T$ as

$y_{i}(T)=\mathrm{e}^{TA}y_{i}(0)-\omega_{i}\Psi(T)y_{i}(T).$ (15)

Equation (15) can be rewritten as

$\left(I+\omega_{i}\Psi(T)\right)y_{i}(T)=\mathrm{e}^{TA}y_{i}(0)$

or

$y_{i}(T)=\left(I+\omega_{i}\Psi(T)\right)^{-1}\mathrm{e}^{TA}y_{i}(0).$ (16)

Note that $y_{i}(T)$ exists for every initial condition $y_{i}(0)$ iff
$\left(I+\omega_{i}\Psi(T)\right)^{-1}$ exists. In other words, the game has
an open-loop Nash equilibrium for every initial states
$x_{0}(0),\cdots,x_{N}(0)$ iff (16) can be calculated for any arbitrary final
state $y_{i}(T)$ and accordingly, $x_{i}(T)$. If so, the equilibrium actions
are unique and exist for all $t\in[0,T]$. Otherwise, the game does not have a
unique open-loop Nash equilibrium for every initial states
$x_{0}(0),\cdots,x_{N}(0)$.

In the following, we show that the matrix $I+\omega_{i}\Psi(T)$ is invertible.

From (6), we have

$\mathrm{e}^{(t-s)A}BB^{\top}\mathrm{e}^{(t-s)A^{\top}}=\mathrm{e}^{(t-s)A}B(\mathrm{e}^{(t-s)A}B)^{\top}.$

The product of any matrix and its transpose is always symmetric. Thus,
$\omega_{i}\Psi(T)$ is symmetric. The matrix $\mathrm{e}^{(t-s)A}$ is positive
definite and all its eigenvalues are positive. The matrix $BB^{\top}$ is a
nonnegative diagonal matrix, and then the eigenvalues of the product of
$\mathrm{e}^{(t-s)A}BB^{\top}\mathrm{e}^{(t-s)A^{\top}}$ still have
nonnegative real parts. Therefore, all the eigenvalues of
$I+\omega_{i}\Psi(T)$ in (6) have positive real parts.

Substituting (16) into (14) and rearranging it, we obtain (8). Similarly,
substituting (13) into (11) and then (16) into it, we get (5).

∎

##  IV Collision Avoidance Estimated Nash Strategy

The platoon control problem (1) and PIs (3) and its solution in Theorem 1
satisfy only the control objectives of maintaining a constant inter-vehicular
spacing with the predecessor and maintaining the consensual velocities and
accelerations of all followers with the leader. In addition, each following
vehicle in the platoon has to ensure the crucial requirement of collision
avoidance.

Control designs that simultaneously guarantee the time-headway spacing and
collision avoidance in platoons were the focus of a few reports [31, 32]. The
differential game literature on collision avoidance is from multi-robot
systems [27, 33].

For the platoon control problem with collision avoidance, the PI for vehicle
$i$ is redefined as

$\displaystyle\hat{J}_{i}=J_{i}+\frac{1}{\mu_{i}\|x_{i-1}(T)-x_{i}(T)-\hat{r}_{i}\|^{2}+\epsilon}$
(17)

for all $i\in\\{1,\ldots,N\\}$ where $\mu_{i}>0$ is a weighting parameter,
$\epsilon>0$ is a positive scalar to ensure a non-zero denominator, and
$\hat{r}_{i}=[r_{i},0,0]^{\top}$ where $r_{i}$ is a safe distance from the
predecessor for collision avoidance. If vehicle $i$ gets closer to its
predecessor than $r_{i}$, a collision is unavoidable.

The platoon control problem with collision avoidance in (1) and (17) is non-
trivial and challenging to solve for its closed-form solution. We attempt to
constitute an estimation of the exact solution that guarantees the collision
avoidance behavior of followers.

Define the following positive scalar function of $y_{i}(t)$

$f(y_{i}(t))=\frac{1}{\left(\mu_{i}(y_{i}(t)+\hat{d}_{i}-\hat{r}_{i})^{\top}(y_{i}(t)+\hat{d}_{i}-\hat{r}_{i})+\epsilon\right)^{2}}.$
(18)

Also, define

$\displaystyle z_{i}(t)=$
$\displaystyle\Big{(}I+\big{(}\omega_{i}-\mu_{i}f(\mathrm{e}^{tA}y_{i}(0))\big{)}\Psi(t)\Big{)}^{-1}$
$\displaystyle\Big{(}\mathrm{e}^{tA}y_{i}(0)-\mu_{i}f(\mathrm{e}^{tA}y_{i}(0))\Psi(t)(\hat{r}_{i}-\hat{d}_{i})\Big{)}$
(19)

where $z_{i}(T)=\hat{y}_{i}(T)$.

######  Theorem 2.

Consider a platoon of vehicles with the feedback linearized dynamics given in
(1) and PIs in (17). Suppose that every vehicle $i$ utilizes the following
estimation of its terminal state vector $y_{i}(T)$ from (IV), i.e.,
$\hat{y}_{i}(T)$. For the platoon control problem with collision avoidance as
a noncooperative differential game, the following estimations of the unique
Nash equilibrium form collision-avoidance control inputs

$\hat{u}_{i}(t)=-\sum_{j=1}^{i}\hat{\xi}_{j}(t)$ (20)

where

$\displaystyle\hat{\xi}_{i}(t)=-B^{\top}\mathrm{e}^{(T-t)A^{\top}}\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(\mathrm{e}^{TA}y_{i}(0))\big{)}\hat{y}_{i}(T)+\mu_{i}f(\mathrm{e}^{TA}y_{i}(0))(\hat{r}_{i}-\hat{d}_{i})\Big{)}.$
(21)

The state trajectories associated with the equilibrium actions are given by

$\hat{x}_{i}(t)=x_{0}(t)-\sum_{j=1}^{i}(\hat{y}_{j}(t)+\hat{d}_{j})$ (22)

where

$\displaystyle\hat{y}_{i}(t)=\mathrm{e}^{tA}y_{i}(0)-\Psi(t)\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(\mathrm{e}^{TA}y_{i}(0))\big{)}\hat{y}_{i}(T)+\mu_{i}f(\mathrm{e}^{TA}y_{i}(0))(\hat{r}_{i}-\hat{d}_{i})\Big{)}.$
(23)

###### Proof.

The platoon control problem in (1) and (17) in terms of the state vector
$y_{i}(t)$ and control input $\xi_{i}(t)$ reduces to the minimization of the
following optimization

$\displaystyle\min_{\xi_{i}}\hat{\mathcal{J}}_{i}$
$\displaystyle=\mathcal{J}_{i}(\xi_{i}(t))+$
$\displaystyle\frac{1}{\mu_{i}(y_{i}(T)+\hat{d}_{i}-\hat{r}_{i})^{\top}(y_{i}(T)+\hat{d}_{i}-\hat{r}_{i})+\epsilon}$

subject to (9).

Define the Hamiltonian (10) and by using the necessary conditions for
optimality, we obtain (11) and (12) with the following terminal condition

$\displaystyle\lambda_{i}(T)=\omega_{i}y_{i}(T)-\mu_{i}f(y_{i}(T))(y_{i}(T)+\hat{d}_{i}-\hat{r}_{i})$
(24)

for $i\in\\{1,\ldots,N\\}$.

The solution of (12) using the terminal condition (24) is given by

$\displaystyle\lambda_{i}(t)=\mathrm{e}^{(T-t)A^{\top}}\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(y_{i}(T))\big{)}y_{i}(T)+\mu_{i}f(y_{i}(T))(\hat{r}_{i}-\hat{d}_{i})\Big{)}.$
(25)

Substituting (IV), respectively, into (11) and then into (9), we have

$\displaystyle\xi$ ${}_{i}(t)=-B^{\top}\mathrm{e}^{(T-t)A^{\top}}\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(y_{i}(T))\big{)}y_{i}(T)+\mu_{i}f(y_{i}(T))(\hat{r}_{i}-\hat{d}_{i})\Big{)},$
(26) $\displaystyle\dot{y}$
${}_{i}(t)=Ay_{i}(t)-BB^{\top}\mathrm{e}^{(T-t)A^{\top}}\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(y_{i}(T))\big{)}y_{i}(T)+\mu_{i}f(y_{i}(T))(\hat{r}_{i}-\hat{d}_{i})\Big{)}$
(27)

for all $i\in\\{1,\ldots,N\\}$.

The solution of (27) is given by

$\displaystyle y_{i}(t)$ $\displaystyle=\mathrm{e}^{tA}y_{i}(0)-$
$\displaystyle\Psi(t)\Big{(}\big{(}\omega_{i}-\mu_{i}f(y_{i})\big{)}y_{i}(T)+\mu_{i}f(y_{i})(\hat{r}_{i}-\hat{d}_{i})\Big{)}$

where at $T$ it can be rearranged as the following

$\displaystyle\Big{(}I+\big{(}\omega_{i}-$
$\displaystyle\mu_{i}f(y_{i}(T))\big{)}\Psi(T)\Big{)}y_{i}(T)=$
$\displaystyle\mathrm{e}^{TA}y_{i}(0)-\mu_{i}f(y_{i}(T))(\hat{r}_{i}-\hat{d}_{i})\Psi(T)$

or equivalently,

$\displaystyle y_{i}(T)=\Big{(}I+$
$\displaystyle\big{(}\omega_{i}-\mu_{i}f(y_{i}(T))\big{)}\Psi(T)\Big{)}^{-1}$
$\displaystyle\Big{(}\mathrm{e}^{TA}y_{i}(0)-\mu_{i}f(y_{i}(T))(\hat{r}_{i}-\hat{d}_{i})\Psi(T)\Big{)}.$
(28)

It is obvious from (IV) that every player $i$ (i.e., every vehicle in the
platoon) for all $i\in\\{1,\ldots,N\\}$ requires the knowledge of
$f(y_{i}(T))$ for every possible terminal state vector $y_{i}(T)$, which is
too complex to acquire from the current expression. Therefore, control inputs
$\xi_{i}(t)$ and their associated state trajectories $y_{i}(t)$ will not be
available explicitly, and thus neither will the true Nash equilibrium
$u_{i}(t)$ and its associated state trajectories $x_{i}(t)$. However, it is
possible to obtain a simplified expression for $\xi_{i}(t)$ and $y_{i}(t)$
from (IV) as follows.

Assume that every player $i$ utilizes $y_{i}(T)=\mathrm{e}^{TA}y_{i}(0)$ to
calculate $f(y_{i}(T))$. Then we arrive at the terminal state estimation of
$\hat{y}_{i}(T)$ from (IV). Substituting $\hat{y}_{i}(T)$ into (26) and (27)
we get the estimations of control inputs $\hat{\xi}_{i}(t)$ in (21) and their
associated state trajectories $\hat{y}_{i}(t)$ in (2), respectively.
Therefore, the estimations of the unique Nash equilibrium actions and their
associated state trajectories are given by (20) and (22), respectively. ∎

The proposed estimated solution approach is incapable of dealing with
collision avoidance since it is designed to implement the collision avoidance
behavior only at the horizon time $T$. To consider collision avoidance for all
$t\in[0,T]$, the PIs (17) must have the collision avoidance term inside the
integration, which brings far more difficulty to designing an implementable
solution.

To implement the estimated Nash strategy design approach to include collision
avoidance for $t\in[0,T]$, we utilize the following solution

$\displaystyle\hat{\xi}_{i}(t)=-B^{\top}\mathrm{e}^{(T-t)A^{\top}}\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(\mathrm{e}^{tA}y_{i}(0))\big{)}z_{i}(t)+\mu_{i}f(\mathrm{e}^{TA}y_{i}(0))(\hat{r}_{i}-\hat{d}_{i})\Big{)}$
(29)

and

$\displaystyle\hat{y}_{i}(t)=\mathrm{e}^{tA}y_{i}(0)-\Psi(t)\times$
$\displaystyle\Big{(}\big{(}\omega_{i}-\mu_{i}f(\mathrm{e}^{tA}y_{i}(0))\big{)}z_{i}(t)+\mu_{i}f(\mathrm{e}^{tA}y_{i}(0))(\hat{r}_{i}-\hat{d}_{i})\Big{)}.$
(30)

Note that the solution above still has an open-loop information structure
since it consists only of the initial state vector and time. As it is seen
from its definition in (IV), the vector $z_{i}(t)$ is also a function of the
initial state vector and time.

##  V Simulation Results

In this section, we provide simulation results to demonstrate the
effectiveness of the proposed platoon control schemes in Section III and IV.
Consider a homogeneous platoon of five vehicles, i.e., $N=4$, of which the
front vehicle is the leader and is not subject to control, and the rest are
the followers with their control inputs to be designed. The inertial time-lag
parameter is arbitrarily selected as $\tau=0.5$. The initial states of the
vehicles are given by $x_{0}(0)=[23,2,0]^{\top}$,
$x_{1}(0)=[18,2.5,1]^{\top}$, $x_{2}(0)=[11,3,1.5]^{\top}$,
$x_{3}(0)=[6,1.5,0.8]^{\top}$, $x_{4}(0)=[1,2,1.2]^{\top}$. Suppose that
vehicles in the desired platoon will be equally spaced by
$d_{1}=d_{2}=d_{3}=d_{4}=2$. Also, let $r_{1}=r_{2}=r_{3}=r_{4}=1$, meaning
that if vehicle $i\in\\{1,\ldots,4\\}$ gets closer to its predecessor than
$1$, a collision occurs. In the PIs, $\omega_{1}=6$, $\omega_{2}=3$,
$\omega_{3}=8$, $\omega_{4}=5$, $\mu_{1}=12$, $\mu_{2}=10$, $\mu_{3}=1$,
$\mu_{4}=5$, and $T=10$ for the time interval of the game.

We first solve the platoon control problem without collision avoidance with
the open-loop Nash strategy given by (4) and its associated state trajectory
(7) in Theorem 1. Fig. 2 shows the following vehicles achieving the desired
platoon at the horizon time $T=10$. In addition, it also shows the
longitudinal velocities and accelerations of the following vehicles reaching
the lead vehicle’s velocity and acceleration. However, a collision between the
lead vehicle and vehicle 1 occurs approximately at $t=5$.

Figure 2: Time histories of positions, velocities, accelerations, and control
inputs of vehicles in the platoon control problem without collision avoidance.
A collision between the lead vehicle and vehicle 1 is unavoidable.

Once again, we resolve the platoon control problem with collision avoidance
with the estimated Nash strategy solution (IV) and (IV). The results in Fig. 3
show the vehicles achieving basically the identical desired platoon at the
horizon time $T=10$ as in the previous problem. However, it follows from Fig.
3 that the collision between the lead vehicle and vehicle 1 is eradicated.
Moreover, the vehicles achieve the desired platoon from approximately $t=3$
on, compared to the previous problem at horizon time $T=10$. This demonstrates
the effectiveness of the proposed estimated solution implementation (IV) and
(IV) in coping with collision avoidance, early acquiring the desired platoon,
and maintaining it. Note that the velocities of all follower vehicles should
be equal to or greater than the leader’s velocity (i.e., $v_{i}(t)\geq v_{0}$
for all $i\in\\{1,\ldots,N\\}$,) in order to avoid a collision risk [31].
While this requirement is not seen in Fig. 2 for the platoon control problem
without collision avoidance, it is totally assured in Fig. 3 for the platoon
control problem with collision avoidance. A smaller velocity than the lead
vehicle’s velocity describes a braking maneuver for the following vehicle that
creates a collision risk with its predecessor. Such maneuvers are seen for
vehicles 3 and 4 in Fig. 2. Finally, the scalar function
$f(\mathrm{e}^{tA}y_{i}(0))$ has been plotted for $t\in[0,T]$ in Fig. 4. This
function reveals collision risk for each following vehicle as a function of
time and its initial state. It is seen that vehicles 1, 2, and 4 experience
the peak collision risks at approximate times 4, 8, and 6, respectively, while
vehicle 3 is not facing any collision risk the whole time.

Figure 3: Time histories of positions, velocities, accelerations, and control
inputs of vehicles in the platoon control problem with collision avoidance.
All following vehicles pursue collision-free trajectories. Figure 4: Time
histories of the scalar function $f(\mathrm{e}^{tA}y_{i}(0))$.

##  VI Conclusions

In this paper, we have introduced differential game models for the homogeneous
predecessor-following vehicle platoon control problem without and with
collision avoidance. We obtained the closed-form expression for the unique
Nash equilibrium and its associated state trajectories for the following
vehicles. Simulation results have shown that the following vehicles acquire
the desired platoon by committing to their self-enforcing controller based on
Nash equilibrium actions. Furthermore, collision avoidance was considered in
the platoon control problem, and the estimated Nash solution was proposed. The
effectiveness of the proposed estimated Nash strategy design approach was
observed in the simulation results. Future work will include more
sophisticated platoon information topologies for connected environments,
investigating feedback Nash equilibrium under feedback information
differential games, and studying the string stability of the platoon.

## Acknowledgment

This work was supported by SGS, VŠB - Technical University of Ostrava, Czech
Republic, under grant No. SP2023/012 “Parallel processing of Big Data X”.

## References

  * [1] C. Bergenhem, S. E. Shladover, E. Coelingh, C. Englund, S. Tsugawa, Overview of platooning systems, Proceedings of the 19th ITS World Congress, 2012.
  * [2] A. Soni, H. Hu, ”Formation control for a fleet of autonomous ground vehicles: a survey,” in Robotics, vol. 7, no. 4, 2018.
  * [3] G. Guo, W. Yue, ”Hierarchical platoon control with heterogeneous information feedback,” in IET Control Theory & Applications, vol. 5, no. 15, 2011.
  * [4] H. B. Jond, A. Yıldız, ”Connected and automated vehicle platoon formation control via differential games,” in IET Intelligent Transport Systems, vol. 17, no. 2, pp. 312-326, 2023.
  * [5] X. Qian, A. de La Fortelle, F. Moutarde, ”A hierarchical Model Predictive Control framework for on-road formation control of autonomous vehicles,” 2016 IEEE Intelligent Vehicles Symposium (IV), Gothenburg, Sweden, pp. 376-381, 2016.
  * [6] H. B. Jond, J. Platoš, ”Differential game-based optimal control of autonomous vehicle convoy,” in IEEE Transactions on Intelligent Transportation Systems, vol. 24, no. 3, pp. 2903-2919, 2023.
  * [7] S. Woo, A. Skabardonis, ”Flow-aware platoon formation of Connected Automated Vehicles in a mixed traffic with human-driven vehicles,” in Transportation Research Part C: Emerging Technologies, vol. 133, pp. 103442, 2021.
  * [8] V. Lesch, M. Breitbach, M. Segata, C. Becker, S. Kounev and C. Krupitzer, ”An overview on approaches for coordination of platoons,” in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 8, pp. 10049-10065, 2022.
  * [9] M. Y. Abualhoul, M. Marouf, O. Shagdar, F. Nashashibi, ”Platooning control using visible light communications: A feasibility study,” 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), The Hague, Netherlands, pp. 1535-1540, 2013.
  * [10] Z. Wang, Y. Bian, S. E. Shladover, G. Wu, S. E. Li, M. J. Barth, ”A survey on cooperative longitudinal motion control of multiple connected and automated vehicles,” in IEEE Intelligent Transportation Systems Magazine, vol. 12, no. 1, pp. 4-24, 2020.
  * [11] W. B. Dunbar, D. S. Caveney, ”Distributed receding horizon control of vehicle platoons: stability and string stability,” in IEEE Transactions on Automatic Control, vol. 57, no. 3, pp. 620-633, 2012.
  * [12] R. Firoozi, X. Zhang, F. Borrelli, ”Formation and reconfiguration of tight multi-lane platoons,” in Control Engineering Practice, vol. 108, pp. 104714, 2021.
  * [13] G. Antonelli, F. Arrichiello, S. Chiaverini, ”The NSB control: a behavior-based approach for multi-robot systems,” Paladyn, Journal of Behavioral Robotics, vol. 1, no. 1, pp. 48-56, 2010.
  * [14] M. EL-Zaher, B. Dafflon, F. Gechter, J.-M. Contet, ”Vehicle platoon control with multi-configuration ability,” Procedia Computer Science, vol. 9, pp. 1503-1512, 2012.
  * [15] W. Ren, R. W. Beard, ”Decentralized scheme for spacecraft formation flying via the virtual structure approach,” Journal of Guidance, Control, and Dynamics, vol. 27, no. 1, pp. 73-82, 2004.
  * [16] E. Semsar-Kazerooni, J. Verhaegh, J. Ploeg, M. Alirezaei, ”Cooperative adaptive cruise control: An artificial potential field approach,” 2016 IEEE Intelligent Vehicles Symposium (IV), Gothenburg, Sweden, pp. 361-367, 2016.
  * [17] R. Hao, M. Liu, W. Ma, B. van Arem, M. Wang, ”A flock-like two-dimensional cooperative vehicle formation model based on potential functions,” Transportmetrica B: Transport Dynamics, vol. 11, no. 1, pp. 174-195, 2023.
  * [18] L. Li, R. Hao, W. Ma, X. Qi, C. Diao, ”Swarm intelligence based algorithm for management of autonomous vehicles on arterials,” Intelligent and Connected Vehicles Symposium, 2018.
  * [19] F. Morbidi, P. Colaneri, T. Stanger, ”Decentralized optimal control of a car platoon with guaranteed string stability,” 2013 European Control Conference (ECC), Zurich, Switzerland, 2013, pp. 3494-3499.
  * [20] W. Lin, ”Distributed UAV formation control using differential game approach,” in Aerospace Science and Technology, vol. 35, pp. 54-62, 2014.
  * [21] E. van Damme, Refinements of the Nash Equilibrium Concept, Lecture Notes in Economics and Mathematical Systems, Springer Berlin Heidelberg, 2012.
  * [22] A. Johansson, E. Nekouei, K. H. Johansson, J. Mårtensson, ”Strategic hub-based platoon coordination under uncertain travel times,” in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 7, pp. 8277-8287, 2022.
  * [23] M. H. Basiri, M. Pirani, N. L. Azad, S. Fischmeister, ”Security of vehicle platooning: a game-theoretic approach,” in IEEE Access, vol. 7, pp. 185565-185579, 2019.
  * [24] J. A. Leon Calvo, R. Mathar, ”Connected Vehicles Coordination: A Coalitional Game-Theory Approach,” 2018 European Conference on Networks and Communications (EuCNC), 2018.
  * [25] Y. Liu, C. Zong, C. Dai, H. Zheng, D. Zhang, ”Behavioral Decision-Making Approach for Vehicle Platoon Control: Two Noncooperative Game Models,” in IEEE Transactions on Transportation Electrification, 2023.
  * [26] D. Gu, ”A differential game approach to formation control,” in IEEE Transactions on Control Systems Technology, vol. 16, no. 1, pp. 85-93, 2008.
  * [27] T. Mylvaganam, M. Sassano and A. Astolfi, ”A differential game approach to multi-agent collision avoidance,” in IEEE Transactions on Automatic Control, vol. 62, no. 8, pp. 4229-4235, 2017.
  * [28] H. B. Jond, V. V. Nabiyev, ”On the finite horizon Nash equilibrium solution in the differential game approach to formation control,” in Journal of Systems Engineering and Electronics, vol. 30, no. 6, pp. 1233-1242, 2019.
  * [29] L. Xiao, F. Gao, ”Practical string stability of platoon of adaptive cruise control vehicles,” in IEEE Transactions on Intelligent Transportation Systems, vol. 12, no. 4, pp. 1184-1194, 2011.
  * [30] J. Hu, P. Bhowmick, F. Arvin, A. Lanzon, B. Lennox, ”Cooperative control of heterogeneous connected vehicle platoons: an adaptive leader-following approach,” in IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 977-984, 2020.
  * [31] J. Lunze, ”Adaptive cruise control with guaranteed collision avoidance,” in IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 5, pp. 1897-1907, 2019.
  * [32] A. Schwab, J. Lunze, ”Design of platooning controllers that achieve collision avoidance by external positivity,” in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 9, pp. 14883-14892, 2022.
  * [33] D. Cappello, S. Garcin, Z. Mao, M. Sassano, A. Paranjape, T. Mylvaganam, ”A hybrid controller for multi-agent collision avoidance via a differential game formulation,” in IEEE Transactions on Control Systems Technology, vol. 29, no. 4, pp. 1750-1757, 2021.