betaFeedback

WorksEngineering

Representing Differential Inclusions as Monads: A Framework for Compositional Controller Synthesis

Abstract

Sequential composition of safety-certified controllers for hybrid and non-smooth robotic systems is well studied piecewise. Yet no existing framework reduces this question to a single algebraic condition. We construct a trajectory monad for Filippov-regular differential inclusions. Its Kleisli category treats controllers as morphisms and sequential execution as trajectory concatenation. Control Barrier Function (CBF) certification, a guarantee of forward invariance, corresponds to a sub-monad of this category. Joint safety of composed controllers then follows from one algebraic condition. All controllers must land in a common sub-monad, which is closed under the monad multiplication. The sub-monad condition recasts recasts existing CBF composition practice categorically. It explains why a smooth intersection of multiple barriers supports safe composition, while enforcing barriers phase by phase does not. For the phase-by-phase case, we derive a closed-form Bernoulli model of the failure rate. We validate it over a randomized sweep of 3{,}000 instances. The same sweep shows that the standard baseline degrades under constraint conflict as the barrier count grows. This baseline enforces all barriers simultaneously as constraints in a single quadratic program (QP). We instantiate the framework on a four-mode piecewise-affine system and on a unicycle reduced-order model over heterogeneous terrain.

Introduction

Compositional controller design is a fundamental challenge in hybrid robotics, including legged locomotion, manipulation with contacts, and variable-structure control. Given controllers certified to be individually safe, does their sequential execution produce a jointly safe trajectory? Existing approaches answer this piecewise, each under its own composition regime. No unifying account explains why some composition strategies preserve safety certificates while others provably fail.

Several mature lines of work address pieces of this problem. Boolean and smooth CBF compositions [1, 2, 3, 4] prove forward invariance for min/max, smooth AND/OR, and nested Boolean combinations of barriers. They are compositional within a fixed operating mode. A separate line of work asks when several CBFs can be enforced jointly without emptying the input-constrained feasible set [5], [6]. We observe this QP infeasibility empirically for the simultaneous-constraint baseline in §VI. Outside the CBF literature, sequential composition has a long history in robotics through funnels built from Lyapunov sublevel sets [7]. Sum-of-squares funnel libraries later made this approach robust to disturbances [8]. Assume-guarantee contracts [9] provide cascade and feedback composition theorems for continuous-time invariance, with extensions to hybrid systems [10].

Monadic and categorical systems theory [11, 12, 13, 14] has used Kleisli categories for dynamical-system composition since the work in [14]. The hybrid monad of [12] is the closest predecessor to our construction.

None of these frameworks gives a unified categorical formulation in which CBF certificates lift as sub-monadic structure with provably closed Kleisli composition. The Boolean nonsmooth compositions of [1] are mode-local and do not address sequential phase transitions. Funnel-based sequential composition [7], [8] checks compatibility funnel by funnel rather than through a single algebraic condition. It also targets Lyapunov sublevel sets rather than CBF-certified safe sets. The input-constrained compatibility conditions of [5], [6] guarantee feasibility of the composed QP. Like the Boolean compositions, however, they are stated mode-locally rather than across sequential handoffs. The hybrid monad [12], [13] handles hybrid trajectory composition but does not embed safety certificates. Assume-guarantee contracts [9] give sufficient conditions for composition in a contract-based formalism rather than an algebraic one. Within that framework, the question of why composition fails has no algebraic answer.

Contribution. We develop a trajectory monad that fills this gap. It is a mathematical structure on Filippov-regular differential inclusions. Its Kleisli category is a formal language for composing safety-certified controllers. Its sub-monad structure gives a sufficient condition for compositional safety and a precise account of why naive composition fails. The sub-monad account also has analytical consequences. It identifies the failure mode as a local mismatch of sub-monad membership at each Kleisli handoff. This locality lets us model the failure probability as a sequence of independent trials, one per handoff (§VI).

Specifically, the contributions of this work are: 1) Construction of the trajectory monad for Filippov-regular differential inclusions on diffeological spaces, with the monad laws holding exactly (§III). 2) Formalization of sequential controller design in the resulting Kleisli category, which encodes mode switching as Kleisli composition (§IV). 3) Lifting of CBF certificates to sub-monads, a characterization of when Kleisli composition fails, and a sufficient condition for compositional safety. The condition is a common sub-monad, realized by a smooth intersection CBF with an explicit margin (§V). 4) A closed-form Bernoulli model for the naive failure rate, which treats each Kleisli handoff as an independent trial. The sub-monad mismatch structure of §V motivates this decomposition. We validate the model over 3,000 randomized instances with phase counts n∈{2,…,6}n \in\{2,\ldots,6\} and barrier counts k∈{2,…,5}k \in\{2,\ldots,5\}. The same sweep shows the standard simultaneousconstraint QP baseline degrading under constraint conflict as kk grows (§VI). 5) Numerical instantiation on two use cases, a four-mode piecewise-affine (PWA) system and a unicycle reduced-order model on heterogeneous terrain (§VII).

Related work. The categorical treatment of open dynamical systems via polynomial functors and lenses is developed in [11]. Section 2.3 of that work uses Kleisli composition explicitly as a systems-composition language. We specialize to Filippov systems and add safety-certificate lifting, which does not appear there. The hybrid monad of [12], [13] uses the same Moore-path construction for strictly associative hybrid composition. Its authors use it to define the meaning of loops in hybrid programs. They do not address safety certificates or controller design (see Remark 3.1). The sheaf-theoretic formulation of [15] offers a complementary account of dynamical-system composition. The smooth Boolean CBF compositions of [3], [16] and the softmin barrier analysis of [17] are the engineering tools we embed into the monadic framework. We recover their safety guarantee from sub-monad closure (Theorem 5.4).

Preliminaries

System Model and Filippov Regularity

Let MM be a smooth manifold of dimension dd representing the state space. Consider the control-affine system

x˙=f(x)+B(x) u,u∈U⊂Rm,(1)\dot{x} = f(x) + B(x)\,u,\quad u \in\mathbb{U} \subset\mathbb{R}^{m}, \tag*{(1)}

where f:M→TMf : M \to TM and B(x):Rm→TxMB(x) : \mathbb{R}^{m} \to T_xM, with TMTM the tangent bundle of MM. We assume ff and BB are locally bounded and measurable, and locally Lipschitz away from finitely many switching surfaces. The input set U\mathbb{U} is compact and convex. The dynamics may switch discontinuously, e.g., at contact events or in variable-structure control. The right-hand side of (1) then need not admit a classical solution. We instead model such behavior via the Filippov differential inclusion [18], [19]

x˙∈F(x):=⋂ρ>0⋂Leb⁡(N)=0co⁡‾{f(y)+B(y)u∣y∈Bρ(x)∖N, u∈U}.(2)\dot{x} \in F(x) := \bigcap_{\rho>0}\bigcap_{\operatorname{Leb}(\mathcal{N})=0}\overline{\operatorname{co}}\{f(y)+B(y)u \mid y \in\mathcal{B}_{\rho}(x)\setminus\mathcal{N},\ u\in\mathbb{U}\}. \tag*{(2)}

Here co⁡‾{⋅}\overline{\operatorname{co}}\{\cdot\} denotes the closed convex hull, and Bρ(x)\mathcal{B}_{\rho}(x) is the ball of radius ρ\rho about xx in local coordinates. The inner intersection ranges over all Lebesgue-null sets N\mathcal{N}. Where ff and BB are continuous, F(x)F(x) reduces to the set of control-reachable velocities co⁡{f(x)+B(x)u∣u∈U}\operatorname{co}\{f(x)+B(x)u\mid u\in\mathbb{U}\}. On a switching surface, it also convexifies the velocities of the adjacent modes. This is what admits absolutely continuous solutions across the switch.

Assumption 2.1 (Filippov regularity [18]): The set-valued map F:M⇒TMF : M \Rightarrow TM is upper-semicontinuous with nonempty compact convex values everywhere on MM. Assumption 2.1 holds for (2) whenever ff and BB are locally bounded and measurable and U\mathbb{U} is compact and convex [19]. It therefore holds for all PWA systems with box input sets. Under Assumption 2.1, Filippov’s theorem guarantees that a solution exists on some [0,r][0,r] from every x0∈Mx_0\in M. The solution need not be unique.

