Richard Dearden

AIJ Journal 2017 Journal Article

Robot task planning and explanation in open and uncertain worlds

• Marc Hanheide
• Moritz Göbelbecker
• Graham S. Horn
• Andrzej Pronobis
• Kristoffer Sjöö
• Alper Aydemir
• Patric Jensfelt
• Charles Gretton

A long-standing goal of AI is to enable robots to plan in the face of uncertain and incomplete information, and to handle task failure intelligently. This paper shows how to achieve this. There are two central ideas. The first idea is to organize the robot's knowledge into three layers: instance knowledge at the bottom, commonsense knowledge above that, and diagnostic knowledge on top. Knowledge in a layer above can be used to modify knowledge in the layer(s) below. The second idea is that the robot should represent not just how its actions change the world, but also what it knows or believes. There are two types of knowledge effects the robot's actions can have: epistemic effects (I believe X because I saw it) and assumptions (I'll assume X to be true). By combining the knowledge layers with the models of knowledge effects, we can simultaneously solve several problems in robotics: (i) task planning and execution under uncertainty; (ii) task planning and execution in open worlds; (iii) explaining task failure; (iv) verifying those explanations. The paper describes how the ideas are implemented in a three-layer architecture on a mobile robot platform. The robot implementation was evaluated in five different experiments on object search, mapping, and room categorization.

ICAPS Conference 2013 Conference Paper

An Approach for Efficient Planning of Robotic Manipulation Tasks

• Richard Dearden
• Chris Burbridge

Robot manipulation is a challenging task for planning as itinvolves a mixture of symbolic planning and geometric plan-ning. We would like to express goals and many action ef-fects symbolically, for example specifying a goal such as forall x, if x is a cup, then x should be on the tray, but to ac-complish this we may need to plan the geometry of fitting allthe cups on the tray and how to grasp, move and release thecups to achieve that geometry. In the ideal case, this couldbe accomplished by a fully hybrid planner that alternates be-tween geometric and symbolic reasoning to generate a solu-tion. However, in practice this is very complex, and the fullpower of this approach may only be required for a small sub-set of problems. Instead, we plan completely symbolically, and then attempt to generate a geometric plan by translatingthe symoblic predicates into geometric relationships. We thenexecute this plan in simulation, and if it fails, we backtrack, first in geometric space, and then if necessary in symbolic. We show that this approach, while not complete, solves anumber of challenging manipulation problems, and demon-strate it running on a robotic platform.

IROS Conference 2013 Conference Paper

Improving robot plans for information gathering tasks through execution monitoring

• Minlue Wang
• Sebastien Canu
• Richard Dearden

Recent advances in navigation and control of robots has increasingly led to systems where the actions are deterministic and the challenge is to collect information about the world using noisy sensors. Examples include search and rescue, Mars rover planning and robotic monitoring tasks. However, theoretical results show that in general these problems are as hard as solving partially observable Markov decision problems (POMDPs). We propose an approach where we build plans assuming both the actions and the observations are reliable, then monitor the execution of the plan and use a value of information calculation to add information gathering actions on-line. We describe two variants: one using a classical contingency planner to generate the initial plan, and the other using a Markov decision problem planner. We show how in both cases the addition of execution monitoring can considerably improve overall performance with lower computational cost than solving the original POMDP.

IJCAI Conference 2013 Conference Paper

Run-Time Improvement of Point-Based POMDP Policies

• Minlue Wang
• Richard Dearden

The most successful recent approaches to partially observable Markov decision problem (POMDP) solving have largely been point-based approximation algorithms. These work by selecting a finite number of belief points, computing alpha-vectors for those points, and using the resulting policy everywhere. However, if during execution the belief state is far from the points, there is no guarantee that the policy will be good. This case occurs either when the points are chosen poorly or there are too few points to capture the whole optimal policy, for example in domains where there are many low probability transitions, such as faults or exogenous events. In this paper we explore the use of an on-line plan repair approach to overcome this difficulty. The idea is to split computation between off-line plan creation and, if necessary, on-line plan repair. We evaluate a variety of heuristics used to determine when plan repair might be useful, and then repair the plan by sampling a small number of additional belief points and recomputing the policy. We show in several domains that the approach is more effective than either off-line planning alone even with much more computation time, or a purely on-line planning based on forward search. We also show that the overhead of checking the heuristics is very small when replanning is unnecessary.

IROS Conference 2012 Conference Paper

Learning operators for manipulation planning

• Chris Burbridge
• Zeyn A. Saigol
• Florian Schmidt 0001
• Christoph Borst 0001
• Richard Dearden

We describe a method for learning planning operators for manipulation tasks from hand-written programs to provide a high-level command interface to a robot manipulator that allows tasks to be specified simply as goals. This is made challenging by the fact that a manipulator is a hybrid system—any model of it consists of discrete variables such as “holding cup” and continuous variables such as the poses of objects and position of the robot. The approach relies on three novel techniques: the action learning from annotated code uses simulation to find PDDL action models corresponding to code fragments. To provide the geometric information needed we use supervised learning to produce a mapping from geometric to symbolic state. The mapping can also be used in reverse to produce a geometric state that makes a set of predicates true, thus allowing desired object positions to be generated during planning. Finally, during execution of the plan we use a partially observable Markov decision problem-based planner to repair the initial plan when unforeseen geometric constraints prevent actions from being executed.

AAAI Conference 2011 Conference Paper

A Switching Planner for Combined Task and Observation Planning

• Moritz Göbelbecker
• Charles Gretton
• Richard Dearden

From an automated planning perspective the problem of practical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the lifetime of the robot it must always respond quickly with new plans that accommodate exogenous events, changing objectives, and the underlying unpredictability of the environment. On the other hand, in order to promote efficient behaviours the planning process must perform computationally expensive reasoning about contingencies and possible revisions of subjective beliefs according to quantitatively modelled uncertainty in acting and sensing. Towards addressing these challenges, we develop a continual planning approach that switches between using a fast satisficing “classical” planner, to decide on the overall strategy, and decision-theoretic planning to solve small abstract subproblems where deeper consideration of the sensing model is both practical, and can significantly impact overall performance. We evaluate our approach in large problems from a realistic robot exploration domain.

AIJ Journal 2010 Journal Article

Planning to see: A hierarchical approach to planning visual actions on a robot using POMDPs

• Mohan Sridharan
• Jeremy Wyatt
• Richard Dearden

Flexible, general-purpose robots need to autonomously tailor their sensing and information processing to the task at hand. We pose this challenge as the task of planning under uncertainty. In our domain, the goal is to plan a sequence of visual operators to apply on regions of interest (ROIs) in images of a scene, so that a human and a robot can jointly manipulate and converse about objects on a tabletop. We pose visual processing management as an instance of probabilistic sequential decision making, and specifically as a Partially Observable Markov Decision Process (POMDP). The POMDP formulation uses models that quantitatively capture the unreliability of the operators and enable a robot to reason precisely about the trade-offs between plan reliability and plan execution time. Since planning in practical-sized POMDPs is intractable, we partially ameliorate this intractability for visual processing by defining a novel hierarchical POMDP based on the cognitive requirements of the corresponding planning task. We compare our hierarchical POMDP planning system (HiPPo) with a non-hierarchical POMDP formulation and the Continual Planning (CP) framework that handles uncertainty in a qualitative manner. We show empirically that HiPPo and CP outperform the naive application of all visual operators on all ROIs. The key result is that the POMDP methods produce more robust plans than CP or the naive visual processing. In summary, visual processing problems represent a challenging domain for planning techniques and our hierarchical POMDP-based approach for visual processing management opens up a promising new line of research.

ICAPS Conference 2009 Conference Paper

Navigation Planning in Probabilistic Roadmaps with Uncertainty

• Michael Lyndon Kneebone
• Richard Dearden

Probabilistic Roadmaps (PRM) are a commonly used class of algorithms for robot navigation tasks where obstacles are present in the environment. We examine the situation where the obstacle positions are not precisely known. A subset of the edges in the PRM graph may possibly intersect the obstacles, and as the robot traverses the graph it can make noisy observations of these uncertain edges to determine if it can traverse them or not. The problem is to traverse the graph from an initial vertex to a goal without taking a blocked edge, and to do this optimally the robot needs to consider the observations it can make as well as the structure of the graph. In this paper we show how this problem can be represented as a POMDP. We show that while too large to be solved with exact methods, approximate point based methods can provide a good quality solution. While feasible for smaller examples, this approach isn't scalable. By exploiting the structure in the belief space, we can construct an approximate belief-space MDP that can be solved efficiently using recent techniques in MDP planning. We then demonstrate that this gives near optimal results in most cases while achieving an order of magnitude speed-up in policy generation time.

ICAPS Conference 2008 Conference Paper

HiPPo: Hierarchical POMDPs for Planning Information Processing and Sensing Actions on a Robot

• Mohan Sridharan
• Jeremy L. Wyatt
• Richard Dearden

Flexible general purpose robots need to tailor their visual processing to their task, on the fly. We propose a new approach to this within a planning framework, where the goal is to plan a sequence of visual operators to apply to the regions of interest (ROIs) in a scene. We pose the visual processing problem as a Partially Observable Markov Decision Process (POMDP). This requires probabilistic models of operator effects to quantitatively capture the unreliability of the processing actions, and thus reason precisely about trade-offs between plan execution time and plan reliability. Since planning in practical sized POMDPs is intractable we show how to ameliorate this intractability somewhat for our domain by defining a hierarchical POMDP. We compare the hierarchical POMDP approach with a Continual Planning (CP) approach. On a real robot visual domain, we show empirically that all the planning methods outperform naive application of all visual operators. The key result is that the POMDP methods produce more robust plans than either naive visual processing or the CP approach. In summary, we believe that visual processing problems represent a challenging and worthwhile domain for planning techniques, and that our hierarchical POMDP based approach to them opens up a promising new line of research.

UAI Conference 2004 Conference Paper

Dynamic Programming for Structured Continuous Markov Decision Problems

• Zhengzhu Feng
• Richard Dearden
• Nicolas Meuleau
• Richard Washington

We describe an approach for exploiting structure in Markov Decision Processes with continuous state variables. At each step of the dynamic programming, the state space is dynamically partitioned into regions where the value function is the same throughout the region. We first describe the algorithm for piecewise constant representations. We then extend it to piecewise linear representations, using techniques from POMDPs to represent and reason about linear surfaces efficiently. We show that for complex, structured problems, our approach exploits the natural structure so that optimal solutions can be computed efficiently.

UAI Conference 2002 Conference Paper

Planning under Continuous Time and Resource Uncertainty: A Challenge for AI

• John L. Bresina
• Richard Dearden
• Nicolas Meuleau
• Sailesh Ramakrishnan
• David E. Smith 0001
• Richard Washington

We outline a class of problems, typical of Mars rover operations, that are problematic for current methods of planning under uncertainty. The existing methods fail because they suffer from one or more of the following limitations: 1) they rely on very simple models of actions and time, 2) they assume that uncertainty is manifested in discrete action outcomes, 3) they are only practical for very small problems. For many real world problems, these assumptions fail to hold. In particular, when planning the activities for a Mars rover, none of the above assumptions is valid: 1) actions can be concurrent and have differing durations, 2) there is uncertainty concerning action durations and consumption of continuous resources like power, and 3) typical daily plans involve on the order of a hundred actions. This class of problems may be of particular interest to the UAI community because both classical and decision-theoretic planning techniques may be useful in solving it. We describe the rover problem, discuss previous work on planning under uncertainty, and present a detailed, but very small, example illustrating some of the difficulties of finding good plans.

