Derek Long

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.

JAIR Journal 2025 Journal Article

Path-Planning on a Spherical Surface with Disturbances and Exclusion Zones

• Jonathan Smith
• Samuel Hall
• George Coombs
• Harrison Abbot
• Ayat Fekry
• Michael A. S. Thorne
• Derek Long
• Maria Fox

An algorithm is presented for path-planning in a non-uniform spheroid mesh containing exclusion zones, vector and scalar fields. The mesh models physical environments such as ocean regions, together with a variety of environmental phenomena such as wind, current and ice conditions which impact on routing decisions. The path-planning method can be used to optimise the travel time of journeys between points in the mesh. We provide the algorithmic details and the mathematical foundations of the algorithms. To demonstrate that the method has basic desirable properties, we show that long paths in unconstrained regions of the mesh closely approximate great circle arcs. We go on to show that the method path-plans efficiently in environments with complex interacting conditions.

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.

JAIR Journal 2021 Journal Article

Contrastive Explanations of Plans through Model Restrictions

• Benjamin Krarup
• Senka Krivic
• Daniele Magazzeni
• Derek Long
• Michael Cashmore
• David E. Smith

In automated planning, the need for explanations arises when there is a mismatch between a proposed plan and the user’s expectation. We frame Explainable AI Planning as an iterative plan exploration process, in which the user asks a succession of contrastive questions that lead to the generation and solution of hypothetical planning problems that are restrictions of the original problem. The object of the exploration is for the user to understand the constraints that govern the original plan and, ultimately, to arrive at a satisfactory plan. We present the results of a user study that demonstrates that when users ask questions about plans, those questions are usually contrastive, i.e. “why A rather than B?”. We use the data from this study to construct a taxonomy of user questions that often arise during plan exploration. Our approach to iterative plan exploration is a process of successive model restriction. Each contrastive user question imposes a set of constraints on the planning problem, leading to the construction of a new hypothetical planning problem as a restriction of the original. Solving this restricted problem results in a plan that can be compared with the original plan, admitting a contrastive explanation. We formally define model-based compilations in PDDL2.1 for each type of constraint derived from a contrastive user question in the taxonomy, and empirically evaluate the compilations in terms of computational complexity. The compilations were implemented as part of an explanation framework supporting iterative model restriction. We demonstrate its benefits in a second user study.

ICAPS Conference 2017 Conference Paper

Boosting Search Guidance in Problems with Semantic Attachments

• Sara Bernardini
• Maria Fox 0001
• Derek Long
• Chiara Piacentini

Most applications of planning to real problems involve complex and often non-linear equations, including matrix operations. PDDL is ill-suited to express such calculations since it only allows basic operations between numeric fluents. To remedy this restriction, a generic PDDL planner can be connected to a specialised advisor, which equips the planner with the ability to carry out sophisticated mathematical operations. Unlike related techniques based on semantic attachment, our planner is able to exploit an approximation of the numeric information calculated by the advisor to compute informative heuristic estimators. Guided by both causal and numeric information, our planning framework outperforms traditional approaches, especially against problems with numeric goals. We provide evidence of the power of our solution by successfully solving four completely different problems.

AAAI Conference 2017 Conference Paper

Deterministic versus Probabilistic Methods for Searching for an Evasive Target

• Sara Bernardini
• Maria Fox
• Derek Long
• Chiara Piacentini

Several advanced applications of autonomous aerial vehicles in civilian and military contexts involve a searching agent with imperfect sensors that seeks to locate a mobile target in a given region. Effectively managing uncertainty is key to solving the related search problem, which is why all methods devised so far hinge on a probabilistic formulation of the problem and solve it through branch-and-bound algorithms, Bayesian filtering or POMDP solvers. In this paper, we consider a class of hard search tasks involving a target that exhibits an intentional evasive behaviour and moves over a large geographical area, i. e. , a target that is particularly difficult to track down and uncertain to locate. We show that, even for such a complex problem, it is advantageous to compile its probabilistic structure into a deterministic model and use standard deterministic solvers to find solutions. In particular, we formulate the search problem for our uncooperative target both as a deterministic automated planning task and as a constraint programming task and show that in both cases our solution outperforms POMDPs methods.

ICAPS Conference 2016 Conference Paper

A Compilation of the Full PDDL+ Language into SMT

• Michael Cashmore
• Maria Fox 0001
• Derek Long
• Daniele Magazzeni

Planning in hybrid systems is important for dealing with real-world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modelling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long. The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems.

AAAI Conference 2016 Conference Paper

Heuristic Planning for Hybrid Systems

• Wiktor Piotrowski
• Maria Fox
• Derek Long
• Daniele Magazzeni
• Fabio Mercorio

