Our recent paper use Google’s PageRank algorithm to evaluate and optimize the behavior of swarms in a computationally efficient way, aimed at making swarms that are scalable, flexible, and robust.
The PageRank algorithm as a method to optimize swarm behavior through local analysis
M. Coppola, J. Guo, E. Gill, G. C. H. E. de Croon
Swarm Intelligence, 2019
The original paper is open access and can be found at: link.springer.com/article/10.1007/s11721-019-00172-z
Swarming
How can we enable swarms of drones, each making their own decisions, to coordinate toward a grander goal such as organized exploration or construction? Just as with many other modern developments, machine learning plays an important role. But machine learning needs data, and in this case, “data” often means computationally expensive simulations where robots try out different behaviors, eventually learning how to fulfill a task. This causes several scalability problems when dealing with larger swarms or complex tasks.
The PageRank algorithm
Our latest research provides a novel solution: to use Google’s famous PageRank algorithm in order to evaluate a behavior without any simulation. The PageRank algorithm was developed by the founders of Google back in the late ‘90s. Its objective was to sort through webpages and find the popular ones. This was done by evaluating how likely it would be for a web surfer to arrive at a webpage when clicking hyperlinks. This algorithm gave Google a competitive advantage.
Bringing the algorithm to swarms
Just as a web surfer surfs the web, we model the experiences of a robot “navigating” in the swarm. The states that the robot can be in become like websites to visit, and the actions that the robot can take become hyperlinks. Then, we use a PageRank based approach to evaluate how likely the robot is to end up in certain states, and learn behaviors that cause the robot to visit states that are beneficial to the swarm’s goal. This is a computationally efficient method that requires no simulation. Because it only analyzes the behavior of a single robot, rather than the whole swarm, it allows to develop complex behaviors for larger swarms without the same scalability issues.