Predictive Receding-Horizon Multi-Robot Task Allocation with Moving Tasks

The first version of the predictive receding-horizon task allocation method, presented on an academic case study.

The setting is a robotic sensor network measuring irradiance across a thermosolar plant, where the things being measured — cloud shadows — keep moving. That makes the assignment time-extended: you cannot allocate once, because by the time a robot arrives the task has gone somewhere else. The answer is to borrow the structure of model predictive control: predict how tasks evolve, allocate a sequence over a horizon, apply only the first step, then recompute.

What makes it scale is that the problem is transformed into a linear program. Other time-extended MRTA formulations solve a non-convex problem, which puts plant-sized instances out of reach.

What came next

This paper was extended into the Solar Energy journal version, Predictive Receding-Horizon Multi-Robot Task Allocation Applied to the Mapping of Direct Normal Irradiance in a Thermosolar Power Plant, which adds:

• a hybrid event-based/synchronous recalculation strategy, replacing the purely event-triggered version here — which matters once cloud velocity is uncertain
• a more compact formulation of the energetic constraints
• better prediction of robot-to-task distances across horizon steps
• realistic simulation in ROS and Gazebo, on a model of the La Africana plant

Compared directly on 1000 random problems, the journal version solves more of them (776 against 744) and achieves a better mean cost on those both can solve — 1384.2 against 1562.1.