Title: An interval partitioning algorithm for constraint satisfaction problems

Authors: Chandra Sekhar Pedamallu, Arun Kumar, Tibor Csendes, Janos Posfai

Addresses: New England Biolabs Inc., Ipswich, MA, 01938, USA. ' School of Aerospace, Mechanical and Manufacturing Engineering, RMIT University, 124 LaTrobe Street, Melbourne, Victoria 3000, Australia. ' Department of Computational Optimisation, University of Szeged, H-6701 Szeged, P.O. Box 652, Hungary. ' New England Biolabs Inc., Ipswich, MA, 01938, USA

Abstract: We propose an efficient interval partitioning algorithm to solve the continuous constraint satisfaction problem (CSP). The method comprises a new dynamic tree search management system that also invokes local search in selected subintervals. This approach is compared with two classical tree search techniques and three other interval methods. We study some challenging kinematics problems for testing the algorithm. The goal in solving kinematics problems is to identify all real solutions of the system of equations defining the problem. In other words, it is desired to find all object positions and orientations that satisfy a coupled non-linear system of equations. The kinematics benchmarks used here arise in industrial applications.

Keywords: continuous constraint satisfaction; interval partitioning; local search; tree search strategies; kinematics.

DOI: 10.1504/IJMIC.2011.042347

International Journal of Modelling, Identification and Control, 2011 Vol.14 No.1/2, pp.133 - 140

Published online: 21 Mar 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article