Reasoning about Executional Uncertainty to Strengthen Schedules

Abstract

We consider a scheduling problem where the goal is to maximize the reward obtained by a team of agents in an execution environment,with duration and activity outcome, uncertainty. To address scalability issues, we take as our starting point a deterministic, partial-order schedule and attempt to hedge against activity failure by adding redundant backup activities into the agent schedules. There is a basic trade-off in adding such backup activities, since they reduce overall temporal slack and can increase the risk that other activities will fail. We approach,this trade-off by explicitly analyzing the executional uncertainty of the deterministic schedule to identify those activities most likely to fail to contribute to scheduled reward, and target the introduction of additional backup activities accordingly. The analysis also determines when,the schedule has become,saturated and further activity additions would,be counterproductive. Experiments in simulation demonstrate that schedules that are strengthened in this manner,earn higher reward than both the original schedules and those produced by less focused mechanisms.