Planning in hybrid systems has been gaining research interest in the Artificial Intelligence community in recent years. Hybrid systems allow for a more accurate representation of real world problems, though solving them is very challenging due to complex system dynamics and a large model feature set. We developed DiNo, a new planner designed to tackle problems set in hybrid domains. DiNo is based on the discretise and validate approach and uses the novel Staged Relaxed Planning Graph+ (SRPG+) heuristic.

IJCAI Conference 2016 Conference Paper

Heuristic Planning for PDDL+ Domains

• Wiktor Piotrowski
• Maria Fox
• Derek Long
• Daniele Magazzeni
• Fabio Mercorio

Planning with hybrid domains modelled in PDDL+ has been gaining research interest in the Automated Planning community in recent years. Hybrid domain models capture a more accurate representation of real world problems that involve continuous processes than is possible using discrete systems. However, solving problems represented as PDDL+ domains is very challenging due to the construction of complex system dynamics, including non-linear processes and events. In this paper we introduce DiNo, a new planner capable of tackling complex problems with non-linear system dynamcs governing the continuous evolution of states. DiNo is based on the discretise-and-validate approach and uses the novel Staged Relaxed Planning Graph+ (SRPG+) heuristic, which is introduced in this paper. Although several planners have been developed to work with subsets of PDDL+ features, or restricted forms of processes, DiNo is currently the only heuristic planner capable of handling non-linear system dynamics combined with the full PDDL+ feature set.

ICAPS Conference 2016 Conference Paper

Leveraging Probabilistic Reasoning in Deterministic Planning for Large-Scale Autonomous Search-and-Tracking

• Sara Bernardini
• Maria Fox 0001
• Derek Long
• Chiara Piacentini

Search-And-Tracking (SaT) is the problem of searching for a mobile target and tracking it once it is found. Since SaT platforms face many sources of uncertainty and operational constraints, progress in the field has been restricted to simple and unrealistic scenarios. In this paper, we propose a new hybrid approach to SaT that allows us to successfully address large-scale and complex SaT missions. The probabilistic structure of SaT is compiled into a deterministic planning model and Bayesian inference is directly incorporated in the planning mechanism. Thanks to this tight integration between automated planning and probabilistic reasoning, we are able to exploit the power of both approaches. Planning provides the tools to efficiently explore big search spaces, while Bayesian inference, by readily combining prior knowledge with observable data, allows the planner to make more informed and effective decisions. We offer experimental evidence of the potential of our approach.

ECAI Conference 2016 Conference Paper

Planning Using Actions with Control Parameters

• Emre Savas
• Maria Fox 0001
• Derek Long
• Daniele Magazzeni

Although PDDL is an expressive modelling language, a significant limitation is imposed on the structure of actions: the parameters of actions are restricted to values from finite (in fact, explicitly enumerated) domains. There is one exception to this, introduced in PDDL2. 1, which is that durative actions may have durations that are chosen (possibly subject to explicit constraints in the action models) by the planner. A motivation for this limitation is that it ensures that the set of grounded actions is finite and, ignoring duration, the branching factor of action choices at a state is therefore finite. Although the duration parameter can make this choice infinite, very few planners support this possibility, but restrict themselves to durative actions with fixed durations. In this paper we motivate a proposed extension to PDDL to allow actions with infinite domain parameters, which we call control parameters. We illustrate reasons for using this modelling feature and then describe a planning approach that can handle domains that exploit it, implemented in a new planner, POPCORN (Partial-Order Planning with Constrained Real Numerics). We show that this approach scales to solve interesting problems.

ICAPS Conference 2016 Conference Paper

Solving Realistic Unit Commitment Problems Using Temporal Planning: Challenges and Solutions

• Chiara Piacentini
• Daniele Magazzeni
• Derek Long
• Maria Fox 0001
• Chris J. Dent

When facing real world planning problems, standard planners are often inadequate and enhancement of the current techniques are required. In this paper we present the challenges that we have faced in solving the Unit Commitment (UC) problem, a well-known problem in the electrical power industry for which current best methods are based on Mixed Integer Programming (MIP). Typical UC instances involve hundreds or even thousands of generating units, pushing the scalability of state of the art planners beyond their limits. Furthermore, UC is characterised by state-dependent action costs, a feature that not many domain independent planners can efficiently handle. In this paper we focus on the challenge of making domain-independent planning competitive with the MIP method on realistic-sized UC instances. We present the results of our investigation into modelling the UC problem as a temporal planning problem, and show how we scaled up from handling fewer than 10 generating units to more than 400, obtaining solutions almost as high quality as those generated by MIP. We conclude by discussing future directions for temporal planning in this domain, that lie beyond what can be modelled and solved using MIP methods.

