This paper proposes a consensus controller for multi-agent systems that can guarantee the agents' safety. The controller, built with the idea of output prediction and the Newton-Raphson method, achieves consensus for a class of heterogeneous nonlinear systems. The Integral Control Barrier Function is applied in conjunction with the controller, such that the agents' states are confined within pre-defined safety sets. Due to the dynamically-defined control input, the resulting optimization problem from the barrier function is always a Quadratic Program, despite the nonlinearities that the system dynamics may have. We verify the proposed controller using a platoon of autonomous vehicles modeled by kinematic bicycles. A convergence analysis of the leader-follower consensus under the path graph topology is conducted. Simulation results show that the vehicles achieve consensus while keeping safe inter-agent distances, suggesting a potential in future applications.

§ INTRODUCTION

Consensus control has been extensively investigated in the setting of multi-agent systems, where typically it is underscored by a distributed algorithm that guarantees convergence of the state or output variables of various agents to a common target value; see, e.g., [1] and references therein. Application areas of consensus control include swarms of unmanned aerial vehicles and platoons of self-driving cars. Following the initial results for homogeneous linear systems, recent studies focused on consensus for nonlinear heterogeneous systems. Ref. [2] derived a consensus controller for heterogeneous Euler-Lagrange systems; [3] investigated general nonlinear single-input-single-output systems; [4] considered a class of second-order systems. Consensus controllers using  adaptive control  [5] [6] and Model Predictive Control (MPC)  [7] [8] are also proposed.

Recently, the authors of this paper developed a consensus controller for heterogeneous nonlinear systems [9] using the agents' predicted outputs after a given time horizon. With the Newton-Raphson method, consensus may be achieved for a class of nonlinear systems. However, the controller does not provide any measure of safety. For example, it allows multiple agents (e.g., autonomous vehicles) to occupy common physical spaces as the consensus control converges, leading to inter-agent collisions that are unfavorable in practice. To satisfy safety constraints, this paper supplements a controller with a Control Barrier Function (CBF), such that the states of the agents are restricted within pre-defined safety sets. Thanks to the dynamically-defined control inputs, the Integral Control Barrier Function (I-CBF) [21] as a special form of the CBF may be used. Despite the nonlinear dynamics of the system, the optimization problems associated with the I-CBF are always Quadratic Programs (QPs), which is different from the classical CBF that may result in Nonlinear Programs (NLPs). This feature enables a faster solution and an easier feasibility check during the control period. While it is also possible to maintain safety by directly modifying the consensus controller, a CBF technique may serve as a backup to unforeseen circumstances and would modify the controller in a less aggressive manner.

As a practical application, this paper considers a platoon of autonomous vehicles. Control of autonomous vehicles has been extensively studied in the literature. Adaptive Cruise Control focuses on vehicle longitudinal dynamics, for which a PID controller is designed in [10], and an MPC controller in [11]. The lateral dynamics, which are nonlinear and can be described by kinematic or dynamic bicycle models [12], have been studied as well. Ref.  [13] designed a controller for vehicle merging and platooning. A hierarchical formation controller for platoons has been derived in [14] using MPC. Ref.   [15] proposes a tracking controller for the lateral dynamics. The CBF technique is also applied to autonomous vehicles. [16] applied CBFs for Adaptive Cruise Control. [17] achieved lane keeping and spacing on unicycle models. [18] applied the CBF with a tracking technique to the dynamic bicycle. While many existing results study the vehicle's lateral and longitudinal dynamics separately, this paper considers them jointly to demonstrate the interactions between platooning and CBFs in a 2-D plane. We also recognize that in practice, it is often desired that the vehicle platoon could follow a pre-defined trajectory. Therefore, this paper considers the consensus of the leader-follower structure, as an extension of the leaderless controller [9].
A convergence analysis is performed for the platoon modeled by directed path graphs. We evaluate the safety of the platoon by the inter-agent distances. Using the I-CBF, each agent maintains a proper distance to its successor and predecessor, avoiding potential collisions in unexpected conditions.

The remainder of this paper is organized as follows: Section II  reviews the existing consensus controller and summarizes relevant results on I-CBFs. Section III defines the consensus problem for the vehicle platoons and presents the proposed solutions. Section IV discusses the simulation results, and Section V concludes the paper.

§ SURVY OF BACKGROUND MATERIAL

§.§ Prediction-based consensus controller

The consensus controller [9] features the idea of the output prediction and the Newton-Raphson method. This approach was inspired by [19], where a tracking controller for single-agent systems is derived. Consider a multi-agent system consisting $N$ agents, denoted by $A_{i}$,    $i\in \mathcal{N}:= \{1,2,3,\hdots, N\}$. Suppose that the motion dynamics of $A_{i}$ are modelled by the differential equation:

\begin{equation}
\label{eqn_mas_dynamics}
\dot{x}_i(t) = f_i(x_i(t),u_i(t)),
\end{equation}

where $x_i(t) \in \mathbb{R}^{n_i}$ and $u_i(t) \in \mathbb{R}^{m}$ are the respective state variable  and input variable  of $A_i$, for some given positive integers $n_{i}$ and $m$. Denote
$x_{i}(0)\in\mathbb{R}^{n_{i}}$ as the initial condition of Eqn. (<ref>) at time $t=0$. Suppose that
$f_i : \mathbb{R}^{n_i}\times \mathbb{R}^m \mapsto \mathbb{R}^{n_i}$ is a continuously differentiable function. In addition, $f_i$ satisfies suitable sufficient conditions for the existence of unique solutions of Eqn. (1), in the time interval $t\in[0,\infty)$ for every bounded, piecewise continuous  input signal $\{u_i(t):t\in[0,\infty)\}$, and initial condition $x_i(0)\in\mathbb{R}^{n_{i}}$ (see, e.g., Ref. [9], Assumption 1). The output of the agent $A_i$ is denoted by

\begin{equation}
\label{eqn_MAS_outputs}
y_i(t) = h_i(x_i(t)),
\end{equation}

where the function $h_i : \mathbb{R}^{n_i}\mapsto\mathbb{R}^m$ is continuously differentiable. Observe that the dimensions of the agents' state spaces, $n_{i}$, may be different from each other, but their input and output spaces must have the same dimension, $m$.

The consensus problem requires a distributed controller, such that the outputs of all agents can (asymptotically) converge to the same point, namely:

\begin{equation}
\label{eqn_consensus_requirement}
\limsup_{t \rightarrow \infty} \Vert y_i(t) - y_j(t)\Vert = 0, \forall i, j \in \mathcal{N}.
\end{equation}

To design such a controller, information exchange among agents is often necessary. This information exchange is carried out over a communication network, whose topology is modeled by an undirected graph $\mathcal{G}$. Its vertices, $V_{i}$, $i=1,\ldots,N$, correspond to the respective agents $A_{i}$, $i=1,\ldots,N$. Its edges, connecting pairs of vertices, correspond to bi-directional communication links between two agents.
$A_{j}$ is a neighbor of $A_{i}$ if and only if $A_{i}$ can receive information from $A_{j}$. The indices of the neighbors of the $i$-th agent are denoted by a set $N_i$. For the leaderless consensus controller over undirected graphs, we make the following assumption:

Assumption I: The (undirected) communication graph $\mathcal{G}$ is connected, meaning that there is a path formed by a sequence of neighboring edges between every pair of vertices $(V_i, V_j), i\not=j$. $\Box$

The consensus controller [9] attempts to reach a consensus among the agents' predicted outputs. Suppose that all agents have the same prediction horizon, $T>0$, and denote the predicted output of $A_i$, computed at time $t$, by $\tilde{y}_i(t+T)$. We make the following assumption:

Assumption II: The predicted output $\tilde{y}_i(t+T)$ functionally depends on $(x_{i}(t)^\top,u_{i}(t)^\top)^\top$ in the following way:

\begin{equation}
\label{eqn_predictor}
\tilde{y}_i(t+T) = g_i(x_i(t), u_i(t)),
\end{equation}

where $g_i : \mathbb{R}^{n_i} \times \mathbb{R}^m \mapsto \mathbb{R}^{m}$ is a continuously differentiable function.$\Box$

We point out that the function $g_i(\cdot, \cdot)$ may not have a known analytic form, but it can be approximated by numerical methods or calculated by simulations.

The consensus controller [9] has the following form:

\begin{equation}
\label{eqn_consensus_controller}
\dot{u}_{i}=-\alpha_{i}\left(\frac{\partial g_{i}}{\partial u_i}(x_{i},u_{i})\right)^{-1}\sum_{j\in N_{i}}\big(g_{i}(x_{i},u_{i})-g_{j}(x_{j},u_{j})\big),
\end{equation}

where $\alpha_i \geq 1$ is a given constant called the controller's speedup factor of $A_{i}$. As discussed in [9] and explained in the sequel, large controller speedup factors may be associated with the stabilization of the closed-loop system and reductions of asymptotic tracking errors. Note that Eqn. (<ref>) is a fluid-flow version of the Newton-Raphson method, which takes the average of the solutions $u_i$ of $g_i(\cdot) = g_j(\cdot), j \in N_i$. Under a bounded-input-bounded-state stability condition defined in [9], there exists a positibe number $\eta$, such that the local consensus error is bounded by:

\begin{equation}
\lim\sup_{t\rightarrow\infty}||\sum_{j\in{\mathcal N}_{i}}\big(\tilde{y}_{i}(t+T)-\tilde{y}_{j}(t+T)\big)||^2<\frac{\eta}{4\alpha_{\min}},
\end{equation}

where $\alpha_{{\rm min}}:={\rm min}\{\alpha_{i}:i\in{\mathcal N}\}$. Moreover, as $\alpha_{\min}\rightarrow \infty$, the global consensus error converges to $0$. Note that the controller achieves consensus on the agents' predicted outputs instead of true outputs. The difference between predictions and true outputs, called the prediction gap, can only be reduced by using high-precision predictors $g_i(\cdot)$.

remove the definition of the predictor?
The predictor used in [9], following [19], is defined by the following equations

\begin{equation}
\begin{split}
\dot{\xi}_i(\tau) = f_i(\xi_i(\tau), u_i(t)),
\end{split}
\end{equation}

where “dot” denotes derivative with respect to $\tau\in[t,t+T]$,
with the boundary condition $\xi(t)=x(t)$; and

\begin{equation}
\label{eqn_predictor}
\tilde{y}_i(t+T) := h_i(\xi_i(t+T)).
\end{equation}

Observe that these equations describe the dynamical system defined by (1), (2), and (5)   in the interval $\tau\in[t,t+T]$ with the constant input $\mu_i(\tau)\equiv u_i(t)$ and the initial condition $\xi_i(t)=x_i(t)$. The function $f_{i}(\cdot,\cdot)$ is the state equation of  agent $A_{i}$ with the constant input $u_i(t)$ for all $\tau\in[t,t+T]$, reflecting the fact that the input at future times ahead of $t$ are not known at time $t$. This predictor satisfies Assumption II, and can be computed by the forward-Euler method.

§.§ Integral Control Barrier Function

The Control Barrier Function (CBF) technique is an effective method that can ensure the safety of feedback control systems. The objective of the CBF is to confine the system states within a pre-defined admissible set while modifying the system inputs in the least invasive way. As a specific form of the CBF, the Integral Control Barrier Function (I-CBF) ([21]) is dedicated to the dynamically-defined controllers. Consider a dynamically controlled system:

