New Heuristics for Timeline-based Planning

The timeline-based approach to planning represents an effective alternative to classical planning in complex domains where different types of reasoning are required in parallel. The iLoC domain independent planning system takes inspiration from both Constraint Programming (CP) and Logic Programming (LP). By solving both planning and scheduling problems in a uniform schema, iLoC is particularly suitable for complex domains arising from real world dynamic scenarios. Despite the planner captures elements that are very relevant for applications, its theory is quite challenging from a computational point of view and its performance are rather weak compared with those of state-of-the-art classical planners, particularly on those domains where such planners, typically, excel. In previous works, a resolution algorithm for the iLoC system has been proposed and enhanced with some (static and dynamic) heuristics that help the solving process. In this paper we propose a first improvement of the data structures underlying the proposed heuristics, producing a more informed heuristic and studying its effectiveness as a solving strategy. We perform tests on different benchmark problems from classical planning domains like the Blocks World to more challenging temporally expressive problems like the Temporal Machine Shop and the Cooking Carbonara problems, showing how the iLoC planner compares with respect to other state-of-the-art planners.