Control Barrier Functions

Let h:M→Rh : M \to\mathbb{R} be a continuously differentiable function and let C={x∈M:h(x)≥0}\mathcal{C}=\{x\in M:h(x)\ge0\} be the corresponding safe set.

Definition 2.1 (Control Barrier Function [20]): A function hh is a Control Barrier Function (CBF) for system (1) if some extended class-K\mathcal{K} function α\alpha satisfies

sup⁡u∈U[∇h(x)T(f(x)+B(x)u)]≥−α(h(x))\sup_{u\in\mathbb{U}}\left[\nabla h(x)^{\mathsf{T}}\left(f(x)+B(x)u\right)\right]\ge-\alpha(h(x))

for all x∈Mx\in M. An extended class-K\mathcal{K} function is continuous and strictly increasing on all of R\mathbb{R}, with α(0)=0\alpha(0)=0.

If hh is a CBF, the CBF-QP safety filter

u∗(x)=arg⁡min⁡u∈U ∥u−unom(x)∥2u^*(x)=\underset{u\in\mathbb{U}}{\arg\min}\ \lVert u-u_{\mathrm{nom}}(x)\rVert^2
s.t.∇h(x)T(f(x)+B(x)u)≥−αh(x)(3)\text{s.t.}\quad\nabla h(x)^{\mathsf{T}}\left(f(x)+B(x)u\right)\ge-\alpha h(x) \tag*{(3)}

renders C\mathcal{C} forward-invariant [20]. That is, x(0)∈Cx(0)\in\mathcal{C} implies x(t)∈Cx(t)\in\mathcal{C} for all t≥0t\ge0. Here unom:M→Uu_{\mathrm{nom}}:M\to\mathbb{U} is a nominal (task-level) controller. Throughout, we take the linear choice α(h)=αh\alpha(h)=\alpha h with scalar gain α>0\alpha>0, as in (3). This choice only fixes the implemented constraint. Our results in §III–§V use only forward invariance and hold for any extended class-K\mathcal{K} function.

Categorical Preliminaries

We recall the minimal diffeology background used in §III, together with monads and Kleisli categories. See [21] and [11] for the general theories. Throughout, ∘\circ denotes composition of functors, natural transformations, or morphisms in an arbitrary category C\mathcal{C}, as determined by context.

