Go With the Flow: An Exploration of Distributed Network Flow for Robot Pathfinding

This project explores the use of network flow in robot swarm navigation. Swarm intelligence characterizes a field of robotics problem-solving that derives inspiration from insect social behavior to rethink efficient solutions. Typically these solutions take advantage of the distributed intelligence of a swarm, meaning that they arise from the collective reactions and interactions of every individual rather than from leader-follower dynamics. The key characteristic of a distributed algorithm is that it is very simple and is executed by every member of the swarm. One such algorithm that is used in graph theory is the Goldberg-Tarjan shortest-path network flow computation. We translated the pseudocode from the paper into a simulation that implemented a path-finding procedure for a robot swarm. In the simulation, the vertices in the network create viable paths for the robots using the Goldberg-Tarjan algorithm. We then created our own distributed, collision-free movement protocol that dictated how the robots would move down these paths. We tested this method for different measures of efficiency, such as travel duration and path length, by comparing against another, simpler routing method. Though the simpler method had a slightly better average performance, the network flow method was able to achieve shorter minimum navigation times. Ultimately we determined that our simulation creates an efficient obstacle-avoiding, collision-free path in polynomial time using purely local interactions between each member of the robot swarm