Nonsubmodular Visual Attention for Robot Navigation
- 8 October 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 41 (15523098) , 6044-6063
Abstract
This paper presents a task-oriented computational framework to enhance Visual-Inertial Navigation (VIN) in robots, addressing challenges such as limited time and energy resources. The framework strategically selects visual features using a Mean Square Error (MSE)-based, non-submodular objective function and a simplified dynamic anticipation model. To address the NP-hardness of this problem, we introduce four polynomial-time approximation algorithms: a classic greedy method with constant-factor guarantees; a low-rank greedy variant that significantly reduces computational complexity; a randomized greedy sampler that balances efficiency and solution quality; and a linearization-based selector based on a first-order Taylor expansion for near-constant-time execution. We establish rigorous performance bounds by leveraging submodularity ratios, curvature, and element-wise curvature analyses. Extensive experiments on both standardized benchmarks and a custom control-aware platform validate our theoretical results, demonstrating that these methods achieve strong approximation guarantees while enabling real-time deployment.Keywords
All Related Versions
Funding Information
- Office of Naval Research (N00014-21-1-2431)
- National Science Foundation (2121121)
- National Science Foundation (2208182)
- U.S. Department of Homeland Security (22STESE00001-03-02)
- DARPA Artificial Intelligence Quantified
This publication has 41 references indexed in Scilit:
- Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint2024
- A separation theorem for joint sensor and actuator scheduling with guaranteed performance boundsAutomatica, 2020
- Sensor selection for optimal filtering of linear dynamical systems: Complexity and approximation2015
- The Design of Approximation Algorithms2011
- Sliding window filter with application to planetary landingJournal of Field Robotics, 2010
- Convex Analysis2006
- Active search for real-time vision2005
- Convex Optimization2004
- Good features to track1994
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978