 | Dear all,
I'm thinking of a constraint programming system that is more
"constructive"
than the examples I see in literature. But maybe I'm mislead and there
are
lots of out there I don't know. I would be grateful for any links,
pointers
to literature, and comments.
By now I know CP the following way: There is a fixed number of
variables
which represent the entities of a problem. A fixed procedure poses
constraints on these variables that correspond to relations between the
entities. Once all constraints are successfully posted, the variables
are
labeled and the solution is extracted. In case, the program fails
while
posting the constraints or labeling the variables, the program exits
and
reports that the problem has no solution.
I call this approach "static" because the solution process is
programmed for
one particular type of problem, regardless of the fact that it is often
possible to apply such solvers to problems of various sizes. They are
still
restricted to a specific class of problems and to a specific way to
solve
them.
But many problems require a more constructive solution process: For
example
in planning, it is not known beforehand how many actions there are
necessary
to solve a problem. Consequently, the number of variables and their
constraints is unknown, too. Planning systems that use constraints,
e.g.,
non-linear (least-commitment) planning systems, address this problem by
constructing the constraint satisfaction problem (aka partial plan)
simultaneously with solving it. Failure then does not mean that the
problem
is unsolvable, just that the current constraint satisfaction problem is
constructed the wrong way: The planning system backtracks and explores
a
different construction.
The system I plan to build has two inputs: (1) A problem (e.g., a
planning
problem) and (2) a description how to construct constraint satisfaction
problems from such an input.
What do you think? As I said, any comment welcome.
Uli
|
|
