Amanda 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%.

AAMAS Conference 2022 Conference Paper

Explainability in Multi-Agent Path/Motion Planning: User-study-driven Taxonomy and Requirements

• Martim Brandao
• Masoumeh Mansouri
• Areeb Mohammed
• Paul Luff
• Amanda Coles

Multi-Agent Path Finding (MAPF) and Multi-Robot Motion Planning (MRMP) are complex problems to solve, analyze and build algorithms for. Automatically-generated explanations of algorithm output, by improving human understanding of the underlying problems and algorithms, could thus lead to better user experience, developer knowledge, and MAPF/MRMP algorithm designs. Explanations are contextual, however, and thus developers need a good understanding of the questions that can be asked about algorithm output, the kinds of explanations that exist, and the potential users and uses of explanations in MAPF/MRMP applications. In this paper we provide a first step towards establishing a taxonomy of explanations, and a list of requirements for the development of explainable MAPF/MRMP planners. We use interviews and a questionnaire with expert developers and industry practitioners to identify the kinds of questions, explanations, users, uses, and requirements of explanations that should be considered in the design of such explainable planners. Our insights cover a diverse set of applications: warehouse automation, computer games, and mining.

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.

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.