Recent efforts recognize the power of scale in 3D learning (e.g. PTv3) and attention mechanisms (e.g. FlashAt-tention). However, current point cloud backbones fail to holistically unify geometric locality, attention mechanisms, and GPU architectures in one view. In this paper, we introduce Flash3D Transformer, which aligns geometric locality and GPU tiling through a principled locality mechanism based on Perfect Spatial Hashing (PSH). The common alignment with GPU tiling naturally fuses our PSH locality mechanism with FlashAttention at negligible extra cost. This mechanism affords flexible design choices throughout the backbone that result in superior downstream task results. Flash3D outperforms state-of-the-art PTv3 results on benchmark datasets, delivering a 2.25x speed increase and 2.4x memory efficiency boost. This efficiency enables scaling to wider attention scopes and larger models without additional overhead. Such scaling allows Flash3D to achieve even higher task accuracies than PTv3 under the same compute budget.

We present DriveGPT, a scalable behavior model for autonomous driving. We model driving as a sequential decision-making task, and learn a transformer model to predict future agent states as tokens in an autoregressive fashion. We scale up our model parameters and training data by multiple orders of magnitude, enabling us to explore the scaling properties in terms of dataset size, model parameters, and compute. We evaluate DriveGPT across different scales in a planning task, through both quantitative metrics and qualitative examples, including closed-loop driving in complex real-world scenarios. In a separate prediction task, DriveGPT outperforms state-of-the-art baselines and exhibits improved performance by pretraining on a large-scale dataset, further validating the benefits of data scaling.

Prevalent imitation learning methods seek to produce behavior that matches or exceeds average human performance. This often prevents achieving expert-level or superhuman performance when identifying the better demonstrations to imitate is difficult. We instead assume demonstrations are of varying quality and seek to induce behavior that is unambiguously better (i.e., Pareto dominant or minimally subdominant) than all human demonstrations. Our minimum subdominance inverse optimal control training objective is primarily defined by high quality demonstrations; lower quality demonstrations, which are more easily dominated, are effectively ignored instead of degrading imitation. With increasing probability, our approach produces superhuman behavior incurring lower cost than demonstrations on the demonstrator’s unknown cost function{—}even if that cost function differs for each demonstration. We apply our approach on a computer cursor pointing task, producing behavior that is 78% superhuman, while minimizing demonstration suboptimality provides 50% superhuman behavior{—}and only 72% even after selective data cleaning.

We introduce a Deep Stochastic IOC RNN Encoder-decoder framework, DESIRE, for the task of future predictions of multiple interacting agents in dynamic scenes. DESIRE effectively predicts future locations of objects in multiple scenes by 1) accounting for the multi-modal nature of the future prediction (i.e., given the same context, future may vary), 2) foreseeing the potential future outcomes and make a strategic prediction based on that, and 3) reasoning not only from the past motion history, but also from the scene context as well as the interactions among the agents. DESIRE achieves these in a single end-to-end trainable neural network model, while being computationally efficient. The model first obtains a diverse set of hypothetical future prediction samples employing a conditional variational auto-encoder, which are ranked and refined by the following RNN scoring-regression module. Samples are scored by accounting for accumulated future rewards, which enables better long-term strategic decisions similar to IOC frameworks. An RNN scene context fusion module jointly captures past motion histories, the semantic scene context and interactions among multiple agents. A feedback mechanism iterates over the ranking and refinement to further boost the prediction accuracy. We evaluate our model on two publicly available datasets: KITTI and Stanford Drone Dataset. Our experiments show that the proposed model significantly improves the prediction accuracy compared to other baseline methods.

Data association problems are an important component of many computer vision applications, with multi-object tracking being one of the most prominent examples. A typical approach to data association involves finding a graph matching or network flow that minimizes a sum of pairwise association costs, which are often either hand-crafted or learned as linear functions of fixed features. In this work, we demonstrate that it is possible to learn features for network-flow-based data association via backpropagation, by expressing the optimum of a smoothed network flow problem as a differentiable function of the pairwise association costs. We apply this approach to multi-object tracking with a network flow formulation. Our experiments demonstrate that we are able to successfully learn all cost functions for the association problem in an end-to-end fashion, which outperform hand-crafted costs in all settings. The integration and combination of various sources of inputs becomes easy and the cost functions can be learned entirely from data, alleviating tedious hand-designing of costs.

Large-scale training for semantic segmentation is challenging due to the expense of obtaining training data for this task relative to other vision tasks. We propose a novel training approach to address this difficulty. Given cheaply-obtained sparse image labelings, we propagate the sparse labels to produce guessed dense labelings. A standard CNN-based segmentation network is trained to mimic these labelings. The label-propagation process is defined via random-walk hitting probabilities, which leads to a differentiable parameterization with uncertainty estimates that are incorporated into our loss. We show that by learning the label-propagator jointly with the segmentation predictor, we are able to effectively learn semantic edges given no direct edge supervision. Experiments also show that training a segmentation network in this way outperforms the naive approach.