ICML Conference 2001 Conference Paper

Structured Prioritised Sweeping

• Richard Dearden

AIJ Journal 2000 Journal Article

Stochastic dynamic programming with factored representations

• Craig Boutilier
• Richard Dearden
• Moisés Goldszmidt

Markov decision processes (MDPs) have proven to be popular models for decision-theoretic planning, but standard dynamic programming algorithms for solving MDPs rely on explicit, state-based specifications and computations. To alleviate the combinatorial problems associated with such methods, we propose new representational and computational techniques for MDPs that exploit certain types of problem structure. We use dynamic Bayesian networks (with decision trees representing the local families of conditional probability distributions) to represent stochastic actions in an MDP, together with a decision-tree representation of rewards. Based on this representation, we develop versions of standard dynamic programming algorithms that directly manipulate decision-tree representations of policies and value functions. This generally obviates the need for state-by-state computation, aggregating states at the leaves of these trees and requiring computations only for each aggregate state. The key to these algorithms is a decision-theoretic generalization of classic regression analysis, in which we determine the features relevant to predicting expected value. We demonstrate the method empirically on several planning problems, showing significant savings for certain types of domains. We also identify certain classes of problems for which this technique fails to perform well and suggest extensions and related ideas that may prove useful in such circumstances. We also briefly describe an approximation scheme based on this approach.

