Spatial distribution of two-agent clusters for efficient navigation

Coordinated navigation by two cooperating sensor-equipped agents in a partially known static environment is investigated. Each agent observes a local part of the otherwise unknown environment and shares the gathered data with the other agents. In general, dynamic programming techniques suitably model the navigation problem, but are computationally hard to solve. We propose a combined dynamic and linear programming framework to circumvent the curse of dimensionality and establish in the process a firm upper bound on the spatial separation of a two-agent cluster navigating on a structured arbitrarily large graph.