Andrew Coles

JAIR Journal 2026 Journal Article

Generalised Merge and Shrink Abstractions for Temporal Planning

• Martim Brandao
• Amanda Coles
• Andrew Coles
• Rebecca Eifler

Temporal planning is a hard problem that requires good heuristic and memoization strategies to solve efficiently. Merge-and-shrink abstractions have been shown to serve as effective heuristics for classical planning, but it is still unclear how to implement merge-and-shrink in the temporal domain and how effective the method is in this setting. In this paper we propose a method to compute merge-and-shrink abstractions for general temporal planning problems, in a way that is applicable to both partial- and total-order temporal planners. We extend a previous publication to allow the formalism to apply to temporal problems with non-compression safe actions, in particular through the use of a classical planning surrogate of a temporal planning task. The method relies on pre-computing heuristics as formulas of temporal variables that are evaluated at search time, and it allows to use standard merging, shrinking and pruning strategies. Compared to state-of-the-art Relaxed Planning Graph heuristics, we show that the method leads to improvements in coverage, computation time, and number of expanded nodes to solve optimal problems, as well as leading to improvements in unsolvability-proving of problems with deadlines, and the time to compute Minimally Unsolvable Goal Subsets (MUGS). We exhaustively test the method over these problems and various usage settings, showing improvements in coverage of up to 53%, computation time up to 60%, and expanded nodes up to 75%.

IJCAI Conference 2025 Conference Paper

Concurrent Planning and Execution Using Dispatch-Dependent Values

• Andrew Coles
• Erez Karpas
• Eyal Shimony
• Shahaf Shperberg
• Wheeler Ruml

Agents operating in the real world must cope with the fact that time passes while they plan. In some cases, such as under tight deadlines, the only way for such an agent to achieve its goal is to execute an action before a complete plan has been found. This problem is called Concurrent Planning and Execution (CoPE). Previous work on CoPE relied on a value function that assumes search will finish before actions are executed, causing the agent to be overly pessimistic in many situations. In this paper, we define a new value function that takes into account the agent's ability to dispatch actions incrementally. This allows us to devise a much simpler algorithm for concurrent planning and execution. An experimental evaluation on problems with time pressure shows that the new method significantly outperforms the previous state-of-the-art.

IROS Conference 2024 Conference Paper

Are Large Language Models Aligned with People's Social Intuitions for Human-Robot Interactions?

• Lennart Wachowiak
• Andrew Coles
• Oya Çeliktutan
• Gerard Canal

Large language models (LLMs) are increasingly used in robotics, especially for high-level action planning. Meanwhile, many robotics applications involve human supervisors or collaborators. Hence, it is crucial for LLMs to generate socially acceptable actions that align with people’s preferences and values. In this work, we test whether LLMs capture people’s intuitions about behavior judgments and communication preferences in human-robot interaction (HRI) scenarios. For evaluation, we reproduce three HRI user studies, comparing the output of LLMs with that of real participants. We find that GPT-4 strongly outperforms other models, generating answers that correlate strongly with users’ answers in two studies — the first study dealing with selecting the most appropriate communicative act for a robot in various situations (r s = 0. 82), and the second with judging the desirability, intentionality, and surprisingness of behavior (r s = 0. 83). However, for the last study, testing whether people judge the behavior of robots and humans differently, no model achieves strong correlations. Moreover, we show that vision models fail to capture the essence of video stimuli and that LLMs tend to rate different communicative acts and behavior desirability higher than people.

SoCS Conference 2024 Conference Paper

Evaluating Distributional Predictions of Search Time: Put Up or Shut Up Games (Extended Abstract)

• Sean Mariasin
• Andrew Coles
• Erez Karpas
• Wheeler Ruml
• Solomon Eyal Shimony
• Shahaf S. Shperberg

Metareasoning can be a helpful technique for controlling search in situations where computation time is an important resource, such as real-time planning and search, algorithm portfolios, and concurrent planning and execution. Metareasoning often involves an estimate of the remaining search time of a running algorithm, and several ways to compute such estimates have been presented in the literature. In this paper, we argue that many applications actually require a full estimated probability distribution over the remaining time, rather than just a point estimate of expected search time. We study several methods for estimating such distributions, including some novel adaptations of existing schemes. To properly evaluate the estimates, we introduce `put-up or shut-up games

ICAPS Conference 2024 Conference Paper

Planning and Acting While the Clock Ticks

• Andrew Coles
• Erez Karpas
• Andrey Lavrinenko
• Wheeler Ruml
• Solomon Eyal Shimony
• Shahaf S. Shperberg

Standard temporal planning assumes that planning takes place offline, and then execution starts at time 0. Recently, situated temporal planning was introduced, where planning starts at time 0, and execution occurs after planning terminates. Situated temporal planning reflects a more realistic scenario where time passes during planning. However, in situated temporal planning a complete plan must be generated before any action is executed. In some problems with time pressure, timing is too tight to complete planning before the first action must be executed. For example, an autonomous car that has a truck backing towards it should probably move out of the way now, and plan how to get to its destination later. In this paper, we propose a new problem setting: concurrent planning and execution, in which actions can be dispatched (executed) before planning terminates. Unlike previous work on planning and execution, we must handle wall clock deadlines that affect action applicability and goal achievement (as in situated planning) while also supporting dispatching actions before a complete plan has been found. We extend previous work on metareasoning for situated temporal planning to develop an algorithm for this new setting. Our empirical evaluation shows that when there is strong time pressure, our approach outperforms situated temporal planning.

ECAI Conference 2024 Conference Paper

Planning for Human-Robot Collaboration Scenarios with Heterogeneous Costs and Durations

• Silvia Izquierdo-Badiola
• Gerard Canal
• Guillem Alenyà
• Carlos Rizzo
• Andrew Coles

This paper looks at human-robot collaboration (HRC) scenarios, in particular where the durations and costs of the actions are heterogeneous between agents, reflecting the agents’ capabilities as well as environmental constraints. We explore the use of temporal PDDL planning as a means of finding over-arching task plans for such collaborative scenarios, and apply suitable heuristics and search algorithms to improve the extent to which plans can be found that are sensitive to combined duration and cost metrics. An evaluation in a kitchen scenario shows our approach is effective, finding cost-effective task plans compared to those from existing planners, and a hand-crafted baseline.

ICAPS Conference 2022 Conference Paper

Merge and Shrink Abstractions for Temporal Planning

• Martim Brandão
• Amanda Jane Coles
• Andrew Coles
• Jörg Hoffmann 0001

Temporal planning is a hard problem that requires good heuristic and memoization strategies to solve efficiently. Merge-and-shrink abstractions have been shown to serve as effective heuristics for classical planning, but they have not yet been applied to temporal planning. Currently, it is still unclear how to implement merge-and-shrink in the temporal domain and how effective the method is in this setting. In this paper we propose a method to compute merge-and-shrink abstractions for temporal planning, applicable to both partial- and total-order temporal planners. The method relies on pre-computing heuristics as formulas of temporal variables that are evaluated at search time, and it allows to use standard shrinking strategies and label reduction. Compared to state-of-the-art Relaxed Planning Graph heuristics, we show that the method leads to improvements in coverage, computation time, and number of explored nodes to solve optimal problems, as well as leading to improvements in unsolvability-proving of problems with deadlines.

AAAI Conference 2022 Conference Paper

PlanVerb: Domain-Independent Verbalization and Summary of Task Plans

• Gerard Canal
• Senka Krivić
• Paul Luff
• Andrew Coles

For users to trust planning algorithms, they must be able to understand the planner’s outputs and the reasons for each action selection. This output does not tend to be user-friendly, often consisting of sequences of parametrised actions or task networks. And these may not be practical for non-expert users who may find it easier to read natural language descriptions. In this paper, we propose PlanVerb, a domain and plannerindependent method for the verbalization of task plans. It is based on semantic tagging of actions and predicates. Our method can generate natural language descriptions of plans including causal explanations. The verbalized plans can be summarized by compressing the actions that act on the same parameters. We further extend the concept of verbalization space, previously applied to robot navigation, and apply it to planning to generate different kinds of plan descriptions for different user requirements. Our method can deal with PDDL and RDDL domains, provided that they are tagged accordingly. Our user survey evaluation shows that users can read our automatically generated plan descriptions and that the explanations help them answer questions about the plan.

ICAPS Conference 2021 Conference Paper

Situated Temporal Planning Using Deadline-aware Metareasoning

• Shahaf S. Shperberg
• Andrew Coles
• Erez Karpas
• Wheeler Ruml
• Solomon Eyal Shimony

We address the problem of situated temporal planning, in which an agent's plan can depend on scheduled exogenous events, and thus it becomes important to take the passage of time into account during the planning process. Previous work on situated temporal planning has proposed simple pruning strategies, as well as complex schemes for a simplified version of the associated metareasoning problem. Although even the simplified version of the metareasoning problem is NP-hard, we provide a pseudo-polynomial time optimal solution to the case with known deadlines. We leverage intuitions emerging from this case to provide a fast greedy scheme that significantly improves upon previous schemes even for the case of unknown deadlines. Finally, we show how this new method can be applied inside a practical situated temporal planner. An empirical evaluation suggests that the new planner provides state-of-the-art results on problems where external deadlines play a significant role.

IJCAI Conference 2020 Conference Paper

Trading Plan Cost for Timeliness in Situated Temporal Planning

• Shahaf Shperberg
• Andrew Coles
• Erez Karpas
• Eyal Shimony
• Wheeler Ruml

If a planning agent is considering taking a bus, for example, the time that passes during its planning can affect the feasibility of its plans, as the bus may depart before the agent has found a complete plan. Previous work on this situated temporal planning setting proposed an abstract deliberation scheduling scheme for maximizing the probability of finding a plan that is still feasible at the time it is found. In this paper, we extend the deliberation scheduling approach to address problems in which plans can differ in their cost. Like the planning deadlines, these costs can be uncertain until a complete plan has been found. We show that finding a deliberation policy that minimizes expected cost is PSPACE-hard and that even for known costs and deadlines the optimal solution is a contingent, rather than sequential, schedule. We then analyze special cases of the problem and use these results to propose a greedy scheme that considers both the uncertain deadlines and costs. Our empirical evaluation shows that the greedy scheme performs well in practice on a variety of problems, including some generated from planner search trees.

AAAI Conference 2019 Conference Paper

Allocating Planning Effort When Actions Expire

• Shahaf S. Shperberg
• Andrew Coles
• Bence Cserna
• Erez Karpas
• Wheeler Ruml
• Solomon E. Shimony

Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent’s planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

AAAI Conference 2019 Conference Paper

Efficient Temporal Planning Using Metastates

• Amanda Coles
• Andrew Coles
• J. Christopher Beck

When performing temporal planning as forward state-space search, effective state memoisation is challenging. Whereas in classical planning, two states are equal if they have the same facts and variable values, in temporal planning this is not the case: as the plans that led to the two states are subject to temporal constraints, one might be extendable into at temporally valid plan, while the other might not. In this paper, we present an approach for reducing the state space explosion that arises due to having to keep many copies of the same ‘classically’ equal state – states that are classically equal are aggregated into metastates, and these are separated lazily only in the case of temporal inconsistency. Our evaluation shows that this approach, implemented in OPTIC and compared to existing state-of-the-art memoisation techniques, improves performance across a range of temporal domains.

AAAI Conference 2019 Conference Paper

Efficiently Reasoning with Interval Constraints in Forward Search Planning

• Amanda Coles
• Andrew Coles
• Moises Martinez
• Emre Savas
• Juan Manuel Delfa
• Tomás de la Rosa
• Yolanda E-Martín
• Angel García-Olaya

In this paper we present techniques for reasoning natively with quantitative/qualitative interval constraints in statebased PDDL planners. While these are considered important in modeling and solving problems in timeline based planners; reasoning with these in PDDL planners has seen relatively little attention, yet is a crucial step towards making PDDL planners applicable in real-world scenarios, such as space missions. Our main contribution is to extend the planner OPTIC to reason natively with Allen interval constraints. We show that our approach outperforms both MTP, the only PDDL planner capable of handling similar constraints and a compilation to PDDL 2. 1, by an order of magnitude. We go on to present initial results indicating that our approach is competitive with a timeline based planner on a Mars rover domain, showing the potential of PDDL planners in this setting.

ICAPS Conference 2019 Conference Paper

Personalized Medication and Activity Planning in PDDL+

• Fares K. Alaboud
• Andrew Coles

The emergence of planners capable of reasoning with continuous dynamics, as expressed in PDDL+, has increased the range of problems that fall within the capabilities of PDDL planners. One such problem is planning patients’ activities and medication regimes, considering non-linear medication pharmacokinetics. In this paper we explore the application of contemporary PDDL+ planners to this problem. To address their performance limitations, we present a linearize–validate cycle; tasks are solved by iterative refinement of a linear approximation of the domain, solved by a linear planner, then validated at each stage against the full non-linear semantics. In doing this we allow this domain to fall within the capabilities of current planners; and in our evaluation we use OPTIC to demonstrate this.

ICAPS Conference 2019 Conference Paper

Replanning for Situated Robots

• Michael Cashmore
• Andrew Coles
• Bence Cserna
• Erez Karpas
• Daniele Magazzeni
• Wheeler Ruml

Planning enables intelligent agents, such as robots, to act so as to achieve their long term goals. To make the planning process tractable, a relatively low fidelity model of the world is often used, which sometimes leads to the need to replan. The typical view of replanning is that the robot is given the current state, the goal, and possibly some data from the previous planning process. However, for robots (or teams of robots) that exist in continuous physical space, act concurrently, have deadlines, or must otherwise consider durative actions, things are not so simple. In this paper, we address the problem of replanning for situated robots. Relying on previous work on situated temporal planning, we frame the replanning problem as a situated temporal planning problem, where currently executing actions are handled via Timed Initial Literals (TILs), under the assumption that actions cannot be interrupted. We then relax this assumption, and address situated replanning with interruptible actions. We bridge the gap between the low-level model of the robot and the high-level model used for planning by the novel notion of a bail out action generator, which relies on the low-level model to generate highlevel actions that describe possible ways to interrupt currently executing actions. Because actions can be interrupted at different times during their execution, we also propose a novel algorithm to handle temporal planning with time-dependent durations.

ICAPS Conference 2018 Conference Paper

Temporal Planning while the Clock Ticks

• Michael Cashmore
• Andrew Coles
• Bence Cserna
• Erez Karpas
• Daniele Magazzeni
• Wheeler Ruml

One of the original motivations for domain-independent planning was to generate plans that would then be executed in the environment. However, most existing planners ignore the passage of time during planning. While this can work well when absolute time does not play a role, this approach can lead to plans failing when there are external timing constraints, such as deadlines. In this paper, we describe a new approach for time-sensitive temporal planning. Our planner is aware of the fact that plan execution will start only once planning finishes, and incorporates this information into its decision making, in order to focus the search on branches that are more likely to lead to plans that will be feasible when the planner finishes.

ICAPS Conference 2017 Conference Paper

A Temporal Relaxed Planning Graph Heuristic for Planning with Envelopes

• Amanda Jane Coles
• Andrew Coles

When planning in temporal domains with required concurrency, envelopes arise where one or more actions need to occur within the execution of another. Starting an envelope action gives rise to an implicit relative deadline: all of the actions that need to occur within the envelope must complete before it ends. Finding effective heuristic guidance in these domains is challenging: the heuristic must not only consider how to reach the goals, but identify when it is not possible to achieve these implicit deadlines to avoid fruitless search. In this paper, we present an adaptation of a Temporal Relaxed Planning Graph heuristic, that accounts for dependencies between facts and actions in the relaxed planning graph; and the envelopes that are open in the state being evaluated. Results show that our new heuristic significantly improves the performance of a temporal planner on benchmark domains with required concurrency.

ICAPS Conference 2016 Conference Paper

Have I Been Here Before? State Memoization in Temporal Planning

• Amanda Jane Coles
• Andrew Coles

State memoization is critical to the good performance of heuristic forward search planners, which represent a significant proportion of the current state-of-the-art planning approaches. In non-temporal planning it is sufficient to discard any state that has been generated before, regardless of the path taken to reach that state, with the only side-constraint being plan cost. We begin this paper by demonstrating that the use of this technique in temporal planning can lead to loss of optimality with respect to metrics involving makespan and that in the case of more expressive domains can lead to loss of completeness. We identify the specific conditions under which this occurs: states where actions are currently executing. Following from this we introduce new memoization techniques for expressive temporal planning problems that are both completeness and optimality preserving, solving the challenging problem of determining when two states in temporal planning can be considered equivalent. Finally, we demonstrate that these have significant impact on improving the planning performance across a wide range of temporal planning benchmarks in the POPF planning framework.

ICAPS Conference 2016 Conference Paper

Heuristic Guidance for Forward-Chaining Planning with Numeric Uncertainty

• Liana Marinescu
• Andrew Coles

Uncertainty hinders many interesting applications of planning - it may come in the form of sensor noise, unpredictable environments, or known limitations in problem models. In this paper we explore heuristic guidance for forward-chaining planning with continuous random variables, while ensuring a probability of plan success. We extend the Metric Relaxed Planning Graph heuristic to capture a model of uncertainty, providing better guidance in terms of heuristic estimates and dead-end detection. By tracking the accumulated error on numeric values, our heuristic is able to check if preconditions in the planning graph are achievable with a sufficient degree of confidence; it is also able to consider acting to reduce the accumulated error. Results indicate that our approach offers improvements in performance compared to prior work where a less-informed relaxation was used.

ECAI Conference 2016 Conference Paper

Non-Deterministic Planning with Numeric Uncertainty

• Liana Marinescu
• Andrew Coles

Uncertainty arises in many compelling real-world applications of planning. There is a large body of work on propositional uncertainty where actions have non-deterministic outcomes. However handling numeric uncertainty has been given less consideration. In this paper, we present a novel offline policy-building approach for problems with numeric uncertainty. In particular, inspired by the planner PRP, we define a numeric constraint representation that captures only relevant numeric information, supporting a more compact policy representation. We also show how numeric dead ends can be generalised to avoid redundant search. Empirical results show we can substantially reduce the time taken to build a policy.

ICAPS Conference 2014 Conference Paper

PDDL+ Planning with Events and Linear Processes

• Amanda Jane Coles
• Andrew Coles

We present a scalable fully-automated forward-chaining planner capable of reasoning with PDDL+ events and linear processes. Processes and events model (respectively) continuous and discrete exogenous activity in the environment, occurring when certain conditions hold. We discuss the significant challenges posed in creating a planner that can reason with these, and present novel state-progression and consistency enforcing techniques that allow us to meet these challenges. We present results showing that our new planner, using PDDL+ models, is able to solve realistic expressive problems more efficiently than the state-of-the-art alternative: a compiled PDDL 2. 1 representation with continuous numeric effects.

ICAPS Conference 2013 Conference Paper

Searching for Good Solutions in Goal-Dense Search Spaces

• Amanda Jane Coles
• Andrew Coles

In this paper we explore the challenges surrounding searching effectively in problems with preferences. These problems are characterized by a relative abundance of goal states: at one extreme, if every goal is soft, every state is a goal state. We present techniques for planning in such search spaces, managing the sometimes-conflicting aims of intensifying search around states on the open list that are heuristically close to new, better goal states; and ensuring search is sufficiently diverse to find new low-cost areas of the search space, avoiding local minima. Our approach uses a novel cost-bound-sensitive heuristic, based on finding several heuristic distance-to-go estimates in each state, each satisfying a different subset of preferences. We present results comparing our new techniques to the current state-of-the-art and demonstrating their effectiveness on a wide range of problems from recent International Planning Competitions.

ICAPS Conference 2012 Conference Paper

Automated Planning for Liner Shipping Fleet Repositioning

• Kevin Tierney
• Amanda Jane Coles
• Andrew Coles
• Christian Kroer
• Adam M. Britt
• Rune Møller Jensen

The Liner Shipping Fleet Repositioning Problem (LSFRP) poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between services in a liner shipping network. The LSFRP is characterized by chains of interacting activities, many of which have costs that are a function of their duration; for example, sailing slowly between two ports is cheaper than sailing quickly. Despite its great industrial importance, the LSFRP has received little attention in the literature. We show how the LSFRP can be solved sub-optimally using the planner POPF and optimally with a mixed-integer program (MIP) and a novel method called Temporal Optimization Planning (TOP). We evaluate the performance of each of these techniques on a dataset of real-world instances from our industrial collaborator, and show that automated planning scales to the size of problems faced by industry.

ICAPS Conference 2012 Conference Paper

Temporal Planning with Preferences and Time-Dependent Continuous Costs

• J. Benton 0001
• Amanda Jane Coles
• Andrew Coles

Temporal planning methods usually focus on the objective of minimizing makespan. Unfortunately, this misses a large class of planning problems where it is important to consider a wider variety of temporal and non-temporal preferences, making makespan lower-order concern. In this paper we consider modeling and reasoning with plan quality metrics that are not directly correlated with plan makespan, building on the planner POPF. We begin with the preferences defined in PDDL3, and present a mixed integer programming encoding to manage the the interaction between the hard temporal constraints for plan steps, and soft temporal constraints for preferences. To widen the support of metrics that can be expressed directly in PDDL, we then discuss an extension to soft-deadlines with continuous cost functions, avoiding the need to approximate these with several PDDL3 discrete-cost preferences. We demonstrate the success of our new planner on the benchmark temporal planning problems with preferences, showing that it is the state-of-the-art for such problems. We then analyze the benefits of reasoning with continuous (versus discretized) models of domains with continuous cost functions, showing the improvement in solution quality afforded through making the continuous cost function directly available to the planner.

ICAPS Conference 2011 Conference Paper

Cost-Sensitive Concurrent Planning Under Duration Uncertainty for Service-Level Agreements

• Andrew Coles
• Amanda Jane Coles
• Allan Clark
• Stephen Gilmore

This paper brings together work in stochastic modelling, using the process algebra PEPA, and work in automated planning. Stochastic modelling has been concerned with verification of system performance metrics for some time: given a model of a system, determining whether it will meet a service-level agreement (SLA). For example, whether a given sequence of transitions on a network will complete within 5 seconds 80% of the time. The problem of deciding how to reconfigure the system most cost-effectively when the SLA cannot be met has not been widely explored: it is currently solved manually. Inspired by this, we consider how planning can be used to automate the configuration of service-oriented systems. Configuring these stochastic systems presents new challenges to planning: building plans that meet SLAs, but also have low cost. To this end, we present a domain-independent planner for planning problems with action costs and stochastic durations, and show how this can be used to solve both traditional planning domains, and within the framework of configuring a larger process algebra model.

ICAPS Conference 2011 Conference Paper

LPRPG-P: Relaxed Plan Heuristics for Planning with Preferences

• Amanda Jane Coles
• Andrew Coles

In this paper we present a planner, LPRPG-P, capable of reasoning with the non-temporal subset of PDDL 3 preferences. Our focus is on computation of relaxed plan based heuristics that effectively guide a planner towards good solutions satisfying preferences. We build on the planner LPRPG, a hybrid relaxed planning graph (RPG)--linear programming (LP) approach. We make extensions to the RPG to reason with propositional preferences, and to the LP to reason with numeric preferences. LPRPG-P is the first planner with direct guidance for numeric preference satisfaction, exploiting the strong numeric reasoning of the LP. We introduce an anytime search approach for use with our new heuristic, and present results showing that LPRPG-P extends the state of the art in domain-independent planning with preferences.

ECAI Conference 2010 Conference Paper

Completeness-Preserving Pruning for Optimal Planning

• Amanda Jane Coles
• Andrew Coles

This paper focuses on efficient methods for pruning the state space in cost-optimal planning. The use of heuristics to guide search and prune irrelevant branches has been widely and successfully explored. However, heuristic computation at every node in the search space is expensive, and even near perfect heuristics still leave a large portion of the search space to be explored [9]. Using up-front analysis to reduce the number of nodes to be considered therefore has great potential. Our contributions are not concerned with heuristic guidance, rather, with orthogonal completeness-preserving pruning techniques that reduce the number of states a planner must explore to find an optimal solution. We present results showing that our techniques can improve upon state-of-the-art optimal planners, both when using blind search and importantly in conjunction with modern heuristics, specifically hLM-CUT[8]. Our techniques are not limited to optimal planning and can also be applied in satisfycing planning.

ICAPS Conference 2010 Conference Paper

Forward-Chaining Partial-Order Planning

• Amanda Jane Coles
• Andrew Coles
• Maria Fox 0001
• Derek Long

Over the last few years there has been a revival of interest in the idea of least-commitment planning with a number of researchers returning to the partial-order planning approaches of UCPOP and VHPOP. In this paper we explore the potential of a forward-chaining state-based search strategy to support partial-order planning in the solution of temporal-numeric problems. Our planner, POPF, is built on the foundations of grounded forward search, in combination with linear programming to handle continuous linear numeric change. To achieve a partial ordering we delay commitment to ordering decisions, timestamps and the values of numeric parameters, managing sets of constraints as actions are started and ended. In the context of a partially ordered collection of actions, constructing the linear program is complicated and we propose an efficient method for achieving this. Our late-commitment approach achieves flexibility, while benefiting from the informative search control of forward planning, and allows temporal and metric decisions to be made - as is most efficient - by the LP solver rather than by the discrete reasoning of the planner. We compare POPF with the approach of constructing a sequenced plan and then lifting a partial order from it, showing that our approach can offer improvements in terms of makespan, and time to find a solution, in several benchmark domains.

IJCAI Conference 2009 Conference Paper

• Amanda Coles
• Andrew Coles
• Maria Fox
• Derek Long

We consider the problem of planning in domains with continuous linear numeric change. Such change cannot always be adequately modelled by discretisation and is a key facet of many interesting problems. We show how a forward-chaining temporal planner can be extended to reason with actions with continuous linear effects. We extend a temporal planner to handle numeric values using linear programming. We show how linear continuous change can be integrated into the same linear program and we discuss how a temporal-numeric heuristic can be used to provide the search guidance necessary to underpin continuous planning. We present results to show that the approach can effectively handle duration-dependent change and numeric variables subject to continuous linear change.

ICAPS Conference 2009 Conference Paper

Extending the Use of Inference in Temporal Planning as Forwards Search

• Amanda Jane Coles
• Andrew Coles
• Maria Fox 0001
• Derek Long

PDDL 2. 1 supports modelling of complex temporal planning domains in which solutions must exploit concurrency. Few existing temporal planners can solve problems that require concurrency and those that do typically pay a performance price to deploy reasoning machinery that is not always required. In this paper we show how to improve the performance of forward-search planners that attempt to solve the full temporal planning problem, both by narrowing the use of the concurrency machinery to situations that demand it and also by improving the power of inference to prune redundant branches of the search space for common patterns of interaction in temporal domains that do require concurrency. Results illustrate the effectiveness of our ideas in improving the efficiency of a temporal planner that can solve problems with required concurrency, both in domains that exploit this ability and in those that do not.

AIJ Journal 2009 Journal Article

Managing concurrency in temporal planning using planner-scheduler interaction

• Andrew Coles
• Maria Fox
• Keith Halsey
• Derek Long
• Amanda Smith

ICAPS Conference 2008 Conference Paper

A Hybrid Relaxed Planning Graph'LP Heuristic for Numeric Planning Domains

• Andrew Coles
• Maria Fox 0001
• Derek Long
• Amanda Jane Coles

Effective search control for numeric planning domains, in which appropriate numeric resource usage is critical to solving the problem, remains an open challenge in domain-independent planning. Most real-world problems rely on metric resources such as energy, money, fuel or materials. Despite the importance of numbers, few heuristics have been proposed to guide search in such domains. Hoffmann's extended relaxation, implemented in Metric-FF, is one of the best general heuristics. We examine the behaviour of the Relaxed Planning Graph (RPG) heuristic, used by Metric-FF, in numeric problems. While effective in problems with simple numeric interactions, it has two weaknesses when numeric reasoning is a fundamental part of solving the problem. We present a new heuristic for use in strongly numeric domains, using a Linear Program to capture numeric constraints as an adjunct to a relaxed planning graph. We demonstrate that an intelligent combination of these two techniques offers greatly improved heuristic guidance.

ICAPS Conference 2008 Conference Paper

Additive-Disjunctive Heuristics for Optimal Planning

• Andrew Coles
• Maria Fox 0001
• Derek Long
• Amanda Jane Coles

The development of informative, admissible heuristics for cost-optimal planning remains a significant challenge in domain-independent planning research. Two techniques are commonly used to try to improve heuristic estimates. The first is disjunction: taking the maximum across several heuristic values. The second is the use of additive techniques, taking the sum of the heuristic values from a set of evaluators in such a way that admissibility is preserved. In this paper, we explore how the two can be combined in a novel manner, using disjunction within additive heuristics. We define a general structure, the Additive-Disjunctive Heuristic Graph (ADHG), that can be used to define an interesting class of heuristics based around these principles. As an example of how an ADHG can be employed, and as an empirical demonstration, we then present a heuristic based on the well-known additive hm heuristic, showing an improvement in performance when additive-disjunctive techniques are used.

AAAI Conference 2008 Conference Paper

Planning with Problems Requiring Temporal Coordination

• Andrew Coles
• Derek Long

We present the first planner capable of reasoning with both the full semantics of PDDL2. 1 (level 3) temporal planning and with numeric resources. Our planner, CRIKEY3, employs heuristic forward search, using the start-and-end semantics of PDDL2. 1 to manage temporal actions. The planning phase is interleaved with a scheduling phase, using a Simple Temporal Network, in order to ensure that temporal constraints are met. To guide search, we introduce a new temporal variant of the Relaxed Planning Graph heuristic that is capable of reasoning with the features of this class of domains, along with the Timed Initial Literals of PDDL2. 2. CRIKEY3 extends the state-of-the-art in handling the full temporal expressive power of PDDL2. 1, including numeric temporal domains.

ICAPS Conference 2007 Conference Paper

A New Local-Search Algorithm for Forward-Chaining Planning

• Andrew Coles
• Maria Fox 0001
• Amanda Jane Coles

Forward-chaining heuristic search is a well-established and popular paradigm for domain-independent planning. Its effectiveness relies on the heuristic information provided by a state evaluator, and the search algorithm used with this in order to solve the problem. This paper presents a new stochastic local-search algorithm for forward-chaining planning. The algorithm is used as the basis of a planner in conjunction with FF's Relaxed Planning Graph heuristic. Our approach is unique in that localised restarts are used, returning to the start of plateaux and saddle points, as well as global restarts to the initial state. The majority of the search time when using FF's ‘Enforced Hill Climbing’ is spent using breadth-first search to escape local minima. Our localised restarts, in conjunction with stochastic search, serve to replace this expensive breadth-first search step. We also describe an extended search neighbourhood incorporating non-helpful actions and the ‘lookahead’ states used in YAHSP. Making use of non-helpful actions and stochastic search allows us to restart the local-search from the initial state when dead-ends are encountered; rather than resorting to best-first search. We present analyses to demonstrate the effectiveness of our restart strategies, along with results that show the new planning algorithm is effective across a range of domains.

ICAPS Conference 2007 Conference Paper

Online Identification of Useful Macro-Actions for Planning

• Andrew Coles
• Maria Fox 0001
• Amanda Jane Coles

This paper explores issues encountered when performing online management of large collections of macro-actions generated for use in planning. Existing approaches to managing collections of macro-actions are designed for use with offline macro-action learning, pruning candidate macro-actions on the basis of their effect on the performance of the planner on small training problems. In this paper we introduce macro-action pruning techniques based on properties of macro-actions that can be discovered online, whilst solving only the problems we are interested in. In doing so, we remove the requirement for additional training problems and offline filtering. We also show how search-time pruning techniques allow the planner to scale well to managing large collections of macro-actions. Further, we discuss the properties of macro-actions that allow the online identification of those that are likely to be useful in search. Finally, we present results to demonstrate that a library of macro-actions managed using the techniques described can give rise to a significant performance improvement across a collection of domains with varied structure.

ICAPS Conference 2007 Conference Paper

Planning with Respect to an Existing Schedule of Events

• Andrew Coles
• Maria Fox 0001
• Derek Long
• Amanda Jane Coles

Decomposition has proved an effective strategy in planning, with one decomposition-based planner, {sc SGPlan}, exhibiting strong performance in the last two IPCs. By decomposing planning problems into several loosely coupled subproblems, themselves planning problems, a planner can be used to solve each of the subproblems individually. The subplans can then be combined to form a solution to the original problem. When planning for subproblems, it is necessary to account for the interactions between the actions used to solve the current subproblem and the actions chosen to solve other subproblems. The approach taken in {sc SGPlan} is inspiring, but some aspects of the decomposition process are not fully described in the literature. In particular, how subplans are merged to form a complete plan is not discussed anywhere in detail. This paper presents an approach to planning at this subproblem level, detailing how the choices made whilst solving one subproblem can be influenced by the conflicts with other subproblems, and introduces a novel technique employing {em wait events} that can be included in subproblem solution plans to allow the context of the existing schedule to be directly considered.