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.
Figures & tables
Xdata←∅,X˙data←∅,x←x0
Algorithm 1 AffineSystemIdentification
Fig. 1 : A pipeline of the proposed motion planning and control framework.
Fig. 2 : Schematic illustration of the maximal and minimal control input range ul′j .
Fig. 3 : A 2D example illustrates uniform and non-uniform state space partitioning. The blue dot represents the current state and the red dot represents the target state. (Left) Uniform partitioning. (Right) Non-uniform partitioning.
Algorithm 3 Hierarchical Motion Planning and Control Framework
Fig. 4 : Simulation results for a fully actuated mobile robot operating under unknown dynamics. Each column corresponds to a distinct time instant during the simulation. The top row illustrates the robot’s trajectory within the simulated environment, while the bottom row depicts the associated reachability analysis and prediction, nonuniform adaptive state space partitioning, and high-level planning performed on the reachability-guaranteed graph. Blue arrows indicate facets that are provably reachable, red arrows denote the absence of feasible transitions, and the absence of an arrow represents uncertainty in edge existence. The initial tile is highlighted in yellow and the target tile is highlighted in green. The green dot and blue dot denote the current tile and the next tile on the predicted graph respectively. The red line shows the optimal path computed at each discrete planning step.
Fig. 5 : Simulation results for an under-actuated mobile robot operating under unknown dynamics. Each column corresponds to a distinct time during the simulation. The top row illustrates the robot’s trajectory (marked as orange line) in the simulated environment. The bottom row depicts the associated reachability analysis and prediction, nonuniform adaptive state space partitioning, and high-level planning performed on the reachability-guaranteed graph. Blue arrows indicate facets that are reachable. The target tile is marked by a red star. The red line represents the sequence of polytopes selected by the high-level planner, and the green dot denotes the robot’s current state.
Fig. 6 : An example of a three-dimensional cube ABCDEFGH and a subpolytope (truncated pyramid) A′B′C′D′EFGH . The blue planes represent the set of velocities generated by gu of vertices C and D , and the green plane represents the set of velocities generated by gu of vertex C′ .
Fig. 7 : An illustration of relaxed facet reachability conditions on side facets.
We consider robotic motion planning and control under unknown dynamics with hybrid state observations, where state measurements are available only in parts of the state space. Existing work combines system identification, predicted reachability, graph search and controller synthesis in a hierarchical framework using local affine approximated models over polytopic state space partitioning, but requires state observations for identification and feedback control. Based on this framework, we address blind regions by selecting nominal dynamics and precomputing open-loop control sequences before observation is lost. Since the true dynamics may differ from the selected nominal model, the robot may exit a blind polytope through an unintended facet. We quantify this transition risk and incorporate the possible outcomes into a stochastic transition system. The high-level planning problem is formulated as a stochastic shortest path problem, whose policy guides controller synthesis. A case study demonstrates that the method guides the robot from an initial state to a target while balancing route efficiency and the risks associated with traversing blind regions.
Zhiquan Zhang, Melkior Ornik
University of Illinois Urbana-Champaign, IL, 61801 USA
Neural network (NN) dynamics models and control policies achieve strong performance in robotics, but providing sound guarantees under uncertainty remains difficult, especially for closed-loop NN systems. Existing reachability tools provide formal over-approximations, yet are often non-differentiable, overly conservative, or too slow for modern learning and online planning pipelines. To address this, we present a parallelizable, differentiable reachability framework in JAX for continuous- and discrete-time systems with analytical and NN-based dynamics and controllers. Our framework combines Taylor-model flowpipe construction with CROWN-style linear bound propagation through a unified representation that preserves affine dependencies while supporting GPU-batched computation and automatic differentiation. Building on this reachability primitive, we develop (i) a certified training method that encourages reachability-friendly dynamics models and controllers, and (ii) a reachability-aware sampling-based MPC scheme with gradient-based refinement. Experiments on non-prehensile manipulation and quadrotor tasks, including hardware and higher-dimensional evaluations (up to 72D), demonstrate practical online planning while maintaining certified reachable-set over-approximations under bounded uncertainty.
Keyi Shen, Glen Chou
Georgia Institute of Technology, Atlanta, GA 30308
Underactuated systems pose a challenge for convex motion planning because their dynamically feasible motions lie on a manifold of trajectories in function space. Building on our earlier formulation of polytopic action sets (PAS), this paper presents a method for rapidly generating, online, trusted convex sets of short-horizon actions for underactuated and potentially nonlinear systems. Around a nominal trajectory, we construct local finite-dimensional action coordinates in which each parameter vector encodes a complete nearby motion through an affine trajectory map, rendering collision-avoidance and control bounds linear. To remain consistent with the nonlinear dynamics, we introduce a dynamics-violation metric and extract a trusted convex inner approximation using an IRIS-inspired inflation procedure directly in action space. The resulting PAS are reusable convex families of actions that can be queried and composed with linear programs, and a PAS-guided tree expansion treats nodes as composed reachable families rather than single trajectories, coupling local nonlinear fidelity with convex reuse for longer-horizon planning. The planner solves cluttered planar scenes in tens of milliseconds (14-78x faster than a kinodynamic RRT baseline) and reduces terminal error on a nonlinear underactuated benchmark by 26-86% over sampling and NLP baselines.
Akshay Jaitly, Siavash Farzan
Onyx Robotics, Boston, MA 02210, USA · Department of Electrical Engineering, California Polytechnic State University, San Luis Obispo, CA 93407, USA