Information Markets for Multi-Robot Navigation Under Uncertainty

Abstract

We investigate the role of an information market in improving navigation outcomes for risk-averse multi-agent systems with incomplete state information. Given a partially observed graph representation of an environment map and the deployed agents, we first create a path planning heuristic that characterizes each agent's path preference, given the currently observable occupancy statuses of environment positions, by the expected utility of path traversal. Secondly, we utilize prior work in the field of decision theory to determine the value of receiving information on positions with uncertainty as well as the cost to obtain the information. Lastly, we create a suite of assignment algorithms to best determine how agents can cooperate to collect additional information and facilitate path planning updates. A synthetic dataset of environments, settings, and team compositions is created according to the operation specifications considered in this paper and is used to demonstrate that information exchange yields significant improvements in the global utility outcomes both in expectation and in practice.