Thomas Dean

AAAI Conference 2012 Conference Paper

Three Controversial Hypotheses Concerning Computation in the Primate Cortex

• Thomas Dean
• Greg Corrado
• Jonathon Shlens

We consider three hypotheses concerning the primate neocortex which have influenced computational neuroscience in recent years. Is the mind modular in terms of its being profitably described as a collection of relatively independent functional units? Does the regular structure of the cortex imply a single algorithm at work, operating on many different inputs in parallel? Can the cognitive differences between humans and our closest primate relatives be explained in terms of a scalable cortical architecture? We bring to bear diverse sources of evidence to argue that the answers to each of these questions — with some judicious qualifications — are in the affirmative. In particular, we argue that while our higher cognitive functions may interact in a complicated fashion, many of the component functions operate through well-defined interfaces and, perhaps more important, are built on a neural substrate that scales easily under the control of a modular genetic architecture. Processing in the primary sensory cortices seem amenable to similar algorithmic principles, and, even for those cases where alternative principles are at play, the regular structure of cortex allows the same or greater advantages as the architecture scales. Similar genetic machinery to that used by nature to scale body plans has apparently been applied to scale cortical computations. The resulting replicated computing units can be used to build larger working memory and support deeper recursions needed to qualitatively improve our abilities to handle language, abstraction and social interaction.

AAAI Conference 2007 Conference Paper

On the Prospects for Building a Working Model of the Visual Cortex

• Thomas Dean

AAAI Conference 2005 Conference Paper

A Computational Model of the Cerebral Cortex

• Thomas Dean

Our current understanding of the primate cerebral cortex (neocortex) and in particular the posterior, sensory association cortex has matured to a point where it is possible to develop a family of graphical models that capture the structure, scale and power of the neocortex for purposes of associative recall, sequence prediction and pattern completion among other functions. Implementing such models using readily available computing clusters is now within the grasp of many labs and would provide scientists with the opportunity to experiment with both hard-wired connection schemes and structure-learning algorithms inspired by animal learning and developmental studies. While neural circuits involving structures external to the neocortex such as the thalamic nuclei are less well understood, the availability of a computational model on which to test hypotheses would likely accelerate our understanding of these circuits. Furthermore, the existence of an agreedupon cortical substrate would not only facilitate our understanding of the brain but enable researchers to combine lessons learned from biology with state-of-theart graphical-model and machine-learning techniques to design hybrid systems that combine the best of biological and traditional computing approaches.

AIJ Journal 2003 Journal Article

Equivalence notions and model minimization in Markov decision processes

• Robert Givan
• Thomas Dean
• Matthew Greig

Many stochastic planning problems can be represented using Markov Decision Processes (MDPs). A difficulty with using these MDP representations is that the common algorithms for solving them run in time polynomial in the size of the state space, where this size is extremely large for most real-world planning problems of interest. Recent AI research has addressed this problem by representing the MDP in a factored form. Factored MDPs, however, are not amenable to traditional solution methods that call for an explicit enumeration of the state space. One familiar way to solve MDP problems with very large state spaces is to form a reduced (or aggregated) MDP with the same properties as the original MDP by combining “equivalent” states. In this paper, we discuss applying this approach to solving factored MDP problems—we avoid enumerating the state space by describing large blocks of “equivalent” states in factored form, with the block descriptions being inferred directly from the original factored representation. The resulting reduced MDP may have exponentially fewer states than the original factored MDP, and can then be solved using traditional methods. The reduced MDP found depends on the notion of equivalence between states used in the aggregation. The notion of equivalence chosen will be fundamental in designing and analyzing algorithms for reducing MDPs. Optimally, these algorithms will be able to find the smallest possible reduced MDP for any given input MDP and notion of equivalence (i. e. , find the “minimal model” for the input MDP). Unfortunately, the classic notion of state equivalence from non-deterministic finite state machines generalized to MDPs does not prove useful. We present here a notion of equivalence that is based upon the notion of bisimulation from the literature on concurrent processes. Our generalization of bisimulation to stochastic processes yields a non-trivial notion of state equivalence that guarantees the optimal policy for the reduced model immediately induces a corresponding optimal policy for the original model. With this notion of state equivalence, we design and analyze an algorithm that minimizes arbitrary factored MDPs and compare this method analytically to previous algorithms for solving factored MDPs. We show that previous approaches implicitly derive equivalence relations that we define here.

AIJ Journal 2003 Journal Article

Solving factored MDPs using non-homogeneous partitions

• Kee-Eung Kim
• Thomas Dean