Definition 2.2 (Diffeology): A diffeology on a set XX plays the role for an arbitrary set that a smooth atlas plays for a manifold. It specifies which maps into XX, from open Euclidean domains, count as smooth. Formally, a diffeology assigns to every open O⊂RpO\subset\mathbb{R}^{p} (any p≥0p\ge0) a set of maps O→XO\to X, called plots, with three properties. 1) Every constant map O→XO\to X is a plot. 2) (Locality) If O=⋃iOiO=\bigcup_i O_i is an open cover and the restriction of λ:O→X\lambda:O\to X to each OiO_i is a plot, then λ\lambda itself is a plot. 3) (Smooth reparametrization) If λ:O→X\lambda:O\to X is a plot and g:O′→Og:O'\to O is smooth in the ordinary sense for open O′⊂Rp′O'\subset\mathbb{R}^{p'}, then λ∘g\lambda\circ g is a plot. A set together with a diffeology is a diffeological space.

Definition 2.3 (Smooth maps): A map q:X→Yq:X\to Y between diffeological spaces is smooth if q∘λq\circ\lambda is a plot of YY for every plot λ\lambda of XX. Let D⊂RpD\subset\mathbb{R}^{p} be a subset that is not open. A map defined on DD is smooth if, around every point of DD, it extends to a smooth map on an open neighborhood in Rp\mathbb{R}^{p}. We write Diff for the category of diffeological spaces with smooth maps as morphisms.

Every smooth manifold carries a canonical diffeology whose plots are the smooth maps in the usual sense. This assignment is a full and faithful embedding Man↪Diff\mathrm{Man}\hookrightarrow\mathrm{Diff} [21]. We use it to regard MM as an object of Diff without altering its manifold structure. Unlike Man, the category of smooth manifolds, Diff⁡\operatorname{Diff} is complete, cocomplete, and cartesian closed [21]. Section III uses these properties.

The following definitions are standard and are stated for a generic monad (T,η,μ)(T,\eta,\mu) on an arbitrary category CC; §III specializes C=Diff⁡C=\operatorname{Diff} and constructs the specific trajectory monad (T,η,μ)(\mathcal{T},\eta,\mu).

Definition 2.4 (Monad): A monad on a category CC is a triple (T,η,μ)(T,\eta,\mu). Here T:C→CT:C\to C is an endofunctor, η:Id⁡C⇒T\eta:\operatorname{Id}_{C}\Rightarrow T is a natural transformation called the unit, and μ:T∘T⇒T\mu:T\circ T\Rightarrow T is a natural transformation called the multiplication. They satisfy the left unit law μ∘ηT=id⁡T\mu\circ\eta_{T}=\operatorname{id}_{T}, the right unit law μ∘T(η)=id⁡T\mu\circ T(\eta)=\operatorname{id}_{T}, and the associativity law μ∘μT=μ∘T(μ)\mu\circ\mu_{T}=\mu\circ T(\mu). The functor Id⁡C\operatorname{Id}_{C} is the identity on CC, and id⁡T\operatorname{id}_{T} is the identity natural transformation on TT, with components (id⁡T)A=id⁡T(A)(\operatorname{id}_{T})_{A}=\operatorname{id}_{T(A)}.

Definition 2.5 (Kleisli category): The Kleisli category Kl⁡(T)\operatorname{Kl}(T) of a monad (T,η,μ)(T,\eta,\mu) on CC has the same objects as CC. A Kleisli morphism φ:X→Y\varphi:X\to Y in Kl⁡(T)\operatorname{Kl}(T) is a morphism φ:X→T(Y)\varphi:X\to T(Y) in CC. Two such morphisms φ:X→T(Y)\varphi:X\to T(Y) and χ:Y→T(Z)\chi:Y\to T(Z) compose as

χ∘Kφ:=μZ∘T(χ)∘φ:X→T(Z),(4)\chi\circ_{K}\varphi:=\mu_{Z}\circ T(\chi)\circ\varphi:X\to T(Z), \tag*{(4)}

where ∘K\circ_{K} denotes Kleisli composition.

Definition 2.6 (Sub-monad): A sub-monad of (T,η,μ)(T,\eta,\mu) is a monad (T′,η′,μ′)(T',\eta',\mu') together with a monad morphism ι:T′↪T\iota:T'\hookrightarrow T, which is a natural transformation commuting with units and multiplications. We say T′T' is a sub-monad of TT and write T′⊂TT'\subset T.

Running Examples

We consider two systems as use cases throughout the paper. Both satisfy Assumption 2.1, so the trajectory monad construction of §III applies to each.

Use Case I (four-mode PWA system). Let x=(x1,x2)T∈R2x=(x_{1},x_{2})^{\mathsf{T}}\in\mathbb{R}^{2} be the state. The system is x˙=Aℓ(x)x+cℓ(x)+u\dot{x}=A_{\ell(x)}x+c_{\ell(x)}+u with u∈U=[−1,1]2u\in U=[-1,1]^{2}. The mode index ℓ(x)∈{1,2,3,4}\ell(x)\in\{1,2,3,4\} is the quadrant of xx [22]. Each mode combines a contraction with a rotation, and the rotation direction alternates between adjacent quadrants. We use

A1=A3=[−0.41.5−1.5−0.4]A_{1}=A_{3}=\begin{bmatrix}-0.4&1.5\\-1.5&-0.4\end{bmatrix}

and A2=A4=A1TA_{2}=A_{4}=A_{1}^{\mathsf{T}}. The offsets are c1=(0.2,0.2)Tc_{1}=(0.2,0.2)^{\mathsf{T}}, c2=(−0.2,0.2)Tc_{2}=(-0.2,0.2)^{\mathsf{T}}, c3=−c1c_{3}=-c_{1}, and c4=−c2c_{4}=-c_{2}, so each offset points away from the origin into its own quadrant. This corresponds to f(x)=Aℓ(x)x+cℓ(x)f(x)=A_{\ell(x)}x+c_{\ell(x)} and B(x)=I2B(x)=I_{2} in (1). In the interior of each quadrant, the map (2) is F(x)=Aℓ(x)x+cℓ(x)+[−1,1]2F(x)=A_{\ell(x)}x+c_{\ell(x)}+[-1,1]^{2}. On the coordinate axes, it is the convex hull of the adjacent modes’ velocity sets. In both cases F(x)F(x) is a compact convex polytope.

Use Case II (modal unicycle reduced-order model). Let ξ=(px,py,ψ)T∈M:=R2×S1\xi=(p_{x},p_{y},\psi)^{\mathsf{T}}\in M:=\mathbb{R}^{2}\times S^{1}, where (px,py)(p_{x},p_{y}) is the planar position and ψ\psi is the heading angle. The control input is u=(v,ω)Tu=(v,\omega)^{\mathsf{T}}, with forward speed vv and yaw rate ω\omega. The unicycle reduced-order model (ROM) [23] has input matrix

G(ξ)=[cos⁡ψ0sin⁡ψ001].G(\xi)=\begin{bmatrix}\cos\psi&0\\\sin\psi&0\\0&1\end{bmatrix}.

We add terrain modes that make the plant a genuine Filippov system. The mode ℓ(ξ)=arg⁡min⁡ihi(ξ)∈{1,2,3}\ell(\xi)=\arg\min_{i}h_{i}(\xi)\in\{1,2,3\} indexes the most binding of the three barriers of §VII, which represent flat ground, stepping stones, and a slope edge. The dynamics are ξ˙=fℓ(ξ)(ξ)+G(ξ)u\dot{\xi}=f_{\ell(\xi)}(\xi)+G(\xi)u with u∈Uℓ(ξ)=[0,vmax⁡,ℓ]×[−ωmax⁡,ℓ,ωmax⁡,ℓ]u\in U_{\ell(\xi)}=[0,v_{\max,\ell}]\times[-\omega_{\max,\ell},\omega_{\max,\ell}]. The limits (vmax⁡,ℓ,ωmax⁡,ℓ)(v_{\max,\ell},\omega_{\max,\ell}) are (0.45,1.50)(0.45,1.50), (0.25,0.90)(0.25,0.90), and (0.35,1.10)(0.35,1.10) for ℓ=1,2,3\ell=1,2,3, in m/s and rad/s. Only the stepping stones carry drift, f2=(0.015,0,0)Tf_{2}=(0.015,0,0)^{\mathsf{T}} m/s, while f1=f3=0f_{1}=f_{3}=0. This corresponds to f=fℓ(ξ)f=f_{\ell(\xi)} and B=GB=G in (1).

The modes switch on the surfaces {hi=hj}\{h_{i}=h_{j}\}, where both the input set and the drift jump. The drift f2f_{2} lies outside the span of G(ξ)G(\xi) unless the robot heads along the pxp_{x}-axis. The velocity sets of mode 2 and its neighbors are then disjoint, so (2) convexifies across a genuine discontinuity. Assumption 2.1 holds because the drift is bounded and each UℓU_{\ell} is compact and convex. Cohen et al. [23] show that the unicycle ROM captures the safety-relevant navigation behavior of an 18-DOF quadruped.

The Trajectory Monad

Definition 2.5 presupposes a monad on the systems of interest. Before asking whether CBF certificates are preserved under sequential composition, we construct one. We write (T,η,μ)(\mathcal{T},\eta,\mu) for this specific trajectory monad, to distinguish it from the generic monad (T,η,μ)(T,\eta,\mu) of Definitions 2.4–2.6. The endofunctor T\mathcal{T} sends each state to the trajectories it can generate. The unit η\eta regards a state as the trivial trajectory at that state. The multiplication μ\mu flattens a trajectory of trajectories. It follows the initial points of the inner trajectories and then appends the last inner trajectory.

We construct T(M)\mathcal{T}(M) in Diff⁡\operatorname{Diff}, the category of diffeological spaces [21]. The space of all admissible trajectories of (2) is infinite-dimensional and not itself a manifold. The category Diff⁡\operatorname{Diff}, by contrast, is complete, cocomplete, and cartesian closed, and it contains every smooth manifold as a full subcategory [21]. The state space MM therefore remains the finite-dimensional manifold of §II-A. Only T(M)\mathcal{T}(M) needs the added generality.

The one genuine difficulty is associativity of concatenation. Suppose trajectories are parametrized on a fixed interval such as [0,1][0,1]. Concatenating two of them then requires rescaling each by a factor of two. Concatenating a third depends on which pair is rescaled first. Associativity then holds only up to a reparametrizing homeomorphism, not as literal equality of functions. Moore trajectories keep their true duration instead of being rescaled onto a fixed interval. They give strict, on-the-nose associativity (§III-A).

Throughout, T\mathcal{T} denotes this specific trajectory monad and Kl⁡(T)\operatorname{Kl}(\mathcal{T}) its Kleisli category. Strictly speaking, T\mathcal{T} acts on pairs (M,FM)(M,F_{M}), since T(M)\mathcal{T}(M) contains only trajectories admissible for FMF_{M}. It acts on smooth maps q:M→Nq:M\to N that send admissible trajectories of FMF_{M} to admissible trajectories of FNF_{N} [24]. We suppress FF from the notation.

Moore Trajectories and Strict Associativity

Definition 3.1 (Moore trajectory space): A Moore trajectory of duration r≥0r\geq0 in MM is a pair (γ,r)(\gamma,r), where γ:[0,r]→M\gamma:[0,r]\to M is absolutely continuous. That is, γ\gamma is

differentiable almost everywhere, its derivative γ˙\dot{\gamma} lies in L1([0,r])L^{1}([0,r]), the space of Lebesgue-integrable functions on [0,r][0,r], and γ(t)=γ(0)+∫0tγ˙(s) ds\gamma(t)=\gamma(0)+\int_{0}^{t}\dot{\gamma}(s)\,\mathrm{d}s. The trajectory monad object is the disjoint union over all durations

T(M)=∐r≥0{(γ,r)∣γ:[0,r]→M, γ˙(t)∈F(γ(t)) a.e.}.(5)\mathcal{T}(M)=\coprod_{r\geq0}\left\{(\gamma,r)\mid\gamma:[0,r]\to M,\ \dot{\gamma}(t)\in F(\gamma(t))\ \text{a.e.}\right\}. \tag*{(5)}

The endpoint map is end⁡(γ,r)=γ(r)\operatorname{end}(\gamma,r)=\gamma(r). We equip T(M)\mathcal{T}(M) with the functional diffeology. A map λ:O→T(M)\lambda:O\to\mathcal{T}(M), with O⊂RpO\subset\mathbb{R}^{p} open and λ(z)=(γz,r(z))\lambda(z)=(\gamma_z,r(z)), is a plot iff the duration map z↦r(z)z\mapsto r(z) is smooth and the evaluation map (z,t)↦γz(t)(z,t)\mapsto\gamma_z(t) is smooth in the sense of Definition 2.3.

Consider two Moore trajectories (γ1,r1)(\gamma_1,r_1) and (γ2,r2)(\gamma_2,r_2) with γ1(r1)=γ2(0)\gamma_1(r_1)=\gamma_2(0). Their concatenation is defined by

(γ1⋅γ2)(t):={γ1(t)0≤t<r1,γ2(t−r1)r1≤t≤r1+r2.(\gamma_1\mathbin{\cdot}\gamma_2)(t):= \begin{cases} \gamma_1(t) & 0\leq t<r_1,\\ \gamma_2(t-r_1) & r_1\leq t\leq r_1+r_2. \end{cases}

The concatenation has duration ∣γ1⋅γ2∣=r1+r2|\gamma_1\mathbin{\cdot}\gamma_2|=r_1+r_2. Durations are real numbers, so (γ1⋅γ2)⋅γ3=γ1⋅(γ2⋅γ3)(\gamma_1\mathbin{\cdot}\gamma_2)\mathbin{\cdot}\gamma_3=\gamma_1\mathbin{\cdot}(\gamma_2\mathbin{\cdot}\gamma_3) holds strictly as functions. Both sides have duration r1+r2+r3r_1+r_2+r_3 and agree on every sub-interval.

Remark 3.1 (Relation to the hybrid monad): The hybrid monad of [12], [13] pairs a duration with a path in a similar way, and our multiplication follows theirs. They use it for strictly associative iteration semantics of hybrid computation, in a deterministic setting. Our construction transfers it to Filippov-admissible trajectories on diffeological spaces. It also lifts safety certificates as sub-monadic structure (§V), which neither prior work does.

Unit and Multiplication

Definition 2.4 requires a unit η\eta and a multiplication μ\mu in addition to the endofunctor. Having constructed T\mathcal{T}, we define these two pieces next.

Definition 3.2 (Unit): The unit ηM:M→T(M)\eta_M:M\to\mathcal{T}(M) maps each state to the duration-zero constant trajectory at that state,

ηM(x0)=(const⁡x0,0),\eta_M(x_0)=(\operatorname{const}_{x_0},0),

where const⁡x0:[0,0]→M\operatorname{const}_{x_0}:[0,0]\to M is the trivial path.

Definition 3.3 (Multiplication): Let head⁡(γ,r):=γ(0)\operatorname{head}(\gamma,r):=\gamma(0) denote the initial point of a Moore trajectory. An element of T(T(M))\mathcal{T}(\mathcal{T}(M)) is an outer Moore trajectory Γ:[0,R]→T(M)\Gamma:[0,R]\to\mathcal{T}(M) whose head path θ↦head⁡(Γ(θ))\theta\mapsto\operatorname{head}(\Gamma(\theta)) is admissible for FF. The multiplication follows the head path up to time RR and then appends the last inner trajectory,

μM(Γ):=(head⁡∘Γ,R)⋅Γ(R).\mu_M(\Gamma):=(\operatorname{head}\circ\Gamma,R)\mathbin{\cdot}\Gamma(R).

The concatenation is well defined because the head path ends at head⁡(Γ(R))\operatorname{head}(\Gamma(R)). This is the multiplication of the hybrid monad of [12], transferred to Filippov-admissible trajectories.

Monad Laws

Having fixed T\mathcal{T}, η\eta, and μ\mu, it remains to check the monad laws, including naturality of η\eta and μ\mu. For set-valued FF, naturality holds only under a regularity condition on FF. Filippov regularity (Assumption 2.1) supplies this condition.

For a map qq as above, define T(q)(γ,r)=(q∘γ,r)\mathcal{T}(q)(\gamma,r)=(q\circ\gamma,r). By the chain rule for absolutely continuous curves, T(q)\mathcal{T}(q) maps admissible trajectories of FMF_M to admissible trajectories of FNF_N.

Naturality of η\eta and μ\mu means that such a map qq commutes with the unit (“doing nothing”) and with concatenation, as in (6). It certifies the monad structure does not depend on the choice of coordinates.

M→qNηM↓↓ηNT(M)→T(q)T(N)T2(M)→T2(q)T2(N)μM↓↓μNT(M)→T(q)T(N)(6)\begin{CD} M @>q>> N \\ @V\eta_MVV @VV\eta_NV \\ \mathcal{T}(M) @>\mathcal{T}(q)>> \mathcal{T}(N) \end{CD} \qquad \begin{CD} \mathcal{T}^{2}(M) @>\mathcal{T}^{2}(q)>> \mathcal{T}^{2}(N) \\ @V\mu_MVV @VV\mu_NV \\ \mathcal{T}(M) @>\mathcal{T}(q)>> \mathcal{T}(N) \tag*{(6)} \end{CD}

Theorem 3.4 (Monad laws): Under Assumption 2.1, (T,η,μ)(\mathcal{T},\eta,\mu) is a monad on Diff\mathsf{Diff}, and the following diagrams commute on the nose.

T3(M)→T(μ)T2(M)μT↓↓μT2(M)→μT(M)T(M)→ηTT2(M)id⁡↓↓μT(M)=T(M)(7)\begin{CD} \mathcal{T}^{3}(M) @>\mathcal{T}(\mu)>> \mathcal{T}^{2}(M) \\ @V\mu_{\mathcal{T}}VV @VV\mu V \\ \mathcal{T}^{2}(M) @>\mu>> \mathcal{T}(M) \end{CD} \qquad \begin{CD} \mathcal{T}(M) @>\eta_{\mathcal{T}}>> \mathcal{T}^{2}(M) \\ @V\operatorname{id}VV @VV\mu V \\ \mathcal{T}(M) @= \mathcal{T}(M) \tag*{(7)} \end{CD}

Proof: [Sketch] Unit laws. For Γ=ηT(M)(γ,r)\Gamma=\eta_{\mathcal{T}(M)}(\gamma,r), the head path has duration zero and μM\mu_M returns (γ,r)(\gamma,r). For Γ=T(ηM)(γ,r)\Gamma=\mathcal{T}(\eta_M)(\gamma,r), the head path is γ\gamma itself and the appended trajectory has duration zero. Associativity. For Γ∈T3(M)\Gamma\in\mathcal{T}^{3}(M), both paths around the left square in (7) produce the same three segments in the same order. These are the heads of the heads of Γ\Gamma, the head path of Γ(R)\Gamma(R), and the last inner trajectory of Γ(R)\Gamma(R). Moore concatenation is strictly associative, so the two results agree as functions. Naturality. The map T(q)\mathcal{T}(q) acts pointwise on paths, preserves durations, and commutes with head. It therefore commutes with η\eta and μ\mu, which is exactly (6). □

The Kleisli Category as Controller Language

We now use the Kleisli category of (T,η,μ)(\mathcal{T},\eta,\mu) to model controllers as morphisms and sequential execution as their composition. This gives the language in which §V states and proves compositional safety.

Apply Definition 2.5 to the trajectory monad (T,η,μ)(\mathcal{T},\eta,\mu), with M,N,ZM,N,Z in the role of the generic objects X,Y,ZX,Y,Z. A Kleisli morphism φ:M→T(N)\varphi:M\to\mathcal{T}(N) assigns to each initial state one admissible Moore trajectory. We call a Kleisli morphism φ:M→T(M)\varphi:M\to\mathcal{T}(M) a controller when it is rooted, i.e., head⁡(φ(x))=x\operatorname{head}(\varphi(x))=x, so that its trajectory starts where it is invoked. Every closed-loop system generates a rooted morphism, and the unit ηM\eta_M is rooted. For controllers φ\varphi and χ\chi, Definition 3.3 gives

(χ∘Kφ)(x)=φ(x)⋅χ(end⁡(φ(x))).(\chi\mathbin{\circ_K}\varphi)(x)=\varphi(x)\mathbin{\cdot}\chi(\operatorname{end}(\varphi(x))).

Indeed, since χ\chi is rooted, the head path of T(χ)(φ(x))\mathcal{T}(\chi)(\varphi(x)) is φ(x)\varphi(x) itself, and the appended trajectory is χ\chi run from the endpoint. Kleisli composition is therefore sequential execution. We run φ\varphi, then run χ\chi from where $\varphi stopped. The composite is again rooted, and by Theorem 3.4, ∘K\circ_K is associative on the nose.

Diagram (8) shows Kleisli composition in Kl⁡(T)\operatorname{Kl}(\mathcal{T}).

M→φT(N)→T(χ)T2(Z)→χ∘KφT(Z)(8)\begin{aligned} M &\xrightarrow{\varphi} \mathcal{T}(N) \xrightarrow{\mathcal{T}(\chi)} \mathcal{T}^{2}(Z) \\ &\xrightarrow{\chi\circ_K\varphi} \mathcal{T}(Z) \tag*{(8)} \end{aligned}

Remark 4.1 (Prior uses of Kleisli composition for systems): Kleisli categories for dynamical systems appear in [14] and in Section 2.3 of [11]. What is new here is that the morphisms carry CBF safety certificates. A morphism φ:M→TE(N)\varphi: M \to\mathcal{T}_{\mathcal{E}}(N), with TE\mathcal{T}_{\mathcal{E}} the CBF sub-monad of §V, is a controller with a proven invariance guarantee. The sub-monad structure of §V is what makes these certificates composable.

CBF Sub-Monads and Compositional Safety

Kleisli composition models sequential execution, but it does not by itself preserve safety certificates. We now identify which Kleisli morphisms carry a safety guarantee. We then ask when composing two such morphisms preserves it.

Lifting CBF Certificates to Sub-Monads

Let h:M→Rh : M \to\mathbb{R} be a CBF with safe set E={x:h(x)≥0}\mathcal{E} = \{x : h(x) \ge0\} as in §II-B.

Definition 5.1 (CBF sub-monad): The CBF sub-monad associated to hh is

TE(M)={(γ,r)∈T(M)∣h(γ(t))≥0, ∀t∈[0,r]}.\mathcal{T}_{\mathcal{E}}(M)=\{(\gamma,r)\in\mathcal{T}(M)\mid h(\gamma(t))\ge0,\ \forall t\in[0,r]\}.

It collects the admissible Moore trajectories that never leave E\mathcal{E}. Its unit is ηM\eta_M restricted to E\mathcal{E}.

Proposition 5.2 (Sub-monad closure): The unit and multiplication of T\mathcal{T} preserve TE\mathcal{T}_{\mathcal{E}}. That is, ηM(E)⊆TE(M)\eta_M(\mathcal{E}) \subseteq\mathcal{T}_{\mathcal{E}}(M), and μM\mu_M maps TE2(M)\mathcal{T}_{\mathcal{E}}^2(M) into TE(M)\mathcal{T}_{\mathcal{E}}(M). Hence TE\mathcal{T}_{\mathcal{E}} is a sub-monad of T\mathcal{T}, and the inclusion ι:TE↪T\iota: \mathcal{T}_{\mathcal{E}} \hookrightarrow\mathcal{T} is a monad morphism. Diagram (9) expresses the compatibility with multiplication.

TE2(M)→μMETE(M)ι∘T(ι)↓↓ιT2(M)→μMT(M)(9)\begin{CD} \mathcal{T}_{\mathcal{E}}^{2}(M) @>{\mu_M^{\mathcal{E}}}>> \mathcal{T}_{\mathcal{E}}(M) \\ @V{\iota\circ\mathcal{T}(\iota)}VV @VV{\iota}V \\ \mathcal{T}^{2}(M) @>{\mu_M}>> \mathcal{T}(M) \tag*{(9)} \end{CD}

Proof: For x0∈Ex_0 \in\mathcal{E}, the unit ηM(x0)=(const⁡x0,0)\eta_M(x_0) = (\operatorname{const}_{x_0},0) never leaves E\mathcal{E}. Now let Γ∈TE2(M)\Gamma\in\mathcal{T}_{\mathcal{E}}^2(M). Each Γ(θ)\Gamma(\theta) lies in TE(M)\mathcal{T}_{\mathcal{E}}(M), so its head lies in E\mathcal{E} and the head path never leaves E\mathcal{E}. The appended trajectory Γ(R)\Gamma(R) also stays in E\mathcal{E}. By the piecewise definition of concatenation, μM(Γ)\mu_M(\Gamma) stays in E\mathcal{E} throughout. Diagram (9) commutes by construction. □

Closure uses only the definition of TE\mathcal{T}_{\mathcal{E}}, not the CBF property. The CBF property enters in Theorem 5.4. There it guarantees that the CBF-QP controller (3) generates a trajectory in TE(M)\mathcal{T}_{\mathcal{E}}(M) from every x0∈Ex_0 \in\mathcal{E}. This is the viability of E\mathcal{E} under (2) in the sense of [25].

Failure of Naive Composition

Proposition 5.3 (Naive composition fails): Let φ:M→TE1(M)\varphi: M \to\mathcal{T}_{\mathcal{E}_1}(M) and χ:M→TE2(M)\chi: M \to\mathcal{T}_{\mathcal{E}_2}(M) be controllers certified for different safe sets E1≠E2\mathcal{E}_1 \ne\mathcal{E}_2. The Kleisli composite (χ∘Kφ)(x)(\chi\circ_K\varphi)(x) need not lie in TE1∩E2(M)\mathcal{T}_{\mathcal{E}_1\cap\mathcal{E}_2}(M). Diagram (10) shows why. The two controllers reach T(M)\mathcal{T}(M) through two different inclusions, and no common sub-monad need contain the image.

M→φTE1χ↓↓ι1TE2→ι2T(M)(10)\begin{CD} M @>{\varphi}>> \mathcal{T}_{\mathcal{E}_1} \\ @V{\chi}VV @VV{\iota_1}V \\ \mathcal{T}_{\mathcal{E}_2} @>{\iota_2}>> \mathcal{T}(M) \tag*{(10)} \end{CD}

Proof: Take M=RM=\mathbb{R} with x˙=u\dot{x}=u and U=[−1,1]\mathcal{U}=[-1,1]. Let h1(x)=xh_1(x)=x and h2(x)=1−xh_2(x)=1-x. Let φ\varphi be the CBF-QP (3) for h1h_1 with unom≡1u_{\mathrm{nom}}\equiv1 and duration 2. From x0=0.5∈E1∩E2x_0=0.5\in\mathcal{E}_1\cap\mathcal{E}_2, the constraint u≥−αxu\ge-\alpha x never binds. The trajectory φ(x0)\varphi(x_0) therefore reaches x=2.5∉E2x=2.5\notin\mathcal{E}_2 while remaining in E1\mathcal{E}_1. Any composite χ∘Kφ\chi\circ_K\varphi contains this segment and leaves E1∩E2\mathcal{E}_1\cap\mathcal{E}_2. □

Compositional Safety via a Shared Sub-Monad

Proposition 5.3 is avoided if all phase controllers map into the same sub-monad. We achieve this with a smooth intersection of the individual CBFs, a known construction [3, 16, 17]. We add an explicit margin to it.

Let h1,…,hkh_1,\ldots,h_k be CBFs with safe sets E1,…,Ek⊂M\mathcal{E}_1,\ldots,\mathcal{E}_k\subset M. For a smoothing parameter ε>0\varepsilon>0, the smooth minimum (softmin) of the barriers is h∩(x):=−εlog⁡∑i=1ke−hi(x)/εh_{\cap}(x):=-\varepsilon\log\sum_{i=1}^{k}e^{-h_i(x)/\varepsilon}. The shifted intersection CBF is h~∩(x)=h∩(x)−δ\widetilde{h}_{\cap}(x)=h_{\cap}(x)-\delta, with margin δ:=εln⁡k\delta:=\varepsilon\ln k.

Remark 5.1 (The margin and its role): The classical log-sum-exp bound [17] gives min⁡ihi(x)−εln⁡k≤h∩(x)≤min⁡ihi(x)\min_i h_i(x)-\varepsilon\ln k\le h_{\cap}(x)\le\min_i h_i(x). The upper bound yields {h∩≥0}⊆E1∩⋯∩Ek\{h_{\cap}\ge0\}\subseteq\mathcal{E}_1\cap\cdots\cap\mathcal{E}_k. In continuous time, every controller certified by h∩h_{\cap} thus lands in a sub-monad of ⋂iTEi\bigcap_i\mathcal{T}_{\mathcal{E}_i}. The margin strengthens this to min⁡ihi(x)≥δ\min_i h_i(x)\ge\delta on {h~∩≥0}\{\widetilde{h}_{\cap}\ge0\}. By the lower bound, min⁡ihi(x)≤2εln⁡k\min_i h_i(x)\le2\varepsilon\ln k on the boundary {h∩=0}\{h_{\cap}=0\}, so the choice δ=εln⁡k\delta=\varepsilon\ln k at most doubles the inherent softmin gap. The margin matters in implementation. Our controllers are sampled-data with zero-order hold, and the continuous-time CBF guarantee does not transfer exactly to this setting [26]. The margin δ\delta absorbs this inter-sample drift at our step sizes. Deriving δ\delta from a sampled-data bound as in [26] would make this rigorous.

Theorem 5.4 (Compositional safety): Let φ1,…,φn:M→T(M)\varphi_1,\ldots,\varphi_n : M\to\mathcal{T}(M) be CBF-QP controllers (3) designed with the shifted intersection CBF h~∩\widetilde{h}_{\cap}. Their nominal controllers may differ. Assume h~∩\widetilde{h}_{\cap} is a CBF for (1) (Definition 2.1). Then every x0x_0 with h~∩(x0)≥0\widetilde{h}_{\cap}(x_0)\ge0 satisfies

(φn∘K⋯∘Kφ1)(x0)∈TE1∩⋯∩Ek(M).(\varphi_n\circ_K\cdots\circ_K\varphi_1)(x_0)\in\mathcal{T}_{\mathcal{E}_1\cap\cdots\cap\mathcal{E}_k}(M).

Diagram (11) shows the composition chain.

M→φ1T{h~∩≥0}→φ2∘K⋯→φn∘KT{h~∩≥0}→ιT⋂iCi(11)M \xrightarrow{\varphi_1} \mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}} \xrightarrow{\varphi_2\circ K} \cdots\xrightarrow{\varphi_n\circ K} \mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}} \xrightarrow{\iota} \mathcal{T}_{\bigcap_i \mathcal{C}_i} \tag*{(11)}

