Abstract
In recent years, interval constraint-based solvers have shown their ability to efficiently solve challenging non-linear real constraint problems. However, most of the working systems limit themselves to delivering point-wise solutions with an arbitrary accuracy. This works well for equalities, or for inequalities stated for specifying tolerances, but less well when the inequalities express a set of equally relevant choices, as for example the possible moving areas for a mobile robot. In that case it is desirable to cover the large number of point-wise alternatives expressed by the constraints using a reduced number of sets, as interval boxes. Several authors [2,1,7] have proposed set covering algorithms specific to inequality systems. In this paper we propose a lookahead backtracking algorithm for inequality and mixed equality/inequality constraints. The proposed technique combines a set covering strategy for inequalities with classical interval search techniques for equalities. This allows for a more compact representation of the solution set and improves efficiency.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Benhamou and F. Goualard. Universally quantified interval constraints. In Procs. of CP’2000, pages 67–82, 2000.
J. Garloff and B. Graf. Solving strict polynomial inequalities by Bernstein expansion. Symbolic Methods in Control System Analysis and Design, London: IEE, pages 339–352, 1999.
L. Granvilliers. Consistances locales et transformations symboliques de contraintes d’intervalles. PhD thesis, Université d’Orléans, déc 98.
ILOG. Solver 4.4, Reference Manual. ILOG, 1999.
L. Jaulin. Solution globale et garantie de problèmes ensemblistes; Application à l’estimation non linéaire et à la commande robuste. PhD thesis, Université Paris-Sud, Orsay, Feb 94.
O. Lhomme and M. Rueher. Application des techniques CSP au raisonnement sur les intervalles. Revue d’intelligence artificielle, 11(3):283–311, 97. Dunod.
D. Sam-Haroud and B. Faltings. Consistency techniques for continuous constraints. Constraints, ] An International Journal,1, pages 85–118, 96.
P. Van Hentenryck.A gentle introduction to Numerica. AI, 103:209–235, 98.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Silaghi, MC., Sam-Haroud, D., Faltings, B. (2001). Search Techniques for Non-Linear Constraint Satisfaction Problems with Inequalities. In: Stroulia, E., Matwin, S. (eds) Advances in Artificial Intelligence. Canadian AI 2001. Lecture Notes in Computer Science(), vol 2056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45153-6_18
Download citation
DOI: https://doi.org/10.1007/3-540-45153-6_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42144-3
Online ISBN: 978-3-540-45153-2
eBook Packages: Springer Book Archive