Extending Classical Planning for Time: Research Trends in Optimal and Suboptimal Temporal Planning

Abstract

The recent advances in AI automated planning algorithms have allowed to tackle with more realistic problems that involve complex features such as explicit management of time and temporal plans (durative actions and temporal constraints), more expressive models of actions to better describe real-world problems (conservative models of actions vs. non-conservative models), utilisation of heuristic techniques to improve performance (strategies to calculate estimations and guide the search), etc. In this chapter we focus on these features, and present a review of the most successful techniques for temporal planning. First, we start with the optimal planning-graph-based approach, we do a thorough review of the general methods, algorithms and planners and finish with heuristic state-based approaches, both optimal and suboptimal. Second, we discuss the inclusion of time features into a Partial Order Causal Link (POCL) approach. In such an approach, we analyse the possibility of mixing planning with Constraint Satisfaction Problems (CSPs), formulating the planning problem as a CSP and leaving the temporal features to a CSP solver. The ultimate objective here is to come up with an advanced, combined model of planning and scheduling. Third, we outline some techniques used in hybrid approaches that combine different techniques. Finally, we provide a synthesis of many well-known temporal planners and present their main techniques.