An efficient algorithm for a sharp approximation of universally quantified inequalities

ABSTRACT

This paper introduces a new algorithm for solving a subclass of quantified constraint satisfaction problems (QCSP) where existential quantifiers precede universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and design. We propose here a new generic branch and prune algorithm for solving such continuous QCSPs. Standard pruning operators and solution identification operators are specialized for universally quantified inequalities. Special rules are also proposed for handling the parameters of the constraints. First experimentation show that our algorithm outperforms the state of the art methods.

REFERENCES

• 1: Frédéric Benhamou , Frédéric Goualard, Universally Quantified Interval Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.67-82, September 18-21, 2000
• 2: Frédéric Benhamou , Frédéric Goualard , Éric Languénou, , Marc Christie, Interval constraint solving for camera control and motion planning, ACM Transactions on Computational Logic (TOCL), v.5 n.4, p.732-767, October 2004 [doi>10.1145/1024922.1024927]
• 3: F. Benhamou and W. Older. Applying interval arithmetic to real, integer and boolean constraints. Journal of Logic Programming, pages 1--24, 1997.
• 4: F. Benhamou , D. McAllester , P. van Hentenryck, CLP(intervals) revisited, Proceedings of the 1994 International Symposium on Logic programming, p.124-138, November 1994, Symposia, Melbourne
• 5: J. G. Cleary. Logical arithmetic. Future Computing Systems, pages 125--149, 1987.
• 6: Hélène Collavizza , François Delobel , Michel Rueher, Extending Consistent Domains of Numeric CSP, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.406-413, July 31-August 06, 1999
• 7: H. Collavizza, F. Delobel, and M. Rueher. Comparing Partial Consistencies. Reliab. Comp., 1:1--16, 1999.
• 8: P. Dorato. Quantified multivariate polynomial inequalities. IEEE Control Systems Magazine, 20(5):48--58, 2000.
• 9: Peter Dorato , Wei Yang , Chaouki Abdallah, Robust multi-objective feedback design by quantifier elimination, Journal of Symbolic Computation, v.24 n.2, p.153-159, August 1997 [doi>10.1006/jsco.1997.0120]
• 10: G. Fiorio, S. Malan, M. Milanese, and M. Taragna. Robust performance design of fixed structure controllers for systems with uncertain parameters. In Proceedings of the 32st IEEE Conference on Decision and Control, volume 4, pages 3029--3031, 1993.
• 11: David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys (CSUR), v.23 n.1, p.5-48, March 1991 [doi>10.1145/103162.103163]
• 12: Alexandre Goldsztejn, A branch and prune algorithm for the approximation of non-linear AE-solution sets, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141665]
• 13: A. Goldsztejn and L. Jaulin. Inner and Outer Approximations of Existentially Quantified Equality Constraints. In Proceedings of CP 2006, volume 4204/2006 of LNCS, pages 198--212.
• 14: L. Jaulin, I. Braems, and E. Walter. Interval methods for nonlinear identification and robust control. In In Proceedings of the 41st IEEE Conference on Decision and Control, volume 4, pages 4676--4681, 2002.
• 15: Luc Jaulin , Éric Walter, Guaranteed tuning, with application to robust control and motion planning, Automatica (Journal of IFAC), v.32 n.9, p.1217-1221, Aug. 1996
• 16: Mats Jirstrand, Nonlinear control system design by quantifier elimination, Journal of Symbolic Computation, v.24 n.2, p.137-152, August 1997 [doi>10.1006/jsco.1997.0119]
• 17: R. B. Kearfott. Interval Computations: Introduction, Uses, and Resources. Euromath, Bulletin 2(1):95--112, 1996.
• 18: O. Knueppel. PROFIL/BIAS - A Fast Interval Library. Computing, 53(3--4):277--287, 1994.
• 19: O. Lhomme. Consistency Techniques for Numeric CSPs. In Proceedings of IJCAI 1993, pages 232--238.
• 20: A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, pages 99--118, 1977.
• 21: S. Malan , M. Milanese , M. Taragna, Robust analysis and design of control systems using interval arithmetic, Automatica (Journal of IFAC), v.33 n.7, p.1363-1372, July 1997 [doi>10.1016/S0005-1098(97)00028-9]
• 22: A. Neumaier. Interval Methods for Systems of Equations. Cambridge Univ. Press, Cambridge, 1990.
• 23: S. Ratschan. Applications of Quantified Constraint Solving over the Reals Bibliography. http://www.cs.cas.cz/ratschan/appqcs.html.
• 24: S. Ratschan. Approximate quantified constraint solving by cylindrical box decomposition. Reliab. Comp., 8(1):21--42, 2002.
• 25: Stefan Ratschan, Efficient solving of quantified inequality constraints over the real numbers, ACM Transactions on Computational Logic (TOCL), v.7 n.4, p.723-748, October 2006 [doi>10.1145/1183278.1183282]
• 26: Xuan-Ha Vu , Djamila Sam-Haroud , Marius-Calin Silaghi, Approximation Techniques for Non-linear Problems with Continuum of Solutions, Proceedings of the 5th International Symposium on Abstraction, Reformulation and Approximation, p.224-241, August 02-04, 2002
• 27: X.-H. Vu, M. Silaghi, D. Sam-Haroud, and B. Faltings. Branch-and-prune search strategies for numerical constraint solving. Technical Report LIA-REPORT-2006-007, Swiss Federal Institute of Technology (EPFL), 2006.
• 28: M. Zettler and J. Garloff. Robustness analysis of polynomials with polynomial parameterdependency using bernstein expansion. IEEE Transactions on Automatic Control, 43(3):425--431, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory

Keywords:
continuous domains, interval arithmetic, quantified constraints