Experimental Complexity Analysis of Continuous Constraint Satisfaction Problems

Yi Shang and Markus P.J. Fromherz

Abstract

Continuous constraint satisfaction problems are at the core of many real-world applications, including planning, scheduling, control, and diagnosis of physical systems such as car, planes, and factories. Yet in order to be effective in such resource-constrained environments, constraint-based techniques must take into account the complexity of continuous constrained problems. In this paper, we study complexity phase transition phenomena of continuous constraint satisfaction problems (CSPs). First, we analyze three continuous constraint satisfaction formulations based on (discrete) 3-SAT problems, which have a strong relation between structure and search cost. Then, we propose a generic benchmarking model for comparing continuous CSPs and algorithms, and present two example problems based on sine functions. In our experiments, these problems are solved using both local and global search methods. Besides comparing the complexities of different continuous CSPs and search algorithms, we also connect these back to results from similar studies on SAT problems. In solving continuous 3-SAT and sine-based CSPs, we find that the median search cost is characterized by simple parameters such as the constraint-to-variable ratio and constraint tightness, and that discrete search algorithms such as GSAT have continuous counter-parts with similar behavior. Regarding local versus global search techniques for constraint solving, our results show that local search methods are more efficient for weakly constrained problems, whereas global search methods work better on highly constrained problems.

For PDF file, send mail to fromherz parc com.

Back to the top.