We present an algorithm for aggregating states in solving large MDPs (represented as factored MDPs) using search by successive refinement in the space of non-homogeneous partitions. Homogeneity is defined in terms of stochastic bisimulation and reward equivalence within blocks of a partition. Since homogeneous partitions that define equivalent reduced-state-space MDPs can have a large number of blocks, we relax the requirement of homogeneity. The algorithm constructs approximate aggregate MDPs from non-homogeneous partitions, solves the aggregate MDPs exactly, and then uses the resulting value functions as part of a heuristic in refining the current best non-homogeneous partition. We outline the theory motivating the use of this heuristic and present empirical results. In addition to investigating more exhaustive local search methods we explore the use of techniques derived from research on discretizing continuous state spaces. Finally, we compare the results from our algorithms which search in the space of non-homogeneous partitions with exact and approximate algorithms which represent homogeneous and approximately homogeneous partitions as decision trees or algebraic decision diagrams.

AIJ Journal 2000 Journal Article

Bounded-parameter Markov decision processes

• Robert Givan
• Sonia Leach
• Thomas Dean

In this paper, we introduce the notion of a bounded-parameter Markov decision process (BMDP) as a generalization of the familiar exact MDP. A bounded-parameter MDP is a set of exact MDPs specified by giving upper and lower bounds on transition probabilities and rewards (all the MDPs in the set share the same state and action space). BMDPs form an efficiently solvable special case of the already known class of MDPs with imprecise parameters (MDPIPs). Bounded-parameter MDPs can be used to represent variation or uncertainty concerning the parameters of sequential decision problems in cases where no prior probabilities on the parameter values are available. Bounded-parameter MDPs can also be used in aggregation schemes to represent the variation in the transition probabilities for different base states aggregated together in the same aggregate state. We introduce interval value functions as a natural extension of traditional value functions. An interval value function assigns a closed real interval to each state, representing the assertion that the value of that state falls within that interval. An interval value function can be used to bound the performance of a policy over the set of exact MDPs associated with a given bounded-parameter MDP. We describe an iterative dynamic programming algorithm called interval policy evaluation that computes an interval value function for a given BMDP and specified policy. Interval policy evaluation on a policy π computes the most restrictive interval value function that is sound, i. e. , that bounds the value function for π in every exact MDP in the set defined by the bounded-parameter MDP. We define optimistic and pessimistic criteria for optimality, and provide a variant of value iteration (Bellman, 1957) that we call interval value iteration that computes policies for a BMDP that are optimal with respect to these criteria. We show that each algorithm we present converges to the desired values in a polynomial number of iterations given a fixed discount factor.

ICAPS Conference 1998 Conference Paper

A Conditional Scheduling Approach to Designing Real-Time Systems

• Lloyd G. Greenwald
• Thomas Dean

Wepresent an approachto designing real-time systems based on dynamically sequencing condition-specific task-execution schedules. A system that dynamically alters its real-time execution componentprovides flexibility in the face of changingon-line conditions. For domainsin wttich real-time response and safety must be guaranteedat design time, achieving this flexibility requires the introduction of newmodelingand analysis tools. Weprovide a~lalytical techniques for validating the belmvior of a real-time system designed under our conditional scheduling approach. Wcdemonstrate the approach through the detailed design and analysis of a real-time avionics scheduling solution. This solution involves architectural changesto existing avionics system hardware and makes use of predictive models of in-flight dynamicsto provide real-time behavior guarantees at design time. The approach described in this paper is an exampleof tim use of a general framework that we have developed for analyzing tradeoffs when designing systems in which an agent with limited computational resources is required to respond in a timely mannerto situations arising in a dynamicenvironment.

AAAI Conference 1997 Conference Paper

Model Minimization in Markov Decision Processes

• Thomas Dean

We use the notion of stochastic bisimulation hornogene&y to analyze planning problems represented as Markov decision processes (MDPs). Informally, a partition of the state space for an MDP is said to be homogeneous if for each action, states in the same block have the same probability of being carried to each other block. We provide an algorithm for finding the coarsest homogeneous reflnement of any partition of the state space of an MDP. The resulting partition can be used to construct a reduced MDP which is minimal in a well defined sense and can be used to solve the original MDP. Our algorithm is an adaptation of known automata minimization algorithms, and is designed to operate naturally on factored or implicit representations in which the full state space is never explicitly enumerated. We show that simple variations on this algorithm are equivalent or closely similar to several different recently published algorithms for fmding optimal solutions to (partially or fully observable) factored Markov decision processes, thereby providing alternative descriptions of the methods and results regarding those algorithms.