\begin{equation}
\label{eqn_dynamic_control}
\begin{split}
\dot{x}(t) &= f(x(t),u(t))\\
\dot{u}(t) &= \Phi(x(t), u(t)),
\end{split}
\end{equation}

where $f:\mathbb{R}^{n}\times \mathbb{R}^{m}\rightarrow \mathbb{R}^{n}$ is the state equation of the system, and $x(t) \in \mathbb{R}^n$ are the system states. The inputs $u(t)\in\mathbb{R}^m$ of the system are dynamically defined by a continuous function $\Phi:\mathbb{R}^n\times \mathbb{R}^m\rightarrow\mathbb{R}^{m}$. This setting is different from a static controller $u(t) = \phi(x(t))$. Let $S\subset \mathbb{R}^n \times \mathbb{R}^m$ be a closed set (called the safety set), such that the system is safe if and only if $z(t) \triangleq (x(t)^\top, u(t)^\top)^\top\in S$[Compared to the traditional CBF, the definition of the safety set $S$ has been extended to encompass the system inputs $u(t)$. This is due to the fact that the controller is dynamically defined. See [21] for a detailed discussion.].  Safety control requires a sequence of control input $u(t), t \in [0, +\infty)$ for (<ref>), so that the set $S$ is:

* forward-invariant, meaning that if $z(t_0) \in S$, then $z(\tau) \in S$ for all $ \tau\in[t_0,+\infty)$.

* exponentially stable,  meaning that the distance from $z(t), t \in [0,+\infty)$ to $S$ reduces exponentially.

To ensure these safety requirements, let $h:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$ be a continuously-differentiable function satisfying the following condition:

\begin{equation}
\begin{split}
&h(z(t)) > 0,~~~~~ \forall z(t)\in\mathcal{S} - \partial\mathcal{S}\\
&h(z(t)) = 0,~~~~~ \forall z(t)\in\partial
\mathcal{S}\\
&h(z(t)) < 0,~~~~~ \forall z(t)\not\in\mathcal{S}.
\end{split}
\end{equation}

Let $\kappa:\mathbb{R}\rightarrow\mathbb{R}$ be an extended class-$\mathcal{K}$ function. Suppose that for every system trajectory $\{z(t):t\in[0,\infty)\}$ the following equation is satisfied for every $t\in[0,\infty)$:

\begin{equation}
\label{eqn_dh_safety}
\dot{h}(z(t)) + \kappa(h(z(t))) \geq 0,
\end{equation}

then the forward invariance and the exponential stability of the set $S$ can be guaranteed ([16, 17]). In case that the original control law $\Phi(x(t), u(t))$ does not satisfy these requirements, consider modifying the dynamics of $\dot{u}(t)$ by adding a bias term $w(t) \in \mathbb{R}^{m}$:

\begin{equation}
\label{eqn_dynamic_control_icbf}
\begin{split}
\dot{x}(t) &= f(x(t),u(t))\\
\dot{u}(t) &= \Phi(x(t), u(t)) + w(t).
\end{split}
\end{equation}

With the bias $w(t)$, an input $u(t)$ satisfying the safety constraint may be calculated. To avoid modifying the original control $\Phi(x(t), u(t))$ excessively, $w(t)$ should be as small as possible, leading to the following optimization problem:

\begin{equation}
\label{eqn_icbf_qp}
\begin{split}
&\min_{w} \Vert w\Vert^2\\
\text{s.t.}\ \  (\dfrac{\partial h}{\partial u}(x,u))^\top w \geq  &-(\dfrac{\partial h}{\partial x}(x,u))^\top f(x,u)\\- (\dfrac{\partial h}{\partial u}(x,u))^\top &\Phi(x, u) - \kappa(h(x,u)).
\end{split}
\end{equation}

The inequality constraints in Eqn. (<ref>) are direct results from Eqn. (<ref>).
The function $h(z(t))$ is a valid I-CBF if $\dfrac{\partial h}{\partial u} \not= 0$ or Eqn. (<ref>) holds when $\dfrac{\partial h}{\partial u} = 0$. If $h(\cdot)$ is invalid, higher-order control barrier function may be used. Define:

\begin{equation}
h^{(2)}(z(t)) = \dot{h}(z(t)) + \kappa(h(z(t))).
\end{equation}

If $\dfrac{\partial h^{(2)}}{\partial u} \not = 0$, then the bias $w$ can be calculated by:

\begin{equation}
\begin{split}
&\min_{w} \Vert w\Vert^2\\
\text{s.t.}\ \  (\dfrac{\partial h^{(2)}}{\partial u}(x,u))^\top w \geq  &-(\dfrac{\partial h^{(2)}}{\partial x}(x,u))^\top f(x,u)\\- (\dfrac{\partial h^{(2)}}{\partial u}(x,u))^\top &\Phi(x, u) - \kappa(h^{(2)}(x,u)),
\end{split}
\end{equation}

which also guarantees the safety of the set $\mathcal{S}$. If $h^{(2)}(\cdot)$ is still invalid, continue to construct higher order I-CBFs:

\begin{equation}
\begin{split}
h^{(3)}(z(t)) &= \dot{h}^{(2)}(z(t)) + \kappa(h^{(2)}(z(t))),\\
h^{(4)}(z(t)) &= \dot{h}^{(3)}(z(t)) + \kappa(h^{(3)}(z(t))),\\
\end{split}
\end{equation}

until a valid one is found. By satisfying the higher-order I-CBFs, the safety of the set $\mathcal{S}$ can also be guaranteed. See [21] for more details.

We remark that since the I-CBF is native to the dynamically defined controller, it is natural to apply the I-CBF instead of the traditional CBF  to the consensus controller defined by (<ref>) and (<ref>) in the sequel. Plus, the optimization problem associated with the I-CBF is always a Quadratic Program, even if the controlled plant is nonlinear or non-control-affine. This property is one of the main advantages of our proposed approach.

§ LEADER-FOLLOWER CONSENSUS OF KINEMATIC BICYCLES

§.§ The kinematic bicycle model

The kinematic bicycle model is a 4-th order nonlinear system, depicted in Fig. <ref>. The dynamics of this model are:

\begin{equation}
\label{eqn_bicycle_dynamics}
\begin{split}
&\dot{z}_1 = V\cos(\psi + \gamma)\\
&\dot{z}_2 = V\sin(\psi + \gamma)\\
&\dot{V} = a\\
&\dot{\psi} = \dfrac{V}{L_r}\sin(\gamma),
\end{split}
\end{equation}

where $(z_1, z_2)^\top \in \mathbb{R}^2$ represents the location of the bicycle in the 2-D plane. $V\in\mathbb{R}$ is the velocity of the bicycle. $a\in[a_{\min}, a_{\max}]$ is the bicycle's acceleration, and $\gamma \in [\gamma_{\min}, \gamma_{\max}]$ is the direction of the bicycle's velocity with respect to the heading of the bicycle frame. $L_r$ is the distance from the rear wheel to the bicycle's center of gravity (COG). Denote the angle of the steering wheel (with respect to the bicycle's heading) with $\delta_f \in (-\frac{\pi}{2},\frac{\pi}{2})$, then:

\begin{equation}
\label{eqn_gamma_delta}
\tan(\gamma) = \dfrac{L_r}{L_f+L_r}\tan(\delta_f),
\end{equation}

where $L_f$ is the distance from the front wheel to the bicycle's COG. The bijection (<ref>) enables us to convert the input $\gamma$ to the physical control $\delta_f$ in reality. The system inputs are chosen to be $u = (a, \gamma)^\top$, and the system outputs are $y = (z_1, z_2)^\top$. To distinguish between different agents, we denote the states of agent $A_i$ by $x_i = (z_{i,1}, z_{i,2}, V_{i}, \psi_i)^\top$, the inputs of $A_i$ by $u_i = (a_i, \gamma_i)^\top$ and the outputs of $A_i$ by $y_i = (z_{i,1}, z_{i,2})^\top$. The distance between the COG and the rear wheel (and front wheel) of $A_i$ is denoted by $L_{i,r}$ (and $L_{i,f}$).

The kinematic bicycle model

§.§ Leader-follower consensus for the vehicle platoon

The controller proposed in [9] considers only the case of leaderless consensus. As an extension to the original algorithm, this paper further studies the leader-follower consensus. Consider the multi-agent system consisting $K+1$ agents, denoted by $A_i, i \in \{0, 1, 2, \hdots, K\}$. The leader of the system, $A_0$, is autonomous, meaning that its control input $u_0$ is pre-defined rather than calculated by (<ref>). In reality, this leader can be replaced by an external reference signal. The followers, $A_i, i = 1,2,3,\hdots,K$, are modeled by dynamics (<ref>) and outputs (<ref>). The leader-follower consensus requires that the output of the followers, $y_i(t), i = 1,2,3,\hdots,K$, could asymptotically converge to the output of the leader, $y_0(t)$, namely:

\begin{equation}
\label{eqn_leaderfollower_require}
\lim\sup_{t\rightarrow\infty} \Vert y_i(t) - y_{0}(t)\Vert = 0, \forall i = 1,2,3,\hdots,K.
\end{equation}

The advantage of the leader-follower consensus over the leaderless consensus is that agents can track a given trajectory specified by the leader $A_0$ (or an external reference signal). This asymptotic tracking may sometimes be more preferable in the control of vehicle platoons.

An example of a vehicle platoon modeled by a directed path graph.

In this paper, we consider the multi-agent system that can be modeled by a (directed) linear graph $\mathcal{G}_L$ (also known as a path graph, see [22])  consisting $K + 1$ agents. Moreover, $\mathcal{G}_L$ satisfies: the neighbors of the agent $A_i$ are $A_{i-1}$ and $A_{i+1}$ for $i = 1,2,3,\hdots,K-1$, the last agent $A_K$ has only one neighbor $A_{K-1}$, and the leader $A_0$ has no neighbors. This is consistent with a group of vehicles marching in a platoon leaded by the first vehicle. An example of a path graph is given by Fig. <ref>. We assume that the leader satisfies:

Assumption III: the outputs of the leader $A_0$ at time $t+T$ can be predicted by $\Tilde{y}_0(t+T)$ satisfying Eqn. (<ref>) and Assumption II. Furthermore, the derivative of the prediction is bounded by:

\begin{equation}
\Vert \frac{dg_0}{dt}(x_0(t), u_0(t)) \Vert \leq \sigma,
\end{equation}

where $\sigma \in [0, +\infty)$. $\Box$

If the output of the leader is defined by an external reference signal $r(t), t\in[0,+\infty)$, then Assumption III indicates: 1) the reference signal $r(t)$ is continuously differentiable and the signal in the future $r(t+T)$ is known; 2) the time derivative $\dot{r}(t)$ of $r(\cdot)$ is bounded by $\sigma \in [0, +\infty)$.

For the multi-agent system under a linear graph topology, if the followers $A_1, A_2, \hdots, A_K$ are $\alpha$-stable (see the Appendix and [9]), then the local consensus error of the agents will be bounded. Denote the trajectory of the system by:

\begin{equation}
\label{eqn_traj_def}
\end{bmatrix}^\top,
\end{equation}

denote the set of all possible system trajectories by $\mathcal{Z}$. Then we have the following:

Lemma I: Let the inputs to the agents $A_1, A_2, \hdots, A_K$ be:

