Advanced Project: Search Tree Maps

Supervisors: Guido Tack (email) and Chris Mears (email)

The goal of this project is to develop and explore novel visualisation techniques for constraint solvers. Tree search, in several variants, is the dominating technique for solving hard combinatorial problems. We want to visualise search trees in a novel way, using treemaps, in order to understand and improve search heuristics and performance. The project involves developing a visualisation tool that is connected to the constraint solvers available from the MiniZinc project.

Treemaps

Treemaps are compact visual representations of hierarchical data. They display tree data using nested rectangles, encoding various extra information into the size and colour of the rectangles.

This map (from the Wikipedia article on treemaps) visualises soft drink preferences in a group of people:

The following two maps use a non-rectangular layout. They are taken from a website on the history of treemaps:

Search Trees

Tree search is a fundamental part of many AI algorithms. Constraint-based solvers for combinatorial problems are typically based on variants of Depth-first Search. Here is a classic visualisation of a search tree for the Eight-Queens-Puzzle:

8 queens puzzle search tree

Red leaf nodes represent dead-ends in the search, the green diamond is a solution of the problem, and inner blue nodes stand for the choices that the solver made to explore the search space.

Project Goals

You will explore existing algorithms for generating treemaps, as well as existing open-source implementations. You will then develop a tool that can visualise the search trees produced by MiniZinc constraint solvers. The project involves experimentation with different parameters for the visualisation, representing different characteristics of the search trees such as time spent at each node, quality of each node, and other internal measures of the constraint solver.


Guido Tack, Wed Aug 08 19:20:13 2012