AAAI Conference 1996 Conference Paper

Challenge Problems for Artificial Intelligence

• Bart Selman
• Thomas Dean
• Tom M. Mitchell

AI textbooks and papers often discuss the big questions, such as "how to reason with uncertainty", "how to reason efficiently", or "how to improve performance through learning ." It is more difficult, however, to find descriptions of concrete problems or challenges that are still ambitious and interesting, yet not so open-ended. The goal of this panel is to formulate a set of such challenge problems for the field. Each panelist was asked to formulate one or more challenges. The emphasis is on problems for which there is a good chance that they will be resolved within the next five to ten years.

IJCAI Conference 1995 Conference Paper

Decomposition Techniques for Planning in Stochastic Domains

• Thomas Dean
• Shieu-Hong I in

This paper is concerned with modeling planning problems involving uncertainty as discrete-time, finite-stale stochastic automata Solving planning problems is reduced to computing policies for Markov decision processes Classical methods for solving Markov decision processes cannot cope with the size of the state spaces for typical problems encountered in practice As an allernative, we investigate methods that decompose global planning problems into a number of local problems solve the local problems separately and then combine the local solutions to generate a global solu tion We present algorithms that decompose planning problems into smaller problems given an arbitrary partition of the state space The local problems are interpreted as Markov decision processes and solutions to the local problems are interpreted as policies restricted to the subsets of the state space defined by the partition One algorithm relies on constructing and solving an abstract version of the original de cision problem A second algorithm itcratively approximates parameters of the local problems to converge to an optimal solution We show how properties of a specified partition affect the time and storage required for Ihese algorithms

AIJ Journal 1995 Journal Article

Learning dynamics: system identification for perceptually challenged agents

• Kenneth Basye
• Thomas Dean
• Leslie Pack Kaelbling

From the perspective of an agent, the input/output behavior of the environment in which it is embedded can be described as a dynamical system. Inputs correspond to the actions executable by the agent in making transitions between states of the environment. Outputs correspond to the perceptual information available to the agent in particular states of the environment. We view dynamical system identification as inference of deterministic finite-state automata from sequences of input/output pairs. The agent can influence the sequence of input/output pairs it is presented by pursuing a strategy for exploring the environment. We identify two sorts of perceptual errors: errors in perceiving the output of a state and errors in perceiving the inputs actually carried out in making a transition from one state to another. We present efficient, high-probability learning algorithms for a number of system identification problems involving such errors. We also present the results of empirical investigations applying these algorithms to learning spatial representations.

AIJ Journal 1995 Journal Article

Planning under time constraints in stochastic domains

• Thomas Dean
• Leslie Pack Kaelbling
• Jak Kirman
• Ann Nicholson

We provide a method, based on the theory of Markov decision processes, for efficient planning in stochastic domains. Goals are encoded as reward functions, expressing the desirability of each world state; the planner must find a policy (mapping from states to actions) that maximizes future rewards. Standard goals of achievement, as well as goals of maintenance and prioritized combinations of goals, can be specified in this way. An optimal policy can be found using existing methods, but these methods require time at best polynomial in the number of states in the domain, where the number of states is exponential in the number of propositions (or state variables). By using information about the starting state, the reward function, and the transition probabilities of the domain, we restrict the planner's attention to a set of world states that are likely to be encountered in satisfying the goal. Using this restricted set of states, the planner can generate more or less complete plans depending on the time it has available. Our approach employs several iterative refinement routines for solving different aspects of the decision making problem. We describe the meta-level control problem of deliberation scheduling, allocating computational resources to these routines. We provide different models corresponding to optimization problems that capture the different circumstances and computational strategies for decision making under time constraints. We consider precursor models in which all decision making is performed prior to execution and recurrent models in which decision making is performed in parallel with execution, accounting for the states observed during execution and anticipating future states. We describe experimental results for both the precursor and recurrent problems that demonstrate planning times that grow slowly as a function of domain size and compare their performance to other relevant algorithms.

TIME Conference 1994 Conference Paper

Localized Temporal Reasoning: A State-Based Approach

• Shieu-Hong Lin
• Thomas Dean

We are concerned with temporal reasoning problems where there is uncertainty about the order in which events occur. The task of temporal reasoning is to derive an event sequence consistent with a given set of ordering constraints to achieve a goal. Previous research shows that the associated decision problems are hard even for very restricted cases. In this article, we investigate locality in event ordering and causal dependencies. We present a localized temporal reasoning algorithm that uses subgoals and abstract events to exploit locality. The computational efficiency of our algorithm for a problem instance is quantified by the inherent locality in the instance. We theoretically demonstrate the substantial improvement in performance gained by exploiting locality. This work provides solid evidence of the usefulness of localized reasoning in exploiting locality.

