betaFeedback

WorksEngineering

Control Barrier Functions for Counting Tasks in Multi-Agent Systems

Abstract

Multi-agent systems increasingly operate in dynamic environments and execute complex tasks that require coordination, posing significant computational challenges. Counting tasks, which require a minimum number of agents to satisfy a given condition, arise naturally in such systems. Examples include surveillance tasks, where at least m drones must continuously monitor a critical area, and emergency-response tasks, where at least m robots must converge to an incident location. The identities of the agents assigned to these tasks may change dynamically depending on their states, input bounds, and individual objectives. In this work, we propose a control barrier function (CBF)-based framework for enforcing counting invariance and counting convergence tasks, without explicitly assigning agents or enumerating all possible subteams. We develop a recursion-based method for constructing differentiable CBFs for counting tasks. The resulting CBF constraints are incorporated into quadratic programs, enabling online controller synthesis. Numerical experiments demonstrate scalability to large multi-agent systems, while a multi-drone emergency-response case study illustrates the satisfaction of counting tasks.

Introduction

Multi-agent systems often execute tasks that depend on the number of agents satisfying a condition rather than on their identities. Examples include smart warehouses, where at least mm drones must continuously patrol storage areas; disaster response, where at least mm robots must converge to a wildfire perimeter or earthquake impact zone; and energy systems, where a minimum number of backup generators must remain within an operating range to provide reserve capacity. Such counting tasks can be satisfied by different agent subteams, making task allocation critical. However, preassigning agents to tasks may lead to inefficient allocations or infeasibility as operating conditions change. This motivates online controllers that dynamically adapt task allocation based on agents’ states, control capabilities, and individual objectives.

Temporal logics provide an expressive framework for specifying high-level control objectives, including safety, reachability, and sequential or repeated execution of tasks. For multi-agent systems, temporal logics have been used to describe collective behaviors and synthesize controllers with formal guarantees of task satisfaction. In [1], a hierarchical framework produces provably correct control laws for temporal-logic specifications over the position and size of robotic swarms. For counting tasks, [2] introduced counting linear temporal logic (cLTL) and used integer programming to synthesize satisfying plans. This framework was extended

in [3] to handle bounded asynchronous execution among agents. More recently, [4] developed a dual-tree-based value iteration framework to reduce computational cost for cLTL tasks in stochastic homogeneous multi-agent systems. These counting-task approaches rely on discrete system representations and offline synthesis, motivating the development of online methods operating directly in continuous state spaces.

Control barrier functions (CBFs) provide a framework for real-time control synthesis with formal safety guarantees [5, 6]. More recently, CBFs have also been used to enforce temporal-logic specifications [7, 8] and security hyperproperties [9]. Boolean combinations of safety constraints can also be addressed through nonsmooth [10] and smooth [11] CBF compositions. However, a direct use of these composition methods to express counting tasks requires enumerating a combinatorial number of possible agent subteams, increasing the size of the specification and the computational cost of constructing and evaluating the associated CBF. This motivates the development of CBF formulations tailored to counting tasks. Recently, [12] introduced combinatorial CBFs for counting invariance, requiring at least mm out of MM agents to remain in a prescribed set at all times. This approach preserves the exact counting safe set and avoids combinatorial enumeration, but imposes one CBF constraint per agent. Enforcing these constraints simultaneously in a quadratic program (QP) can increase computational cost for large teams and pose significant QP feasibility challenges.

In this paper, we develop a CBF-based framework for counting invariance and counting convergence tasks for large multi-agent systems. While counting invariance requires at least mm of MM agents to satisfy a prescribed condition at all times, counting convergence requires the system to converge to a configuration in which at least mm out of MM agents satisfy such a condition. We associate each agent with a scalar value that is nonnegative if and only if the agent satisfies the prescribed condition. The counting task is therefore equivalent to nonnegativity of the mthm^{\mathrm{th}} largest value. Since this ordered value is generally nondifferentiable, we construct arbitrarily tight, differentiable lower approximations as candidate CBFs for counting tasks. We also provide a method that efficiently evaluates these CBFs through a forward recursion and their gradients through a backward recursion, without explicit task allocation or combinatorial enumeration of agent subteams. Compared with [12], our framework handles both counting invariance and counting convergence tasks, using one aggregate CBF constraint per task rather than MM agent-wise constraints. We also establish sufficient conditions for locally Lipschitz continuity of the QP controller under standard feasibility and regularity assumptions.

The remainder of the paper is organized as follows. Sec. II introduces the preliminaries and problem formulation, and Sec. III constructs candidate CBFs for counting tasks. Sec. IV presents the control synthesis framework with guarantees of counting-task satisfaction. Sec. V evaluates the scalability of the proposed method and presents a multi-drone case study, and Sec. VI concludes the paper.

Preliminaries & Problem Formulation

Notation. Let R\mathbb{R} and R≥0\mathbb{R}_{\ge0} denote the sets of real and nonnegative real numbers, respectively. The zero vector is denoted 0\mathbf{0}. For a vector x∈Rn\mathbf{x} \in\mathbb{R}^{n}, ∥x∥\|\mathbf{x}\| denotes its Euclidean norm. Given a nonempty set C⊂RnC \subset\mathbb{R}^{n}, ∥x∥C:=inf⁡y∈C∥x−y∥\|\mathbf{x}\|_{C} := \inf_{\mathbf{y}\in C}\|\mathbf{x}-\mathbf{y}\| denotes the Euclidean distance of x\mathbf{x} from CC. The cardinality of a set I\mathcal{I} is denoted by ∣I∣|\mathcal{I}|. For integers M≥0M \ge0 and 0≤k≤M0 \le k \le M, the binomial coefficient (Mk):=M!k!(M−k)!\binom{M}{k} := \frac{M!}{k!(M-k)!} denotes the number of kk-element subsets of an MM-element set, with 0!:=10! := 1. A continuous function α:R≥0→R≥0\alpha: \mathbb{R}_{\ge0} \to\mathbb{R}_{\ge0} is class-K\mathcal{K} if it is strictly increasing and α(0)=0\alpha(0)=0. The definition extends to extended class-K\mathcal{K} functions α:R→R\alpha: \mathbb{R} \to\mathbb{R}. The notations exp⁡(x)\exp(x) and exe^{x} are used interchangeably for the exponential function. Continuously differentiable functions are denoted by C1C^{1}.

System model

Consider a multi-agent system with MM agents, indexed by I={1,…,M}\mathcal{I}=\{1,\ldots,M\}. Each agent i∈Ii\in\mathcal{I} follows nonlinear input-affine dynamics, i.e.,

x˙i=fi(xi)+Gi(xi)ui,i∈I,(1)\dot{\mathbf{x}}_{i}=\mathbf{f}_{i}(\mathbf{x}_{i})+\mathbf{G}_{i}(\mathbf{x}_{i})\mathbf{u}_{i},\quad i\in\mathcal{I}, \tag*{(1)}

where xi∈Rn\mathbf{x}_{i}\in\mathbb{R}^{n} and ui∈Rp\mathbf{u}_{i}\in\mathbb{R}^{p} are its state and control input, respectively. The functions fi:Rn→Rn\mathbf{f}_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n} and Gi:Rn→Rn×p\mathbf{G}_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n\times p}, i∈Ii\in\mathcal{I}, are locally Lipschitz continuous. Let

x~=[x1T ⋯ xMT]T∈RMn,u~=[u1T ⋯ uMT]T∈RMp(2)\tilde{\mathbf{x}}=[\mathbf{x}_{1}^{\mathsf{T}}\ \cdots\ \mathbf{x}_{M}^{\mathsf{T}}]^{\mathsf{T}}\in\mathbb{R}^{Mn},\quad\tilde{\mathbf{u}}=[\mathbf{u}_{1}^{\mathsf{T}}\ \cdots\ \mathbf{u}_{M}^{\mathsf{T}}]^{\mathsf{T}}\in\mathbb{R}^{Mp} \tag*{(2)}

denote the stacked state and input, respectively. Note that given a locally Lipschitz controller, the closed-loop system is locally Lipschitz. Then, for any initial condition x~(0)=x~0\tilde{\mathbf{x}}(0)=\tilde{\mathbf{x}}_{0}, there exists a unique maximal solution x~(t)\tilde{\mathbf{x}}(t) defined on I(x~0)=[0,τmax⁡)I(\tilde{\mathbf{x}}_{0})=[0,\tau_{\max}). The closed-loop system is forward complete if τmax⁡=∞\tau_{\max}=\infty for any x~0\tilde{\mathbf{x}}_{0}.

Control barrier functions

Let D~⊆RMn\widetilde{D}\subseteq\mathbb{R}^{Mn} be an open set, and define the set C~⊂D~\widetilde{C}\subset\widetilde{D} as the zero-superlevel set of a C1C^{1} function H:D~→RH:\widetilde{D}\to\mathbb{R}, i.e.,

