Exploration under Sparsity Constraints

Abstract

This paper addresses the problem of designing an efficient exploration strategy for multiple mobile agents. As an exploration strategy, an intelligent waypoint generation is considered, where the trajectory of the agent is governed by the properties of the explored phenomenon. Here it is assumed that the explored field is sparse in it’s spatial distribution; consequently, it is assumed that a certain agent’s movement trajectory might favor a sparse solution, as contrasted to simple sampling strategies. Specifically, these trajectories lead to an emergence of a structured sensing matrix consisting of shifted sensor impulse responses. Nevertheless some properties of this matrix, such as low mutual coherence, are essential for a successful sparse reconstruction of the phenomenon. Thus, the agents are directed to move so as to favor the desired properties of the sensing matrix, an approach termed sparse exploration. Unfortunately, numerical techniques for optimization of the sensing matrix are intractable. Therefore this paper proposes a number of heuristics, which numerically optimize the measurement locations of the agents so as to favor a sparse solution. Synthetic experiments are performed to demonstrate the effectiveness of the proposed heuristics as compared to simple random walk or regular movement patterns.