  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.