ECAI Conference 2016 Conference Paper

Temporal Planning with Constants in Context

• Josef Bajada
• Maria Fox 0001
• Derek Long

AIJ Journal 2015 Journal Article

An extension of metric temporal planning with application to AC voltage control

• Chiara Piacentini
• Varvara Alimisis
• Maria Fox
• Derek Long

In this paper we explore the deployment of planning techniques to solve a new class of metric temporal planning problems, characterised by the need to manage both plan trajectory constraints and uncontrollable numeric events. This combination gives rise to challenges not previously solved in state-of-the-art planners. We introduce new planning methods to handle these challenges, and demonstrate our approach using a real application domain: voltage control in Alternating Current (AC) electrical networks. Embedding electricity networks in a domain description presents important modelling challenges. We introduce an encapsulated type, Network, the implementation of which is hidden from the planner. The effects of actions trigger complex updates to the state of the network. We distinguish between the direct effects of planned actions, and the indirect effects triggered by them, and we propose a method for integrating a specialised external AC power equation solver with a planner. We consider a new heuristic function that takes into account the next uncontrollable event, and its interaction with active trajectory constraints, when determining the actions that are helpful in a state. This lookahead heuristic also exploits an abstraction of the encapsulated Network type to obtain more informative distance estimates. We conduct experiments to evaluate the benefits of the lookahead heuristic, showing that our approach scales very well with the size of the network and the number of controllable components of the network.

AAAI Conference 2015 Conference Paper

Planning with Numeric Timed Initial Fluents

• Chiara Piacentini
• Maria Fox
• Derek Long

Numeric Timed Initial Fluents represent a new feature in PDDL that extends the concept of Timed Initial Literals to numeric fluents. They are particularly useful to model independent functions that change through time and influence the actions to be applied. Although they are very useful to model real world problems, they are not systematically defined in the family of PDDL languages and they are not implemented in any generic PDDL planner, except for POPF2 and UPMurphi. In this paper we present an extension of the planner POPF2 (POPF-TIF) to handle problems with numeric Timed Initial Fluents. We propose and evaluate two contributions: the first is based on improvements of the heuristic evaluation, while the second considers alternative search algorithms based on a mixture of Enforced Hill Climbing and Best First Search.

ICAPS Conference 2015 Conference Paper

ROSPlan: Planning in the Robot Operating System

• Michael Cashmore
• Maria Fox 0001
• Derek Long
• Daniele Magazzeni
• Bram Ridder
• Arnau Carrera
• Narcís Palomeras
• Natàlia Hurtós

The Robot Operating System (ROS) is a set of software libraries and tools used to build robotic systems. ROS is known for a distributed and modular design. Given a model of the environment, task planning is concerned with the assembly of actions into a structure that is predicted to achieve goals. This can be done in a way that minimises costs, such as time or energy. Task planning is vital in directing the actions of a robotic agent in domains where a causal chain could lock the agent into a dead-end state. Moreover, planning can be used in less constrained domains to provide more intelligent behaviour. This paper describes the ROSP LAN framework, an architecture for embedding task planning into ROS systems. We provide a description of the architecture and a case study in autonomous robotics. Our case study involves autonomous underwater vehicles in scenarios that demonstrate the flexibility and robustness of our approach.

IJCAI Conference 2015 Conference Paper

Temporal Planning with Semantic Attachment of Non-Linear Monotonic Continuous Behaviours

• Josef Bajada
• Maria Fox
• Derek Long

Non-linear continuous change is common in realworld problems, especially those that model physical systems. We present an algorithm which builds upon existent temporal planning techniques based on linear programming to approximate non-linear continuous monotonic functions. These are integrated through a semantic attachment mechanism, allowing external libraries or functions that are difficult to model in native PDDL to be evaluated during the planning process. A new planning system implementing this algorithm was developed and evaluated. Results show that the addition of this algorithm to the planning process can enable it to solve a broader set of planning problems.

ICRA Conference 2014 Conference Paper

AUV mission control via temporal planning

• Michael Cashmore
• Maria Fox 0001
• Tom Larkworthy
• Derek Long
• Daniele Magazzeni

Underwater installations require regular inspection and maintenance. We are exploring the idea of performing these tasks using an autonomous underwater vehicle, achieving persistent autonomous behaviour in order to avoid the need for frequent human intervention. In this paper we consider one aspect of this problem, which is the construction of a suitable plan for a single inspection tour. In particular we generate a temporal plan that optimises the time taken to complete the inspection mission. We report on physical trials with the system at the Diver and ROV driver Training Center in Fort William, Scotland, discussing some of the lessons learned.

ICAPS Conference 2014 Conference Paper