C~:={x~∈D~:H(x~)≥0}.\widetilde{C}:=\left\{\tilde{\mathbf{x}}\in\widetilde{D}:H(\tilde{\mathbf{x}})\ge0\right\}.

Definition 2.1. A C1C^{1} function H:D~→RH:\widetilde{D}\to\mathbb{R} is a control barrier function (CBF) for C~\widetilde{C} if there exists a locally Lipschitz extended class-K\mathcal{K} function α\alpha such that, for all x~∈D~\tilde{\mathbf{x}}\in\widetilde{D},

sup⁡ui∈Rp, i∈I∑i=1M∂H∂xi(x~)(fi(xi)+Gi(xi)ui)≥−α(H(x~)).(3)\sup_{\mathbf{u}_{i}\in\mathbb{R}^{p},\,i\in\mathcal{I}}\sum_{i=1}^{M}\frac{\partial H}{\partial\mathbf{x}_{i}}(\tilde{\mathbf{x}})\left(\mathbf{f}_{i}(\mathbf{x}_{i})+\mathbf{G}_{i}(\mathbf{x}_{i})\mathbf{u}_{i}\right)\ge-\alpha\left(H(\tilde{\mathbf{x}})\right). \tag*{(3)}

Note that Def. 2.1 implies a centralized control framework, that is, each agent’s control input ui\mathbf{u}_{i} may depend on the joint state x~\tilde{\mathbf{x}}. This definition is used in Sec. IV to synthesize online controllers for counting tasks.

Problem formulation

Consider the system in (1), and minv,mconv∈{1,…,M}m_{\mathrm{inv}},m_{\mathrm{conv}}\in\{1,\ldots,M\}. Consider the C1C^{1} functions hinv,hconv:Rn→Rh_{\mathrm{inv}},h_{\mathrm{conv}}:\mathbb{R}^{n}\to\mathbb{R}, and the sets

Cinv={x:hinv(x)≥0},Cconv={x:hconv(x)≥0}⊂Rn.C_{\mathrm{inv}}=\{\mathbf{x}:h_{\mathrm{inv}}(\mathbf{x})\ge0\},\quad C_{\mathrm{conv}}=\{\mathbf{x}:h_{\mathrm{conv}}(\mathbf{x})\ge0\}\subset\mathbb{R}^{n}.

Define, for any set CC, IC(x)=1\mathbb{I}_{C}(\mathbf{x})=1 if x∈C\mathbf{x}\in C, and 00 otherwise.

Definition 2.2. A counting invariance task is satisfied if at least minvm_{\mathrm{inv}} out of the MM agents in (1) belong to CinvC_{\mathrm{inv}} at all times, i.e., ∑i=1MICinv(xi(t))≥minv\sum_{i=1}^{M}\mathbb{I}_{C_{\mathrm{inv}}}(\mathbf{x}_{i}(t))\ge m_{\mathrm{inv}}, ∀t∈R≥0\forall t\in\mathbb{R}_{\ge0}.

The identities of the agents satisfying the counting invariance task need not be fixed over time, provided that the required number minvm_{\mathrm{inv}} is maintained.

Definition 2.3. A counting convergence task is satisfied if the joint state x~\tilde{\mathbf{x}} of (1) eventually converges to the set T~conv={x~∈RMn:∑i=1MICconv(xi)≥mconv}\widetilde{T}_{\mathrm{conv}}=\{\tilde{\mathbf{x}}\in\mathbb{R}^{Mn}:\sum_{i=1}^{M}\mathbb{I}_{C_{\mathrm{conv}}}(\mathbf{x}_{i})\ge m_{\mathrm{conv}}\} as t→∞t\to\infty.

Problem 2.4: Design controllers ui(x~)∈Rp\mathbf{u}_{i}(\tilde{\mathbf{x}})\in\mathbb{R}^{p}, i∈Ii\in\mathcal{I}, such that the system in (1) satisfies the counting invariance task in Def. 2.2 and/or the counting convergence task in Def. 2.3.

To solve Prob. 2.4, we first construct differentiable candidate CBFs for the counting tasks and develop an efficient recursion-based approach for evaluating their values and gradients (cf. Sec. III). Then, we incorporate the corresponding CBF constraints into a QP that enables controller synthesis for counting invariance and convergence without explicitly assigning agents to tasks (cf. Sec. IV).

Candidate CBFs for Counting Tasks

In this section, we develop a method for constructing and efficiently evaluating differentiable CBFs.

Consider the system in (1). Let h:Rn→Rh:\mathbb{R}^{n}\to\mathbb{R} be a C1C^{1} function defining a set C={x∈Rn:h(x)≥0}C=\{\mathbf{x}\in\mathbb{R}^{n}:h(\mathbf{x})\ge0\}. This function is evaluated at each agent’s state, such that h(xi)≥0h(\mathbf{x}_{i})\ge0 if and only if agent ii belongs to CC. The construction of candidate CBFs in this section applies to both counting invariance tasks with h=hinvh=h_{\mathrm{inv}} and counting convergence tasks with h=hconvh=h_{\mathrm{conv}}. We denote the jthj^{\mathrm{th}} largest among these values by h(j)h_{(j)}, j∈Ij\in\mathcal{I}, such that h(1)≥h(2)≥⋯≥h(M)h_{(1)}\ge h_{(2)}\ge\cdots\ge h_{(M)}. Requiring at least mm agents to belong to CC is thus equivalent to requiring h(m)≥0h_{(m)}\ge0. Although evaluating h(m)h_{(m)} is straightforward, the function is generally nondifferentiable at points where the ordering of the values changes, preventing its direct use as a CBF for counting tasks. Therefore, we seek a differentiable lower approximation h(m)≤h(m)h_{(m)}\le h_{(m)} to serve as a candidate CBF. Enforcing h(m)≥0h_{(m)}\ge0 guarantees h(m)≥0h_{(m)}\ge0, and hence ensures that at least mm agents belong to CC.

We start by expressing h(m)h_{(m)} in terms of sums of ordered values. The sum of the kk largest values is

σk=∑j=1kh(j),k=1,…,M,\sigma_{k}=\sum_{j=1}^{k}h_{(j)},\quad k=1,\ldots,M,

with σ0=0\sigma_{0}=0. We denote by Ik\mathcal{I}_{k} the collection of all subsets consisting of kk agents, i.e., Ik:={I⊂I:∣I∣=k}\mathcal{I}_{k}:=\{I\subset\mathcal{I}:|I|=k\}. Then, we can express σk\sigma_{k} in terms of the agents’ values h(xi)h(\mathbf{x}_{i}) as

σk=max⁡I∈Ik∑i∈Ih(xi).(4)\sigma_{k}=\max_{I\in\mathcal{I}_{k}}\sum_{i\in I}h(\mathbf{x}_{i}). \tag*{(4)}

Intuitively, among all possible subteams of kk agents, the largest sum σk\sigma_k is obtained by selecting the agents associated with the kk largest values. The mthm^{\mathrm{th}} largest value, h(m)h_{(m)}, can then be recovered from two consecutive sums as

h(m)=σm−σm−1.(5)h_{(m)} = \sigma_m - \sigma_{m-1}. \tag*{(5)}

Note that σm\sigma_m and σm−1\sigma_{m-1} are still nondifferentiable. Next, we construct C1C^1 approximations of these two sums and develop a recursion-based method to efficiently evaluate the derived candidate CBF and its gradient.

Construction of candidate CBFs

To obtain a C1C^1 approximation of (5), we approximate the sums σm\sigma_m and σm−1\sigma_{m-1} using the LogSumExp function. Recall that, for any y1,…,yN∈Ry_1,\ldots,y_N \in\mathbb{R} and τ>0\tau> 0, the following inequality holds

max⁡iyi≤τln⁡(∑i=1Neyiτ)≤max⁡iyi+τln⁡N.(6)\max_i y_i \leq\tau\ln\left(\sum_{i=1}^{N}e^{\frac{y_i}{\tau}}\right) \leq\max_i y_i + \tau\ln N. \tag*{(6)}

In order to apply it to lower approximate σk\sigma_k in (4), we define

σ^k:=τln⁡(∑Ij∈Ik, j∈∣Ik∣eyjτ),where yj=∑i∈Ijh(xi).(7)\hat{\sigma}_k := \tau\ln\left(\sum_{I_j \in\mathcal{I}_k,\,j \in|\mathcal{I}_k|} e^{\frac{y_j}{\tau}}\right), \qquad\text{where } y_j = \sum_{i\in I_j}h(x_i). \tag*{(7)}

