Privacy Preserving Multi Agent Path Finding

In the multi-agent path finding (MAPF) problem, a group of agents search in a graph for a path for each agent where no two paths collide. This work considers MAPF applications in which the agents do not wish to share their paths due to privacy constraints. We formulatetwotypesofprivacyconstraintsinthiscontext: planninglevel privacy and execution-level privacy. The former means the agents cannot identify the planned location of the other agents, and the latter means agents cannot sense the location of each other duringexecution. Weshowageneralapproachtopreserveplanninglevelprivacyand show tohowadapttwo popular MAPF algorithms, namely PIBT and LaCAM, to preserve execution-level privacy. We also propose a post-processing technique that allows agents to reducethe costsofthe returnedsolutionwithout losinganyprivacy.

Authors

• Rotem Lev Lehman Computer and Information Systems, Ben Gurion University of the Negev
• Roni Stern Ben-Gurion University of the Negev
• Guy Shani MSAI, Microsoft & Ben Gurion University of the Negev

Keywords

• Multi-Agent Path Finding
• Privacy Preserving Planning