The Artificial Life and Adaptive Robotics Laboratory
Media Releases
Scientists at the Australian Defence Force Academy in Canberra are among researchers worldwide getting hints from nature for research into artificial life and complex adaptive systems.
This new but rapidly growing branch of artificial intelligence promises fast solutions to complex optimisation problems involving huge numbers of variables.
And this research is spawning some very intelligent computer programs by drawing on the behaviour of some of nature's most humble creatures.
Moulded through eons of natural selection, the behaviour of social insects, such as ants, bees and wasps, gives the impression of intelligence and self-organisation.
The ADFA team, led by Professor Charles Newton, head of computer science, is combining lessons from the insect world with insights from evolutionary theory to handle complex problems.
Optimisation problems abound in real life. Efficient methods of solving them would give companies an edge on their competitors, so the field is an area of active research, both in academe and the private sector.
British Telecom and big airline companies are among those tackling the most arcane artificial life questions in attempts to solve optimisation problems.
Examples include finding the shortest paths for expensive optical fibre cable networks, water mains and road networks, and optimising manufacturing processes and airline scheduling.
Optimisation is also important in bioinformatics, the hybrid discipline in which the computer meets biology.
Computers crunch masses of genetic data to find relationship between species. Engineers and architects also routinely face optimisation problems in their designs.
Previous approaches, including analytical ones, have yielded solutions, but the programs require supercomputers or years of computer processing time to run.
This renders them useless in the real world.
"For most real-life problems, the notion of getting to the absolute optimal solution is a dream," says team member Dr Hussein Abbass.
"These problems are so complex that, by the time you reach the solution, the problem has changed.
"We are looking for practical solutions that are less than optimal but good enough, and that can adapt quickly to changes in the environment."
The ADFA team is writing algorithms that can get to within about 5 per cent of absolute optimal solutions, but get there very fast.
Many optimisation problems reduce to the well-known travelling salesman problem, Newton says.
A salesman has to work out the shortest route between several cities, visiting each only once.
The problem is classified mathematically as a non-deterministic polynomial (or NP-hard) problem, because its difficulty increases exponentially with the number of variables, in this case, cities.
For a large number of cities, the problem is impossible to solve through trial and error, at least quickly.
For example, a salesman looking for the best route between just 10 cities would have to consider 3,628,800 possibilities.
"If you've got 50 cities, it's very complex," Newton says. "We're trying to come up with new search techniques to handle that."
Abbass says: "We are no longer trying to hard-wire computers with what we think intelligence is." He says nature is the perfect teacher when it comes to intelligence and complexity.
"Traditional approaches narrowed the definition of intelligence to a single human and ignored the notion of groups, interaction and adaptation."
The ADFA team is developing approaches pioneered a decade ago by Italian computer scientist Marco Dorigo based on ant behaviour.
Ants use their keen sense of smell to navigate.
They head out from the nest in search of food sources, choosing their routes at random.
The first to venture out leave a chemical pheromone trail, which affects the choices made by other ants.
Ants happening on the shortest route make more trips between the nest and food source, deepening the pheromone trail on that pathway, and attracting more to it.
The chemical trails marking the longest routes evaporate, and soon no ants will follow them.
The ants don't know it, but this approach delivers huge energy savings as they earn their living. "Ants are not very intelligent and they don't look organised, but when they work together in a large swarm they appear to be a very well-organised, intelligent group of agents," Newton says.
"We are trying to model this natural behaviour in solving large travelling salesman and other problems."
The computer replicates the insect behaviour by using "virtual ant" agents that leave trails of numbers, rather than pheromones. The trail that winds up with the highest numerical value is the shortest. The ADFA team has taken the technique a step further by marrying it to other insights drawn from nature.
Abbass is combining the ants algorithm with evolutionary computation, another branch of artificial intelligence, which mimics the harsh laws of Darwinian natural selection.
He has created software, called Evo-Ants, to solve optimisation problems. The algorithm, or set of problem-solving steps, combines the ant colony optimisation algorithm with genetic algorithms.
In the biological world, random mutations occur in genes. Some genetic mutations confer an advantage on the organism and spread throughout the population. Others are duds and go extinct from the gene pool.
In evolutionary computation, solutions are allowed to compete for survival.
The fittest pass on characteristics - partial solutions - to the next generation.
The solutions are subjected to random changes, analogous to genetic mutations.
The computer also simulates crossing over -- the biological process in which genes are shuffled in sperm and egg cells.
Through several generations of breeding, the best solutions evolve.
Abbass has used his Evo-Ant algorithm to find the optimal breeding strategy for a herd of dairy cattle. The aim was to maximise the progeny's productivity.
It is a classic optimisation problem that involves many variables, including the age and relatedness of the bulls and cows, and tough decisions on which animals to cull and which to breed.
Abbass's methodology, published in international journals, delivered an improvement compared with methods currently used on farms.
He is now turning his attention to the mating habits of the honeybee.
Queen bees mate with up to 20 drones while in flight, keeping sperm from each male in a sac called a spermatheca.
When she returns to the hive to lay, the queen chooses sperm at random to fertilise each egg.
While this choice is random, bee mating is not a pure lottery.
Mid-air seduction separates the men from the boys, as only males that can fly as fast as the queen get a chance to pass on their genes.
The ADFA team is introducing this mechanism into its swarm intelligence and evolutionary computations research.
Some algorithms are tested and selected for their fitness in solving a problem before being thrown into the computer gene pool, where Darwinian natural selection takes over.
While some cognitive science gurus are looking to the human brain for guidance in artificial intelligence, Newton is convinced the simplest creatures will point the way to the biggest developments in the field.
He points out that the Federal Government acknowledged the importance of complex systems research in January, when it made the field one of its four priority areas for Australian Research Council funding.