Risk-Aware Conditional Replanning for Globally Constrained Multi-Agent Sequential Decision Making

Collaborating agents typically must share limited resources, such as power or bandwidth. When dealing with global constraints on resource use, agents need to plan their decisions in advance to maximize utility obtained from resources. However, deciding which agent should claim a resource under uncertainty is a hard problem: we prove that optimally planning for a globally constrained, multi-agent Markov decision process is pspace-hard, even when agents' transition and reward dynamics are independent, resource consumption is binary, and only one constraint is active for any decision. To overcome this complexity, relaxations may be used to find high-value policies efficiently. Unfortunately, relaxed policies are not guaranteed to satisfy the constraints in every realizable trajectory, making them unusable in practice. In this paper, we address this weakness by investigating the use of such efficient-but-unsafe algorithms in online replanning. We show that replanning can be used to obtain high-quality safe solutions, by replanning conditionally with a Lagrangian relaxation-based column generation procedure. By replanning only when the risk of constraint violations becomes too high, both the computational cost and the obtained value can be improved over naive replanning, while retaining safety with respect to the constraints.