Oz 2.0: The Oz Explorer


The Idea

Development of applications based on constraint programming proceeds in two steps. The first step is to design a principally working solution. This is followed by the much harder task to make this solution work for problems of real-world size. The latter task usually involves a high amount of experimentation to gain additional insights into the structure of the problem.

The Explorer

The Oz Explorer is a visual constraint programming tool for Oz. The Explorer uses the search tree of a constraint problem as its central metaphor. The Explorer implements a user-guided search strategy: The user can interactively explore the search tree which is visualised as it is explored.

Above a screen shot of the Explorer is shown with around 7450 nodes, of which about 7350 are hidden automatically (of course, the nodes can be unhidden, if desired).

Nodes carry information on the corresponding constraints. The information can be accessed interactively by using predefined or user-defined display procedures. The Explorer can be used with any search problem. The problem need not be changed, annotated or modified in any way. In particular, the Explorer does not rely on a fixed constraint system.

Understanding Constraint Problems

First insights into the structure of the problem can be gained from the visualisation of the search tree: how are solutions distributed, how many solutions exist, how large are the parts of the tree explored before finding a solution. The insights can be deepened by displaying and analysing the constraints of nodes in the search tree: from this it can be deduced whether constraint propagation is sufficient and whether the heuristic suggests the right choices. User-defined display procedures allow to customise the Explorer such that analysing can be done by tools suited to a particular application (e.g., Gantt-charts for scheduling applications).

Interactive exploration allows to follow promising paths in the search tree without exploring irrelevant parts of it. This supports the design of new heuristics and search strategies.

Complex real world problems require that a tool is practical with respect to both efficiency and display economics. The amount of information displayed by the Explorer is variable: the search tree can be scaled and subtrees can be hidden. In particular, all subtrees that do not contain solutions can be hidden automatically. To deal with constraint problems that would use too much memory otherwise, the Explorer employs recomputation which trades space for time.

Further Information

How to use the Oz Explorer is described in a chapter of the Oz User's Manual.

There is also a research paper Oz Explorer: A Visual Constraint Programming Tool on the Explorer.


Christian Schulte