For k=1,…,Mk=1,\ldots,M, the collection Ik\mathcal{I}_k contains (Mk)\binom{M}{k} subteams, i.e., ∣Ik∣=(Mk)|\mathcal{I}_k|=\binom{M}{k}, corresponding to all ways of selecting kk agents of the system. Thus, applying (6) to these (Mk)\binom{M}{k} subteam sums gives σk≤σ^k≤σk+τln⁡(Mk)\sigma_k \leq\hat{\sigma}_k \leq\sigma_k+\tau\ln\binom{M}{k}, or, equivalently,

σ^k−τln⁡(Mk)≤σk≤σ^k.\hat{\sigma}_k-\tau\ln\binom{M}{k}\leq\sigma_k\leq\hat{\sigma}_k.

We can now construct a C1C^1 lower approximation of h(m)=σm−σm−1h_{(m)}=\sigma_m-\sigma_{m-1}, by lower-bounding σm\sigma_m and upper-bounding σm−1\sigma_{m-1}. We have

h(m)=σm−σm−1≥σ^m−τln⁡(Mm)−σ^m−1:=h‾(m).(8)h_{(m)}=\sigma_m-\sigma_{m-1}\geq\hat{\sigma}_m-\tau\ln\binom{M}{m}-\hat{\sigma}_{m-1}:=\underline{h}_{(m)}. \tag*{(8)}

Therefore, h‾(m)≥0\underline{h}_{(m)}\geq0 implies h(m)≥0h_{(m)}\geq0, which guarantees that at least mm agents belong to CC. The conservatism introduced by this approximation can be explicitly bounded as

0≤h(m)−h‾(m)≤τ(ln⁡(Mm)+ln⁡(Mm−1)).(9)0\leq h_{(m)}-\underline{h}_{(m)}\leq\tau\left(\ln\binom{M}{m}+\ln\binom{M}{m-1}\right). \tag*{(9)}

The approximation becomes arbitrarily tight as τ→0\tau\to0, with h‾(m)→h(m)\underline{h}_{(m)}\to h_{(m)}. We have now obtained a differentiable lower approximation of h(m)h_{(m)}, i.e., h‾(m)\underline{h}_{(m)}, which serves as a candidate CBF. However, directly evaluating σ^m\hat{\sigma}_m and σ^m−1\hat{\sigma}_{m-1} requires enumerating a combinatorial number of subteams and becomes prohibitive for online computation as the number of agents increases (cf. Figure 2). Next, we show how we can compute these quantities recursively without explicit subteam enumeration.

Figure 2. Experiment (i): Computation times of the recursion-based and combinatorial methods as MM increases, with m/M≈0.4m/M \approx0.4.

Forward recursion for efficient CBF evaluation

We compute the candidate CBF by processing all agents sequentially and accumulating the exponential contributions of all possible subteams of each size as in (7). We use stage l=0,…,Ml=0,\ldots,M to indicate that the first ll agents have been processed. For each stage l=0,…,Ml=0,\ldots,M and subteam size k=0,…,mk=0,\ldots,m, let us define

Zk(l):=∑I⊆{1,…,l}:∣I∣=kexp⁡(1τ∑i∈Ih(xi)).Z_k^{(l)}:=\sum_{\substack{I\subseteq\{1,\ldots,l\}:\\ |I|=k}}\exp\left(\frac{1}{\tau}\sum_{i\in I}h(x_i)\right).

At the final stage l=Ml=M, all agents have been processed, thus (7) gives

σ^k=τln⁡Zk(M).(10)\hat{\sigma}_k=\tau\ln Z_k^{(M)}. \tag*{(10)}

Substituting this into (8) yields

h‾(m)=τln⁡Zm(M)−τln⁡Zm−1(M)−τln⁡(Mm).(11)\underline{h}_{(m)}=\tau\ln Z_m^{(M)}-\tau\ln Z_{m-1}^{(M)}-\tau\ln\binom{M}{m}. \tag*{(11)}

Therefore, evaluating the candidate CBF h‾(m)\underline{h}_{(m)} requires only the terminal quantities Zm(M)Z_m^{(M)} and Zm−1(M)Z_{m-1}^{(M)}.

To update Zk(l)Z_k^{(l)}, we partition the kk-agent subteams drawn from the first ll agents into two disjoint groups, according to whether they contain agent ll. Subteams in the first group exclude agent ll and are formed by selecting kk agents from the first l−1l-1 agents. Thus, their total contribution is Zk(l−1)Z_k^{(l-1)}. Subteams in the second group are formed by adding agent ll to a (k−1)(k-1)-agent subteam selected from the first l−1l-1 agents. The total contribution of the second group is therefore exp⁡(h(xl)/τ)Zk−1(l−1)\exp(h(x_l)/\tau)Z_{k-1}^{(l-1)}. Combining the two groups, we obtain

Zk(l)=Zk(l−1)+exp⁡(h(xl)τ)Zk−1(l−1).(12)Z_k^{(l)}=Z_k^{(l-1)}+\exp\left(\frac{h(x_l)}{\tau}\right)Z_{k-1}^{(l-1)}. \tag*{(12)}

We initialize the recursion by setting Z0(l)=1Z_0^{(l)}=1 for l=0,…,Ml=0,\ldots,M, since the empty subteam contributes one. We also set Zk(l)=0Z_k^{(l)}=0 whenever k>lk>l, because a kk-agent subteam cannot be formed from only l<kl<k agents. At each stage l=1,…,Ml=1,\ldots,M, we apply (12) for k=1,…,min⁡{l,m}k=1,\ldots,\min\{l,m\}, using values only from stage l−1l-1. This forward recursion produces the two terminal quantities required in (11).

The following example illustrates how the forward recursion evaluates the candidate CBF by updating and reusing intermediate quantities across successive stages.

Example 3.1. Consider a system with M=4M=4, m=3m=3, τ=1\tau=1, and h(x1)=0.8h(x_1)=0.8, h(x2)=0.45h(x_2)=0.45, h(x3)=−0.4h(x_3)=-0.4, h(x4)=−0.2h(x_4)=-0.2. Figure 1 shows the recursion process, with

Illustration of the forward recursion for M = 4 and m = 3

Figure 1. Illustration of the forward recursion for M=4M=4 and m=3m=3. Green entries equal one, red entries equal zero, and blue entries do not need to be evaluated.

stages ll in columns and subteam sizes kk in rows. Horizontal and diagonal arrows represent the two terms in (12). The gray nodes mark the terminal sums Z2(4)Z_{2}^{(4)} and Z3(4)Z_{3}^{(4)} used to evaluate the candidate CBF as in (11).

At stage l=1l=1, the only way to select one agent is to select agent 1. Thus, Z1(1)=eh(x1)=e0.8Z_{1}^{(1)}=e^{h(x_{1})}=e^{0.8}. At stage l=2l=2, there are two ways to select one agent, either agent 1 or agent 2. Thus, Z1(2)=Z1(1)+eh(x2)=e0.8+e0.45Z_{1}^{(2)}=Z_{1}^{(1)}+e^{h(x_{2})}=e^{0.8}+e^{0.45}. Moreover, the only way to select two agents is to include both agents 1 and 2. Thus,

Z2(2)=eh(x2)Z1(1)=e0.8+0.45=e1.25.Z_{2}^{(2)}=e^{h(x_{2})}Z_{1}^{(1)}=e^{0.8+0.45}=e^{1.25}.

At stage l=3l=3, the two-agent subteam {1,2}\{1,2\} excludes agent 3, whereas {1,3}\{1,3\} and {2,3}\{2,3\} include it. Accordingly,

Z2(3)=Z2(2)+e−0.4Z1(2)≈6.033.Z_{2}^{(3)}=Z_{2}^{(2)}+e^{-0.4}Z_{1}^{(2)}\approx6.033.

These two contributions correspond to the two arrows entering Z2(3)Z_{2}^{(3)} in Figure 1. At the final stage, Z2(4)≈9.688Z_{2}^{(4)}\approx9.688 and Z3(4)≈7.279Z_{3}^{(4)}\approx7.279. Since the third-largest value is h(3)=h(x4)=−0.2h_{(3)}=h(x_{4})=-0.2, (11) yields

h^(3)=ln⁡Z3(4)−ln⁡Z2(4)−ln⁡(43)≈−1.672≤h(3)=−0.2.\widehat{h}_{(3)}=\ln Z_{3}^{(4)}-\ln Z_{2}^{(4)}-\ln\binom{4}{3}\approx-1.672\leq h_{(3)}=-0.2.

For τ=1\tau=1, the approximation is conservative, as expected from the bound in (9), which gives

0≤h(3)−h^(3)≤3.178.0\leq h_{(3)}-\widehat{h}_{(3)}\leq3.178.

However, h^(3)\widehat{h}_{(3)} remains a valid lower approximation of h(3)h_{(3)}. Reducing τ\tau to 0.10.1 and 0.010.01 yields h^(3)≈−0.326\widehat{h}_{(3)}\approx-0.326 and ≈−0.214\approx-0.214, respectively, showing convergence to h(3)h_{(3)} as τ→0\tau\to0, consistent with the approximation error bounds in (9). ⋄

