Multi-robot coordination under temporal uncertainty

Sources of temporal uncertainty affect the duration and start time of robot actions during execution. For example, mobile robots may slip on uneven terrain, slowing them down. The presence of multiple robots in the environment contributes towards temporal uncertainty, as robot interactions such as congestion affect navigation performance. Existing multi-robot coordination solutions often disregard temporal uncertainty through simplifying assumptions such as fixed, identical action durations, which simplifies the problem at the cost of inefficient execution-time behaviour. To synthesise multi-robot behaviour that is robust to unexpected temporal disturbances, we must explicitly capture temporal uncertainty during coordination. In this thesis, we present techniques for effective multi-robot coordination under temporal uncertainty. To represent temporal uncertainty, we construct probabilistic models of action duration for each spatiotemporal situation an action may be executed in. With this, we build formal multi-robot models which accurately capture asynchronous robot execution in continuous time. We then develop planning and task allocation solutions which reason over the effects of temporal uncertainty to synthesise efficient multi-robot behaviour. Further, we consider the problem of policy evaluation, i.e. evaluating properties of synthesised multi-robot behaviour prior to execution, and present two approaches which trade between the accuracy of the model and the solution methods used for policy evaluation. Empirically, our methods outperform solutions which ignore temporal uncertainty, use simplified models, or constrain robot behaviour to reduce temporal uncertainty