Proof. Since h~∩\tilde{h}_{\cap} is a CBF, each φj\varphi_j keeps trajectories inside {h~∩≥0}\{\tilde{h}_{\cap} \geq0\} when started there [20]. Each such trajectory is an element of T{h~∩≥0}(M)\mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}}(M). Every handoff state is the endpoint of such a trajectory, so it also lies in {h~∩≥0}\{\tilde{h}_{\cap} \geq0\}. Each phase therefore starts where its certificate applies. By Proposition 5.2, T{h~∩≥0}\mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}} is closed under μM\mu_M. The Kleisli composite thus lands in T{h~∩≥0}(M)\mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}}(M), as in diagram (11). Finally, Remark 5.1 gives {h~∩≥0}⊆⋂iCi\{\tilde{h}_{\cap} \geq0\} \subseteq\bigcap_i \mathcal{C}_i, and the inclusion T{h~∩≥0}↪T⋂iCi\mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}} \hookrightarrow\mathcal{T}_{\bigcap_i \mathcal{C}_i} completes the proof. □

■

Theorem 5.4 gives a sufficient condition. Controllers in different sub-monads may still compose safely from particular initial states, as the nonzero Naive safety rates in §VI show. The hypothesis that h~∩\tilde{h}_{\cap} is a CBF is not automatic under input bounds [5], [17]. We monitor it empirically through QP feasibility.

