There is increasing awareness in the planning community that the burden of specifying complete domain models is too high, which impedes the applicability of planning technology in many real-world domains. Although there have been many learning approaches that help automatically creating domain models, they all assume plan traces (training data) are \emph{correct}. In this paper, we aim to remove this assumption, allowing plan traces to be with noise. Compared to collecting large amount of correct plan traces, it is much easier to collect noisy plan traces, e.g., we can directly exploit sensors to help collect noisy plan traces. We consider a novel solution for this challenge that can learn action models from noisy plan traces. We create a set of random variables to capture the possible correct plan traces behind the observed noisy ones, and build a graphical model to describe the physics of the domain. We then learn the parameters of the graphical model and acquire the domain model based on the learnt parameters. In the experiment, we empirically show that our approach is effective in several planning domains.

One drawback of Hierarchical Task Network (HTN) planning is the difficulty of providing complete domain knowledge, i.e., a complete and correct set of HTN methods for every task. To provide a principled way to overcome this difficulty, we define a simple formalism that extends classical planning to include problem decomposition using methods, and a planning algorithm based on this formalism. In our formalism, the methods specify ways to achieve goals (rather than tasks as in conventional HTN planning), and goals may be achieved even when no methods are available. Our planning algorithm, GoDeL (Goal Decomposition with Landmarks), is sound and complete irrespective of whether the domain knowledge (i.e., the set of methods given to the planner) is complete. By comparing GoDeL's performance with varying amounts of domain knowledge across three benchmark planning domains, we show experimentally that (1) GoDeL works correctly with partial planning knowledge, (2) GoDeL's performance improves as more planning knowledge is given, and (3) when given full domain knowledge, GoDeL matches the performance of a state-of-the-art hierarchical planner.

The ability to understand the goals and plans of other agents is an important characteristic of intelligent behaviours in many contexts. One of the approaches used to endow agents with this capability is the weighted model counting approach. Given a plan library and a sequence of observations, this approach exhaustively enumerates plan execution models that are consistent with the observed behaviour. The probability that the agent might be pursuing a particular goal is then computed as a proportion of plan execution models satisfying the goal. The approach allows to recognize multiple interleaved plans, but suffers from a combinatorial explosion of plan execution models, which impedes its application to real-world domains. This paper presents a heuristic weighted model counting algorithm that limits the number of generated plan execution models in order to recognize goals quickly by computing their lower and upper bound likelihoods.

The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

We provide a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level reasoning to address hybrid planning problems in robotics. We identify four distinct strategies for such an integration: (i) low-level checks are done for all possible cases in advance and then this information is used during plan generation, (ii) low-level checks are done exactly when they are needed during the search for a plan, (iii) first all plans are computed and then infeasible ones are filtered, and (iv) by means of replanning, after finding a plan, low-level checks identify whether it is infeasible or not; if it is infeasible, a new plan is computed considering the results of previous low- level checks. We perform experiments on hybrid planning problems in robotic manipulation and legged locomotion domains considering these four methods of integration, as well as some of their combinations. We analyze the usefulness of levels of integration in these domains, both from the point of view of computational efficiency (in time and space) and from the point of view of plan quality relative to its feasibility. We discuss advantages and disadvantages of each strategy in the light of experimental results and provide some guidelines on choosing proper strategies for a given domain.

We present ReAct!, an interactive tool for high-level reasoning for cognitive robotic applications. ReAct! enables robotic researchers to describe robots' actions and change in dynamic domains, without having to know about the syntactic and semantic details of the underlying formalism in advance, and solve planning problems using state-of-the-art automated reasoners, without having to learn about their input/output language or usage. In particular, ReAct! can be used to represent sophisticated dynamic domains that feature concurrency, indirect effects of actions, and state/transition constraints. It allows for embedding externally defined calculations (e.g., checking for collision-free continuous trajectories) into representations of hybrid domains that require a tight integration of (discrete) high-level reasoning with (continuous) geometric reasoning. ReAct! also enables users to solve planning problems that involve complex goals. Such variety of utilities are useful for robotic researchers to work on interesting and challenging domains, ranging from service robotics to cognitive factories. ReAct! provides sample formalizations of some action domains (e.g., multi-agent path planning, Tower of Hanoi), as well as dynamic simulations of plans computed by a state-of-the-art automated reasoner (e.g., a SAT solver or an ASP solver).

In the real world, robots with embodiment face various issues such as dynamic continuous changes of the environment and input/output disturbances. The key to solving these issues can be found in daily life; people `do actions associated with sensing' and `dynamically change their plans when necessary'. We propose the use of a new concept, enabling robots to do these two things, for autonomously controlling mobile robots. We implemented our concept to make two experiments under static/dynamic environments. The results of these experiments show that our idea provides a way to adapt to dynamic changes of the environment in the real world.

In exploratory domains, agents' actions map onto logs of behavior that include switching between activities, extraneous actions, and mistakes. These aspects create a challenging plan recognition problem. This paper presents a new algorithm for inferring students' activities in exploratory domains that is evaluated empirically using a new type of flexible and open-ended educational software for science education. Such software has been shown to provide a rich educational environment for students, but challenge teachers to keep track of students' progress and to assess their performance. The algorithm decomposes students’ complete interaction histories to create hierarchies of interdependent tasks that describe their activities using the software. It matches students' actions to a predefined grammar in a way that reflects that students solve problems in a modular fashion but may still interleave between their activities. The algorithm was empirically evaluated on people’s interaction with two separate software systems for simulating a chemistry laboratory and for statistics education. It was separately compared to the state-of-the-art recognition algorithms for each of the software. The results show that the algorithm was able to correctly infer students' activities significantly more often than the state-of-the-art, and was able to generalize to both of the software systems with no intervention.

Modern multi-core computers provide an opportunity to parallelize plan recognition algorithms to decrease runtime. Viewing the problem as one of parsing and performing a complete breadth first search, makes ELEXIR (Engine for LEXicalized Intent Recognition) (Geib '09, Geib '11) particularly suitable for such parallelism. This paper documents the extension of ELEXIR to utilize such modern computing platforms. We will discuss multiple possible algorithms for distributing work between parallel threads and the associated performance wins. We will show, that the best of these algorithms will provide close to linear speedup (up to a maximum number of processors), and that features of the problem domain have an impact on the speedup.

In many applications a user attempts to configure a complex object with many possible internal choices. Recommendation engines that automatically configure such objects given user preferences and constraints, may provide much value in such cases. These applications offer the user various methods to provide the input and generate appropriate recommendations. It is likely, though, that the user will not be able to fully express her preferences and constraints, requiring a phase of manual tuning of the recommended configuration. We suggest that following this manual revision, additional constraints and preferences can be automatically collected, and the recommended configuration can be automatically improved. Specifically, we suggest a recommender component that takes as input an initial manual configuration of a complex object, deduces certain user preferences and constraints from this configuration, and constructs an alternative configuration. We show an appealing application for our method in complex trip planning, and demonstrate its usability in a user study.