PaperlayerView exact revision on arXiv

Source-linked AI summary

A Distributed Version of the Hungarian Method for Multi-Robot Assignment

Smriti Chopra, Giuseppe Notarstefano, Matthew Rice, Magnus Egerstedt

arXiv:1805.08712v1eess.SY

TL;DR

The paper addresses how multi-robot teams can solve assignment problems without a centralized authority or shared memory. It distributes the Hungarian Method over local peer-to-peer communication, proves finite-time convergence to a common optimal assignment, and demonstrates iterative use for dynamic spatio-temporal routing and orchestral-floor interaction.

  • Problem

    Multi-robot assignment requires a common optimal allocation despite limited global knowledge, limited communication, and the absence of feasible centralized infrastructure.

  • Method

    The paper distributes the Hungarian Method by having robots run local sub-routines and exchange solution estimates with neighboring robots.

  • Results

    The algorithm makes all robots converge in finite time to a common optimal assignment under the stated communication model.

  • Takeaways & Limitations

    The distributed method supports cooperative LSAP solving and iterative online routing in a dynamic multi-robot orchestral-floor application.

Abstract

from arXiv · show

In this paper, we propose a distributed version of the Hungarian Method to solve the well known assignment problem. In the context of multi-robot applications, all robots cooperatively compute a common assignment that optimizes a given global criterion (e.g. the total distance traveled) within a finite set of local computations and communications over a peer-to-peer network. As a motivating application, we consider a class of multi-robot routing problems with "spatio-temporal" constraints, i.e. spatial targets that require servicing at particular time instants. As a means of demonstrating the theory developed in this paper, the robots cooperatively find online, suboptimal routes by applying an iterative version of the proposed algorithm, in a distributed and dynamic setting. As a concrete experimental test-bed, we provide an interactive "multi-robot orchestral" framework in which a team of robots cooperatively plays a piece of music on a so-called orchestral floor.

I. INTRODUCTION

The paper redesigns the Hungarian Method for distributed multi-robot assignment, allowing robots to compute a common optimal LSAP assignment through local computation and neighbor communication without centralized infrastructure. It also extends the method to distributed, dynamic spatio-temporal routing and a multi-robot orchestral test-bed.

  • Distributed assignment lets robots coordinate one-to-one task matching while avoiding the costly global computation and information requirements of centralized infrastructure.
  • The paper redesigns the Hungarian Method so anonymous robots exchange information with single-hop neighbors and execute identical local routines.
  • The proposed algorithm enables robots to cooperatively compute optimal LSAP assignments without a coordinator or shared memory.
  • O(r^3) synchronous communication rounds suffice for convergence to a common optimal assignment, while simulations show much faster average convergence in practice.
  • The algorithm is applied iteratively to online, suboptimal spatio-temporal routes in a distributed multi-robot orchestral framework.

B. The Hungarian Method

The centralized Hungarian Method solves the LSAP through feasible vertex labels, equality-subgraph matchings, and repeated two-step updates. Its feasibility-preserving updates increase the matching toward an optimal perfect matching.

  • The Hungarian Method is a primal-dual algorithm whose optimality basis is the Kuhn-Munkres theorem.
  • Initialization: Initialization chooses an arbitrary feasible labeling, constructs equality-subgraph edges, and finds a maximum-cardinality matching with a corresponding minimum vertex cover.
  • Two-step iteration: Each iteration selects candidate edges between uncovered vertices using minimum slack, then updates the labeling by the smallest candidate slack.
  • Two-step iteration: Every two-step iteration preserves labeling feasibility and either increases matching size or changes the vertex-cover structure.
  • Convergence: The method reaches an optimal perfect matching after O(r^2) two-step iterations, with O(r^4) total running time in the described implementation.

III. DISTRIBUTED PROBLEM SETUP

The distributed problem gives each robot local assignment costs and connects robots through a time-varying directed communication graph. All robots must converge to one common minimum-cost assignment despite local knowledge, dynamic communication, and possible degeneracy.

  • Each robot knows the robot and target sets plus its own costs for assignable targets, while the communication graph links robots over time.
  • The baseline communication assumption requires the time-varying directed graph to be strongly connected at every time instant.
  • The assignment graph models robot-target costs, whereas the communication graph models peer-to-peer information exchange among robots.
  • The setup can be relaxed to joint strong connectivity over a bounded time period, supporting asynchronous implementations.
  • Because degenerate assignments may have multiple minimum-cost solutions, robots must agree on the same optimal assignment rather than merely achieve equal cost.
  • The distributed objective is for all robots to converge to a common assignment that is optimal for the centralized assignment problem.

