Data Acquisition in Dynamic Environments: A Submodular Perspective

While the recent advances in Artificial Intelligence have mainly relied on the availability of a wealth of centralized data, a fundamental challenge in many DoD-relevant applications is to acquire high-quality data at minimal cost. These applications range from robotic sensing and autonomous planning to experimental design and active learning; furthermore, such applications often take place in unknown or even adversarial environments, in which data is highly limited and precious. More specifically, each observation may significantly impact our ability to learn and operate in unknown and dynamic environments. Moreover, dealing with complex real-world environments requires a paradigm shift from the existing static, model aware data acquisition approaches to methods that learn adaptively and are robust against imperfect, stochastic and evolving knowledge. Whether we select a bunch of sensory observations, or choose a sequence of actions, or collaborate with a number of agents, the data-acquisition task often involves inherent combinatorial structures and is fundamentally discrete. Even though discrete optimization problems are generally hard, prior work has shown that many data-acquisition problems admit a key structural property called submodularity.