Tackling task allocation uncertainty via a combinatorial method

A task-executing robot may encounter various types of uncertainty born of sensing, actuation, and motion errors. A robot uncertain of its current state is likely to reflect this uncertainty in the calculation of its utilities or performance estimates (e.g., costs, fitnesses) for planning purposes too. While controlling a single robot under uncertainty is challenging, coordinating a group of robots is likely to exacerbate the problem. An efficient and reliable way for assessing the uncertainty in the system in light of how it will affect robot´s decisions and subsequent actions can help address the challenge of distributed reasoning under uncertainty. This paper examines our previously developed Interval Hungarian algorithm, providing complementary interpretations from the perspective of robotics applications. The method is described step by step via a common scenario: multi-robot navigation with localization uncertainty. Which we provide an extended comparison and analysis of this algorithm, as well as insights that we gained from experience conducting physical robots experiments.