Spreadsheet Interface for Tabular Constraint Programming
In this project we are developing a generalization of
the spreadsheet paradigm, called Knowledgesheet,
for solving a class of constraint satisfaction problems. The traditional
spreadsheet paradigm is based on attaching expression to individual cells
and then evaluating them; the Knowledgesheet interface instead allows finite
domain constraints to be attached to individual cells that are then solved
to obtain a solution. This extension
provides an easy-to-use interface for solving a large class of constraint
satisfaction problems---those whose specification and solution conforms to
a 2-dimensional structure, e.g., scheduling problems, time-tabling problems, etc.
A prototype for the Knowledgesheet has been developed and applied to solve many
different types of problems. This prototype includes
the spreadsheet-like interface as well as the protocol between the interface
and the back-end constraint-solving engine. The constraint solving engine
is based on a finite domain constraint logic programming system (CLP(FD)).
The protocol maps the constraints attached to the various cells of the Knowledgesheet
to a CLP(FD) program. The auto-generated program is executed by the back-end
CLP(FD) engine and the computed results communicated to the Knowledgesheet
interface for display. A major advantage of Knowledgesheet is that novice users can
solve certain types of practical constraint satisfaction problems without being an
expert in constraint logic programming or constraint solving.
Participants: S. Akhter (now at Intel), Larry King.
Papers
-
G. Gupta, S. Akhter. Knowledgesheet: A Graphical Spreadsheet Interface for
Interactively Developing A Class of Constraint Programs.
In Proc. Practical Aspects of Declarative Languages,
Lecture Notes in Computer Science 1753,
Springer Verlag, 2000, (to appear).