Planning the Behaviour of Low-Cost Quadcopters for Surveillance Missions

• Sara Bernardini
• Maria Fox 0001
• Derek Long

Micro Aerial Vehicles (MAVs) are increasingly regarded as a valid low-cost alternative to UAVs and ground robots in surveillance missions and a number of other civil and military applications. Research on autonomous MAVs is still in its infancy and has focused almost exclusively on integrating control and computer vision techniques to achieve reliable autonomous flight. In this paper, we describe our approach to using automated planning in order to elicit high-level intelligent behaviour from autonomous MAVs engaged in surveillance applications. Planning offers effective tools to handle the unique challenges faced by MAVs that relate to their fast and unstable dynamics as well as their low endurance and small payload capabilities. We demonstrate our approach by focusing on the "Parrot AR. Drone2. 0" quadcopter and Search-and-Tracking missions, which involve searching for a mobile target and tracking it after it is found.

ICAPS Conference 2013 Conference Paper

Autonomous Search and Tracking via Temporal Planning

• Sara Bernardini
• Maria Fox 0001
• Derek Long
• John Bookless

Search And Tracking (SAT) is the problem of searching for a mobile target and tracking it after it is found. As this problem has important applications in search-and-rescue and surveillance operations, recently there has been increasing interest in equipping unmanned aerial vehicles (UAVs) with autonomous SAT capabilities. State-of-the-art approaches to SAT rely on estimating the probability density function of the target's state and solving the search control problem in a greedy fashion over a short planning horizon (typically, a one-step lookahead). These techniques suffer high computational cost, making them unsuitable for complex problems. In this paper, we propose a novel approach to SAT, which allows us to handle big geographical areas, complex target motion models and long-term operations. Our solution is to track the target reactively while it is in view and to plan a recovery strategy that relocates the target every time it is lost, using a high-performing automated planning tool. The planning problem consists of deciding where to search and which search patterns to use in order to maximise the likelihood of recovering the target. We show experimental results demonstrating the potential of our approach.

ICAPS Conference 2013 Conference Paper

Challenge: Modelling Unit Commitment as a Planning Problem

• Joshua Campion
• Chris J. Dent
• Maria Fox 0001
• Derek Long
• Daniele Magazzeni

Unit Commitment is a fundamental problem in power systems engineering, deciding which generating units to switch on, and when to switch them on, in order to efficiently meet anticipated demand. It has traditionally been solved as a Mixed Integer Programming (MIP) problem but upcoming changes to the power system drastically increase the MIP solution time. In this paper, we discuss the benefits that using planning may have over the established methods. We provide a formal description of Unit Commitment, and we present its formulation as MIP and as a planning problem. This is a novel and interesting application area for planning, with features that make the domain challenging for current planners.

ICAPS Conference 2013 Conference Paper

Combining a Temporal Planner with an External Solver for the Power Balancing Problem in an Electricity Network

• Chiara Piacentini
• Varvara Alimisis
• Maria Fox 0001
• Derek Long

The electricity network balancing problem consists of ensuring that the electricity demands of the consumers are met by the committed supply. Constraints are imposed on the different elements of the network, so that damage to the equipment is prevented when transformers are stepped up or down, or generation is increased. We consider this problem within zones, which are sub-networks constructed using carefully chosen decomposition principles. The automation of decision making in electricity networks is a step forward in their management which is necessary for coping with the increase in power system complexity that we expect in the near term. In this paper we explore the deployment of planning techniques to solve the zone-balancing problem. Embedding electricity networks in a domain description presents new challenges for planning. The key point is that the propagation of information requires complex updates to the state when an action is applied. We have developed a method in which the computation of the critical numeric quantities is performed calling an external power flow equation solver, demonstrating a clean interface between the planner and this domain-specific computation. This solver allows us to move the power flow computations outside of the planning process and update the values efficiently. We also examine a second important feature of this problem, which is the interaction between exogenous events and constraints over the entire plan trajectory within a zone.

ICAPS Conference 2012 Conference Paper

Plan-Based Policy-Learning for Autonomous Feature Tracking

• Maria Fox 0001
• Derek Long
• Daniele Magazzeni

Mapping and tracking biological ocean features, such as harmful algal blooms, is an important problem in the environmental sciences. The problem exhibits a high degree of uncertainty, because of both the dynamic ocean context and the challenges of sensing. Plan-based policy learning has been shown to be a powerful technique for obtaining robust intelligent behaviour in the face of uncertainty. In this paper we apply this technique in simulation, to the problem of tracking the outer edge of 2D biological features, such as the surfaces of harmful algal blooms. We show that plan-based policy-learning leads to highly accurate tracking in simulation, even in situations where the uncertainty governing the shape of the patch cannot be directly modelled. We present simulation results that give confidence that the approach could work in practice. We are now collaborating with ocean scientists at MBARI to perform physical tests at sea.

