Online Trajectory Optimization Using Inexact Gradient Feedback for Time-Varying Environments

This article considers the problem of online trajectory design under time-varying environments. We formulate the general trajectory optimization problem within the framework of time-varying constrained convex optimization and propose a novel version of online gradient ascent algorithm (OGA) for such problems. Respecting the online nature, we carefully select the step size of OGA at each iteration so that the iterates stay feasible. Importantly, the proposed algorithm allows noisy gradients, expanding the range of practical applicability. In contrast to the most available literature, we present the offline sublinear regret of OGA up to the path length variations of the offline optimal solution, the cumulative gradient, and the error in the gradient variations. Furthermore, we establish a lower-bound on the offline dynamic regret, which defines the optimality of any trajectory. To show the efficacy of the proposed algorithm, we consider two practical problems of interest. First, a device to device (D2D) communications setting, where the goal is to design a user trajectory while maximizing its connectivity to the internet. Second, planning energy-efficient trajectories for unmanned surface vehicles (USV) under strong disturbances in ocean environments. Different from the state-of-the-art trajectory planning algorithms that entail planning and re-planning the full trajectory using the forecast data at each time instant, the proposed algorithm is entirely online and relies mostly on the ocean velocity measurements at the vehicle location. The detailed simulation results demonstrate the significance of the proposed algorithm on both synthetic and real data sets. Video result is available at https://tinyurl.com/y3ahmhsf.