Safe Pontryagin Differentiable Programming
Year: 2021

Abstract:
We propose a Safe Pontryagin Differentiable Programming (Safe PDP) methodology, which establishes a theoretical and algorithmic framework to solve a broad class of safety-critical learning and control tasks—problems that require the guarantee of safety constraint satisfaction at any stage of the learning and control progress. In the spirit of interior-point methods, Safe PDP handles different types of system constraints on states and inputs by incorporating them into the cost or loss through barrier functions. We prove three fundamentals of the proposed Safe PDP: first, both the solution and its gradient in the backward pass can be approximated by solving their more efficient unconstrained counterparts; second, the approximation for both the solution and its gradient can be controlled for arbitrary accuracy by a barrier parameter; and third, importantly, all intermediate results throughout the approximation and optimization strictly respect the constraints, thus guaranteeing safety throughout the entire learning and control process. We demonstrate the capabilities of Safe PDP in solving various safety-critical tasks, including safe policy optimization, safe motion planning, and learning MPCs from demonstrations, on different challenging systems such as 6-DoF maneuvering quadrotor and 6-DoF rocket powered landing.

heading: 1 Introduction
text: Safety is usually a priority in the deployment of a learning or control algorithm to real-world systems. For a physical system (agent), safety is normally given in various constraints on system states and inputs, which must not be violated by the algorithm at any stage of the learning and control process, otherwise will cause irrevocable or unacceptable failure/damage. Those systems are referred to as safety-critical. The constraints in a safety-critical system can include the immediate ones, which are directly imposed on the system state and input at certain or all-time instances, and the long-term ones, which are defined on the trajectory of system states and inputs over a long period.
Compared to the abundant results that focus on system optimality [1–3], systematic and principled treatments for safety-critical learning and control problems seem largely insufficient, particularly in the following gaps (detailed in Section 1.1). First, existing safety strategies are either too conservative, which may restrict the task performance, or violation-tolerable, which only pursues the near-constraint guarantee and thus are not strictly constraint-respecting. Second, a systematic safety paradigm capable of handling different types of constraints, including system state and input (or mixed), immediate, or/and long-term constraints, is still lacked. Third, some existing safety strategies suffer from huge computational- and data- complexity, difficult to be integrated into any differentiable programming frameworks to solve large-scale learning and continuous control tasks.
To address the above research gaps, this paper aims to develop a safe differentiable programming framework with the following key capabilities. First, the framework provides a systematic treatment for different types of constraints in a safety-critical problem; second, it attains provable safety- and accuracy- guarantees throughout the learning and control process; third, it is flexible to perform safe learning of any unknown aspects of a constrained decision-making system, including policy, dynamics, state and input constraints, and control cost; finally, it can be integrated to any differentiable programming framework to efficiently solve large-scale safe learning and control tasks.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1.1 Related Work
text: In machine learning and control fields, safety has been defined by different criteria, such as worstcase [4, 5], risk-sensitive [6], ergodicity [7], robust [8, 9], etc., most of which are formulated by directly altering an objective function [10]. In this paper, we focus only on constrained learning and control problems, where constraints are explicitly formulated and must be satisfied. We categorize existing techniques into at-convergence safety methods, which only concern constraint satisfaction at convergence, or in-progress safety methods, which attempt to ensure constraint satisfaction during the entire optimization process.
At-convergence safety methods. In reinforcement learning (RL), a constrained agent is typically formulated as a Constrained Markov Decision Process (CMDP) [11], seeking a policy that not only optimizes a reward but also satisfies an upper bound for a cumulative cost. A common strategy [12– 17] to solve CMDPs is to use the primal-dual method, by establishing the unconstrained Lagrangian and performing saddle-point optimization. In deep learning, the primal-dual method has been recently used [18] to train deep neural networks with constraints. In control, the primal-dual method has been used to solve constrained optimal control (constrained trajectory) problems [19–21]. While proved to satisfy constraints at convergence [22, 23], the primal-dual type methods cannot guarantee constraint satisfaction during optimization, as shown in [13, 24], thus are not suitable for safety-critical tasks.
In-progress safety methods. To enforce safety during training, [25] and [26] solve CMDPs by introducing additional constraints into the Trust Region Policy Optimization (TRPO) [27]. Since these methods only obtain the ‘near constraint’ guarantee, constraint violation is not fully eliminated. Another line of constrained RL [24, 28–30] leverages the Lyapunov theory [31] to bound behavior of an agent. But how to choose a valid Lyapunov function for general tasks is still an open problem to date [32], particularly for constrained RL, since it requires a Lyapunov function to be consistent with the constraints and to permit optimal policies [28]. Some other work also attempts to handle immediate constraints — the constraints imposed on agent state and input at any time. In [33], a safe exploration scheme is proposed to produce a safe reachable region; and it only considers finite state space. [34] develops a method that learns safety constraints and then optimizes a reward within the certified safe region; the method defines constraints purely on agent state and thus may not be readily applicable to mixed state-input constraints.
In control, in-progress safety can be achieved via two model-based frameworks: reachability theory [35] and control barrier functions [36, 37]. Safe control based on reachability theory [35, 38–40] explicitly considers adversarial factors and seeks a strategy that maintains the constraints despite the adversarial factors. This process typically requires solving the Hamilton-Jacobi-Isaacs equations [41], which become computationally difficult for high-dimensional systems [35]. Control barrier functions [36, 37] constrain a system only on safety boundaries, making it a less-conservative strategy for safety-critical tasks [42–44]. Most of the methods consider affine dynamics and directly use the given constraint function as a control barrier function. Such a choice could be problematic when a system is uncontrollable at the boundary of the sublevel set. Thus, how to find a valid control barrier function is still an ongoing research topic [45–47]. The above two control safety frameworks favorably focus on pure state constraints and cannot be readily extended to other constraints, such as mixed state-input constraints or the cumulative constraints defined on the system trajectory.
Interior-point methods and control. Interior-point methods (IPMs) [48–50] solve constrained optimization by sequentially finding solutions to unconstrained problems with the objective combining the original objective and a barrier that prevents from leaving the feasible regions. IPMs have been used for constrained linear quadratic regular (LQR) control in [51–57]. While IPMs for nonlinear constrained optimal control are studied in [58–62], they mostly focus on developing algorithms to solve the unconstrained approximation (from the perturbed KKT conditions) and lack of performance analysis. Most recently, [63] uses the IPM to develop a zero-th order non-convex optimization method; and [64] uses IPMs to solve reinforcement learning with only cumulative constraints. Despite the promise of the trend, the theoretical results and systematic algorithms regarding the differentiability of general constrained control systems based on IPMs have not been studied and established.
Differentiable projection layer. In machine learning, a recent line of work considers embedding a differentiable projection layer [65–67] into a general training process to ensure safety. Particularly, [67] and [66] enforce safety by constructing a dedicated projection layer, which projects the unsafe actions outputted from a neural policy into a safe region (satisfying safety constraints). This projection layer is a differentiable convex layer [68, 69], which can be trained end-to-end. In [65], safety is
defined as robustness in the case of the worst adversarial disturbance, and the set of robust policies is solved by classic robust control (solving LMIs). An RL neural policy with a differentiable projection layer is learned such that the action from the neural policy lies in the robust policy set. Different from the above work, Safe PDP does not enforce safety by projection; instead, Safe PDP uses barrier functions to guarantee safety constraint satisfaction. More importantly, we have shown, in both theory and experiments, that with barrier functions, differentiability can also be attained.
Sensitivity analysis and differentiable MPCs. Other work related to Safe PDP includes the recent results for sensitivity analysis [70], which focuses on differentiation of a solution to a general nonlinear program, and differentiable MPCs [68], which is based on differentiable quadratic programming. In long-horizon control settings, directly applying [70] and [68] can be inefficient: the complexity of [68, 70] for differentiating a solution to a general optimal control system is at least O(T 2) (T is the time horizon) due to computing the inverse of Jacobian of the KKT conditions. Since an optimal control system has more sparse structures than general nonlinear or quadratic programs, by exploiting those structures and proposing the Auxiliary Control System, Safe PDP enjoys the complexity of O(T ) for differentiating a solution to a general control system. Such advantages have been discussed and shown in the foundational PDP work [71] and will also be shown later (in Section 8) in this paper.