ICAPS Conference 2012 Conference Paper

Planning Modulo Theories: Extending the Planning Paradigm

• Peter Gregory
• Derek Long
• Maria Fox 0001
• J. Christopher Beck

Considerable effort has been spent extending the scope of planning beyond propositional domains to include, for example, time and numbers. Each extension has been designed as a separate specific semantic enrichment of the underlying planning model, with its own syntax and customised integration into a planning algorithm. Inspired by work on SAT Modulo Theories (SMT) in the SAT community, we develop a modelling language and planner that treat arbitrary first order theories as parameters. We call the approach Planning Modulo Theories (PMT). We introduce a modular language to represent PMT problems and demonstrate its benefits over PDDL in expressivity and compactness. We present a generalisation of the $h_{max}$ heuristic that allows our planner, PMTPlan, to automatically reason about arbitrary theories added as modules. Over several new and existing benchmarks, exploiting different theories, we show that PMTPlan can significantly out-perform an existing planner using PDDL models.

ICAPS Conference 2011 Conference Paper

Automatic Construction of Efficient Multiple Battery Usage Policies

• Maria Fox 0001
• Derek Long
• Daniele Magazzeni

Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem. We describe the approach we have adopted to modelling and solving this problem, seen as a Markov Decision Problem, building effective policies for battery switching in the face of stochastic load profiles. Our solution exploits and adapts several existing techniques from the planning literature and leads to the construction of policies that significantly outperform those that are currently in use and the best published solutions to the battery management problem. We achieve solutions that achieve more than 99\% efficiency compared with the theoretical limit and do so with far fewer battery switches than existing policies. We describe the approach in detail and provide empirical evaluation demonstrating its effectiveness.

IJCAI Conference 2011 Conference Paper

Automatic Construction of Efficient Multiple Battery Usage Policies

• Maria Fox
• Derek Long
• Daniele Magazzeni

There is a huge and growing number of systems that depend on batteries for power supply, ranging from small mobile devices to large high-powered systems such as electrical substations. In most of these systems, there are significant user-benefits or engineering reasons to base the supply on multiple batteries, with load being switched between batteries by a control system. The key to efficient use of multiple batteries lies in the design of effective policies for the management of the switching of load between them. This paper describes work in which we show that automated planning can produce much more effective policies than other approaches to multiple battery load management in the literature.

AAAI Conference 2011 Conference Paper

Exploiting Path Refinement Abstraction in Domain Transition Graphs

• Peter Gregory
• Derek Long
• Craig McNulty
• Susan Murphy

Partial Refinement A-Star (PRA ) is an abstraction technique, based on clustering nearby nodes in graphs, useful in large path-planning problems. Abstracting the underlying graph yields a simpler problem whose solution can be used, by refinement, as a guide to a solution to the original problem. A fruitful way to view domain independent planning problems is as a collection of multi-valued variables that must perform synchronised transitions through graphs of possible values, where the edges are defined by the domain actions. Planning involves finding efficient paths through Domain Transition Graphs (DTGs). In problems where these graphs are large, planning can be prohibitively expensive. In this paper we explore two ways to exploit PRA in DTGs.

ECAI Conference 2010 Conference Paper

Constraint Based Planning with Composable Substate Graphs

• Peter Gregory
• Derek Long
• Maria Fox 0001

Constraint satisfaction techniques provide powerful inference algorithms that can prune choices during search. Constraint-based approaches provide a useful complement to heuristic search optimal planners. We develop a constraint-based model for cost-optimal planning that uses global constraints to improve the inference in 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.

AIJ Journal 2009 Journal Article

Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners

• Alfonso E. Gerevini
• Patrik Haslum
• Derek Long
• Alessandro Saetti
• Yannis Dimopoulos

The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field. We present an extension of pddl, called pddl3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into pddl2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.

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

Metric temporal planning involves both selecting and organising actions to satisfy the goals and also assigning to each of these actions its start time and, where necessary, its duration. The assignment of start times to actions is a central concern of scheduling. In pddl2. 1, the widely adopted planning domain description language standard, metric temporal planning problems are described using actions with durations. A large number of planners have been developed to handle this language, but the great majority of them are fundamentally limited in the class of temporal problems they can solve. In this paper, we review the source of this limitation and present an approach to metric temporal planning that is not so restricted. Our approach links planning and scheduling algorithms into a planner, Crikey, that can successfully tackle a wide range of temporal problems. We show how Crikey can be simplified to solve a wide and interesting subset of metric temporal problems, while remaining competitive with other temporal planners that are unable to handle required concurrency. We provide empirical data comparing the performance of this planner, Crikey SHE, our original version, Crikey, and a range of other modern temporal planners. Our contribution is to describe the first competitive planner capable of solving problems that require concurrent actions.

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