\begin{equation}
\label{eqn_leader_follower_controller}
\begin{split}
\dot{u}_{i}=-\alpha_{i}\left(\frac{\partial g_{i}}{\partial u_i}(x_{i},u_{i})\right)^{-1}\sum_{j\in N_{i}}\big(g_{i}(x_{i},u_{i})-g_{j}(x_{j},u_{j})\big),
\end{split}
\end{equation}

where $N_i = \{i-1, i+1\}, 1\leq i\leq K-1; N_K = \{K-1\}.$
Assume that the leader $A_0$ satisfies Assumption III, and the followers satisfy Assumption II. If the multi-agent system is $\alpha$-stable over a compact set $\Gamma \subset \mathcal{Z}$, then for every initial condition $z_0 = z(0) \in \Gamma$, the local consensus error of the agent $i \in \{1,2,3,\hdots,K\}$ is bounded by:

\begin{equation}
\label{eqn_local_error}
\lim\sup_{t\rightarrow\infty}\Vert\sum_{j\in N_i}(\tilde{y}_{i}(t+T) - \tilde{y}_{j}(t+T))\Vert^2 \leq \dfrac{\eta}{\alpha_{\min}},
\end{equation}

where $\eta > 0$ is a constant,  $\alpha_{\min} = \min\{\alpha_1, \alpha_2, \hdots, \alpha_K\}$. $\Box$

Note that Lemma I gives the local consensus error instead of the leader-follower consensus error. However, thanks to the linear graph topology, the leader-follower consensus error can be eliminated by enlarging the controller speedup $\alpha_{\min}$.

Proposition I: Under the (directed) linear graph topology $\mathcal{G}_L$, Assumption II for the followers, Assumption III for the leader, and the assumption of $\alpha$-stability of the system, the controller (<ref>) achieves leader-follower consensus for initial condition $z(0) \in \Gamma$ as $\alpha_{\min}$ goes to infinity:

\begin{equation}
\lim_{\alpha_{\min}\rightarrow \infty}\lim\sup_{t\rightarrow \infty} \Vert \tilde{y}_i(t+T) - \tilde{y}_0(t+T)\Vert = 0.
\end{equation}

Please see the Appendix for the proofs of Lemma I and Proposition I. Again, the consensus under control law (<ref>) is achieved over the agents' predicted outputs instead of the actual outputs, which calls for accurate predictors $g_i(\cdot)$ to reduce the consensus error defined by (<ref>).

§.§ Consensus control with Integral Control Barrier Function

The original consensus controller [9] has the risk of inter-agent collisions. To avoid such a situation, we apply the Integral Control Barrier Function to enforce a safety distance between two neighboring agents. With the I-CBF, the inputs of the $i$-th agent, $i = 1,2,3,\hdots,K$, become:

\begin{equation}
\label{eqn_consensus_input_icbf}
\begin{split}
\dot{u}_{i}=-\alpha_{i}\left(\frac{\partial g_{i}}{\partial u_i}(x_{i},u_{i})\right)^{-1}\sum_{j\in N_{i}}\big(g_{i}(x_{i},u_{i})\\-g_{j}(x_{j},u_{j})\big) + w_i.
\end{split}
\end{equation}

According to [20], it is recommended that the time headway when driving on the road should be at least $2$ seconds. Hence, the distance $D$ between two vehicles should satisfy:

\begin{equation}
\label{eqn_min_dist}
D \geq k_vV,
\end{equation}

where $k_v \geq 2s$. Since the agents are moving in a 2-D plane, the unsafe areas for agent $A_i$ are circles with radius $k_vV_i$ (where $V_i$ is the speed of the bicycle $i$), and the centers of the circles are the neighbor's location $({z}_{j,1}, z_{j,2})^\top$. This leads to the definition of the safety set for $A_i$:

\begin{equation}
\label{eqn_safety_set}
\begin{split}
&\mathcal{S}_i:= \{(z_{i,1}, z_{i,2})^\top \in \mathbb{R}^2 :\\ &(z_{i,1} - {z}_{j,1})^2 + (z_{i,2} - {z}_{j,2})^2 \geq k_v^2V_{i}^2, \forall j \in N_i\}.
\end{split}
\end{equation}

To guarantee $\mathcal{S}_i$ is forward-invariant and exponentially-stable, define the barrier function between agent $i$ and $j$ as:

\begin{equation}
\label{eqn_cbf_agenti}
h_{i,j}^{(1)}(x_i; x_j) = -k_v^2V_i^2 + (z_{i,1} - {z}_{j,1})^2 + (z_{i,2} - {z}_{j,2})^2.
\end{equation}

Taking the derivative of Eqn. (<ref>) yields:

\begin{equation}
\begin{split}
\dot{h}^{(1)}_{i,j}(x_i, u_i; x_j) &= -2k_v^2V_ia_i \\&+ 2(z_{i,1} - {z}_{j,1})V_i\cos(\psi_i + \gamma_i)\\& + 2(z_{i,2} - {z}_{j,2})V_i\sin(\psi_i + \gamma_i).
\end{split}
\end{equation}

Speeds $(\dot{z}_{j,1}, \dot{z}_{j,2})^\top$ are taken as constants, because if not, then the safety distance will be zero when the neighbors are moving at the same velocity, which is obviously against our common sense. This setting could also help prevent unforeseen accidents where the predecessor stops in a sudden (e.g., in a traffic pile-up).
We choose the class-$\mathcal{K}$ function as:

\begin{equation}
\kappa(h^{(1)}_{i,j}(\cdot)) = h^{(1)}_{i,j}(\cdot).
\end{equation}

Note that the bias term $w_i$ does not appear in the term $\dot{h}^{(1)}_{i,j}(\cdot)$. Therefore, the second order I-CBF must be applied. Define:

\begin{equation}
h^{(2)}_{i,j}(x_i, u_i; x_j) = \dot{h}^{(1)}_{i,j}(x_i, u_i; x_j) + h^{(1)}_{i,j}(x_i, u_i; x_j),
\end{equation}

\begin{equation}
\begin{split}
\dot{h}^{(2)}_{i,j}(x_i, u_i; x_j) = \dfrac{\partial h^{(2)}_{i,j}}{\partial x_i}\dot{x_i} + \dfrac{\partial h^{(2)}_{i,j}}{\partial u_i}\dot{u}_i,
\end{split}
\end{equation}

\begin{equation}
\dfrac{\partial h^{(2)}_{i,j}}{\partial x_i} = \begin{bmatrix}
2V_i\cos(\psi_i + \gamma_i) + 2(z_{i,1} - z_{j,1})\\2V_i\sin(\psi_i +\gamma_i) + 2(z_{i,2} - z_{j,2})\\-2k_v^2a_i - 2k_i^2V_i\\\left(\makecell{-2(z_{i,1} - z_{i,2})V_i\sin(\psi + \gamma_i) \\+ 2(z_{i,2} - z_{j,2})V_i\cos(\psi_i + \gamma_i)}\right)
\end{bmatrix}^\top,
\end{equation}

\begin{equation}
\dfrac{\partial h^{(2)}_{i,j}}{\partial u_i} = \begin{bmatrix}-2k_v^2V_i\\\left(\makecell{-2(z_{i,1} - z_{j,1})V_i\sin(\psi_i + \gamma_i) \\+ 2(z_{i,2} - z_{j,2})V_i\cos(\psi_i + \gamma_i)}\right)
\end{bmatrix}^\top,
\end{equation}

and $\dot{u}_i$, $\dot{x}_i$ follows input (<ref>) and dynamics (<ref>) respectively. The bias term $w_i$ appears as long as the vehicle's velocity $V_i$ is not zero. Therefore, we implicitly assume that the vehicles are always moving during the control period. The Quadratic Program associated with the I-CBF is:

\begin{equation}
\label{eqn_bicycle_qp_original}
\begin{split}
&\min_{w_i} \Vert w_i\Vert^2\\
\text{s.t.}\ &\dot{h}^{(2)}_{i,j}(x_i, u_i; x_j) + h^{(2)}_{i,j}(x_i,u_i;x_j) \geq 0, \forall j \in N_i.
\end{split}
\end{equation}

For this particular kinematic bicycle system, we noticed that if the solution of $w_i$ from (<ref>) is applied, then the bicycles may diverge excessively from its original trajectory. The reason is because the vehicle system (<ref>) is more sensitive to the steering wheel angle $\gamma_i$ instead of the acceleration $a_i$. In other words, a slight change in $\gamma_i$ may result in a huge change on the vehicle's path. To avoid such situation, we add weights to (<ref>), yielding a weighted quadratic program:

\begin{equation}
\begin{split}
&\min_{w_i}\ w_i^\top Qw_i\\
\text{s.t.}\ &\dot{h}^{(2)}_{i,j}(x_i, u_i; x_j) + h^{(2)}_{i,j}(x_i,u_i;x_j) \geq 0, \forall j \in N_i
\end{split}
\end{equation}

where $Q = \text{diag}(q_1, q_2)$ is a diagonal positive definite matrix, and $q_2 > q_1$. Since the constraints on $h_{i,j}^{(2)}(\cdot)$ didn't change, the safety requirements can still be satisfied.

§ SIMULATION RESULTS

In this section, we test our proposed consensus controller through a leader-follower consensus control problem consisting six agents. The followers, $A_1, A_2, \hdots, A_5$, are kinematic bicycles following the dynamics of (<ref>). The leader, $A_0$, is a virtual agent represented by an external reference signal. The system parameters of the followers are listed in Table <ref>, and their inputs are restricted by $a_i\in[-2,2] (m/s^2)$ and $\gamma_{i} \in [\frac{\pi}{6}, \frac{\pi}{6}] (rad)$ for $i = \{1,2,3,4,5\}$. A path graph is used to describe the agents' communication, as is in Fig. <ref>.

Agent Number    1   2   3   4   5
$L_f$   1.105   1.2   1.5   1.2   1.3
$L_r$   1.738   1.7   1.3   1.4   1.3

System parameters of five kinematic bicycles

The reference signal (leader) is specified by:

\begin{equation}
r(t) = \begin{cases}
(-50 + 3.75t, -60 + 4.5t)^\top, t \in [0,\frac{40}{3}]\\

\big(350\sin(0.01(t - \frac{40}{3})), 210\sin(0.02(t-\frac{40}{3}))\big)^\top, \\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~t \in [\frac{40}{3}, \infty).
\end{cases}
\end{equation}

At time $0$, the five agents are arranged in a straight line. The initial locations of the five bicycles are $(-50,-60)$, $(-60,-72)$, $(-70, -84)$, $(-80, -96)$ and $(-90, -108)$, respectively. The controller speedup parameters are $\alpha_i = 10$ for $i = 1,2,\hdots,5$, and the lookahead time horizon is $T = 0.3$.

The communication graph of the multi-agent system.

The Integral Control Barrier Function applied by agent $A_i, i = 2,3,4,5,$ considers both its successor $A_{i+1}$ and predecessor $A_{i-1}$ (if exists). However, the first agent $A_1$, considers only its successor $A_2$, because the leader $A_0$ is virtual and thus cannot be crashed. The minimal distance that the I-CBF attempts to maintain is chosen to be two times of the agents velocity, indicating $k_v = 2s$. To avoid excessive modifications to the bicycle's steering wheel, the weight matrix is designed as $Q = \text{diag}(1, 999)$. The simulation is carried out using the Forward-Euler method, starting from $t_s = 0s$ until $t_f = 680s$. The simulation stepsize is $0.01s$. The output prediction, $g_i(x_i,u_i; t+T)$, and its partial derivative, $\dfrac{\partial g_i}{\partial u_i}(x_i, u_i; t+T)$, are calculated using explicit Runge-Kutta method of order 5(4) (RK45) using the predictor described in [9]. The trajectories of the agents in the 2-D plain are illustrated in Fig. <ref>. The initial positions of the vehicles are marked with "x", and the finial positions are marked with dots.

