When planning in temporal domains with required concurrency, envelopes arise where one or more actions need to occur within the execution of another. Starting an envelope action gives rise to an implicit relative deadline: all of the actions that need to occur within the envelope must complete before it ends. Finding effective heuristic guidance in these domains is challenging: the heuristic must not only consider how to reach the goals, but identify when it is not possible to achieve these implicit deadlines to avoid fruitless search. In this paper, we present an adaptation of a Temporal Relaxed Planning Graph heuristic, that accounts for dependencies between facts and actions in the relaxed planning graph; and the envelopes that are open in the state being evaluated. Results show that our new heuristic significantly improves the performance of a temporal planner on benchmark domains with required concurrency.

We present a scalable fully-automated forward-chaining planner capable of reasoning with PDDL+ events and linear processes.  Processes and events model (respectively) continuous and discrete exogenous activity in the environment, occurring when certain conditions hold.  We discuss the significant challenges posed in creating a planner that can reason with these, and present novel state-progression and consistency enforcing techniques that allow us to meet these challenges.  We present results showing that our new planner, using PDDL+ models, is able to solve realistic expressive problems more efficiently than the state-of-the-art alternative: a compiled PDDL 2.1 representation with continuous numeric effects.

In this paper we explore the challenges surrounding searching effectively in problems with preferences.  These problems are characterized by a relative abundance of goal states: at one extreme, if every goal is soft, every state is a goal state.  We present techniques for planning in such search spaces, managing the sometimes-conflicting aims of intensifying search around states on the open list that are heuristically close to new, better goal states; and ensuring search is sufficiently diverse to find new low-cost areas of the search space, avoiding local minima.  Our approach uses a novel cost-bound-sensitive heuristic, based on finding several heuristic distance-to-go estimates in each state, each satisfying a different subset of preferences.  We present results comparing our new techniques to the current state-of-the-art and demonstrating their effectiveness on a wide range of problems from recent International Planning Competitions.

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.