Learning Macro-Actions for Arbitrary Planners and Domains

• M. A. Hakim Newton
• John Levine
• Maria Fox 0001
• Derek Long

Many complex domains and even larger problems in simple domains remain challenging in spite of the recent progress in planning. Besides developing and improving planning technologies, re-engineering a domain by utilising acquired knowledge opens up a potential avenue for further research. Moreover, macro-actions, when added to the domain as additional actions, provide a promising means by which to convey such knowledge. A macro-action, or macro in short, is a group of actions selected for application as a single choice. Most existing work on macros exploits properties explicitly specific to the planners or the domains. However, such properties are not likely to be common with arbitrary planners or domains. Therefore, a macro learning method that does not exploit any structural knowledge about planners or domains explicitly is of immense interest. This paper presents an offline macro learning method that works with arbitrarily chosen planners and domains. Given a planner, a domain, and a number of example problems, the learning method generates macros from plans of some of the given problems under the guidance of a genetic algorithm. It represents macros like regular actions, evaluates them individually by solving the remaining given problems, and suggests individual macros that are to be added to the domain permanently. Genetic algorithms are automatic learning methods that can capture inherent features of a system using no explicit knowledge about it. Our method thus does not strive to discover or utilise any structural properties specific to a planner or a domain.

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.

ICAPS Conference 2006 Conference Paper

Plan Stability: Replanning versus Plan Repair

• Maria Fox 0001
• Alfonso Emilio Gerevini
• Derek Long
• Ivan Serina

The ultimate objective in planning is to construct plans for execution. However, when a plan is executed in a real environment it can encounter differences between the expected and actual context of execution. These differences can manifest as divergences between the expected and observed states of the world, or as a change in the goals to be achieved by the plan. In both cases, the old plan must be replaced with a new one. In replacing the plan an important consideration is plan stability. We compare two alternative strategies for achieving the {em stable} repair of a plan: one is simply to replan from scratch and the other is to adapt the existing plan to the new context. We present arguments to support the claim that plan stability is a valuable property. We then propose an implementation, based on LPG, of a plan repair strategy that adapts a plan to its new context. We demonstrate empirically that our plan repair strategy achieves more stability than replanning and can produce repaired plans more efficiently than replanning.

AIJ Journal 2006 Journal Article

Robot introspection through learned hidden Markov models

• Maria Fox
• Malik Ghallab
• Guillaume Infantes
• Derek Long

In this paper we describe a machine learning approach for acquiring a model of a robot behaviour from raw sensor data. We are interested in automating the acquisition of behavioural models to provide a robot with an introspective capability. We assume that the behaviour of a robot in achieving a task can be modelled as a finite stochastic state transition system. Beginning with data recorded by a robot in the execution of a task, we use unsupervised learning techniques to estimate a hidden Markov model (HMM) that can be used both for predicting and explaining the behaviour of the robot in subsequent executions of the task. We demonstrate that it is feasible to automate the entire process of learning a high quality HMM from the data recorded by the robot during execution of its task. The learned HMM can be used both for monitoring and controlling the behaviour of the robot. The ultimate purpose of our work is to learn models for the full set of tasks associated with a given problem domain, and to integrate these models with a generative task planner. We want to show that these models can be used successfully in controlling the execution of a plan. However, this paper does not develop the planning and control aspects of our work, focussing instead on the learning methodology and the evaluation of a learned model. The essential property of the models we seek to construct is that the most probable trajectory through a model, given the observations made by the robot, accurately diagnoses, or explains, the behaviour that the robot actually performed when making these observations. In the work reported here we consider a navigation task. We explain the learning process, the experimental setup and the structure of the resulting learned behavioural models. We then evaluate the extent to which explanations proposed by the learned models accord with a human observer's interpretation of the behaviour exhibited by the robot in its execution of the task.

IJCAI Conference 2005 Conference Paper

Abstraction-based Action Ordering in Planning

• Maria Fox
• Derek Long
• Julie

Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that the detection and exploitation of symmetric structure in planning problems can dramatically reduce the size of the search space and the time taken to find a solution. We present the idea of using an abstraction of the problem domain to reveal symmetric structure and guide the navigation of the search space. We show that this is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerful alternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of almost symmetry is defined and results are presented showing that proactive exploitation of almost symmetry can improve the performance of a heuristic forward search planner.

ECAI Conference 2004 Conference Paper

An Investigation into the Expressive Power of PDDL2. 1

• Maria Fox 0001
• Derek Long
• Keith Halsey

ECAI Conference 2004 Conference Paper