TIME Conference 1994 Invited Paper

Meditations on Time and Space: Expediting Temporal Inference by Exploiting Structure in Time and Space (Abstract)

• Thomas Dean

ICAPS Conference 1994 Conference Paper

Solving Time-critical Decision-making Problems with Predictable Computational Demands

• Thomas Dean
• Lloyd G. Greenwald

In this work we present an approach to solving time-critical decision-making problems by taking advantage of domain structure to expand the amount of time available for processing difficult combinatorial tasks. Our approach uses predictable variability in computational demands to allocate on-line deliberation time and exploits problem regularity and stochastic models of environmental dynamics to restrict attention to small subsets of the state space. This approach demonstrates howslow, high-level systems (e. g., for planning and scheduling) might interact with faster, more reactive systems (e. g., for real-time execution and monitoring) and enables us to generate timely solutions to difficult combinatorial planning and scheduling problems such as air traffic control.

AAAI Conference 1993 Conference Paper

Planning With Deadlines in Stochastic Domains

• Thomas Dean
• Jak Kirman

AAAI Conference 1992 Conference Paper

Inferring Finite Automata with Stochastic Output Functions and an Application to Map Learning

• Thomas Dean
• Leslie Kaelbling
• Oded Maron

We assume that it is useful for a robot to construct a spatial representation of its environment for navigation purposes. In addition, we assume that robots, like people, make occasional errors in perceiving the spatial features of their environment. Typical perceptual errors include confusing two distinct locations or failing to identify the same location seen at different times. We are interested in the consequences of perceptual uncertainty in terms of the time and space required to learn a map with a given accuracy. We measure accuracy in terms of the probability that the robot correctly identifies a particular underlying spatial configuration. We derive considerable power by providing the robot with routines that allow it to identify landmarks on the basis of local features. We provide a mathematical model of the problem and algorithms that are guaranteed to learn the underlying spatial configuration for a given class of environments with probability 1 - 5 in time polynomial in l/S and some measure of the structural complexity of the environment and the robot’ s ability to discern that structure. Our algorithms apply to a variety of environments that can be modeled as labeled graphs or deterministic finite automata.

AAAI Conference 1992 Conference Paper

Oblivious PAC Learning of Concept Hierarchies

• Thomas Dean
• Leslie Kaelbling
• Oded Maron

In this paper we introduce an extension of the Probably Approximately Correct (PAC) learning model to study the problem of learning inclusion hierarchies of concepts (sometimes called is-a hierarchies) from random examples. Using only the hypothesis representations output over many different runs of a learning algorithm, we wish to reconstruct the partial order (with respect to generality) among the different target concepts used to train the algorithm. We give an efficient algorithm for this problem with the property that each run is oblivious of all other runs: each run can take place in isolation, without access to any examples except those of the current target concept, and without access to the current pool of hypothesis representations. Thus, additional mechanisms providing shared information between runs are not necessary for the inference of some nontrivial hierarchies.

AAAI Conference 1990 Conference Paper

An Approach to Reasoning About Continuous Change for Applications in Planning

• Thomas Dean

There are many planning applications that require an agent to coordinate its activities with processes that change continuously over time. Several proposals have been made for combining a temporal logic of time with the differential and integral calculus to provide a hybrid calculus suitable for planning applications. We take one proposal and explore some of the issues involved in implementing a practical system that derives conclusions consistent with such a hybrid calculus. Models for realvalued parameters are specified as systems of ordinary differential equations, and constructs are provided for reasoning about how these models change over time. For planning problems that require projecting the consequences of a set of events from a set of initial conditions and causal rules, a combination of numerical approximation and symbolic math routines and a simple default reasoning strategy provide for an efficient inference engine.

AAAI Conference 1990 Conference Paper

Coping with Uncertainty in a Control System for Navigation and Exploration

• Thomas Dean
• Robert Chekaluk
• Moises Lejter

IJCAI Conference 1989 Conference Paper

A Model for Projection and Action

• Keiji Kanazawa
• Thomas Dean

