SearchToolKit: A Toolkit for Constraint-based Search Engines

Martin Henz and Chew Tee Yong
School of Computing

The Problem

Solutions to combinatorial search problems can benefit from custom-made constraint-based inference engines that go beyond depth-first search. The concurrent constraint language Oz provides support for programming inference engines. The Mozart system for Oz comes with several engines, extended in dimensions such as interaction, visualization, and optimization. However, these extensions are monolithic in their software design, not catering for systematic reuse of components.

SearchToolKit

SearchToolKit provides an object-oriented modular architecture for building inference engines that achieves high reusability and supports rapid prototyping of search algorithms and their extensions.

Highlights

  • Search algorithms: SearchToolKit provides several basic search algorithms, including depth-first, breadth-first, iterative deepening and limited-discrepancy search. It is easy to program new algorithms and integrate them with the other components of the system.
  • Interactivity: SearchToolKit allows to specify several modes of interactivity such as first-solution, all-solution, and node-level tracing.
  • Optimization: SearchToolKit allows to integrate branch-and-bound and restart optimization with all given engines.
  • Visualization: SearchToolKit allows to visualize the search trees of all search algorithms.

Download

SearchToolKit comes as a toolkit for building search engines (STK), and as a tool for experimenting with engines and their components (ST).

STK (Mozart functor) ST (Mozart application) Source code

For information on Oz/Mozart functors, applications and sources, look at Mozart and Oz and Mozart functors and applications.

Documentation
Report on SearchToolKit (MS Word)
Paper on SearchToolKit

Using SearchToolKit The SearchToolKit can be used
  • as a toolkit (STK) to produce custom-made engines, and
  • as a tool (ST) for experimenting with engines and their extensions.
In order to use STK, you need to include import STK at 'http://www.comp.nus.edu.sg/~henz/projects/stk/stk.ozf' in your Oz functor declaration. Then, STK can be used to produce custom-made engines as follows. E= {STK.engineGenerator makeEngine( modules( 'Information': STK.stdLinks 'Memory Policy': STK.null 'Exploration': STK.depthFirst 'Interaction': STK.stdTracer 'Visualization': STK.stdDisplay 'Optimization': STK.branchBound ) $)}

In order to use ST, download st.oza and run it (using ozengine). You will get a selection window as shown below

To generate an engine, click on "Make Engine". If the engine specifies a GUI, for example if you use "Tracer" and "Standard Display", the GUI will pop up, which may look as follows. Problem script and optimization procedures can be loaded via URL. Example scripts are given in the demo directory.
Feedback

SearchToolKit is distributed free of charge, including the sources. Please let us know if you are making or wanting improvements, found interesting applications, encountered problems and limitations in using and extending the software.

Martin Henz