This paper describes a data-driven framework for approximate global optimization in which precomputed solutions to a sample of problems are retrieved and adapted during online use to solve novel problems. This approach has promise for real-time applications in robotics, since it can produce near-globally optimal solutions orders of magnitude faster than standard methods. This paper establishes theoretical conditions on how many and where samples are needed over the space of problems to achieve a given approximation quality. The framework is applied to solve globally optimal collision-free inverse kinematics (IK) problems, wherein large solution databases are used to produce near-optimal solutions in sub-millisecond time on a standard PC.
The instance-based framework used in this paper is arguably most closely related to the work of Jetchev and Toussaint @cite_14 , which select past plans to initialize trajectory optimization. Similarly, this paper uses experience to initialize optimization, but considers the more general context of nonlinear optimization problems, and focuses on the conditions under which such databases provide theoretical guarantees on solution quality. Furthermore, the prior work uses locally optimal examples in the database, whereas our work uses globally optimal ones.
@cite_14
2079148749
Trajectory planning and optimization is a fundamental problem in articulated robotics. Algorithms used typically for this problem compute optimal trajectories from scratch in a new situation. In effect, extensive data is accumulated containing situations together with the respective optimized trajectories--but this data is in practice hardly exploited. This article describes a novel method to learn from such data and speed up motion generation, a method we denote tajectory pediction. The main idea is to use demonstrated optimal motions to quickly predict appropriate trajectories for novel situations. These can be used to initialize and thereby drastically speed-up subsequent optimization of robotic movements. Our approach has two essential ingredients. First, to generalize from previous situations to new ones we need a situation descriptor--we construct features for such descriptors and use a sparse regularized feature selection approach to improve generalization. Second, the transfer of previously optimized trajectories to a new situation should not be made in joint angle space--we propose a more efficient task space transfer. We present extensive results in simulation to illustrate the benefits of the new method, and demonstrate it also with real robot hardware. Our experiments in diverse tasks show that we can predict good motion trajectories in new situations for which the refinement is much faster than an optimization from scratch.