Temporal planning for rich numeric contexts

Abstract

Real-world planning problems often feature complex temporal and numeric characteristics. These include concurrent activities and also effects that involve continuous change. This work presents the formalism behind reasoning with required concurrency that involves continuous change in temporal planning problems, together with a set of techniques to solve a class of tasks that to date are hard to solve with current state-of-the-art temporal planners. The motivation for this work is scenarios where planning actions have rich numeric effects on some physical system. One such example is automated demand dispatch for electricity provision, where actions that fulfil customer requirements have an effect on various metrics, such as wattage or costs, which could be subject to operational or commercial constraints. An algorithm that handles discrete interference of linear continuous effects, referred to as constants in context, is presented. This technique allows discrete actions to update the rate of change of a continuous effect taking place concurrently. This work builds on techniques used in current temporal planners that make use of linear programming, and also extends the heuristic to guide the search to a solution. This algorithm was implemented in a new temporal and numeric planner called DICE and evaluated with some benchmark domains. PDDL, the current de facto standard language for planning domains and corresponding planning tasks, was extended to support interactions with external class modules. The proposed extension, PDDLx, defines a generic planner-solver interface for both discrete and continuous effects. This enables planners that implement this interface to interact with external solvers and incorporate context-specific effects in a black-box fashion, enabling complex numeric behaviour to be encapsulated within such modules. Non-linear monotonic continuous effects, defined in the proposed PDDLx extension, are integrated within the planner using a non-linear iterative convergence algorithm. It searches for a linear approximation within an acceptable configurable error margin, which is then used within the linear program computed for each temporal state. This algorithm proves to be effective in various domains where non-linear continuous behaviour is prevalent. This technique was implemented as an extension to DICE, called uNICOrn, which performs non-linear iterative convergence for continuous effects whose duration needs to be determined by the planner. uNICOrn was also evaluated with some benchmark non-linear domains. A case study on the automated demand dispatch domain is presented to demonstrate the use of the planning algorithms proposed in this thesis. Linear and non-linear planning problems are evaluated and the performance of uNICOrn on these problem instances was analysed. This work builds on current techniques used for temporal planning with continuous numeric behaviour using linear programming, and enhances them to remove some of their intrinsic limitations. The result is a set of algorithms that are more effective in solving real-world applications that involve continuous change and rich numeric behaviour.