A TIL-Relaxed Heuristic for Planning with Time Windows
Keywords:Automated Planning, Temporal Planning, Time Windows, Timed Initial Literals, Heuristic Search Planning
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.