Decentralized Planning for Non-Dedicated Agent Teams with Submodular Rewards in Uncertain Environments

Abstract

Planning under uncertainty is seen in many domains such as disaster rescue, sensor networks, security patrolling, etc. where individual agents work in a decentralized, yet co-operative manner and are tied together through a global reward function. Existing research has made significant progress by providing a rich framework to represent co-operative and decentralized planning under uncertainty. This class of problems also deal with non-dedication of team members where agents may leave due to high priority tasks(e.g., emergency, accidents etc.) or due to damange to the agent. However, there is very limited literature to handle problems of non-dedication in agent teams in decentralized settings. In this paper, we provide a general model to represent such problems and solution approaches for handling cooperative and decentralized planning under uncertainty for non-dedicated agent teams. We specifically provide two greedy approaches (an offline one and an offline-online one) that are able to deal with agents leaving the team in an effective and efficient way by exploiting the submodularity property. We provide a detailed evaluation of our approaches on existing benchmark problems and demonstrate that our approaches are able to obtain more than 90% of optimal solution quality on benchmark problems from the literature.