heading: 1.2 Paper Contributions
text: We propose a safe differentiable programming methodology named as Safe Pontryagin Differentiable Programming (Safe PDP). Safe PDP provides a systematic treatment of different types of system constraints, including state and inputs (or mixed), immediate, and long-term constraints, with provable safety- and performance-guarantee. Safe PDP is also a unified differentiable programming framework, which can be used to efficiently solve a broad class of safety-critical learning and control tasks.
In the spirit of interior-point methods, Safe PDP incorporates different types of system constraints into control cost and loss through barrier functions, approximating a constrained control system and task using their unconstrained counterparts. Contributions of Safe PDP are theoretical and algorithmic. Theoretically, we prove in Theorem 2 and Theorem 3 that (I) not only a solution but also the gradient of the solution can be safely approximated by solving a more efficient unconstrained counterpart; (II) any intermediate results throughout the approximation and optimization are strictly safe, that is, never violating the original system/task constraints; and (III) the approximations for both solution and its gradient can be controlled for arbitrary accuracy by barrier parameters. Arithmetically, (IV) we prove in Theorem 1 that if a constrained control system is differentiable, the gradient of its trajectory is a globally unique solution to an Auxiliary Control System [71], which can be solved efficiently with the complexity of only O(T ), T is control horizon; (V) in Section 7, we experimentally demonstrate the capability of Safe PDP for efficiently solving various safety-critical learning and control problems, including safe neural policy optimization, safe motion planning, learning MPCs from demonstrations.

