J. Yu and S. M. LaValle. Shortest path set induced vertex ordering and its application to distributed distance optimal formation planning and control on graphs. Conference on Decision and Control, 2013.
L. E. Erickson, J. Yu, Y. Huang, and S. M. LaValle. Counting moving bodies using sparse sensor beams. Autonomous Robots, 2013. Under review.
L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. Controlling wild bodies using discrete transition systems. Autonomous Robots, 2013. Invited submission. Under review.
K. Taylor and S. M. LaValle. Intensity-based navigation with global guarantees. Autonomous Robots, 2013. To appear.
B. Tovar, F. Cohen, L. Bobadilla, J. Czarnowski, and S. M. LaValle. Combinatorial filters: Sensor beams, obstacles, and possible paths. ACM Transactions on Sensor Networks, 2013. To appear.
L. E. Erickson, J. Yu, Y. Huang, and S. M. LaValle. Counting moving bodies using sparse sensor beams. Autonomous Robots, 2013. Under review.
G. Gordon. Galerkin Methods for Complementarity Problems and Variational Inequalities. Technical report arXiv:1306.4753, 2013.
B. Boots, A. Gretton and G. Gordon. Hilbert Space Embeddings of Predictive State Representations. ICML Workshop on Machine Learning and System Identification (MLSYSID), 2013.
B. Boots, A. Gretton and G. Gordon. Hilbert space embeddings of predictive state representations. Uncertainty in Artificial Intelligence (UAI), 2013.
S. Aine and M. Likhachev. Anytime Truncated D*: Anytime Replanning with Truncation. International Symposium on Combinatorial Search (SoCS), 2013.
S. Aine and M. Likhachev. Truncated Incremental Search: Faster Replanning by Exploiting Suboptimality. National Conference on Artificial Intelligence (AAAI), 2013.
J. Yu and S. M. LaValle. Fast, near-optimal computation for multi-robot path planning on graphs. AAAI Conference on Artificial Intelligence (AAAI), 2013. Late breaking paper.
J. Yu and S. M. LaValle. Structure and intractability of optimal multi-robot path planning on graphs. AAAI Conference on Artificial Intelligence (AAAI), 2013.
B. Boots and G. Gordon. A spectral learning approach to range-only SLAM. International Conference on Machine Learning (ICML), 2013.
K. Gochev, A. Safonova and M. Likhachev. Incremental Planning with Adaptive Dimensionality. Incremental Planning with Adaptive Dimensionality. International Conference on Automated Planning and Scheduling (ICAPS), 2013.
F. Duvallet, T. Kollar and A. Stentz. Imitation Learning for Natural Language Direction Following through Unknown Environments. International Conference on Robotics and Automation (ICRA), 2013.
L. H. Erickson and S. M. LaValle. Toward the design and analysis of blind, bouncing robots. International Conference on Robotics and Automation (ICRA), 2013.
M. Katsev, J. Yu, and S. M. LaValle. Efficient formation path planning on large graphs. International Conference on Robotics and Automation (IRCA), 2013.
D. S. Yershov, P. Vernaza, and S.M. LaValle. Continuous planning with winding constraints using optimal heuristic-driven front propagation. International Conference on Robotics and Automation (ICRA), 2013.
D. S. Yershov and S. M. LaValle. Simplicial label correcting algorithms for continuous stochastic shortest path problems. International Conference on Robotics and Automation (ICRA), 2013.
J. Yu and S. M. LaValle. Planning optimal paths for multiple robots on graphs. International Conference on Robotics and Automation (ICRA), 2013.
V. Narayanan, P. Vernaza, M. Likhachev and S. LaValle. Planning Under Topological Constraints Using Beam-Graphs. International Conference on Robotics and Automation (ICRA), 2013.
F. Duvallet, T. Kollar, and A. Stentz. Following Natural Language Directions through Unknown Environments. Human-Robot Interaction Pioneers Workshop 2013, 2013.
B. Boots. A spectral learning approach to learning predictive representations. Doctoral thesis, Carnegie Mellon University, 2012.
S. M. LaValle. Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces. Now Publishers, Delft, The Netherlands, 2012.
B. Boots and G. Gordon. A spectral learning approach to range-only SLAM. NIPS Workshop on Spectral Algorithms for Latent Variable Models, 2012.
B. Boots, A. Gretton and G. Gordon. Hilbert space embeddings of PSRs. NIPS Workshop on Spectral Algorithms for Latent Variable Models, 2012.
G. Gordon. Fast solutions to projective monotone linear complementarity problems. Technical Report arXiv:1212.6958, 2012.
V. Narayanan, M. Phillips and M. Likhachev. Anytime Safe Interval Path Planning for Dynamic Environments. International Conference on Intelligent Robots and Systems (IROS), 2012.
P. Vernaza and J. A. Bagnell. Efficient high dimensional maximum entropy modeling via symmetric partition functions. Neural Information Processing Systems (NIPS), 2012. [pdf]
Abstract: The application of the maximum entropy principle to sequence modeling has been popularized by methods such as Conditional Random Fields (CRFs). However, these approaches are generally limited to modeling paths in discrete spaces of low dimensionality. We consider the problem of modeling distributions over paths in continuous spaces of high dimensionality—a problem for which inference is generally intractable. Our main contribution is to show that maximum entropy modeling of high-dimensional, continuous paths is tractable as long as the constrained features possess a certain kind of low dimensional structure. In this case, we show that the associated {\em partition function} is symmetric and that this symmetry can be exploited to compute the partition function efficiently in a compressed form. Empirical results are given showing an application of our method to maximum entropy modeling of high dimensional human motion capture data.[show]
G. J. Gordon, P. Varakantham, W. Yeoh, H. Chuin Lau, A. S. Aravamudhan and S. Cheng. Lagrangian Relaxation for Large-Scale Multi-Agent Planning. Autonomous Agents and Multiagent Systems (AAMAS), 2012. [pdf]
Abstract: Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of convergence of our algorithm to a near-optimal solution.[show]
S. Bhattacharya, M. Likhachev and V. Kumar. Search-based Path Planning with Homotopy Class Constraints in 3D.
National Conference on Artificial Intelligence (AAAI), 2012. [pdf]
Abstract: Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by grad- ual bending and stretching without colliding with obstacles. The problem of exploring/finding the different homotopy classes in an environment and the problem of finding least-cost paths restricted to a specific ho- motopy class (or not belonging to certain homotopy classes) arises frequently in such applications as pre- dicting paths for unpredictable entities and deployment of multiple agents for efficient exploration of an en- vironment. In (Bhattacharya, Kumar, and Likhachev 2010) we have shown how homotopy classes of trajectories on a two-dimensional plane with obstacles can be classified and identified using the Cauchy Integral Theorem and the Residue Theorem from Complex Analysis. In more recent work (Bhattacharya, Likhachev, and Kumar 2011) we extended this representation to three-dimensional spaces by exploiting certain laws from the Theory of Electromagnetism (Biot-Savart law and Ampere’s Law) for representing and identifying homotopy classes in three dimensions in an efficient way. Using such a representation, we showed that homotopy class constraints can be seamlessly weaved into graph search techniques for determining optimal path constrained to certain homotopy classes or forbidden from others, as well as for exploring different homotopy classes in an environment. [show]
P. Vernaza, V. Narayanan and M. Likhachev. Efficiently finding optimal winding-constrained loops in the plane. Robotics: Science and Systems Conference (RSS), 2012. [pdf]
Abstract: We present a method to efficiently find winding- constrained loops in the plane that are optimal with respect to a minimum-cost objective and in the presence of obstacles. Our approach is similar to a typical graph-based search for an optimal path in the plane, but with an additional state variable that encodes information about path homotopy. Upon finding a loop, the value of this state corresponds to a line integral over the loop that indicates how many times it winds around each obstacle, enabling us to reduce the problem of finding paths satisfying winding constraints to that of searching for paths to suitable states in this augmented state space. We give an intuitive interpretation of the method based on fluid mechanics and show how this yields a way to perform the necessary calculations efficiently. Results are given in which we use our method to find optimal routes for autonomous surveillance and intruder containment.[show]
S. Bhattacharya, M. Likhachev and V. Kumar. Topological Constraints in Search-based Robot Path Planning. Autonomous Robots (AURO), 2012. [pdf]
Abstract: There are many applications in motion planning where it is important to consider and distinguish between different topological classes of trajectories. The two important, but related, topological concepts for classifying manifolds that are of importance to us are those of homotopy and homology. In this paper we consider the problem of robot exploration and planning in Euclidean configuration spaces with obstaclees to (a) identify and represent different homology classes of trajectories; (b) plan trajectories constrained to certain homology classes or avoiding specified homology classes; and (c) explore different homotopy classes of trajectories in an environment and determine the least cost trajectories in each class. We exploit theorems from complex analysis and the theory of electromagnetism to solve the problem 2-dimensional and 3-dimensional configuration spaces respectively. Finally, we describe the extension of these ideas to arbitrary D-dimensional configuration spaces. We incorporate these basic concepts to develop a practical graph-search based planning tool with theoretical guarantees by combining integration theory with search techniques, and illustrate it with several examples.[show]
B. Boots and G. J. Gordon. A spectral learning approach to range-only SLAM. Technical report arXiv:1207.2491, 2012.
[pdf]
Abstract: We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences. This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no local optima. Compared with popular batch optimization or multiple-hypothesis tracking (MHT) methods for range-only SLAM, our spectral approach offers guaranteed low computational requirements and good tracking performance. Compared with popular extended Kalman filter (EKF) or extended information filter (EIF) approaches, and many MHT ones, our approach does not need to linearize a transition or measurement model; such linearizations can cause severe errors in EKFs and EIFs, and to a lesser extent MHT, particularly for the highly non-Gaussian posteriors encountered in range-only SLAM. We provide a theoretical analysis of our method, including finite-sample error bounds. Finally, we demonstrate on a real-world robotic SLAM problem that our algorithm is not only theoretically justified, but works well in practice: in a comparison of multiple methods, the lowest errors come from a combination of our algorithm with batch optimization, but our method alone produces nearly as good a result at far lower computational cost.[show]
B. Boots and G. J. Gordon. Two manifold problems with applications to nonlinear system identification. International Conference on Machine Learning (ICML), 2012. [pdf]
Abstract: Recently, there has been much interest in spectral approaches to learning manifolds — so-called kernel eigenmap methods. These methods have had some successes, but their applicability is limited because they are not robust to noise. To address this limitation, we look at two-manifold problems, in which we simultaneously reconstruct two related manifolds, each representing a different view of the same data. By solving these interconnected learning problems together, two-manifold algorithms are able to succeed where a non-integrated approach would fail: each view allows us to suppress noise in the other, reducing bias. We propose a class of algorithms for two-manifold problems, based on spectral decomposition of cross-covariance operators in Hilbert space, and discuss when two-manifold problems are useful. Finally, we demonstrate that solving a two-manifold problem can aid in learning a nonlinear dynamical system from limited data.[show]
A. Bry, A. Bachrach and N. Roy. State Estimation for Aggressive Flight in GPS-Denied Environments Using Onboard Sensing. IEEE International Conference on Robotics and Automation (ICRA), 2012. Best Conference Paper Finalist. [pdf]
Abstract: In this paper we present a state estimation method based on an inertial measurement unit (IMU) and a planar laser range finder suitable for use in real-time on a fixed- wing micro air vehicle (MAV). The algorithm is capable of maintaing accurate state estimates during aggressive flight in unstructured 3D environments without the use of an external positioning system. Our localization algorithm is based on an extension of the Gaussian Particle Filter. We partition the state according to measurement independence relationships and then calculate a pseudo-linear update which allows us to use 20x fewer particles than a naive implementation to achieve similar accuracy in the state estimate. We also propose a multi-step forward fitting method to identify the noise parameters of the IMU and compare results with and without accurate position measurements. Our process and measurement models integrate naturally with an exponential coordinates representation of the attitude uncertainty. We demonstrate our algorithms experimentally on a fixed-wing vehicle flying in a challenging indoor environment.[show]
L. Chang, J. Smith, and D. Fox. Interactive singulation of objects from a pile. IEEE International Conference on Robotics & Automation (ICRA), 2012. [pdf]
Abstract: Interaction with unstructured groups of objects allows a robot to discover and manipulate novel items in cluttered environments. We present a framework for interactive singulation of individual items from a pile. The proposed framework provides an overall approach for tasks involving operation on multiple objects, such as counting, arranging, or sorting items in a pile. A perception module combined with pushing actions accumulates evidence of singulated items over multiple pile interactions. A decision module scores the likelihood of a single-item pile to a multiple-item pile based on the magnitude of motion and matching determined from the perception module. Three variations of the singulation framework were evaluated on a physical robot for an arrangement task. The proposed interactive singulation method with adaptive pushing reduces the grasp errors on non-singulated piles compared to alternative methods without the perception and decision modules. This work contributes the general pile interaction framework, a specific method for integrating perception and action plans with grasp decisions, and an experimental evaluation of the cost trade-offs for different singulation methods.[show]
K. Gochev, A. Safonova and M. Likhachev. Planning with Adaptive Dimensionality for Mobile Manipulation. IEEE International Conference on Robotics and Automation (ICRA), 2012. [pdf]
Abstract: Mobile manipulation planning is a hard problem composed of multiple challenging sub-problems, some of which require searching through large high-dimensional state-spaces. The focus of this work is on computing a trajectory to safely maneuver an object through an environment, given the start and goal configurations. In this work we present a heuristic search-based deterministic mobile manipulation planner, based on our recently-developed algorithm for planning with adaptive dimensionality. Our planner demonstrates reasonable performance, while also providing strong guarantees on completeness and suboptimality bounds with respect to the graph representing the problem.[show]
H. Zhang, J. Butzke, and M. Likhachev. Combining Global and Local Planning with Guarantees on Completeness. IEEE International Conference on Robotics and Automation (ICRA), 2012. [pdf]
Abstract: Planning with kinodynamic constraints is often required for mobile robots operating in cluttered, complex environments. A common approach is to use a two-dimensional (2-D) global planner for long range planning, and a short range higher dimensional planner or controller capable of satisfying all of the constraints on motion. However, this approach is incomplete and can result in oscillations and the inability to find a path to the goal. In this paper we present an approach to solving this problem by combining the global and local path planning problem into a single search using a combined 2-D and higher dimensional state-space.[show]
S. M. LaValle. Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces. Foundations and Trends in Robotics Series, 2012. [book]
D. Yershov and S. M. LaValle. Simplicial Dijkstra and A* Algorithms for Optimal Feedback Planning. Advanced Robotics, 2012. To appear.
J. Yu and S. M. LaValle. Shadow Information Spaces: Combinatorial Filters for Tracking Targets. IEEE Transactions on Robotics, 28(2):440-456, 2012. [pdf]
Abstract: This paper introduces and solves a problem of maintaining the distribution of hidden targets that move outside the field of view while a sensor sweep is being performed, resulting in a generalization of the sensing aspect of visibility-based pursuit-evasion games. Our solution first applies information space concepts to significantly reduce the general 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 the field of view. The cases of distinguishable, partially distinguishable, and completely indistinguishable targets are handled. Depending on whether the targets move nondeterministically or probabilistically, more specific classes of problems are formulated. For each case, efficient filtering algorithms are introduced, implemented, and demonstrated that provide critical information for tasks such as counting, herding, pursuit-evasion, and situational awareness.[show]
B. Tovar, F. Cohen, L. Bobadilla, J. Czarnowski and S. M. LaValle. Combinatorial Filters: Sensor Beams, Obstacles, and Possible Paths. ACM Transactions on Sensor Networks, 2012. Under review.
L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman and S. M. LaValle. Controlling Wild Bodies Using Discrete Transition Systems. Advanced Robotics, 2012. Invited submission for special issue. Under review.
J. Yu and S. M. LaValle. Time Optimal Multi-agent Path Planning on Graphs. AAAI Workshop on Multiagent Pathfinding (WoMP), 2012. [pdf]
Abstract: Significant progress has been made in the area of multi-agent path finding/planning in the past decade (Silver 2005; van den Berg et al. 2009; Standley 2010; Luna and Bekris 2011; Wang and Botea 2011). In this work, we introduce a multi-agent path planning problem similar to that of (Standley 2010) and aim at maximizing parallelism among the agents. That is, we seek a feasible plan that minimizes the time it takes the last agent to reach its goal. To solve the problem, we convert it into an equivalent multiflow problem, from which an integer linear programming (ILP) problem is readily obtained. Our algorithm is complete.[show]
J. Yu and S. M. LaValle. Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee. IEEE Conference on Decision and Control, 2012. Under review.
M. Arnold, Y. Baryshnikov and S. M. LaValle. Convex Hull Asymptotic Shape Evolution. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf]
Abstract: The asymptotic properties of Rapidly exploring Random Tree (RRT) growth in large spaces is studied both in simulation and analysis. The main phenomenon is that the convex hull of the RRT reliably evolves into an equilateral triangle when grown in a symmetric planar region (a disk). To characterize this and related phenomena from flocking and swarming, a family of dynamical systems based on incremental evolution in the space of shapes is introduced. Basins of attraction over the shape space explain why the number of hull vertices tends to reduce and the shape stabilizes to a regular polygon.[show]
L. Erickson, J. Yu, Y. Huang and S. M. LaValle. Counting Moving Bodies Using Sparse Sensor Beams. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf]
Abstract: This paper examines the problem of determining the distribution of a number of indistinguishable moving bodies located in regions separated by sensor beams that can detect whether a body moves across them. We characterize the conditions under which an exact distribution of bodies can be determined, and bounds on the expected number of sensor observations required to determine this exact distribution for a certain movement model of the bodies.[show]
J. Yu and S. M. LaValle. Multi-agent Path Planning and Network Flow. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf]
Abstract: This paper connects multi-agent path planning on graphs (roadmaps) to network flow problems, showing that the former can be reduced to the latter, therefore enabling the application of combinatorial network flow algorithms, as well as general linear program techniques, to multi-agent path planning problems on graphs. Exploiting this connection, we show that when the goals are permutation invariant, the problem always has a feasible solution path set with a longest finish time of no more than n+V?1 steps, in which n is the number of agents and V is the number of vertices of the underlying graph. We then give a complete algorithm that finds such a solution in O(nVE) time, with E being the number of edges of the graph. Taking a further step, we study time and distance optimality of the feasible solutions, show that they have a pairwise Pareto optimal structure, and again provide efficient algorithms for optimizing each of these practical objectives.[show]
R. Lopez-Padilla, R. Murrieta-Cid and S. M. LaValle. Optimal Gap Navigation for a Disc Robot. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf]
Abstract: This paper considers the problem of globally optimal navigation with respect to Euclidean distance for a disc-shaped, differential-drive robot placed into an unknown, simply connected planar region with piecewise-analytic boundary. The robot is unable to build precise geometric maps or localize itself in any Euclidean frame. Most of the robot’s information comes from a gap sensor, which indicates depth discontinuities and allows the robot to move toward them. A motion strategy is presented that optimally navigates the robot to any landmark in the region. Optimality is proved and the method is illustrated in simulation.[show]
L. Bobadilla, F. Martinez, E. Gobst, K. Gossman and S. M. LaValle. Controlling Wild Mobile Robots Using Virtual Gates and Discrete Transitions. American Control Conference, 2012. [pdf]
Abstract: We present an approach to controlling multiple mobile robots without requiring system identification, geometric map building, localization, or state estimation. Instead, we purposely design them to execute wild motions, which means each will strike every open set infinitely often along the boundary of any connected region in which it is placed. We then divide the environment into a discrete set of regions, with borders delineated with simple markers, such as colored tape. Using simple sensor feedback, we show that complex tasks can be solved, such as patrolling, disentanglement, and basic navigation. The method is implemented in simulation and on real robots, which for many tasks are fully distributed without any mutual communication.[show]
L. Erickson and S. M. LaValle. Navigation among visually connected sets of partially distinguishable landmarks. IEEE International Conference on Robotics and Automation, 2012. [pdf]
Abstract: A robot navigates in a polygonal region populated by a set of partially distinguishable landmarks. The robot’s motion primitives consist of actions of the form “drive toward a landmark of class x”. To effectively navigate, the robot must always be able to see a landmark. Also, if the robot sees two landmarks of the same class, its motion primitives become ambiguous. Finally, if the robot wishes to navigate from landmark s0 to landmark sgoal with a simple graph search algorithm, then there must be a sequence of landmarks [s_0, s_1, s_2, ... , s_k = s_goal], in which landmark s_i is visible from s_{i?1}. Given these three conditions, how many landmark classes are required for navigation in a given polygon P ? We call this minimum number of landmark classes the connected landmark class number, denoted ?CL(P). We study this problem for the monotone polygons, an important family of polygons that are frequently generated as intermediate steps in other decomposition algorithms. We demonstrate that for all odd k, there exists a monotone polygon Mk with 3 (k2 + 2k + 1) vertices such 4 that ?CL(P) ? k. We also demonstrate that for any n-vertex monotone polygon P, ?CL(P) ? n/3 + 12.[show]
B. Boots and G. J. Gordon. Online Spectral Identification of Dynamical Systems. NIPS Workshop on Sparse Representation and Low-rank Approximation, 2011. [pdf]
Abstract: Recently, a number of researchers have proposed spectral algorithms for learning models of dynamical systems—for example, Hidden Markov Models (HMMs), Partially Observable Markov Decision Processes (POMDPs), and Transformed Predictive State Representations (TPSRs). These algorithms are attractive since they are statistically consistent and not sub- ject to local optima. However, they are batch methods: they need to store their entire training data set in mem- ory at once and operate on it as a large matrix, and so they cannot scale to extremely large data sets (either many examples or many features per example). In turn, this restriction limits their ability to learn accurate models of complex systems. To overcome these limitations, we propose a new online spectral algorithm, which uses tricks such as incremental Singular Value Decomposition (SVD) and random projections to scale to much larger data sets and more complex systems than previous methods. We demonstrate the new method on an inertial measurement prediction task and a high-bandwidth video mapping task and we illustrate desirable behaviors such as “closing the loop,” where the latent state representation changes suddenly as the learner recognizes that it has returned to a previously known place.[show]
B. Boots and G. J. Gordon. Two-Manifold Problems. Technical report arXiv:1112.6399, 2011.
[pdf]
Abstract: Recently, there has been much interest in spectral approaches to learning manifolds—so-called kernel eigenmap methods. These methods have had some successes, but their applicability is limited because they are not robust to noise. To address this limitation, we look at two-manifold problems, in which we simultaneously reconstruct two related manifolds, each representing a different view of the same data. By solving these interconnected learning problems together and allowing information to flow between them, two-manifold algorithms are able to succeed where a non-integrated approach would fail: each view allows us to suppress noise in the other, reducing bias in the same way that an instrumental variable allows us to remove bias in a linear dimensionality reduction problem. We propose a class of algorithms for two-manifold problems, based on spectral decomposition of cross-covariance operators in Hilbert space. Finally, we discuss situations where two-manifold problems are useful, and demonstrate that solving a two-manifold problem can aid in learning a nonlinear dynamical system from limited data.[show]
H. Gong, J. Sim, M. Likhachev and J. Shi. Multi-hypothesis Motion Planning for Visual Object Tracking. International Conference on Computer Vision (ICCV), 2011. [pdf]
Abstract: In this paper, we propose a long-term motion model for visual object tracking. In crowded street scenes, persistent occlusions are a frequent challenge for tracking algorithm and a robust, long-term motion model could help in these situations. Motivated by progresses in robot motion planning, we propose to construct a set of ‘plausible’ plans for each person, which are composed of multiple long-term motion prediction hypotheses that do not include redundancies, unnecessary loops or collisions with other objects. Constructing plausible plan is the key step in utilizing motion planning in object tracking, which has not been fully investigate in robot motion planning. We propose a novel method of efficiently constructing disjoint plans in different homotopy classes, based on winding numbers and winding angles of planned paths around all obstacles. As the goals can be specified by winding numbers and winding angles, we can avoid redundant plans in the same homotopy class and multiple whirls or loops around a single obstacle.
We test our algorithm on a challenging, real-world dataset, and compare our algorithm with Linear Trajectory Avoidance and a simplified linear planning model. We find that our algorithm outperforms both algorithms in most sequences.[show]
S. M. LaValle. Motion planning: The essentials. IEEE Robotics and Automation Society. Magazine, 18(1):79–89, 2011. [pdf]
Abstract: This is the first installment of a two-part tutorial. The goal of the first part is to give the reader a basic understanding of the technical issues and types of approaches to solving the basic path planning or obstacle avoidance problem. The second installment will cover more advanced issues, including feedback, differential constraints, and uncertainty. Note that is a brief tutorial, rather than a comprehensive survey of methods. For the latter, consult recent textbooks.
[show]
S. M. LaValle. Motion planning: Wild Frontiers. IEEE Robotics and Automation Society. Magazine, 18(2):108-118, 2011. [pdf]
Abstract: Here we give Part II the two-part tutorial. Part I emphasized the basic problem formulation, mathematical concepts, and the most common solutions. The goal of the Part II is to bring you to understand current robotics challenges from a motion planning perspective.[show]
J. Yu and S. M. LaValle. Shadow information spaces: Combinatorial filters for tracking targets. IEEE Transactions on Robotics, 2011. [pdf]
Abstract: This paper introduces and solves a problem of maintaining the distribution of hidden targets that move outside the field of view while a sensor sweep is being performed, resulting in a generalization of the sensing aspect of visibility-based pursuit-evasion games. Our solution first applies information space concepts to significantly reduce the general 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 the field of view. The cases of distinguishable, partially distinguishable, and completely indistinguishable targets are handled. Depending on whether the targets move nondeterministically or probabilistically, more specific classes of problems are formulated. For each case, efficient filtering algorithms are introduced, implemented, and demonstrated that provide critical information for tasks such as counting, herding, pursuit-evasion, and situational awareness.
[show]
J. Kuffner and S. M. LaValle. Space-filling trees: A new perspective on motion planning via incremental search. Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS), 2011. [pdf]
Abstract: This paper introduces space-filling trees and analyzes them in the context of sampling-based motion planning. Space-filling trees are analogous to space-filling curves, but have a branching, tree-like structure, and are defined by an incremental process that results in a tree for which every point in the space has a finite-length path that converges to it. In contrast to space-filling curves, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. We compare some basic constructions of space-filling trees to Rapidly-exploring Random Trees (RRTs), which underlie a number of popular algorithms used for sampling-based motion planning. We characterize several key tree properties related to path quality and the overall efficiency of exploration and conclude with a number of open mathematical questions.[show]
D. Yershov and S. M. LaValle. Simplicial Dijkstra and A* algorithms for optimal feedback planning. Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS), 2011. [pdf]
Abstract: This paper considers the Euclidean shortest path problem among obstacles in R^n. Adaptations of Dijkstra’s and A* algorithms are introduced that compute the approximate cost-to-go function over a simplicial complex embedded in the free space. Interpolation methods are carefully designed and analyzed so that they are proven to converge numerically to the optimal cost-to-go function. As the result, the computed function produces approximately optimal trajectories. The methods are implemented and demonstrated on 2D and 3D examples. As expected, the simplicial A* algorithm significantly improves performance over the simplicial Dijkstra’s algorithm.[show]
M. Katsev and S. M. LaValle. Learning the delaunay triangulation of landmarks from a distance ordering sensor. Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS), 2011. [pdf]
Abstract: This paper considers a robot that moves in a plane and is only able to sense the distance order of landmarks with respect to its current position. The robot has no access to either metric information about the location of landmarks and its own position, or to odometry or speed controls. We propose several algorithms for the robot that allow it to navigate to certain points in the plane and to learn global information about the landmark locations. We, furthermore, demonstrate example tasks, such as convex hull computation, that can be performed using this information.[show]
L. Bobadilla, O. Sanchez, J. Czarnowski, and S. M. LaValle. Minimalist multiple target tracking using directional sensor beams. Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS), 2011. [pdf]
Abstract: We consider the problem of determining the paths of multiple, unpredictable moving bodies in a cluttered environment using weak detection sensors that provide simple crossing information. Each sensor is a beam that, when broken, provides the direction of the crossing (one bit) and nothing else. Using a simple network of beams, the individual paths are separated and reconstructed as well as possible, up to combinatorial information about the route taken. In this setup, simple filtering algorithms are introduced, and a low-cost hardware implementation that demonstrates the practicality of the approach is shown. The results may apply in settings such as verification of multirobot system execution, surveillance and security, and unobtrusive behavioral monitoring for wildlife and the elderly.[show]
A. Huang, N. Roy, A. Bachrach, P. Henry, M. Krainin, D. Maturana, and D. Fox. Visual odometry and mapping for autonomous flight using an RGB-D camera. International Symposium of Robotics Research (ISRR), 2011. [pdf]
Abstract: RGB-D cameras provide both a color image and per-pixel depth estimates. The richness of their data and the recent development of low-cost sensors have combined to present an attractive opportunity for mobile robotics research. In this paper, we describe a system for visual odometry and mapping using an RGB-D camera, and its application to autonomous flight. By leveraging results from recent state-of-the-art algorithms and hardware, our system enables 3D flight in cluttered environments using only onboard sensor data. All computation and sensing required for local position control are performed onboard the vehicle, eliminating its dependence on unreliable wireless links. We evaluate the effectiveness of our system for stabilizing and controlling a quadrotor micro-air vehicle, demonstrate its use for constructing detailed 3D maps of an indoor environment, and discuss its limitations.[show]
S. Bhattacharya, M. Likhachev and V. Kumar. Identification and Representation of Homotopy Classes of Trajectories for Search-based Path Planning in 3D. Proceedings of Robotics: Science and Systems Conference (RSS), 2011. Best paper award winner. [pdf]
Abstract: There are many applications in motion planning where it is important to consider and distinguish between different homotopy classes of trajectories. Two trajectories are homotopic if one trajectory can be continuously deformed into another without passing through an obstacle, and a homotopy class is a collection of homotopic trajectories. In this paper we consider the problem of robot exploration and planning in three-dimensional configuration spaces to (a) identify and classify different homotopy classes; and (b) plan trajectories constrained to certain homotopy classes or avoiding specified homotopy classes. In previous work [1] we have solved this problem for two-dimensional, static environments using the Cauchy Integral Theorem in concert with graph search techniques. The robot workspace is mapped to the complex plane and obstacles are poles in this plane. The Residue Theorem allows the use of integration along the path to distinguish between trajectories in different homotopy classes. However, this idea is fundamentally limited to two dimensions. In this work we develop new techniques to solve the same problem, but in three dimensions, using theorems from electromagnetism. The Biot-Savart law lets us design an appropriate vector field, the line integral of which, using the integral form of Ampere’s Law, encodes information about homotopy classes in three dimensions. Skeletons of obstacles in the robot world are extracted and are modeled by current- carrying conductors. We describe the development of a practical graph-search based planning tool with theoretical guarantees by combining integration theory with search techniques, and illustrate it with examples in three-dimensional spaces such as two-dimensional, dynamic environments and three-dimensional static environments. [show]
L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. Controlling wild bodies using linear temporal logic. Proceedings of Robotics: Science and Systems (RSS), 2011. [pdf]
Abstract: There is substantial interest controlling a group of bodies from specifications of tasks given in a high-level, humanlike language. This paper proposes a methodology that creates low-level hybrid controllers that guarantee that a group of bodies execute a high-level specified task without dynamical system modeling, precise state estimation or state feedback. We do this by exploiting the wild motions of very simple bodies in an environment connected by gates which serve as the system inputs, as opposed motors on the bodies. We present experiments using inexpensive hardware demonstrating the practical feasibility of our approach to solving tasks such as navigation, patrolling, and coverage.[show]
M. P. Deisenroth, C. E. Rasmussen, and D. Fox. Learning to Control a Low-Cost Manipulator using Data-Efficient Reinforcement Learning. Proceedings of Robotics: Science & Systems (RSS), 2011. [pdf]
Abstract: Over the last years, there has been substantial progress in robust manipulation in unstructured environments. The long-term goal of our work is to get away from precise, but very expensive robotic systems and to develop affordable, potentially imprecise, self-adaptive manipulator systems that can interactively perform tasks such as playing with children. In this paper, we demonstrate how a low-cost off-the-shelf robotic system can learn closed-loop policies for a stacking task in only a handful of trials—from scratch. Our manipulator is inaccurate and provides no pose feedback. For learning a controller in the work space of a Kinect-style depth camera, we use a model-based reinforcement learning technique. Our learning method is data efficient, reduces model bias, and deals with several noise sources in a principled way during long-term planning. We present a way of incorporating state-space constraints into the learning process and analyze the learning gain by exploiting the sequential structure of the stacking task.[show]
L. Bobadilla, K. Gossman, and S. M. LaValle. Manipulating ergodic bodies through gentle guidance. Proceedings of IEEE Conference on Robot Motion and Control, 2011. [pdf]
Abstract: This paper proposes methods for achieving basic tasks such as navigation, patrolling, herding, and coverage by exploiting the wild motions of very simple bodies in the environment. Bodies move within regions that are connected by gates that enforce specific rules of passage. Common issues such as dynamical system modeling, precise state estimation, and state feedback are avoided. The method is demonstrated in a series of experiments that manipulate the flow of weasel balls (without the weasels) and Hexbug Nano vibrating bugs.[show]
B. Boots, S. Siddiqi and G. Gordon. Closing the Learning-Planning Loop with Predictive State Representations. <1em>International Journal of Robotics Research (IJRR), 2011. To appear.
Abstract: A central problem in artificial intelligence is to choose actions to maximize reward in a partially observable, uncertain environment. To do so, we must learn an accurate environment model, and then plan to maximize reward. Unfortunately, learning algorithms often recover a model that is too inaccurate to support planning or too large and complex for planning to succeed; or they require excessive prior domain knowledge or fail to provide guarantees such as statistical consistency. To address this gap, we propose a novel algorithm which provably learns a compact, accurate model directly from sequences of action-observation pairs. We then evaluate the learner by closing the loop from observations to actions. In more detail, we present a spectral algorithm for learning a predictive state representation (PSR), and evaluate it in a simulated, vision-based mobile robot planning task, showing that the learned PSR captures the essential features of the environment and enables successful and efficient planning. Our algorithm has several benefits which have not appeared together in any previous PSR learner: it is computationally efficient and statistically consistent; it handles high-dimensional observations and long time horizons; and, our close-the-loop experiments provide an end-to-end practical test.[show]
A. Grubb, F. Duvallet, S. Tellex, T. Kollar, N. Roy, and A. Stentz, and J. A. Bagnell. Imitation Learning for Natural Language Direction Following. International Conference on Machine Learning Workshop on New Developments in Imitation Learning, 2011.
K. Waugh, Brian D. Ziebart and J. A. Bagnell. Computational Rationalization: The Inverse Equilibrium Problem. Proceedings of the International Joint Conference on Machine Learning (ICML), 2011. Best paper award winner.[pdf]
Abstract: Modeling the behavior of imperfect agents from a small number of observations is a difficult, but important task. In the single-agent decision-theoretic setting, inverse optimal control has been successfully employed. It assumes that observed behavior is an approximately optimal solution to an unknown decision problem, and learns the problem’s parameters that best explain the examples. The inferred parameters can be used to accurately predict future behavior, describe the agent’s preferences, or imitate the agent’s behavior in similar unobserved situations. In this work, we consider similar tasks in competitive and cooperative multi-agent domains. Here, unlike single-agent settings, a player cannot myopically maximize its reward — it must speculate on how the other agents may act to influence the game’s outcome. Employing the game-theoretic notion of regret and the principle of maximum entropy, we introduce a technique for predicting and generalizing behavior, as well as recovering a reward function in these domains.[show]
K. Gochev, B. Cohen, J. Butzke, A. Safonova and M. Likhachev. Path Planning with Adaptive Dimensionality. Proceedings of International Symposium on Combinatorial Search (SoCS), 2011. [pdf]
Abstract: Path planning quickly becomes computationally hard as the dimensionality of the state-space increases. In this paper, we present a planning algorithm intended to speed up path plan- ning for high-dimensional state-spaces such as robotic arms. The idea behind this work is that while planning in a high- dimensional state-space is often necessary to ensure the fea- sibility of the resulting path, large portions of the path have a lower-dimensional structure. Based on this observation, our algorithm iteratively constructs a state-space of an adaptive dimensionality–a state-space that is high-dimensional only where the higher dimensionality is absolutely necessary for finding a feasible path. This often reduces drastically the size of the state-space, and as a result, the planning time and mem- ory requirements. Analytically, we show that our method is complete and is guaranteed to find a solution if one ex- ists, within a specified suboptimality bound. Experimentally, we apply the approach to 3D vehicle navigation (x, y, head- ing), and to a 7 DOF robotic arm on the Willow Garage’s PR2 robot. The results from our experiments suggest that our method can be substantially faster than some of the state-of- the-art planning algorithms optimized for those tasks.[show]
B. Boots and G. Gordon. An Online Spectral Learning Algorithm for Partially Observable Nonlinear Dynamical Systems. Proceedings of the Conference on Artificial Intelligence (AAAI), 2011. [pdf]
Abstract: Recently, a number of researchers have proposed spectral algorithms for learning models of dynamical systems—for example, Hidden Markov Models (HMMs), Partially Observable Markov Decision Processes (POMDPs), and Transformed Predictive State Representations (TPSRs). These algorithms are attractive since they are statistically consistent and not subject to local optima. However, they are batch methods: they need to store their entire training data set in memory at once and operate on it as a large matrix, and so they cannot scale to extremely large data sets (either many examples or many features per example). In turn, this restriction limits their ability to learn accurate models of complex systems. To overcome these limitations, we propose a new online spectral algorithm, which uses tricks such as incremental SVD updates and random projections to scale to much larger data sets and more complex systems than previous methods. We demonstrate the new method on a high-bandwidth video mapping task, and illustrate desirable behaviors such as “closing the loop,” where the latent state representation changes suddenly as the learner recognizes that it has returned to a previously known place.[show]
M. Phillips and M. Likhachev. Planning in Domains with Cost Function Dependent Actions. Proceedings of Association for the Advancement of Artificial Intelligence Conference (AAAI), 2011. [pdf]
Abstract: In a number of graph search-based planning problems, the value of the cost function that is being minimized also affects the set of possible actions at some or all the states in the graph. For example, in path planning for a robot with a limited battery power, a common cost function is energy consumption, whereas the level of re- maining energy affects the navigational capabilities of the robot. Similarly, in path planning for a robot nav- igating dynamic environments, a total traversal time is a common cost function whereas the timestep affects whether a particular transition is valid. In such planning problems, the cost function typically becomes one of the state variables thereby increasing the dimensional- ity of the planning problem, and consequently the size of the graph that represents the problem. In this paper, we show how to avoid this increase in the dimensional- ity for the planning problems whenever the availability of the actions is monotonically non-increasing with the increase in the cost function. We present three variants of A* search for dealing with such planning problems: a provably optimal version, a suboptimal version that scales to larger problems while maintaining a bound on suboptimality, and finally a version that relaxes our as- sumption on the relationship between the cost function and action space. Our experimental analysis on several domains shows that the presented algorithms achieve up to several orders of magnitude speed up over the alter- native approaches to planning.[show]
S. A. Hong and G. Gordon. Optimal Distributed Market-Based Planning for Multi-Agent Systems with Shared Resources. Proceedings of Artificial Intelligence and Statistics, 2011. [pdf]
Abstract: Market-based algorithms have become popu- lar in collaborative multi-agent planning due to their simplicity, distributedness, low com- munication requirements, and proven suc- cess in domains such as task allocation and robotic exploration. Most existing market- based algorithms, however, suffer from two main drawbacks: resource prices must be carefully handcrafted for each problem do- main, and there is no guarantee on final solu- tion quality. We present an optimal market- based algorithm, derived from a mixed in- teger program formulation of planning prob- lems. Our method is based on two well- known techniques for optimization: Dantzig- Wolfe decomposition and Gomory cuts. The former prices resources optimally for a re- laxed version of the problem, while the latter introduces new derivative resources to correct pricing imbalances that arise from the relax- ation. Our algorithm is applicable to a wide variety of multi-agent planning domains. We provide optimality guarantees and demon- strate the effectiveness of our algorithm in both centralized and distributed settings on synthetic planning problems.[show]
S. Ross, G. Gordon and J. A. Bagnell. A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. Proceedings of Artificial Intelligence and Statistics, 2011. [pdf]
Abstract: Sequential prediction problems such as imitation learning, where future observations depend on previous predictions (actions), violate the common i.i.d. assumptions made in statistical learning. This leads to poor performance in theory and often in practice. Some recent approaches provide stronger guarantees in this setting, but remain somewhat unsatisfactory as they train either non-stationary or stochastic policies and require a large number of iterations. In this paper, we propose a new iterative algorithm, which trains a stationary deterministic policy, that can be seen as a no regret algorithm in an online learning setting. We show that any such no regret algorithm, combined with additional reduction assumptions, must find a policy with good performance under the distribution of observations it induces in such sequential settings. We demonstrate that this new approach outperforms previous approaches on two challenging imitation learning problems and a benchmark sequence labeling problem.[show]
B. Tovar, L. Freda and S. M. LaValle. Learning Combinatorial Map Information From Permutations of Landmarks. International Journal of Robotics Research, 2011. [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 (i.e., knowledge of 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 succinctly 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.[show]
M. Katsev, A. Yershova, B. Tovar, R. Ghrist and S. M. LaValle. Mapping and Pursuit-Evasion Strategies For a Simple Wall-Following Robot. IEEE Transactions on Robotics:27(1), 2011. [pdf]
Abstract: This paper de?nes and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented for solving several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.[show]
L. Bobadilla, K. Gossman and S. M. LaValle. Manipulating Ergodic Bodies Through Gentle Guidance. Proceedings of IEEE Conference on Robot Motion and Control, 2011. [pdf]
Abstract: This paper proposes methods for achieving basic tasks such as navigation, patrolling, herding, and coverage by exploiting the wild motions of very simple bodies in the environment. Bodies move within regions that are connected by gates that enforce speci?c rules of passage. Common issues such as dynamical system modeling, precise state estimation, and state feedback are avoided. The method is demonstrated in a series of experiments that manipulate the ?ow of weasel balls(without the weasels) and Hexbug Nano vibrating bugs.[show]
L. Bo, K. Lai, X. Ren, and D. Fox. Object recognition with hierarchical kernel descriptors. In Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2011. [pdf]
Abstract: Kernel descriptors provide a unified way to generate rich visual feature sets by turning pixel attributes into patch-level features, and yield impressive results on many object recognition tasks. However, best results with kernel descriptors are achieved using efficient match kernels in conjunction with nonlinear SVMs, which makes it impractical for large-scale problems. In this paper, we propose hierarchical kernel descriptors that apply kernel descriptors recursively to form image-level features and thus provide a conceptually simple and consistent way to generate imagelevel features from pixel attributes. More importantly, hierarchical kernel descriptors allow linear SVMs to yield stateof-the-art accuracy while being scalable to large datasets. They can also be naturally extended to extract features over depth images. We evaluate hierarchical kernel descriptors both on the CIFAR10 dataset and the new RGB-D Object Dataset consisting of segmented RGB and depth images of 300 everyday objects.[show]
J. Ko and D. Fox. Learning GP-BayesFilters via Gaussian process latent variable models. Autonomous Robots, 30(1), 2011. [pdf]
Abstract: GP-BayesFilters are a general framework for integrating Gaussian process prediction and observation models into Bayesian filtering techniques, including particle filters and extended and unscented Kalman filters. GP-BayesFilters have been shown to be extremely well suited for systems for which accurate parametric models are difficult to obtain. GP-BayesFilters learn non-parametric models from training data containing sequences of control inputs, observations, and ground truth states. The need for ground truth states limits the applicability of GP-BayesFilters to systems for which the ground truth can be estimated without significant overhead. In this paper we introduce GPBF-LEARN, a framework for training GP-BayesFilters without ground truth states. Our approach extends Gaussian Process Latent Variable Models to the setting of dynamical robotics systems. We show how weak labels for the ground truth states can be incorporated into the GPBF-LEARN framework. The approach is evaluated using a difficult tracking task, namely tracking a slotcar based on inertial measurement unit (IMU) observations only. We also show some special features enabled by this framework, including time alignment, and control replay for both the slotcar, and and a robotic arm.[show]
A. Bry and N. Roy. Rapidly-exploring Random Belief Trees for Motion Planning Under Uncertainty. Proceedings of the IEEE Conference on Robotics and Automation (ICRA), 2011. [pdf]
Abstract: In this paper we address the problem of motion planning in the presence of state uncertainty, also known as planning in belief space. The work is motivated by planning domains involving nontrivial dynamics, spatially varying mea- surement properties, and obstacle constraints. To make the problem tractable, we restrict the motion plan to a nominal trajectory stabilized with a linear estimator and controller. This allows us to predict distributions over future states given a can- didate nominal trajectory. Using these distributions to ensure a bounded probability of collision, the algorithm incrementally constructs a graph of trajectories through state space, while ef?ciently searching over candidate paths through the graph at each iteration. This process results in a search tree in belief space that provably converges to the optimal path. We analyze the algorithm theoretically and also provide simulation results demonstrating its utility for balancing information gathering to reduce uncertainty and ?nding low cost paths.[show]
L. Erickson and S. M. LaValle. How Many Landmark Colors Are Needed to Avoid Confusion in a Polygon? Proceedings of IEEE International Conference on Robotics and Automation (ICRA), 2011. [pdf]
Abstract: Suppose that two members of a finite point guard set S within a polygon P must be given different colors if their visible regions overlap, and that every point in P is visible from some point in S. The chromatic art gallery problem, asks for the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of P . We study two related problems. First, given a polygon P and a guard set S of P , can the members of S be effciently and optimally colored so that no two members of S that have overlapping visibility regions have the same color? Second, given a polygon P and a set of candidate guard locations N , is it possible to effciently and optimally choose the guard set S, a subset of N, that requires the minimum number of colors? We provide an algorithm that solves the first question in polynomial time, and demonstrate the NP-hardness of the second question. Both questions are motivated by common robot tasks such as mapping and surveillance.[show]
C. Matuszek, B. Mayton, R. Aimi, L. Bo, M. Deisenroth, R. Chu, M. Kung, L. LeGrand, J. Smith, and D. Fox. Gambit: A robust chess-playing robotic system. In Proc. of the IEEE International Conference on Robotics & Automation (ICRA), 2011. [pdf]
Abstract: This paper presents Gambit, a custom, mid-cost 6-DoF robot manipulator system that can play physical board games against human opponents in non-idealized environments. Historically, unconstrained robotic manipulation in board games has often proven to be more challenging than the underlying game reasoning, making it an ideal testbed for small-scale manipulation. The Gambit system includes a low-cost Kinect-style visual sensor, a custom manipulator, and state-of-the-art learning algorithms for automatic detection and recognition of the board and objects on it. As a use-case, we describe playing chess quickly and accurately with arbitrary, uninstrumented boards and pieces, demonstrating that Gambit’s engineering and design represent a new state-of-the-art in fast, robust tabletop manipulation.[show]
M. Phillips and M. Likhachev. SIPP: Safe Interval Path Planning for Dynamic Environments. Proceedings of IEEE International Conference on Robotics and Automation (ICRA), 2011. [pdf]
Abstract: Robotic path planning in static environments is a thoroughly studied problem that can typically be solved very efficiently. However, planning in the presence of dynamic obstacles is still computationally challenging because it requires adding time as an additional dimension to the search-space explored by the planner. In order to avoid the increase in the dimensionality of the planning problem, most real-time approaches to path planning treat dynamic obstacles as static and constantly re-plan as dynamic obstacles move. Although gaining efficiency, these approaches sacrifice optimality and even completeness. In this paper, we develop a planner that builds on the observation that while the number of safe timesteps in any configuration may be unbounded, the number of safe time intervals in a configuration is finite and generally very small. A safe interval is a time period for a configuration with no collisions and if it were extended one timestep in either direction, it would then be in collision. The planner exploits this observation and constructs a search-space with states defined by their configuration and safe interval, resulting in a graph that generally only has a few states per configuration. On the theoretical side, we show that our planner can provide the same optimality and completeness guarantees as planning with time as an additional dimension. On the experimental side, in simulation tests with up to 200 dynamic obstacles, we show that our planner is significantly faster, making it feasible to use in real-time on robots operating in large dynamic environments. We also ran several real robot trials on the PR2, a mobile manipulation platform.[show]
J. Yu and S. M. LaValle. Story Validation and Approximate Path Inference with a Sparse Network of Heterogeneous Sensors. Proceedings of IEEE International Conference on Robotics and Automation (ICRA), 2011. [pdf]
Abstract: Given a story from an agent (sensor outputs from a robot or a tale told by a human) and recordings from a spare network of heterogeneous sensors, this paper provides ef?cient algorithms that validate whether it is possible to reconstruct a path compatible with the sensor recordings that is also “close” to the agent’s story. In solving the proposed problems, we show that effective exploitation of a unique ?nite automaton structure yields time complexity linear in both the length of the story and the length of the sensor observation history. Besides immediate applicability towards security and forensics problems, the idea of behavior validation using external sensors also appears promising in complementing design time model veri?cation.[show]
B. Boots and G. Gordon. Predictive State Temporal Difference Linearing. Proceedings of Neural Information Processing Systems, 2010. [arXiv]
Abstract: We propose a new approach to value function approximation which combines linear temporal difference reinforcement learning with subspace identification. In practical applications, reinforcement learning (RL) is complicated by the fact that state is either high-dimensional or partially observable. Therefore, RL methods are designed to work with features of state rather than state itself, and the success or failure of learning is often determined by the suitability of the selected features. By comparison, subspace identification (SSID) methods are designed to select a feature set which preserves as much information as possible about state. In this paper we connect the two approaches, looking at the problem of reinforcement learning with a large set of features, each of which may only be marginally useful for value function approximation. We introduce a new algorithm for this situation, called Predictive State Temporal Difference (PSTD) learning. As in SSID for predictive state representations, PSTD finds a linear compression operator that projects a large set of features down to a small set that preserves the maximum amount of predictive information. As in RL, PSTD then uses a Bellman recursion to estimate a value function. We discuss the connection between PSTD and prior approaches in RL and SSID. We prove that PSTD is statistically consistent, perform several experiments that illustrate its properties, and demonstrate its potential on a difficult optimal stopping problem.[show]
P. Henry, M. Krainin, E. Herbst, X. Ren, and D. Fox. RGB-D mapping: Using depth cameras for dense 3D modeling of indoor environments. In Proc. of the International Symposium on Experimental Robotics (ISER), 2010. [pdf]
Abstract: RGB-D cameras are novel sensing systems that capture RGB images along with per-pixel depth information. In this paper we investigate how such cameras can be used in the context of robotics, specifically for building dense 3D maps of indoor environments. Such maps have applications in robot navigation, manipulation, semantic mapping, and telepresence. We present a full 3D mapping system that utilizes a novel joint optimization algorithm combining visual features and shape based alignment. We evaluate our approach on two large indoor environments, and show that our approach effectively combines the visual and shape information available from RGB-D cameras. We describe how we detect and optimize over loop closures, and verify the accuracy of the resulting maps by comparison with existing maps of our test environments. Our dense 3D maps can be efficiently represented as surfels, which are small surface patches allowing for efficient updates and occlusion reasoning. The paper demonstrates that it is possible to build and visualize accurate and extremely rich 3D maps with RGB-D cameras, and that it will be feasible to build complete robot navigation and interaction systems solely based on cheap depth cameras.[show]
B. Ziebart, J. A. Bagnell and A. Dey. Maximum Causal Entropy Correlated Equilibria for Markov Games. Proceedings of Autonomous Agents and Multi-agent Systems (AAMAS), 2010. [pdf]
Abstract: Motivated by a machine learning perspective, that game theoretic equilibria constraints should serve as guidelines for predicting agents’ strategies, we introduce maximum causal entropy correlated equilibria (MCECE), a novel solution concept for general-sum Markov games. In line with this perspective, a MCECE strategy profile is a uniquely-defined joint probability distribution over actions for each game state that minimizes the worst-case prediction of agents’ actions under log-loss. Equivalently, it maximizes the worstcase growth rate for gambling on the sequences of agents’ joint actions under uniform odds. We present a convex optimization technique for obtaining MCECE strategy profiles that resembles value iteration in infnite-horizon games. We assess the predictive benefits of our approach by predicting the strategies generated by previously proposed correlated equilibria solution concepts, and compare against those previous approaches on that same prediction task.[show]
H. Gang, J. Sim, M. Likhachev, and J. Shi. Tracking with Planning. Proc. of the European Conference on Computer Vision (ECCV), 2010. [pdf]
Abstract: Coming Soon![show]
K. Fragkiadaki and J. Shi. Figure-Ground Image Segmentation helps Weakly-Supervised Learning of Objects. Proc. of the European Conference on Computer Vision (ECCV), 2010. [pdf]
Abstract: Given a collection of images containing a common object, we seek to learn a model for the object without using bounding boxes or segmentation masks. We separate image topics into foreground and background. Most salient image parts are likely to capture image foreground. We propose a novel probabilistic model, we call shape and figure-ground aware model (sFGmodel) that exploits figure-ground organization in each image separately, as well as feature re-occurrence across images, to find the common object. We use an image dependent topic prior and optimize a conditional likelihood of the image collection given the image bottom-up saliency information. Our framework can tolerate larger intraclass variability with fewer training data. We present results of our approach on diverse datasets showing great improvement over generative probabilistic models.[show]
S. Bhattacharya , V. Kumar, and M. Likhachev. Distributed Optimization with Pairwise Constraints and its Application to Multi-robot Path Planning. Proc. of the Robots Science and Systems (RSS), 2010. [pdf]
Abstract: Distributed approaches to constrained optimization problems have immense applications to multi-robot path planning, scheduling, task allocation and other problems requiring multiple robots to optimize a global objective function. The aim of these approaches is to solve a series of smaller optimization problems for each robot while sharing information among the robots, and in the process, solve the global optimization problem, which otherwise would have been intractable. Distributed approaches to separable convex optimization problems with linear constraints have been studied extensively in the past using techniques of dual and Lagrangian decomposition. In the present work, we investigate a distributed implementation of a general separable optimization problem with pair-wise non-linear constraints. On the theoretical side, we show the conditions under which the algorithm converges to an optimal solution. On the experimental side, we demonstrate the utility of the algorithm on the problem of multi-robot path planning with pair-wise distance constraints in large complex 2-D environments with obstacles.[show]
S. Bhattacharya , V. Kumar, and M. Likhachev. Path Planning with Homotopy Class Constraints. Proc. of the Association for the Advancement of Artificial Intelligence (AAAI) Conference, 2010. [pdf]
Abstract: Goal-directed path planning is one of the basic and widely studied problems in the field of mobile robotics. Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of finding least-cost paths restricted to a specific homotopy class or finding least-cost paths that do not belong to certain homotopy classes arises frequently in such applications as predicting paths for dynamic entities and computing heuristics for path planning with dynamic constraints. In the present work, we develop a compact way of representing homotopy classes and propose an efficient method of graph search-based optimal path planning with constraints on homotopy classes. The method is based on representing the environment of the robot as a complex plane and making use of the Cauchy Integral Theorem. We prove optimality of the method and show its efficiency experimentally.[show]
B. Tovar, L. Freda and S. M. LaValle. Learning Combinatorial Map Information from Permutations of Landmarks. To appear in the International Journal of Robotics Research, 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 (i.e., knowledge of 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 succinctly 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.[show]
F. Duvallet and A. Stentz. Imitation Learning for Task Allocation. To appear in the Proc. IEEE International Conference on Intelligent Robotics and Systems (IROS), 2010. [pdf]
Abstract: At the heart of multi-robot task allocation lies the ability to compare multiple options in order to select the best. In some domains, this utility computation is not straightforward, for example due to complex and unmodeled underlying dynamics or an adversary in the environment. Explicitly modeling these extrinsic in?uences well enough so that they can be accounted for in utility computation (and thus task allocation) may be intractable, but a human expert may be able to quickly gain some intuition about the form of the desired solution.
We propose to harness the expert’s intuition by applying imitation learning to the multi-robot task allocation domain. Using a market-based task allocation method, we steer the allocation process by biasing prices in the market according to a policy which we learn using a set of demonstrated allocations that represent the expert’s solutions (accounting for external in?uences). We present results in two distinct domains: a disaster response domain where a team of agents must put out fires that are spreading between buildings, and an adversarial game in which teams must make complex strategic decisions to score more points than the opposite team.
[show]
D. Munoz, J. A. Bagnell and M. Hebert. Stacked Hierarchical Labeling. Proc. of the European Conference on Computer Vision (ECCV), 2010. [pdf]
Abstract: In this work we propose a hierarchical approach for labeling semantic objects and regions in scenes. Our approach is reminiscent of early vision literature in that we use a decomposition of the image in order to encode relational and spatial information. In contrast to much existing work on structured prediction for scene understanding, we bypass a global probabilistic model and instead directly train a hierarchical inference procedure inspired by the message passing mechanics of some approximate inference procedures in graphical models. This approach mitigates both the theoretical and empirical difficulties of learning probabilistic models when exact inference is intractable. In particular, we draw from recent work in machine learning and break the complex inference process into a hierarchical series of simple machine learning subproblems. Each subproblem in the hierarchy is designed to capture the image and contextual statistics in the scene. This hierarchy spans coarse-to-fine regions and explicitly models the mixtures of semantic labels that may be present due to imperfect segmentation. To avoid cascading of errors and overfitting, we train the learning problems in sequence to ensure robustness to likely errors earlier in the inference sequence and leverage the stacking approach developed by Cohen et al.[show]
B. D. Ziebart, J. A. Bagnell and A. K. Dey. Modeling Interaction via the Principle of Maximum Causal Entropy. Proc. of the International Conference on Machine Learning (ICML), 2010. [pdf]
Abstract: The principle of maximum entropy provides a powerful framework for statistical models of joint, conditional, and marginal distributions. However, there are many important distributions with elements of interaction and feedback where its applicability has not been established. This work presents the principle of maximum causal entropy–an approach based on causally conditioned probabilities that can appropriately model the availability and influence of sequentially revealed side information. Using this principle, we derive models for sequential data with revealed information, interaction, and feedback, and demonstrate their applicability for statistically framing inverse optimal control and decision prediction tasks.[show]
L. Song, B. Boots, S. M. Siddiqi, G. J. Gordon and A. J. Smola. Hilbert space embeddings of hidden Markov models. Proc. of the International Conference on Machine Learning (ICML), 2010. [pdf]
Abstract: Hidden Markov Models (HMMs) are important tools for modeling sequence data. However, they are restricted to discrete latent states, and are largely restricted to Gaussian and discrete observations. And,learning algorithms for HMMs have predominantly relied on local search heuristics, with the exception of spectral methods such as those described below. We propose a non parametric HMM that extends traditional HMMs to structured and non-Gaussian continuous distributions. Furthermore, we derive a local-minimum-free kernel spectral algorithm for learning these HMMs. We apply our method to robot vision data, slot car inertial sensor data and audio event classification data, and show that in these applications, embedded HMMs exceed the previous state-of-the-art performance.[show]
A. Grubb and J. A. Bagnell. Boosted Backpropagation Learning for Training Deep Modular Networks. Proc. of the International Conference on Machine Learning (ICML), 2010. [pdf]
Abstract: Divide-and-conquer is key to building sophisticated learning machines: hard problems are solved by composing a network of modules that solve simpler problems (LeCun et al., 1998; Rohde, 2002; Bradley, 2009). Many such existing systems rely on learning algorithms which are based on simple parametric gradient descent where the parametrization must be predetermined, or more specialized per-application algorithms which are usually ad-hoc and complicated. We present a novel approach for training generic modular networks that uses two existing techniques: the error propagation strategy of backpropagation and more recent research on descent in spaces of functions (Mason et al., 1999; Scholkopf & Smola, 2001). Combining these two methods of optimization gives a simple algorithm for training heterogeneous networks of functional modules using simple gradient propagation mechanics and established learning algorithms. The resulting separation of concerns between learning individual modules and error propagation mechanics eases implementation, enables a larger class of modular learning strategies, and allows per-module control of complexity/regularization. We derive and demonstrate this functional backpropagation and contrast it with traditional gradient descent in parameter space, observing that in our example domain the method is significantly more robust to local optima. [show]
S. M. Siddiqi, B. Boots and G. J. Gordon. Reduced-rank hidden Markov models. Proc. of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS), 2010. [pdf]
Abstract: Hsu et al.(2009) recently proposed an efficient, accurate spectral learning algorithm for Hidden Markov Models (HMMs). In this paper we relax their assumptions and prove a tighter finite-sample error bound for the case of Reduced-Rank HMMs, i.e., HMMs with low-rank transition matrices. Since rank-k RR-HMMs are a larger class of models than k-state HMMs while being equally efficient to work with, this relaxation greatly increases the learning algorithm’s scope. In addition, we generalize the algorithm and bounds to models where multiple observations are needed to disambiguate state, and to models that emit multivariate real-valued observations. Finally we prove consistency for learning Predictive State Representations, an even larger class of models. Experiments on synthetic data and a toy video, as well as on difficult robot vision data, yield accurate models that compare favorably with alternatives in simulation quality and prediction accuracy. [show]
S. Ross and J. A. Bagnell. Efficient Reductions for Imitation Learning. 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.[show]
A. Yershova, B. Tovar, M. Katsev, R. Ghrist, and S. M. LaValle. Mapping and pursuit-evasion strategies for a simple wall-following robot. Under review for IEEE Transactions on Robotics, 2010. [pdf]
Abstract: This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented for solving several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems. [show]
J. Yu, D. Liberzon, and S. M. LaValle. Rendezvous without coordinates. Under review for IEEE Transactions on Automatic Control, 2010. [pdf]
Abstract: We study minimalism in sensing and control by considering a multi-agent system in which each agent moves like a Dubins car and has a limited sensor that reports only the presence of another agent within some sector of its windshield. Using a very simple quantized control law with three values, each agent tracks another agent assigned to it by maintaining that agent within this windshield sector. We use Lyapunov analysis to show that by acting autonomously in this way, the agents will achieve rendezvous if the initial assignment graph is connected. We then proceed to show that, under a slightly different control law, the sensing model can be weakened further and a connected assignment graph is not necessary. A distinguishing feature of our approach is that it does not involve any estimation procedure aimed at reconstructing coordinate information. Our scenario thus appears to be the first example in which an interesting task is performed with extremely coarse sensing and control, and without state estimation. The system was implemented in computer simulation, accessible through the Web, of which the results are presented in the paper. [show]
B. Boots, G. Gordon, and S. Siddiqi. Closing the Learning-Planning Loop with Predictive State Representations. Proc. of Robotics: Science and Systems VI (RSS), 2010. [pdf]
Abstract: A central problem in artificial intelligence is to choose actions to maximize reward in a partially observable, uncertain environment. To do so, we must learn an accurate model of our environment, and then plan to maximize reward. Unfortunately, learning algorithms often recover a model which is too inaccurate to support planning or too large and complex for planning to be feasible; or, they require large amounts of prior domain knowledge or fail to provide important guarantees such as statistical consistency. To begin to fill this gap, we propose a novel algorithm which provably learns a compact, accurate model directly from sequences of action-observation pairs. To evaluate the learner, we then close the loop from observations to actions: we plan in the learned model and recover a policy which is nearoptimal in the original environment (not the model). In more detail, we present a spectral algorithm for learning a Predictive State Representation (PSR). We demonstrate the algorithm by learning a model of a simulated high-dimensional, vision-based mobile robot planning task, and then performing approximate point-based planning in the learned model. This experiment shows that the learned PSR captures the essential features of the environment, allows accurate prediction with a small number of parameters, and enables successful and efficient planning. Our algorithm has several benefits which have not appeared together in any previous PSR learner: it is computationally efficient and statistically consistent; it handles high-dimensional observations and long time horizons by working from real-valued features of observation sequences; and finally, our close-the-loop experiments provide an end-to-end practical test. [show]
B. Boots, G. Gordon, and S. Siddiqi. Closing the Learning-Planning Loop with Predictive State Representations (extended abstract). Proc. of the 9th Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2010. [pdf]
P. Henry, C. Vollmer, B. Ferris, and D. Fox. Learning to navigate through crowded environments. 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. [show]
B. Tovar and S. M. LaValle. Searching and mapping among indistinguishable convex obstacles. 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. [show]
J. Yu and S. M. LaValle. Probabilistic shadow information spaces. Proc. of the IEEE International Conference on Robotics & Automation (ICRA), 2010. [pdf]
Abstract: This paper introduces a Bayesian filter 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. [show]
J. Ramos, S. Siddiqi, A. Dubrawski, and G. Gordon. Automatic State Discovery for Unstructured Audio Scene Classification. Proc. 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. [show]
J. J. Kuffner and S. M. LaValle. Space-filling trees. Technical Report CMU-RI-TR-09-47, Robotics Institute, Carnegie Mellon University, 2009. [pdf]
Abstract: This paper introduces the notion of space-filling trees, which are analogous to space-filling curves, but have a branching, tree-like structure and are rooted. A space-filling tree is defined by an incremental process that results in a tree for which every point in the space has a finite-length path that converges to it. In contrast to space-filling curves, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. These structures have interesting parallels in nature, including fluid distribution systems, vascular networks, and fractal plant growth, and may have many uses in engineering and computer science. We provide basic examples, general definitions and constructions, characterizations of some tree properties, and leave many open mathematical questions. [show]
S. Siddiqi, B. Boots, and G. Gordon. Reduced-Rank Hidden Markov Models. Technical Report, 2009. [arxiv]
Abstract: We introduce the Reduced-Rank Hidden Markov Model (RR-HMM), a generalization of HMMs that can model smooth state evolution as in Linear Dynamical Systems (LDSs) as well as non-log-concave predictive distributions as in continuous-observation HMMs. RR-HMMs assume an m-dimensional latent state and n discrete observations, with a transition matrix of rank k <= m. This implies the dynamics evolve in a k-dimensional subspace, while the shape of the set of predictive distributions is determined by m. Latent state belief is represented with a k-dimensional state vector and inference is carried out entirely in R^k, making RR-HMMs as computationally efficient as k-state HMMs yet more expressive. To learn RR-HMMs, we relax the assumptions of a recently proposed spectral learning algorithm for HMMs (Hsu, Kakade and Zhang 2009) and apply it to learn k-dimensional observable representations of rank-k RR-HMMs. The algorithm is consistent and free of local optima, and we extend its performance guarantees to cover the RR-HMM case. We show how this algorithm can be used in conjunction with a kernel density estimator to efficiently model high-dimensional multivariate continuous data. We also relax the assumption that single observations are sufficient to disambiguate state, and extend the algorithm accordingly. Experiments on synthetic data and a toy video, as well as on a difficult robot vision modeling problem, yield accurate models that compare favorably with standard alternatives in simulation quality and prediction capability. [show]
S. M. LaValle. Filtering and planning in information spaces. Technical report, Department of Computer Science, University of Illinois, 2009. [pdf]
Abstract: This tutorial presents a fresh perspective on modeling sensors and then using them for filtering and planning. The concepts and tools are motivated by many problems of current interest, such as tracking, monitoring, navigation, pursuit-evasion, exploration, and mapping. First, an overview of sensors that appear in numerous systems is presented. Following this, the notion of a virtual sensor is explained, which provides a mathematical way to model numerous sensors while abstracting away their particular physical implementation. Dozens of useful models are given. In the next part, a new perspective on filtering is given based on information spaces. This includes classics such as the Kalman and Bayesian filters; however, it also opens up a new family of reduced-complexity filters that try to maintain as little information as possible while performing their required task. Finally, the planning problem is presented in terms of filters and information spaces. [show]
J. Ko and D. Fox. Learning GP-BayesFilters via Gaussian Process Latent Variable Models. Proc. Robotics: Science and Systems V, 2009. [pdf]
Abstract: GP-BayesFilters are a general framework for integrating Gaussian process prediction and observation models into Bayesian filtering techniques, including particle filters and extended and unscented Kalman filters. GP-BayesFilters learn nonparametric filter models from training data containing sequences of control inputs, observations, and ground truth states. The need for ground truth states limits the applicability of GP-BayesFilters to systems for which the ground truth can be estimated without prohibitive overhead. In this paper we introduce GPBF-LEARN, a framework for training GP-BayesFilters without any ground truth states. Our approach extends Gaussian Process Latent Variable Models to the setting of dynamical robotics systems. We show how weak labels for the ground truth states can be incorporated into the GPBF-LEARN framework. The approach is evaluated using a difficult tracking task, namely tracking a slotcar based on IMU measurements only. [show]
