M. Mouhoub, S. Sadaoui, and B. Chen (Canada)
Constraint Satisfaction, Formal Methods, Artificial Intelli gence.
A Constraint Satisfaction Problem (CSP) is a power ful framework used to solve a large variety of combina torial problems including frequency assignment, configu ration and conceptual design, molecular biology, chemi cal hypothetical reasoning, scheduling and planning, and scene analysis. While many algorithms have been proposed to efficiently solve CSPs, transforming arbitrary real-life combinatorial problems into CSPs remains a challenging task. In this paper we propose a Lotos-based CSP frame work that on the one hand eases the description of CSPs by providing a generic Lotos template to be customized, and on the other hand solves efficiently CSPs by integrat ing into the template constraint propagation techniques. In deed, Lotos, a formal specification language, provides an ideal level of abstraction for clearly and correctly describ ing CSPs. We use Lotos simulator together with constraint propagation to enumerate the solutions of CSPs. Experi mental tests, we have conducted on general CSPs, demon strate the efficiency of our framework to deal with large size combinatorial problems.
Important Links:
Go Back
