Abstract
This paper introduces Inexact Online Gradient Descent (IOGD), a robust framework for tracking moving targets with multiple robots in environments where sensor data is noisy or "inexact." By providing new theoretical guarantees (dynamic regret bounds) for non-strongly convex functions, the authors bridge the gap between idealized optimization theory and the practical constraints of field robotics. The proposed method achieves significant computational speedups while maintaining tracking accuracy comparable to state-of-the-art solvers.
Introduction
In multi-agent systems—such as drone swarms tracking intruders—the optimal configuration for agents changes continuously as targets move. This is traditionally modeled as a time-varying optimization problem. However, real-world deployment is often hindered by two factors: the "strong convexity trap," where standard guarantees require strict mathematical properties rarely found in practice, and the presence of noisy or adversarial information from sensors and communications.
This work addresses these challenges by proving that high-performance tracking can be achieved using a computationally efficient first-order method, even without strong convexity and in the presence of noisy data.
Methodology
The authors propose the Inexact Online Gradient Descent (IOGD) algorithm. Rather than solving a complex optimization problem to high precision at every time step, agents take a single update step in the direction of a potentially noisy gradient.
Key Innovations
- Quadratic Growth (QG) Condition: The analysis utilizes the QG property, a more relaxed and realistic condition than standard strong convexity, making it applicable to a wider range of robotics problems like least-squares tracking.
- Dynamic Regret Analysis: Performance is measured using dynamic regret, which compares the agent's path to the sequence of optimal actions over time, rather than a single fixed best action.
- Error Modeling: The framework explicitly accounts for cumulative gradient error ($E_K$), allowing for both stochastic (white noise) and adversarial error models.
Theoretical Results
The paper establishes that the "difficulty" of tracking is mathematically tied to the path length ($W_K$) of the target. If the target moves in a relatively smooth trajectory, the algorithm maintains sublinear regret. The theoretical contributions are summarized in the following table, which compares IOGD against existing literature.
As shown in the table, this work provides dynamic regret bounds of $O(1 + E_K + W_K)$ for functions with quadratic growth, even when gradients are inexact—a scenario not covered by previous benchmarks.
Experimental Evaluation
The framework was evaluated using two distinct approaches:
- Synthetic Multi-Target Tracking: Simulations involving up to 50 agents tracking 10 targets in a 2D plane. This tested the algorithm's ability to handle complex behaviors, such as target splitting.
- MovieLens 10M Dataset: To demonstrate flexibility beyond robotics, the algorithm was applied to an online movie recommendation task (matrix completion), tracking changing user preferences over time.
Key Findings
- Massive Speedup: In head-to-head simulations, the IOGD-based tracker required only 49 ms per iteration, compared to 974 ms for a state-of-the-art interior-point method. This 20x speedup is critical for real-time tracking of high-speed targets on limited onboard hardware.
- Performance Parity: Despite its simplicity, the tracking accuracy of IOGD was found to be on par with much more computationally expensive optimization approaches.
- Robustness: Unlike high-precision solvers that may become infeasible if parameters are not perfectly tuned, IOGD is robust and provides consistent "best effort" updates in challenging scenarios.
Conclusion
IOGD offers a computationally light and theoretically sound approach to multi-agent tracking. While current proofs rely on bounded target velocity and compact domains for general convex functions, the framework's ability to handle inexact gradients and non-strongly convex functions represents a significant advancement. Future work will explore fully decentralized settings and non-convex objective functions.
Summary updated