Hierarchical Motion Planning and Control under Unknown Nonlinear Dynamics via Predicted Reachability

Researchers Zhiquan Zhang and Melkior Ornik have introduced a novel hierarchical framework that enables autonomous systems to plan and execute motions in environments with completely unknown and nonlinear dynamics. The core innovation lies in partitioning the state space into polytopes and approximating the complex, unknown system with simpler, local piecewise-affine (PWA) models. These models are identified only as the agent enters each region, allowing for online learning. To manage computational load, the team developed a non-uniform adaptive state space partition that refines the model only in areas critical to the task, avoiding unnecessary complexity elsewhere.

This learned PWA system is then abstracted into a directed weighted graph, where edges represent possible transitions between regions. The existence of these edges is rigorously verified using reach control theory and predictive reachability conditions. Certified edges are assigned weights based on provable time-to-reach bounds, while uncertain edges receive information-theoretic weights to strategically guide exploration. High-level planning is performed via graph search on this continuously updated map, while low-level affine feedback controllers execute the chosen path. A key extension is the introduction of relaxed reachability conditions, which allows the framework to be applied to challenging underactuated systems where classical control theory often fails. Simulation results demonstrate that the method successfully balances the need to explore the unknown environment with the goal of efficiently reaching a target, all while maintaining formal safety and reachability guarantees.