Binary Combinatorial Optimization-based Path Planning and Optimal Reach Control in Piecewise Linear Neural Abstraction Domain

Farid, Yousef;Jungers, Raphaël
(2025) Neurocomputing — Vol. 669 (2026)

Files

Neural_Abstraction_manuscript_R1.pdf
  • Open Access
  • Adobe PDF
  • 2.35 MB
Download

Details

Authors
Abstract
(en) This paper addresses the construction of a finite-state neural abstraction (NA) for a broad class of unknown, uncertain nonlinear discrete-time systems. The framework relies on an -approximate alternating simulation relation (ASR), where the neural network (NN) approximation error provides a quantitative bound between the abstracted model and the real system. We first formalize a state–space partitioning (SSP) induced by a NN with an activation function of type rectified linear unit (ReLU), whereby the continuous state–space is decomposed into polyhedral cells, and a discrete-time piecewise linear (PWL) dynamics model is associated with each input symbol. To efficiently compute transitions among cells, we introduce a binary combinatorial optimization (BCO) algorithm that finds the shortest paths between initial and target cells. A hybrid control law is then designed for optimal cell-to-cell transitions in PWL subsystems, combining tube model predictive control (MPC) with minimax-based feedback to ensure robustness. The result is a weighted automaton over polyhedral cells, where edge weights correspond to tube-MPC costs used within the BCO procedure. Establishing a feedback-refinement relation between the real unknown system and its data-driven finite abstraction model enables certified controller synthesis on the abstraction, with guaranteed refinement back to the real system. The proposed approach is validated on three benchmarks: autonomous vehicle path planning, a double-pendulum robotic system, and an inverted pendulum.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Farid, Y., & Jungers, R. (2025). Binary Combinatorial Optimization-based Path Planning and Optimal Reach Control in Piecewise Linear Neural Abstraction Domain. Neurocomputing, 669. https://doi.org/10.1016/j.neucom.2025.132504 (Original work published 2026)