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:
- Synthetic D2D Scenarios: Simulated pedestrians in an urban grid attempting to maintain high-speed Device-to-Device (D2D) links while moving toward separate destinations.
- 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).
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.
- 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