After completing my honours research in nurse rostering I continued to work on algorithms designed to simulate aspects of human intelligence. Not that I thought these algorithms were actually intelligent, it was more a case of showing that something we think requires intelligence (like playing chess) is finally only a matter of brute calculation. This interest in intelligence led me to enrol in a PhD in artificial intelligence, specialising in the area of constraint satisfaction. This was a natural evolution from my honours research, as the nurse rostering problem is itself an example of a constraint satisfaction problem.

In my PhD I started to refine the local search approach I had used in my honours work. This approach takes a rough and ready answer to a problem and then improves it by making small changes until there is no single change that could make the answer any better. The difficulty is that for many interesting problems this leads the algorithm into a local minimum, i.e. a place where no single change can improve the answer, but where a change that initially makes things worse could still lead to an even better solution. One way out of a local minimum is to randomly restart the algorithm as soon as it gets stuck and let it improve that new random starting place until it reaches another local minimum, and to keep doing this until a perfect (or at least a good enough) answer is found. Alternatively you can avoid a complete restart by every now and then taking a random move that makes things a bit worse, and then continuing to try and make improvements. The unsatisfying aspect of these algorithms, even though they can be effective, is that they do not learn from their mistakes, because they have no memory.

I remember my first significant breakthrough was to see that an algorithm could remember the past by penalising the constraints it could not satisfy in a local mimimum. For example, let’s say a search gets stuck in a roster where there are not enough nurses on a Thursday morning shift. That means that every single possibility of moving a nurse from another shift in order to fix the Thursday shift makes the solution just as bad or even worse. My answer here was to make getting enough nurses on a Thursday morning more important than for any other single shift . In this way the algorithm learns that Thursday morning is hard to fill by making it more costly. This changes the cost space of the problem so that other alternative solutions (such as one without enough nurses on Tuesday afternoon) will now cost less than the Thursday morning shortage. But, of course, we can now equally become stuck in the Tuesday afternoon shortage. And so we increase the cost of the Tuesday afternoon shift, and try again, continuing like this, adding weights to the constraints we cannot satisfy, until we find a solution that satisifies all the constraints (or until we give up and get a nurse from another ward).

It turned out that this constraint weighting approach was far better than the other randomised algorithms I had been using. This entire weighting idea struck me as if from nowhere one sunny afternoon in 1996 and I had it coded up in a matter of an hour or so. When I discovered it actually worked, I thought my research career was about to take off. I immediately wrote a paper and submitted it to one of the world’s great artificial intelligence conferences (AAAI) only to be told that someone else (Paul Morris) had had the same idea three years earlier. But still, I was underway.

The papers below tell the rest of this story. Finally I developed a constraint weighting algorithm that was worth publishing in AAAI, called PAWS (see AAAI 2004). By then I was no longer working on nurse rostering, but on the universal computational form of the satisfiability (SAT) problem – in which many different kinds of real world scenarios can be represented and then solved by super-fast algorithms specially optimised for the SAT formalism. For a while PAWS was the state-of-the-art in this area, but it was soon superceded by a series of other algorithms, some of which were developed by my own PhD students. The most notable of these was presented in an IJCAI 2007 paper entitled Building Structure into Local Search for SAT (which went on to gain a prestigious IJCAI distinguished paper award). Most of the rest of my work in this area has involved applying and developing the constraint weighting approach to other problem domains, including over-constrained problems (e.g. AAAI 2014), temporal reasoning problems (see the Temporal and Probabilistic Reasoning page), developing more sophisticated ways of weighting different classes of constraints (e.g. AI 2002), and adapting the way constraints are weighted according to the way the algorithm is behaving during the search (e.g. PRICAI 2008). I also branched out and worked with Stuart Bain on algorithms that automatically evolve new constraint satisfaction algorithms (see the Robotics and Evolutionary Computing page).

Finally, I should mention that although I was involved the development of the key ideas and concepts presented in the papers below, as my academic career continued, most of the hard work of coding and experimenting was increasingly taken over by the PhD students whom I was fortunate enough to be supervising. Here, as a rule of thumb, you can tell who did the most work on a particular paper by the order in which the authors are listed. Of these authors, I was a primary PhD supervisor for Stuart Bain, Valnir Ferreira Jnr., Raouf Ishtaiwi and Duc Pham Nghia, and secondary PhD supervisor for Matthew Beaumont and Lingzhong Zhou.

And, as is customary, if we think of these relationships as a kind of family tree, then the grandfather here is my own PhD supervisor, Professor Abdul Sattar, who has so diligently guided and assisted me throughout my career, and remains a dear friend and brother to this day.