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

Mohan Krishna Nutalapati, Amrit Singh Bedi, Ketan Rajawat, Marceau Coupechoux

Abstract

This paper 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 the online gradient ascent algorithm for such problems. Moreover, the gradient feedback is noisy, allowing the proposed algorithm to be used for a range of practical applications where it is difficult to acquire the true gradient. In contrast to most available literature, we present the offline sublinear regret of the proposed algorithm up to the path length variations of the optimal offline 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: device-to-device (D2D) communications and energy-efficient trajectories for unmanned surface vehicles (USV) in ocean environments.

Introduction

Traditional trajectory planning for autonomous systems, such as drones or underwater robots, typically relies on offline models. These methods involve planning a complete path based on forecasts, which often fails when environments change unpredictably—such as shifting ocean currents or moving targets. Re-calculating paths in real-time is computationally expensive and sensitive to forecast inaccuracies.

This research addresses the challenge of online trajectory optimization. In this setting, an agent lacks a complete future view, possessing only its current state and receiving local, potentially noisy feedback. The objective is to navigate from a start to a destination while maximizing a utility function (e.g., data transfer rate or energy efficiency) under strict physical constraints like maximum velocity.

Methodology: Inexact Online Gradient Ascent (IOGA)

The core contribution is the Inexact Online Gradient Ascent (IOGA) algorithm. It treats trajectory planning as a time-varying constrained convex optimization problem with several key features:

  • Online Learning: The agent takes incremental steps in the direction of the gradient (the direction of maximum utility improvement) at each time step rather than planning the entire path upfront.
  • Inexact Feedback: The algorithm is robust to "noisy" gradients, which is essential for real-world applications where sensors like GPS or flow meters provide imperfect data.
  • Feasibility Constraints: A variable step-size rule ensures that each new waypoint satisfies physical limits, such as the vehicle's maximum speed.
  • Theoretical Guarantees: The authors mathematically prove that the algorithm's "regret"—the performance gap between the online path and a perfect offline path—grows sublinearly ($O(\sqrt{T})$), assuming the environment's rate of change is bounded.

Experimental Setup

The IOGA algorithm was evaluated using two distinct scenarios:

  1. Synthetic D2D Scenarios: Simulated pedestrians in an urban grid attempting to maintain high-speed Device-to-Device (D2D) links while moving toward separate destinations.
  2. Real-World Ocean Data: Historical current data from the Regional Ocean Modeling System (ROMS) for the Southern California Bight was used to test the energy efficiency of Unmanned Surface Vehicles (USVs).
Application scenarios for trajectory optimization: (a) D2D communication and (b) USV ocean navigation.

Key Insights and Results

The simulations revealed several critical behaviors and performance metrics:

  • The "Knee Region": In D2D tests, the optimal online trajectory exhibits a "knee" behavior. Users initially converge toward each other to maximize data exchange before abruptly diverging to reach their destinations on time.
  • Directional Utility: For ocean navigation, a utility function accounting for the current's angle relative to the goal proved superior to simple time-based strategies.
  • Robustness and Efficiency: IOGA remained stable even with 10% noise in ocean current measurements. Computationally, it runs in $O(N)$ time, making it more suitable for low-power embedded hardware than sampling-based methods like STOMP or EESTO.
Visualization of the 'knee region' behavior in D2D user trajectories.
  • Energy Savings: In USV navigation, IOGA saved significantly more energy than benchmarks. With a 10% allowed delay, IOGA saved 123.08 kJ, compared to 112.01 kJ for EESTO and 107.10 kJ for STOMP.
  • Consistency: Unlike stochastic sampling methods, IOGA is deterministic, providing consistent optimal paths for identical inputs.

Conclusion and Future Work

While IOGA provides strong theoretical and practical results, it currently relies on environment "convexity," which limits its application in areas with complex non-convex obstacles like islands. Future work aims to extend this framework to multi-agent coordination and incorporate non-convex obstacle avoidance into the online optimization process.

Reference: Nutalapati, M. K., Bedi, A. S., Rajawat, K., & Coupechoux, M. (2020). Online Trajectory Optimization Using Inexact Gradient Feedback for Time-Varying Environments. arXiv:2001.00685

Summary updated

Abstract

This paper considers the problem of online trajectory design under\ntime-varying environments. We formulate the general trajectory optimization\nproblem within the framework of time-varying constrained convex optimization\nand proposed a novel version of the online gradient ascent algorithm for such\nproblems. Moreover, the gradient feedback is noisy and allows us to use the\nproposed algorithm for a range of practical applications where it is difficult\nto acquire the true gradient. In contrast to the most available literature, we\npresent the offline sublinear regret of the proposed algorithm up to the path\nlength variations of the optimal offline solution, the cumulative gradient, and\nthe error in the gradient variations. Furthermore, we establish a lower bound\non the offline dynamic regret, which defines the optimality of any trajectory.\n To show the efficacy of the proposed algorithm, we consider two practical\nproblems of interest. First, we consider a device to device (D2D)\ncommunications setting, and the goal is to design a user trajectory while\nmaximizing its connectivity to the internet. The second problem is associated\nwith the online planning of energy-efficient trajectories for unmanned surface\nvehicles (USV) under strong disturbances in ocean environments with both static\nand dynamic goal locations. The detailed simulation results demonstrate the\nsignificance of the proposed algorithm on synthetic and real data sets. Video\non the real-world datasets can be found at\n{https://www.youtube.com/watch?v=FcRqqWtpf\\_0}\n
BibTeX
@article{nutalapati2020online,
  author = {Mohan Krishna Nutalapati and Amrit Singh Bedi and Ketan Rajawat and Marceau Coupechoux},
  title = {{Online Trajectory Optimization Using Inexact Gradient Feedback for\textbackslash\{\}n Time-Varying Environments}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  doi = {10.1109/tsp.2020.3015276},
}
Figure