Constraint satisfaction and fixes: revisiting Sisyphus VT

Trevor Runcie, Peter Gray, Derek Sleeman

Research output: Chapter in Book/Report/Conference proceedingPublished conference contribution


This paper explores the solution of the VT Sisyphus II challenge using a Constraint Satisfaction Problem (CSP) paradigm and is an extension of the ExtrAKTor work presented at EKAW 2006. ExtrAKTor takes a Protege KB describing a propose and-revise (PnR) problem, including both constraints & fixes. Subsequently, it extracts and transforms these components so that they are directly usable by the ECLiPSe CSP toolkit to solve a range of configuration tasks. It was encouraging to note that (a) the solver coped very well with constraints involving real variables even when using a generalised propagation technique and (b) the techniques needed no "fix"' information, yet successfully dealt with the "antagonistic constraints" and the associated "thrashing" problem that had been a key issue in the original Marcus, Stout & McDermott VT paper. Consequently, we believe this is a widely useable technique for automatically generating and then solving this class of constraint problems, when they are expressed as Protege ontologies.

Original languageEnglish
Title of host publicationResearch and development in intelligent systems XXV
Subtitle of host publicationProceedings of AI-2008, The Twenty-eighth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence
EditorsFrans Coenen, Miltos Petridis
Place of PublicationGodalming
Number of pages14
ISBN (Print)978-1-84882-170-5
Publication statusPublished - 2009


Dive into the research topics of 'Constraint satisfaction and fixes: revisiting Sisyphus VT'. Together they form a unique fingerprint.

Cite this