UAI Conference 1999 Conference Paper

Model based Bayesian Exploration

• Richard Dearden
• Nir Friedman
• David Andre

Reinforcement learning systems are often concerned with balancing exploration of untested actions against exploitation of actions that are known to be good. The benefit of exploration can be estimated using the classical notion of Value of Information --- the expected improvement in future decision quality arising from the information acquired by exploration. Estimating this quantity requires an assessment of the agent's uncertainty about its current value estimates for states. In this paper we investigate ways of representing and reasoning about this uncertainty in algorithms where the system attempts to learn a model of its environment. We explicitly represent uncertainty about the parameters of the model and build probability distributions over Q-values based on these. These distributions are used to compute a myopic approximation to the value of information for each action and hence to select the action that best balances exploration and exploitation.

AAAI Conference 1998 Conference Paper

Bayesian Q-Learning

• Richard Dearden

A central problem in learning in complex environmentsis balancing exploration of untested actions against exploitation of actions that are known to be good. The benefit of exploration can be estimated using the classical notion of Value of Information—the expected improvement in future decision quality that might arise from the information acquired by exploration. Estimating this quantity requires an assessment of the agent’s uncertainty about its current value estimates for states. In this paper, we adopt a Bayesian approach to maintaining this uncertain information. We extend Watkins’ Q-learning by maintaining and propagating probability distributions over the Q-values. These distributions are used to compute a myopic approximation to the value of information for each action and hence to select the action that best balances exploration and exploitation. We establish the convergence properties of our algorithm and show experimentally that it can exhibit substantial improvements over other well-known model-free exploration strategies.