The trajectory of the agents in the bicycle platoon

The distances between two adjacent agents, together with the minimal safety distances defined by (<ref>), are shown in Fig. <ref>. It is shown that the agents' inter-agent distances are always larger than the minimal safety distances, maintaining a headway time of more than two seconds. In real-world driving scenario, this distance allows at least two seconds for the drivers to react if the vehicle in the front stops in a sudden. It is also observed that the inter-agent distances are varying according to the vehicle's velocities, and the minimal and maximal distances appear when the vehicles have the minimal and maximal velocities, respectively.

The distance between two adjacency agents in the bicycle platoon

The input $\gamma_i(t)$ of each agent in the platoon

The agents'  steering angles $\gamma_i(t)$ are shown in Fig. <ref>, while their accelerations $a_i(t)$ are shown in Fig. <ref>. At the beginning of the simulation, the controller exerts large accelerations to reduce inter-agent distances and achieve consensus, leading to initial transients in the inputs. Throughout the simulation, each agent activates the Integral Control Barrier Function for five times. The first activation happens at the beginning when the agents get closed enough, and the following four cases correspond to the four turnings in the vehicles trajectory. Due to the coupling of two neighboring agents, slight input oscillations can be observed in the system inputs when the I-CBF is activated.

The input $a_i(t)$ of each agent in the platoon

§ CONCLUSION

In this paper, we proposed a consensus controller for multi-agent systems that can also guarantee safety. The consensus control is achieved using output prediction and Newton-Raphson method, and the safety is provided by using the Integral Control Barrier Function. Compared to traditional Control Barrier Functions, the Integral Control Barrier Function is native to the dynamically-defined consensus controller, yielding Quadratic Programs even for nonlinear non-control-affine systems. We applied the proposed consensus controller on a platoon of autonomous vehicles. The vehicles are described by nonlinear kinematic bicycles, and the communication topology is modeled by a path graph. For this special structure, we prove the asymptotic convergence of the leader-follower consensus. Simulation results show that the vehicles can maintain a suitable safety distance while keeping consensus. This approach may have a potential in the control of autonomous vehicles and other similar multi-agent systems.

[1]
M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in Multiagent Networks, Princeton University Press, 2010.
[2]W. Ren, “Distributed leaderless consensus algorithms for networked Euler–Lagrange systems,” Int. J. Control, vol. 82, no. 11, pp. 2137–2149, 2009.

[3]Z. Ding, "Consensus Output Regulation of a Class of Heterogeneous Nonlinear Systems,"  IEEE Transactions on Automatic Control, vol. 58, no. 10, pp. 2648-2653, 2013.

[4]Y. Yin, Y. Shi, F. Liu, K. L. Teo, and S. Wang, “Second-order consensus for heterogeneous multi-agent systems with input constraints,” Neurocomputing, vol. 351, pp. 43–50, 2019.

[5]X. Feng, Y. Yang, and D. Wei, “Adaptive fully distributed consensus for a class of heterogeneous nonlinear multi-agent systems,” Neurocomputing, vol. 428, pp. 12–18, 2021.

[6]J. An et al., “Decentralized adaptive control for quasi-consensus in heterogeneous nonlinear multiagent systems,” Discrete Dyn. Nat. Soc., vol. 2021, pp. 1–14, 2021.

[7]H. Xiao and C. L. P. Chen, "Leader-Follower Consensus Multi-Robot Formation Control Using Neurodynamic-Optimization-Based Nonlinear Model Predictive Control," IEEE Access, vol. 7, pp. 43581-43590, 2019.
[8]Y. Gao, L. Dai, Y. Xia, and Y. Liu, “Distributed model predictive control for consensus of nonlinear second-order multi-agent systems,” Int. J. Robust Nonlinear Control, vol. 27, no. 5, pp. 830–842, 2017.

[9] K. Niu, Y. Wardi, C. T. Abdallah and M. Hayajneh, "Consensus Controller for Heterogeneous Multi-Agent Systems Using Output Prediction," in IEEE Control Systems Letters, vol. 7, pp. 673-678, 2023, doi: 10.1109/LCSYS.2022.3217160.

[10]V. Milanés, S. E. Shladover, J. Spring, C. Nowakowski, H. Kawazoe and M. Nakamura, "Cooperative Adaptive Cruise Control in Real Traffic Situations," in IEEE Transactions on Intelligent Transportation Systems, vol. 15, no. 1, pp. 296-305, Feb. 2014, doi: 10.1109/TITS.2013.2278494.

[11]V. L. Bageshwar, W. L. Garrard and R. Rajamani, "Model predictive control of transitional maneuvers for adaptive cruise control vehicles," in IEEE Transactions on Vehicular Technology, vol. 53, no. 5, pp. 1573-1585, Sept. 2004, doi: 10.1109/TVT.2004.833625

[12]J. Kong, M. Pfeiffer, G. Schildbach and F. Borrelli, "Kinematic and dynamic vehicle models for autonomous driving control design," 2015 IEEE Intelligent Vehicles Symposium (IV), Seoul, Korea (South), 2015, pp. 1094-1099, doi: 10.1109/IVS.2015.7225830.

[13]J. Wu, Y. Wang, L. Wang, Z. Shen, and C. Yin, “Consensus-based platoon forming for connected autonomous vehicles,” IFAC-PapersOnLine, vol. 51, no. 31, pp. 801–806, 2018.

[14]X. Qian, A. de La Fortelle and F. Moutarde, "A hierarchical Model Predictive Control framework for on-road formation control of autonomous vehicles," 2016 IEEE Intelligent Vehicles Symposium (IV), Gothenburg, Sweden, 2016, pp. 376-381, doi: 10.1109/IVS.2016.7535413.

[15]A. Khalifa, O. Kermorgant, S. Dominguez and P. Martinet, "Vehicles Platooning in Urban Environment: Consensus-based Longitudinal Control with Limited Communications Capabilities," 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, 2018, pp. 809-814, doi: 10.1109/ICARCV.2018.8581142.

[16]A. D. Ames, J. W. Grizzle and P. Tabuada, "Control barrier function based quadratic programs with application to adaptive cruise control," 53rd IEEE Conference on Decision and Control, Los Angeles, CA, USA, 2014, pp. 6271-6278, doi: 10.1109/CDC.2014.7040372.
[17]A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath and P. Tabuada, "Control Barrier Functions: Theory and Applications," 2019 18th European Control Conference (ECC), Naples, Italy, 2019, pp. 3420-3431, doi: 10.23919/ECC.2019.8796030.
[18]J. Seo, J. Lee, E. Baek, R. Horowitz and J. Choi, "Safety-Critical Control With Nonaffine Control Inputs Via a Relaxed Control Barrier Function for an Autonomous Vehicle," in IEEE Robotics and Automation Letters, vol. 7, no. 2, pp. 1944-1951, April 2022, doi: 10.1109/LRA.2022.3142408.

[19] Y. Wardi, C. Seatzu, J. Cortés, M. Egerstedt, S. Shivam, and I. Buckley, “Tracking control by the Newton–Raphson method with output prediction and controller speedup,” Int. J. Robust Nonlinear Control, 2023, doi: 10.1002/rnc.6976.

[20]K. Vogel, “A comparison of headway and time to collision as safety indicators,” Accid. Anal. Prev., vol. 35, no. 3, pp. 427–433, 2003.

[21]A. D. Ames, G. Notomista, Y. Wardi and M. Egerstedt, "Integral Control Barrier Functions for Dynamically Defined Control Laws," in IEEE Control Systems Letters, vol. 5, no. 3, pp. 887-892, July 2021, doi: 10.1109/LCSYS.2020.3006764.

§ APPENDIX

§.§ Proof of Lemma I

We first state the definition of $\alpha$-stability [9]. In the remainder of this appendix, $z(t)$ represents the trajectory (<ref>) of the multi-agent system, and $\mathcal{Z}$ represents all possible system trajectories. Define $\alpha_{\min} \triangleq \min \{\alpha_1, \alpha_2, \hdots, \alpha_K\}$.

Definition I: The multi-agent system (<ref>) with inputs (<ref>) is $\alpha$-stable on a closed set $\Gamma\subset\mathcal{Z}$ if there exists $\Bar{\alpha} >0$, and a continuous, monotonous non-decreasing function $\beta : \mathbb{R}^+\rightarrow\mathbb{R}^+$, such that for all $\alpha_{\min} > \Bar{\alpha}$, the system trajectory $z(t), \forall t \in [0,+\infty)$ is well-defined and satisfies:

* the partial Jacobian matrix $\dfrac{\partial g_i}{\partial u_i}(x_i, u_i)$ is non-singular;

* For every initial condition $z_0 = z(0) \in \Gamma$, the trajectory $z(t)$ is bounded by:

\begin{equation*}
~~~~~~~~~~~~~~~\sup_{t \in [0,\infty)}\Vert z(t)\Vert \leq \beta(\Vert z_0\Vert).~~~~~~~~~~~~~~~~~~~~\Box
\end{equation*}

The definition of the system trajectories and the $\alpha$-stability concerns only the agents controlled by (<ref>). This excludes the autonomous agent $A_0$ in the leader-follower consensus. The $\alpha$-stability of nonlinear systems has to be verified case-by-case, and a criterion for single-agent linear systems can be find in [19]. Based on $\alpha$-stability, Lemma I can be proved.

Proof of Lemma I: For $i = 0, 1,2,\hdots,K-1$, let:

\begin{equation}
V_i(z(t)) = \Vert g_i(x_i, u_i) - g_{i+1}(x_{i+1}, u_{i+1})\Vert^2.
\end{equation}

Each $V_i(z(t))$ measures the difference between two predictions of two neighboring agents. Let:

\begin{equation}
V(z(t)) = \dfrac{1}{2}\sum_{i = 0}^{K-1}V_i(z(t)).
\end{equation}

Taking the derivative of $V$ yields:

\begin{equation}
\begin{split}
&\dot{V}(z(t)) = \dfrac{1}{2}\sum_{i = 0}^{K-1}\dot{V}_i(z(t)),
\end{split}
\end{equation}

\begin{equation}
\begin{split}
\dot{V}_i(z(t)) = \langle &g_i(x_i, u_i)
- g_{i+1}(x_{i+1}, u_{i+1}),\\& \dot{g}_i(x_i, u_i) - \dot{g}_{i+1}(x_{i+1}, u_{i+1})\rangle.
\end{split}
\end{equation}

Gathering terms of two neighboring terms yields:

\begin{equation}
\begin{split}
&\dot{V}(z(t)) = \langle g_0(x_0, u_0) - g_1(x_1, u_1), \dot{g}_0(x_0, u_0)\rangle+  \\
&\sum_{i=1}^{K-1}\langle (g_i(x_i, u_i) - g_{i-1}(x_{i-1},u_{i-1}))+ \\&~~~~~~(g_{i}(x_i, u_i) - g_{i+1}(x_{i+1}, u_{i+1})), \dot{g}_i(x_i, u_i)\rangle+\\
&\langle g_{K}(x_K, u_K) - g_{K-1}(x_{K-1},u_{K-1}) , \dot{g}_K(x_K,u_K)\rangle.
\end{split}
\end{equation}

