
Graph Element Networks: adaptive, structured computation and memory
We explore the use of graph neural networks (GNNs) to model spatial processes in which there is a priori graphical structure. Similar to finite element analysis, we assign nodes of a GNN to spatial locations and use a computational process defined on the graph to model the relationship between an initial function defined over a space and a resulting function in the same space. We use GNNs as a computational substrate, and show that the locations of the nodes in space as well as their connectivity can be optimized to focus on the most complex parts of the space. Moreover, this representational strategy allows the learned inputoutput relationship to generalize over the size of the underlying space and run the same model at different levels of precision, trading computation for accuracy. We demonstrate this method on a traditional PDE problem, a physical prediction problem from robotics, and a problem of learning to predict scene images from novel viewpoints.
04/18/2019 ∙ by Ferran Alet, et al. ∙ 30 ∙ shareread it

Learning to guide task and motion planning using scorespace representation
In this paper, we propose a learning algorithm that speeds up the search in task and motion planning problems. Our algorithm proposes solutions to three different challenges that arise in learning to improve planning efficiency: what to predict, how to represent a planning problem instance, and how to transfer knowledge from one problem instance to another. We propose a method that predicts constraints on the search space based on a generic representation of a planning problem instance, called scorespace, where we represent a problem instance in terms of the performance of a set of solutions attempted so far. Using this representation, we transfer knowledge, in the form of constraints, from previous problems based on the similarity in score space. We design a sequential algorithm that efficiently predicts these constraints, and evaluate it in three different challenging task and motion planning problems. Results indicate that our approach performs orders of magnitudes faster than an unguided planner
07/26/2018 ∙ by Beomjoon Kim, et al. ∙ 12 ∙ shareread it

STRIPS Planning in Infinite Domains
Many robotic planning applications involve continuous actions with highly nonlinear constraints, which cannot be modeled using modern planners that construct a propositional representation. We introduce STRIPStream: an extension of the STRIPS language which can model these domains by supporting the specification of blackbox generators to handle complex constraints. The outputs of these generators interact with actions through possibly infinite streams of objects and static predicates. We provide two algorithms which both reduce STRIPStream problems to a sequence of finitedomain planning problems. The representation and algorithms are entirely domain independent. We demonstrate our framework on simple illustrative domains, and then on a highdimensional, continuous robotic task and motion planning domain.
01/01/2017 ∙ by Caelan Reed Garrett, et al. ∙ 0 ∙ shareread it

Learning to Rank for Synthesizing Planning Heuristics
We investigate learning heuristics for domainspecific planning. Prior work framed learning a heuristic as an ordinary regression problem. However, in a greedy bestfirst search, the ordering of states induced by a heuristic is more indicative of the resulting planner's performance than mean squared error. Thus, we instead frame learning a heuristic as a learning to rank problem which we solve using a RankSVM formulation. Additionally, we introduce new methods for computing features that capture temporal interactions in an approximate plan. Our experiments on recent International Planning Competition problems show that the RankSVM learned heuristics outperform both the original heuristics and heuristics learned through ordinary regression.
08/03/2016 ∙ by Caelan Reed Garrett, et al. ∙ 0 ∙ shareread it

Focused ModelLearning and Planning for NonGaussian Continuous StateAction Systems
We introduce a framework for model learning and planning in stochastic domains with continuous state and action spaces and nonGaussian transition models. It is efficient because (1) local models are estimated only when the planner requires them; (2) the planner focuses on the most relevant states to the current planning problem; and (3) the planner focuses on the most informative and/or highvalue actions. Our theoretical analysis shows the validity and asymptotic optimality of the proposed approach. Empirically, we demonstrate the effectiveness of our algorithm on a simulated multimodal pushing problem.
07/26/2016 ∙ by Zi Wang, et al. ∙ 0 ∙ shareread it

BackwardForward Search for Manipulation Planning
In this paper we address planning problems in highdimensional hybrid configuration spaces, with a particular focus on manipulation planning problems involving many objects. We present the hybrid backwardforward (HBF) planning algorithm that uses a backward identification of constraints to direct the sampling of the infinite action space in a forward search from the initial state towards a goal configuration. The resulting planner is probabilistically complete and can effectively construct long manipulation plans requiring both prehensile and nonprehensile actions in cluttered environments.
04/12/2016 ∙ by Caelan Reed Garrett, et al. ∙ 0 ∙ shareread it

