Abstract
This paper details a technique, called inter-block backtracking (IBB), which improves interval solving of decomposed systems with non-linear equations over the reals.
This technique, introduced in 1998 by Bliek et al., handles a system of equations previously decomposed into a set of (small) k × k sub-systems, called blocks. All solutions are obtained by combining the solutions computed in the different blocks. The approach seems particularly suitable for improving interval solving techniques.
In this paper, we analyze into detail the different variants of IBB which differ in their backtracking and filtering strategies. We also introduce IBB-GBJ, a new variant based on Dechter’s graph-based backjumping.
An extensive comparison on a sample of eight CSPs allows us to better understand the behavior of IBB. It shows that the variants IBB-BT+ and IBB-GBJ are good compromises between simplicity and performance. Moreover, it clearly shows that limiting the scope of the filtering to the blocks is very useful. For all the tested instances, IBB gains several orders of magnitude as compared to a global solving.
This is a preview of subscription content, log in via an institution to check access.
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
Ait-Aoudia, S., Jegou, R., Michelucci, D.: Reduction of constraint systems. In: Compugraphic (1993)
Bliek, C., Neveu, B., Trombettoni, G.: Using graph decomposition for solving continuous csps. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 102–116. Springer, Heidelberg (1998)
Bouma, W., Fudos, I., Hoffmann, C.M., Cai, J., Paige, R.: Geometric constraint solver. Computer Aided Design 27(6), 487–501 (1995)
Buchberger, B.: An algebraic method in ideal theory. In: Multidimensional System Theory, pp. 184–232. Reidel Publishing Co., Dordrecht (1985)
Mourrain, B., Bondyfalat, D., Papadopoulo, T.: An application of automatic theorem proving in computer vision. In: 2nd International Workshop on Automated Deduction in Geometry. Springer, Heidelberg (1999)
Dechter, R.: Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. Artificial Intelligence 41(3), 273–312 (1990)
Durand, C.: Symbolic and Numerical Techniques For Constraint Solving. PhD thesis, Purdue University (1998)
Van Hentenryck, P., Michel, L., Deville, Y.: Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge (1997)
Hoffmann, C., Lomonossov, A., Sitharam, M.: Finding solvable subsets of constraint graphs. In: Proc. Constraint Programming, CP 1997, pp. 463–477 (1997)
Jaulin, L., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis. Springer, Heidelberg (2001)
Jermann, C., Trombettoni, G., Neveu, B., Rueher, M.: A constraint programming approach for solving rigid geometric systems. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 233–248. Springer, Heidelberg (2000)
Lahaye, E.: Une méthode de résolution d’une catégorie d’équations transcendantes. Compte-rendu des Séances de L’Académie des Sciences 198, 1840–1842 (1934)
Latham, R.S., Middleditch, A.E.: Connectivity analysis: A tool for processing geometric constraints. Computer Aided Design 28(11), 917–928 (1996)
Lhomme, O.: Consistency techniques for numeric csps. In: IJCAI, pp. 232–238 (1993)
McAllester, D.A.: Partial order backtracking. Research Note, Artificial Intelligence Laboratory, MIT (1993), ftp://ftp.ai.mit.edu/people/dam/dynamic.ps
Merlet, J.-P.: Optimal design for the micro robot. In: IEEE Int. Conf. on Robotics and Automation (2002)
Trombettoni, G., Wilczkowiak, M.: Scene Reconstruction based on Constraints: Details on the Equation System Decomposition. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 956–961. Springer, Heidelberg (2003)
Wilczkowiak, M., Trombettoni, G., Jermann, C., Sturm, P., Boyer, E.: Scene Modeling Based on Constraint System Decomposition Techniques. In: Proc. International Conference on Computer Vision, ICCV 2003 (2003)
Wu, W.: Basic principles of mechanical theorem proving in elementary geometries. J. Automated Reasoning 2, 221–254 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neveu, B., Jermann, C., Trombettoni, G. (2005). Inter-block Backtracking: Exploiting the Structure in Continuous CSPs. In: Jermann, C., Neumaier, A., Sam, D. (eds) Global Optimization and Constraint Satisfaction. COCOS 2003. Lecture Notes in Computer Science, vol 3478. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11425076_2
Download citation
DOI: https://doi.org/10.1007/11425076_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26003-5
Online ISBN: 978-3-540-32041-8
eBook Packages: Computer ScienceComputer Science (R0)