We propose a method for generating interpretable descriptions of inputs that cause faults in high-dimensional software interfaces. Our method models the set of fault-triggering inputs as a Cartesian product and identifies this set by actively querying the system under test. The active sampling scheme is very efficient in the common case that few fields in the interface are relevant to causing the fault. This scheme also solves the problem of efficiently finding sufficient examples to model rare faults, which is problematic for other learning-based methods. Compared to other techniques, ours requires no parameter turning or post-processing in order to produce useful results. We analyze the method qualitatively, theoretically, and empirically. An experimental evaluation demonstrates superior performance and reliability compared to a basic decision tree approach. We also briefly discuss how the method has assisted in debugging a commercial autonomous ground vehicle system.

We present a framework based on graph search for navigation in the plane with a variety of topological constraints. The method is based on modifying a standard graph-based navigation approach to keep an additional state variable that encodes topological information about the path. The topological information is represented by a sequence of virtual sensor beam crossings. By considering classes of beam crossing sequences to be equivalent under certain equivalence relations, we obtain a general method for planning with topological constraints that subsumes existing approaches while admitting more favorable representational characteristics. We provide experimental results that validate the approach and show how the planner can be used to find loop paths for autonomous surveillance problems, simultaneously satisfying minimum-cost objectives and in dynamic environments. As an additional application, we demonstrate the use of our planner on the PR2 robot for automated building of 3D object models.

Recent work has produced methods to solve the winding-constrained optimal feedback navigation problem. Given the start and the goal positions and the winding constraints, the solution to this problem is a feedback vector field such that, when integrated from the start, the trajectory is the shortest path connecting the start and the goal which satisfies given constraints. Such constraints intuitively restrict the direction and the number of times the path winds around given planar regions. We formulate a continuous version of this problem that contrasts with the discrete treatments previously presented. This leads to a geometrical characterization of the problem for which simplicial complex approximation is particularly useful. Thus, it yields theoretical insight as well as a practical algorithm for approximating the continuous problem using an efficient and high-accuracy heuristic-driven front propagation method on simplicial meshes. Experimental results are given evaluating the solution quality and efficiency of the method versus methods based on the discrete formulation and without using heuristics.

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.

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 in- terpretation 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.

We present a novel learning-based method for generating optimal motion plans for high-dimensional motion planning problems. In order to cope with the curse of dimensional- ity, our method proceeds in a fashion similar to block co- ordinate descent in finite-dimensional optimization: at each iteration, the motion is optimized over a lower dimensional subspace while leaving the path fixed along the other dimen- sions. Naive implementations of such an idea can produce vastly suboptimal results. In this work, we show how a prof- itable set of directions in which to perform this dimensional descent procedure can be learned efficiently. We provide suf- ficient conditions for global optimality of dimensional de- scent in this learned basis, based upon the low-dimensional structure of the planning cost function. We also show how this dimensional descent procedure can easily be used for problems that do not exhibit such structure with monotonic convergence. We illustrate the application of our method to high dimensional shape planning and arm trajectory planning problems.

We demonstrate how to find high-quality motion plans for high-dimensional holonomic systems efficiently using dynamic programming in a learned subspace of vastly reduced dimension. Our approach (SLASHDP) learns the low dimensional cost structure of an optimal control problem via an efficient spectral method. This structure results in a symmetric value function that serves as a an efficiently-computable surrogate for the true value function. High-quality feedback motion plans can then be obtained from the symmetric value function. Experimental results show that SLASHDP yields higher-quality plans than can be obtained by post-processing plans generated by a sampling-based motion planner, and with less computational effort for very high-dimensional problems. We demonstrate high-quality dynamic programming plans for an arm planning problem of up to 144 dimensions without using any domain-specific knowledge aside from that learned automatically by SLASHDP. Positive results are also shown for a high-dimensional deformable robot planning problem.

We present an method for generating high-quality plans for a robot arm with many degrees of freedom based on Learning Dimensional Descent (LDD), a recently-developed algorithm for planning in high-dimensional spaces based on machine learning and optimization techniques. Unlike other approaches used to solve this problem, our method optimizes a well-defined objective and can be shown to generate optimal plans, in theory and practice, for a well-defined class of problems—those that possess low-dimensional cost structure. For the common case where such structure is only approximately present, LDD constitutes a powerful iterative optimization technique that makes non-homotopic path adjustments in each iteration, while still providing a guarantee of convergence to a local minimum of the objective. Experiments with a 7-DOF robot arm show that the method is able to find solutions in cluttered environments that are of a much higher quality than can be obtained with sampling-based planners and smoothing.

