Game Theory and Markets as Foundation for Swarm Intelligence
by amcnicoll
Over the last several years, the concept of networks has figured more and more heavily into the control of autonomous devices. By tapping into existing networks such as the Internet or GPS, a variety of devices are able to better perform their job. However, there is also quite a bit of incentive to have such devices form isolated networks where each device is a node or even participant in a game.
This concept most commonly appears within the context of swarm robotics, where dozens or even hundreds of identical robots share information to accomplish a mission. Such missions could be anything; for example, there is interest in developing a swarm to automatically repair reefs off the coast of Scotland. A simple example we can work with here is a search-and-rescue mission. This example is of particular interest, since researchers have proposed that a swarm intelligence based on game theory could be an effective alternative to simple divide-and-conquer approaches.
Imagine you have dropped a small screw in the middle of your shop floor. You deploy your swarm of screw-seeking robots, and provide them with a map of probability map of where you believe the screw to have tumbled. To find the screw, all robots play a game with each other, where the goal is to find the screw. The expected payoff values for a strategy (search location) is a complex “utility function”, where probability of successfully finding the screw for one’s self contributes to utility, and distance to the search location and number of robots already searching this location detract from utility. If a robot has a dominant strategy (ie, one which promises the best chance of finding the screw regardless of what other robots play), it will follow through with it.
An oversimplified way of considering the same problem is to conceive of it as a market matching problem, where sellers correspond to search location, buyers correspond to robots, price corresponds to distance, and value corresponds to expected payoff. Of course, such an algorithm would have to allow for multiple robots matching to the same seller when there are more robots than search locations; nevertheless, the end result will still be that each robot will look in the most promising location given knowledge of what the other robots are doing. These approaches to swarm intelligence can prove to be much more efficient than simple scans, especially given search spaces as large as coral reefs.
To learn more about the nitty-gritty of game theory in swarm seeking problems, check out this paper and others like it.