Publication Details
Decentralized Planning Using Probabilistic Hyperproperties
Češka Milan, doc. RNDr., Ph.D. (DITS FIT BUT)
Francesco Pontiggia (TU-Wien)
Macák Filip, Ing. (DITS FIT BUT)
Michele Chiari
Probabilistic Hyperproperties, Decentralized Planning, Markov Decision Processes, Abstraction Refinement, Self-composition
Multi-agent planning under stochastic dynamics is usually formalised using decentralized (partially observable) Markov decision processes (MDPs) and reachability or expected reward specifications. In this paper, we propose a different approach: we use an MDP describing how a single agent operates in an environment and probabilistic hyperproperties to capture desired temporal objectives for a set of decentralized agents operating in the environment. We extend existing approaches for model checking probabilistic hyperproperties to handle temporal formulae relating paths of different agents, thus requiring the self-composition between multiple MDPs. Using several case studies, we demonstrate that our approach provides a flexible and expressive framework to broaden the specification capabilities with respect to existing planning techniques. Additionally, we establish a close connection between a subclass of probabilistic hyperproperties and planning for a particular type of Dec-MDPs, for both of which we show undecidability. This lays the ground for the use of existing decentralized planning tools in the field of probabilistic hyperproperty verification.
@INPROCEEDINGS{FITPUB13364, author = "Roman Andriushchenko and Milan \v{C}e\v{s}ka and Pontiggia Francesco and Filip Mac\'{a}k and Chiari Michele", title = "Decentralized Planning Using Probabilistic Hyperproperties", pages = "1688--1697", booktitle = "Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems", year = 2025, location = "Detroit, US", publisher = "International Foundation for Autonomous Agents and Multiagent Systems", ISBN = "979-8-4007-1426-9", language = "english", url = "https://www.fit.vut.cz/research/publication/13364" }