New Heuristics and Search Control Techniques for Temporal Planning with Time Windows

Abstract

A common feature in planning is the need to interact with events that occur at known times, but are outside of a planner's control. For example, the loading and unloading of cargo at a warehouse that may only occur during business hours. These events introduce time window constraints on resource availability, which can have implications on the causal structure of the plan. Existing planners are not good at eliciting search guidance from time window constraints, and therefore often explore many causal decisions that are temporally infeasible. Planning systems like these may perform many causal searches that lead to dead-ends, and can cause a planner to fail to find a solution. In practice, the difficulty in solving problems with time windows is proportional to the duration of the time window constraint; increasing as the temporal constraint tightens. Tight time window constraints can also lead to plans requiring concurrent action.

Motivated by the challenge of Planning Problems with Time Windows, this thesis makes several contributions to advance the field of Automated Planning. First, we present a new planning domain, the Multi-Modal Cargo Routing problem, intended to provide a rich model to support planning research for real world problems with time windows. We demonstrate this as a temporally interesting and complex domain, tunable to support research on problems with numerous and/or tight time windows, that often require concurrency in plans. We use this domain to produce a problem set that challenges contemporary planning systems, and supports the evaluation of our contributions. The study and evaluation of our approaches to this class of problems also highlights a challenging sub-class; where a sequential chain of actions is required to satisfy a goal condition within a time window constraint. In such approaches there may be many causal action sequences that achieve the goal, but only very few that do so within the time window constraint. We present a synthetic domain, the Action Chains domain, intended to model this problem type and support our investigation and contribution of suitable solution procedures.

Next, we present a new family of heuristics for approaching planning problems with time windows; specifically those with numerous and/or tight time windows. The approach we detail is based on relaxing away the challenging temporal aspects of time windows, forming a relaxed problem that considers only their casual effects. We use metrics from the solution to this problem relaxation as a heuristic state evaluation to guide search. These approaches have been integrated into two state-based heuristic search planners. A detailed study of the performance of these planning systems, guided by our heuristics, is conducted on our cargo routing problem, and benchmark problems from literature. We demonstrate that relaxing the temporal aspects of time window constraints can be an effective heuristic guidance for forward state-space search planning systems.

Finally, motivated by the challenge of problems that require chains of actions to satisfy a goal condition within a time window, we present a new planning system. This approach aims to efficiently prune causal executions during search that do not meet the time window constraint. The planning system is built on the concepts of temporal relaxation, constraint generation, and search control. We present a number of approaches to generate and model constraints, and use them to constrain search. Performance of all contemplated approaches is evaluated on IPC benchmarks, and new domains developed to highlight the importance and challenge of planning with time windows. Our observations show that by solving the underlying causal problem we can quickly identify inconsistent action sequences and control search to admit a solution for the temporal problem with time windows. Show more