A new paper from the project set to appear at AISTATS 2010:

S. Ross and J. A. Bagnell. Efficient Reductions for Imitation Learning. To appear in Proc. of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2010. [pdf] [supplementary material]

Abstract: Imitation Learning, while applied successfully on many large real-world problems, is typically addressed as a standard supervised learning problem, where it is assumed the training and testing data are i.i.d..  This is not true in imitation learning as the learned policy influences the future test inputs (states) upon which it will be tested. We show that this leads to compounding errors and a regret bound that grows quadratically in the time horizon of the task. We propose two alternative algorithms for imitation learning where training occurs over several episodes of interaction. These two approaches share in common that the learner’s policy is slowly modified from executing the expert’s policy to the learned policy. We show that this leads to stronger performance guarantees and demonstrate the improved performance on two challenging problems: training a learner to play 1) a 3D racing game (Super Tux Kart) and 2) Mario Bros.; given input images from the games and corresponding actions taken by a human expert and near-optimal planner respectively.

There are a number of papers from the project set to appear at ICRA 2010 in May:

P. Henry, C. Vollmer, B. Ferris, and D. Fox. Learning to navigate through crowded environments. To appear in Proc. of the IEEE International Conference on Robotics & Automation (ICRA), 2010. [pdf]

Abstract: The goal of this research is to enable mobile robots to navigate through crowded environments such as indoor shopping malls, airports, or downtown side walks. The key research question addressed in this paper is how to learn planners that generate human-like motion behavior. Our approach uses inverse reinforcement learning (IRL) to learn human-like navigation behavior based on example paths. Since robots have only limited sensing, we extend existing IRL methods to the case of partially observable environments. We demonstrate the capabilities of our approach using a realistic crowd flow simulator in which we modeled multiple scenarios in crowded environments. We show that our planner learned to guide the robot along the flow of people when the environment is crowded, and along the shortest path if no people are around.

B. Tovar and S. M. LaValle. Searching and mapping among indistinguishable convex obstacles. To appear in Proc. of the IEEE International Conference on Robotics & Automation (ICRA), 2010. [pdf]

Abstract: This paper considers a robot that moves in the plane and is only able to sense the cyclic order of landmarks with respect to its current position. No metric information is available regarding the robot or landmark positions; moreover, the robot does not have a compass or odometers (e.g., coordinates). We carefully study the information space of the robot, and establish its capabilities in terms of mapping the environment and accomplishing tasks, such as navigation and patrolling. When the robot moves exclusively inside the convex hull of the set of landmarks, the information space can be nicely characterized as an order type, which provides information powerful enough to determine which points lie inside the convex hulls of subsets of landmarks. Additionally, if the robot is allowed to move outside the convex hull of the set of landmarks, the information space is described with a swap cell decomposition, which is an aspect graph in which each aspect is a cyclic permutation of landmarks. We show how to construct such decomposition through its dual, using two kinds of feedback motion commands based on the landmarks sensed.

J. Yu and S. M. LaValle. Probabilistic shadow information spaces. To appear in Proc. of the IEEE International Conference on Robotics & Automation (ICRA), 2010. [pdf]

Abstract: This paper introduces a Bayesian ?lter that is specifically designed for counting targets that move outside of the field of view while performing a sensor sweep. Information space concepts are used to dramatically reduce the filter complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of view. Previous work assumed perfect observations; however, this paper extends the approach to enable probabilistic disturbances. Practical algorithms are introduced, implemented, and demonstrated for computing the filter outputs based on realistic data.

You can see more publications from the RIRIS project here.

Geoff Gordon and his group have papers appearing in the upcoming ICASSP 2010 and AAMAS 2010:

B. Boots, G. Gordon, and S. Siddiqi. Closing the Learning-Planning Loop with Predictive State Representations (extended abstract). To appear in 9th Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2010. [pdf]

J. Ramos, S. Siddiqi, A. Dubrawski, and G. Gordon. Automatic State Discovery for Unstructured Audio Scene Classification. To appear in 35th International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2010. [pdf]

Abstract: In this paper we present a novel scheme for unstructured audio scene classification that possesses three highly desirable and powerful features: autonomy, scalability, and robustness. Our scheme is based on our recently introduced machine learning algorithm called Simultaneous Temporal And Contextual Splitting (STACS) that discovers the appropriate number of states and efficiently learns accurate Hidden Markov Model (HMM) parameters for the given data. STACS-based algorithms train HMMs up to five times faster than Baum-Welch, avoid the overfitting problem commonly encountered in learning large state-space HMMs using Expectation Maximization (EM) methods such as Baum-Welch, and achieve superior classification results on a very diverse dataset with minimal pre-processing. Furthermore, our scheme has proven to be highly effective for building real-world applications and has been integrated into a commercial surveillance system as an event detection component.

You can see more publications from the RIRIS project here.

Steven LaValle, one of the group’s members, is giving a tutorial on Information Spaces at the upcoming IROS 2009 workshop. More information on the tutorial can be found at http://msl.cs.uiuc.edu/~lavalle/iros09/.

There is also an accompanying paper at http://msl.cs.uiuc.edu/~lavalle/iros09/paper.pdf with a number of minimalist abstract sensor models including detection sensors, gap sensors, and relational sensors as well as minimalist filters that might be interesting to consider when thinking about reduced information spaces.

“An Overview of MOOS-IvP and a Brief Users Guide to the IvP Helm Autonomy Software”

http://dspace.mit.edu/handle/1721.1/45569

“Extending a MOOS-IvP Autonomy System and Users Guide to the IvPBuild Toolbox”

http://dspace.mit.edu/handle/1721.1/46361

“MOOS-IvP Autonomy Tools Users Manual”

http://dspace.mit.edu/handle/1721.1/43708

“A Tour of MOOS-IvP Autonomy Software Modules”

http://dspace.mit.edu/handle/1721.1/44590

Any system with sensors finds itself living in an information space (called I-space for short), whether it wants to or not. What does this mean and why does this happen? Consider a complicated scenario such as a team of robots operating in the real world. What is the appropriate notion of state?

In computer science, state is usually internal, referring to the discrete modes of a computer. In physics and control theory, state usually models the external physical world. We often hear that the most important distinction between these two spaces is discrete vs. continuous; however, the far more important distinction is internal vs. external. For robots deployed in a complicated scenario, it is therefore important to maintain the distinction between these two. There exists an external, physical state space in which a state captures the configuration, phase, or other changeable properties of all physical bodies of interest in the world. In contrast, we refer to the internal, information space as an I-state, which captures the data received from sensors and given to actuators. The external state space should represent everything that is needed to define sensors, control laws, and the task, and ideally nothing more. If the task is to track several vehicles in a city, then the external state should define the city map and all vehicle configurations.

For a complex domain with many agents, such a state space is unwieldy. A naive representation of the internal information space is also unwieldy; in its raw form it is referred to as the history I-space, in which each element is the full history of every sensor reading and control (or action) given up to the current time. Note that the history I-state is always trivially known, whereas reconstructing the precise physical state may be a dif?cult or impossible problem. Most of our research efforts involve mapping the gigantic I-spaces down to reduced I-spaces on which computations can be ef?ciently and reliably performed while ensuring that tasks are achieved.

Recall the celebrated Kalman filter; this Bayesian approach enabled history I-states to be transformed into probability density functions and Kalman further showed that for linear-Gaussian (LG) systems the I-states could be further reduced to Gaussians. This meant that the filter could “live” in a reduced I-space in which each internal state encoded only mean and covariance.