David A J Lee

Research

Distributed Constraint Satisfaction

Constraint Satisfaction Problems are solved by algorithms assigning values (from a domain) to variables in the problem so that all constraints are satisfied. In Distributed Constraint Satisfaction Problems, variables are represented by agents who have only a partial understanding of the problem (their understanding is limited to the variables they represent and the constraints that those variables are involved in). Distributed problems are important when information cannot be shared either because there is too much information or because of privacy concerns. Existing algorithms for Distributed Constraint Satisfaction can be categorised as backtracking and local search algorithms. The former, whilst able to guarantee completeness, are often too slow for practical use whilst the later are often able to converge to a solution quicker but may not solve all problems (i.e. they are incomplete). In a summer scholarship in 2005 (supervised by Dr. Ines Arana & Dr. Hatem Ahriz), I compared the Distributed Breakout Algorithm with the Distributed Stochastic Algorithm on randomly-generated problems and scheduling problems. The tentative conclusions suggested that the Distributed Breakout Algorithm was more suited to randomly-generated problems whilst the Distributed Stochastic Algorithm performed better on scheduling problems. A prize was awarded for the research undertaken during this project. In addition to my research, I developed an experimental workbench written in Java to compare Distributed Constraint Satisfaction algorithms. In my doctoral research (supervised by Dr. Ines Arana, Dr. Hatem Ahriz & Dr. Kit-Ying Hui), I investigated and developed hybrid algorithms for Distributed Constraint Satisfaction, combining the convergence abilities of local search with the completeness of backtracking. This has led to the development of new algorithms for Distributed Constraint Satisfaction including PenDHyb, Multi-Hyb and Multi-HDCS. I also continued to develop the experimental workbench (SEICOSSA – A Smart Experimental Interface for Constraints) which I started to develop during my initial scholarship.

Information Retrieval & Relevance Profiling

Before starting my doctoral projects, I was involved in the Information Retrieval research field. Together with Professor David J. Harper I sought answers to the question how effective is relevance profiling in retrieving relevant pages of a book as defined by the book’s own index? This project sought to measure this effectiveness through an investigation of a number of weighting functions on the within-document retrieval tool, ProfileSkim. Conclusions from the project were presented at the Ninth Australasian Document Computing Symposium.