This paper deals with multi-agent scenarios where individual agents must coordinate their plans in order to efficiently complete a set of tasks. Our strategy formulates the task planning problem as a potential game and uses decentralized stochastic sampling policies to reach a consensus on which sequences of actions agents should take. We execute this over a receding finite time horizon and take special care to discourage agents from breaking promises in the near future, which may cause other agents to unsuccessfully attempt a joint action. At the same time, we allow agents to change plans in the distant future, as this gives time for other agents to adapt their plans, allowing the team to escape locally optimal solutions. To do this we introduce two sampling schemes for new actions: a geometric based scheme, where the probability of sampling a new action increases geometrically in time, and an inference-based sampling scheme, where a convolutional neural network provides recommendations for joint actions. We test the proposed schemes in a cooperative orienteering environment to illustrate their performance and validate the intuition behind their design. (C) 2021 The Author(s). Published by Elsevier B.V.