Multiple Relaxations in Temporal Planning

• Keith Halsey
• Derek Long
• Maria Fox 0001

ECAI Conference 2004 Conference Paper

Planning with Numeric Varibles in Multiobjective Planning

• Antonio Garrido 0002
• Derek Long

ICAPS Conference 2003 Conference Paper

Exploiting a Graphplan Framework in Temporal Planning

• Derek Long
• Maria Fox 0001

Graphplan has proved a popular and successful basis for a succession of extensions. An extension to handle temporal planning is a natural one to consider, because of the seductively time-like structure of the layers in the plan graph. TGP and TPSys are both examples of temporal planners that have exploited the Graphplan foundation. However, both of these systems (including both versions of TPSys) exploit the graph to represent a uniform flow of time. In this paper we describe an alternative approach, in which the graph is used to represent the purely logical structuring of the plan, with temporal constraints being managed separately (although not independently). The approach uses a linear constraint solver to ensure that temporal durations are correctly respected. The resulting planner offers an interesting alternative to the other approaches, offering an important extension in expressive power.

ECAI Conference 2002 Conference Paper

A Temporal Planning System for Durative Actions of PDDL2. 1

• Antonio Garrido 0002
• Maria Fox 0001
• Derek Long

ICAPS Conference 2002 Conference Paper

Extending the Exploitation of Symmetries in Planning

• Maria Fox 0001
• Derek Long

Highly symmetric problems result in redundant search effort which can render apparently simple problems intractable. Whilst the potential benefits of symmetry-breaking have been explored in the broader search and constraint satisfaction community there has been relatively little interest in the exploitation of this potential in planning. An initial exploration of the benefits of symmetry-breaking in a Graphplan framework, by Fox and Long in 1999 yielded promising results but failed to take into account the importance of identifying and exploiting new symmetries that arise during the search process. In this paper we extend the symmetry exploitation ideas described in Fox and Long (1999) to handle new symmetries and report results obtained from a range of planning problems.

ICAPS Conference 2002 Conference Paper

The Third International Planning Competition: Temporal and Metric Planning

• Maria Fox 0001
• Derek Long

The International Planning Competitions, run by Drew Mc- Dermott in 1998 and Fahiem Bacchus in 2000, have provided an important spur to the planning community, encouraging the development of planning technology and of a wide selection of planning bench mark domains. One of the most important contributions has been the introduction of a widely accepted standard for domain description, Drew McDermott’s PDDL language (McDermott 2000), leading to the sharing of domains and planning systems. An equally important outcome, which has been extremely beneficial to the community, has been that planning research has made rapid progress in the four years since the competitions began and has risen to many interesting challenges. A complaint that has been often levelled at competitions in various research communities (theorem proving, natural language understanding, etc.,) is that they have tended to encourage a focus on winning for its own sake, rather than on tackling real problems that might have longer term interest for application. Competitions can have the negative effect of turning developers’ attention inwards so that systems are honed on artificial benchmark problems at which they can excel, rather than extended to meet real challenges. A consequence of this is that potential participants can be put off taking part in the competition if their technology is not tailored for efficient solution of such problems. The community is at risk of being deprived of seeing exciting and adventurous new developments whilst simple and unscaleable approaches occupy the limelight. Although this has not yet become a serious issue for the planning competitions it is a real danger and it is important to anticipate the danger and try to ensure that the competition remains relevant to the wider planning community. With these points in mind we decided to focus the 2002 competition on planning with temporal and metric domains. It is generally agreed that temporal modelling and reasoning is essential for the application of planning to practical problems, and certain high-profile application areas, such as space and aerospace applications, have encouraged developers to turn their attention towards these issues. Although some developers have already considered the management of temporal constraints in their planning systems this has not been widespread and there has been little agreement over the modelling of time. Certainly there have been no commonly accepted standards for modelling temporal planning domains and no temporal bench mark problems. This document briefly introduces the objectives of the 2002 competition and the extensions we have made to PDDL to support temporal modelling. Finally, we outline the structure of the competition, in terms of the tracks being run and the domains being considered in those tracks.

ICAPS Conference 2000 Conference Paper

Automatic Synthesis and Use of Generic Types in Planning

• Derek Long
• Maria Fox 0001

