Many real-world planning problems are best modeled as infinite search space problems, using numeric fluents. Unfortunately, most planners and planning heuristics do not directly support such fluents. We propose a search space abstraction technique that compiles a planning problem with numeric fluents into a finite state propositional planning problem. To account for the loss of precision resulting from the abstraction, we leverage a policy repair technique used for non-deterministic planning. We evaluate our approach on a set of benchmarks and compare it to state-of-the-art planners that deal with numeric fluents.

Path planning in the presence of dynamic obstacles is a challenging problem due to the added time dimension in search space. In approaches that ignore the time dimension and treat dynamic obstacles as static, frequent re-planning is unavoidable as the obstacles move, and their solutions are generally sub-optimal and can be incomplete. To achieve both optimality and completeness, it is necessary to consider the time dimension during planning. The notion of adaptive dimensionality has been successfully used in high-dimensional motion planning such as manipulation of robot arms, but has not been used in the context of path planning in dynamic environments. In this paper, we apply the idea of adaptive dimensionality to speed up path planning in dynamic environments for a robot with no assumptions on its dynamic model. Specifically, our approach considers the time dimension only in those regions of the environment where a potential collision may occur, and plans in a low-dimensional state-space elsewhere. We show that our approach is complete and is guaranteed to find a solution, if one exists, within a cost sub-optimality bound. We experimentally validate our method on the problem of 3D vehicle navigation (x, y, heading) in dynamic environments. Our results show that the presented approach achieves substantial speedups in planning time over 4D heuristic-based A*, especially when the resulting plan deviates significantly from the one suggested by the heuristic.

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

The International Competition on Knowledge Engineering for Planning and Scheduling has been running since 2005 as a biennial event promoting the development and importance of the use of knowledge engineering methods and techniques within P&S. Past events include 4 competitions (ICKEPS) interleaved with KEPS workshops, all held during ICAPS conferences. We would like to encourage AI planning researchers to present tools that support the KE phases, and to exploit them (as well as other existing tools) to encode a number of scenarios and problems given by the organisers. Competitors (competing teams) can develop their tools in advance. The ICKEPS competition will be held on-site.

In the study of human learning, there is broad evidence that our ability to retain information improves with repeated exposure and decays with delay since last exposure. This plays a crucial role in the design of educational software, leading to a trade-off between teaching new material and reviewing what has already been taught. A common way to balance this trade-off is spaced repetition, which uses periodic review of content to improve long-term retention. Though spaced repetition is widely used in practice, e.g., in electronic flashcard software, there is little formal understanding of the design of these systems. Our paper addresses this gap in three ways. First, we mine log data from spaced repetition software to establish the functional dependence of retention on reinforcement and delay. Second, we use this memory model to develop a stochastic model for spaced repetition systems. We propose a queueing network model of the Leitner system for reviewing flashcards, along with a heuristic approximation that admits a tractable optimization problem for review scheduling. Finally, we empirically evaluate our queueing model through a Mechanical Turk experiment, verifying a key qualitative prediction of our model: the existence of a sharp phase transition in learning outcomes upon increasing the rate of new item introductions.

Recent work has begun exploring the value of domain abstractions in Monte-Carlo Tree Search (MCTS) algorithms for probabilistic planning. These algorithms automatically aggregate symmetric search nodes (states or state-action pairs) saving valuable planning time. Existing algorithms alternate between two phases: (1) abstraction computation forcomputing node aggregations, and (2) modified MCTS that use aggregate nodes. We believe that these algorithms do not achieve the full potential of abstractions because of disjoint phases – e.g., it can take a while to recover from erroneous abstractions, or compute better abstractions based on newly found knowledge.In response, we propose On-the-Go Abstractions (OGA), a novel approach in which abstraction computation is tightlyintegrated into the MCTS algorithm. We implement these on top of UCT and name the resulting algorithm OGA-UCT.It has several desirable properties, including (1) rapid use of new information in modifying existing abstractions, (2) elimination of the expensive batch abstraction computationphase, and (3) focusing abstraction computation on important part of the sampled search space. We experimentally compare OGA-UCT against ASAP-UCT, a recent state-of-the-art MDP algorithm as well as vanilla UCT algorithm. We find that OGA-UCT is robust across a suite of planning competition and other MDP domains, and obtains up to 28 % quality improvements.

We introduce an algorithm for long distance path planning in complex marine environments. The available free space in marine environments changes over time as a result of tides, environmental restrictions, and weather. As a result of these considerations, the free space region in marine environments needs to be dynamically generated and updated. The approach presented in this paper demonstrates that it is feasible to compute optimal paths using A* search on visibility graphs defined over quadtrees. Our algorithm exploits quadtree data structures for efficiently computing tangent edges in visibility graphs. We have developed an admissible heuristic that accounts for large islands while estimating the cost-to-go and provides a better lower bound than the Euclidean distance-based heuristic. During the search over visibility graphs, the branching factor of A* can be large due to the large size of the region. We introduce the idea of focusing the search by limiting the child nodes to be in certain regions of the workspace. Our results show that focusing the search significantly improves the computational efficiency without any noticeable degradation in path quality. We have also developed a method to estimate bounds on how far the computed path can be from the optimal path when methods for focusing the search are utilized for speeding up the computation.

The deployment of robots in populated environments is recently gaining more interest because of increased maturity and capability of this technology. In this context, sophisticated planning techniques are required because there is a need of increasing the complexity of the tasks that the robot can accomplish. In particular, there is a large emphasis on service robots, i.e., robots that can satisfy several user needs. In this paper, we present a practical framework based on a decision-theoretic formalism for generation and execution of robust plans for service robots. The proposed framework has been implemented and succesfully tested on service robots interacting with non-expert users in public environments, facing many sources of uncertainty and failures in task execution.

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. Further, we experimentally validate the approach using a quadrotor in the outdoor environment.