Since only the two terminal sums are needed to evaluate the candidate CBF in (11), some entries of the recursion do not need to be computed. A kk-agent subteam at stage ll can grow to at most k+M−lk+M-l agents by stage MM, so it cannot contribute to either terminal sum if k+M−l<m−1k+M-l<m-1. Thus, the update range can be restricted to

kmin⁡(l)=max⁡{1,m−M+l−1}≤k≤min⁡{l,m}.k_{\min}^{(l)}=\max\{1,m-M+l-1\}\leq k\leq\min\{l,m\}.

In Figure 1, the blue entries can be omitted for this reason, while the red entries are zero. With this restricted update range, the constant entries Z0(l)=1Z_{0}^{(l)}=1 are needed only for 0≤l≤M−m+10\leq l\leq M-m+1, as shown in green.

Next, we differentiate the forward recursion to efficiently evaluate the gradient required by the CBF constraint in (3).

Backward recursion for CBF gradient evaluation

We compute the gradient of h^(m)\widehat{h}_{(m)} by differentiating the forward recursion in (12). We first propagate derivatives backward from the terminal quantities, then apply the chain rule to obtain the derivatives with respect to h(xl)h(x_l) and the agent states xlx_l, l=1,…,Ml=1,\ldots,M.

For each entry, we define λk(l):=∂h^(m)/∂Zk(l)\lambda_k^{(l)}:=\partial\widehat{h}_{(m)}/\partial Z_k^{(l)}. This derivative accounts for all subsequent stages through which Zk(l)Z_k^{(l)} affects the candidate CBF. At the final stage l=Ml=M, (11) depends only on Zm(M)Z_m^{(M)} and Zm−1(M)Z_{m-1}^{(M)}, so we initialize the backward recursion with

λm(M)=τZm(M),λm−1(M)=−τZm−1(M).\lambda_m^{(M)}=\frac{\tau}{Z_m^{(M)}},\qquad\lambda_{m-1}^{(M)}=-\frac{\tau}{Z_{m-1}^{(M)}}.

and λk(M)=0\lambda_k^{(M)}=0, for k=0,…,m−2k=0,\ldots,m-2. Starting from these terminal derivatives, we proceed backward through stages l=M−1,…,1l=M-1,\ldots,1. By (12), each Zk(l)Z_k^{(l)} contributes to two entries at stage l+1l+1: Zk(l+1)Z_k^{(l+1)} and Zk+1(l+1)Z_{k+1}^{(l+1)}. Hence, the chain rule sums the contributions through these two entries:

λk(l)=λk(l+1)+eh(xl+1)τλk+1(l+1),k=kmin⁡(l),…,min⁡{l,m−1}.\lambda_k^{(l)}=\lambda_k^{(l+1)}+e^{\frac{h(x_{l+1})}{\tau}}\lambda_{k+1}^{(l+1)},\qquad k=k_{\min}^{(l)},\ldots,\min\{l,m-1\}.

If l≥ml\geq m, the entry Zm(l)Z_m^{(l)} contributes only to Zm(l+1)Z_m^{(l+1)}, giving λm(l)=λm(l+1)\lambda_m^{(l)}=\lambda_m^{(l+1)}. As in the forward recursion, entries with l≤k<kmin⁡(l)l\leq k<k_{\min}^{(l)} are omitted, and their derivatives are set to zero. The constant entries Z0(l)=1Z_0^{(l)}=1 and Zk(l)=0Z_k^{(l)}=0 for k>lk>l require no backward updates.

Once the derivatives at stage ll are available, we compute the derivative with respect to h(xl)h(x_l). Note that h(xl)h(x_l) appears explicitly in the forward recursion in (12) only at stage ll. Thus, differentiating (12) gives

∂Zk(l)∂h(xl)=1τeh(xl)τZk−1(l−1),k=kmin⁡(l),…,min⁡{l,m}.\frac{\partial Z_k^{(l)}}{\partial h(x_l)}=\frac{1}{\tau}e^{\frac{h(x_l)}{\tau}}Z_{k-1}^{(l-1)},\qquad k=k_{\min}^{(l)},\ldots,\min\{l,m\}.

Since h(xl)h(x_l) affects all entries at stage ll with k≥1k\geq1, we apply the chain rule and sum their contributions to obtain

∂h^(m)∂h(xl)=∑k=kmin⁡(l)min⁡{l,m}∂h^(m)∂Zk(l)∂Zk(l)∂h(xl)=∑k=kmin⁡(l)min⁡{l,m}λk(l)∂Zk(l)∂h(xl)=1τeh(xl)τ∑k=kmin⁡(l)min⁡{l,m}λk(l)Zk−1(l−1).\begin{aligned} \frac{\partial\widehat{h}_{(m)}}{\partial h(x_l)} =\sum_{k=k_{\min}^{(l)}}^{\min\{l,m\}}\frac{\partial\widehat{h}_{(m)}}{\partial Z_k^{(l)}}\frac{\partial Z_k^{(l)}}{\partial h(x_l)} \\ &=\sum_{k=k_{\min}^{(l)}}^{\min\{l,m\}}\lambda_k^{(l)}\frac{\partial Z_k^{(l)}}{\partial h(x_l)} =\frac{1}{\tau}e^{\frac{h(x_l)}{\tau}}\sum_{k=k_{\min}^{(l)}}^{\min\{l,m\}}\lambda_k^{(l)}Z_{k-1}^{(l-1)}. \end{aligned}

Finally, multiplying by the gradient of h(xl)h(x_l) gives the desired state gradient:

∂h^(m)∂xl=∂h^(m)∂h(xl)∂h(xl)∂xl,l=1,…,M.(13)\frac{\partial\widehat{h}_{(m)}}{\partial x_l} =\frac{\partial\widehat{h}_{(m)}}{\partial h(x_l)} \frac{\partial h(x_l)}{\partial x_l},\qquad l=1,\ldots,M. \tag*{(13)}

Alg. 1 summarizes the forward and backward recursions presented in § 3-B and § 3-C. Given the individual agents’ h(xi)h(x_i) and their gradients, Lines 1–5 initialize and evaluate the forward recursion, producing the terminal sums required to compute the candidate CBF h^(m)\widehat{h}_{(m)} in line 6. The backward recursion in lines 7–15 reuses the stored intermediate quantities from the forward recursion to compute the gradient with respect to the agent states xlx_l (line 15). These outputs are used in Sec. IV to formulate the CBF constraints for counting invariance and convergence tasks.

The proposed approach constructs a C1C^1 candidate CBF for counting tasks and efficiently evaluates its value and gradient through forward and backward recursions, without explicitly enumerating agent subteams. Moreover, the approach is permutation invariant: reordering the agents leaves the CBF value unchanged and permutes its gradient components accordingly.

Complexity analysis

Next, we analyze the computational and memory complexity of the proposed method. Direct evaluation of σ^m\widehat{\sigma}_m and σ^m−1\widehat{\sigma}_{m-1} as in (7) requires enumerating (Mm)\binom{M}{m} and (Mm−1)\binom{M}{m-1} subteams, respectively. Since computing each subteam sum

Algorithm 1 Recursions for CBF and gradient evaluation
Input: $m$, $\tau$, $h(x_l)$, $\partial h(x_l)/\partial x_l$, $l=1,\ldots,M$
Output: $h_{(m)}$, $\partial h_{(m)}/\partial x_l$, $l=1,\ldots,M$
1: $k_{\min}^{(l)}=\max\{1,m-M+l-1\}$
2: Initialize the forward recursion: $Z_0^{(l)}\leftarrow 1$, $l=0,\ldots,M$, and $Z_k^{(l)}\leftarrow 0$, $k>l$
3: for $l=1,\ldots,M$ do
4:   for $k=k_{\min}^{(l)},\ldots,\min\{l,m\}$ do
5:     $Z_k^{(l)}\leftarrow Z_k^{(l-1)}+\exp(h(x_l)/\tau)Z_{k-1}^{(l-1)}$
6: $h_{(m)}\leftarrow\tau\ln Z_m^{(M)}-\tau\ln Z_{m-1}^{(M)}-\tau\ln\binom{M}{m}$
7: Initialize the backward recursion:
$\lambda_k^{(l)}\leftarrow 0$, $k=0,\ldots,m$, $l=0,\ldots,M$,
$\lambda_m^{(M)}\leftarrow\tau/Z_m^{(M)}$, $\lambda_{m-1}^{(M)}\leftarrow-\tau/Z_{m-1}^{(M)}$
8: for $l=M,\ldots,1$ do
9:   if $l<M$ then
10:     for $k=k_{\min}^{(l)},\ldots,\min\{l,m-1\}$ do
11:       $\lambda_k^{(l)}\leftarrow\lambda_k^{(l+1)}+\exp(h(x_{l+1})/\tau)\lambda_{k+1}^{(l+1)}$
12:   if $m\leq l$ then
13:     $\lambda_m^{(l)}\leftarrow\lambda_m^{(l+1)}$
14: $\frac{\partial h_{(m)}}{\partial h(x_l)}\leftarrow\frac{1}{\tau}\exp(h(x_l)/\tau)\sum_{k=k_{\min}^{(l)}}^{\min\{l,m\}}\lambda_k^{(l)}Z_{k-1}^{(l-1)}$
15: $\frac{\partial h_{(m)}}{\partial x_l}\leftarrow\frac{\partial h_{(m)}}{\partial h(x_l)}\frac{\partial h(x_l)}{\partial x_l}$

