Recently I had a course on Constraint Satisfaction Problems in my university. The subject was so interesting to me. We studied basic concepts and recent works on CSPs, and also, distributed CSPs and parallel search algorithms used to solve this kind of problems. Among these staff Asynchronous Backtracking was the most interesting to me. For my final project of CSP course, My friend and I have implemented an improvement of ABT that uses polynomial space. Better improvements exists, especially Agile-ABT which we failed to implement in-time.
A Simple Constraint Satisfaction Problem
During research phase I was looking around to find similar projects. Then encountered Geocode project (generic constraint development environment). Its documentation says:
Gecode Logo
Gecode is a toolkit for developing constraint-based systems and applications. Gecode provides a constraint solver with state-of-the-art performance while being modular and extensible. Gecode is:
open, comprehensive, efficient, documented, free, portable, parallel and tested
Well, that is a very nice set of features. The developers of project have done a great job. They pretend that gecode is most optimized and efficient infrastructure of CSP:
Gecode offers excellent performance with respect to both runtime and memory usage. It won all gold medals in all categories at the MiniZinc Challenges from 2008 to 2012: 2012, 2011, 2010, 2009, and 2008.
Unfortunately the library has some drawbacks making it useless for simple CSP staff. Most importantly, I think gecode is hard to use. In order to solve a CSP you need to inherit from a class of library, add constraint sets by hand, in code, and compile. While it’s so flexible and fast, it’s a little bit hard to use. This gives me an idea: Implement an easy-to-use, portable and efficient library for doing CSP staff.
At first glance it looks like re-inventing the wheel. Well, it’s kind of. But not exactly! The library I’m thinking of is much more simpler. It’s supposed to be fast. Most important feature that I need to include, is support for XCSP 2.1 specification. This file structure is the standard XML-based description of constraint satisfaction problems developed by International CSP Solver Competition comitee. User should be able to implement his/her own CSP solver, on the top of infrastructure layer. Infrastructure do the boring, repeated staff. Generic CSP solver should be able to read CSPs from XCSP files or streams and then convert them into a well-defined data structures, very close to formal definition of CSP. Any other solver is supposed to inherit from GCSPS. Nothing special is here. This is just matter of OOP design. I must take care to avoid making a disaster design. You know, it’s very easy in C++ to make a mess 😀
The killer feature of my (not-yet-born) library, is support for XCSP. XCSP 2.1 is very flexible. You can define constraints, relations, functions and generalized constraints in terms of XML. It supports MathML and a C-style notation with a set of functions to declare implicit constraints.
For example consider N-Queens problem. One can easily define a predicate to “implicitly” specify constraints:
<predicates nbPredicates="1"> <predicate name="P0"> <parameters>int X0 int X1 int X2</parameters> <expression> <functional>and(ne(X0,X1),ne(abs(sub(X0,X1)),X2))</functional> </expression> </predicate> </predicates>
And then, many constraints can refer to same predicate:
<constraints nbConstraints="66"> <constraint name="C0" arity="2" scope="V0 V1" reference="P0"> <parameters>V0 V1 1</parameters> </constraint> <constraint name="C1" arity="2" scope="V0 V2" reference="P0"> <parameters>V0 V2 2</parameters> </constraint> <!-- And so on... --> </constraints>
This makes things simpler. You don’t need to have a huge C set. I’m planning to simulate same idea in C++ code using function pointers. It’s not very easy… I will need a good XML parser and I need to implement very fast lexer/parser pair to interpret C-style notation of functional objects.
It may be fast enough to catch gecode!
Final word: I am planning to add AI-planner infrastructure (PDDL parser, etc) in far future. That’s why it’s named libAIT instead of libGCSP !
Challenge accepted 🙂
One Alone Bit 