Uploaded May 2018 | Updated September 2026, 2 weeks ago
ICRA 2018 Spotlight Video
Interactive Session Wed AM Pod S.1
Authors: Palmer, Andrew William; Hill, Andrew John; Scheding, Steven
Title: Modelling Resource Contention in Multi-Robot Task Allocation Problems with Uncertain Timing
Abstract:
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.
ICRA 2018 Spotlight Video
Interactive Session Wed AM Pod S.1
Authors: Palmer, Andrew William; Hill, Andrew John; Scheding, Steven
Title: Modelling Resource Contention in Multi-Robot Task Allocation Problems with Uncertain Timing
Abstract:
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.