requires O(m)O(m) operations, direct enumeration has computational complexity O(m(Mm))O\left(m\binom{M}{m}\right), which is combinatorial in MM and quickly becomes prohibitive for online computation.

The proposed recursion-based method processes at most mm entries over MM stages, with a constant number of operations per entry in both the forward and backward recursions. Thus, the computational complexity is O(Mm)O(Mm). For m>(M+1)/2m>(M+1)/2, it is more efficient to view the mmth largest value as the (M−m+1)(M-m+1)th smallest value, and express it as the difference between the sum of the M−m+1M-m+1 and M−mM-m smallest values. These sums can be smoothly approximated using the LogSumExp approximation of the minimum. The same forward and backward recursions then apply, with only M−m+1M-m+1 instead of mm entries per stage. Thus, the computational complexity is O(M⋅min⁡{m,M−m+1})O\left(M\cdot\min\{m,M-m+1\}\right), with worst-case complexity O(M2)O(M^2). The backward recursion requires storing intermediate quantities from the forward recursion. Thus, the memory complexity is O(M⋅min⁡{m,M−m+1})O\left(M\cdot\min\{m,M-m+1\}\right), or O(M2)O(M^2) in the worst case.

Controller Synthesis

In this section, we use the candidate CBFs and their gradient developed in § 3 to synthesize controllers for the counting tasks defined in Def. 2.2-2.3. We first establish sufficient conditions for forward invariance and attractivity of sets. We then incorporate the corresponding CBF constraints into an online QP and establish guarantees for satisfaction of the counting tasks.

Proposition 4.1: Consider the system in (1), a C1C^1 function H:RMn→RH:\mathbb{R}^{Mn}\to\mathbb{R}, and a locally Lipschitz extended class-K\mathcal{K} function α\alpha. Let D~⊆RMn\widetilde{D}\subseteq\mathbb{R}^{Mn} be an open set that contains the set C~={x~∈RMn:H(x~)≥0}⊂D~\widetilde{C}=\{\widetilde{x}\in\mathbb{R}^{Mn}:H(\widetilde{x})\geq0\}\subset\widetilde{D}.

(i) Suppose that HH is a CBF as in Def. 2.1. Then, any locally Lipschitz controller u~(x~)=[u1⊤ ⋯ uM⊤]⊤\widetilde{u}(\widetilde{x})=[u_1^\top\ \cdots\ u_M^\top]^\top satisfying

∑i=1M∂H∂xi(x~)(fi(xi)+Gi(xi)ui)≥−α(H(x~))(14)\sum_{i=1}^{M}\frac{\partial H}{\partial x_i}(\widetilde{x})\left(f_i(x_i)+G_i(x_i)u_i\right)\geq-\alpha(H(\widetilde{x})) \tag*{(14)}

for all x~∈D~\widetilde{x}\in\widetilde{D} renders C~\widetilde{C} forward invariant over the maximal interval of existence of each closed-loop solution.

(ii) Let T~⊆RMn\widetilde{T}\subseteq\mathbb{R}^{Mn} be a closed set with C~⊆T~\widetilde{C}\subseteq\widetilde{T}. Suppose there exists a class-K\mathcal{K} function γ\gamma such that

γ(∥x~∥T~)≤−H(x~)(15)\gamma\left(\left\|\widetilde{x}\right\|_{\widetilde{T}}\right)\leq-H(\widetilde{x}) \tag*{(15)}

for all x~∉T~\widetilde{x}\notin\widetilde{T}. Then, any locally Lipschitz controller u~(x~)\widetilde{u}(\widetilde{x}) satisfying (14) for all x~∈C~\widetilde{x}\in\widetilde{C} renders T~\widetilde{T} attractive, provided that the closed-loop solutions are forward complete. That is, lim⁡t→∞∥x~(t)∥T~=0\lim_{t\to\infty}\left\|\widetilde{x}(t)\right\|_{\widetilde{T}}=0 for any x~(0)∈RMn∖T~\widetilde{x}(0)\in\mathbb{R}^{Mn}\setminus\widetilde{T}.

Proof: (i) Let x~(0)∈C~\widetilde{x}(0)\in\widetilde{C} and define z(t):=H(x~(t))z(t):=H(\widetilde{x}(t)). By (14), we have z˙≥−α(z)\dot{z}\geq-\alpha(z). Comparing the comparison system w˙=−α(w)\dot{w}=-\alpha(w), with w(0)=z(0)≥0w(0)=z(0)\geq0. Since α\alpha is extended class-K\mathcal{K} and locally Lipschitz, it holds that w(t)≥0w(t)\geq0, t∈I(x~(0))t\in I(\widetilde{x}(0)). By the comparison lemma [13], z(t)≥w(t)≥0z(t)\geq w(t)\geq0, t∈I(x~(0))t\in I(\widetilde{x}(0)). Hence, every closed-loop trajectory with x~(0)∈C~\widetilde{x}(0)\in\widetilde{C} remains in C~\widetilde{C} over I(x~(0))I(\widetilde{x}(0)).

(ii) Let x~(0)∉T~\widetilde{x}(0)\notin\widetilde{T}. Then H(x~(0))<0H(\widetilde{x}(0))<0, since C~⊆T~\widetilde{C}\subseteq\widetilde{T}. Define V(t):=max⁡{−H(x~(t)),0}V(t):=\max\{-H(\widetilde{x}(t)),0\} and a class-K\mathcal{K} function β(s):=−α(−s)\beta(s):=-\alpha(-s). The function VV is locally absolutely continuous, and (14) gives V˙≤α(−V)=−β(V)\dot{V}\leq\alpha(-V)=-\beta(V) whenever V>0V>0. When V=0V=0, its derivative is zero almost everywhere, so the inequality holds almost everywhere along the trajectory. Since β\beta is locally Lipschitz and class-K\mathcal{K}, comparing with w˙=−β(w)\dot{w}=-\beta(w), w(0)=V(0)≥0w(0)=V(0)\geq0, yields 0≤V(t)≤w(t)→00\leq V(t)\leq w(t)\to0 as t→∞t\to\infty and that the closed-loop solution is forward complete. Moreover, γ(∥x~(t)∥T~)≤V(t)\gamma(\|\widetilde{x}(t)\|_{\widetilde{T}})\leq V(t), ∀t∈R≥0\forall t\in\mathbb{R}_{\geq0}. This follows from (15) for x~∉T~\widetilde{x}\notin\widetilde{T}, while γ(∥x~(t)∥T~)=0\gamma(\|\widetilde{x}(t)\|_{\widetilde{T}})=0 otherwise. Since γ\gamma is class-K\mathcal{K} and V(t)→0V(t)\to0 as t→∞t\to\infty, we have lim⁡t→∞∥x~(t)∥T~=0\lim_{t\to\infty}\|\widetilde{x}(t)\|_{\widetilde{T}}=0, proving attractivity of T~\widetilde{T}. ■

We consider the counting invariance and convergence tasks as in Defs. 2.2-2.3, associated with minv,mconv∈{1,…,M}m_{\mathrm{inv}},m_{\mathrm{conv}}\in\{1,\ldots,M\}, and C1C^1 functions hinv,hconv:Rn→Rh_{\mathrm{inv}},h_{\mathrm{conv}}:\mathbb{R}^n\to\mathbb{R}, defining Cinv={x:hinv(x)≥0}C_{\mathrm{inv}}=\{x:h_{\mathrm{inv}}(x)\geq0\} and Cconv={x:hconv(x)≥0}C_{\mathrm{conv}}=\{x:h_{\mathrm{conv}}(x)\geq0\}, respectively. From (11), we obtain candidate CBFs Hinv(x~):=h(minv)(x~)H_{\mathrm{inv}}(\widetilde{x}):=h_{(m_{\mathrm{inv}})}(\widetilde{x}) and Hconv(x~):=h(mconv)(x~)H_{\mathrm{conv}}(\widetilde{x}):=h_{(m_{\mathrm{conv}})}(\widetilde{x}). The corresponding sets associated with the CBFs are C~inv={x~:Hinv(x~)≥0}\widetilde{C}_{\mathrm{inv}}=\{\widetilde{x}:H_{\mathrm{inv}}(\widetilde{x})\geq0\}, C~conv={x~:Hconv(x~)≥0}\widetilde{C}_{\mathrm{conv}}=\{\widetilde{x}:H_{\mathrm{conv}}(\widetilde{x})\geq0\}. Since HinvH_{\mathrm{inv}} (resp. HconvH_{\mathrm{conv}}) provides a lower approximation of the mmth largest value with respect to CinvC_{\mathrm{inv}} (resp. CconvC_{\mathrm{conv}}), we get