For $i = 1,2,3, \hdots, K-1$:

\begin{equation}
\begin{split}
\dot{g}_i(x_i, u_i) = \dfrac{\partial g_i}{\partial x_i}\dot{x}_i + \dfrac{\partial g_i}{\partial u_i}\dot{u}_i\\ = \dfrac{\partial g_i}{\partial x_i}\dot{x}_i -\alpha_i((g_i(x_i, u_i) - g_{i-1}(x_{i-1},u_{i-1})) \\ +(g_{i}(x_i, u_i) - g_{i+1}(x_{i+1}, u_{i+1}))).
\end{split}
\end{equation}

and for $i = K$:

\begin{equation}
\begin{split}
\dot{g}_K(x_K, u_K) = \dfrac{\partial g_K}{\partial x_K}\dot{x}_K -\alpha_K(g_K(x_K, u_K) \\- g_{K-1}(x_{K-1},u_{K-1})).
\end{split}
\end{equation}

\begin{equation}
\begin{split}
&\dot{V}(z(t)) = \nu_0(z(t)) + \sum_{i = 1}^{K-1} \nu_i(z(t)) + \nu_{K}(z(t)) -\\& \sum_{i = 1}^{K-1}\alpha_{i}\Vert (g_i(x_i, u_i) - g_{i-1}(x_{i-1}, u_{i-1}))\\&~~~~~~+(g_i(x_i, u_i) - g_{i+1}(x_{i+1}, u_{i+1}))\Vert^2 \\&~~
- \alpha_K\Vert g_K(x_K, u_K) - g_{K-1}(x_{K-1}, u_{K-1})\Vert^2,
\end{split}
\end{equation}

\begin{equation}
\begin{split}
\nu_0(z(t)) &= \langle g_0(x_0, u_0) - g_1(x_1, u_1), \dot{g}_0(x_0, u_0)\rangle\\
&\leq \Vert g_0(x_0, u_0) - g_1(x_1, u_1)\Vert \Vert \dot{g}_0(x_0, u_0)\Vert,
\end{split}
\end{equation}

\begin{equation}
\begin{split}
&\nu_i(z(t)) = \langle (g_{i}(x_i, u_i) - g_{i-1}(x_{i-1},u_{i-1})) \\&~(g_i(x_i,u_i) - g_{i+1}(x_{i+1}, u_{i+1})),\dfrac{\partial g_i}{\partial x_i}\dot{x}_i\rangle \\&\leq\Vert (g_i(x_i,u_i) - g_{i-1}(x_{i-1},u_{i-1})) \\&~~ + (g_i(x_i,u_i) - g_{i+1}(x_{i+1},u_{i+1}))\Vert\Vert \dfrac{\partial g_i}{\partial x_i}\dot{x}_i\Vert,\\
&~~~~~i = 1,2,3,\hdots, K-1,
\end{split}
\end{equation}

\begin{equation}
\begin{split}
\nu_K(z(t)) = \langle g_K(x_K,u_K) - g_{K-1}(x_{K-1}, u_{K-1}), \dfrac{\partial g_K}{\partial x_{K}}\dot{x}_K\rangle\\
\leq \Vert g_K(x_K,u_K) - g_{K-1}(x_{K-1}, u_{K-1})\Vert\Vert\dfrac{\partial g_K}{\partial x_K}\dot{x_K}\Vert.
\end{split}
\end{equation}

By Assumption II, Assumption III, and the assumed $\alpha$-stability, there exists $\eta > 0$, such that:

\begin{equation}
\sum_{i=0}^{K}\nu_{i}(z(t)) \leq \eta.
\end{equation}

\begin{equation}
\begin{split}
&\dot{V}(z(t)) \leq \eta -   \sum_{i = 1}^{K-1}\alpha_{i}\Vert (g_i(x_i, u_i) - g_{i-1}(x_{i-1}, u_{i-1}))+ \\&~~~~~~~~~~~~~~~~~~~~~~~~~(g_i(x_i, u_i)- g_{i+1}(x_{i+1}, u_{i+1}))\Vert^2 -\\& ~~~~~~~~~~~~~~\alpha_K\Vert g_K(x_K, u_K) - g_{K-1}(x_{K-1}, u_{K-1})\Vert^2.
\end{split}
\end{equation}

By dropping extra negative terms, we have:

\begin{equation}
\begin{split}
\dot{V}(z(t)) \leq \eta - \alpha_i\Vert &(g_i(x_i, u_i) - g_{i-1}(x_{i-1}, u_{i-1}))+ \\&(g_i(x_i, u_i)- g_{i+1}(x_{i+1}, u_{i+1}))\Vert^2,\\&i = 1,2,3,\hdots,K-1;
\end{split}
\end{equation}

\begin{equation}
\dot{V}(z(t)) \leq \eta - \alpha_K\Vert g_K(x_K, u_K) - g_{K-1}(x_{K-1}, u_{K-1})\Vert^2.
\end{equation}

Since $V(z(t))$ is positive definite, by the standard Lyapunov method, the local consensus error satisfies:

\begin{equation}
\lim\sup_{t\rightarrow\infty}(\eta - \alpha_{\min}\Vert \sum_{j \in N_i}(g_i(x_i,u_i) - g_j(x_j,u_j))\Vert^2) \geq 0,
\end{equation}
which indicates Eqn. (<ref>). $\blacksquare$

§.§ Proof of Proposition I

The proof of Proposition I requires the concept of rooted out-branching ([1], Definition 3.7).

Definition II: A directed graph is a rooted out-branching if:

* it does not contain a directed circle, and

* it has a vertex $V_r$, such that for every other vertex $V_i, r\not=i$, there exists a directed path from $V_r$ to $V_i$.

Denote the adjacency matrix of the communication graph $\mathcal{G}_L$ by $A \in \mathbb{R}^{(K+1)\times(K+1)}$, such that:

\begin{equation}
A_{i,j} = \begin{cases}
1, \text{directed edge $(V_{j-1}, V_{i-1})$ exists}\\0, \text{otherwise.}
\end{cases}
\end{equation}

The index of the vertex is $j-1,i-1$ because the agents are numbered from $0$ instead of $1$. The directed edge $(V_{j-1}, V_{i-1})$ exists if and only if $A_{i-1}$ can receive information from $A_{j-1}$. Denote the degree matrix of $\mathcal{G}$ by $D$, such that:

\begin{equation}
\begin{split}
D &= \text{diag}(d_1, d_2, d_3, \hdots, d_{K+1}),\
d_i = \sum_{j = 1}^{K+1}A_{i,j}.
\end{split}
\end{equation}

Denote the Laplacian of the graph $\mathcal{G}_L$ by $L \triangleq D - A$. Then the following results holds ([1], Proposition 3.8):

Lemma II: The directed graph $\mathcal{G}_L$ with $K+1$ nodes contains a rooted out-branching as a subgraph if and only if $\text{rank}(L) = K$. Moreover, if a rooted out-branching exists, then $\text{null}(L) = \text{span}(\mathbf{1}) \triangleq \text{span}([1,1,1,\hdots,1]^\top)$. $\Box$

Proof of Proposition I: By Eqn. (<ref>), since $\eta \not = \infty $, the local consensus error satisfies:

\begin{equation}
\label{eqn_local_error_inf}
\lim_{\alpha_{\min}\rightarrow\infty}\lim \sup_{t\rightarrow\infty} \Vert \sum_{j\in N_i} (\tilde{y}_i(t+T) - \tilde{y}_j(t+T))\Vert^2 = 0.
\end{equation}

Define $\tilde{Y} \triangleq [\tilde{y}_0(t+T)^\top,\tilde{y}_1(t+T)^\top,\hdots, \tilde{y}_n(t+T)^\top]^\top$, denote $I_{K+1}$ as the $(K+1)\times (K+1)$ identity matrix. Denote $\otimes$ as the Kronecker product.
Since Eqn. (<ref>) holds for all $i \in \{1,2,3,\hdots, K\}$, it follows:

\begin{equation}    \lim_{\alpha_{\min}\rightarrow\infty}\lim\sup_{t\rightarrow\infty} (L\otimes I_{K+1})\tilde{Y} = 0,
\end{equation}

which is:

\begin{equation}
\label{eqn_y_null_space}
\tilde{Y} \in \text{null}(L\otimes I_{K+1}).
\end{equation}

Observe that the linear graph $\mathcal{G}_L$ contains a rooted out-branching $V_0, V_1, \hdots, V_K$. By Lemma II and the properties of the Kronecker product, the null space of $L\otimes I_{K+1}$ is:

\begin{equation}
\text{span}(\mathbf{1}\otimes e_1, \mathbf{1}\otimes e_2, \hdots, \mathbf{1}\otimes e_{K+1}),
\end{equation}

where $e_i$ is the unit vector with the $i$-th element being $1$ and others being $0$. Therefore, Eqn. (<ref>) indicates:

\begin{equation}
\tilde{y}_0(t+T) = \tilde{y}_1(t+T) = \hdots = \tilde{y}_n(t+T),
\end{equation}

and thus Proposition I holds. $\blacksquare$


11institutetext: University of Maryland, College Park MD 20742, USA 11email:
<EMAIL_ADDRESS>22institutetext: HLTCOE. Johns Hopkins University,
Baltimore MD 21211, USA
22email:
{eugene.yang,lawrie,mcnamee,kenton,mayfield}<EMAIL_ADDRESS>
# Transfer Learning Approaches for Building Cross-Language Dense Retrieval
Models

Suraj Nair 1122 0000-0003-2283-7672 Eugene Yang 22 0000-0002-0051-1535
Dawn Lawrie 22 0000-0001-7347-7086 Kevin Duh 22 0000-0001-8107-4383
Paul McNamee 22 0000-0002-0548-5751 Kenton Murray 22 0000-0002-5628-1003 James
Mayfield 22 0000-0003-3866-3013 Douglas W. Oard 1122 0000-0002-1696-0407

###### Abstract

The advent of transformer-based models such as BERT has led to the rise of
neural ranking models. These models have improved the effectiveness of
retrieval systems well beyond that of lexical term matching models such as
BM25. While monolingual retrieval tasks have benefited from large-scale
training collections such as MS MARCO and advances in neural architectures,
cross-language retrieval tasks have fallen behind these advancements. This
paper introduces ColBERT-X, a generalization of the ColBERT multi-
representation dense retrieval model that uses the XLM-RoBERTa (XLM-R) encoder
to support cross-language information retrieval (CLIR). ColBERT-X can be
trained in two ways. In zero-shot training, the system is trained on the
English MS MARCO collection, relying on the XLM-R encoder for cross-language
mappings. In translate-train, the system is trained on the MS MARCO English
queries coupled with machine translations of the associated MS MARCO passages.
Results on ad hoc document ranking tasks in several languages demonstrate
substantial and statistically significant improvements of these trained dense
retrieval models over traditional lexical CLIR baselines.

###### Keywords:

CLIR, ColBERT, ColBERT-X, Dense Retrieval

##  1 Introduction

