High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions

Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g., the value function) in a compressed format, and directly perform dynamic programming computations (e.g., value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in "compressible" problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to ten orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture.

Comments: 32 pages, 20 figures

Similar Publications

We propose an approach based on probabilistic models, in particular POMDPs, to plan optimized search processes of known objects by intelligent eye in hand robotic arms. Searching and reaching for a known object (a pen, a book, or a hammer) in one's office is an operation that humans perform frequently in their daily activities. There is no reason why intelligent robotic arms would not encounter this problem frequently in the various applications in which they are expected to serve. Read More


As part of a complete software stack for autonomous driving, NVIDIA has created a neural-network-based system, known as PilotNet, which outputs steering angles given images of the road ahead. PilotNet is trained using road images paired with the steering angles generated by a human driving a data-collection car. It derives the necessary domain knowledge by observing human drivers. Read More


In this paper we introduce an adaptive cost function for pointcloud registration. The algorithm automatically estimates the sensor noise, which is important for generalization across different sensors and environments. Through experiments on real and synthetic data, we show significant improvements in accuracy and robustness over state-of-the-art solutions. Read More


Path planning for multiple robots is well studied in the AI and robotics communities. For a given discretized environment, robots need to find collision-free paths to a set of specified goal locations. Robots can be fully anonymous, non-anonymous, or organized in groups. Read More


We study the problem of reducing the amount of communication in decentralized target tracking. We focus on the scenario where a team of robots are allowed to move on the boundary of the environment. Their goal is to seek a formation so as to best track a target moving in the interior of the environment. Read More


With introduction of new technologies in the operating room like the da Vinci Surgical System, training surgeons to use them effectively and efficiently is crucial in the delivery of better patient care. Coaching by an expert surgeon is effective in teaching relevant technical skills, but current methods to deliver effective coaching are limited and not scalable. We present a virtual reality simulation-based framework for automated virtual coaching in surgical education. Read More


The threat to safety of aging bridges has been recognized as a critical concern to the general public due to the poor condition of many bridges in the U.S. Currently, the bridge inspection is conducted manually, and it is not efficient to identify bridge condition deterioration in order to facilitate implementation of appropriate maintenance or rehabilitation procedures. Read More


Simulation environments for Unmanned Aerial Vehicles (UAVs) can be very useful for prototyping user interfaces and training personnel that will operate UAVs in the real world. The realistic operation of such simulations will only enhance the value of such training. In this paper, we present the integration of a model-based waypoint navigation controller into the Reno Rescue Simulator for the purposes of providing a more realistic user interface in simulated environments. Read More


This paper considers the problem of autonomous multi-agent cooperative target search in an unknown environment using a decentralized framework under a no-communication scenario. The targets are considered as static targets and the agents are considered to be homogeneous. The no-communication scenario translates as the agents do not exchange either the information about the environment or their actions among themselves. Read More


Visual-Inertial Odometry (VIO) utilizes an Inertial Measurement Unit (IMU) to overcome the limitations of Visual Odometry (VO). However, the VIO for vehicles in large-scale outdoor environments still has some difficulties in estimating forward motion with distant features. To solve these difficulties, we propose a robust VIO method based on the analysis of feature confidence in forward motion estimation using an IMU. Read More