Best-First Width Search for Multi Agent Privacy-Preserving Planning

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings of the 29th International Conference on Automated Planning and Scheduling
Subtitle of host publication(ICAPS 2019)
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
PublisherAAAI press
Pages163-171
Number of pages9
ISBN (Print)9781577358077
Publication statusPublished - 6 Jul 2019
Externally publishedYes
Event29th International Conference on Automated Planning and Scheduling - Berkeley, United States
Duration: 11 Jul 201915 Jul 2019
Conference number: 29
https://icaps19.icaps-conference.org/

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

Conference29th International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS 2019
CountryUnited States
CityBerkeley
Period11/07/1915/07/19
Internet address

Fingerprint Dive into the research topics of 'Best-First Width Search for Multi Agent Privacy-Preserving Planning'. Together they form a unique fingerprint.

  • Cite this

    Gerevini, A. E., Lipovetzky, N., Percassi, F., Saetti, A., & Serina, I. (2019). Best-First Width Search for Multi Agent Privacy-Preserving Planning. In J. Benton, N. Lipovetzky, E. Onaindia, D. E. Smith, & S. Srivastava (Eds.), Proceedings of the 29th International Conference on Automated Planning and Scheduling: (ICAPS 2019) (pp. 163-171). (Proceedings International Conference on Automated Planning and Scheduling, ICAPS). AAAI press. https://aaai.org/ojs/index.php/ICAPS/article/view/3472