heading: 2 Safe PDP Problem Formulation
text: Consider a class of constrained optimal control systems (models) Σ(θ), which are parameterized by a tunable parameter θ ∈ Rr in its control cost function, dynamics, initial condition, and constraints:
Σ(θ) :
control cost: J(θ) = ∑T−1
t=0 ct(xt,ut,θ) + cT (xT ,θ)
subject to dynamics: xt+1 = f(xt,ut,θ) with x0 = x0(θ), ∀t,
terminal constraints: gT (xT ,θ) ≤ 0, hT (xT ,θ) = 0, path constraints: gt(xt,ut,θ) ≤ 0, ht(xt,ut,θ) = 0, ∀t.
(1)
Here, xt ∈ Rn is the system state; ut ∈ Rm is the control input; ct : Rn × Rm × Rr → R and cT : Rn × Rr → R are the stage and final costs, respectively; f : Rn × Rm × Rr → Rn is the dynamics with initial state x0 = x0(θ) ∈ Rn; t = 0, 1, ..., T is the time step with T the time horizon; gT : Rn × Rr → RqT and hT : Rn × Rr → RsT are the final inequality and equality constraints, respectively; gt : Rn×Rm×Rr → Rqt and ht : Rn×Rm×Rr → Rst are the immediate inequality and equality constraints at time t, respectively. All inequalities (here and below) are entry-wise. We consider that all functions in Σ(θ) are three-times continuously differentiable (i.e., C3) with respect to its arguments. Although we here have parameterized all aspects of Σ(θ), for a specific application (see Section 7), one only needs to parameterize the unknown aspects in Σ(θ) and keep others given.
Any unknown aspects in Σ(θ) can be implemented by differentiable neural networks. For a given θ, Σ(θ) produces a trajectory ξθ = {xθ0:T ,uθ0:T−1} by solving the following Problem B(θ):
ξθ = {x θ 0:T ,u θ 0:T−1} ∈ arg min{x0:T ,u0:T−1} J(θ)
subject to xt+1 = f(xt,ut,θ) with x0 = x0(θ), ∀t, gT (xT ,θ) ≤ 0 and hT (xT ,θ) = 0, gt(xt,ut,θ) ≤ 0 and ht(xt,ut,θ) = 0, ∀t.
B(θ)
Here, we use ∈ since ξθ to Problem B(θ) may not be unique in general, thus constituting a solution set {ξθ}. We will discuss the existence and uniqueness of {ξθ} in Section 4. For a specific task, we aim to find a specific model Σ(θ∗), i.e, searching for a specific θ∗, such that its trajectory ξθ∗ from B(θ
∗) meets the following two given requirements. First, ξθ∗ minimizes a given task loss `(ξθ,θ); and second, ξθ∗ satisfies the given task constraints Ri(ξθ,θ) ≤ 0, i = 1, 2, ..., l. Note that, we need to distinguish between the two types of objectives: task loss `(ξθ,θ) and control cost J(θ), and also the two types of constraints: task constraints Ri(ξθ,θ) and model constraints gt(θ). In fact, J(θ) and gt(θ) in Σ(θ) are unknown and parameterized by θ and can represent the unknown inherent aspects of a physical agent, while `(ξθ,θ) and Ri(ξθ,θ) are given and known depending on the specific task (they also explicitly depend on θ since θ needs to be regularized in some learning cases). Assume `(ξθ,θ) and Ri(ξθ,θ) are both twice-continuously differentiable. The problem of searching for θ∗ can be formally written as:
θ∗ = arg min θ `(ξθ,θ)
subject to Ri(ξθ,θ) ≤ 0, i = 1, 2, ..., l, ξθ solves Problem B(θ) .
P
For a specific learning and control task, one only needs to specify the details of Σ(θ) and give a task loss `(ξθ,θ) and constraints Ri(ξθ,θ) ≤ 0. Section 7 will give representative examples.

