TY - JOUR
T1 - Width-Based Search for Multi Agent Privacy-Preserving Planning
AU - Gerevini, Alfonso Emilio
AU - Lipovetzky, Nir
AU - Percassi, Francesco
AU - Saetti, Alessandro
AU - Serina, Ivan
N1 - Funding Information:
We would like to thank the reviewers for their thoughtful comments and efforts towards improving the paper. This research has been carried out with the support of resources from the National Collaborative Research Infrastructure Strategy (NeCTAR), the Department of Excellence Fund 2018-2022 of the Department of Information Engineering of the University of Brescia, and by AIPlan4EU , a project funded by EU Horizon 2020 research and innovation programme under GA n. 101016442 (since 2021). The work of A. E. Gerevini was supported by the EU ICT-48 2020 project TAILOR (n. 952215 ) and by the PRIN project RIPER (n. 20203FFYLK ). Nir Lipovetzky has been partially funded by DST group.
Publisher Copyright:
© 2023
PY - 2023/5/1
Y1 - 2023/5/1
N2 - In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, blind search algorithms such as width-based search can solve instances of many existing domains in low polynomial time when they feature atomic goals. Moreover, the performance of goal-oriented search can be improved by combining it with width-based search. In this paper, we investigate the usage of width-based search in the context of (decentralised) collaborative multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that width-based search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other involved agents. Moreover, we show that the use of width-based techniques can significantly reduce the number of messages transmitted among the agents, better preserving their privacy and improving their performance. An experimental study presented in the paper analyses the effectiveness of our techniques, and compares them with the state-of-the-art of collaborative multi-agent planning.
AB - In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, blind search algorithms such as width-based search can solve instances of many existing domains in low polynomial time when they feature atomic goals. Moreover, the performance of goal-oriented search can be improved by combining it with width-based search. In this paper, we investigate the usage of width-based search in the context of (decentralised) collaborative multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that width-based search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other involved agents. Moreover, we show that the use of width-based techniques can significantly reduce the number of messages transmitted among the agents, better preserving their privacy and improving their performance. An experimental study presented in the paper analyses the effectiveness of our techniques, and compares them with the state-of-the-art of collaborative multi-agent planning.
KW - Planning
KW - Multi-agent planning
KW - Privacy-preserving planning
KW - Distributed planning
UR - http://www.scopus.com/inward/record.url?scp=85150475154&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2023.103883
DO - 10.1016/j.artint.2023.103883
M3 - Article
VL - 318
JO - Artificial Intelligence
JF - Artificial Intelligence
SN - 0004-3702
M1 - 103883
ER -