This paper reveals the inherent limitations of A* in HTN planning by identifying various cycle types induced by the task hierarchy and analyzing their effects on the termination of the algorithm. We prove that A* even with the perfect heuristic, and for the special case of totally ordered problems, which are known to be decidable, is incomplete. An especially interesting results is that having a visited list (i.e., graph search) with the null heuristic has better termination guarantees than tree search with the perfect heuristic. We provide a polynomial-time test for detecting those cycles that render A* incomplete, and analyzed all existing benchmark domains from the most-recent international planning competition. Results show that in more than half of all domains, A* tree search would be incomplete even with the perfect heuristic, and in roughly 40% of cases A* graph search might also be incomplete depending on the provided heuristic function. We also point to a normal form that preserves semantics and guarantees completeness of the resulting models, though implementation and testing remains for future work.

Hierarchical Task Network (HTN) planning is an approach to sequential decision making that allows expressing complex grammar-like path constraints. In this paper, we first introduce an extension to HTN planning that takes probabilistic outcomes into account, and then study the computational complexity of deciding such problems either by finding a fixed sequence of actions (i.e., a conformant solution) or an outcome-dependent policy. This formalization extends factored Markov Decision Processes (MDPs) to have a hierarchical structure. In all studied cases, the conformant solutions are harder to obtain than their non-deterministic analogues, whereas policies are not always harder. Surprisingly, unlike their deterministic counterparts, severely restricted cases of probabilistic HTN problems are proven to be undecidable. The result holds even if all of the transition probabilities are bounded to be 0, 0.5, or 1.

Domain model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Learning action models from narrative texts in an automated way is essential to overcome this barrier, but challenging because of the inherent complexities of such texts. We present an evaluation of planning domain models derived from narrative texts using our fully automated, unsupervised system, NaRuto. Our system combines structured event extraction, predictions of commonsense event relations, and textual contradictions and similarities. Evaluation results show that NaRuto generates domain models of significantly better quality than existing fully automated methods, and even sometimes on par with those created by semi-automated methods, with human assistance.

Relation extraction is a crucial task in natural language processing (NLP) and information retrieval (IR).Previous work on event relation extraction mainly focuses on hierarchical, temporal and causal relations.Such relationships consider two events to be independent in terms of syntax and semantics, but they fail to recognize the interdependence between events.To bridge this gap, we introduce a human-annotated Event Dependency Relation dataset (EDeR).The annotation is done on a sample of documents from the OntoNotes dataset, which has the additional benefit that it integrates with existing, orthogonal, annotations of this dataset.We investigate baseline approaches for EDeR's event dependency relation prediction.We show that recognizing such event dependency relations can further benefit critical NLP tasks, including semantic role labelling and co-reference resolution.

In multi-objective (MO) heuristic search, solution costs, as well as heuristic values, are sets of multi-dimensional cost vectors, representing possible non-dominated trade-offs between objectives. The maximum of two or more such vector sets, which is an important operation in creating informative admissible MO heuristics, can be defined in several ways: Geißer et al. recently proposed two MO maximum operators, the component-wise maximum (comax) and the anti-dominance maximum (admax), which represent different trade-offs between informativeness and computational cost. We show that the anti-dominance maximum is not admissibility-preserving, and propose an alternative, the “select one” maximum (somax). We also show that the comax operator is the greatest admissibility-preserving MO maximum, and briefly investigate its efficient implementation. The conclusion of our experimental results is that somax achieves a trade-off similar to that intended with admax – cheaper to compute but less informed – also when compared to an improved comax implementation.

Detecting, characterizing and adapting to novelty, whether in the form of previously unseen objects or phenomena, or unexpected changes in the behavior of known elements, is essential for Artificial Intelligence agents to operate reliably in unconstrained real-world environments. We propose an automatic, unsupervised approach to novelty characterization for dynamic domains, based on describing the behaviors and interactions of objects in terms of their possible actions. To abstract from the variety of realizations of an action that can occur in physical domains, we model states in terms of qualitative spatial relations (QSRs) between their entities. By first learning a model of actions in the non-novel environment from the state transitions observed as the agent interacts with the world, we can detect novelty by the persistent deviations from this model that it causes, and characterize the novelty by new or modified actions. We also present a new method of learning action models from observation, based on conceptual similarity and hierarchical clustering.

This paper studies novel subgoaling relaxations for automated planning with propositional and numeric state variables. Subgoaling relaxations address one source of complexity of the planning problem: the requirement to satisfy conditions simultaneously. The core idea is to relax this requirement by recursively decomposing conditions into atomic subgoals that are considered in isolation. Such relaxations are typically used for pruning, or as the basis for computing admissible or inadmissible heuristic estimates to guide optimal or satis_cing heuristic search planners. In the last decade or so, the subgoaling principle has underpinned the design of an abundance of relaxation-based heuristics whose formulations have greatly extended the reach of classical planning. This paper extends subgoaling relaxations to support numeric state variables and numeric conditions. We provide both theoretical and practical results, with the aim of reaching a good trade-o_ between accuracy and computation costs within a heuristic state-space search planner. Our experimental results validate the theoretical assumptions, and indicate that subgoaling substantially improves on the state of the art in optimal and satisficing numeric planning via forward state-space search.

Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the "envelope" of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is complete only under certain assumptions. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints while assigning the discrete variables statically it is not.

