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

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

TL;DR

This paper introduces a novel Inexact Online Gradient Ascent (IOGA) algorithm for designing optimal trajectories in real-time, even when the environment is changing unpredictably and sensor data is noisy. By treating trajectory planning as a time-varying constrained convex optimization problem, the authors prove that their method achieves "sublinear regret"—meaning that over time, the online agent performs nearly as well as an omniscient observer who knew the entire future in advance.

What Problem Does This Paper Address?

Traditional trajectory planning for autonomous systems (like drones or underwater robots) usually relies on "offline" models: you take a forecast, plan the whole path, and hope the forecast was right. If the environment changes—like a sudden shift in ocean currents or a moving target—you have to re-calculate everything, which is computationally expensive and often fails if the forecast is inaccurate.

The authors tackle the challenge of online trajectory optimization. In this setting, the agent doesn't have a crystal ball; it only knows its current state and receives local, potentially noisy feedback about its surroundings. The goal is to move from point A to point B while maximizing a "utility" (like data transfer rate or energy efficiency) under strict physical constraints (like maximum speed).

Methods

The core of the paper is the Inexact Online Gradient Ascent (IOGA) algorithm. Here’s how it works:

  • Online Learning: Instead of planning the whole path at once, the agent takes a small step in the direction of the "gradient" (the direction that most improves its utility) at every time step.
  • Inexact Feedback: The algorithm is designed to handle "noisy" gradients. This is crucial for real-world applications where sensors (like GPS or flow meters) aren't perfect.
  • Feasibility Constraints: A key innovation is a variable step-size rule. It ensures that the agent’s next "waypoint" always satisfies physical limits, such as not exceeding the vehicle's maximum speed.
  • Theoretical Guarantees: The authors provide a rigorous mathematical proof that the algorithm's "regret" (the gap between the online path and the perfect offline path) grows slower than time itself ($O(\sqrt{T})$), provided the environment doesn't change too violently.

Datasets

The authors evaluated their algorithm using two distinct setups:

  1. Synthetic D2D Scenarios: Simulated pedestrians moving through an urban environment, trying to stay close to each other to maintain high-speed Device-to-Device (D2D) data links while heading toward separate destinations.
  2. Real-World Ocean Data: They used historical ocean current data from the Regional Ocean Modeling System (ROMS), specifically focusing on the Southern California Bight. This dataset provides complex, time-varying current velocities used to test the energy efficiency of Unmanned Surface Vehicles (USVs).

Key Insights and Ideas

  • The "Knee Region": In the D2D communication tests, the optimal online trajectory naturally discovers a "knee" behavior—users initially move toward each other to maximize data exchange and then abruptly split to reach their respective destinations just in time.
  • Direction Matters: For ocean navigation, the authors found that a "direction-dependent" utility function (which accounts for the angle of the current relative to the goal) is far superior to a simple time-based strategy.
  • Robustness to Noise: The IOGA algorithm proved remarkably stable. Even when 10% noise was added to the ocean current measurements, the resulting trajectories remained efficient and reached the goal.
  • Computational Efficiency: Unlike sampling-based methods (like STOMP or EESTO) that require running hundreds of simulations to find a path, IOGA is deterministic and runs in $O(N)$ time, making it much better suited for low-power embedded hardware.

Key Results

  • Energy Savings: In the USV ocean navigation task, the proposed IOGA method saved significantly more energy than state-of-the-art algorithms. For a 10% allowed delay, IOGA saved 123.08 kJ, outperforming EESTO (112.01 kJ) and STOMP (107.10 kJ).
  • Zero Variability: Unlike sampling-based methods which produce different paths every time they run, IOGA is consistent, providing the same optimal path for the same inputs every time.
  • Sublinear Regret: The mathematical analysis confirmed that the "cost of not knowing the future" diminishes over time, proving the algorithm is theoretically "optimal" in a dynamic sense.

Limitations and Future Work

  • Convexity Constraints: The current mathematical bounds rely on the environment being "convex." This means the algorithm struggles with complex obstacles like islands or buildings that create "non-convex" holes in the map.
  • Strong Concavity: The proofs require the utility function to be "strongly concave," which might not fit every possible application.
  • Future Directions: The authors suggest extending the framework to handle multi-agent coordination (e.g., a swarm of robots) and incorporating non-convex obstacle avoidance into the online optimization framework.

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 Time-Varying Environments}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  doi = {10.1109/tsp.2020.3015276},
}

Loading related content...

Figure