Probabilistic Plan Management

This paper describes an approach to scheduling under uncertainty that achieves scalability through a coupling of deterministic and probabilistic reasoning. A class of oversubscribed scheduling problems is considered where the goal is to maximize the reward earned by a team of agents in a distributed execution environment. There is uncertainty in both the duration and outcomes of executed activities, and activities are subject to deadlines. To ensure scalability, the approach takes as its starting point an initial deterministic schedule for the agents, computed using expected duration reasoning. This initial agent schedule is probabilistically analyzed to find likely points of failure, and then selectively strengthened based on this analysis. Experimental results obtained in a multi-agent simulation environment demonstrate that coupling probabilistic and deterministic reasoning in this way results in significantly higher rewards than are achieved by relying on deterministic reasoning alone. In the future, the approach will be extended to include probability-driven meta-level management of execution.