Risk-aware conditional replanning for globally constrained multi-agent sequential decision making

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Collaborating agents typically must share limited resources, such as power or bandwidth. When dealing with global constraints on resource use, agents need to plan their decisions in advance to maximize utility obtained from resources. However, deciding which agent should claim a resource under uncertainty is a hard problem: we prove that optimally planning for a globally constrained, multi-agent Markov decision process is PSPACE-hard, even when agents' transition and reward dynamics are independent, resource consumption is binary, and only one constraint is active for any decision.

To overcome this complexity, relaxations may be used to find high-value policies efficiently. Unfortunately, relaxed policies are not guaranteed to satisfy the constraints in every realizable trajectory, making them unusable in practice. In this paper, we address this weakness by investigating the use of such efficient-but-unsafe algorithms in online replanning. We show that replanning can be used to obtain high-quality safe solutions, by replanning conditionally with a Lagrangian relaxation-based column generation procedure. By replanning only when the risk of constraint violations becomes too high, both the computational cost and the obtained value can be improved over naive replanning, while retaining safety with respect to the constraints.
Original languageEnglish
Title of host publicationProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems
EditorsBo An, Neil Yorke-Smith
Place of PublicationRichland SC USA
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages303-311
Number of pages9
ISBN (Electronic)9781450375184
Publication statusPublished - May 2020
EventInternational Conference on Autonomous Agents and MultiAgent Systems 2020 - Auckland , New Zealand
Duration: 9 May 202013 Jun 2020
Conference number: 19th
https://dl-acm-org.ezproxy.lib.monash.edu.au/doi/proceedings/10.5555/3398761 (Proceedings)
https://aamas2020.conference.auckland.ac.nz (Website)

Conference

ConferenceInternational Conference on Autonomous Agents and MultiAgent Systems 2020
Abbreviated titleAAMAS 2020
CountryNew Zealand
CityAuckland
Period9/05/2013/06/20
Internet address

Cite this

de Nijs, F., & Stuckey, P. (2020). Risk-aware conditional replanning for globally constrained multi-agent sequential decision making. In B. An, & N. Yorke-Smith (Eds.), Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (pp. 303-311). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).