Consider the following problem: a human-robot team is actively In this paper, we explore the issues involved in engineering engaged in an urban search and rescue (USAR) scenario an automated planner to guide a robot towards maximizing inside a building of interest. The robot is placed inside net benefit accompanied with goal achievement in such this building, at the beginning of a long corridor; a sample scenarios. The planning problem that we face involves partial layout is presented in Figure 1. The human team member satisfaction (in that the robot has to weigh the rewards of has intimate knowledge of the building's layout, but is removed the soft goals against the cost of achieving them); it also requires from the scene and can only interact with the robot replanning ability (in that the robot has to modify its via on-board wireless audio communication. The corridor in current plan based on new goals that are added). An additional which the robot is located has doors leading off from either (perhaps more severe) complication is that the planner side into rooms, a fact known to the robot. However, unknown needs to handle goals involving objects whose existence is to the robot (and the human team member) is the possibility not known in the initial state (e.g., the location of the humans that these rooms may contain injured humans (victims).

We consider how to learn Hierarchical Task Networks (HTNs) for planning problems in which both the quality of solution plans generated by the HTNs and the speed at which those plans are found is important. We describe an integration of HTN Learning with Reinforcement Learning to both learn methods by analyzing semantic annotations on tasks and to produce estimates of the expected values of the learned methods by performing Monte Carlo updates. We performed an experiment in which plan quality was inversely related to plan length. In two planning domains, we evaluated the planning performance of the learned methods in comparison to two state-of-the-art satisficing classical planners, FastForward and SGPlan6, and one optimal planner, HSP*. The results demonstrate that a greedy HTN planner using the learned methods was able to generate higher quality solutions than SGPlan6 in both domains and FastForward in one. Our planner, FastForward, and SGPlan6 ran in similar time, while HSP* was exponentially slower.

Planning in dynamic continuous environments requires reasoning about nonlinear continuous effects, which previous Hierarchical Task Network (HTN) planners do not support. In this paper, we extend an existing HTN planner with a new state projection algorithm. To our knowledge, this is the first HTN planner that can reason about nonlinear continuous effects. We use a wait action to instruct this planner to consider continuous effects in a given state. We also introduce a new planning domain to demonstrate the benefits of planning with nonlinear continuous effects. We compare our approach with a linear continuous effects planner and a discrete effects HTN planner on a benchmark domain, which reveals that its additional costs are largely mitigated by domain knowledge. Finally, we present an initial application of this algorithm in a practical domain, a Navy training simulation, illustrating the utility of this approach for planning in dynamic continuous environments.

This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. This approach is based on a direct approximation of AIXI, a Bayesian optimality notion for general reinforcement learning agents. Previously, it has been unclear whether the theory of AIXI could motivate the design of practical algorithms. We answer this hitherto open question in the affirmative, by providing the first computationally feasible approximation to the AIXI agent. To develop our approximation, we introduce a Monte Carlo Tree Search algorithm along with an agent-specific extension of the Context Tree Weighting algorithm. Empirically, we present a set of encouraging results on a number of stochastic, unknown, and partially observable domains.

My research represents an approach to integrating planning and execution in time-sensitive environments. The primary focus is on a problem called continual on-line planning. New goals arrive stochastically during execution, the agent issues actions for execution one at a time, and the environment is otherwise deterministic. My dissertation will address this setting in three stages: optimizing total goal achievement time, handling on-line goal arrival during planning or execution, and adapting to changes in state also during planning or execution. My current approach to this problem is based on incremental heuristic search. The two central issues are the decision of which partial plans to elaborate during search and the decision of when to issue an action for execution. I have proposed an extension of Russell and Wefald's decision-theoretic A* algorithm that is not limited by assumptions of an admissible heuristic like DTA*. This algorithm, Decision Theoretic On-line Continual Search (DTOCS), handles the complexities of the on-line setting by balancing deliberative planning and real-time response.

I present skill bootstrapping, a proposed new research direction for agent learning and planning that allows an agent to start with low-level primitive actions, and develop skills that can be used for higher-level planning. Skills are developed over the course of solving many different problems in a domain, using reinforcement learning techniques to complement the benefits and disadvantages of heuristic-search planning. I describe the overall architecture of the proposed approach and discuss how it relates to other work.

Low-level direct commanding of space robots can be time consuming or impractical for complex systems with many degrees of freedom. My research will adaptively raise the level of interaction between the operator and the robot by (1) allowing the robot to learn implicit plans by detecting patterns in the interaction history, and (2) enabling the human to demonstrate continuous motions through teleoperation. Learned tasks and plans are recorded for future use. I introduce a novel representation of continuous actions called parameterized probabilistic flow tubes that I hypothesize will more closely encode a human's intended motions and provide flexibility during execution in new situations. I also introduce the use of planning for plan recognition in the domain of hybrid tasks.

The success of autonomous vehicles has made path planning in real, physically grounded environments an increasingly important problem. In environments where speed matters and vehicles must maneuver around obstructions, such as autonomous car navigation in hostile environments, the speed with which real vehicles can traverse a path is often dependent on the sharpness of the corners on the path as well as the length of path edges. We present an algorithm that incorporates the use of the turn angle through path nodes as a limiting factor for vehicle speed. Vehicle speed is then used in a time-weighting calculation for each edge. This allows the path planning algorithm to choose potentially longer paths, with less turns in order to minimize path traversal time. Results simulated in the Breve environment show that travel time can be reduced over the solution obtained using the Anytime D* Algorithm by approximately 10% for a vehicle that is speed limited based on turn rate.

Probabilistic programing is an emerging field at the intersection of statistical learning and programming languages. An appealing property of probabilistic programming languages (PPL) is their support for constructing arbitrary probability distributions. This allows one to model many different domains and solve a variety of problems. We show the link between probabilistic planning and PPLs by introducing a translation that allows one to map probabilistic planning problems onto parameter learning in PPLs. The advantage of our approach is twofold. Firstly, having the expressivity of a programming language simplifies modeling compared to using existing planning languages such as PPDDL. Secondly, there exist effective general-purpose learning algorithms that — having the correct encoding — can readily be used to learn optimal policies. In this paper we use ProbLog — a probabilistic version of Prolog — as programming language, but our approach can be applied on any other PPL as well.

Many task execution techniques tend to repeatedly invoke motion planning algorithms in order to perform complex tasks. In order to accelerate the perform of such methods, we present a real-time global motion planner that utilizes the computational capabilities of current many-core GPUs (graphics processing units). Our approach is based on randomized sample-based planners and we describe highly parallel algorithms to generate samples, perform collision queries, nearest-neighbor computations, local planning and graph search to compute collision-free paths for rigid robots. Our approach can efficiently solve the single-query and multiquery versions of the planning problem and can obtain one to two orders of speedup over prior CPU-based global planning algorithms. The resulting GPU-based planning algorithm can also be used for real-time feedback for task execution in challenging scenarios.