|
LIRRA
1.0.0
|
This page summarizes the method of the paper: the planning model and its tube, the receding interval-STL synthesis program that defines what may be flown, the terminal sets, the runtime loop, the recursive-feasibility guarantee, and how the proposer is trained.
Planning uses a discrete-time linear model with sampling period \(\Delta t\),
\[ x_{k+1} = A x_k + B u_k + G w_k, \qquad u_k \in \mathcal{U}, \quad w_k \in \mathcal{W} = \{ w : |w| \le \bar w \}, \]
with box constraints \(\mathcal{X}\), \(\mathcal{U}\) and output \(y_k = C x_k\). A nominal plan \((\hat x_{0:N}, \hat u_{0:N-1})\) satisfies \(\hat x_{i+1} = A\hat x_i + B\hat u_i\) and is flown with the tracking law \(u_k = \hat u_k + K(x_k - \hat x_k)\), where \(A_K = A + BK\) is Schur. The tracking error \(e_k = x_k - \hat x_k\) then evolves as \(e_{k+1} = A_K e_k + G w_k\), so if it starts at zero, after \(i\) steps it lies in
\[ \mathcal{Z}(i) = \bigoplus_{l<i} A_K^l G \mathcal{W}, \qquad |e| \le \bar z(i) = \sum_{l<i} |A_K^l G|\, \bar w, \]
and the feedback correction is bounded by \(\bar k(i) = \sum_{l<i} |K A_K^l G|\,\bar w\). The index \(i\) is the error age: the number of steps since the tracking error was last known to be zero. For the MuJoCo vehicles, which are flown by a separate low-level tracker, \(K = 0\) at the planning level and the tube is a constant planar bound \(\varepsilon\) that is measured rather than proved.
STL formulas are built from affine predicates \(\mu : a^\top y - b \ge 0\) with conjunction, disjunction, and bounded eventually and always, in negation normal form. Robustness assigns each predicate the value \(a^\top y_k - b\) and evaluates conjunctions and disjunctions as minima and maxima. For an interval-valued signal \([\hat y_k - |C|\bar z,\ \hat y_k + |C|\bar z]\), a lower bound on robustness is obtained by evaluating each predicate at its worst case.
Let the formula \(\psi\) have horizon \(h\), so a window \([s, s+h]\) holds \(h+1\) samples. At planning step \(t\) the signal consists of
The specification is enforced on every window that ends at a planned sample. A predicate at planned step \(i\) (or at a predicted root, \(i = 0\)) counts as satisfied when
\[ a^\top C \hat x_i - b \;\ge\; \delta + |a^\top C|\,\bar z(o + i), \]
where \(\delta\) is the robustness margin. A predicted preceding sample of age \(\alpha\) uses the threshold \(\delta + |a^\top C|\bar z(\alpha)\), and a measured sample uses \(0\). Evaluating \(\psi\) with these predicate tests gives the interval-robustness test \(\rho^{\mathrm{I}} \ge \delta\) on each enforced window.
Given the root \((x_0, o)\), the preceding samples \(\mathcal{H}\) and the nominal mission trajectory \((x^{\mathrm{nom}}, u^{\mathrm{nom}})\), the receding-horizon program is
\[ \begin{aligned} \mathcal{P}(x_0, o, \mathcal{H}) : \quad \min_{\hat u_{0:N-1}} \;& \sum_{i=1}^{N_c} \gamma^i \,\| W(\hat x_i - x^{\mathrm{nom}}_i) \|_1 + w_u \sum_i \| \hat u_i - u^{\mathrm{nom}}_i \|_1 \\ \text{s.t.}\;& \hat x_{i+1} = A\hat x_i + B\hat u_i, \quad \hat x_0 = x_0, \\ & \hat x_i \in \mathcal{X} \ominus [-\bar z(o+i), \bar z(o+i)], \quad \hat u_i \in \mathcal{U} \ominus [-\bar k(o+i), \bar k(o+i)], \\ & \rho^{\mathrm{I}} \ge \delta \text{ on every enforced window}, \quad \hat x_{N-b+1}, \dots, \hat x_N \in \mathcal{Q}_f \text{ for some face } f. \end{aligned} \]
The objective keeps the vehicle close to its nominal mission (here, a PD patrol controller); robustness is a hard constraint, not something to maximize. The STL windows and the choice of terminal face make this a mixed-integer linear program.
Problem. For any proposer \(\pi\) that maps observations to input sequences \(\tilde u_{0:N-1}\), the architecture must (i) satisfy \(\psi\) on every window of the realized trajectory and (ii) hold a certified feasible input at every step, including while an optimization that takes up to \(d\) steps is pending. Both must hold regardless of how well the proposer is trained. The third goal, (iii) solving as rarely as possible by accepting feasible proposals, is what learning is for.
The patrol specifications constrain position through a box: in the original task the square \(S = \{|p_x|, |p_y| < c\}\), whose complement is the union of four half-planes (faces): \(p_x \ge c\), \(p_x \le -c\), \(p_y \ge c\), \(p_y \le -c\). The 3-D extension uses the cube \(S = \{|p_x|, |p_y|, |p_z| < c\}\), with six faces. With uncertain boundaries, each face is an interval predicate \([a]^\top y - [b] \ge 0\), and its terminal strip starts far enough out to satisfy the worst case anywhere along the face. The planning models are decoupled two-state blocks, one per axis (position and velocity; for the blimp also altitude and heading), each with a bounded input.
For each face \(f\) and axis \(a\), the region \(R_{f,a}\) is the tightened state box, intersected along the face-normal axis with the half-plane tightened by \(\delta + \bar z_p(\infty)\). Its maximal control-invariant subset \(\Omega_{f,a}\) under the tightened input bound is computed by iterating \(\Omega \leftarrow \Omega \cap \mathrm{Pre}(\Omega)\) until \(\Omega \subseteq \mathrm{Pre}(\Omega)\), and invariance is then verified by checking that every vertex admits an input that returns it to \(\Omega\) (enough by convexity). The terminal set of face \(f\) is \(\mathcal{Q}_f = \prod_a \Omega_{f,a}\).
Lemma (terminal sets). Each \(\mathcal{Q}_f\) is control invariant under the nominal dynamics with tightened inputs, lies inside the tightened state box, and satisfies face \(f\) of \(x \notin S\) with margin \(\delta + |a^\top C|\bar z(\infty)\). For \(\vartheta = \mathbf{F}_{[0,h_F]}(x \notin S)\) with \(b = 1\), and \(\varphi = (x \notin S) \vee \mathbf{F}_{[0,h_F]}\mathbf{G}_{[0,h_G]}(x \notin S)\) with \(b = h_G + 1\): if the last \(b\) states of a feasible plan lie in one \(\mathcal{Q}_f\) and a terminal controller keeps the nominal trajectory there, every window that extends past the planning horizon satisfies the specification, with the margins above, for all error ages.
The terminal condition is encoded with one binary variable per face, shared by all \(b\) terminal states, so a plan commits to a single face.
*The learned proposer suggests a trajectory segment; the check accepts it only if it is a feasible point of the synthesis program rooted at the measured state. Otherwise the vehicle keeps flying the cached plan while the program is solved from the state the plan predicts \(d\) steps ahead.*
The cached plan \(\Pi = (\hat x, \hat u, r, o_r, f)\) stores the nominal trajectory, its root step \(r\), the root's error age \(o_r\) and its terminal face \(f\). The terminal controller extends it indefinitely, so \(\hat x_k, \hat u_k\) are defined for all \(k \ge r\) with error age \(o_r + k - r\). The vehicle always flies \(u_k = \hat u_k + K(x_k - \hat x_k)\).
Proposal and check. When no solve is pending, the policy proposes \(\tilde u_{0:N-1}\) from the measured state, and its rollout \(\tilde x\) is accepted only if it is feasible for \(\mathcal{P}(x_k, 0, \mathcal{H}_k)\). Since the candidate is given, the check is a rollout, bound comparisons, Boolean evaluation of the STL windows with the tightened predicates, and a terminal-set membership test. An accepted proposal becomes the cached plan, rooted at \(k\) with error age zero.
Delay-compensated fallback. On rejection, the vehicle keeps flying the cached plan and a solve starts with a budget of \(d\) steps. It is rooted not at the current measured state but at the predicted state \(\hat x_{k+d}\), with error age \(o_r + k + d - r\). Its history holds the measurements through \(k\) and the cached predictions \(\hat y_{k+1}, \dots, \hat y_{k+d-1}\) with their ages. The solver is warm-started with the shifted cached plan and given a time limit of \(d\,\Delta t\) minus overhead, so it can return a feasible incumbent before converging. The result is checked independently and installed only if feasible; otherwise the cached plan stays.
Theorem. Assume (A1) the terminal sets satisfy the lemma above; (A2) \(\mathcal{P}(x_0, 0, \emptyset)\) is feasible; and (A3) the realized error satisfies \(|x_k - \hat x_k| \le \bar z(\text{age at } k)\) relative to the cached plan. Then, for any proposer, the loop
These guarantees do not depend on solver latency, since a missed deadline leaves the cached plan in force. For the linear model with \(w_k \in \mathcal{W}\), (A3) follows from the disturbance-tube construction.
Proof idea. A synthesis request rooted at \(\hat x_{k+d}\) with age \(o_r + k + d - r\) gives every shifted cached sample exactly its original tightening, so the state and input bounds still hold, and samples past the cached horizon are covered by the terminal lemma. Every constant sample is either measured (threshold zero) or predicted by \(\Pi\) with its original margin; by (A3), a predicate satisfied by a prediction stays satisfied once the sample is measured. Because \(\psi\) is in negation normal form, satisfaction is monotone in its predicates, so every window the cached plan enforced is still satisfied. Hence the shifted cached plan is feasible for every request (ii); accepted proposals and installed solutions pass the same check, which gives (i); and each realized window was enforced by some verified plan, which with (A3) and monotonicity gives (iii).
Three remarks delimit the result:
The proposer is a multilayer perceptron whose outputs pass through \(\tanh\) into the tightened input bounds, so input feasibility holds by construction. It observes the current state; the preceding \(h-1\) measured outputs, their margins outside \(S\) and a mask for samples before the episode; the current patrol waypoint; clock-indexed reference offsets \(x^{\mathrm{nom}}_{k+j} - x_k\) at \(j = 0, N/2, N\); and the uncertainty bound \(\bar w\) or \(\varepsilon\) (never its realization). It is trained across several bounds.
Feasibility margin. The check has a differentiable counterpart, implemented in JAX,
\[ c(\tilde u) = \min\Big( \rho^{\mathrm{I}} - \delta,\; \max_f \min\big(g_f - H_f \tilde x_{N-b+1:N}\big),\; \min(\text{state-bound slack}) \Big), \]
which is differentiable almost everywhere and whose sign reproduces the acceptance test exactly. It gives gradients through the rollout and the constraints, so training can push proposals to be feasible even when their imitation error is already small.
Behavior cloning and DAgger. The proposer first imitates solutions of \(\mathcal{P}\) collected along trajectories driven by the synthesis expert, a noise-perturbed expert (DART) and the nominal patrol, from randomized starts near \(S\) (including inward velocities) at several uncertainty levels. The loss is the squared input error, normalized by the input range, plus \(\lambda \max(0, \epsilon - c(\tilde u))\). DAgger then lets the proposer drive 80% of episodes, with the expert labeling every state at which a proposal is requested. Noise is added only to the first input of a proposal: perturbing the whole sequence would break the terminal condition, trigger a rejection, and send the vehicle back to states the expert already covers. After the last round the proposer is retrained from scratch on all the data with a larger margin ( \(\lambda = 5\), \(\epsilon = 0.05\)).
PPO fine-tuning. Finally the proposer is fine-tuned with PPO in a JAX planning environment batched with Brax. Each environment step is one planning step, and each action is a whole proposed trajectory. The reward
\[ r = -c_J J(\tilde u) - c_c \max\big(0, \epsilon - \max(c(\tilde u), -1)\big) + c_{\mathrm{ok}} \mathbb{1}[c(\tilde u) \ge \epsilon] - c_s \mathbb{1}[c(\tilde u) < 0] - c_v \mathbb{1}[\text{realized window violated}] \]
combines mission cost, the feasibility hinge, an acceptance bonus, a price on the fallback synthesis a rejection would cause, and realized violations ( \(c_J = 0.1\), \(c_c = 100\), \(c_{\mathrm{ok}} = 10\), \(c_s = 10\), \(c_v = 5\)). A checked-loop variant also approximates the fallback during training: rejected proposals are not flown, and the vehicle follows the last accepted plan instead, with the solver's result approximated by the shifted cached plan. Once that plan is used up the training environment applies a damping input rather than the terminal controller, and it runs on the linear planning model with sampled tracking errors, so the theorem does not cover it; training only shapes the proposer, and the guarantee comes from the check at runtime. No optimization runs inside batched training. PPO starts from the cloned policy with a small initial standard deviation (0.05) and learning rate ( \(10^{-5}\)) to stay close to it.