Evaluation of Solving Models for Conditional Constraint Satisfaction Problems

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 21

AAAI Member Abstracts

Conditional constraint satisfaction problems (CondCSPs) adequately capture problem change at solving time by conditionally identifying those variables and constraints that are relevant to final solutions. Real-world tasks with dynamic behavior, such as configuration, design, diagnosis, planning, and hardware test generation, have been modeled more naturally with CondCSPs. Such interest has been matched by the development of more effective algorithms that depart from classical backtracking and incorporate local consistency checking. Although performance results have been reported for these specialized algorithms, the experimental analysis has been conducted separately, using different test suites, and little is known about the algorithms' relative performance. In this abstract we present a CondCSP solver that implements direct and reformulation-based algorithms, each of which using forward checking and maintaining local consistency. In our experimental analysis we have considered randomly generated CondCSPs of diverse topologies in terms of problem density and satisfiability of the standard and conditional problem components. Execution time results show that there is not one winner but that reformulation solving in conjunction with forward checking performs better on problems with larger solution sets, while direct solving in conjunction with maintaining arc consistency is always preferred over direct solving using forward checking.