BERT-style neural ranking models that use cross-attention between query and
document terms [7, 16] define the state of the art for monolingual English
retrieval. Such models are typically used as rerankers in a retrieve-and-
rerank pipeline, due to the quadratic time and space complexity of self-
attention in the transformer architecture [30]. Reranking using these models
is effective but time-consuming, so the number of documents to be reranked
must be tuned to balance the trade-off between effectiveness and efficiency.
In contrast to the reranking approach, dense retrieval models encode query and
document representations independently and match them with custom similarity
functions (e.g., cosine similarity). Dense retrieval complements the lexical
first phase retrieval by using an approximate nearest neighbor search over
contextualized representations.

While the retrieve-and-rerank framework has been adapted and explored in
cross-language information retrieval (CLIR) [37, 11, 38, 3, 36], most
approaches translate queries into the language of the documents and perform
monolingual retrieval [28, 29]. Dense retrieval models, on the other hand,
remain under-explored in CLIR. In this work, we develop an effective dense
retrieval model for CLIR.

Dense retrieval models can be broadly categorized into two variants: single-
representation and multi-representation [15]. Single-representation models
encode queries and documents separately to create a single aggregate
representation. However, that can lead to loss of information. Multi-
representation models use multiple representations of queries and documents to
predict relevance. One such model is ColBERT [13], which computes a similarity
between each query term representation and each document term representation.
Yet ColBERT is exclusively monolingual. This paper presents ColBERT-X, a
generalization of the ColBERT approach that supports CLIR. ColBERT-X uses a
translate and train fine-tuning approach to exploit existing CLIR training
resources.

This generalization poses two challenges: enabling the encoders to process
multiple languages, and identifying appropriate resources with which to train
the model. To address the former, we adapt XLM-R [5], a multilingual
pretrained transformer language model, to initialize the dense retrieval
model. For the latter challenge, we use translations of MS MARCO [2], a
widely-used passage ranking collection for training monolingual neural
retrieval models.

We evaluate ColBERT-X on ad hoc document ranking tasks using English queries
to retrieve documents in other languages, exploring two ways to cross the
language barrier. In the zero-shot setting, where we lack cross-language
training resources, we train the model only on English MS MARCO. In the
translate-train setting, the model is trained on machine-generated
translations of MS MARCO passages paired with English queries. This paper
additionally investigates the effect of machine translation on ColBERT-X
retrieval results.

Our main contributions can be summarized as follows:

  * •

We generalize ColBERT to support CLIR and develop a fine-tuning task that
leverages translations of existing monolingual retrieval collections.

  * •

We demonstrate significant effectiveness gains over query translation
baselines on news in several languages, showing the ability of term-level
Approximate Nearest Neighbor (ANN) search to overcome vocabulary mismatch.

  * •

We analyze components of ColBERT-X and techniques to improve effectiveness,
including effects of different machine translation models, alternative
multilingual encoders, and relevance feedback.

  * •

We release our code to train and evaluate ColBERT-X, and our new machine
translations of MS MARCO into Chinese, Persian and
Russian.111https://github.com/hltcoe/ColBERT-X

##  2 Related Work

In this section, we briefly review related work on neural retrieval and its
extension to cross-lingual settings. For many years, sparse retrieval models
such as BM25 [26] and Query Likelihood [24] were the dominant models for ad
hoc retrieval tasks. Only in recent years, with the rise of BERT [7] and the
availability of large scale retrieval collections such as MSMARCO [2] for
training, have neural information retrieval (neural IR) models emerged as the
state of the art.

Similar to sparse retrieval models, neural IR models take as input the query
and documents, and produce a relevance score. For each query and document
pair, matching mechanisms, such as DRMM [9], KNRM [6] or PACCR [10], construct
the interaction matrix between the distributed term representations of the
query and the documents, and aggregate them into a relevance score.
Alternatively, the BERT passage pair classification model [7] considers the
query and the document as the input pair, and uses the final classification
score as the relevance score [35]. CEDR [18] incorporates contextualized
embeddings such as ELMo [23] or BERT [7] into the matching, providing
significant effectiveness improvements by taking advantage of
contextualization. However, due to the high computational cost, these models
are used to rerank top-ranked documents from a sparse retrieval system.

ColBERT [13] further improves efficiency by keeping separate the query-
document interaction until the end of the neural architecture. This is called
late interaction. As opposed to matching mechanisms that require both the
query and the document to be present simultaneously, late interaction allows
offline encoding of the documents into bags-of-vectors. Document
representations are combined with query representations by an efficient MaxSim
operator, which significantly reduces computation at inference time. This
decoupling enables the documents to be encoded offline and indexed to support
approximate nearest neighbor search. Further details are discussed in Section
3.

Cross-language transfer learning is important for CLIR. Due to the lack of
training data for ad hoc neural retrieval models other than in English, prior
work explored zero-shot model transfer to other languages, trained with only
English retrieval examples [17, 28]. Model initialization with a multilingual
language model such as mBERT [7] has been shown to be effective in zero-shot
evaluations. However, this approach requires both queries and documents to be
in the same language, resulting in evaluation based either on monolingual non-
English retrieval [17], or on query translation into the target language [28].

With the availability of translations of the widely-used English ad hoc
retrieval resource MS MARCO [4], translate-train (training the retrieval model
on a translated collection) using large ad hoc retrieval collections becomes
feasible. Prior work explored a dense retrieval approach to translate-train,
showing effectiveness gains on monolingual non-English retrieval tasks [29].
However, this approach relied on a single-representation dense retrieval model
with an mBERT encoder, combined with sparse retrieval methods such as BM25.
Lacking an end-to-end CLIR dense retrieval model that does not require the
help of a sparse retrieval system, we bridge the gap by generalizing ColBERT
to support directly querying non-English documents with English queries.

##  3 ColBERT-X

ColBERT is a multi-stage dense retrieval model that uses monolingual BERT [7]
to encode both query and document terms. It employs a late-interaction
mechanism, MaxSim, that computes the similarity between the encoded query and
document term representations. Computing MaxSim for every query and document
term pair in the collection is not feasible, so ColBERT has two ways to reduce
the number of required similarity comparisons: reranking or end-to-end
retrieval. In reranking, a retrieval system such as BM25 generates an initial
ranked list, which is then reranked using ColBERT’s MaxSim operation. The
disadvantage of such a cascaded pipeline is that the overall recall of the
system is limited to the recall of the initial ranked list. In the context of
CLIR systems, we face the additional complexity of crossing the language
barrier that further affects recall. We thus restricted our work to end-to-end
(E2E) retrieval.

In the first stage of the E2E setting, a candidate set of documents is
generated by ANN search using every query term. Specifically, the k nearest
document tokens are retrieved from the ANN index for every query term
representation. These tokens are mapped to document IDs, and the union of
these IDs creates the final set of candidate documents. In the next stage,
these documents are reranked using the late-interaction “MaxSim” operation.
For every query term, MaxSim finds the closest document token using the dot
product of the encoded query and document term representation. The final score
of the document is the summation of individual query term contributions, as
shown in Equation 1. $\eta$ denotes the monolingual BERT encoder.

$s_{q,d}=\sum_{i=1}^{|q|}\max_{j=1..|d|}\eta(q_{i})\ .\ \eta(d_{j})^{T}$ (1)

To generalize ColBERT to CLIR, we replaced monolingual BERT with XLM-R. We
call the resulting model ColBERT-X. Initializing the encoder to a multilingual
model allows retrieval in any language supported by the embeddings. However,
these models must be trained before they can be used for CLIR.

###  3.1 CLIR Training Strategies

Figure 1:  Two ColBERT-X Transfer Learning Pipelines: Zero-Shot (left) and
Translate-Train (right). Dashed boxes denote components used during the
training step. In zero-shot, ColBERT-X trained on English MS MARCO is applied
on the machine translated queries. With translate-train, the training set
consists of translated passages to enable ColBERT-X to cross the language
barrier.

ColBERT was trained using pairwise cross-entropy loss on MS MARCO [2] triples,
which consist of an English query, a relevant English passage, and a non-
relevant English passage. To train ColBERT-X for CLIR, we explored two
strategies from the cross-language transfer learning literature:

  1. 1.

Zero-Shot: This is a common technique in which a multilingual model (e.g.,
mBERT or XLM-R) is trained in a high-resource language (usually English) and
then applied to the document language. In this paper, we first train a
ColBERT-X model initialized with an XLM-R encoder on English MS MARCO passage
ranking triples. At query time, we use machine translation (MT) to translate
the English query to the document language, and use the trained ColBERT-X
model to perform retrieval in the document language using Equation 2.
$\hat{q}$ is the translated query. Multilingual language models have
demonstrated good cross-language generalization in many other natural language
processing tasks; we hypothesized it would also work well for CLIR.

$s_{\hat{q},d}=\sum_{i=1}^{|\hat{q}|}\max_{j=1..|d|}\eta(\hat{q}_{i})*\eta(d_{j})$
(2)

  2. 2.

Translate-Train: In this setting, an existing high-resource language (e.g.,
English) collection is translated to the document language. As in zero-shot
training, we choose training triples from the MS MARCO passage ranking
collection and use a trained MT model to translate them. Since our focus here
is using English queries to retrieve content in non-English languages, we pair
the original English queries with machine translations of relevant and non-
relevant MS MARCO passages to form new triples.222If we had wanted to
experiment with using non-English queries to find English content, we could
have instead translated only the MS MARCO queries. We then train ColBERT-X on
these newly constructed triples in the same manner as ColBERT.

Figure 1 shows these two pipelines. The key difference is that in the zero-
shot setting we have a single ColBERT-X model for a given query language (in
this case English) that is used for retrieval in multiple document languages.
In the translate-train setting, we train a ColBERT-X model for each query-
document language pair. We might also combine translations in multiple
languages to train a single multilingual ColBERT-X model, but we leave that
for future work.

###  3.2 Retrieval

While we train ColBERT-X on passages, our goal is to rank documents. We split
large documents into overlapping passages of fixed length with a stride.
During indexing, we use the trained ColBERT-X model to generate term
representations from these passages. These representations are stored in a
FAISS-based ANN index [12] and are saved to disk for subsequent MaxSim
computation. At query time, we use the trained ColBERT-X model to generate a
ranked list of passages for each query using the approaches discussed in the
section above and then use a document’s maximum passage score as its document
score.

##  4 Experiments

####  4.0.1 Collection Statistics.

Table 1 provides details for the test collections used in our experiments. We
worked with several languages from the 2000 to 2003 Cross-Language Evaluation
Forum (CLEF) evaluations [22], using ad hoc news collections for French,
German, Italian, Russian and Spanish. We also conducted experiments using the
new CLIR Common Crawl Collection (HC4) [14], where the documents are newswire
articles from Common Crawl in Chinese or Persian. Throughout, English queries
are used to search a collection in a non-English language. We experiment with
title and description queries. The MS MARCO [2] passage ranking dataset, which
we use for training ColBERT-X, consists of roughly 39M training triples,
spanning over 500k queries and 8.8M passages.

Table 1: Test collection statistics for the CLEF and HC4 newswire collections. Collection | HC4 | HC4 | CLEF | CLEF | CLEF | CLEF | CLEF
---|---|---|---|---|---|---|---
Chinese | Persian | French | German | Italian | Russian | Spanish
#documents | 646K | 486K | 129k | 294k | 157k | 16k | 454k
#passages | 3.6M | 3.1M | 0.7M | 1.6M | 0.8M | 0.1M | 2.7M
#queries | 50 | 50 | 200 | 200 | 200 | 62 | 160

