Resource constraints frequently complicate multi-agent planning problems. Existing algorithms for resource-constrained, multi-agent planning problems rely on the assumption that the constraints are deterministic. However, frequently resource constraints are themselves subject to uncertainty from external influences. Uncertainty about constraints is especially challenging when agents must execute in an environment where communication is unreliable, making on-line coordination difficult. In those cases, it is a significant challenge to find coordinated allocations at plan time depending on availability at run time. To address these limitations, we propose to extend algorithms for constrained multi-agent planning problems to handle stochastic resource constraints. We show how to factorize resource limit uncertainty and use this to develop novel algorithms to plan policies for stochastic constraints. We evaluate the algorithms on a search-and-rescue problem and on a power-constrained planning domain where the resource constraints are decided by nature. We show that plans taking into account all potential realizations of the constraint obtain significantly better utility than planning for the expectation, while causing fewer constraint violations.
|Title of host publication||Proceedings of the 32th AAAI Conference on Artificial Intelligence|
|Editors||S. McIlraith , K. Weinberger|
|Publisher||Association for the Advancement of Artificial Intelligence (AAAI)|
|Number of pages||8|
|Publication status||Published - Jan 2018|
|Event||The 32nd AAAI Conference on Artificial Intelligence (AAAI-18): The Thirtieth Innovative Applications of Artificial Intelligence Conference, The Eighth AAAI Symposium on Educational Advances in Artificial Intelligence - New Orleans, United States|
Duration: 2 Feb 2018 → 7 Feb 2018
Conference number: 32nd
|Conference||The 32nd AAAI Conference on Artificial Intelligence (AAAI-18)|
|Period||2/02/18 → 7/02/18|
Bibliographical noteGreen Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.