Timelines are a formalism to model planning domains where the  temporal aspects are predominant, and have been used in many  real-world applications. Despite their practical success, a major limitation is the inability  to model temporal uncertainty, i.e. the plan executor cannot decide  the duration of some activities. In this paper we make two key contributions. First, we propose a comprehensive, semantically well founded framework that  (conservatively) extends with temporal uncertainty the state of the  art timeline approach. Second, we focus on the problem of producing time-triggered plans  that are robust with respect to temporal uncertainty, under a  bounded horizon. In this setting, we present the first complete  algorithm, and we show how it can be made practical by leveraging  the power of Satisfiability Modulo Theories.

Planning is a notoriously difficult computational problem of high worst-case complexity. Researchers have been investing significant efforts to develop heuristics or restrictions to make planning practically feasible. Case-based planning is a heuristic approach where one tries to reuse previous experience when solving similar problems in order to avoid some of the planning effort. Plan reuse may offer an interesting alternative to plan generation in some settings. We provide theoretical results that identify situations in which plan reuse is provably tractable. We perform our analysis in the framework of parameterized complexity, which supports a rigorous worst-case complexity analysis that takes structural properties of the input into account in terms of parameters. A central notion of parameterized complexity is fixed-parameter tractability which extends the classical notion of polynomial-time tractability by utilizing the effect of parameters. We draw a detailed map of the parameterized complexity landscape of several variants of problems that arise in the context of case-based planning. In particular, we consider the problem of reusing an existing plan, imposing various restrictions in terms of parameters, such as the number of steps that can be added to the existing plan to turn it into a solution of the planning instance at hand.

In this paper we apply AI planning to address the hypothesis exploration problem and provide assistance to network administrators in detecting malware based on unreliable observations derived from network traffic.Building on the already established characterization and use of AI planning for similar problems, we propose a formulation of the hypothesis generation problem for malware detection as an AI planning problem with temporally extended goals and actions costs. Furthermore, we propose a notion of hypothesis ``plausibility'' under unreliable observations, which we model as plan quality. We then show that in the presence of unreliable observations, simply finding one most ``plausible'' hypothesis, although challenging, is not sufficient for effective malware detection. To that end, we propose a method for applying a state-of-the-art planner within a principled exploration process, to generate multiple distinct high-quality plans. We experimentally evaluate this approach by generating random problems of varying hardness both with respect to the number of observations, as well as the degree of unreliability. Based on these experiments, we argue that our approach presents a significant improvement over prior work that are focused on finding a single optimal plan, and that our hypothesis exploration application can motivate the development of new planners capable of generating the top high-quality plans.

Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, often resulting in high quality plans where no conformant plan exists. We are interested in this paradigm of planning for two reasons: 1) it captures a compelling form of \emph{commonsense planning}, and 2) it is of great utility in the generation of explanations, diagnoses, and counter-examples -- tasks which share a computational core with We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm.

We aim to reduce the burden of programming and deploying autonomous systems to work in concert with people in time-critical domains, such as military field operations and disaster response. Deployment plans for these operations are frequently negotiated on-the-fly by teams of human planners. A human operator then translates the agreed upon plan into machine instructions for the robots. We present an algorithm that reduces this translation burden by inferring the final plan from a processed form of the human team's planning conversation. Our approach combines probabilistic generative modeling with logical plan validation used to compute a highly structured prior over possible plans. This hybrid approach enables us to overcome the challenge of performing inference over the large solution space with only a small amount of noisy data from the team planning session. We validate the algorithm through human subject experimentation and show we are able to infer a human team's final plan with 83% accuracy on average. We also describe a robot demonstration in which two people plan and execute a first-response collaborative task with a PR2 robot. To the best of our knowledge, this is the first work that integrates a logical planning technique within a generative model to perform plan inference.

Despite its success, the delete relaxation has significant pitfalls. Recent work has devised the red-black planning framework, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. Provided the red variables are chosen so that red-black plan generation is tractable, one can generate such a plan for every search state, and take its length as the heuristic distance estimate. Previous results were not suitable for this purpose because they identified tractable fragments for red-black plan existence, as opposed to red-black plan generation. We identify a new fragment of red-black planning, that fixes this issue. We devise machinery to efficiently generate red-black plans, and to automatically select the red variables. Experiments show that the resulting heuristics can significantly improve over standard delete relaxation heuristics.

In Automated Planning, learning and exploiting additional knowledge within a domain model, in order to improve plan generation speed-up and increase the scope of problems solved, has attracted much research. Reformulation techniques such as those based on macro-operators or entanglements are very promising because they are to some extent domain model and planning engine independent. This paper aims to exploit recent work on inner entanglements, relations between pairs of planning operators and predicates encapsulating exclusivity of predicate `achievements` or `requirements', for generating macro-operators. We discuss conditions which are necessary for generating such macro-operators and conditions that allow removing primitive operators without compromising solvability of a given (class of) problem(s). The effectiveness of our approach will be experimentally shown on a set of well-known benchmark domains using several high-performing planning engines.

Monte-Carlo search is successfully used in simulation-based planning for various large-scale sequential decision problems, and the UCT algorithm seems to be the choice in most (if not all) such recent success stories. Based on some recent discoveries in theory and empirical analysis of Monte-Carlo search, here we argue that, if online sequential decision making is your problem, and Monte-Carlo tree search is your way to go, then UCT is unlikely to be the best fit for your needs.

In this paper, we consider the problem of planning any-angle paths with small numbers of turns on grid maps. We propose a novel heuristic search algorithm called Link* that returns paths containing fewer turns at the cost of slightly longer path lengths. Experimental results demonstrate that Link* can produce paths with fewer turns than other any-angle path planning algorithms while still maintaining comparable path lengths. Because it produces this type of path, artificial agents can take advantage of Link* when the cost of turns is expensive.

AI Planning is inherently hard and hence it is desirable to derive as much information as we can from the structure of the planning problem and let this information be exploited by a planner. Many recent planners use the finite-domain state-variable representation of the problem instead of the traditional propositional representation. However, most planning problems are still specified in the propositional representation due to the widespread modeling language PDDL and it is hard to generate a compact and computationally efficient state variable representation from the propositional model. In this paper we propose a novel method for automaticallygenerating an efficient state-variable representation from the propositional representation. This method groups sets of propositions into state variables based onthe mutex relations introduced in the planning graph. As we shall show experimentally, our method outperforms the current state-of-the-art method both in the smaller number of generated state variables and in the increased performance of planners.