####  4.0.2 ColBERT-X Training and Retrieval.

Our two ColBERT-X model strategies, zero-shot (ZS) and translate-train (TT),
are trained using mostly the same hyperparameters used to train the original
ColBERT model.333We increase our batch size from 32 to 128. We replaced the
BERT encoder with the XLM-RoBERTa (large) encoder provided by the HuggingFace
transformers [33] library (but see Section 5.2 for mBERT results). To generate
passages from documents, we use a passage length of 180 tokens with a stride
of 90 tokens. We index these passages using the trained ColBERT-X model in the
same way as the original ColBERT model in the E2E
setting.444https://github.com/stanford-futuredata/ColBERT#indexing

####  4.0.3 Machine Translation.

For CLEF languages, we use MS MARCO passage
translations555https://github.com/unicamp-dl/mMARCO from Bonifacio et al. [4],
and the same MT model to translate queries. For the HC4 languages, we use
directional MT models built on top of a transformer base architecture (6-layer
encoder/decoder) using Sockeye [8]. To produce translations of MS MARCO, the
original passages were split using ersatz [32], and sentence-level translation
was performed using the trained MT model.

####  4.0.4 Baselines.

We compare these strategies with several baselines:

  * •

Human Translation: Monolingual retrieval using Anserini BM25 [34] with the
document-language queries provided in the test collection.

  * •

Query Translation: BM25 retrieval using translated queries produced by a
specific MT model and original documents in the target language.666To compare
the retrieval models fairly, we use the same MT model to translate the queries
as the one used to translate the MS MARCO passages.

  * •

Reranking: We rerank query translation baseline results using the public mT5
reranker777https://huggingface.co/unicamp-dl/mt5-base-multi-msmarco trained on
translated MS MARCO in 8 languages [4].

####  4.0.5 Evaluation.

We evaluate ranking using Mean Average Precision (MAP). Differences in means
are tested for significance using a paired t-test (p$<$0.05) with Holm-
Bonferroni multiple test correction.

Table 2:  Effectiveness results (mean average precision) for CLIR HC4 and CLEF
collections using title queries. Statistically significant improvements over
the query translation and reranking baselines are marked with ∗ and †
respectively. Bold indicates best MAP among the query translation and
reranking methods.

Collection($\rightarrow$) Model($\downarrow$) |  HC4 Chinese |  HC4 Persian |  CLEF French |  CLEF German |  CLEF Italian |  CLEF Russian |  CLEF Spanish
---|---|---|---|---|---|---|---
human translation
BM25 | 0.301 | 0.276 | 0.403 | 0.304 | 0.350 | 0.452 | 0.452
ColBERT-X (ZS) | 0.510 | 0.343 | 0.401 | 0.360 | 0.328 | 0.479 | 0.418
query translation
BM25 | 0.237 | 0.211 | 0.387 | 0.263 | 0.275 | 0.377 | 0.405
reranker
BM25+mT5-multi | 0.312 | - | 0.333 | 0.297 | 0.279 | 0.303 | 0.370
our methods |  |  |  |  |  |  |
ColBERT-X (ZS) | 0.450∗† | 0.297∗ | 0.382† | 0.328∗† | 0.272 | 0.418† | 0.379
ColBERT-X (TT) | 0.408∗† | 0.310∗ | 0.422† | 0.397∗† | 0.339∗† | 0.410† | 0.415†

####  4.0.6 Results.

Table 2 compares the effectiveness of our models to the baselines. Our main
finding is that both ColBERT-X variants perform better than BM25 query
translation in general. ColBERT-X trained using English MS MARCO alone
performs better than query translation and fine-tuning ColBERT-X on translated
MS MARCO data helps improve effectiveness further. These gains are
statistically significant in both HC4 collections, and for many CLEF
collections.

We also compare the ColBERT-X variants to the multilingual T5 reranker that
reranks the query translation baseline output. In each collection, ColBERT-X
performs consistently and significantly better than the reranker. This is
particularly interesting in CLEF collections since both the mT5 reranker and
ColBERT-X (TT) were trained on the same MS MARCO translations. However, the
reranker was trained on a combined dataset in 8 languages, which might point
to the curse of multilinguality [5].

When we compare the two variants of ColBERT-X, we observe that on average
translate-train often does better than zero-shot, but these differences are
only significant in CLEF collections except Russian and not in HC4
collections. The difference is likely a result of using different MT models in
CLEF and HC4 collections, so we conduct further analysis in the next section.

##  5 Detailed Analysis

This section considers several aspects of ColBERT-X. First, different machine
translation models are compared using both MT and CLIR measures. Second,
effects of different multilingual encoders are explored. Third, the impact of
pseudo-relevance feedback is examined. Then the influence of query length on
performance is considered. Finally, ColBERT-X costs in terms of index size are
noted.

###  5.1 Effect of Machine Translation

ColBERT-X utilizes machine translation in two different ways depending on
whether it is trained using the zero-shot strategy or the translate-train
strategy. In the zero-shot strategy, the queries are translated to the
document language at query time, while the translate-train strategy requires
an MT system to translate the monolingual training corpus (in this case, the
MS MARCO passages) to the document language. The MT systems used to produce
translations include:

  * •

OpusMT – bidirectional MT model(s) with MarianNMT as the base
architecture,888https://huggingface.co/Helsinki-NLP released by the Helsinki
NLP group from Bonifacio et al. [4].

  * •

SockeyeMT1 – MT model built on top of a transformer base architecture (6-layer
encoder/decoder) trained on bitext. Depending on language, these include
publicly available bitext such as OpenSubtitles, UN Corpus, Europarl, and WMT.
The model is trained using AWS Sockeye v2 [8].

  * •

SockeyeMT2 – identical model to SockeyeMT1 but trained with 2x–3x more bitext.
The number of training sentence pairs for MT1 vs MT2 are 51M vs 120M for
Russian, 36M vs 85M for Chinese, and 6M vs 11M for Persian.

Table 10 provides an intrinsic comparison of the systems translating from
English on a translation task using BLEU scores [21]. For Russian and Chinese
we evaluated using a recent WMT shared task (newstest’19); for Persian we
evaluated with a collection of around 3000 sentences about COVID-19, as no WMT
test is available. Scores were calculated with sacrebleu [25] using the -lc
setting. The table reveals that SockeyeMT outputperforms OpusMT and that
exposing SockeyeMT to more training data improves the BLEU score.

