Neuro-Symbolic Acceleration of MILP Motion Planning with Temporal Logic and Chance Constraints
For autonomous systems requiring real-time motion planning under complex constraints, this work provides a scalable acceleration method that improves solver performance by 20%.
The paper tackles the high computational cost and limited scalability of MILP-based motion planning for autonomous systems with temporal logic and chance constraints. By using graph neural networks to guide symbolic MILP solvers, they achieve an average performance gain of about 20% over state-of-the-art solvers in runtime and solution quality across three problem classes.
Autonomous systems must solve motion planning problems subject to increasingly complex, time-sensitive, and uncertain missions. These problems often involve high-level task specifications, such as temporal logic or chance constraints, which require solving large-scale Mixed-Integer Linear Programs (MILPs). However, existing MILP-based planning methods suffer from high computational cost and limited scalability, hindering their real-time applicability. We propose to use a neuro-symbolic approach to accelerate MILP-based motion planning by leveraging machine learning techniques to guide the solver's symbolic search. Focusing on three representative classes of diverse planning problems - Signal Temporal Logic (STL) specifications, chance constraints formulated via Conformal Predictive Programming (CPP), and Capability Temporal Logic (CaTL) specifications - we demonstrate how graph neural network-based learning methods can guide traditional symbolic MILP solvers in solving challenging planning problems, including branching variable selection and solver parameter configuration. Through extensive experiments, we show that neuro-symbolic search techniques yield scalability gains. Our approach yields substantial improvements across all three classes of planning problems, achieving an average performance gain of about 20% over state-of-the-art solver across key metrics, including runtime and solution quality.