This paper studies an effect-abstraction based relaxation for reasoning about linear numeric planning problems. The effect-abstraction decomposes non-constant linear numeric effects into actions with conditional effects over additive constant numeric effects. With little effort, on this compiled version, it is possible to use known subgoaling based relaxations and relative heuristics. The combination of these two steps leads to a novel relaxation based heuristic. Theoretically, the relaxation is proved tighter than previous interval based relaxation and leading to safe-pruning heuristics. Empirically, a heuristic developed on this relaxation leads to substantial improvements for a class of problems that are currently out of the reach of state-of-the-art numeric planners.

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. In this paper, we present a generalization of the operator-counting family of heuristics to Stochastic Shortest Path problems (SSPs) that is able to represent the probability of the actions outcomes. Our experiments show that the equivalent of the net change heuristic in this generalized framework obtains significant run time and coverage improvements over other state-of-the-art heuristics in different planners.

We present a principled way of extending a classical AI planning formalism with systems of state constraints, which relate - sometimes determine - the values of variables in each state traversed by the plan. This extension occupies an attractive middle ground between expressivity and complexity. It enables modelling a new range of problems, as well as formulating more efficient models of classical planning problems. An example of the former is planning-based control of networked physical systems - power networks, for example - in which a local, discrete control action can have global effects on continuous quantities, such as altering flows across the entire network. At the same time, our extension remains decidable as long as the satisfiability of sets of state constraints is decidable, including in the presence of numeric state variables, and we demonstrate that effective techniques for cost-optimal planning known in the classical setting - in particular, relaxation-based admissible heuristics - can be adapted to the extended formalism. In this paper, we apply our approach to constraints in the form of linear or non-linear equations over numeric state variables, but the approach is independent of the type of state constraints, as long as there exists a procedure that decides their consistency. The planner and the constraint solver interact through a well-defined, narrow interface, in which the solver requires no specialisation to the planning context.

The paper generalises the notion of landmarks for reasoning about planning problems involving propositional and numeric variables. Intuitively, numeric landmarks are regions in the metric space defined by the problem whose crossing is necessary for its resolution. The paper proposes a relaxation-based method for their automated extraction directly from the problem structure, and shows how to exploit them to infer what we call disjunctive and additive hybrid action landmarks. The justification of such a disjunctive representation results from the intertwined propositional and numeric structure of the problem. The paper exercises their use in two novel admissible LP-Based numeric heuristics, and reports experiments on cost-optimal numeric planning problems. Results show the heuristics are more informed and effective than previous work for problems involving a higher number of (sub)goals.

Over-subscription, that is, being assigned too many things to do, is commonly encountered in temporal scheduling problems. As human beings, we often want to do more than we can actually do, and underestimate how long it takes to perform each task. Decision makers can benefit from aids that identify when these failure situations are likely, the root causes of these failures, and resolutions to these failures. In this paper, we present a decision assistant that helps users resolve over-subscribed temporal problems. The system works like an experienced advisor that can quickly identify the cause of failure underlying temporal problems and compute resolutions. The core of the decision assistant is the Best-first Conflict-Directed Relaxation (BCDR) algorithm, which can detect conflicting sets of constraints within temporal problems, and computes continuous relaxations for them that weaken constraints to the minimum extent, instead of removing them completely. BCDR is an extension to the Conflict-Directed A* algorithm, first developed in the model-based reasoning community to compute most likely system diagnoses or reconfigurations. It generalizes the discrete conflicts and relaxations, to hybrid conflicts and relaxations, which denote minimal inconsistencies and minimal relaxations to both discrete and continuous relaxable constraints. In addition, BCDR is capable of handling temporal uncertainty, expressed as either set-bounded or probabilistic durations, and can compute preferred trade-offs between the risk of violating a schedule requirement, versus the loss of utility by weakening those requirements. BCDR has been applied to several decision support applications in different domains, including deep-sea exploration, urban travel planning and transit system management. It has demonstrated its effectiveness in helping users resolve over-subscribed scheduling problems and evaluate the robustness of existing solutions. In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers.

We generalise the interval-based relaxation to sequential numeric planning problems with non-linear conditions and effects, and cyclic dependencies. This effectively removes all the limitations on the problem placed in previous work on numeric planning heuristics, and even allows us to extend the planning language with a wider set of mathematical functions. Heuristics obtained from the generalised relaxation are pruning-safe. We derive one such heuristic and use it to solve discrete-time control-like planning problems with autonomous processes. Few planners can solve such problems, and search with our new heuristic compares favourably with them.

