Situated Temporal Planning Using Deadline-aware Metareasoning

Authors

  • Shahaf S. Shperberg Ben-Gurion University
  • Andrew Coles King's College London
  • Erez Karpas Technion
  • Wheeler Ruml University of New Hampshire
  • Solomon E. Shimony Ben-Gurion University

Keywords:

Classical Planning Techniques And Analysis

Abstract

We address the problem of situated temporal planning, in which an agent's plan can depend on scheduled exogenous events, and thus it becomes important to take the passage of time into account during the planning process. Previous work on situated temporal planning has proposed simple pruning strategies, as well as complex schemes for a simplified version of the associated metareasoning problem. Although even the simplified version of the metareasoning problem is NP-hard, we provide a pseudo-polynomial time optimal solution to the case with known deadlines. We leverage intuitions emerging from this case to provide a fast greedy scheme that significantly improves upon previous schemes even for the case of unknown deadlines. Finally, we show how this new method can be applied inside a practical situated temporal planner. An empirical evaluation suggests that the new planner provides state-of-the-art results on problems where external deadlines play a significant role.

Downloads

Published

2021-05-17

How to Cite

Shperberg, S. S., Coles, A., Karpas, E., Ruml, W., & Shimony, S. E. (2021). Situated Temporal Planning Using Deadline-aware Metareasoning. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 340-348. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15979