Duration prediction for proactive replanning

May 2008

Duration prediction for proactive replanning

Authors:

Brennan Sellner and Reid Simmons
Conference Paper
Proceedings of (ICRA) International Conference on Robotics and Automation

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.
@conference{Sellner-2008-122300,
author = {Brennan Sellner And Reid Simmons},
title = {Duration prediction for proactive replanning},
booktitle = {Proceedings of (ICRA) International Conference on Robotics and Automation},
year = {2008},
month = {May},
pages = {1365 - 1371},
}
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.