Table 3: BLEU scores for translation systems using WMT’19 newstest for Chinese and Russian, and TICO-19 (from OPUS101010https://opus.nlpl.eu/) for Persian. These are computed on test sets distinct from the CLIR collections, so absolute BLEU score is not an exact reflection of quality of translations in CLIR experiments. Nevertheless, relative comparison of BLEU scores among MT systems is meaningful. | Language
---
Benchmark
| Russian
---
newstest’19
| Chinese
---
newstest’19
| Persian
---
tico-19
OpusMT | 26.3 | 14.6 | -
SockeyeMT1 | 32.1 | 25.8 | 4.4
SockeyeMT2 | 35.9 | 38.6 | 20.2

Table 4 shows that improving BLEU scores likely leads to improvements in CLIR
for both training strategies. Table 4(a) shows the results of translating
queries in the zero-shot strategy. While BLEU improvements tend to be realized
downstream, this is not seen for HC4 Chinese where OpusMT has better MAP than
SockeyeMT1. Note that asking MT to translate keyword queries may not align
well with how the systems were trained with complete sentences.

Table 4(b) shows results for using different translation models on MS MARCO
triples, and the effect this has on ColBERT-X retrieval as measured using MAP.
Again, we see that the MAP scores tend to improve with improved BLEU; however,
in this case the improvement in Russian BLEU from Table 10 between SockeyeMT1
and SockeyeMT2 does not carry over to ColBERT-X, where the performance is
essentially the same. Generally, one can expect that improving MT quality will
lead to improved effectiveness of ColBERT-X.

###  5.2 Effect of Multilingual Language Models

Comparing different multilingual encoders to initialize ColBERT-X, we observe
that XLM-R performs significantly better than mBERT, as shown in Table 5.
While this might be unsurprising given that the XLM-R model is twice as large
and was pretrained on more data than mBERT, tokenization differs across the
languages. Considering the case of Chinese, mBERT tokenization produces
character-level tokens, whereas the XLM-R tokenizer generates subwords
(sentencepieces). This also implies that mBERT indexes are larger than XLM-R
indexes, resulting from the term-level storage requirements of ColBERT-X
model.

Table 4: MAP using different MT models for ColBERT-X.

| MT
---
model
| CLEF
---
Russian
| HC4
---
Chinese
| HC4
---
Persian
OpusMT | 0.418 | 0.411 | -
SockeyeMT1 | 0.442 | 0.391 | 0.230
SockeyeMT2 | 0.461 | 0.450 | 0.297
(a) ColBERT-X zero-shot

| MT
---
model
| CLEF
---
Russian
| HC4
---
Chinese
| HC4
---
Persian
OpusMT | 0.410 | 0.365 | -
SockeyeMT1 | 0.459 | 0.389 | 0.287
SockeyeMT2 | 0.456 | 0.408 | 0.310
(b) ColBERT-X translate-train

Table 5: MAP scores for ColBERT-X initialized with the mBERT and XLM-R encoders, and trained on SockeyeMT1 MS MARCO translations.  | Multilingual
---
Model
| CLEF
---
Russian
| HC4
---
Chinese
| HC4
---
Persian
mBERT | 0.341 | 0.284 | 0.173
XLM-R | 0.459∗ | 0.389∗ | 0.287∗

###  5.3 Pseudo-Relevance Feedback

Pseudo-relevance feedback (PRF) is a form of query expansion that adds
discriminative terms extracted from retrieved documents. While PRF has been
explored for pre and post translation query expansion [19], here we choose
cross-language expansion terms using the ColBERT-X term representation, as
suggested by Wang et al [31]. First, feedback documents (fb-docs) are selected
from the top of a ColBERT E2E ranked list. Next, embeddings of terms from the
feedback documents are clustered into $k$ clusters. The top ranked centroids
of these $k$ clusters111111Each centroid is mapped to the nearest document
token using the ANN index. by token IDF are used as feedback embeddings (fb-
embs). These fb-embs are added to the original query and ColBERT E2E is run
again to produce the final ranked list. We extend this approach to the
ColBERT-X CLIR setting.

To better understand the effect of PRF, we compare ColBERT-X translate-train
and query translation BM25, with and without PRF. For BM25, we use Anserini’s
RM3 to perform PRF, with default hyperparameters. For ColBERT-X PRF, we extend
Terrier’s [20]
implementation121212https://github.com/terrierteam/pyterrier_colbert with
default hyperparameters. Table 6 shows the effect of PRF on ColBERT-X
translate-train MAP. Except in Spanish, applying PRF to ColBERT-X
significantly improves effectiveness compared to ColBERT-X without PRF or
compared to BM25 with PRF.

Table 6: MAP for query translation BM25 and ColBERT-X translate-train. ∗ or † denote significant improvement over BM25+PRF or ColBERT-X respectively | Retrieval
---
Model
| CLEF
---
French
| CLEF
---
German
| CLEF
---
Italian
| CLEF
---
Spanish
baseline
BM25 | 0.387 | 0.263 | 0.275 | 0.405
ColBERT-X | 0.422 | 0.397 | 0.339 | 0.415
with PRF
BM25 | 0.410 | 0.321 | 0.320 | 0.438
ColBERT-X | 0.459∗† | 0.406∗† | 0.371∗† | 0.436†

###  5.4 Effect of Longer Queries

Table 7 analyzes the effect of query type on ColBERT-X translate-train. We
compare three representations: title (t), which is a short Web-like query;
description (d), a well-formed sentence describing the information need, and
title+description (td), the concatenation of the two. Longer queries pose a
problem for ColBERT-X, however, since the model only supports queries up to 32
tokens long. To mitigate this problem, we use a list of “stop structures”[1]
consisting of phrases (e.g., find documents on, reports of, etc.), which have
been shown to work in the past, removing them from the td queries. We observe
that td with stop structures removed leads to significant improvements over t
or d alone.

Table 7: MAP results for ColBERT-X (TT) model using different query representations. ∗ and † denote significant improvements over t and d queries respectively. | Query
---
Representation
| CLEF
---
French
| CLEF
---
German
| CLEF
---
Italian
| CLEF
---
Spanish
title | 0.422 | 0.397 | 0.339 | 0.415
description | 0.434 | 0.410 | 0.380 | 0.456
title+description | 0.507∗† | 0.466∗† | 0.424∗† | 0.500∗†

###  5.5 Indexing Footprint

In addition to the FAISS-based ANN index, ColBERT-X requires access to the
representation of each term to compute MaxSim. With each term embedded as a
128-dimensional vector and each dimension using 16-bits, that’s 256 bytes per
term. These are onerous requirements, with index size increasing with
collection size. Table 8 provides statistics on storage requirements.
ColBERTv2 [27] addresses this issue by clustering token embeddings. That
approach could be extended to ColBERT-X for CLIR; we leave it for future work.
An artifact of our design that affects index size is how passages are
generated. We use a sliding window of document tokens, so most tokens have two
representations. In the future, we will explore the effects of alternative
document segmentation approaches.

Table 8: Collection-specific memory footprint. | Collection
---
| HC4
---
Chinese
| HC4
---
Persian
| CLEF
---
French
| CLEF
---
German
| CLEF
---
Italian
| CLEF
---
Russian
| CLEF
---
Spanish
#passages | 3.6M | 3.1M | 0.7M | 1.6M | 0.8M | 0.1M | 2.7M
Disk Space | 154GB | 134GB | 33GB | 70GB | 36GB | 4.7GB | 117GB

##  6 Conclusion

We have developed ColBERT-X, a cross-language generalization of ColBERT that
uses a multilingual query and document encoder to improve CLIR beyond what
traditional systems such as BM25 can achieve. Using MT systems to translate MS
MARCO, we create CLIR collections for training ColBERT-X. We additionally
analyze the effect of MT on the CLIR task. In the future, we would like to
create a single multilingual model that is trained on the data from many
languages, and compare that with a separate models for each language. For
pseudo-relevance feedback, it is important to understand which type of queries
benefit from it; a per-query comparison could shed some light on that
question.

### Acknowledgments

This research is based upon work supported in part by the Office of the
Director of National Intelligence (ODNI), Intelligence Advanced Research
Projects Activity (IARPA), via contract # FA8650-17-C-9117. Views and
conclusions contained herein are those of the authors and should not be
interpreted as necessarily representing the official policies, expressed or
implied, of ODNI, IARPA, or the U.S. Government (USG). The USG is authorized
to reproduce and distribute reprints for governmental purposes notwithstanding
any copyright annotation therein.

## References

  * [1] Allan, J., Callan, J., Croft, W.B., Ballesteros, L., Byrd, D., Swan, R., Xu, J.: INQUERY does battle with TREC-6. NIST Special Publication 500-240 pp. 169–206 (1998)
  * [2] Bajaj, P., Campos, D., Craswell, N., Deng, L., Gao, J., Liu, X., Majumder, R., McNamara, A., Mitra, B., Nguyen, T., et al.: MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. arXiv preprint arXiv:1611.09268v3 (2018)
  * [3] Bonab, H., Sarwar, S.M., Allan, J.: Training effective neural CLIR by bridging the translation gap. In: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 9–18. Association for Computing Machinery, New York, NY, USA (Jul 2020)
  * [4] Bonifacio, L.H., Campiotti, I., Lotufo, R., Nogueira, R.: mMARCO: A multilingual version of MS MARCO passage ranking dataset. arXiv preprint arXiv:2108.13897 (2021)
  * [5] Conneau, A., Khandelwal, K., Goyal, N., Chaudhary, V., Wenzek, G., Guzmán, F., Grave, E., Ott, M., Zettlemoyer, L., Stoyanov, V.: Unsupervised cross-lingual representation learning at scale. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. pp. 8440–8451. Association for Computational Linguistics, Online (Jul 2020)
  * [6] Dai, Z., Xiong, C., Callan, J., Liu, Z.: Convolutional neural networks for soft-matching n-grams in ad-hoc search. In: Proceedings of the 11th ACM International Conference on Web Search and Data Mining. pp. 126–134 (2018)
  * [7] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171–4186. Association for Computational Linguistics, Minneapolis, Minnesota (Jun 2019)
  * [8] Domhan, T., Denkowski, M., Vilar, D., Niu, X., Hieber, F., Heafield, K.: The Sockeye 2 neural machine translation toolkit at AMTA 2020. In: Proceedings of the 14th Conference of the Association for Machine Translation in the Americas (Volume 1: Research Track). pp. 110–115. Association for Machine Translation in the Americas, Virtual (Oct 2020)
  * [9] Guo, J., Fan, Y., Ai, Q., Croft, W.B.: A deep relevance matching model for ad-hoc retrieval. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. pp. 55–64 (2016)
  * [10] Hui, K., Yates, A., Berberich, K., de Melo, G.: PACRR: A position-aware neural IR model for relevance matching. In: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. pp. 1049–1058. Association for Computational Linguistics, Copenhagen, Denmark (Sep 2017)
  * [11] Jiang, Z., El-Jaroudi, A., Hartmann, W., Karakos, D., Zhao, L.: Cross-lingual information retrieval with BERT. arXiv preprint arXiv:2004.13005 (Apr 2020)
  * [12] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. arXiv preprint arXiv:1702.08734 (2017)
  * [13] Khattab, O., Zaharia, M.: ColBERT: Efficient and effective passage search via contextualized late interaction over BERT. In: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 39–48. Association for Computing Machinery, New York, NY, USA (Jul 2020)
  * [14] Lawrie, D., Mayfield, J., Oard, D.W., Yang, E.: HC4: A new suite of test collections for ad hoc CLIR. In: Proceedings of the 44th European Conference on Information Retrieval (2021)
  * [15] Lin, J., Nogueira, R., Yates, A.: Pretrained transformers for text ranking: Bert and beyond. Synthesis Lectures on Human Language Technologies 14(4), 1–325 (2021)
  * [16] Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., Stoyanov, V.: Roberta: A robustly optimized BERT pretraining approach. arXiv preprint arXiv:1907.11692 (2019)
  * [17] MacAvaney, S., Soldaini, L., Goharian, N.: Teaching a new dog old tricks: Resurrecting multilingual retrieval using zero-shot learning. Advances in Information Retrieval p. 246 (2020)
  * [18] MacAvaney, S., Yates, A., Cohan, A., Goharian, N.: Cedr: Contextualized embeddings for document ranking. In: Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1101–1104 (2019)
  * [19] McNamee, P., Mayfield, J.: Comparing cross-language query expansion techniques by degrading translation resources. In: Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 159–166 (2002)
  * [20] Ounis, I., Amati, G., Plachouras, V., He, B., Macdonald, C., Johnson, D.: Terrier information retrieval platform. In: European Conference on Information Retrieval. pp. 517–519. Springer (2005)
  * [21] Papineni, K., Roukos, S., Ward, T., Zhu, W.J.: BLEU: a method for automatic evaluation of machine translation. In: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics. pp. 311–318. Association for Computational Linguistics, Philadelphia, Pennsylvania, USA (Jul 2002)
  * [22] Peters, C., Braschler, M.: European research letter: Cross-language system evaluation: The CLEF campaigns. Journal of the American Society for Information Science and Technology 52(12), 1067–1072 (2001)
  * [23] Peters, M.E., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., Zettlemoyer, L.: Deep contextualized word representations. In: Proceedings of NAACL-HLT. pp. 2227–2237 (2018)
  * [24] Ponte, J.M., Croft, W.B.: A language modeling approach to information retrieval. In: Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 275–281 (1998)
  * [25] Post, M.: A call for clarity in reporting BLEU scores. In: Proceedings of the Third Conference on Machine Translation: Research Papers. pp. 186–191. Association for Computational Linguistics, Brussels, Belgium (Oct 2018)
  * [26] Robertson, S.E., Walker, S., Jones, S., et al.: Okapi at TREC-3. In: Overview of the Third Text REtrieval Conference (TREC-3) (1995)
  * [27] Santhanam, K., Khattab, O., Saad-Falcon, J., Potts, C., Zaharia, M.: Colbertv2: Effective and efficient retrieval via lightweight late interaction. arXiv preprint arXiv:2112.01488 (2021)
  * [28] Shi, P., Lin, J.: Cross-lingual relevance transfer for document retrieval. arXiv preprint arXiv:1911.02989 (2019)
  * [29] Shi, P., Zhang, R., Bai, H., Lin, J.: Cross-lingual training with dense retrieval for document retrieval. arXiv preprint arXiv:2109.01628 (2021)
  * [30] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need. arXiv preprint arXiv:1706.03762 (2017)
  * [31] Wang, X., Macdonald, C., Tonellotto, N., Ounis, I.: Pseudo-relevance feedback for multiple representation dense retrieval. arXiv preprint arXiv:2106.11251 (2021)
  * [32] Wicks, R., Post, M.: A unified approach to sentence segmentation of punctuated text in many languages. In: Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). pp. 3995–4007. Association for Computational Linguistics, Online (Aug 2021)
  * [33] Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Le Scao, T., Gugger, S., Drame, M., Lhoest, Q., Rush, A.: Transformers: State-of-the-art natural language processing. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. pp. 38–45. Association for Computational Linguistics, Online (Oct 2020)
  * [34] Yang, P., Fang, H., Lin, J.: Anserini: Enabling the use of Lucene for information retrieval research. In: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1253–1256. SIGIR ’17, Association for Computing Machinery, New York, NY, USA (Aug 2017)
  * [35] Yang, W., Zhang, H., Lin, J.: Simple applications of BERT for ad hoc document retrieval. arXiv preprint arXiv:1903.10972 (2019)
  * [36] Yu, P., Allan, J.: A study of neural matching models for cross-lingual ir. In: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. p. 1637–1640. Association for Computing Machinery, New York, NY, USA (2020)
  * [37] Zhang, R., Westerfield, C., Shim, S., Bingham, G., Fabbri, A., Verma, N., Hu, W., Radev, D.: Improving low-resource cross-lingual document retrieval by reranking with deep bilingual representations. arXiv preprint arXiv:1906.03492 (2019)
  * [38] Zhao, L., Zbib, R., Jiang, Z., Karakos, D., Huang, Z.: Weakly supervised attentional model for low resource ad-hoc cross-lingual information retrieval. In: Proceedings of the 2nd Workshop on Deep Learning Approaches for Low-Resource NLP (DeepLo 2019). pp. 259–264. Association for Computational Linguistics, Hong Kong, China (Nov 2019)