C~inv⊆T~inv={x~:∑i=1MICinv(xi)≥minv},(16)\widetilde{C}_{\mathrm{inv}}\subseteq\widetilde{T}_{\mathrm{inv}}=\left\{\widetilde{x}:\sum_{i=1}^{M}\mathbb{I}_{C_{\mathrm{inv}}}(x_i)\geq m_{\mathrm{inv}}\right\}, \tag*{(16)}
C~conv⊆T~conv={x~:∑i=1MICconv(xi)≥mconv}.(17)\widetilde{C}_{\mathrm{conv}}\subseteq\widetilde{T}_{\mathrm{conv}}=\left\{\widetilde{x}:\sum_{i=1}^{M}\mathbb{I}_{C_{\mathrm{conv}}}(x_i)\geq m_{\mathrm{conv}}\right\}. \tag*{(17)}

To apply Prop. 4.1(ii) to counting convergence tasks, we must verify (15) for the candidate CBF H=HconvH = H_{\mathrm{conv}} and T~=T~conv\widetilde{T} = \widetilde{T}_{\mathrm{conv}}. The following lemma derives this bound from a corresponding condition on hconvh_{\mathrm{conv}} that can be readily checked when choosing hconvh_{\mathrm{conv}}.

Lemma 4.2. Suppose there exists a class-K\mathcal{K} function γh\gamma_h such that

γh(∥x∥Cconv)≤−hconv(x)(18)\gamma_h(\lVert x\rVert_{C_{\mathrm{conv}}}) \leq-h_{\mathrm{conv}}(x) \tag*{(18)}

for all x∉Cconvx \notin C_{\mathrm{conv}}. Then (15) holds with H=HconvH = H_{\mathrm{conv}}, T~=T~conv\widetilde{T} = \widetilde{T}_{\mathrm{conv}}, and γ(s)=γh(s/mconv)\gamma(s) = \gamma_h(s/\sqrt{m_{\mathrm{conv}}}).

Proof. Let h=hconvh = h_{\mathrm{conv}}, m=mconvm = m_{\mathrm{conv}}, and x(1),…,x(m)x_{(1)}, \ldots, x_{(m)} denote the states corresponding to the mm largest values h(xi)h(x_i). For x~∉T~conv\widetilde{x} \notin\widetilde{T}_{\mathrm{conv}}, h(m)(x~)<0h_{(m)}(\widetilde{x}) < 0. By definition, we have h(x(i))≥h(m)(x~)h(x_{(i)}) \geq h_{(m)}(\widetilde{x}), i=1,…,mi = 1, \ldots, m. Thus, by (18) and γh(0)=0\gamma_h(0) = 0, each agent i=1,…,mi = 1, \ldots, m satisfies γh(∥x(i)∥Cconv)≤max⁡{−h(x(i)),0}≤−h(m)(x~)\gamma_h(\lVert x_{(i)}\rVert_{C_{\mathrm{conv}}}) \leq\max\{-h(x_{(i)}),0\} \leq-h_{(m)}(\widetilde{x}). Define dmax⁡:=max⁡i=1,…,m∥x(i)∥Cconvd_{\max} := \max_{i=1,\ldots,m}\lVert x_{(i)}\rVert_{C_{\mathrm{conv}}}. Then,

∥x~∥T~conv≤∥x(1)∥Cconv2+⋯+∥x(m)∥Cconv2≤m dmax⁡.\lVert\widetilde{x}\rVert_{\widetilde{T}_{\mathrm{conv}}} \leq\sqrt{\lVert x_{(1)}\rVert^2_{C_{\mathrm{conv}}}+\cdots+\lVert x_{(m)}\rVert^2_{C_{\mathrm{conv}}}} \leq\sqrt{m}\,d_{\max}.

Monotonicity of γh\gamma_h then gives

γh(∥x~∥T~convm)≤γh(dmax⁡)≤−h(m)(x~).\gamma_h\left(\frac{\lVert\widetilde{x}\rVert_{\widetilde{T}_{\mathrm{conv}}}}{\sqrt{m}}\right) \leq\gamma_h(d_{\max}) \leq-h_{(m)}(\widetilde{x}).

The function γ(s):=γh(s/m)\gamma(s) := \gamma_h(s/\sqrt{m}) is class-K\mathcal{K}. Moreover, by (9), h(m)(x~)≥Hconv(x~)h_{(m)}(\widetilde{x}) \geq H_{\mathrm{conv}}(\widetilde{x}), thus γ(∥x~∥T~conv)≤−Hconv(x~)\gamma(\lVert\widetilde{x}\rVert_{\widetilde{T}_{\mathrm{conv}}}) \leq-H_{\mathrm{conv}}(\widetilde{x}), which completes the proof. ■

We synthesize controllers for both counting tasks by solving a convex QP. At each state x~\widetilde{x}, the optimal joint input u~∗(x~)=[u1∗⊤ ⋯ uM∗⊤]⊤\widetilde{u}^{*}(\widetilde{x}) = [u_1^{* \top}\ \cdots\ u_M^{* \top}]^{\top} is obtained by solving

min⁡u~,δinv,δconv12∥u~−u~nom(x~)∥2+pinv2δinv2+pconv2δconv2s.t.Ψinv(x~,u~)≥−δinvΨconv(x~,u~)≥−δconv(19)\begin{aligned} \min_{\widetilde{u},\delta_{\mathrm{inv}},\delta_{\mathrm{conv}}}\quad& \frac{1}{2}\lVert\widetilde{u}-\widetilde{u}_{\mathrm{nom}}(\widetilde{x})\rVert^2 +\frac{p_{\mathrm{inv}}}{2}\delta_{\mathrm{inv}}^2 +\frac{p_{\mathrm{conv}}}{2}\delta_{\mathrm{conv}}^2\\ \text{s.t.}\quad& \Psi_{\mathrm{inv}}(\widetilde{x},\widetilde{u})\geq-\delta_{\mathrm{inv}}\\ & \Psi_{\mathrm{conv}}(\widetilde{x},\widetilde{u})\geq-\delta_{\mathrm{conv}} \tag*{(19)} \end{aligned}

where u~nom(x~)∈RMp\widetilde{u}_{\mathrm{nom}}(\widetilde{x}) \in\mathbb{R}^{Mp} is a locally Lipschitz nominal controller encoding the individual objectives of the agents, δinv,δconv∈R\delta_{\mathrm{inv}},\delta_{\mathrm{conv}} \in\mathbb{R} are slack variables, and pinv,pconv>0p_{\mathrm{inv}},p_{\mathrm{conv}}>0 are their respective penalty weights. For j∈{inv,conv}j\in\{\mathrm{inv},\mathrm{conv}\}, the CBF constraints are defined by

Ψj(x~,u~)=∑i=1M∂Hj∂xi(x~)(fi(xi)+Gi(xi)ui)+α(Hj(x~)),\Psi_j(\widetilde{x},\widetilde{u})=\sum_{i=1}^{M}\frac{\partial H_j}{\partial x_i}(\widetilde{x})\left(f_i(x_i)+G_i(x_i)u_i\right)+\alpha(H_j(\widetilde{x})),

with α\alpha being locally Lipschitz and extended class-K\mathcal{K}. The gradient of Hj(x~)=h(mj)(x~)H_j(\widetilde{x})=h_{(m_j)}(\widetilde{x}) is efficiently evaluated through the backward recursion in (13). The closed-loop trajectories of (1) are obtained by applying ui∗(x~)u_i^{*}(\widetilde{x}), i∈Ii\in\mathcal{I}.

Remark 4.3. The QP in (19) allows the two counting tasks to be enforced separately, relaxed or prioritized. In particular, setting δinv=0\delta_{\mathrm{inv}}=0 (resp. δconv=0\delta_{\mathrm{conv}}=0) enforces the counting invariance (resp. convergence) constraint without relaxation. In this case, satisfaction guarantees can be established for the prioritized task, whenever the QP admits a solution.

The following theorem establishes sufficient conditions under which u~∗(x~)\widetilde{u}^{*}(\widetilde{x}) from (19) guarantees satisfaction of the counting invariance task (with δinv=0\delta_{\mathrm{inv}}=0) and the counting convergence task (with δconv=0\delta_{\mathrm{conv}}=0).