In designing autonomous agents that deal competently with issues involving time and space, there is a tradeoff to be made between guaranteed response-time reactions on the one hand, and flexibility and expressiveness on the other. We propose a model of action with probabilistic reasoning and decision analytic evaluation for use in a layered control architecture. Our model is well suited to tasks that require reasoning about the interaction of behaviors and events in a fixed temporal horizon. Decisions are continuously reevaluated, so that there is no problem with plans becoming obsolete as new information becomes available. In this paper, we are particularly interested in the tradeoffs required to guarantee a fixed reponse time in reasoning about nondeterministic cause-andeflect relationships. By exploiting approximate decision making processes, we are able to trade accuracy in our predictions for speed in decision making in order to improve expected performance in dynamic situations.

IJCAI Conference 1989 Conference Paper

Coping With Uncertainty in Map Learning

• Kenneth Basye
• Thomas Dean
• Jeffrey

IJCAI Conference 1989 Conference Paper

Solving Time-Dependent Planning Problems

• Mark Boddy
• Thomas Dean

A planning problem is time-dependent, if the time spent planning affects the utility of the system's performance. In [Dean and Boddy, 1988], we define a framework for constructing solutions to time-dependent planning problems, called expectation-driven iterative refinement. In this paper, we analyze and solve a moderately complex time-dependent planning problem involving path planning for a mobile robot, as a way of exploring a methodology for applying expectation-driven iterative refinement. The fact that we construct a solution to the proposed problem without appealing to luck or extraordinary inspiration provides evidence that expectation-driven iterative refinement is an appropriate framework for solving time-dependent planning problems.

AAAI Conference 1988 Conference Paper

An Analysis of Time-Dependent Planning

• Thomas Dean

AAAI Conference 1988 Conference Paper

Probabilistic Temporal Reasoning

• Thomas Dean

AIJ Journal 1988 Journal Article

Reasoning about partially ordered events

• Thomas Dean
• Mark Boddy

This paper describes a class of temporal reasoning problems involving events whose order is not completely known. We examine the complexity of such problems and show that for all but trivial cases these problems are likely to be intractable. As an alternative to a complete, but potentially exponential-time decision procedure, we provide a partial decision procedure that reports useful results and runs in polynomial time.

AAAI Conference 1987 Conference Paper

Incremental Causal Reasoning

• Thomas Dean

Causal reasoning comprises a large portion of the inference performed by automatic planners. In this paper, we consider a class of inference systems that are said to be predictive in that they derive certain causal consequences of a base set of premises corresponding to a set of events and constraints on their occurrence. The inference system is provided with a set of rules, referred to as a causal theory, that specifies, with some limited accuracy, the cause and effect relationships between objects and processes in a given domain. As modifications are made to the base set of premises, the inference system is responsible for accounting for all and only those inferences licensed by the premises and current causal theory. Unfortunately, the general decision problem for nontrivial causal theories involving partially ordered events is NP-complete. As an alternative to a complete but potentially exponential-time inference procedure, we describe a limited-inference polynomial-time algorithm capable of dealing with partially ordered events. This algorithm generates a useful subset of those inferences that will be true in all total orders consistent with some specified partial order. The algorithm is incremental and, while it is not complete, it is provably sound.

IJCAI Conference 1987 Conference Paper

Large-Scale Temporal Data Bases for Planning in Complex Domains

• Thomas Dean

Planning in any realistic setting requires the management of an enormous amount of information. This information is generally temporal in nature; prediction, plan choice, and debugging all involve reasoning about time. The assertions manipulated by traditional predicate-calculus data base systems, such as Prolog, are timelessly true. In the temporal data base system described in this paper, the classical data base assertion is replaced with the notion of a tunc token. For any given event or fact type, the data base will typically contain a large number of time tokens of that type. These tokens correspond to different occasions when an event of that type occurred or a fact of that type was made true and remained so for some period of time. This profusion of time tokens of the same type presents a problem for systems supporting temporal deductions of the sort needed in planning. Many routine planning operations must search through the data base for tokens satisfying certain temporal constraints. To expedite these operations, this paper describes a computational framework in which common-sense strategies for organizing temporal facts are exploited to speed search.

IJCAI Conference 1985 Conference Paper

Deadlines, Travel Time, and Robot Problem Solving

• David Miller
• R. James Firby
• Thomas Dean

IJCAI Conference 1985 Conference Paper

Temporal Reasoning Involving Counterfactuals and Disjunctions

• Thomas Dean

This paper describes a mechanism for nonmonotonic temporal reasoning involving counterfactuals and disjunctions. The mechanism supports a method for exploring alternatives well suited to automatic planning. The application of these techniques to robot problem solving is discussed with an emphasis on reasoning about exclusive choices and monitoring the continued warrant and effectiveness of prevention tasks.