Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.07515 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914505480470528 |
|---|---|
| author | Cai, Junyang Huang, Weimin Long, Brendan Cleaveland, Matthew Deshmukh, Jyotirmoy V. Lindemann, Lars Dilkina, Bistra |
| author_facet | Cai, Junyang Huang, Weimin Long, Brendan Cleaveland, Matthew Deshmukh, Jyotirmoy V. Lindemann, Lars Dilkina, Bistra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_07515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Neuro-Symbolic Acceleration of MILP Motion Planning with Temporal Logic and Chance Constraints Cai, Junyang Huang, Weimin Long, Brendan Cleaveland, Matthew Deshmukh, Jyotirmoy V. Lindemann, Lars Dilkina, Bistra Systems and Control 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. |
| title | Neuro-Symbolic Acceleration of MILP Motion Planning with Temporal Logic and Chance Constraints |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2508.07515 |