A Caltech Library Service

Learning-Based Abstractions for Nonlinear Constraint Solving

Dathathri, Sumanth and Aréchiga, Nikos and Gao, Sicun and Murray, Richard M. (2017) Learning-Based Abstractions for Nonlinear Constraint Solving. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence , pp. 592-599. ISBN 978-0-9992411-0-3.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We propose a new abstraction refinement procedure based on machine learning to improve the performance of nonlinear constraint solving algorithms on large-scale problems. The proposed approach decomposes the original set of constraints into smaller subsets, and uses learning algorithms to propose sequences of abstractions that take the form of conjunctions of classifiers. The core procedure is a refinement loop that keeps improving the learned results based on counterexamples that are obtained from partial constraints that are easy to solve. Experiments show that the proposed techniques significantly improved the performance of state-of-the-art constraint solvers on many challenging benchmarks. The mechanism is capable of producing intermediate symbolic abstractions that are also important for many applications and for understanding the internal structures of hard constraint solving problems.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Murray, Richard M.0000-0002-5785-7481
Additional Information:© 2017 International Joint Conferences on Artificial Intelligence. This work was partially supported by STARnet, a Semiconductor Research Corporation program, sponsored by MARCO and DARPA and in part by Toyota InfoTechnology Center and NSF CPS1446725. The authors would also like to thank Joel W. Burdick for helpful input.
Funding AgencyGrant Number
Toyota InfoTechnology CenterUNSPECIFIED
Subject Keywords:Symbolic Algorithms, Machine Learning, Interpolants, Constraint Solving, Machine Intelligence
Record Number:CaltechAUTHORS:20170523-230106516
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:77682
Deposited By: Sumanth Dathathri
Deposited On:24 May 2017 16:59
Last Modified:03 Oct 2019 18:00

Repository Staff Only: item control page