IV. A DISTRIBUTED VERSION OF THE HUNGARIAN METHOD

The Distributed-Hungarian algorithm adapts the Hungarian Method so robots exchange local states and cooperatively update a shared assignment through repeated communication rounds. Each robot maintains sparse graph information, labels, counters, and candidate edges while using local computations to advance the distributed process.

  • The Distributed-Hungarian algorithm solves the Distributed Assignment Problem by adapting the Hungarian Method to robots with local information and communication.The method is designed for the distributed setting described in the paper.
  • Each robot state contains a lean weighted bipartite graph, a vertex labeling function, and a counter value.The lean graph represents the robot’s sparse graph information, while the label and counter support algorithm coordination.
  • At each synchronous time instant, every robot sends its state to outgoing neighbors and computes a new state after receiving incoming messages.Each time instant is an iteration or communication round of the algorithm.
  • Before execution, each robot creates original weighted bipartite-graph information and initializes its state with a minimum-weight incident edge.The initialization uses the robot’s original information and selects an edge of minimum weight.
  • During each round, robots build a latest temporary graph from stored neighbor states and use the Local Hungarian function with original information to compute new states.The temporary graph is formed from the robot’s own state and the most recent incoming states.

A. Build Latest Graph

Build Latest Graph combines the most up-to-date robot states into a temporary sparse state. It selects labels and equality edges from a leading state while combining candidate edges across robots sharing the highest counter value.

  • Build Latest Graph retains information from robots with the highest counter value.The resulting temporary state contains only the most-updated information according to the counters.
  • When the highest counter is positive, the function selects one leading robot’s counter, labels, and equality edges.Any robot among those tied for the highest counter may supply these fields.
  • Candidate edges are combined across all robots tied for the highest counter, producing a lean graph with equality and candidate edge sets.The resulting graph is Glean = (V, (Ey, Ecand), wlean).
  • If all counters are −1, the function sets the counter to −1, clears candidate edges, and combines equality-subgraph edges.This is the special initialization case for Build Latest Graph.
  • The resulting labels are globally feasible for the centralized graph, while the robot’s state remains a sparse version of the centralized Hungarian state.The paper identifies this relationship as the connection between the distributed and centralized procedures.

B. Local Hungarian

Local Hungarian applies the Hungarian Method to a temporary lean graph, adding candidate edges from a robot’s original information when needed. It then updates labels, matching, vertex cover, equality edges, and counters before returning the robot’s new state.

  • Local Hungarian computes a maximum-cardinality matching and corresponding minimum vertex cover on the temporary equality graph.These are computed from the equality edges and vertex labeling in the temporary state.
  • If the matching is not perfect, an uncovered robot contributes one candidate edge selected from its original information.The Get Best Edge sub-function chooses the candidate edge only when the robot is uncovered.
  • When an uncovered robot lacks a candidate edge, Local Hungarian continues with the Hungarian Method’s label, equality-subgraph, matching, and vertex-cover updates.This path increments the counter and resets the candidate edge using the robot’s original information when available.
  • The function prunes equality-subgraph edges through Reduce Edge Set and returns a new lean graph together with updated labels and counter.The returned state includes the possibly updated candidate-edge set.
  • The Distributed-Hungarian algorithm repeatedly executes these state updates while its stopping criterion remains unsatisfied.The formal algorithm wraps message reception, parsing, and local computation inside the iteration loop.

V. CONVERGENCE ANALYSIS

The Distributed-Hungarian algorithm propagates locally computed graph states so robots converge to a common optimal assignment in finite time. Under the stated communication assumptions, convergence requires O(r^3) communication rounds, while perfect-match information can stop propagating after r−1 rounds.

  • Distributed state evolution: Equal counter values imply identical feasible vertex labelings, equality subgraphs, and maximal matchings across robots.The uniqueness of the labeling and equality-edge set at each counter value yields identical maximal matchings.
  • Distributed state evolution: The algorithm builds increasingly updated equality subgraphs and candidate-edge sets from locally received states, preserving a common labeling and matching structure for robots with equal counters.Robots merge information from highest-counter neighbors and apply the same candidate-edge selection process as the centralized Hungarian Method.
  • Optimality and convergence: Finite counter growth leads all robots to the same counter value and a common perfect matching, which is optimal by the Kuhn-Munkres Theorem.A perfect matching stops counter increases; if the shared matching were not perfect, the convergence argument would be contradicted.
  • Optimality and convergence: Within at most r−1 communication rounds, information sent by one robot reaches every other robot in the strongly connected dynamic network.This information-dispersion property supports a stopping rule after a robot finds a perfect matching.

A. Simulation Experiments