heading: 3 Challenges to Solve Problem P
text: Problem P belongs to bi-level optimization [72]—each time θ is updated in the outer-level (including task loss ` and task constraint Ri) of Problem P, the corresponding trajectory ξθ needs to be solved from the inner-level Problem B(θ). Similar to PDP [71], one could approach Problem P using gradient-based methods by ignoring the process of solving inner-level Problem B(θ) and just viewing ξθ as an explicit differentiable function of θ. Then, based on interior-point methods [48], one can introduce a logarithmic barrier function for each task constraint, − ln ( −Ri ) , and a barrier parameter
> 0. This leads to solving the following unconstrained Problem SP( ) sequentially
θ∗( ) = arg min θ
`(ξθ,θ)− ∑l i=1 ln ( −Ri(ξθ,θ) ) SP( )
for a fixed . By controlling → 0, θ∗( ) is expected to converge to the solution θ∗ to Problem P. Although plausible, the above process has the following technical challenges to be addressed: (1) As ξθ is a solution to the constrained optimal control Problem B(θ), is ξθ differentiable? Does
the auxiliary control system [71] exist for solving ∂ξθ∂θ ?
(2) Since we want to obtain ξθ and ∂ξθ ∂θ at as low cost as possible, instead of solving the constrained
Problem B(θ), can we use an unconstrained system to approximate both ξθ and ∂ξθ ∂θ ? Importantly, can the accuracy of the approximations for ξθ and ∂ξθ ∂θ be arbitrarily and safely controlled? (3) Can we guarantee that the approximation for ξθ is safe in a sense that the approximation always respects the system original inequality constraints gt ≤ 0 and gT ≤ 0?
(4) With the safe approximations for both ξθ and ∂ξθ ∂θ , can accuracy of the solution to the outer-level
unconstrained optimization SP( ) be arbitrarily controlled towards θ∗?
(5) With the safe approximations for both ξθ and ∂ξθ ∂θ , can we guarantee the safety of the outer-level
inequality constraints Ri ≤ 0 during the optimization for the outer-level SP( )?
The following paper will address the above challenges. For reference, we give a quick overview: Challenge (1) will be addressed in Section 4 and the result is in Theorem 1; Challenges (2) and (3) will be addressed in Section 5 and the result is in Theorem 2; Challenges (4) and (5) will be addressed in Section 6 and the result is in Theorem 3; and Section 7 gives some representative applications.

heading: 4 Differentiability for Σ(θ) and its Auxiliary Control System

heading: 4.1 Differentiability of ξθ
text: For the constrained optimal control system Σ(θ) in (1), we define the following Hamiltonian Lt for t = 0, 1, ..., T−1 and LT , respectively,
Lt = ct(xt,ut,θ) + λ ′ t+1f(xt,ut,θ) + v ′ tgt(xt,ut,θ) +w ′ tht(xt,ut,θ), (2a)
LT = cT (xT ,θ) + v ′ TgT (xT ,θ) +w ′ ThT (xT ,θ), (2b)
where λt ∈ Rn is the costate, vt ∈ Rqt and wt ∈ Rst are multipliers for the inequality and equality constraints, respectively. The well-known second-order condition for ξθ to be a local isolated (locally unique) minimizing trajectory to Σ(θ) in Problem B(θ) has been well-established in [73]. For completeness, we present it in Lemma A.2 in Appendix A. Lemma A.2 states that there exist costate sequence λθ1:T , and multiplier sequences v θ 0:T and w θ 0:T , such that (ξθ, λ θ 1:T , v θ 0:T , w θ 0:T ) satisfies the well-known Constrained Pontryagin Minimum Principle (C-PMP) given in (S.5) in Lemma A.2. Based on the above, one can have the following result for the differentiability of ξθ. Lemma 1 (Differentiability of ξθ). Given a fixed θ̄, assume the following conditions hold for Σ(θ̄):
(i) the second-order condition (Lemma A.2) is satisfied for Σ(θ̄);
(ii) the gradients of all binding constraints at ξθ̄ are linearly independent (binding constraints include all equality constraints and all active inequality constraints);
(iii) strict complementarity holds at ξθ̄, i.e., active inequality constraint has positive multiplier.
Then, for all θ in a neighborhood of θ̄, there exists a unique once-continuously differentiable function (ξθ ,λ θ 1:T ,v θ 0:T ,w θ 0:T ) that satisfies the second-order condition (Lemma A.2) for the constrained opti-
mal control system Σ(θ) with ( ξθ,λ θ 1:T ,v θ 0:T ,w θ 0:T ) = ( ξθ̄,λ θ̄ 1:T ,v θ̄ 0:T ,w θ̄ 0:T ) at θ=θ̄. Hence, ξθ is a local isolated minimizing trajectory to Σ(θ). Further, for all θ near θ̄, the strict complementarity is preserved, and the linear independence of the gradients of all binding constraints at ξθ hold.
The proof of Lemma 1 can directly follow the well-known first-order sensitivity result in Theorem 2.1 in [74]. Here, conditions (i)-(iii) are the sufficient conditions to guarantee the applicability of the well-known implicit function theorem [75] to the C-PMP. Condition (ii) is well-known and serves as a sufficient condition for the constraint qualification to establish the C-PMP (see Corollary 3, pp. 22, [48]). Condition (iii) is necessary to ensure that the Jacobian matrix in the implicit function theorem is invertible, and it also leads to the persistence of strict complementarity, saying that the inactive inequalities remain inactive and active ones remain active and there is no ‘switching’ between them near θ̄. Both our practice and previous works [68, 69, 71, 74, 76] show that the conditions (i)-(iii) are very mild and the differentiability of ξθ can be attained almost everywhere in the space of θ.

heading: 4.2 Auxiliary Control System to Solve ∂ξθ∂θ
text: If the conditions (i)-(iii) in Lemma 1 for differentiability of ξθ hold, we next show that ∂ξθ ∂θ can also be efficiently solved by an auxiliary control system, which is originally proposed in the foundational work [71]. First, we define the new state and input (matrix) variables Xt ∈ Rn×r and Ut ∈ Rm×r, respectively. Then, we introduce the following auxiliary control system,
Σ(ξθ) :
control cost: J̄ = Tr T−1∑ t=0
( 1
2
[ Xt Ut ]′ [ Lxxt L xu t Luxt L uu t ] [ Xt Ut ] + [ Lxθt Luθt ]′ [ Xt Ut ])
+ Tr
( 1
2 X ′TL xx T XT + (L xθ T ) ′XT ) subject to
dynamics: Xt+1 = F xt Xt + Fut Ut + F θt with X0 = Xθ0 terminal constraint: ḠxTXT + ḠθT = 0, HxTXT +HθT = 0,
path constraint: ḠxtXt + Ḡut Ut + Ḡθt = 0, Hxt Xt +Hut Ut +Hθt = 0.
(3)
Here, Lxt and L xx t denote the first- and second- order derivatives, respectively, of the Hamiltonian Lt in (2) with respect to x; F xt , H x t , Ḡt denote the first-order derivatives of f t, ht, ḡt with respect
to x, respectively, where ḡt is the vector of stacking all active inequality constraints in gt; and the similar convention applies to the other notations. All derivative matrices defining Σ(ξθ) are evaluated at ( ξθ,λ θ 1:T ,v θ 0:T ,w θ 0:T ) , where λθ1:T , v θ 0:T , and w θ 0:T are usually the byproducts of a constrained optimal control solver [77] or can be easily solved from the C-PMP given ξθ, as done in [71]. We note that Σ(ξθ) is a Equality-constrained Linear Quadratic Regulator (LQR) system, as its control cost function is quadratic and dynamics and constraints are linear. For the above Σ(ξθ), we have the following important result without additional assumptions.
Theorem 1 (∂ξθ∂θ is a globally unique minmizing trajectory to Σ(ξθ)). Let the conditions (i)-(iii) in Lemma 1 for differentiability of ξθ hold. Then, the auxiliary control system Σ(ξθ) in (3) has a globally unique minimizing trajectory, denoted as { Xθ0:T , U θ 0:T−1
} , which is exactly ∂ξθ∂θ , i.e.,{
Xθ0:T , U θ 0:T−1 } = ∂ξθ ∂θ with Xθt = ∂xθt ∂θ and Uθt = ∂uθt ∂θ . (4)
The proof of the above theorem is in Appendix B. Theorem 1 states that as long as the conditions (i)(iii) in Lemma 1 for differentiability of ξθ are satisfied, without additional assumptions, the auxiliary control system Σ(ξθ) always has a globally unique minimizing trajectory, which is exactly ∂ξθ ∂θ . Thus, obtaining ∂ξθ∂θ is equivalent to solving Σ(ξθ), which be efficiently done thanks to the recent development of the equality-constrained LQR algorithms [78–80], all of which have a complexity of O(T ). The algorithm that implements Theorem 1 is given in Algorithm 1 in Appendix E.1.
5 Safe Unconstrained Approximations for ξθ and ∂ξθ ∂θ
From Section 4, we know that one can solve the constrained system Σ(θ) to obtain ξθ and solve its auxiliary control system Σ(ξθ) to obtain ∂ξθ ∂θ . Although theoretically appealing, there are several difficulties in implementation. First, solving a constrained optimal control Problem B(θ) is not as easy as solving an unconstrained optimal control, for which many trajectory optimization algorithms, e.g., iLQR [81] and DDP [82], are available. Second, establishing Σ(ξθ) requires the values of the multipliers vθ0:T and w θ 0:T . And third, to construct Σ(ξθ), one also needs to identify all active inequality constraints ḡt, which can be numerically difficult due to numerical error (we will show this in later experiments). All those difficulties motivate us to develop a more efficient paradigm to obtain both ξθ and ∂ξθ ∂θ , which is the goal of this section.
To proceed, we first convert the constrained system Σ(θ) to an unconstrained system Σ(θ, γ) by adding all constraints to its control cost via barrier functions. Here, we use quadratic barrier function for each equality constraint and logarithm barrier functions for each inequality constraint; and all barrier functions are associated with the same barrier parameter γ > 0. This leads to Σ(θ, γ) to be
Σ(θ, γ) :
control cost: J(θ, γ) = T−1∑ t=0 ( ct(xt,ut,θ)−γ qt∑ i=1 ln ( −gt,i(xt,ut,θ) ) +
1
2γ st∑ i=1 ( ht,i(xt,ut,θ) )2) + cT (xT ,θ)−
γ qT∑ i=1 ln ( −gT,i(xT ,θ) ) + 1 2γ sT∑ i=1 ( hT,i(xT ,θ) )2 ,
subject to dynamics: xt+1 = f(xt,ut,θ) with x0 = x0(θ), ∀t.
(5)
The trajectory ξ(θ,γ) = { x (θ,γ) 0:T ,u (θ,γ) 0:T−1 } produced by the above unconstrained system Σ(θ, γ) is
ξ(θ,γ) = { x (θ,γ) 0:T ,u (θ,γ) 0:T−1 } ∈ arg min{x0:T ,u0:T−1} J(θ, γ)
s.t. xt+1 = f(xt,ut,θ) with x0 = x0(θ), SB(θ, γ)
that is, ξ(θ,γ) is minimizing the new control cost J(θ, γ) subject to only dynamics. Then we have the following important result about the safe unconstrained approximation for ξθ and ∂ξθ ∂θ using Σ(θ, γ).
Theorem 2. Let conditions (i)-(iii) in Lemma 1 for differentiability of ξθ hold. For any small γ > 0,
(a) there exists a local isolated minimizing trajectory ξ(θ,γ) that solves Problem SB(θ, γ), and Σ(θ, γ) is well-defined at ξ(θ,γ), i.e., gt ( x (θ,γ) t ,u (θ,γ) t ,θ ) <0 and gT ( x (θ,γ) T ,θ ) <0;
(b) ξ(θ,γ) is once-continuously differentiable with respect to (θ, γ), and
ξ(θ,γ) → ξθ and ∂ξ(θ,γ) ∂θ → ∂ξθ ∂θ as γ → 0; (6)
(c) the trajectory derivative ∂ξ(θ,γ) ∂θ is a globally unique minimizing trajectory to the auxiliary control system Σ ( ξ(θ,γ) ) corresponding to Σ(θ, γ).
The proof of the above theorem is given in Appendix C. It is worth noting that the above assertions require no additional assumption except the same conditions (i)-(iii) for differentiability of ξθ. We make the following comments on the above results, using an illustrative cartpole example in Fig. 1.
First, assertion (b) states that by choosing a small γ > 0, one can simply use ξ(θ,γ) and ∂ξ(θ,γ) ∂θ
of the unconstrained optimal control system Σ(θ, γ) to approximate ξθ and ∂ξθ ∂θ
of the original constrained system Σ(θ), respectively. Second, notably, assertion (b) also states that the above approximations can be controlled for arbitrary accuracy by simply letting γ → 0, as illustrated in the upper panels in Fig. 1. Third, more importantly, assertion (a) states that the above approximations are always safe in a sense that the approximation ξ(θ,γ) with any small γ > 0 is guaranteed to satisfy all inequality constraints in the original Σ(θ), as illustrated in the bottom panels in Fig. 1. Finally, similar to Theorem 1, assertion (c) states that the derivative ∂ξ(θ,γ)
∂θ for Σ(θ, γ) is a globally unique mini-
mizing trajectory to its corresponding auxiliary control system Σ ( ξ(θ,γ) ) , thus PDP [71] directly applies here.
In addition to the theoretical importance of Theorem 2, we also summarize its algorithmic advantage compared to directly handling the original constrained system Σ(θ) and its auxiliary control system Σ(ξθ). First, solving the unconstrained Σ(θ, γ) is easier than solving the constrained Σ(θ) as more off-the-shelf algorithms are available for unconstrained trajectory optimization than for constrained one. Second, when solving ∂ξ(θ,γ)
∂θ using Σ ( ξ(θ,γ) ) , there is no need to identify the inactive and
active inequality constraints, as opposed to solving ∂ξθ ∂θ using Σ(ξθ); thus it is easier to implement and more numerically stable (we will show this later in experiments). Third, in contrast to Theorem 1, the unconstrained Σ(θ, γ) and Σ ( ξ(θ,γ) ) avoid dealing with the multipliers v0:T and w0:T . Finally, by absorbing hard inequality constraints into the control cost through barrier functions, Σ(θ, γ) introduces the ‘softness’ of constraints and mitigates the discontinuous ‘switching’ between inactive/active inequalities over a large range of θ. This leads to a more numerically stable algorithm, as we will show in later experiments. Implementation of Theorem 2 is given in Algorithm 2 in Appendix E.2.

heading: 6 Safe PDP to Solve Problem P
text: According to Theorem 2, we use the safe unconstrained approximation system Σ(θ, γ) in (5) to replace the original inner-level constrained system Σ(θ) in (1). Then, we give the following important result for solving Problem P, which addresses the Challenges (4) and (5) in Section 3. Theorem 3. Consider all functions defining the constrained optimal control system Σ(θ) are at least three-times continuously differentiable, and let the conditions (i)-(iii) in Lemma 1 for differentiability of ξθ hold in a neighborhood of θ
∗. Suppose that the second-order condition for a local isolated minimizor θ∗ to Problem P is satisfied, that the gradients∇θRi(ξθ∗ ,θ
∗) of all binding constraints Ri(ξθ,θ) = 0 are linearly independent at θ
∗, and that the strict complementary holds at θ∗. Then, for any small > 0 and any small γ > 0, the following outer-level unconstrained approximation
θ∗( , γ) = arg min θ
` ( ξ(θ,γ),θ ) − ∑l i=1 ln ( −Ri ( ξ(θ,γ),θ )) , SP( , γ)
with ξ(θ,γ) being the optimal trajectory to the inner-level safe unconstrained approximation system Σ(θ, γ) in (5), has the following assertions:
(a) there exists a local isolated minimizor θ∗( , γ) to the above SP( , γ), and the corresponding trajectory ξ(θ∗( ,γ),γ) from the inner-level approximation system Σ ( θ∗( , γ), γ ) is safe with
respect the original outer-level constraints, i.e., Ri ( ξ(θ∗( ,γ),γ),θ ∗( , γ) ) < 0, i = 1, 2, ..., l;
(b) θ∗( , γ) is once-continuously differentiable with respect to both and γ, and
θ∗( , γ)→ θ∗ as ( , γ)→ (0, 0); (7)
(c) for any θ near θ∗( , γ), ξ(θ,γ) from the inner-level approximation system Σ(θ, γ) is safe with respect to the original outer-level constraints, i.e., Ri ( ξ(θ,γ),θ ) < 0, i = 1, 2, ..., l.
The proof of the above theorem is given in Appendix D. The above result says that instead of solving the original constrained Problem P with the inner-level constrained system Σ(θ) in (1), one can solve an unconstrained approximation Problem SP( , γ) with the inner-level safe unconstrained approximation system Σ(θ, γ) in (5). Particularly, we make the following comments on the importance of the above theorem. First, claim (a) affirms that although the inner-level trajectory ξ(θ,γ) is an approximation (recall Theorem 2), the outer-level unconstrained Problem SP( , γ) always has a locally unique solution θ∗( , γ); furthermore, at θ∗( , γ), the corresponding inner-level trajectory ξ(θ∗( ,γ),γ) is safe with respect to the original outer-level constraints, i.e., Ri ( ξ(θ∗( ,γ),γ),θ ∗( , γ) ) < 0, i = 1, 2, ..., l. Second, claim (b) asserts that the accuracy of the solution θ∗( , γ) to the outer-level approximation Problem SP( , γ) is controlled jointly by the inner-level barrier parameter γ and outer-level barrier parameter : as both barrier parameters approach zero, θ∗( , γ) is converging to the true solution θ∗ to the original Problem P. Third, claim (c) says that during the local search of the outer-level solution θ∗( , γ), the corresponding inner-level trajectory ξ(θ,γ) is always safe with respect to the original outer-level constraints, i.e., Ri ( ξ(θ,γ),θ ) < 0, i = 1, 2, ..., l. The above Theorem 3, together with Theorem 2 provide the safety- and accuracy- guarantees for the whole Safe PDP framework. Then entire Safe PDP algorithm is given in Algorithm 3 in Appendix E.3.

heading: 7 Applications to Different Safety-Critical Tasks
text: We apply Safe PDP to solve some representative safety-critical learning/control tasks. For a specific task, one only needs to specify the parameterization detail of Σ(θ), a task loss `(ξθ,θ), and task constraints Ri(ξθ,θ) in Problem P. The experiments are performed on the systems of different complexities in Table 1. All codes are available at https://github.com/wanxinjin/Safe-PDP.
Problem I: Safe Policy Optimization aims to find a policy that minimizes a control cost J subject to constraints g while guaranteeing that any intermediate policy during optimization should never violate the constraints. To apply Safe PDP to solve such a problem for the systems in Table 1, we set:
Σ(θ) : dynamics: xt+1 = f(xt,ut) with x0,
policy: ut = πt(xt,θ), (8)
where dynamics f is learned from demonstrations in Problem III, and π(θ) is represented by a (deep) feedforward neural network (NN) with θ the NN parameter. In Problem P, the task loss `(ξθ,θ) is set as J(θobj), and task constraints Ri(ξθ,θ) as g(θcstr), with both θobj and θcstr known. Then, safe policy optimization is to solve Problem P using Safe PDP. The results for the robot arm and 6-DoF maneuvering quadrotor are in Fig. 2, and the other results and details are in Appendix F.1.
Fig. 2a and 2c plot loss (control cost) versus gradient-descent iteration under different , showing that the NN policy achieves a good convergence when ≤ 10−2 (as asserted by Theorem 3). Fig. 2b and 2d show all indeterminate control trajectories generated from the NN policy during entire iterations; we also mark the constraints Umax and compare with the unconstrained policy optimization under the same settings. The results confirm that Safe PDP enables to achieve an optimal policy while guaranteeing that any intermediate policy throughout optimization is safe.
Problem II: Safe Motion Planning searches for a dynamics-feasible trajectory that optimizes a criterion and avoids unsafe regions (obstacles), meanwhile guaranteeing that any intermediate motion trajectory during search must avoid the unsafe regions. To apply Safe PDP to solve such problem, we specialize Σ(θ) as (8) except that policy here is ut = u(t,θ), which is represented by Lagrangian polynomial [83] with θ the parameters (pivots). In Problem P, task loss is set as J(θobj), and task constraints as g(θcstr), with θobj and θcstr known in Table 1. The safe planning results using Safe PDP for cartpole and 6-DoF rocket landing are in Fig. 2, in comparison with ALTRO, a state-of-the-art constrained trajectory optimization method [21]. Other results and more details are in Appendix F.2.
Fig. 3a and 3c plot the task loss versus gradient-descent iteration, showing that the trajectory achieves a good convergence with ≤ 10−2. Fig. 3b and 3d show all intermediate motion trajectories during entire optimization, with constraints marked. The results confirm that Safe PDP can find an optimal trajectory while always respecting constraints throughout planning process.
Problem III: Learning MPC from Demonstrations. Suppose for all systems in Table 1, the control cost J(θcost), dynamics f(θdyn) and constraints gt(θcstr) are all unknown and parameterized as in Table 1. We aim to jointly learn θ = {θcost,θdyn,θcstr} from demonstrations ξdemo = {xdemo0:T ,udemo0:T−1} of a true expert system. In Problem P, set Σ(θ) as (1), consisting of J(θcost), f(θdyn), and gt(θcstr) parameterized; set task loss `(ξθ,θ) = ‖ξ
demo−ξθ‖2, which quantifies the reproducing loss between ξdemo and ξθ; and there is no task constraints. By solving Problem P, we can learn Σ(θ) such that its reproduced ξθ is closest to given ξ
demo. The demonstrations ξdemo here are generated with θ known (two episode trajectories for each system with time horizon T=50). The plots of the loss versus gradient-descent iteration are in Fig. 4, and more details and results are in Appendix F.3.
In Fig. 4a-4d, for each system, we use three strategies to obtain ξθ and ∂ξθ ∂θ for Σ(θ): (A) use a solver [77] to obtain ξθ and use Theorem 1 to obtain ∂ξθ ∂θ
; (B) use Theorem 2 to approximate both ξθ and ∂ξθ ∂θ by ξ(θ,γ) and ∂ξ(θ,γ) ∂θ
, respectively, γ=10−2; and (C) use a solver to obtain ξθ and Theorem 2 only for ∂ξθ
∂θ . Fig. 4a-4d show that for Strategies (B) and (C), the reproducing loss quickly
converges to zeros, indicating that the dynamics, constraints, and control cost are successfully learned to reproduce the demonstrations. Fig. 4a-4d also show numerical instability for strategy (A); this is due to the discontinuous ‘switching’ of active inequalities between iterations, and also the error in correctly identifying active inequalities (we identify them by checking gt,i > −δ with δ > 0 a small
threshold), as analyzed in Section 5. More analysis is given in Appendix F.3. Note that we are not aware of any existing methods that can handle jointly learning of cost, dynamics, and constraints here, and thus we have not given benchmark comparison. Fig. 4e gives timing results of Safe PDP.
8 Discussion
Comparisons with other differentiable frameworks. Fig. 5 compares Safe PDP, CasADi [70], and Differentiable MPC [68] for the computational efficiency of differentiating an optimal trajectory of a constrained optimal control system with different control horizons T . The results show a significantly computational advantage of Safe PDP over CasADi and Differentiable MPC. Specifically, Safe PDP has a complexity of O(T ), while CasADi and Differentiable MPC have at least O(T 2). This is because both CasADi and differentiable MPC are based on the implicit function theorem [75] and need to compute the inverse of a Hessian matrix of the size proportional to T × T . In contrast, Safe PDP solves the gradient of a trajectory by constructing an Auxiliary Control System, which can be solved using the Riccati equation.
Limitation of Safe PDP. Safe PDP requires a safe (feasible) initialization such that the log-barrier control cost or loss is well-defined. While restrictive, safe initialization is common in safe learning [63, 84]. We have the following empiricism on how to provide safe initializations for different types of problems, as adopted in our experiments in Section 7. In safe policy optimization, one could first use supervised learning to learn a safe policy from some safe trajectories/demonstrations (not necessarily be optimal) and then use the learned safe policy to initialize Safe PDP. In safe motion planning, one could arbitrarily provide a safe trajectory (not necessarily optimal) to initialize Safe PDP. In learning MPCs, the goal includes learning of constraint itself, and there is no such requirement.
Strategies to accelerate forward pass of Safe PDP. There are many strategies to accelerate a long-horizon trajectory optimization (optimal control) in the forward pass of Safe PDP. (I) One effective way is to scale the (continuous) long-horizon problem into a smaller one (e.g., a unit) by applying a time-warping function to the dynamics and cost function [85]. After solving the scaled short-horizon problem, re-scale the trajectory back. (II) There are also ‘warm-up’ tricks, e.g., one can initialize the trajectory at the next iteration using the result of the previous iteration. (III) One can also use a hierarchical strategy to solve trajectory optimization from coarse to fine resolutions. We have tested and provided the comparison for the above three acceleration strategies in Appendix G.2.
Please refer to Appendix G for more discussion, which includes G.1: comparison between Safe-PDP and non-safe PDP; G.2: comparison of different strategies for accelerating long-horizon trajectory optimization; G.3: trade-offs between accuracy and computational efficiency using barrier penalties; G.4: learning MPCs from non-optimal data; and G.5: detailed discussion on limitation of Safe PDP.

heading: 9 Conclusions
text: This paper proposes a Safe Pontryagin Differentiable Programming methodology, which establishes a provable and systematic safe differentiable framework to solve a broad class of safety-critical control and learning tasks with different types of safety constraints. For a constrained system and task, Safe PDP approximates both the solution and its gradient in backward pass by solving their more efficient unconstrained counterparts. Safe PDP has established two results: one is the controlled accuracy guarantee for approximations of the solution and its gradient, and the other is the safety guarantee for constraint satisfaction throughout the control and learning process. We envision the potential of Safe PDP for addressing various safety-critical problems in machine learning, control, and robotics fields.
Acknowledgments and Disclosure of Funding
This work is supported by the NASA University Leadership Initiative (ULI) under grant number 80NSSC20M0161. The research of Prof. George J. Pappas is supported by the AFOSR Assured Autonomy in Congested Environments under grant number FA9550-19-1-0265. This work has been done primarily in the last semester of Wanxin Jin’s Ph.D. study at Purdue University. Wanxin Jin thanks Prof. Zhaoran Wang for some discussion about this work.

Review summaries:
The authors propose a procedure for safe end-to-end learning of parameterized trajectory optimization problems. The entire learning problem is presented as a bi-level optimization. The outer optimization prescribes a loss function and safety constraints, which take as inputs the parameters and the output of an inner trajectory optimization problem using these same parameters. The overall map from parameters to the output of the outer problem is differentiated approximately with the help of: 1) approximating the inner and outer problems with unconstrained versions via log-barrier objective terms, and 2) using the discrete-time constrained PMP to differentiate the inner problem along an optimal trajectory. Safety is enforced by the log-barrier functions in the outer problem approximation.

