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

Pritee Agrawal, Pradeep Varakantham, William Yeoh
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:957-966, 2018.

Abstract

Decentralized planning under uncertainty for agent teams is a problem of interest in many domains including (but not limited to) disaster rescue, sensor networks and security patrolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decentralized planning under uncertainty problems. However, in many domains, agents may not be dedicated to the team for the entire time horizon. For instance, due to limited availability of resources, it is quite common for police personnel leaving patrolling teams to attend to accidents. Such non-dedication can arise due to the emergence of higher priority tasks or damage to existing agents. However, there is very limited literature dealing with handling of non-dedication in decentralized settings. To that end, we provide a general model to represent problems dealing with cooperative and decentralized planning for non-dedicated agent teams. We also 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. Finally, we demonstrate that our approaches are able to obtain more than 90% of optimal solution quality on benchmark problems from the literature.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-agrawal18a, title = {Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments}, author = {Agrawal, Pritee and Varakantham, Pradeep and Yeoh, William}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {957--966}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/agrawal18a/agrawal18a.pdf}, url = {https://proceedings.mlr.press/r16/agrawal18a.html}, abstract = {Decentralized planning under uncertainty for agent teams is a problem of interest in many domains including (but not limited to) disaster rescue, sensor networks and security patrolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decentralized planning under uncertainty problems. However, in many domains, agents may not be dedicated to the team for the entire time horizon. For instance, due to limited availability of resources, it is quite common for police personnel leaving patrolling teams to attend to accidents. Such non-dedication can arise due to the emergence of higher priority tasks or damage to existing agents. However, there is very limited literature dealing with handling of non-dedication in decentralized settings. To that end, we provide a general model to represent problems dealing with cooperative and decentralized planning for non-dedicated agent teams. We also 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. Finally, we demonstrate that our approaches are able to obtain more than 90% of optimal solution quality on benchmark problems from the literature.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments %A Pritee Agrawal %A Pradeep Varakantham %A William Yeoh %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-agrawal18a %I PMLR %P 957--966 %U https://proceedings.mlr.press/r16/agrawal18a.html %V R16 %X Decentralized planning under uncertainty for agent teams is a problem of interest in many domains including (but not limited to) disaster rescue, sensor networks and security patrolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decentralized planning under uncertainty problems. However, in many domains, agents may not be dedicated to the team for the entire time horizon. For instance, due to limited availability of resources, it is quite common for police personnel leaving patrolling teams to attend to accidents. Such non-dedication can arise due to the emergence of higher priority tasks or damage to existing agents. However, there is very limited literature dealing with handling of non-dedication in decentralized settings. To that end, we provide a general model to represent problems dealing with cooperative and decentralized planning for non-dedicated agent teams. We also 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. Finally, we demonstrate that our approaches are able to obtain more than 90% of optimal solution quality on benchmark problems from the literature. %Z Reissued by PMLR on 04 October 2026.
APA
Agrawal, P., Varakantham, P. & Yeoh, W.. (2018). Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:957-966 Available from https://proceedings.mlr.press/r16/agrawal18a.html. Reissued by PMLR on 04 October 2026.

Related Material