Remark 5.2 (Automatic activation): At state xx, the CBF-QP constraint imposed by h~∩\tilde{h}_{\cap} is ∑i=1kwi(x)∇hi(x)T(f(x)+B(x)u)≥−αh~∩(x)\sum_{i=1}^{k} w_i(x)\nabla h_i(x)^\mathsf{T}(f(x)+B(x)u) \geq-\alpha\tilde{h}_{\cap}(x). The softmin weights are wi(x)=e−hi(x)/ε∑je−hj(x)/εw_i(x) = \frac{e^{-h_i(x)/\varepsilon}}{\sum_j e^{-h_j(x)/\varepsilon}}. Let i∗(x)∈arg⁡min⁡ihi(x)i^*(x) \in\arg\min_i h_i(x) index the most binding barrier at xx. When hj(x)≫0h_j(x) \gg0 for all j≠i∗j \ne i^*, the weight wi∗(x)w_{i^*}(x) approaches 11. The constraint then concentrates on the most binding barrier without any scheduling logic. This lazy activation, observed in [3], [17], is a property of the softmin gradient. The sub-monad view adds that it needs no coordination across phases, since every phase controller enforces the same constraint.

Statistical Validation

We compare three strategies. Naive has phase jj enforce only hσ(j)h_{\sigma(j)}, with σ(j):=((j−1) mod k)+1\sigma(j) := ((j-1)\bmod k)+1, so successive controllers land in different sub-monads (Proposition 5.3). Global enforces all kk barriers as hard constraints in one QP [5], [20] and lands in T⋂iCi\mathcal{T}_{\bigcap_i \mathcal{C}_i} whenever that QP is feasible. Monadic enforces the single constraint h~∩≥0\tilde{h}_{\cap} \geq0 and lands in T{h~∩≥0}\mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}} (Theorem 5.4). Inputs are two-dimensional, so we solve each QP exactly by enumerating its candidate minimizers. If none is feasible, the saturated nominal input is applied, which is what exposes Global to violations. Proposition 5.3 shows that Naive composition can fail, and Theorem 5.4 shows that Monadic composition cannot. Neither result says how often Naive fails. We now quantify this failure probability (§VI-A) and validate all three strategies over a randomized sweep (§VI-B).