Objectbased World Modeling in SemiStatic Environments with Dependent DirichletProcess Mixtures
To accomplish tasks in humancentric indoor environments, robots need to represent and understand the world in terms of objects and their attributes. We refer to this attributebased representation as a world model, and consider how to acquire it via noisy perception and maintain it over time, as objects are added, changed, and removed in the world. Previous work has framed this as multipletarget tracking problem, where objects are potentially in motion at all times. Although this approach is general, it is computationally expensive. We argue that such generality is not needed in typical world modeling tasks, where objects only change state occasionally. More efficient approaches are enabled by restricting ourselves to such semistatic environments. We consider a previouslyproposed clusteringbased world modeling approach that assumed static environments, and extend it to semistatic domains by applying a dependent Dirichletprocess (DDP) mixture model. We derive a novel MAP inference algorithm under this model, subject to data association constraints. We demonstrate our approach improves computational performance in semistatic environments.
12/02/2015 ∙ by Lawson L. S. Wong, et al. ∙ 0 ∙ shareread it

Bayesian Optimization with Exponential Convergence
This paper presents a Bayesian optimization method with exponential convergence without the need of auxiliary optimization and without the deltacover sampling. Most Bayesian optimization methods require auxiliary optimization: an additional nonconvex global optimization problem, which can be timeconsuming and hard to implement in practice. Also, the existing Bayesian optimization method with exponential convergence requires access to the deltacover sampling, which was considered to be impractical. Our approach eliminates both requirements and achieves an exponential convergence rate.
04/05/2016 ∙ by Kenji Kawaguchi, et al. ∙ 0 ∙ shareread it

Guiding the search in continuous stateaction spaces by learning an action sampling distribution from offtarget samples
In robotics, it is essential to be able to plan efficiently in highdimensional continuous stateaction spaces for long horizons. For such complex planning problems, unguided uniform sampling of actions until a path to a goal is found is hopelessly inefficient, and gradientbased approaches often fall short when the optimization manifold of a given problem is not smooth. In this paper we present an approach that guides the search of a statespace planner, such as A*, by learning an actionsampling distribution that can generalize across different instances of a planning problem. The motivation is that, unlike typical learning approaches for planning for continuous action space that estimate a policy, an estimated action sampler is more robust to error since it has a planner to fall back on. We use a Generative Adversarial Network (GAN), and address an important issue: search experience consists of a relatively large number of actions that are not on a solution path and a relatively small number of actions that actually are on a solution path. We introduce a new technique, based on an importanceratio estimation method, for using samples from a nontarget distribution to make GAN learning more dataefficient. We provide theoretical guarantees and empirical evaluation in three challenging continuous robot planning problems to illustrate the effectiveness of our algorithm.
11/04/2017 ∙ by Beomjoon Kim, et al. ∙ 0 ∙ shareread it

SamplingBased Methods for Factored Task and Motion Planning
This paper presents a generalpurpose formulation of a large class of discretetime planning problems, with hybrid state and controlspaces, as factored transition systems. Factoring allows state transitions to be described as the intersection of several constraints each affecting a subset of the state and control variables. Robotic manipulation problems with many movable objects involve constraints that only affect several variables at a time and therefore exhibit large amounts of factoring. We develop a theoretical framework for solving factored transition systems with samplingbased algorithms. The framework characterizes conditions on the submanifold in which solutions lie, leading to a characterization of robust feasibility that incorporates dimensionalityreducing constraints. It then connects those conditions to corresponding conditional samplers that can be composed to produce values on this submanifold. We present two domainindependent, probabilistically complete planning algorithms that take, as input, a set of conditional samplers. We demonstrate the empirical efficiency of these algorithms on a set of challenging task and motion planning problems involving picking, placing, and pushing.
01/02/2018 ∙ by Caelan Reed Garrett, et al. ∙ 0 ∙ shareread it

STRIPStream: Integrating Symbolic Planners and Blackbox Samplers
Many planning applications involve complex relationships defined on highdimensional, continuous variables. For example, robotic manipulation requires planning with kinematic, collision, and motion constraints involving robot configurations, object transforms, and robot trajectories. These constraints typically require specialized procedures to sample satisfying values. We extend the STRIPS planning language to support a generic, declarative specification for these procedures while treating their implementation as blackboxes. We provide several domainindependent algorithms that reduce STRIPStream problems to a sequence of finitedomain STRIPS planning problems. Additionally, we describe costsensitive planning within this framework. Finally, we evaluate our algorithms on three robotic task and motion planning domains.
02/23/2018 ∙ by Caelan Reed Garrett, et al. ∙ 0 ∙ shareread it
Tomas LozanoPerez
is this you? claim profile
School of Engineering Professor of Teaching Excellence at MIT, Member of the Computer Science and Artificial Intelligence Laboratory, Associate Director of the Artificial Intelligence Laboratory and Associate Head for Computer Science of MIT's Department of Electrical Engineering and Computer Science.