Modelling resource contention in multi-robot task allocation problems with uncertain timing
This provides a general framework for improving multi-robot system planning by incorporating uncertainty, though it is incremental as it builds on existing methods for stochastic modeling.
The paper tackles the problem of resource contention in multi-robot task allocation under uncertain timing by proposing an analytical framework that uses approximation methods to compute probability distributions for task start and finish times, showing it is faster than Monte Carlo approaches for the same accuracy.
This paper proposes an analytical framework for modelling resource contention in multi-robot systems, where the travel times and task durations are uncertain. It uses several approximation methods to quickly and accurately calculate the probability distributions describing the times at which the tasks start and finish. Specific contributions include exact and fast approximation methods for calculating the probability of a set of independent normally distributed random events occurring in a given order, a method for calculating the most likely and n-th most likely orders of occurrence for a set of independent normally distributed random events that have equal standard deviations, and a method for approximating the conditional probability distributions of the events given a specific order of the events. The complete framework is shown to be faster than a Monte Carlo approach for the same accuracy in two multi-robot task allocation problems. In addition, the importance of incorporating uncertainty is demonstrated through a comparison with a deterministic method. This is a general framework that is agnostic to the optimisation method and objective function used, and is applicable to a wide range of problems.