Non-linear continuous change is common in real-world problems, especially those that model physical systems. We present an algorithm which builds upon existent temporal planning techniques based on linear programming to approximate non-linear continuous monotonic functions. These are integrated through a semantic attachment mechanism, allowing external libraries or functions that are difficult to model in native PDDL to be evaluated during the planning process. A new planning system implementing this algorithm was developed and evaluated. Results show that the addition of this algorithm to the planning process can enable it to solve a broader set of planning problems.

Monte-Carlo Tree Search (MCTS) algorithms such as UCT are an attractive online framework for solving planning under uncertainty problems modeled as a Markov Decision Process. However, MCTS search trees are constructed in flat state and action spaces, which can lead to poor policies for large problems. In a separate research thread, domain abstraction techniques compute symmetries to reduce the original MDP. This can lead to significant savings in computation, but these have been predominantly implemented for offline planning. This paper makes two contributions. First, we define the ASAP (Abstraction of State-Action Pairs) framework, which extends and unifies past work on domain abstractions by holistically aggregating both states and state-action pairs -- ASAP uncovers a much larger number of symmetries in a given domain. Second, we propose ASAP-UCT, which implements ASAP-style abstractions within a UCT framework combining strengths of online planning with domain abstractions. Experimental evaluation on several benchmark domains shows up to 26% improvement in the quality of policies obtained over existing algorithms.

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since "missing required tasks" may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet -- only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.

Plan recognition, the problem of inferring the goals or plans of an observed agent, is a key element of situation awareness in human-machine and machine-machine interactions for many applications. Some plan recognition algorithms require knowledge about the potential behaviours of the observed agent in the form of a plan library, together with a decision model about how the observed agent uses the plan library to make decisions. It is however difficult to elicit and specify the decision model a priori. In this paper, we present a recursive neural network model that learns such a decision model automatically. We discuss promising experimental results of the approach with comparisons to selected state-of-the-art plan recognition algorithms on three benchmark domains.

Self-play Monte Carlo Tree Search (MCTS) has been successful in many perfect-information two-player games. Although these methods have been extended to imperfect-information games, so far they have not achieved the same level of practical success or theoretical convergence guarantees as competing methods. In this paper we introduce Smooth UCT, a variant of the established Upper Confidence Bounds Applied to Trees (UCT) algorithm. Smooth UCT agents mix in their average policy during self-play and the resulting planning process resembles game-theoretic fictitious play. When applied to Kuhn and Leduc poker, Smooth UCT approached a Nash equilibrium, whereas UCT diverged. In addition, Smooth UCT outperformed UCT in Limit Texas Hold'em and won 3 silver medals in the 2014 Annual Computer Poker Competition.

Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents, where each agent wants to move from its start location to its goal location on a shared graph. The paper addresses the question of how to model MAPF as a classical planning problem, specifically, how to encode various collision constraints. Several models in the PDDL modeling language are proposed and empirically compared.

We consider a setting where an agent-based planner instructs teams of human emergency responders to perform tasks in the real world. Due to uncertainty in the environment and the inability of the planner to consider all human preferences and all attributes of the real-world, humans may reject plans computed by the agent. A naive solution that re-plans given a rejection is inefficient and does not guarantee the new plan will be acceptable. Hence, we propose a new model re-planning problem using a Multi-agent Markov Decision Process that integrates potential rejections as part of the planning process and propose a novel algorithm to efficiently solve this new model. We empirically evaluate our algorithm and show that it outperforms current benchmarks. Our algorithm is also shown to perform better in pilot studies with real humans.

Search methods are useful in hierarchical task network (HTN) planning to make performance less dependent on the domain knowledge provided, and to minimize plan costs. Here we investigate Monte-Carlo tree search (MCTS) as a new algorithmic alternative in HTN planning. We implement combinations of MCTS with heuristic search in PANDA. We furthermore investigate MCTS in JSHOP, to address lifted (non-grounded) planning, leveraging the fact that, in contrast to other search methods, MCTS does not require a grounded task representation. Our new methods yield coverage performance on par with the state of the art, but in addition can effectively minimize plan cost over time.

We present a heuristic-based search method for path planning in shared human-robot control scenarios in which the robot should adhere to specific motion constraints imposed by the human's control interface. This approach to path planning gives special consideration to kinematic and dynamic constraints introduced to reconcile discrepancies between the control space of the user and the control space of the robot. The resulting paths more closely mirror paths produced by users of the same interface; which is helpful, for example, when inferring human intent or for control sharing. Our first insight is to develop a hierarchical finite state machine describing the constrained state space, state transitions and associated costs. We then use this definition to embed the constraints of the interface into our heuristic planning algorithm, named C*, with simple modifications to the A*/D* family of graph search algorithms. This approach allows us to maintain powerful theoretical guarantees such as complexity and completeness. In this paper, we ground our augmented path planning algorithm with an implementation on a robotic wheelchair system and a Sip-and-Puff interface. We demonstrate that the new approach produces paths and control signals that more closely resemble user-generated data and can easily be incorporated into real hardware systems.

Path planning for nonholonomic robots in real-life environments is a challenging problem, as the planner needs to consider the presence of obstacles, the kinematic constraints, and also the environmental disturbances (like wind and currents). In this paper, we develop a path planning algorithm called Control Based A* (CBA*), which integrates search-based planning (on grid) with a path-following controller, taking the motion constraints and external disturbances into account. We also present another algorithm called Dynamic Control Based A* (DCBA*), which improves upon CBA* by allowing the search to look beyond the immediate grid neighborhood and thus makes it more flexible and robust, especially with high resolution grids. We investigate the performance of the new planners in different environments under different wind disturbance conditions and compare the performance against (i) finding a path in the discretized grid and following it with a nonholonomic robot, and (ii) a kinodynamic sampling-based path planner. The results show that our planners perform considerably better than (i) and (ii), especially in difficult situations such as in cluttered spaces or in presence of strong winds/currents.