Bernoulli Failure Model

Under Naive, phase jj enforces only hσ(j)h_{\sigma(j)}. By forward invariance, the trajectory stays in Cσ(j)\mathcal{C}_{\sigma(j)} throughout phase jj. Nothing constrains the other k−1k-1 barriers. At time τj\tau_j, the handoff passes a state certified only for Cσ(j)\mathcal{C}_{\sigma(j)} to a controller certified only for Cσ(j+1)\mathcal{C}_{\sigma(j+1)}. Proposition 5.3 identifies these handoffs as the source of the sub-monad mismatch. This motivates modeling each handoff as a separate trial.

Lemma 6.1 (Bernoulli failure model): For j=1,…,n−1j=1,\ldots,n-1, let EjE_j be the event that the Naive trajectory leaves ⋂iCi\bigcap_i \mathcal{C}_i during phase j+1j+1, i.e., after handoff jj. Assume that phase 1, which starts from x0∈⋂iCix_0 \in\bigcap_i \mathcal{C}_i, is jointly safe. The Naive trajectory is then jointly safe iff ⋂j=1n−1Ejc\bigcap_{j=1}^{n-1} E_j^c occurs. Suppose E1,…,En−1E_1,\ldots,E_{n-1} are mutually independent with common probability p0=P(Ej)∈[0,1)p_0=P(E_j)\in[0,1). Then

PsafeNaive(n)=(1−p0)n−1.(12)P_{\mathrm{safe}}^{\mathrm{Naive}}(n)=(1-p_0)^{n-1}. \tag*{(12)}

This has two consequences. 1) If p0>0p_0>0, then PsafeNaive(n)→0P_{\mathrm{safe}}^{\mathrm{Naive}}(n)\to0 geometrically in nn. 2) The index of the first failing handoff has mean 1/p01/p_0. The expected number of safe handoffs before the first failure is therefore (1−p0)/p0(1-p_0)/p_0.

Proof: By independence, P(⋂j=1n−1Ejc)=∏j=1n−1(1−p0)=(1−p0)n−1P(\bigcap_{j=1}^{n-1}E_j^c)=\prod_{j=1}^{n-1}(1-p_0)=(1-p_0)^{n-1}. This gives (12) and claim 1. The index of the first failing handoff is geometric with success probability p0p_0, so its mean is 1/p01/p_0. Excluding the failing handoff itself gives claim 2. □

■

