14921614
Scaling Reinforcement Learning Algorithms by Learning Variable Temporal Resolution Models
The close connection between reinforcement learning (RL) algorithms and dynamic programming algorithms has fueled research on RL within the machine learning community. Yet, despite increased theoretical understanding, RL algorithms remain applicable to simple tasks only. In this paper I use the abstract framework afforded by the connection to dynamic programming to discuss the scaling issues faced by RL researchers. I focus on learning agents that have to learn to solve multiple structured RL tasks in the same environment. I propose learning abstract environment models where the abstract actions represent “intentions” of achieving a particular state. Such models are variable temporal resolution models because in different parts of the state space the abstract actions span different number of time steps. The operational definitions of abstract actions can be learned incrementally using repeated experience at solving RL tasks. I prove that under certain conditions solutions to new RL tasks can be found by using simulated experience with abstract actions alone.
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.
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.
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.
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.
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.
14312550
Obstacle detection using adaptive color segmentation and color stereo homography
Obstacle detection is a key component of autonomous systems. In particular, when dealing with large robots in unstructured environments, robust obstacle detection is vital. In this paper, we describe an obstacle detection methodology which combines two complementary methods: adaptive color segmentation, and stereo-based color homography. This algorithm is particularly suited for environments in which the terrain is relatively flat and of roughly the same color. We will show results in applying this method to an autonomous outdoor robot.
52828064
Smart-Aloha for Multi-Hop Wireless Networks

This paper presents a novel slotted ALOHA-based protocol for use in ad hoc networks where nodes are equipped with adaptive array smart antennas. The protocol relies on the ability of the antenna and DoA (Direction of Arrival) algorithms to identify the direction of transmitters and then beamform appropriately to maximize SINR (Signal to Interference and Noise Ratio) at the receiver. The performance of the protocol is evaluated using analytical modeling as well as detailed simulation in OPNET and Matlab where we demonstrate the benefits of using smart antennas. The impact of using different number of antenna elements is also studied for this environment.
1823400
Models for Automated Earthmoving
We present a composite forward model of the mechanics of an excavator backhoe digging in soil. This model is used to predict the trajectories developed by a closed-loop force based control scheme given initial conditions, some of which can be controlled (excavator control parameters), some directly measured (shape of the terrain), and some estimated (soil properties). Since soil conditions can vary significantly, it is necessary that soil properties be estimated online. Our models are used to both estimate soil properties and predict contact forces between the excavator and the terrain. In a large set of experiments we have conducted, we find that these models are accurate to within approximately 20% and run about 10 times faster than real-time. In this paper we motivate the development of these models and discuss experimental data from our testbed.
62491573
A Robotic Excavator for Autonomous Truck Loading
Excavators are used for the rapid removal of soil and other materials in mines, quarries, and construction sites. The automation of these machines offers promise for increasing productivity and improving safety. To date, most research in this area has focussed on selected parts of the problem. In this paper, we present a system that completely automates the truck loading task. The excavator uses two scanning laser rangefinders to recognize and localize the truck, measure the soil face, and detect obstacles. The excavator's software decides where to dig in the soil, where to dump in the truck, and how to quickly move between these points while detecting and stopping for obstacles. The system was fully implemented and was demonstrated to load trucks as fast as human operators.
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.