Maria Fox 0001

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.

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.

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

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.

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

Heuristic Evaluation Based on Lifted Relaxed Planning Graphs

• Bram Ridder
• Maria Fox 0001

In previous work we have shown that grounding, while used by most (if not all) modern state-of-the-art planners, is not necessary and is sometimes even undesirable. In this paper we extend this work and present a novel forward-chaining planner that does not require grounding and can solve problem instances that are too large for current planners to handle. We achieve this by exploiting equivalence relationships between objects whist constructing a lifted version of the relaxed planning graph (RPG) and extracting a relaxed plan. We compare our planner to FF and show that our approach consumes far less memory whist still being competitive. In addition we show that by not having to ground the domain we can solve much larger problem instances.

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 2013 Conference Paper

Partially Grounded Planning as Quantified Boolean Formula

• Michael Cashmore
• Maria Fox 0001
• Enrico Giunchiglia

This paper describes a technique for translating bounded propositional reachability problems, such as Planning, into Quantified Boolean Formulae (QBF). The key feature of this translation is that the problem, and the resultant encoding is only partially grounded. The technique is applicable to other SAT or QBF encodings as an additional improvement, potentially reducing the size of the resulting formula by an exponential amount. We present experimental results showing that the approach applied to a simple SAT translation greatly improves the time taken to encode and solve problems in which there are many objects of a single type, even solving some problems that cannot be reasonably encoded as SAT.

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.

ECAI Conference 2012 Conference Paper

Planning as Quantified Boolean Formula

• Michael Cashmore
• Maria Fox 0001
• Enrico Giunchiglia

This paper introduces two techniques for translating bounded propositional reachability problems into Quantified Boolean Formulae (QBF). Both exploit the binary-tree structure of the QBF problem to produce encodings logarithmic in the size of the instance and thus exponentially smaller than the corresponding SAT encoding with the same bound. The first encoding is based on the iterative squaring formulation of Rintanen. The second encoding is a compact tree encoding that is more efficient than the first one, requiring fewer alternations of quantifiers and fewer variables. We present experimental results showing that the approach is feasible, although not yet competitive with current state of the art SAT-based solvers.

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.

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.

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

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

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.

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.

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

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.