Non-Submodular Visual Attention for Robot Navigation

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.