Duration prediction for proactive replanning

Abstract

Proactive replanning attempts to predict scheduling problems or opportunities and adapt to them throughout a schedule's execution. By continuously predicting a task's remaining duration, a proactive replanner is able to accommodate upcoming problems or opportunities before they manifest themselves. We have developed a kernel density estimation-based method for predicting a task's duration distribution as it executes, and have integrated our prediction algorithm with an existing planner based on heuristic repair. Our predictor allows the planner to anticipate problems, or opportunities, early enough to avoid, or take advantage of, them, resulting in executed schedules that score significantly higher on a number of metrics. We have evaluated a limited form of our approach in simulation, and present the results of our experiments. The addition of duration prediction resulted in a 11.1% improvement in average reward. Compared with an omniscient planner, this is 45.0% of the maximum possible improvement.