Theorem 4.4. Consider the system in (1) and the counting tasks in Def. 2.2–2.3, with mjm_j and functions hjh_j defining CjC_j, j∈{inv,conv}j\in\{\mathrm{inv},\mathrm{conv}\}. Let HjH_j be constructed as in (11), with its value and gradient evaluated using Alg. 1. Assume that hinvh_{\mathrm{inv}} and hconvh_{\mathrm{conv}} have locally Lipschitz gradients. Consider the controller obtained from the QP in (19), and assume that the resulting closed-loop solutions are forward complete.

(i) Counting invariance. Consider C~inv={x~:Hinv(x~)≥0}\widetilde{C}_{\mathrm{inv}}=\{\widetilde{x}:H_{\mathrm{inv}}(\widetilde{x})\geq0\}. Let D~inv⊆C~inv\widetilde{D}_{\mathrm{inv}}\subseteq\widetilde{C}_{\mathrm{inv}} be an open set such that, for every x~∈D~inv\widetilde{x}\in\widetilde{D}_{\mathrm{inv}}, there exists i∈Ii\in\mathcal{I} such that ∂Hinv∂xi(x~)Gi(xi)≠0⊤\frac{\partial H_{\mathrm{inv}}}{\partial x_i}(\widetilde{x})G_i(x_i)\neq\mathbf{0}^{\top}. Then the QP controller in (19) with δinv=0\delta_{\mathrm{inv}}=0 satisfies the counting invariance task for every x~(0)∈C~inv\widetilde{x}(0)\in\widetilde{C}_{\mathrm{inv}}.

(ii) Counting convergence. Consider C~conv={x~:Hconv(x~)≥0}\widetilde{C}_{\mathrm{conv}}=\{\widetilde{x}:H_{\mathrm{conv}}(\widetilde{x})\geq0\}. Suppose that for every x~∉C~conv\widetilde{x}\notin\widetilde{C}_{\mathrm{conv}}, there exists i∈Ii\in\mathcal{I} such that ∂Hconv∂xi(x~)Gi(xi)≠0⊤\frac{\partial H_{\mathrm{conv}}}{\partial x_i}(\widetilde{x})G_i(x_i)\neq\mathbf{0}^{\top}. Assume that (18) holds for all x∉Cconvx\notin C_{\mathrm{conv}} with a class-K\mathcal{K} function γh\gamma_h. Then, the QP controller in (19) with δconv=0\delta_{\mathrm{conv}}=0 satisfies the counting convergence task for every x~(0)∉T~conv\widetilde{x}(0)\notin\widetilde{T}_{\mathrm{conv}}.

Proof. (i) Since the gradient of hinvh_{\mathrm{inv}} is locally Lipschitz, the gradient of Hinv=h(minv)H_{\mathrm{inv}}=h_{(m_{\mathrm{inv}})} is locally Lipschitz, as follows from (13). By the nonvanishing condition ∂Hinv∂xi(x~)Gi(xi)≠0⊤\frac{\partial H_{\mathrm{inv}}}{\partial x_i}(\widetilde{x})G_i(x_i)\neq\mathbf{0}^{\top}, the active constraints of the QP in (19) with δinv=0\delta_{\mathrm{inv}}=0 are linearly independent on D~inv\widetilde{D}_{\mathrm{inv}}. Note that without input bounds, and by choosing the slack variable δconv\delta_{\mathrm{conv}} sufficiently large, the inequality in (19) is always feasible for all x~∈D~inv\widetilde{x}\in\widetilde{D}_{\mathrm{inv}}. Together with strong convexity of the objective and local Lipschitz continuity of α\alpha, u~nom\widetilde{u}_{\mathrm{nom}}, fif_i and GiG_i, i∈Ii\in\mathcal{I}, this implies that the unique optimizer u~∗(x~)\widetilde{u}^{*}(\widetilde{x}) is locally Lipschitz on D~inv\widetilde{D}_{\mathrm{inv}}. According to Def. 2.1, we get that the HinvH_{\mathrm{inv}} constructed in (11) is indeed a CBF. Then, applying Prop. 4.1(i), together with forward completeness, we get that C~inv\widetilde{C}_{\mathrm{inv}} is forward invariant ∀t∈R≥0\forall t\in\mathbb{R}_{\geq0}. Recalling that C~inv⊆T~inv\widetilde{C}_{\mathrm{inv}}\subseteq\widetilde{T}_{\mathrm{inv}} by (16), the counting invariance task is satisfied for every x~(0)∈C~inv\widetilde{x}(0)\in\widetilde{C}_{\mathrm{inv}}.

(ii) Similarly, the nonvanishing condition ensures linear independence of the active constraints of the QP in (19) with δconv=0\delta_{\mathrm{conv}}=0. Thus, u~∗(x~)\widetilde{u}^{*}(\widetilde{x}) is locally Lipschitz on RMn∖C~conv\mathbb{R}^{Mn}\setminus\widetilde{C}_{\mathrm{conv}}. Moreover, with the QP being feasible for all x~∉C~conv\widetilde{x}\notin\widetilde{C}_{\mathrm{conv}}, we get that HconvH_{\mathrm{conv}} constructed in (11) satisfies (14) for all x~∉C~conv\widetilde{x}\notin\widetilde{C}_{\mathrm{conv}}. Since (18) holds for x∉Cconvx\notin C_{\mathrm{conv}}, by Lemma 4.2, (15) holds for all x~∉T~conv\widetilde{x}\notin\widetilde{T}_{\mathrm{conv}}. Recalling that C~conv⊆T~conv\widetilde{C}_{\mathrm{conv}}\subseteq\widetilde{T}_{\mathrm{conv}} by (17). By applying Prop. 4.1(ii), together with the forward completeness, we get that T~conv\widetilde{T}_{\mathrm{conv}} is attractive. Hence, the counting convergence task is satisfied for every x~(0)∉T~conv\widetilde{x}(0)\notin\widetilde{T}_{\mathrm{conv}}. ■

Numerical Results

In this section, we evaluate the scalability of the proposed recursion-based method and illustrate controller synthesis for counting invariance and counting convergence tasks through a multi-drone emergency response case study. Simulations were run in MATLAB R2025a on a computer equipped with an AMD Ryzen 7 PRO 8845HS processor and 32 GB of RAM.

Computational performance and scalability

Let MM denote the total number of agents and mm the required agent count. We evaluate the computation times required to calculate the CBF and its gradient using the recursion-based method in Sec. III. For comparison, we consider a naïve combinatorial method that explicitly enumerates all subsets of cardinalities mm and m−1m-1, computes the LogSumExp approximations σ^m\hat{\sigma}_m and σ^m−1\hat{\sigma}_{m-1} from (7), and evaluates the candidate CBF h(m)h_{(m)} in (8) and its gradient. Both methods yield the same CBF and gradient, but the recursion-based method avoids combinatorial computational complexity by reusing intermediate quantities. Two experiments are conducted in MATLAB: (i) varying MM from 8 to 20000, with m/M≈0.4m/M \approx0.4, and (ii) varying mm from 1 to 241, with M=500M = 500. For each experiment, the task function values hih_i are randomly generated, and the median computation times over 15 evaluations are reported. We choose

τ=Wln⁡(Mm)+ln⁡(Mm−1),W=0.1,\tau= \frac{W}{\ln\left(\frac{M}{m}\right) + \ln\left(\frac{M}{m-1}\right)}, \qquad W = 0.1,

to ensure 0≤h(m)−h(m)≤W0 \le h_{(m)} - h_{(m)} \le W, according to (9). The results in Fig. 2-3 are consistent with the complexity analysis in Sec. III-D. In Fig. 2, computation time of the proposed approach scales approximately quadratically with MM at a fixed ratio m/Mm/M, remaining below 10 ms even at M=800M = 800. In contrast, combinatorial enumeration becomes prohibitive for online computation with only M=20M = 20 agents. In Fig. 3, computation time scales approximately linearly with mm for M=500M = 500, remaining below 3 ms for all tested values of mm.

These computation times quantify the cost of evaluating the CBF and its gradient at each sampling instant before solving the QP in (19). The results demonstrate the potential of the proposed method for real-time control of hundreds of agents, even when the task requires a large fraction of the team to satisfy the prescribed condition.

Case study

We illustrate the proposed framework on a multi-drone emergency response scenario. A fleet of M=12M = 12 drones delivers supplies between villages following an earthquake, with each drone assigned two villages to visit alternately. The emergency response protocol requires at least minv=5m_{\mathrm{inv}} = 5 drones to remain in the standby region

Cinv={x∈R2:hinv(x)=9−∥x∥2≥0},\mathcal{C}_{\mathrm{inv}} = \left\{ \mathbf{x} \in\mathbb{R}^{2} : h_{\mathrm{inv}}(\mathbf{x}) = 9 - \lVert\mathbf{x} \rVert^{2} \ge0 \right\},

