We investigate the use of a simple, discriminative reranking approach to plan recognition in an abductive setting. In contrast to recent work, which attempts to model abductive plan recognition using various formalisms that integrate logic and graphical models (such as Markov Logic Networks or Bayesian Logic Programs), we instead advocate a simpler, more flexible approach in which plans found through an abductive beam-search are discriminatively scored based on arbitrary features. We show that this approach performs well even with relatively few positive training examples, and we obtain state-of-the-art results on two abductive plan recognition datasets, outperforming more complicated systems.

Property Directed Reachability (PDR), also known as IC3, is a very promising recent method for deciding reachability in symbolically represented transition systems. While originally conceived as a model checking algorithm for hardware circuits, it has already been successfully applied in several other areas. This paper summarizes the first investigation of PDR from the perspective of automated planning.

Simple Temporal Networks (STNs) allow minimum and maximum distance constraints between time-points to be represented. They are often used when tackling planning and scheduling problems that involve temporal aspects. This paper is a summary of the journal article "Time-dependent Simple Temporal Networks: Properties and Algorithms" published in RAIRO - Operations Research. This journal article introduces an extension of STN called Time-dependent STN (TSTN), which covers temporal constraints for which the temporal distance required between two time-points is not necessarily constant. Such constraints are useful to model time-dependent scheduling problems, in which the duration of an activity may depend on its starting time. The paper introduces the TSTN framework, its properties, resolution techniques, as well as examples of applications.

In (Otte and Correll 2013) we present C-FOREST, a parallelization framework for single-query sampling-based shortest-path planning algorithms. C-FOREST has been observed to have super linear speedup on many problems, e.g., paths of quality Ltarget are found 350X faster by 64 CPUs working in parallel than by 1 CPU. In (Otte and Correll 2013) C-FOREST is tested in conjunction with the RRT* algorithm. In the current work we perform additional experiments that show C-FOREST provides similar advantages when used conjunction with the SPRT algorithm. This reinforces our original claim that C-FOREST is generally applicable to a wide range of sampling based motion planning algorithms.

In order to overcome a large variety of run-time constraints, robots are being designed to be more resourceful by incorporating more sensory and motor options for any given task. The added flexibility provides a basis for dexterous problem solving, but challenges planners by increasing the complexity of search. Moreover, the cost of functionally equivalent options can vary dramatically. In the worst case, naive approaches to planning avoid expensive actions until inexpensive options are explored exhaustively leading to poor overall search performance. We present a dexterous robot that introduces multiple types of locomotor actions with significant differences in cost and situational value and apply standard search techniques to demonstrate the additional challenges that arise in the context of dexterous mobility. Results highlight incentives, opportunities, and impact for overcoming these challenges. Additionally, we present a prototype for a path planner that uses environmental features to define an efficient set of subgoals for dexterous motion planning.

Focused D* and D*-Lite are two popular incremental heuristic search algorithm amenable to goal-directed navigation in partially known terrain. Recently it has been shown that, unlike commonly believed, a version of A* is in many cases faster than D*-Lite, posing the question of whether or not there exist other variants of A* which could outperform algorithms in the D* family on most problems. In this paper we present Multipath Adaptive A* (MPAA*), a simple, easy-to-implement modification of Adaptive A* (AA*) that reuses paths found in previous searches to speed up subsequent searches, and that almost always outperforms D*Lite. We evaluate MPAA* against D*-Lite on random maps and standard game, room, and maze maps, assuming partially known terrain. In environments comparable to indoor and outdoor navigation (room and game maps) MPAA* is 35% faster than D*Lite on average, while on random maps MPAA* is over 3 times faster than D*Lite. D*Lite is faster than MPAA* only in mazes; notwithstanding, we show that if a small percentage of obstacle cells in a maze are made traversable, MPAA* outperforms D*Lite. In addition, we prove MPAA* is optimal and that it finds a solution if one exists. We conclude that for most real-life goal-directed navigation applications MPAA* should be preferred to D*Lite.

Adapting plans to changes in the environment by finding alternatives and taking advantage of opportunities is a common human behavior. The need for such behavior is often rooted in the uncertainty produced by our incomplete knowledge of the environment. While several existing planning approaches deal with such issues, artificial agents still lack the robustness that humans display in accomplishing their tasks. In this work, we address this brittleness by combining Hierarchical Task Network planning, Description Logics, and the notions of affordances and conceptual similarity. The approach allows a domestic service robot to find ways to get a job done by making substitutions. We show how knowledge is modeled, how the reasoning process is used to create a constrained planning problem, and how the system handles cases where plan generation fails due to missing/unavailable objects. The results of the evaluation for two tasks in a domestic service domain show the viability of the approach in finding and making the appropriate goal transformations.

There is a strong demand for robots to work in environments, such as aircraft manufacturing, where they share tasks with humans and must quickly adapt to each other's needs. To do so, a robot must both infer the intent of humans, and must adapt accordingly. The literature to date has made great progress on these two tasks - recognition and adaptation - but largely as separate research activities. In this paper, we present a unified approach to these two problems, in which recognition and adaptation occur concurrently and holistically.  Key to our approach is a task representation that uses choice to represent alternative plans for both the human and robot, allowing a single set of algorithms to simultaneously achieve recognition and adaptation. To achieve such fluidity, a labeled propagation mechanism is used where decisions made by the human and robot during execution are propagated to relevant future open choices, as determined by causal link analysis, narrowing the possible options that the human would reasonably take (hence achieving intent recognition) as well as the possible actions the robot could consistently take (adaptation). This paper introduces Pike, an executive for human-robot teamwork that quickly adapts and infers intent based on the preconditions of actions in the plan, temporal constraints, unanticipated disturbances, and choices made previously (by either robot or human).  We evaluate Pike's performance and demonstrate it on a household task in a human-robot team testbed.

In this paper, we present a tree-based algorithm for construction robots. Inspired by the TERMES project of Harvard University, robots in this domain are required to gather construction blocks from a reservoir and build user-specified structures much larger than themselves. While the robots are of roughly the same size as the blocks, they can scale greater heights by using temporarily constructed ramps in the substructures. In this paper, we consider the problem of minimizing the number of pickup and drop-off operations performed on blocks in order to build user-specified structures. Our polynomial-time algorithm heuristically solves this problem and is based on the idea of performing dynamic programming on a spanning tree in the inner loop and searching for a good tree to do so in the outer loop. Our algorithm performs very well in simulation and scales easily to large problem instances. For planning problems of this nature that are akin to construction domains, we believe that valuable lessons can be learned from comparing the success of our algorithm with the failure of off-the-shelf planning technologies.

The evolution in precision manufacturing has resulted in the requirement to produce and maintain more accurate machine tools. This new requirement coupled with desire to reduce machine tool downtime places emphasis on the calibration procedure during which the machine’s capabilities are assessed. Machine tool downtime is significant for manufacturers because the machine will be unavailable for manufacturing use, therefore wasting the manufacturer’s time and potentially increasing lead-times for clients. In addition to machine tool downtime, the uncertainty of measurement, due to the schedule of the calibration plan, has significant implications on tolerance conformance, resulting in an increased possibility of false acceptance and rejection of machined parts. The work presented in this paper is focussed on expanding a developed temporal optimisation model to reduce the uncertainty of measurement. Encoding the knowledge in regular PDDL requires the discretization of non-linear, continuous temperature change and implementing the square root function. The implementation shows that not only can domainindependent automated planning reduce machine downtime by 10.6% and the uncertainty of measurement by 59%, it is also possible to optimise both metrics reaching a compromise that is on average 9% worse that the best-known solution for each individual metric.