In robotics applications where large numbers of robots work together such as robotic swarms or fleets of warehouse robots organizing pallets, algorithms are needed to efficiently route each robot to its destination. Frequently, these systems are modeled as directed graph networks, with nodes indicating possible robot destinations and edges for viable paths not colliding with other robots. Any work the robot needs to do along the way, or work that needs to be performed by another human or machine on an item the robot is carrying can be represented as a wait time at particular nodes. When modeled this way, the problem of getting robots to reach their destination efficiently while performing necessary work along the way are remarkably similar to problems of efficiently routing messages, such as emails, internet packets, or telephone calls, which have been investigated in depth under the study of queueing theory.

Queueing theory provides the ability to calculate the performance of a system of queues based on a probability distribution of arrival events and the expected processing time for each node in the system. Specifically it provides equations for expected waiting time in each queue and overall processing time through the system as a whole. Typically, the random distribution of arrival events is modeled as a Poisson or exponential distribution, to provide both a mean level of traffic and bursts of traffic commonly seen in the phone and internet networks the equations were created to model, and because the time until the next arrival doesn't depend on how long it has been since the last arrival. While the normal distribution describes a wide range of natural processes, it is not frequently used in this case because its continuous, symmetric nature makes it less suitable for modeling time intervals or discrete counts. Geometric distributions are often used in queueing theory as the discrete equivalent of the exponential, when a precise integer count of messages is important, rather than the continuous time between events.

Backpressure Routing

The state of the art algorithm for optimal network throughput in a queueing network is backpressure routing. The core idea of backpressure routing is to maximize the throughput of the entire system by analogy to throughput in a system of water pipes, where the amount of water at any given node creates pressure pushing back on neighboring nodes in the system. Specifically, at any given node, the algorithm decides which outgoing link to use by identifying the link that leads to a neighboring node which has the least traffic already queued up there. By comparing current queue lengths across the entire system this creates a "pressure gradient" across that pushes traffic from congested areas toward less congested areas (or areas closer to the ultimate destination). For an optimal solution, this requires a centralized router, which will start at the end of the network and observe the current queue length of the final node, then work its way backwards, calculating a weight for each node equal to the difference between its queue length and the next node’s queue length plus the weight already calculated for the next node.

Virtual Stigmergy

Some downsides of backpressure routing include that it does not find optimal routes through the system when traffic is absent (because it is not an optimal pathing algorithm), and it requires knowledge of the current state of the entire system, which means it must be calculated by a centralized router rather than distributing the processing across the robot swarm. Virtual stigmergy is an alternative approach, originally as a path finding algorithm for robot swarms, based on the behavior of ants (stigmergy). In this approach, robots begin traversing the system randomly, and each robot tracks the path it chose and the time it takes. Then, at the end of its route, the robot adds value to each node visited in a virtual representation of the network based on the total time it took (higher values for quicker trips).

Each subsequent robot arriving at a node, instead of choosing its next destination randomly, will make a weighted random choice based on the stigmergy values of the available edges. Once enough robots have traversed the network, the stigmergy values will indicate the most efficient path through the system, including both the time to travel that path and any traffic encountered along the way. If the path becomes too backed up, where backpressure routing would avoid it, a few robots will still randomly select other paths, and, if they reach their destination quicker than robots waiting in the backed up queue, those other paths will become the new preferred path. However, this is still not quite as efficient in high traffic conditions as the centralized backpressure routing algorithm, because robots have to be delayed in order for the swarm to realize there is a problem with their preferred path.

Simulation

I have created a simulation in Unity to experiment with these different routing approaches and arrival probability distributions, which you can play around with below or at http://leif.sahyun.net/projects/routing_sim. It provides a simple directed graph network and robot spawners for geometric, exponential, and normal distributions of arrival rates. Checkboxes in the top left allow selecting between routing algorithms: backpressure routing, virtual stigmergy, or random (uniform stochastic). Tool buttons at the bottom left allow selecting a node to adjust its processing time or to add nodes and edges. To get started, add an edge to connect one of the probabilistic spawners to another node.