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.

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.

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.

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.

Required concurrency can cause actions to interfere with running continuous effects. This interference can modify the rate of change, including the polarity, of a continuous effect. In this work, we propose a mechanism to support discrete interference of rates of change caused by instantaneous actions, the start and end endpoints of other durative actions, and numeric timed initial fluents. Current temporal planners have very limited support for such numeric dynamics. COLIN reduces a temporal numeric planning problem to a linear program (LP), but operates on an implicit assumption that the rate of change of a durative action’s continuous effect is constant throughout its execution. In this work we propose some enhancements to the algorithms used in COLIN, in order to support discrete interference of continuous effects, and a new planner, DICE, was developed to implement them.

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.

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.

Planning-based methods to guide switched hybrid systems from an initial state into a desired goal region opens an interesting field for control. The idea of the Domain Predictive Control (DPC) approach is to generate input signals affecting both the numerical states and the modes of the system by stringing together atomic actions to a logically consistent plan. However, the existing DPC approach is restricted in the sense that a discrete and pre-defined input signal is required for each action. In this paper, we extend the approach to deal with symbolic states. This allows for the propagation of reachable regions of the state space emerging from actions with inputs that can be arbitrarily chosen within specified input bounds. This symbolic extension enables the applicability of DPC to systems with bounded inputs sets and increases its robustness due to the implicitly reduced search space. Moreover, precise numeric goal states instead of goal regions become reachable.

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.

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.

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.

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.

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.

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.

In this paper we present pddl+, a planning domain description language for modelling mixed discrete-continuous planning domains. We describe the syntax and modelling style of pddl+, showing that the language makes convenient the modelling of complex time-dependent effects. We provide a formal semantics for pddl+ by mapping planning instances into constructs of hybrid automata. Using the syntax of HAs as our semantic model we construct a semantic mapping to labelled transition systems to complete the formal interpretation of pddl+ planning instances. An advantage of building a mapping from pddl+ to HA theory is that it forms a bridge between the Planning and Real Time Systems research communities. One consequence is that we can expect to make use of some of the theoretical properties of HAs. For example, for a restricted class of HAs the Reachability problem (which is equivalent to Plan Existence) is decidable. pddl+ provides an alternative to the continuous durative action model of pddl2.1, adding a more flexible and robust model of time-dependent behaviour.

This work describes aspects of our plan validation tool, VAL. The tool was initially developed to support the 3rd International Planning Competition, but has subsequently been extended in order to exploit its capabilities in plan validation and development. In particular, the tool has been extended to include advanced features of PDDL2.1 which have proved important in mixed-initiative planning in a space operations project. Amongst these features, treatment of continuous effects is the most significant, with important effects on the semantic interpretation of plans. The tool has also been extended to keep abreast of developments in PDDL, providing critical support to participants and organisers of the 4th IPC.

In recent years research in the planning community has moved increasingly toward s application of planners to realistic problems involving both time and many typ es of resources. For example, interest in planning demonstrated by the space res earch community has inspired work in observation scheduling, planetary rover ex ploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. The International Planning Competitions have acted as an important motivating fo rce behind the progress that has been made in planning since 1998. The third com petition (held in 2002) set the planning community the challenge of handling tim e and numeric resources. This necessitated the development of a modelling langua ge capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, PDDL2.1, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that PDDL2.1 has considerable modelling power --- exceeding the capabilities of current planning technology --- and presents a number of important challenges to the research community.

This paper reports the outcome of the third in the series of biennial international planning competitions, held in association with the International Conference on AI Planning and Scheduling (AIPS) in 2002. In addition to describing the domains, the planners and the objectives of the competition, the paper includes analysis of the results. The results are analysed from several perspectives, in order to address the questions of comparative performance between planners, comparative difficulty of domains, the degree of agreement between planners about the relative difficulty of individual problem instances and the question of how well planners scale relative to one another over increasingly difficult problems. The paper addresses these questions through statistical analysis of the raw results of the competition, in order to determine which results can be considered to be adequately supported by the data. The paper concludes with a discussion of some challenges for the future of the competition series.

STAN is a Graphplan-based planner, so-called because it uses a variety of STate ANalysis techniques to enhance its performance. STAN competed in the AIPS-98 planning competition where it compared well with the other competitors in terms of speed, finding solutions fastest to many of the problems posed. Although the domain analysis techniques STAN exploits are an important factor in its overall performance, we believe that the speed at which STAN solved the competition problems is largely due to the implementation of its plan graph. The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumstances under which advantages can be obtained from using this implementation.

As planning is applied to larger and richer domains the effort involved in constructing domain descriptions increases and becomes a significant burden on the human application designer. If general planners are to be applied successfully to large and complex domains it is necessary to provide the domain designer with some assistance in building correctly encoded domains. One way of doing this is to provide domain-independent techniques for extracting, from a domain description, knowledge that is implicit in that description and that can assist domain designers in debugging domain descriptions. This knowledge can also be exploited to improve the performance of planners: several researchers have explored the potential of state invariants in speeding up the performance of domain-independent planners. In this paper we describe a process by which state invariants can be extracted from the automatically inferred type structure of a domain. These techniques are being developed for exploitation by STAN, a Graphplan based planner that employs state analysis techniques to enhance its performance.