To avoid collisions, a robot must repeatedly predict where nearby agents may move, usually with an imperfect model of their dynamics. Reachable sets provide such predictions, but computing them when the system matrices themselves are uncertain can become computationally expensive and conservative for frequent replanning. Moreover, a planner often needs to know only how far an agent can move in one particular direction, for example toward the robot, rather than the complete reachable set. We propose a direction-conditioned reachability method for linear systems with uncertain state and input matrices. Given a query direction d, the method selects one admissible model (A⋆,B⋆) whose reachable set extends nearly as far along d as the reachable set of the entire uncertain model family, and then computes the reachable set of only this model with a standard reachability solver. On an uncertain linearized bicycle model, the complete selection-and-computation pipeline is about three times faster than computing the reachable set of the full uncertain family in the CORA toolbox, while its extent along d is within 5% of the full family's in the reported directions. We also use the method in a closed-loop multi-vehicle simulation in which the robot queries, at each replanning step, how far each nearby vehicle can move toward it, and replans to avoid the resulting sets.
Figures & tables
Fig. 1: Direction-conditioned reachable sets for planning.
Fig. 2: Reachable sets for the query θ=60∘ . Green: uncertain CORA outer approximation Runc . Red: direction-conditioned reachable set RA⋆,B⋆ for the direction d shown by the arrow. Blue: initial set. Along d , the red set extends nearly as far as the green set, although it is much smaller in other directions.
Fig. 3: Range ( 27 ) of d(θ)⊤x as a function of θ . Green: uncertain CORA outer approximation Runc . Red: direction-conditioned reachable set RA⋆,B⋆ . Solid curves show the upper extent ρR(d) and dashed curves show the lower extent −ρR(−d) . Black curves evaluate ( 7 ) directly for the selected model.
θ
hunc+
hsel+
gap [%]
tsel [s]
ttotal [s]
0∘
3.564
3.484
2.2
0.0378
0.153
30∘
4.243
4.167
1.8
0.0375
0.167
60∘
4.458
4.414
1.0
0.0373
0.146
90∘
3.478
3.478
0.0
0.0356
0.158
120∘
1.805
1.718
4.8
0.0339
0.155
TABLE I: Upper extent along d(θ) of the uncertain CORA outer approximation ( hunc+ ) and the direction-conditioned set ( hsel+ ), their relative gap, and the time for selecting (A⋆,B⋆) ( tsel ) and for the complete Algorithm 1 ( ttotal ). Computing the uncertain CORA outer approximation takes 0.457s .
Fig. 4: Computation time versus query direction θ . Green: uncertain CORA propagation, computed once because it is independent of θ . Red: CORA propagation of the direction-conditioned model. The remaining curves show matrix-selection time and the total direction-conditioned pipeline.
Fig. 5: Reachable sets of Vehicle 1 at one update. The arrow d points from Vehicle 1 toward the ego. Green: uncertain CORA outer approximation Runc . Red: direction-conditioned reachable set RA⋆,B⋆ , which the planner avoids.
Fig. 6: Closed-loop simulation. Black: ego’s executed trajectory. Dashed blue: current A* path. Star: goal. Dashed circle: sensing radius. Green: uncertain CORA outer approximations Runc (reference only). Red: direction-conditioned reachable sets RA⋆,B⋆ , which the planner avoids. As the vehicles move, the red direction-conditioned sets and the A* path are recomputed at every update.
Sampling-Based Model-Predictive Control (MPC) algorithms are a flexible class of controllers used for navigation on a wide range of robotic systems. Historically, such approaches have lacked hard safety guarantees, a shortcoming which we remedy in this work by computing guaranteed reachable-set overapproximations online with a fast, interval-based pipeline. We show that our method achieves similar performance to a state-of-the-art reachability-based planner without the need for the expensive pre-computation step, and can be scaled to systems that are infeasible using existing approaches. Finally, we demonstrate that our technique reduces safety violations by over 99% in a racing simulation and successfully controls a model racecar on real hardware experiments without crashes.
Autonomous motion planning under unknown nonlinear dynamics requires learning system properties while navigating toward a target. In this work, we develop a hierarchical planning-control framework that enables online motion synthesis with limited prior system knowledge. The state space is partitioned into polytopes and approximates the unknown nonlinear system using a piecewise-affine (PWA) model. The local affine models are identified once the agent enters the corresponding polytopes. To reduce computational complexity, we introduce a non-uniform adaptive state space partition strategy that refines the partition only in task-relevant regions. The resulting PWA system is abstracted into a directed weighted graph, whose edge existence is incrementally verified using reach control theory and predictive reachability conditions. Certified edges are weighted using provable time-to-reach bounds, while uncertain edges are assigned information-theoretic weights to guide exploration. The graph is updated online as new data becomes available, and high-level planning is performed by graph search, while low-level affine feedback controllers are synthesized to execute the plan. Furthermore, the conditions of classical reach control theory are often difficult to satisfy in underactuated settings. We therefore introduce relaxed reachability conditions to extend the framework to such systems. Simulations demonstrate effective exploration-exploitation trade-offs with formal reachability guarantees.
Zhiquan Zhang, Melkior Ornik
University of Illinois Urbana-Champaign, IL, 61801 USA.
Safe motion planning in uncertain, time-varying environments is challenging because the safe region can change unpredictably across planning steps, often causing a loss of recursive feasibility. In this work, we present a Probabilistic Recursively Feasible Model Predictive Control (PRF-MPC) framework that guarantees recursive feasibility with a specified probability. We introduce properties that an ideal predictor should satisfy to ensure distributional consistency, and use these properties to derive closed-form expressions for the means and covariances of trajectories predicted at future time steps. Building on this analysis, we construct safety constraints that ensure, with high probability, that the current safe set is contained within the safe sets at future time steps, thereby probabilistically guaranteeing recursive feasibility. Simulation results on a lane-change scenario demonstrate that the proposed method significantly improves recursive feasibility.
Hyeontae Sung, Hyeongchan Ham, Junyoung Park +2
School of Electrical Engineering, Korea Advanced Institute of Science and Technology, Daejeon, Korea · The SYCAMORE Lab, ´Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Switzerland