Remark 6.1 (Geometric interpretation of p0p_0): Independence and a common p0p_0 are modeling assumptions that we impose and then test empirically. They are plausible when each phase nearly converges to its CLF target before the handoff, which decorrelates successive handoff states. They are also plausible when barriers are drawn i.i.d., as in the sweep below. We test them empirically in §VI-B, where any residual phase-1 failures are absorbed into the fitted p0p_0. Suppose further that the handoff state is roughly uniform on Cσ(j)\mathcal{C}_{\sigma(j)}. A first-order estimate is then p0≈1−Vol⁡(⋂iCi)/Vol⁡(Cσ(j))p_0 \approx1-\operatorname{Vol}(\bigcap_i \mathcal{C}_i)/\operatorname{Vol}(\mathcal{C}_{\sigma(j)}). This is the fraction of the active safe set that lies outside the joint safe set. Adding a barrier can only shrink ⋂iCi\bigcap_i \mathcal{C}_i, so the estimate is nondecreasing in kk. This agrees with the fits reported below.

Randomized Sweep

Setup. We sweep (n,k)∈{2,…,6}×{2,…,5}(n,k)\in\{2,\ldots,6\}\times\{2,\ldots,5\} with Ns=150N_s=150 instances per cell, 3,000 in total, on the modal ROM of Use Case II. Each instance draws kk random ellipses, corridors, or half-planes, an initial state with h~∩(ζ0)>0.015\tilde{h}_{\cap}(\zeta_0)>0.015, and nn waypoints inside ⋂iCi\bigcap_i \mathcal{C}_i. Phases last 2 s, and the final phase lasts 4 s. We use α=2.0\alpha=2.0, ε=0.05\varepsilon=0.05, and Δt=0.02\Delta t=0.02 s. A run is safe if min⁡ihi≥−10−3\min_i h_i \geq-10^{-3} throughout. We fit p0(k)p_0(k) by nonlinear least squares.

Results. Figure 1 summarizes the sweep. The fitted values p0=0.54,0.70,0.84,0.90p_0=0.54, 0.70, 0.84, 0.90 for k=2,…,5k=2,\ldots,5 increase monotonically with kk (Remark 6.1). Naive drops to single digits by n=6n=6 for every kk. Monadic achieves 100% on every cell, as Theorem 5.4 guarantees.

Figure 1. Randomized sweep over Ns=150N_s=150 random CBF geometries per cell, with ϵ=0.05\epsilon=0.05 and α=2.0\alpha=2.0. (A) Naive safety rate versus phase count nn for each barrier count kk. Dashed curves show the fitted Bernoulli model Naivesafe(n)=(1−p0)n−1\mathrm{Naive}_{\mathrm{safe}}(n)=(1-p_0)^{n-1}, and shaded regions show p0±2p_0 \pm2 standard errors. The fitted p0p_0 increases monotonically with kk (Remark 6.1). (B)–(D) Safety rate over the full (n,k)(n,k) grid for Naive, Global, and Monadic. Naive collapses exponentially with nn. Global degrades under constraint conflict as kk grows, despite being the exact simultaneous-QP baseline. Monadic achieves 100% on all 20 cells, as Theorem 5.4 guarantees.

Panel (C) shows a failure mode that our framework does not capture. Global degrades as kk and nn grow, reaching 58% at k=5k=5, n=6n=6. When the kk constraint normals conflict in the two-dimensional input space, the QP becomes infeasible and Global falls back to the nominal input. This does not contradict Theorem 5.4. Sub-monad membership presupposes that a certified controller exists, and Global lands in T⋂iCi\mathcal{T}_{\bigcap_i \mathcal{C}_i} only while its QP is feasible. Input-constrained compatibility conditions [5], [6] address exactly this existence question. Softmin composition does not guarantee Monadic feasibility in general [17], yet Monadic remained safe in all 3,000 instances. Building feasibility into the sub-monad condition itself is an open question.

Use Cases

We have established the categorical account and quantified how reliably it avoids the failure mode of naive composition. We now demonstrate the three strategies of §VI on two concrete robotic systems.

Both use cases compare three composition strategies. Naive has each phase controller fif_i enforce only the single barrier hih_i, placing controllers in different sub-monads (Proposition 5.3). Global [1] enforces all kk barriers as separate hard QP constraints at every step, giving a shared sub-monad ⋂iCi\bigcap_i \mathcal{C}_i at the cost of kk constraints per step. Monadic uses a single h~∩\tilde{h}_{\cap} constraint, giving the shared sub-monad T{h~∩≥0}⊆T⋂iCi\mathcal{T}_{\{\tilde{h}_{\cap}\geq0\}} \subseteq\mathcal{T}_{\bigcap_i \mathcal{C}_i} of Theorem 5.4 with one constraint per step. All CBF-QPs are solved with Gurobi at 50 Hz.

Use Case I: Four-Mode PWA System

Setup. We use three safe sets, the ellipse h1=1−x12/0.922−x22/0.782h_1=1-x_1^2/0.92^2-x_2^2/0.78^2, the corridor h2=0.722−x12h_2=0.72^2-x_1^2, and the half-plane h3=x2+0.36h_3=x_2+0.36. Four phases of (3.0,2.0,2.5,8.0) s(3.0,2.0,2.5,8.0)\,\mathrm{s} take the state from x0=(−0.50,0.55)Tx_0=(-0.50,0.55)^\mathsf{T} in mode 2 to the goal (0.35,−0.20)T(0.35,-0.20)^\mathsf{T} in mode 4 under a saturated proportional nominal law. We use ϵ=0.04\epsilon=0.04, α=1.5\alpha=1.5, forward Euler with Δt=0.015 s\Delta t=0.015\,\mathrm{s}, and Ns=50N_s=50 runs with initial states perturbed by U([−0.06,0.06]2)\mathcal{U}([-0.06,0.06]^2).

Failure mechanism. The phase-1 target (−0.65,0.25)T(-0.65,0.25)^\mathsf{T} lies near the left corridor wall, where the mode-2 drift points left. Naive enforces only h1h_1 in phase 1, so the drift carries x1x_1 past −0.72-0.72 before the first handoff. A controller in TC1\mathcal{T}_{\mathcal{C}_1} thus need not lie in TC1∩C2\mathcal{T}_{\mathcal{C}_1\cap\mathcal{C}_2}.

Results. Naive violates safety in 78% of runs. Monadic matches the 100% safety of Global with one constraint per step instead of three. It also keeps a larger margin, min⁡h1=+0.09\min h_1=+0.09 versus +0.04+0.04, consistent with δ=ϵln⁡3=0.044\delta=\epsilon\ln3=0.044. Figure 2 shows a representative rollout.

Figure 2. Four-mode PWA system, one representative rollout. Naive (red) exits C1∩C2∩C3\mathcal{C}_1 \cap\mathcal{C}_2 \cap\mathcal{C}_3 near the mode-2/mode-3 transition. Global (green) and Monadic (blue) remain safe throughout. Line style shows the plant mode ℓ(x)\ell(x), which switches as the trajectory crosses quadrants. Distances are for this single rollout, not the Ns=50N_s=50 Monte Carlo averages.

Use Case II: Unicycle ROM on Heterogeneous Terrain

Setup. The ROM of Use Case II crosses a Rocky Terrain Traverse in four phases of (2.0,2.5,2.5,5.0) s(2.0,2.5,2.5,5.0)\,\mathrm{s}. It must respect the ellipsoidal margin h1=1−px2/1.202−py2/0.882h_1=1-p_x^2/1.20^2-p_y^2/0.88^2, the stepping-stone corridor h2=0.552−px2h_2=0.55^2-p_x^2, and the cliff h3=py+0.28h_3=p_y+0.28. A proportional nominal controller drives to phase targets inside ⋂iCi\bigcap_i\mathcal{C}_i, at constant speed in phases 1 to 3. We use ϵ=0.05\epsilon=0.05, α=2.0\alpha=2.0, Δt=0.02 s\Delta t=0.02\,\mathrm{s}, and Ns=50N_s=50 runs.

Failure mechanism. The heading ψ\psi carries across each handoff. Naive enforces h1h_1, h2h_2, h3h_3, and h1h_1 in turn, so nothing constrains the cliff in phases 2 and 4. Near τ2\tau_2 and τ3\tau_3, the inherited heading carries the robot across h3=0h_3=0 (Figure 3). The composite lands in T(M)\mathcal{T}(\mathcal{M}) but not in T⋂iCi\mathcal{T}_{\bigcap_i\mathcal{C}_i}.

