John Thornton's Research

Research

This page gives a general introduction to the various areas of my research. For more details see publications where papers are listed under the same headings: Hierarchical Temporal Memory, Constraint Satisfaction, Satisfiability, Temporal Reasoning and Robotics.

Hierarchical Temporal Memory: Currently I am working with Trevor Hine (from the School of Applied Psychology) and Michael Blumenstein on the development of a new computational memory structure modelled on the operation of the neocortex. We hold a IIIS research grant and are employing one part-time research assistant (Jolon Faichney). Jolon is working on a new temporal pooling algorithm that associates patterns (e.g. visual images) according to how connected they are in time (as well as considering how spatially similar they are) within a hierarchical, predictive memory structure.

This work is based on the ideas of Jeff Hawkins who recently proposed a hierarchical temporal memory model of neocortical function in his book On Intelligence (co-authored with Sandra Blakeslee). The model integrates a number of existing ideas about the hierarchical, predictive capacities of the neocortex and has resulted in the development of a prototype Numenta software architecture.

Constraint Satisfaction: A large proportion of my published research fits under the heading of constraint satisfaction. In turn, constraint satisfaction falls under the broader heading of artificial intelligence, as it deals with the general problem of representing and reasoning about the world. In particular, constraint satisfaction models the world using constraints and is concerned with searching for states of the world that best satisfy these constraints.

Setting aside the issue of how best to model the world, my work has concentrated on how best to solve constraint satisfaction problems once they have been formulated. This has led me into a detailed investigation of algorithms for solving difficult (i.e. NP-complete) problems, and, in particular, local search techniques that solve problems by manipulating constraint weights.

Part of this work has looked at the problem of solving over-constrained problems with hard (mandatory) and soft constraints. This has resulted in the development of several new algorithms that dynamically alter the relative importance of the hard constraints and combine constraint weighting with other local search heuristics.

Satisfiability: The satisfiability (SAT) problem represents an alternative way of representing constraint satisfaction problems. As all NP-complete problems can be transformed to a satisfiability problem, the SAT domain has attracted considerable research interest. In particular, much energy has been devoted to developing fast and efficient SAT solving algorithms, and many benchmark problems exist on which to compare performance of different approaches. Consequently, I have generally also used the SAT domain to test the performance of my own algorithms.

More recently, as part of the CSP group research, we have been looking at building SAT solvers that exactly replicate the behaviour of a binary CSP solver, thereby removing the need to test our algorithms in multiple domains. In addition we are looking at recovering the underlying problem structure that can be lost in a SAT problem representation, and at developing a SAT problem generator that can produce controlled degrees of useful structure.

Temporal Reasoning: As a result of related interest in our research group, we looked at developing a local search approach to solving temporal reasoning problems that are traditionally solved using complete techniques such as path consistency combined with backtracking. By reformulating the temporal constraint satisfaction problem (TCSP) as a standard CSP that considers the relative ordering of the end-points of each time interval, we were able to produce a promising local search algorithm that exploits the special features of interval algebra.

In our current work we are looking at extending this technique to the more challenging domain of over-constrained temporal reasoning problems, where complete search has more difficulty as it cannot necessarily backtrack on failure.

Robotics: My work in robotics began in 2000 with the purchase of a set of Yujin MiroSot robots which we then entered into the 2000 FIRA World Cup in Rockhampton. As our team (the RoboCoasters) were fresh out of the box it was no great surprise that we lost all three of our matches (although we did score one goal at our opponents end). Here is a picture of the team - to get an idea of scale each robot fits within a 7.5cm dimensioned cube:

Our next appearance at the 2001 FIRA World Cup in Beijing produced our first victory and at the 2002 FIRA World Cup in Korea we qualified in the last 8 teams (out of 32) and were narrowly beaten 3-2 in extra time by the University of Dortmund (who went on to be runners up in the final).

It was in the 2002 competition that we first entered a 5-a-side team using our shape recognition vision system. Unlike other teams that use different coloured patches to recognise individual players, we concentrated on distinguishing between five shapes. This proved to be a more reliable solution and partly accounts for our 2002 success.

From 2002 to 2003, I was involved with Vladmir Estivill-Castro and Griffith University's Mobile Robotics Group, who work with a team of Sony Aibo robot dogs. The dogs provide a more interesting research challenge as they are fully autonomous, having on-board vision and processing, with infra-red, gyroscopic and touch pad sensors, and the capability for wireless communication:

Currently I am working on the more general problem of perception. I have two students working with an ER1 robot - this is a mobile platform that carries a laptop on board (see below). Now we can avoid buying a new robot every year - instead we can upgrade the processor and hardware components on a piece by piece basis. Our current configuration sports a stereo camera system with independent pan-tilt units. We are exploring computational models of visual perception inspired by the work of the ecological psychologist James Gibson and combining this with more recent work that models the operation of the human neo-cortex.