Biologically inspired computing is an emerging field, somewhere between field biology, software engineering, and sci-fi. Among other topics, it delves into how the living world processes information: things like how slime mold can solve a maze, or the way ants vote on the quality of a new nest site, or what kind of things will go viral on a given day on Facebook. Ants, in particular, are really good at quorum sensing, or estimating population density in real time. Now a team of researchers from MIT’s Computer Science and Artificial Intelligence Laboratory has used the way ants do quorum sensing to build new algorithms modeling network connectivity on the fly .
Ants use a more-or-less random walk procedure when they’re wandering around en masse to find a new nest site. They converge rapidly on a site attractive enough to catch the attention of lots of ants, and in so doing, maintain a pretty good running estimate of the quality of the site . Now, you wouldn’t think of a random walk process as efficient, but here’s how it works: Think of the whole network diagram as a graph, and each ant as a node in the graph. If there are only a couple of possible paths away from any point on the graph, you can traverse the same few points over and over, costing time. But if a graph is well connected — for example, if a given user has a lot of connections in their social network of choice — a random walk process could converge on an accurate measure of population density nearly as fast as it’s even theoretically possible to do. This works for things like swarms, hives, and schooling behavior. But these researchers found that it can also work for social networks, robot swarms, and other ad hoc networks like sensor grids.
While the report focused on a single “explorer,” such as a single ant or sensor, the team noted that many explorers could pool their observations and converge even faster on an accurate estimation of population density. “If they were robots instead of ants, they could get gains by talking to each other and saying, ‘Oh, this is my estimate,’” said Cameron Musco, coauthor of the report.
“It’s intuitive that if a bunch of people are randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density,” said Musco. “What we’re doing is giving a rigorous analysis behind that intuition, and also saying that the estimate is a very good estimate, rather than some coarse estimate. As a function of time, it gets more and more accurate, and it goes nearly as fast as you would expect you could ever do.”
There was one curious problem with the algorithm the team used in their proof, though. Random walk procedures have a comparatively large likelihood of oversampling. (That’s one of the reasons they’re not usually efficient.) Trying to correct for oversampling by filtering out the oversampled data, though, seemed to make the algorithm behave worse, not better.
Musco said that if you’re randomly walking around a grid, you’re not going to bump into everybody, because you’re not going to cross the whole grid. “So there’s somebody on the far side of the grid that I have pretty much a zero percent chance of bumping into. But while I’ll bump into those guys less, I’ll bump into local guys more. I need to count all my interactions with the local guys to make up for the fact that there are these faraway guys that I’m never going to bump into. It sort of perfectly balances out.” Musco and colleagues will present their report at the Association for Computing Machinery’s Symposium on Principles of Distributed Computing conference later this month.