Social network coordination and graph routing

Abstract

Abstract We consider the problem of coordinating robots moving on a network. Each robot is autonomous and needs to visit various sites of the network at various times. The sequence of destinations for each robot changes dynamically and unpredictably. Recently, Onn and Tennenholtz showed that the problem can be solved by introducing a social law on the network, which, once obeyed by all robots, enables each to move to any desired destination without collisions and regardless of the actions of other robots, needing neither central coordination nor mutual communication. This social law can be derived from a suitably defined routing of the graph underlying the network. Here, we study the complexity of routing. We provide an effective characterization of 2‐routable graphs, and by establishing a correspondence between hypergraph coloring and graph routing, we show that computing or approximating an optimal routing is generally hard. We also discuss routing in planar graphs, which often underlie robotic networks and show that the correspondence between coloring and routing together with the Four Color Theorem guarantee the existence of small and effectively computable routings in bipartite planar graphs of small radius. The complexity of routing arbitrary planar graphs remains open. © 2002 Wiley Periodicals, Inc.