Width-based search for multi agent privacy-preserving planning

DOI10.1016/J.ARTINT.2023.103883arXiv1906.03955MaRDI QIDQ6161467

Nir Lipovetzky, Alessandro Saetti, Ivan Serina, Francesco Percassi, Alfonso E. Gerevini

Publication date: 27 June 2023

Published in: Artificial Intelligence (Search for Journal in Brave)

Abstract: 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, the performance of goal oriented search can be improved by combining goal oriented search and width-based search. The combination of these techniques has been called best-first width search. In this paper, we investigate the usage of best-first width search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that best-first width 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 agents. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.

Full work available at URL: https://arxiv.org/abs/1906.03955

zbMATH Keywords

planningdistributed planningmulti-agent planningprivacy-preserving planning

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Unnamed Item
• Unnamed Item
• Fast planning through planning graph analysis
• The MADLA planner: multi-agent planning by combination of distributed and local heuristic search
• Distributed Heuristic Forward Search for Multi-agent Planning
• Strengthening Landmark Heuristics via Hitting Sets
• Quantifying privacy in multiagent planning
• Privacy-Preserving Set Operations
• Planning as heuristic search

This page was built for publication: Width-based search for multi agent privacy-preserving planning