For some, mazes are a way to idle away a few spare minutes or a way to get lost among the hedges of country gardens. Yet maze solving has more serious uses, such as helping robots navigate or planning better routes for traffic. Now such applications could benefit from what two U.S. researchers say is the best maze-solving method yet—and it all rests on a simple electrical circuit and an unusual device called a memristor.
In the past, researchers have tried various ways to solve mazes. They include the slow but simple "random mouse" method, which involves taking a random left-or-right decision at every junction and wandering aimlessly until the exit is found, and mathematical algorithms that analyze each possible route. Last year, a group from Northwestern University in Evanston, Illinois, showed that even simple oil droplets could navigate mazes, so long as they were driven by chemicals placed at the end.
Yet all these methods suffer from what scientists call sequential computation: to find the best route, each must be tried in turn. This might be fine if the maze is simple, but as mazes get bigger and more complex, the time taken to solve them grows dramatically. A much faster method would be to try each route simultaneously—what is known as parallel computation.
Yuriy Pershin of the University of South Carolina, Columbia, and Massimiliano Di Ventra of the University of California, San Diego, claim to have developed the first parallel way to automatically solve mazes. Their method relies on an electronic device called a memristor which was first created in 2008 by a group at HP Labs in Palo Alto, California. Like its cousin the resistor, a memristor hinders the flow of electric current, but it also has an internal memory that can reveal how much current has flowed through it in the past.
Pershin and Di Ventra's scheme is to replicate an ordinary maze of vertical and horizontal pathways with a grid of many—hundreds or perhaps thousands—interconnected memristors. Where there are walls, Pershin and Di Ventra switch off the corresponding interconnection so that the memristor grid is left with pathways corresponding to those on the original maze. The same grid could be used again for different mazes by resetting the interconnections.
The trick comes when the researchers apply a voltage across the grid's entrance and exit. This prompts a current to flow, but it can only go along paths that have no dead ends—that is, it can take paths that lead only to the exit. What's more, it flows faster through the shortest routes because those contain the fewest memristors. Pershin and Di Ventra can then simply tap into the memory states of all the memristors, which have recorded the current levels through them, to discover which are the shortest routes.
The researchers have already successfully simulated their method on a computer, as they reported in a paper submitted to the arXiv preprint server last week. However, they say that the computer algorithms still technically proceed step by step and that for truly parallel solving, one would need to make the memristor grid for real. "But making this memristor processor requires fabrication procedures that do take some time," Di Ventra admits.
This problem is picked up by other scientists. Stanley Williams, one of the inventors of the memristor at HP Labs, thinks that although the idea is "very clever," the effort to make the device might make it less useful for practical situations. "It's as much work to construct the circuit as it is the maze, " he says.
But David Suits, a philosopher at the Rochester Institute of Technology in New York who has studied mazes, is more impressed. "It seems to me that [Pershin and Di Ventra] have a very plausible case," he says. "The only big problem which I can think of is that it seems that their circuit would have to be constructed for a particular size of maze; for a larger maze, they'd have to build a larger circuit. But it ought to be blazingly fast, compared to software methods." Once the circuit is built, anyway.