A TIL-Relaxed Heuristic for Planning with Time Windows - Allard, Tony; Gretton, Charles; Haslum, Patrik (Proceedings of the International Conference on Automated Planning and Scheduling, 2018)
We consider planning problems with time windows, in which the availability of discrete resources is time constrained. We develop a novel heuristic that addresses specifically the difficulty of coordinating actions within time windows. The heuristic is based on solving a temporally relaxed problem and measuring the magnitude by which the relaxed solution violates the time window constraints. Applied in a state-space search planner, the heuristic reduces the number of dead-ends encountered during search, and improves planner coverage.