Physically routing robots in a multi-robot network: Flexibility through a three-dimensional matching graph

Many multi-robot scenarios involve navigation of a set of networked robots through a constrained environment to achieve coverage, maintain a predefined shape, sense at predefined locations, or to satisfy some other distance-defined property. When new robots and tasks are added to a network of already deployed interchangeable robots, a trade-off arises in seeking to minimize cost to execute the tasks and the level of disruption to the system. This paper examines a navigation-oriented variant of this problem in which robots are physically routed through an existing network. We propose a parametrizable method to tune emphasis between minimizing global travel cost (or energy, or distance), minimizing interruption (i.e. obtaining the fewest number of robot reassignments), reducing travel distance per robot, and completing all operations as soon as possible. Since these are related optimization criteria, a single parameter provides sufficient flexibility to balance between them.

Paths through the network are computed via a task-allocation formulation in which destination locations of newly deployed robots are added as tasks to an existing allocation. We adapt the graph matching variant of the Hungarian Algorithm—originally designed to solve the optimal assignment problem in complete bipartite graphs—to construct routing paths in sparse networks. We do this by constructing a three-dimensional graph that incorporates logical aspects of the Hungarian bipartite graph, and spatial elements of the Euclidean graph. The approach has several useful features including being particularly effective at generating multiple simultaneous, non-interfering paths. When new agent–task pairs are inserted, the assignment is globally reallocated in an incremental fashion so that it requires only linear time when the robots’ traversal options have bounded degree. The algorithm is studied systematically in simulation and also validated with physical robots.