Figure 3. Rocky Terrain Traverse, one representative rollout. Naive (red) loops through mode ℓ=3\ell=3 near the handoffs τ2\tau_2 and τ3\tau_3 and crosses the cliff boundary h3=0h_3=0. Global (green) and Monadic (blue) remain within C1∩C2∩C3C_1 \cap C_2 \cap C_3 and reach the goal. Distances are for this single rollout, not the Ns=50N_s=50 Monte Carlo averages.

Results. Naive is never safe, with min⁡h3=−0.343\min h_3=-0.343. Monadic matches the 100% safety of Global with one constraint per step. Its margins, min⁡h2=+0.077\min h_2=+0.077 and min⁡h3=+0.070\min h_3=+0.070, exceed δ=ϵln⁡3=0.055\delta=\epsilon\ln3=0.055. Global’s margins are only +0.002+0.002 and +0.001+0.001.

Results. Naive achieves 0% safety, with min⁡h3=−0.343\min h_3=-0.343. This is a structural, not marginal, violation, confirming Proposition 5.3. Monadic matches Global safety at 100% with one QP constraint per step. The Monadic minimum margins, min⁡h2=+0.077\min h_2=+0.077 and min⁡h3=+0.070\min h_3=+0.070, are both tightly consistent with the theoretical lower bound 2ϵln⁡2=0.0692\epsilon\ln2=0.069. This validates that the controller is conservative by exactly the shift of Remark 5.1, no more and no less. Global, by contrast, attains margins only marginally above zero, +0.002+0.002 and +0.001+0.001. Monadic therefore achieves the same safety guarantee with quantified, structural conservatism rather than incidental margin.

Conclusion

We constructed the trajectory monad (T,η,μ)(\mathcal{T}, \eta, \mu) for Filippov-regular differential inclusions. We showed that CBF certificates lift to sub-monads, so controllers that land in a common sub-monad compose safely. Naive phase-by-phase composition fails because successive controllers land in different sub-monads. This mismatch is localized at each Kleisli handoff. It motivates a closed-form Bernoulli failure model, which we validated over 3,000 randomized instances. A smooth intersection CBF with an explicit margin places all phase controllers in one shared sub-monad, with one QP constraint per step. It achieved 100% safety in the sweep and on both use cases. The standard simultaneous-constraint baseline, in contrast, degraded under constraint conflict as the barrier count grew. Future work includes incorporating QP feasibility into the sub-monad condition, a sampled-data derivation of the margin, and Eilenberg–Moore algebras of T\mathcal{T}, which we conjecture to be Lyapunov certificates. We also plan hardware validation on a Unitree Go2 quadruped.

References

  1. [1]P. Glotfelter, J. Cortés, and M. Egerstedt, “Nonsmooth barrier functions with applications to multi-robot systems,” IEEE Control Systems Letters, vol. 1, no. 2, pp. 310–315, 2017.
  2. [2]P. Glotfelter, I. Buckley, and M. Egerstedt, “Hybrid nonsmooth barrier functions with applications to provably safe and composable collision avoidance,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1303–1310, 2019.DOI
  3. [3]T. G. Molnár and A. D. Ames, “Composing control barrier functions for complex safety specifications,” IEEE Control Systems Letters, vol. 7, pp. 3615–3620, 2023, arXiv:2309.06647.arxiv.org/abs/2309.06647
  4. [4]P. Ong, H. Lee, T. G. Molnar, D. Panagou, and A. D. Ames, “Combinatorial control barrier functions: Nested boolean and p-choose-r compositions of safety constraints,” arXiv preprint arXiv:2509.10716, 2025.DOI
  5. [5]J. Breeden and D. Panagou, “Compositions of multiple control barrier functions under input constraints,” in American Control Conference (ACC), 2023, pp. 3688–3695.arxiv.org/abs/2210.01354
  6. [6]X. Tan and D. V. Dimarogonas, “Compatibility checking of multiple control barrier functions for input constrained systems,” in IEEE Conference on Decision and Control (CDC), 2022, pp. 939–944.arxiv.org/abs/2209.02284
  7. [7]R. R. Burridge, A. A. Rizzi, and D. E. Koditschek, “Sequential composition of dynamically dexterous robot behaviors,” The International Journal of Robotics Research, vol. 18, no. 6, pp. 534–555, 1999.DOI
  8. [8]A. Majumdar and R. Tedrake, “Funnel libraries for real-time robust feedback motion planning,” The International Journal of Robotics Research, vol. 36, no. 8, pp. 947–982, 2017.arxiv.org/abs/1601.04037
  9. [9]A. Saoud, A. Girard, and L. Fribourg, “Assume-guarantee contracts for continuous-time systems,” Automatica, vol. 134, p. 109910, 2021.DOI
  10. [10]J. Moeller and A. D. Ames, “Hybrid systems as coalgebras: Lyapunov morphisms for Zeno stability,” arXiv preprint, vol. arXiv:2604.05255, 2026.arxiv.org/abs/2604.05255
  11. [11]D. J. Myers, Categorical Systems Theory. Topos Institute, 2022, book draft, https://topos.site.
  12. [12]S. Goncharov, R. Jakob, and R. Neves, “A semantics for hybrid iteration,” in 29th International Conference on Concurrency Theory (CONCUR), ser. LIPIcs, vol. 118, 2018, pp. 22:1–22:17, arXiv:1807.01053.DOI
  13. [13]S. Goncharov and R. Neves, “An adequate while-language for hybrid computation,” in 21st International Symposium on Principles and Practice of Declarative Programming (PPDP), 2019, arXiv:1902.07684.arxiv.org/abs/1902.07684
  14. [14]B. Jacobs, “Coalgebraic specifications and models of deterministic hybrid systems,” in Eighth International Conference on Algebraic Methodology and Software Technology (AMAST), ser. LNCS, vol. 1101, 1996, pp. 237–251.DOI
  15. [15]P. Schultz, D. I. Spivak, and C. Vasilakopoulou, “Dynamical systems and sheaves,” Applied Categorical Structures, vol. 28, pp. 1–57, 2020.arxiv.org/abs/1609.08086
  16. [16]L. Lindemann and D. V. Dimarogonas, “Controller barrier functions for signal temporal logic tasks,” IEEE Control Systems Letters, vol. 3, no. 1, pp. 96–101, 2019.DOI
  17. [17]P. Rabiee and J. B. Hoagg, “Soft-minimum barrier functions for safety-critical control subject to actuation constraints,” arXiv preprint, vol. arXiv:2304.00693, 2023.DOI
  18. [18]A. F. Filippov, Differential Equations with Discontinuous Righthand Sides. Springer, 1988.
  19. [19]J. Cortés, “Discontinuous dynamical systems: A tutorial on solutions, nonsmooth analysis, and stability,” IEEE Control Systems Magazine, vol. 28, no. 3, pp. 36–73, 2008.DOI
  20. [20]A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada, “Control barrier functions: Theory and applications,” in European Control Conference (ECC), 2019, pp. 3420–3431.arxiv.org/abs/1903.11199
  21. [21]P. Iglesias-Zemmour, Diffeology. American Mathematical Society, 2013, vol. 185.
  22. [22]C. Belta, B. Yordanov, and E. Aydin Gol, Formal Methods for Discrete-Time Dynamical Systems. Springer, 2017.
  23. [23]M. H. Cohen, T. G. Molnár, and A. D. Ames, “Safety-critical control for autonomous systems: Control barrier functions via reduced-order models,” Annual Reviews in Control, vol. 57, p. 100947, 2024.DOI
  24. [24]P. Tabuada, Verification and Control of Hybrid Systems: A Symbolic Approach. Springer, 2009.DOI
  25. [25]J.-P. Aubin, Viability Theory. Boston: Birkhäuser, 1991.
  26. [26]J. Breeden, K. Garg, and D. Panagou, “Control barrier functions in sampled-data systems,” IEEE Control Systems Letters, vol. 6, pp. 367–372, 2022.DOI

Paper details

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

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents