Amanda Jane Coles

HAXP Workshop 2025 Workshop Paper

How Humans Explain the Difference in the Quality of Plans -- A User Study

• Benjamin Krarup
• Amanda Jane Coles
• Dancheng Gao
• Derek Long
• David E. Smith

Recent advances in plan explanation have used abstractions to produce explanations. We consider the task of explaining why there is a difference in the quality of plans produced for a planning problem, $\Pi$, and the same problem constrained in some way, $\Pi + c$. The method involves abstracting away details of the planning problems until the difference in the quality of plans they support is minimised. It is not known whether humans use abstractions to explain these differences, and if so, what types of properties these abstractions have. We present the results of a qualitative user study investigating this. We tasked participants with explaining the difference in the quality of plans and found that users do indeed use abstractions to explain differences. We extract a set of properties that these abstractions satisfy, which can be used in automatic abstraction for explanation generation.

ICAPS Conference 2024 Conference Paper

Explaining Plan Quality Differences

• Benjamin Krarup
• Amanda Jane Coles
• Derek Long
• David E. Smith 0001

We describe a method for explaining the differences between the quality of plans produced for similar planning problems. The method exploits a process of abstracting away details of the planning problems until the difference in solution quality they support has been minimised. We give a general definition of a valid abstraction of a planning problem. We then give the details of the implementation of a number of useful abstractions. Finally, we present a breadth-first search algorithm for finding suitable abstractions for explanations; and detail the results of an evaluation of the approach.

ICAPS Conference 2022 Conference Paper

Evaluating Plan-Property Dependencies: A Web-Based Platform and User Study

• Rebecca Eifler
• Martim Brandão
• Amanda Jane Coles
• Jeremy Frank
• Jörg Hoffmann 0001

The trade-offs between different desirable plan properties -- e. g. PDDL temporal plan preferences -- are often difficult to understand. Recent work addresses this by iterative planning with explanations elucidating the dependencies between such plan properties. Users can ask questions of the form ``Why does the plan not satisfy property p? '', which are answered by ``Because then we would have to forego q''. It has been shown that such dependencies can be computed reasonably efficiently. But is this form of explanation actually useful for users? We run a large crowd-worker user study (N=100 in each of 3 domains) evaluating that question. To enable such a study in the first place, we contribute a Web-based platform for iterative planning with explanations, running in standard browsers. Comparing users with vs. without access to the explanations, we find that the explanations enable users to identify better trade-offs between the plan properties, indicating an improved understanding of the planning task.

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.

ICAPS Conference 2021 Conference Paper

Explaining Path Plan Optimality: Fast Explanation Methods for Navigation Meshes Using Full and Incremental Inverse Optimization

• Martim Brandão
• Amanda Jane Coles
• Daniele Magazzeni

Path planners are important components of various products from video games to robotics, but their output can be counter-intuitive due to problem complexity. As a step towards improving the understanding of path plans by various users, here we propose methods that generate explanations for the optimality of paths. Given the question "why is path A optimal, rather than B which I expected? ", our methods generate an explanation based on the changes to the graph that make B the optimal path. We focus on the case of path planning on navigation meshes, which are heavily used in the computer game industry and robotics. We propose two methods - one based on a single inverse-shortest-paths optimization problem, the other incrementally solving complex optimization problems. We show that these methods offer computation time improvements of up to 3 orders of magnitude relative to domain-independent search-based methods, as well as scaling better with the length of explanations. Finally, we show through a user study that, when compared to baseline cost-based explanations, our explanations are more satisfactory and effective at increasing users' understanding of problems.

ICAPS Conference 2019 Conference Paper

Mixed Discrete Continuous Non-Linear Planning through Piecewise Linear Approximation

• Elad Denenberg
• Amanda Jane Coles

Reasoning with continuously changing numeric quantities is vital to applying planners in many real-world scenarios. Several planners capable of doing this have been developed recently. Scalability remains a challenge for such planners, especially those that reason with non-linear continuous change. In this paper, we present a novel approach to reasoning with non-linear domains. Bounding the problem using linear over and under-estimators, allows us to use scalable planners that handle linear change to find plans for non-linear domains. We compare the performance of our approach to existing planners on several domains and demonstrate that our planner can achieve state-of-the-art performance in non-linear planning.

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.

ECAI Conference 2016 Conference Paper

Optimal Simple Strategies for Persuasion

• Elizabeth Black
• Amanda Jane Coles
• Christopher Hampson

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.

ECAI Conference 2012 Conference Paper

Opportunistic Branched Plans to Maximise Utility in the Presence of Resource Uncertainty

• Amanda Jane Coles

In many applications, especially autonomous exploration, there is a trade-off between operational safety, forcing conservatism about resource usage; and maximising utility, requiring high resource utilisation. In this paper we consider a method of generating plans that maintain this conservatism whilst allowing exploitation of situations where resource usage is better than pessimistically estimated. We consider planning problems with soft goals, each with a violation cost. The challenge is to maximise utility (minimise the violation cost paid) whilst maintaining confidence that the plan will execute within the specified limits. We first show how forward search planning can be extended to generate such plans. Then we extend this to build branched plans: tree structures labelled with conditions on executing branches. Lower cost branches can be followed if their conditions are met. We demonstrate that the use of such plans can dramatically increase utility whilst still obeying strict safety constraints.

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.

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.

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.

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.