Decentralized planning for non-dedicated agent teams with submodular rewards in uncertain environments

• Main Authors: AGRAWAL, Pritee, VARAKANTHAM, Pradeep, YEOH, William
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/sis_research/4251; https://ink.library.smu.edu.sg/context/sis_research/article/5254/viewcontent/342.pdf
• Institution: Singapore Management University

Decentralized planning under uncertainty foragent teams is a problem of interest in manydomains including (but not limited to) disaster rescue, sensor networks and security patrolling. Decentralized MDPs, Dec-MDPs havetraditionally been used to represent such decentralized planning under uncertainty problems.However, in many domains, agents may notbe dedicated to the team for the entire timehorizon. For instance, due to limited availability of resources, it is quite common for policepersonnel leaving patrolling teams to attend toaccidents. Such non-dedication can arise dueto the emergence of higher priority tasks ordamage to existing agents. However, there isvery limited literature dealing with handlingof non-dedication in decentralized settings. Tothat end, we provide a general model to represent problems dealing with cooperative anddecentralized planning for non-dedicated agentteams. We also provide two greedy approaches(an offline one and an offline-online one) thatare able to deal with agents leaving the teamin an effective and efficient way by exploitingthe submodularity property. Finally, we demonstrate that our approaches are able to obtainmore than 90% of optimal solution quality onbenchmark problems from the literature.