Derek Long
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Derek Long has a total of 39 co-authors. Here are the top co-authors by number of shared publications:
- Maria Fox
King’s College London
26 shared publications - Amanda Coles
Department of Informatics King's College London Strand Building London WC2R 2LS UK
5 shared publications - Daniele Magazzeni
King's College London
5 shared publications - Andrew Coles
King's College, London, UK
2 shared publications Bram Ridder
Department of Informatics, King’s College London, London, U.K.
2 shared publications- Josef Bajada
Department of Artificial Intelligence University of Malta Msida Malta
2 shared publications
Latest Publications
- 27 January 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Artificial Intelligence
- Vol. 3 (4) , 506-517
Efficient Temporal Piecewise-Linear Numeric Planning With Lazy Consistency Checking
Temporal planning often involves numeric effects that are directly proportional to their action’s duration. These include continuous effects, where a numeric variable is subjected to a rate of change while the action is being executed, and discrete duration-dependent effects, where the variable is updated instantaneously but the magnitude of such change is computed from the action’s duration. When these effects are linear, state-of-the-art temporal planners often make use of linear programming to ensure that these numeric updates are consistent with the chosen start times and durations of the plan’s actions. This is typically done for each evaluated state as a part of the search process. This exhaustive approach is not scalable to solve real-world problems that require long plans, because the size of the linear program becomes larger and slower to solve. In this article, we propose techniques that minimize this overhead by computing these checks more selectively and formulating linear programs that have a smaller footprint. The effectiveness of these techniques is demonstrated on domains that use a mix of discrete and continuous effects, which is typical of real-world planning problems. The resultant planner also outperforms most state-of-the-art temporal–numeric and hybrid planners, in terms of both coverage and scalability.
- 27 January 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Artificial Intelligence
- Vol. 3 (4) , 506-517
Efficient Temporal Piecewise-Linear Numeric Planning With Lazy Consistency Checking
Temporal planning often involves numeric effects that are directly proportional to their action’s duration. These include continuous effects, where a numeric variable is subjected to a rate of change while the action is being executed, and discrete duration-dependent effects, where the variable is updated instantaneously but the magnitude of such change is computed from the action’s duration. When these effects are linear, state-of-the-art temporal planners often make use of linear programming to ensure that these numeric updates are consistent with the chosen start times and durations of the plan’s actions. This is typically done for each evaluated state as a part of the search process. This exhaustive approach is not scalable to solve real-world problems that require long plans, because the size of the linear program becomes larger and slower to solve. In this article, we propose techniques that minimize this overhead by computing these checks more selectively and formulating linear programs that have a smaller footprint. The effectiveness of these techniques is demonstrated on domains that use a mix of discrete and continuous effects, which is typical of real-world planning problems. The resultant planner also outperforms most state-of-the-art temporal–numeric and hybrid planners, in terms of both coverage and scalability.
- 20 January 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automation Science and Engineering
- Vol. 15 (2) , 519-530
Opportunistic Planning in Autonomous Underwater Missions
This paper explores the execution of planned autonomous underwater vehicle (AUV) missions where opportunities to achieve additional utility can arise during execution. The missions are represented as temporal planning problems, with hard goals and time constraints. Opportunities are soft goals with high utility. The probability distributions for the occurrences of these opportunities are not known, but it is known that they are unlikely, so it is not worth trying to anticipate their occurrence prior to plan execution. However, as they are high utility, it is worth trying to address them dynamically when they are encountered, as long as this can be done without sacrificing the achievement of the hard goals of the problem. We formally characterize the opportunistic planning problem, introduce a novel approach to opportunistic planning, and compare it with an on-board replanning approach in the domain of AUVs performing pillar expection and chain-following tasks.
- 20 January 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automation Science and Engineering
- Vol. 15 (2) , 519-530
Opportunistic Planning in Autonomous Underwater Missions
This paper explores the execution of planned autonomous underwater vehicle (AUV) missions where opportunities to achieve additional utility can arise during execution. The missions are represented as temporal planning problems, with hard goals and time constraints. Opportunities are soft goals with high utility. The probability distributions for the occurrences of these opportunities are not known, but it is known that they are unlikely, so it is not worth trying to anticipate their occurrence prior to plan execution. However, as they are high utility, it is worth trying to address them dynamically when they are encountered, as long as this can be done without sacrificing the achievement of the hard goals of the problem. We formally characterize the opportunistic planning problem, introduce a novel approach to opportunistic planning, and compare it with an on-board replanning approach in the domain of AUVs performing pillar expection and chain-following tasks.
- 1 April 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-8
The PANDORA project: A success story in AUV autonomy
This paper presents some of the results of the EU-funded project PANDORA - Persistent Autonomy Through Learning Adaptation Observation and Re-planning. The project was three and a half years long and involved several organisations across Europe. The application domain is underwater inspection and intervention, a topic particularly interesting for the oil and gas sector, whose representatives constituted the Industrial Advisory Board. Field trials were performed at The Underwater Centre, in Loch Linnhe, Scotland, and in harbour conditions close to Girona, Spain.
- 1 April 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-8
The PANDORA project: A success story in AUV autonomy
This paper presents some of the results of the EU-funded project PANDORA - Persistent Autonomy Through Learning Adaptation Observation and Re-planning. The project was three and a half years long and involved several organisations across Europe. The application domain is underwater inspection and intervention, a topic particularly interesting for the oil and gas sector, whose representatives constituted the Industrial Advisory Board. Field trials were performed at The Underwater Centre, in Loch Linnhe, Scotland, and in harbour conditions close to Girona, Spain.
- Open Access
- 28 December 2015
- Published by Springer Nature in Autonomous Robots
- Vol. 41 (1) , 181-203
Combining temporal planning with probabilistic reasoning for autonomous surveillance missions
It is particularly challenging to devise techniques for underpinning the behaviour of autonomous vehicles in surveillance missions as these vehicles operate in uncertain and unpredictable environments where they must cope with little stability and tight deadlines in spite of their restricted resources. State-of-the-art techniques typically use probabilistic algorithms that suffer a high computational cost in complex real-world scenarios. To overcome these limitations, we propose a hybrid approach that combines the probabilistic reasoning based on the target motion model offered by Monte Carlo simulation with long-term strategic capabilities provided by automated task planning. We demonstrate our approach by focusing on one particular surveillance mission, search-and-tracking, and by using two different vehicles, a fixed-wing UAV deployed in simulation and the “Parrot AR.Drone2.0” quadcopter deployed in a physical environment. Our experimental results show that our unique way of integrating probabilistic and deterministic reasoning pays off when we tackle realistic missions.
- 28 December 2015
- Published by Springer Nature in Autonomous Robots
- Vol. 41 (1) , 181-203
Open AccessCombining temporal planning with probabilistic reasoning for autonomous surveillance missions
It is particularly challenging to devise techniques for underpinning the behaviour of autonomous vehicles in surveillance missions as these vehicles operate in uncertain and unpredictable environments where they must cope with little stability and tight deadlines in spite of their restricted resources. State-of-the-art techniques typically use probabilistic algorithms that suffer a high computational cost in complex real-world scenarios. To overcome these limitations, we propose a hybrid approach that combines the probabilistic reasoning based on the target motion model offered by Monte Carlo simulation with long-term strategic capabilities provided by automated task planning. We demonstrate our approach by focusing on one particular surveillance mission, search-and-tracking, and by using two different vehicles, a fixed-wing UAV deployed in simulation and the “Parrot AR.Drone2.0” quadcopter deployed in a physical environment. Our experimental results show that our unique way of integrating probabilistic and deterministic reasoning pays off when we tackle realistic missions.
- 1 December 2015
- Published by Elsevier in Artificial Intelligence
- Vol. 229, 210-245
An extension of metric temporal planning with application to AC voltage control
- 1 December 2015
- Published by Elsevier in Artificial Intelligence
- Vol. 229, 210-245
An extension of metric temporal planning with application to AC voltage control
- 1 January 2015
- Published by Elsevier in IFAC-PapersOnLine
- Vol. 48 (2) , 262-267
Artificial Intelligence Planning for AUV Mission Control
- 1 January 2015
- Published by Elsevier in IFAC-PapersOnLine
- Vol. 48 (2) , 262-267
Artificial Intelligence Planning for AUV Mission Control
- Open Access
A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning
Although the use of metric fluents is fundamental to many practical planning problems, the study of heuristics to support fully automated planners working with these fluents remains relatively unexplored. The most widely used heuristic is the relaxation of metric fluents into interval-valued variables --- an idea first proposed a decade ago. Other heuristics depend on domain encodings that supply additional information about fluents, such as capacity constraints or other resource-related annotations. A particular challenge to these approaches is in handling interactions between metric fluents that represent exchange, such as the transformation of quantities of raw materials into quantities of processed goods, or trading of money for materials. The usual relaxation of metric fluents is often very poor in these situations, since it does not recognise that resources, once spent, are no longer available to be spent again. We present a heuristic for numeric planning problems building on the propositional relaxed planning graph, but using a mathematical program for numeric reasoning. We define a class of producer--consumer planning problems and demonstrate how the numeric constraints in these can be modelled in a mixed integer program (MIP). This MIP is then combined with a metric Relaxed Planning Graph (RPG) heuristic to produce an integrated hybrid heuristic. The MIP tracks resource use more accurately than the usual relaxation, but relaxes the ordering of actions, while the RPG captures the causal propositional aspects of the problem. We discuss how these two components interact to produce a single unified heuristic and go on to explore how further numeric features of planning problems can be integrated into the MIP. We show that encoding a limited subset of the propositional problem to augment the MIP can yield more accurate guidance, partly by exploiting structure such as propositional landmarks and propositional resources. Our results show that the use of this heuristic enhances scalability on problems where numeric resource interaction is key in finding a solution.
Open AccessA Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning
Although the use of metric fluents is fundamental to many practical planning problems, the study of heuristics to support fully automated planners working with these fluents remains relatively unexplored. The most widely used heuristic is the relaxation of metric fluents into interval-valued variables --- an idea first proposed a decade ago. Other heuristics depend on domain encodings that supply additional information about fluents, such as capacity constraints or other resource-related annotations. A particular challenge to these approaches is in handling interactions between metric fluents that represent exchange, such as the transformation of quantities of raw materials into quantities of processed goods, or trading of money for materials. The usual relaxation of metric fluents is often very poor in these situations, since it does not recognise that resources, once spent, are no longer available to be spent again. We present a heuristic for numeric planning problems building on the propositional relaxed planning graph, but using a mathematical program for numeric reasoning. We define a class of producer--consumer planning problems and demonstrate how the numeric constraints in these can be modelled in a mixed integer program (MIP). This MIP is then combined with a metric Relaxed Planning Graph (RPG) heuristic to produce an integrated hybrid heuristic. The MIP tracks resource use more accurately than the usual relaxation, but relaxes the ordering of actions, while the RPG captures the causal propositional aspects of the problem. We discuss how these two components interact to produce a single unified heuristic and go on to explore how further numeric features of planning problems can be integrated into the MIP. We show that encoding a limited subset of the propositional problem to augment the MIP can yield more accurate guidance, partly by exploiting structure such as propositional landmarks and propositional resources. Our results show that the use of this heuristic enhances scalability on problems where numeric resource interaction is key in finding a solution.
- Open Access
Plan-based Policies for Efficient Multiple Battery Load Management
Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem under uncertainty. 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: planning for deterministic mixed discrete-continuous problems and Monte Carlo sampling for policy learning. The paper describes the development of planning techniques to allow solution of the non-linear continuous dynamic models capturing the battery behaviours. This approach depends on carefully handled discretisation of the temporal dimension. The construction of policies is performed using a classification approach and this idea offers opportunities for wider exploitation in other problems. The approach and its generality are described in the paper. Application of the approach leads to construction of policies that, in simulation, 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 in simulation compared with the theoretical limit and do so with far fewer battery switches than existing policies. Behaviour of physical batteries does not exactly match the simulated models for many reasons, so to confirm that our theoretical results can lead to real measured improvements in performance we also conduct and report experiments using a physical test system. These results demonstrate that we can obtain 5%-15% improvement in lifetimes in the case of a two battery system.
Open AccessPlan-based Policies for Efficient Multiple Battery Load Management
Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem under uncertainty. 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: planning for deterministic mixed discrete-continuous problems and Monte Carlo sampling for policy learning. The paper describes the development of planning techniques to allow solution of the non-linear continuous dynamic models capturing the battery behaviours. This approach depends on carefully handled discretisation of the temporal dimension. The construction of policies is performed using a classification approach and this idea offers opportunities for wider exploitation in other problems. The approach and its generality are described in the paper. Application of the approach leads to construction of policies that, in simulation, 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 in simulation compared with the theoretical limit and do so with far fewer battery switches than existing policies. Behaviour of physical batteries does not exactly match the simulated models for many reasons, so to confirm that our theoretical results can lead to real measured improvements in performance we also conduct and report experiments using a physical test system. These results demonstrate that we can obtain 5%-15% improvement in lifetimes in the case of a two battery system.
- Open Access
COLIN: Planning with Continuous Linear Numeric Change
In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.
Open AccessCOLIN: Planning with Continuous Linear Numeric Change
In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.
- 1 December 2013
- Published by Springer Nature in Autonomous Robots
- Vol. 37 (1) , 47-69
Policy learning for autonomous feature tracking
- 1 December 2013
- Published by Springer Nature in Autonomous Robots
- Vol. 37 (1) , 47-69
Policy learning for autonomous feature tracking