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) disas- ter rescue, sensor networks and security pa- trolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decen- tralized 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 availabil- ity 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 rep- resent 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 demon- strate 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) disas- ter rescue, sensor networks and security pa- trolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decen- tralized 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 availabil- ity 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 rep- resent 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 demon- strate 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) disas- ter rescue, sensor networks and security pa- trolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decen- tralized 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 availabil- ity 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 rep- resent 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 demon- strate 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