Every Thursday, Laboratory Equipment features a Scientist of the Week, chosen from the science industry’s latest headlines. This week’s scientist is Graham Kendall from the Univ. of Nottingham. He and Phil Hingston solved the famous knight’s tour chess problem with ants.
Q: What made you interested in attempting to solve the knight’s tour problem with ants?
A: Ant algorithms were introduced a few years before I started my PhD so they seemed worthy of investigation. I was also fascinated by being able to write a computer program that simulated ants, which were then able to solve problems that were — seemingly — totally unrelated to ants.
If you try to try and solve the knight’s tour manually, using a knight and a chess board, you might struggle to find just one solution (from among the trillions that actually exist). It is difficult to believe that an ant algorithm would do any better. Phil Hingston and I were anxious to see if this was the case. We were fortunate enough to discover that ants are actually quite good at solving this problem.
The other nice thing about using games as an experimental test bed is that the rules are fixed and unambiguous. This is often not the case when tackling real world problems, when it is often difficult — if not impossible — to agree on what the problem is, let alone solve it to everybody’s satisfaction.
Q: What are the future implications of your research and findings?
A: The knight’s tour is one of those interesting problems that, to me anyway, has no obvious application. But the history of science is littered with these examples — especially in mathematics. Some interesting, but apparently useless problem, is investigated and it is only later, perhaps hundreds of years later, that somebody else finds that this previous result is essential for the current research they are doing
Of course, the knight’s tour is related to problems such as the travelling salesman problem (TSP), which underpins many real world applications. Perhaps, insights gained from the knight’s tour will assist researchers who are tackling the TSP.
Q: What was the most surprising thing you found in your research?
A: Despite having a lot of faith in ant algorithms, I was a little concerned that it would not work. The fact that the ants found any tours is amazing. The fact that they found so many is both surprising and very pleasing.
Q: What is the take home message of your research and results?
A: Don’t be afraid to try something. One of the good things about being an academic is that you are able to carry out research into things that interest you. In an industrial setting you are usually given a specific task, which you might not find interesting, but you don’t really have a choice about the type of problems you work on.
Q: What new technologies did you use in your lab during your research?
A: This was the first time that ant algorithms had been used for the knight’s tour. Other researchers had used other methodologies, such as genetic algorithms (which we mention in the papers) but nobody had tried ant algorithms.
Apart from the need to understand ant algorithms, we did not require anything else of a specialist nature. We just needed a PC, a programming language and some time to develop and test.
Q: What is next for you and your research?
A: The knight’s tour forms part of my research portfolio that investigates various games.
My main research, however, is focused on heuristics, meta-heuristics and hyper-heuristics. These methodologies — which include ant algorithms and genetic algorithms — are used to tackle problems that might otherwise take millions, or even billions, of years to solve.
I use these methodologies for problems that are found in the real world. This includes vehicle routing, personnel scheduling, supermarket shelf packing and cutting stock; and many more besides.
As my main research interest is in operations research. If you ever say, “We need to minimize something,” (costs, waste, staff etc.), or, “maximize something” (profit, use of space etc.) then those are the problems that I like to think that I can help solve.