  Planning is one of the main approaches used to improve agents' working
efficiency by making plans beforehand. However, during planning, agents face
the risk of having their private information leaked. This paper proposes a
novel strong privacy-preserving planning approach for logistic-like problems.
This approach outperforms existing approaches by addressing two challenges: 1)
simultaneously achieving strong privacy, completeness and efficiency, and 2)
addressing communication constraints. These two challenges are prevalent in
many real-world applications including logistics in military environments and
packet routing in networks. To tackle these two challenges, our approach adopts
the differential privacy technique, which can both guarantee strong privacy and
control communication overhead. To the best of our knowledge, this paper is the
first to apply differential privacy to the field of multi-agent planning as a
means of preserving the privacy of agents for logistic-like problems. We
theoretically prove the strong privacy and completeness of our approach and
empirically demonstrate its efficiency. We also theoretically analyze the
communication overhead of our approach and illustrate how differential privacy
can be used to control it.
