13948516
Planning in Models that Combine Memory with Predictive Representations of State
Models of dynamical systems based on predictive state representations (PSRs) use predictions of future observations as their representation of state. A main departure from traditional models such as partially observable Markov decision processes (POMDPs) is that the PSR-model state is composed entirely of observable quantities. PSRs have recently been extended to a class of models called memory-PSRs (mPSRs) that use both memory of past observations and predictions of future observations in their state representation. Thus, mPSRs preserve the PSR-property of the state being composed of observable quantities while potentially revealing structure in the dynamical system that is not exploited in PSRs. In this paper, we demonstrate that the structure captured by mPSRs can be exploited quite naturally for stochastic planning based on value-iteration algorithms. In particular, we adapt the incremental-pruning (IP) algorithm defined for planning in POMDPs to mPSRs. Our empirical results show that our modified IP on mPSRs outperforms, in most cases, IP on both PSRs and POMDPs.
2661414
Graphical Models for Game Theory
We introduce a compact graph-theoretic representation for multi-party game theory. Our main result is a provably correct and efficient algorithm for computing approximate Nash equilibria in one-stage games represented by trees or sparse graphs.
2695116
Near-Optimal Reinforcement Learning in Polynomial Time
We present new algorithms for reinforcement learning and prove that they have polynomial bounds on the resources required to achieve near-optimal return in general Markov decision processes. After observing that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or by the horizon time T (in the discounted case), we then give algorithms requiring a number of actions and total computation time that are only polynomial in T and the number of states and actions, for both the undiscounted and discounted cases. An interesting aspect of our algorithms is their explicit handling of the Exploration-Exploitation trade-off.
5053575
Bias-Variance Error Bounds for Temporal Difference Updates
Temporal difference (td) algorithms are used in reinforcement learning to compute estimates of the value of a given policy in an unknown Markov decision process (policy evaluation). We give rigorous upper bounds on the error of the closely related phased td algorithms (which differ from the standard updates in their treatment of the learning rate) as a function of the amount of experience. These upper bounds prove exponentially fast convergence, with both the rate of convergence and the asymptote strongly dependent on the length of the backups k or the parameter . Our bounds give formal verification to the well-known intuition that td methods are subject to a bias-variance tradeoff, and they lead to schedules for k and that are predicted to be better than any fixed values for these parameters. We give preliminary experimental confirmation of our theory for a version of the random walk problem.
7241207
Intrinsically Motivated Reinforcement Learning
Psychologists call behavior intrinsically motivated when it is engaged in for its own sake rather than as a step toward solving a specific problem of clear practical value. But what we learn during intrinsically motivated behavior is essential for our development as competent autonomous entities able to efficiently solve a wide range of practical problems as they arise. In this paper we present initial results from a computational study of intrinsically motivated reinforcement learning aimed at allowing artificial agents to construct and extend hierarchies of reusable skills that are needed for competent autonomy.
2624439
Learning Predictive State Representations
We introduce the first algorithm for learning predictive state representations (PSRs), which are a way of representing the state of a controlled dynamical system. The state representation in a PSR is a vector of predictions of tests, where tests are sequences of actions and observations said to be true if and only if all the observations occur given that all the actions are taken. The problem of finding a good PSR. one that is a sufficient statistic for the dynamical system--can be divided into two parts: 1) discovery of a good set of tests, and 2) learning to make accurate predictions for those tests. In this paper, we present detailed empirical results using a gradient-based algorithm for addressing the second problem. Our results demonstrate several sample systems in which the algorithm learns to make correct predictions and several situations in which the algorithm is less successful. Our analysis reveals challenges that will need to be addressed in future PSR learning algorithms.
570980
An efficient on-line path planner for outdoor mobile robots
Abstract Mobile robots operating in outdoor unstructured environments often have only incomplete maps and must deal with new objects found during traversal. Path planning in these environments must be incremental to accommodate new information and must use efficient representations. This article reports recent results in path planning using an efficient data structure (framed-quadtrees) and an optimal algorithm (D*) to incrementally replan optimal paths. We show how the use of framed-quadtrees leads to paths that are shorter and more direct than when other representations are used. We also show the difference in performance when the robot starts with no information about the world versus when it starts with partial information about the world. Our results indicate that, as would be expected, starting with partial information is better than starting with no information. However, in many cases, partial information results in performance that is almost as good as starting out with complete information about the world, while the computational cost incurred is significantly lower. Our system has been tested in simulation as well on an autonomous jeep equipped with local obstacle avoidance capabilities. Results from both simulation and real experimentation are discussed.
17852912
Lock Free Data Structures Using STM in Haskell
This paper explores the feasibility of re-expressing concurrent algorithms with explicit locks in terms of lock free code written using Haskell's implementation of software transactional memory. Experimental results are presented which show that for multi-processor systems the simpler lock free implementations offer superior performance when compared to their corresponding lock based implementations.
1919208
Texture Analysis Experiments with Meastex and Vistex Benchmarks
The analysis of texture in images is an important area of study. Image benchmarks such as Meastex and Vistex have been developed for researchers to compare their experiments on these texture benchmarks. In this paper we compare five different texture analysis methods on these benchmarks in terms of their recognition ability. Since these benchmarks are limited in terms of their content, we have divided each image into n images and performed our analysis on a larger data set. In this paper we investigate how well the following texture extraction methods perform: autocorrelation, co-occurrence matrices, edge frequency, Law's, and primitive length. We aim to determine if some of these methods outperform others by a significant margin and whether by combining them into a single feature set will have a significant impact on the overall recognition performance. For our analysis we have used the linear and nearest neighbour classifiers.
14183054
Framed-quadtree path planning for mobile robots operating in sparse environments
Mobile robots operating in vast outdoor unstructured environments often only have incomplete maps and must deal with new objects found during traversal. Path planning in such sparsely occupied regions must be incremental to accommodate new information, and, must use efficient representations. In previous work we have developed an optimal method D* to plan paths when the environment is not known ahead of time, but, rather is discovered as the robot moves around. To date, D* has been applied to a uniform grid representation for obstacles and free space. In this paper we propose the use of D* with framed quadtrees to improve the efficiency of planning paths in sparse environments. The new system has been tested in simulation as well on an autonomous jeep, equipped with local obstacle avoidance capabilities. We show how the use of framed quadtrees improves performance in terms of path length, computation speed, and memory requirements.
3396566
U-DBMS: A Database System for Managing Constantly-Evolving Data
In many systems, sensors are used to acquire information from external environments such as temperature, pressure and locations. Due to continuous changes in these values, and limited resources (e.g., network bandwidth and battery power), it is often infeasible for the database to store the exact values at all times. Queries that uses these old values can produce invalid results. In order to manage the uncertainty between the actual sensor value and the database value, we propose a system called U-DBMS. U-DBMS extends the database system with uncertainty management functionalities. In particular, each data value is represented as an interval and a probability distribution function, and it can be processed with probabilistic query operators to produce imprecise (but correct) answers. This demonstration presents a PostgreSQL-based system that handles uncertainty and probabilistic queries for constantly-evolving data.