maintaining a reserve in case of potential aftershocks. This defines a counting invariance task as in Def. 2.2. Figure 4 shows the drones in yellow, the villages in gray, and the standby region in blue.

Figure 4. Drone positions at (a) t=0t = 0, (b) t=3.5t = 3.5 (before the aftershock), and (c) t=8.3t = 8.3, (d) t=15t = 15 (after). Drones (in yellow), villages (in gray), the standby region (in blue), and the emergency region (in red) are shown.

At time t=5t = 5, an aftershock activates a counting convergence task as in Def. 2.3 requiring at least mconv=6m_{\mathrm{conv}} = 6 drones to converge to the emergency region

Cconv={x∈R2:hconv(x)=4−∥x−[−72]T∥2≥0},\mathcal{C}_{\mathrm{conv}} = \left\{ \mathbf{x} \in\mathbb{R}^{2} : h_{\mathrm{conv}}(\mathbf{x}) = 4 - \left\lVert\mathbf{x} - \begin{bmatrix} -7 & 2 \end{bmatrix}^{\mathsf{T}} \right\rVert^{2} \ge0 \right\},

shown in red in Figure 4. The standby invariance task is reduced to minv′=3m'_{\mathrm{inv}} = 3 drones, and its CBF constraint is relaxed using

Figure 3. Experiment (ii): Computation times of the recursion-based method as mm increases, with M=500M = 500.

a slack variable δinv≥0\delta_{\mathrm{inv}} \ge0 with penalty weight pinv=1000p_{\mathrm{inv}} = 1000 as in (19). The emergency convergence task is enforced without relaxation (δconv=0\delta_{\mathrm{conv}} = 0), prioritizing the emergency response task over the standby invariance task as described in Remark 4.3.

Each drone follows single-integrator dynamics, i.e.,

x˙i=ui,i∈I,\dot{\mathbf{x}}_i = \mathbf{u}_i, \qquad i \in\mathcal{I},

where xi,ui∈R2\mathbf{x}_i,\mathbf{u}_i \in\mathbb{R}^{2} denote its position and velocity, respectively. Both hinvh_{\mathrm{inv}} and hconvh_{\mathrm{conv}} have locally Lipschitz gradients. Moreover, hconvh_{\mathrm{conv}} satisfies (18), by choosing γh(s)=s\gamma_h(s) = s.

Following Sec. III, we construct CBFs for the counting tasks. For t∈[0,5)t \in[0,5), we construct HinvH_{\mathrm{inv}} from hinvh_{\mathrm{inv}} and minv=5m_{\mathrm{inv}} = 5. For t∈[5,15]t \in[5,15], we construct HconvH_{\mathrm{conv}} and Hinv′H'_{\mathrm{inv}} from hconvh_{\mathrm{conv}}, mconv=6m_{\mathrm{conv}} = 6, and hinvh_{\mathrm{inv}}, minv′=3m'_{\mathrm{inv}} = 3, respectively. We evaluate their values and gradients using the forward and backward recursions in Alg. 1. We choose τ≈0.0074\tau\approx0.0074, ensuring that the worst-case approximation error is at most 0.1 for all three counting tasks, according to (9). The resulting CBF constraints are incorporated into the QP in (19) for controller synthesis.

The individual delivery objective of each drone ii, i∈Ii \in\mathcal{I}, is encoded by the nominal input

ui,nom=−c1c2∥xi−ri∥22(1+c1∥xi−ri∥2)(xi−ri),\mathbf{u}_{i,\mathrm{nom}} = -c_1 c_2 \frac{\lVert\mathbf{x}_i-\mathbf{r}_i\rVert^2}{2\left(1+c_1\lVert\mathbf{x}_i-\mathbf{r}_i\rVert^2\right)}(\mathbf{x}_i-\mathbf{r}_i),

where ri\mathbf{r}_i is the center of the current target village, c1=105c_1 = 10^5 and c2=5c_2 = 5. Whenever a drone reaches within distance 0.2 of its current target village’s center, its target is updated to the other assigned village.

Figure 4(a)-(Figure 4d) show snapshots of the fleet at initial deployment (t=0t = 0), before the aftershock (t=3.5t = 3.5), after the aftershock but before convergence (t=8.3t = 8.3) and after convergence (t=15t = 15), respectively. Figure 5 shows the numbers of drones in the standby and emergency regions over time, together with the desired thresholds, i.e., minv=5m_{\mathrm{inv}} = 5 for t∈[0,5)t \in[0, 5), and mconv=6m_{\mathrm{conv}} = 6, minv′=3m'_{\mathrm{inv}} = 3 for t∈[5,15]t \in[5, 15]. The standby invariance task is satisfied throughout [0,5)[0, 5), while the emergency region count first reaches six at t=10.82t = 10.82, corresponding to a response time of 5.825.82 after the aftershock. Figure 6 relates these counts to the exact ordered values and the corresponding CBFs: at least mm drones belong to a region if and only if h(m)≥0h(m) \ge0, while the CBF HH is a lower approximation of h(m)h(m). At t=15t = 15, both counting requirements hold, as confirmed by Figure 4-Figure 6. These results demonstrate that the proposed framework enables controller synthesis for both counting invariance and counting convergence tasks, while accommodating individual objectives.

Figure 5. Drone counts and desired thresholds for the standby invariance and emergency convergence tasks.

Figure 6. CBFs and exact ordered values for the standby invariance and emergency convergence tasks.

Conclusion

This paper proposes an online CBF-based control synthesis framework for counting invariance and counting convergence tasks in continuous-time multi-agent systems. A recursion-based method enables efficient construction and evaluation of differentiable CBFs without explicit task allocation or enumeration of agent subteams. The framework provides theoretical guarantees of counting-task satisfaction and is validated through a multi-drone emergency-response case study. Future work includes extensions to more general cLTL specifications and higher-order dynamics through high-order CBFs [14], experimental validation, and distributed implementations.

References

  1. [1]M. Kloetzer and C. Belta, “Temporal logic planning and control of robotic swarms by hierarchical abstractions,” IEEE Trans. Robot., vol. 23, no. 2, pp. 320–330, 2007.DOI
  2. [2]Y. E. Sun, P. Nilsson, and N. Ozay, “Provably-correct coordination of large collections of agents with counting temporal logic constraints,” in Proc. ACM/IEEE Int. Conf. Cyber-Phys. Syst., 2017, pp. 249–258.
  3. [3]——, “Multirobot coordination with counting temporal logics,” IEEE Trans. Robot., vol. 36, no. 4, pp. 1189–1206, 2019.
  4. [4]X. Qiu, R. Wang, S. Liu, and S. Haesaert, “Compressing correct-by-design synthesis for stochastic homogeneous multi-agent systems with counting tl,” Proc. 65th IEEE Conf. Decis. Control, to appear, 2026.DOI
  5. [5]A. D. Ames, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs with application to adaptive cruise control,” in Proc. 53rd IEEE Conf. Decis. Control, 2014, pp. 6271–6278.DOI
  6. [6]A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada, “Control barrier functions: Theory and applications,” in Proc. 18th Eur. Conf. Control, 2019, pp. 3420–3431.arxiv.org/abs/1903.11199
  7. [7]L. Lindemann and D. V. Dimarogonas, “Control barrier functions for signal temporal logic tasks,” IEEE Control Syst. Lett., vol. 3, no. 1, pp. 96–101, 2019.DOI
  8. [8]M. Srinivasan and S. Coogan, “Control of mobile robots using barrier functions under temporal logic specifications,” IEEE Trans. Robot., vol. 37, no. 2, pp. 363–374, 2021.arxiv.org/abs/1908.04903
  9. [9]G. Mitsos and S. Liu, “Control synthesis for security hyperproperties via control barrier functions,” IEEE Control Syst. Lett., to appear, 2026.DOI
  10. [10]P. Clotfelter, J. Cortés, and M. Egerstedt, “A nonsmooth approach to controller synthesis for boolean specifications,” IEEE Trans. Autom. Control, vol. 66, no. 11, pp. 5160–5174, 2021.
  11. [11]T. G. Molnar and A. D. Ames, “Composing control barrier functions for complex safety specifications,” IEEE Control Syst. Lett., vol. 7, pp. 3615–3620, 2023.arxiv.org/abs/2309.06647
  12. [12]P. Ong, H. Lee, T. G. Molnar, D. Panagou, and A. Ames, “Combinatorial control barrier functions: Nested boolean and p-choose-r compositions of safety constraints,” IEEE Control Syst. Lett., vol. 9, pp. 2705–2710, 2025.DOI
  13. [13]H. K. Khalil, Nonlinear Systems, 3rd ed. Prentice Hall, 2002.
  14. [14]W. Xiao and C. Belta, “Higher-order control barrier functions,” IEEE Trans. Autom. Control, vol. 67, no. 7, pp. 3655–3662, 2021.

Paper details

vlnc:W_uuv2ated
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents