# Robotics: Science and Systems VI

### Assessing Optimal Assignment under Uncertainty: An Interval-based Algorithm

*L. Liu and D. Shell*

**Abstract:**

We consider the problem of multi-robot taskallocation
when robots have to deal with uncertain utility estimates.
Typically an allocation is performed to maximize expected
utility; we consider a means for measuring the robustness of
a given optimal allocation when robots have some measure of
the uncertainty (e.g., a probability distribution, or moments of
such distributions). We introduce a new O(n^{4}) algorithm, the
Interval Hungarian algorithm, that extends the classic Kuhn-
Munkres Hungarian algorithm to compute the maximum interval
of deviation (for each entry in the assignment matrix) which
will retain the same optimal assignment. This provides an
efficient measurement of the tolerance of the allocation to the
uncertainties, for both a specific interval and a set of interrelated
intervals. We conduct experiments both in simulation and with
physical robots to validate the approach and to gain insight into
the effect of location uncertainty on allocations for multi-robot
multi-target navigation tasks.

**Bibtex:**

@INPROCEEDINGS{ Liu-RSS-10, AUTHOR = {L. Liu AND D. Shell}, TITLE = {Assessing Optimal Assignment under Uncertainty: An Interval-based Algorithm}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2010}, ADDRESS = {Zaragoza, Spain}, MONTH = {June} }