I), mmin-indel)endent phmningconcentrates, m the gem, ’ral algorithmic issues raised in exploring a search. ~p~u’egeneratedin fin(ling sequencesof state-transition fllnc: t. ioLuS betweenan initial state anda goal state. h is ackuowledgcd that domain-dependent planning, in whi, ’h fi, atures of specific domains~e exploited in this search, offers opportunities for moreefficient planning, but at the price of greater effort in the, Iomain-en(’oding. The work presented in this paper is concerned with giving a domain-independentplmlnrr ~u’~: ess to certain kinds of domain-sl)ecificheuristit’s without the need for additional domainencoding effort. This is achieve, l by automatically identifying g~: nerie typ(: s from WI’ltlps planning domaindescriptions. Generic types are higher order types allowing the categorisation of domains(and componentsof domains) into dolnain classe. s, inchading the commonly occurring Ounsportation domain class. Weshow how!!w generic type structure of (lomains can begin to be exploited to in(: rc~me planner efficiency. Aa interesting property of the work described here is that domain componentswhich wouldnot e. a. sily be rccognised, iff the human. ~. ’~ transportation problemscan turn out to I, ave an underlyingtraztsportation character which(’mr be,,xpioited by the application of st~mdardtransportat. i, m, Iomain t, euristics. The an, ’flyses described here are r, mtpletely planner-independentand contribute to mt increasing collection of p~t, -pl, tnning analysis tools whichhelp to incrra. se peribrmanceof planners by decomposingand understanding the stru(’tures rff planuiug prol)lems before planners ~tre applied.

ICAPS Conference 2000 Conference Paper

Utilizing Automatically Inferred Invariants in Graph Construction and Search

• Maria Fox 0001
• Derek Long

In this paper we explore the relative importanceof persistent mid non-persistent mutexrelations in the perfornmnce of Graphpl~m-basedplanners. Wealso show tlmadvantages of pre-compiling persistent mutexreindons. ITsing TIMwe are ableto generate, during a prepr. cessing analysis, all of the persistent Ifinary nmtex relations that wouldbe infi, rred by Graphplanduring graph construction. Weshowhowthe efficient storage of: mtd access to, these pre-processed persistent xnutexes yiehts a inodest improvementin graph construction imrformance. Wefurther demonstrate that the process by which these persistent mutexes are idemilied can, in certain kinds of domain, allow the exploitation of binary nmtexrelations whichaxe inaccessible to GraphlflmL"O, re present The Island of Sodor, a simph’ planning domaincharacterizing a class of domainsin which certain persistent mutexesare present but are not detectable by Graphpl-’~n during graph constructi. n. Weshowthat the expkfitation of those hidden binary mutexes makes problems in this kind of domain trivially solvable by STAN, wherethey are intractable for other Graphplan-basedplanners.

IJCAI Conference 1999 Conference Paper

The Detection and Exploitation of Symmetry in Planning Problems

• Maria Fox
• Derek Long

Many planning problems exhibit a high degree of symmetry that cannot yet be exploited successfully by modern planning technology. For example, problems in the Gripper domain, in which a robot with two grippers must transfer balls from one room to another, are trivial to the human problem-solver because the high degree of symmetry in the domain means that the order in which pairs of balls are transported is irrelevant to the length of the shortest transportation plan. However, planners typically search all possible orderings giving rise to an exponential explosion of the search space. This paper describes a way of detecting and exploiting symmetry in the solution of problems that demonstrate these characteristics. We have implemented our techniques in STAN, a Graphplan-based planner that uses state analysis techniques in a number of ways to exploit the underlying structures of domains. We have achieved a dramatic improvement in performance in solving problems exhibiting symmetry. We present a range of results and indicate the further developments we are now pursuing.

IJCAI Conference 1997 Conference Paper

Content Ordering in the Generation of Persuasive Discourse

• Chris Reed
• Derek Long

A framework is summarized which supports the planning of natural language argument structure. One key aspect of natural argument is the order in which components are presented. This is in part responsible for both the coherency and persuasive effect of an argument. One means of effecting such ordering is proposed, and an overview is provided of the various classes of ordering heuristics. These heuristics are based upon insights offered by rhetoric texts, psychological research, and a corpus study. Finally, it is demonstrated that such an approach can also contribute to the generation of surface textual features including formatting, punctuation and clue words.

KER Journal 1989 Journal Article

A review of temporal logics

• Derek Long

Abstract A series of temporal reasoning tasks are identified which motivate the consideration and application of temporal logics in artificial intelligence. There follows a discussion of the broad issues involved in modelling time and constructing a temporal logic. The paper then presents a detailed review of the major approaches to temporal logics: first-order logic approaches, modal temporal logics and reified temporal logics. The review considers the most significant exemplars within the various approaches, including logics due to Russell, Hayes and McCarthy, Prior, McDermott, Allen, Kowalski and Sergot. The logics are compared and contrasted, particularly in their treatments of change and action, the roles they seek to fulfil and the underlying models of time on which they rest. The paper concludes with a brief consideration of the problem of granularity—a problem of considerable significance in temporal reasoning, which has yet to be satisfactorily treated in a temporal logic.