Probabilistic Strengthening of Distributed Multi-Agent Schedules

Abstract

Principled handling of uncertainty can be critical for teams of agents that collaborate in realistic environments to maximize reward. We focus on a class of
over-subscribed distributed scheduling problems where there is uncertainty in both the duration and outcomes of executed activities, and activities are subject to deadlines.At the core of each agent is a scalable, distributed, deterministic scheduler whose fundamental mode for handling uncertainty is selective invocation in response to the dynamics of execution. In this paper, we describe a methodology enabling agents to locally improve their deterministic schedules via a probabilistic analysis. The distributed analysis allows each agent to identify likely points of failure posing the greatest risk to overall team reward and to hedge against such failure by modifying its local schedule to strengthen the overall mission. We present experimental results demonstrating that coupling probabilistic and deterministic reasoning in this way results in significantly higher rewards than are achieved by relying on deterministic reasoning alone, with little additional computational expense.