Just-In-Time backfilling in Multi-Agent Scheduling

May 2009

Just-In-Time backfilling in Multi-Agent Scheduling

Authors:

A. Gallagher, L. Hunsberger, and S. F. Smith

Abstract:

This paper addresses the problem of how a group of agents cooperating on a complex plan with interdependent actions can coordinate their scheduling and execution of those actions, particularly in domains where actions may fail or have uncertain durations. If actions fail (or fail to meet their deadlines), the repercussions for the rest of the team’s plan can be dramatic. This paper presents a pro-active strategy, called Just-in-Time Backfilling (JIT-BF), that agents can use to increase the fault tolerance of their interdependent schedules by identifying actions in danger of failing and inserting redundant (or back-up) actions into their schedules. The insertion of redundant actions can be done locally (i.e., by the agent whose action is in danger of failing) or through negotiations with the rest of the team. The computations performed by agents following the JIT-BF strategy depend on probabilistic models of action durations and the “quality” achieved by successfully executing actions. The paper presents an experimental evaluation of the JIT-BF strategy within a simulated real-time dynamic environment that demonstrates that teams using the pro-active JIT-BF strategy significantly out-perform teams that rely solely on reactive strategies.
@conference{Gallagher-2009-120482,
author = {A. Gallagher And L. Hunsberger And S. F. Smith},
title = {Just-In-Time backfilling in Multi-Agent Scheduling},
booktitle = {Proceedings of 22nd International Conference of the Florida Artificial Intelligence Research Society (FLAIRS '09)},
year = {2009},
month = {May},
pages = {189 - 194},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.