This paper provides an efficient method based on Pontryagin Differentiable Programming (PDP) for the control of safety-critical systems. The method entails formulating the control problem as a bi-level optimization problem, where * The lower-level problem solves for a trajectory that minimizes some control cost subject to dynamics, terminal constraints, and path constraints associated with the underlying system (all of which are potentially parameterized), and * The upper-level problem aims to pick the parameters of the lower-level problem to minimize some task-specific loss subject to task-specific constraints.  The authors provide an efficient method to solve problems of this form (e.g., both terminal and path constraints) by employing barrier methods to both rewrite the outer problem as an unconstrained optimization problem, and to efficiently solve for solutions of and implicit gradients through the inner problem. They then prove that under certain assumptions, their method satisfies all problem constraints, as needed for the safety-critical setting. They provide experimental validation for the problems of policy optimization, motion planning, and imitation learning in several dynamical systems settings.

In order to satisfy both immediate and long-term safety constraints, this paper proposes Safe Pontryagin Differentiable Programming (Safe PDP). The proposed method is based on interior-point methods, and it enables us to incorporate heterogeneous types of constraints. The advantages of Safe PDP lie both theoretically and empirically. In the experiments, the authors demonstrated that their proposed method is better than unconstrained methods (in one experiment, a baseline is ALTRO, though) in toy problems.  

This paper proposes a Safe Pontryagin Differentiable Programming (Safe PDP) methodology. The contributions are at both theory and algorithmics for a new safe differentiable framework for various safety-critical learning and control tasks. The proposed approach is inspired by interior-point methods. Both backward and forward pass can be approximated and computed efficient by solving an unconstrained counterpart. The approximation can also be controlled for arbitrary accuracy using a barrier parameter. In addition, the authors can also show that all constraints are respected throughout the course of approximation and optimization, thus guaranteeing safety. Experiment results are shown in many learning and control tasks on different challenging control systems such as 6-DoF maneuvering quadrotor and 6-DoF rocket powered landing.