AIJ Journal 1997 Journal Article

Abstraction and approximate decision-theoretic planning

• Richard Dearden
• Craig Boutilier

Markov decision processes (MDPs) have recently been proposed as useful conceptual models for understanding decision-theoretic planning. However, the utility of the associated computational methods remains open to question: most algorithms for computing optimal policies require explicit enumeration of the state space of the planning problem. We propose an abstraction technique for MDPs that allows approximately optimal solutions to be computed quickly. Abstractions are generated automatically, using an intensional representation of the planning problem (probabilistic strips rules) to determine the most relevant problem features and optimally solving a reduced problem based on these relevant features. The key features of our method are: abstractions can be generated quickly; the abstract solution can be applied directly to the original problem; and the loss of optimality can be bounded. We also describe methods by which the abstract solution can be viewed as a set of default reactions that can be improved incrementally, and used as a heuristic for search-based planning or other MDP methods. Finally, we discuss certain difficulties that point toward other forms of aggregation for MDPs.

ICML Conference 1996 Conference Paper

Approximate Value Trees in Structured Dynamic Programming

• Craig Boutilier
• Richard Dearden

UAI Conference 1994 Conference Paper

Integrating Planning and Execution in Stochastic Domains

• Richard Dearden
• Craig Boutilier

We investigate planning in time-critical domains represented as Markov Decision Processes, showing that search based techniques can be a very powerful method for finding close to optimal plans. To reduce the computational cost of planning in these domains, we execute actions as we construct the plan, and sacrifice optimality by searching to a fixed depth and using a heuristic function to estimate the value of states. Although this paper concentrates on the search algorithm, we also discuss ways of constructing heuristic functions suitable for this approach. Our results show that by interleaving search and execution, close to optimal policies can be found without the computational requirements of other approaches.