Simulation experiments evaluate convergence and computational load for Distributed-Hungarian instances with varying team sizes. The experiments compare observed convergence behavior with the theoretical worst-case bound and with centralized Hungarian computation.

  • Experimental setup: Simulations varied the number of robots from 5 to 160 and averaged results over 20 runs for each problem size.The experiments were implemented in MATLAB on a PC with an Intel Quad Core i5 CPU and 16GB RAM.
  • Experimental setup: The experiments used a synchronous implementation with dynamic incoming and outgoing communication edges at each time instant.
  • Results: Observed average convergence iterations were well under the O(r^3) worst-case bound.Figure 9a reports the average number of iterations required for convergence across the tested problem instances.
  • Results: Per-robot computational load was evaluated by averaging the slowest iteration across robots and comparing it with the corresponding centralized Hungarian computation.The comparison is shown in Figure 9b.

VI. A MOTIVATING APPLICATION: DYNAMIC SPATIO-TEMPORAL MULTI-ROBOT ROUTING

The paper applies its distributed assignment algorithm to dynamic spatio-temporal routing, where robots service skilled targets at specified times. It illustrates this setting through an interactive orchestral-floor framework in which users can modify music while robots adapt their routes.

  • Spatio-temporal routing assigns robots to targets that require service at specific time instants and have associated skill requirements.
  • The robots determine routes online for successive spatio-temporal requests by repeatedly applying the Distributed-Hungarian algorithm.
  • The iterative scheme solves assignments between consecutive time instants, providing a framework for dynamic distributed routing.
  • On the Robot Orchestral Floor, planar positions correspond to notes from instruments such as piano, guitar, and drums, turning music into spatio-temporal requests.
  • A conductor-like user can modify the music in real time through a tablet, while robots adapt their routes to incorporate the changes.

A. Overview of the Methodology

The methodology repeatedly formulates routing between successive time instants as unbalanced assignment problems and solves them with the Distributed-Hungarian algorithm while robots execute previously planned route segments. Dynamic updates trigger recalculation from a selected future time onward.

  • Distributed Aspect: The distributed aspect determines routes by iteratively solving assignments between successive time instants using the Distributed-Hungarian algorithm.
  • Distributed Aspect: Each assignment is an unbalanced Linear Sum Assignment Problem in which binary variables map robots to timed positions.
  • Distributed Aspect: The assignment constraints require every timed position to receive one robot, each robot to receive at most one position, and assigned robots to possess compatible skills.
  • Distributed Aspect: Robots solve assignments between future consecutive time instants while simultaneously executing routes already determined.
  • Dynamic Aspect: When a Score modification arrives, robots retain routes until a selected time instant and recalculate routes from that point onward.
  • Dynamic Aspect: The interface delays modifications until after a conservative duration covering distributed-assignment computation and travel to assigned positions.

B. The Multi-Robot Orchestra

The paper implements the routing framework as a multi-robot orchestra using simulated and hardware orchestral floors. A tablet broadcasts Scores and their updates while robots execute musical routes in real time under stated feasibility assumptions.

  • The simulated Robot Orchestral Floor includes piano, guitar, and drum sounds, with a graphical interface for creating and modifying Scores.
  • The heterogeneous Score for “The Final Countdown” is divided into single-instrument sub-scores, including separate piano lead, bass, and harmony parts.
  • After the user selects the available robot count and broadcasts the initial Score, robots determine and execute routes in real time while receiving later changes.
  • The musical demonstration does not consider velocity constraints because the user lacks the robot-position information needed to assess them.
  • The orchestra is implemented in both simulation and hardware using miniature Khepera III robots, motion capture, and overhead projection.

VII. CONCLUSION AND FUTURE DIRECTIONS

The paper concludes that its distributed Hungarian algorithm enables robots to compute optimal LSAP assignments without centralized coordination, and demonstrates the approach in dynamic routing experiments. It identifies a primal reformulation as a future direction that may improve robustness and simplicity at the cost of slower convergence.

  • O(r3) iterations are sufficient under synchronous implementation for robots to converge to a common optimal LSAP assignment without a coordinator or shared memory.
  • Simulation experiments show average convergence requires far fewer iterations than the theoretic O(r3) worst-case bound.
  • Each robot performs only sub-steps of the centralized Hungarian algorithm, yielding minor computational load relative to the centralized method.
  • The distributed algorithm is extended to dynamic spatio-temporal routing with online sub-optimal routes, demonstrated through simulation and hardware multi-robot orchestra experiments.
  • A distributed primal version of the Hungarian Method is proposed as future work that may be more robust and simpler but slower to converge.
Loading 1805.08712v1…