Finding high quality plans for large planning problems is hard. Although some current anytime planners are often able to improve plans quickly, they tend to reach a limit at which the plans produced are still very far from the best possible, but these planners fail to find any further improvement, even when given several hours of runtime. We present an approach to continuing plan quality optimisation at larger time scales, and its implementation in a system called BDPO2. Key to this approach is a decomposition into subproblems of improving parts of the current best plan. The decomposition is based on block deordering, a form of plan deordering which identifies hierarchical plan structure. BDPO2 can be seen as an application of the large neighbourhood search (LNS) local search strategy to planning, where the neighbourhood of a plan is defined by replacing one or more subplans with improved subplans. On-line learning is also used to adapt the strategy for selecting subplans and subplanners over the course of plan optimisation. Even starting from the best plans found by other means, BDPO2 is able to continue improving plan quality, often producing better plans than other anytime planners when all are given enough runtime. The best results, however, are achieved by a combination of different techniques working together.

Many areas of computer science require answering questions about reachability in compactly described discrete transition systems. Answering such questions effectively requires techniques to be able to do so without building the entire system. In particular, heuristic search uses lower-bounding (“admissible”) heuristic functions to prune parts of the system known to not contain an optimal solution. A prominent technique for deriving such bounds is to consider abstract transition systems that aggregate groups of states into one. The key question is how to design and represent such abstractions. The most successful answer to this question are pattern databases, which aggregate states if and only if they agree on a subset of the state variables. Merge-and-shrink abstraction is a new paradigm that, as we show, allows to compactly represent a more general class of abstractions, strictly dominating pattern databases in theory. We identify the maximal class of transition systems, which we call factored transition systems , to which merge-and-shrink applies naturally, and we show that the well-known notion of bisimilarity can be adapted to this framework in a way that still guarantees perfect heuristic functions, while potentially reducing abstraction size exponentially. Applying these ideas to planning, one of the foundational subareas of artificial intelligence, we show that in some benchmarks this size reduction leads to the computation of perfect heuristic functions in polynomial time and that more approximate merge-and-shrink strategies yield heuristic functions competitive with the state of the art.

Heuristic functions based on the delete relaxation compute upper and lower bounds on the optimal delete-relaxation heuristic h+, and are of paramount importance in both optimal and satisficing planning. Here we introduce a principled and flexible technique for improving h+, by augmenting delete-relaxed planning tasks with a limited amount of delete information. This is done by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task, rendering h+ the perfect heuristic h* in the limit. Previous work has introduced a method in which the growth of the task is potentially exponential in the number of conjunctions introduced. We formulate an alternative technique relying on conditional effects, limiting the growth of the task to be linear in this number. We show that this method still renders h+ the perfect heuristic h* in the limit. We propose techniques to find an informative set of conjunctions to be introduced in different settings, and analyze and extend existing methods for lower-bounding and upper-bounding h+ in the presence of conditional effects. We evaluate the resulting heuristic functions empirically on a set of IPC benchmarks, and show that they are sometimes much more informative than standard delete-relaxation heuristics.

The currently dominant approach to domain-independent planning is planning as heuristic search, with most successful planning heuristics being based on solutions to delete-relaxed versions of planning problems, in which the negative effects of actions are ignored. We introduce a principled, flexible, and practical technique for augmenting delete-relaxed tasks with a limited amount of delete information, by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task. Differently from previous work, conditional effects are used to limit the growth of the task to be linear in the number of such conjunctions, making its use for obtaining heuristic functions feasible. The resulting heuristics are empirically evaluated, and shown to be some- times much more informative than standard delete-relaxation heuristics.

A model of story generation recently proposed by Riedl and Young casts it as planning, with the additional condition that story characters behave intentionally. This means that characters have perceivable motivation for the actions they take. I show that this condition can be compiled away (in more ways than one) to produce a classical planning problem that can be solved by an off-the-shelf classical planner, more efficiently than by Riedl and Young's specialised planner.

The language of linear temporal logic (LTL) has been proposed as a formalism for specifying temporally extended goals and search control constraints in planning. However, the semantics of LTL is defined wrt. infinite state sequences, while a finite plan generates only a finite trace. This necessitates the use of a finite trace semantics for LTL. A common approach is to evaluate LTL formulae on an infinite extension of the finite trace, obtained by infinitely repeating the last state. We study several aspects of this finite LTL se mantics: we show its satisfiability problem is PSpace-complete (same as normal LTL), show that it complies with all equivalence laws that hold under standard (infinite) LTL semantics, and compare it with other finite trace semantics for LTL proposed in planning and in runtime verification. We also examine different mechanisms for determining whether or not a finite trace satisfies or violates an LTL formula, interpreted using the infinite extension semantics.

The hm admissible heuristics for (sequential and temporal) regression planning are defined by a parameterized relaxation of the optimal cost function in the regression search space, where the parameter m offers a trade-off between the accuracy and computational cost of theheuristic. Existing methods for computing the hm heuristic require time exponential in m, limiting them to small values (m