We present a method for real-time simultaneous object recognition and segmentation based on cascaded discriminative Markov random fields. A Markov random field models coupling between the labels of adjacent image regions. The MRF affinities are learned as linear functions of image features in a structured max-margin framework that admits a solution via convex optimization. In contrast to other known MRF/CRF-based approaches, our method classifies in real-time and has computational complexity that scales only logarithmically in the number of object classes. We accomplish this by applying a cascade of binary MRF-classifiers in a way similar to error-correcting output coding for general multiclass learning problems. Inference in this model is exact and can be performed very efficiently using graph cuts. Experimental results are shown that demonstrate a marked improvement in classification accuracy over purely local methods.

We consider the problem of finding sufficiently simple models of high-dimensional physical systems that are consistent with observed trajectories, and using these models to synthesize new trajectories. Our approach models physical trajectories as least-time trajectories realized by free particles moving along the geodesics of a curved manifold, reminiscent of the way light rays obey Fermat's principle of least time. Finding these trajectories, unfortunately, requires finding a minimum-cost path in a high-dimensional space, which is generally a computationally intractable problem. In this work we show that this high-dimensional planning problem can often be solved nearly optimally in practice via deterministic search, as long as we can find a certain low-dimensional structure in the Lagrangian that describes our observed trajectories. This low-dimensional structure additionally makes it feasible to learn an estimate of a Lagrangian that is consistent with the observed trajectories, thus allowing us to present a complete approach for learning from and predicting high-dimensional physical motion sequences. We finally show experimental results applying our method to human motion and robotic walking gaits. In doing so, we furthermore demonstrate efficient path planning in a 990-dimensional space.

We present a search-based planning approach for controlling a quadrupedal robot over rough terrain. Given a start and goal position, we consider the problem of generating a complete joint trajectory that will result in the legged robot successfully moving from the start to the goal. We decompose the problem into two main phases: an initial global planning phase, which results in a footstep trajectory; and an execution phase, which dynamically generates a joint trajectory to best execute the footstep trajectory. We show how R* search can be employed to generate high-quality global plans in the high-dimensional space of footstep trajectories. Results show that the global plans coupled with the joint controller result in a system robust enough to deal with a variety of terrains.

The authors present a novel approach to the task of autonomous terrain classification based on structured prediction. We consider the problem of learning a classifier that will accurately segment an image into "obstacle" and "ground" patches based on supervised input. Previous approaches to this problem have focused mostly on local appearance; typically, a classifier is trained and evaluated on a pixel-by-pixel basis, making an implicit assumption of independence in local pixel neighborhoods. We relax this assumption by modeling correlations between pixels in the submodular MRF framework. We show how both the learning and inference tasks can be simply and efficiently implemented-exact inference via an efficient max flow computation; and learning, via an averaged-subgradient method. Unlike most comparable MRF-based approaches, our method is suitable for implementation on a robot in real-time. Experimental results are shown that demonstrate a marked increase in classification accuracy over standard methods in addition to real-time performance.

The authors present an innovative method for the efficient joint estimation of attitude and position in six degrees of freedom via sensors such as GPS, inertial measurement units, and odometry. Traditional methods for attitude estimation via Kalman filtering are beset by many conceptual problems relating to the representation of orientations in linear spaces, leading to difficulties in implementation and the interpretation of uncertainty estimates, among other issues. These problems are compounded when it is necessary to jointly estimate position and attitude. We demonstrate how Rao-Blackwellized particle filtering provides a framework for approaching this estimation problem that is both conceptually appealing and practical. Results are shown that demonstrate the filter's robustness to sensor outages and its ability to perform well even in situations with noisy sensors and high initial uncertainty in all state dimensions; these situations are precisely those in which traditional Kalman filtering approaches are most likely to experience problems

We describe a method for estimating the relative poses of a team of mobile robots using only acoustic sensing. The relative distances and bearing angles of the robots are estimated using the time of arrival of audible sound signals on stereo microphones. The robots emit specially designed sound waveforms that simultaneously enable robot identification and time of arrival estimation. These acoustic observations are then combined with odometry to update a belief state describing the positions and heading angles of all the robots. To efficiently resolve the ambiguity in the heading angle of the observing robot as well as the back-front ambiguity of the observed robot, we employ a Rao-Blackwellised particle filter (RBPF) where the distribution over heading angles is represented by a discrete set of particles, and the uncertainty in the translational positions conditioned on each of these particles is described by a Gaussian. This approach combines the representational accuracy of conventional particle filters with the efficiency of Kalman filter updates in modeling the pose distribution over a number of robots. We demonstrate how the RBPF can quickly resolve uncertainties in the binaural acoustic measurements and yield a globally consistent pose estimate. Simulations as well as an experimental implementation on robots with generic sound hardware illustrate the accuracy and the convergence of the resulting pose estimates.