Paper deep dive
Privacy Preserving Multi Agent Path Finding
Rotem Lev Lehman, Roni Stern, Guy Shani
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 87%
Last extracted: 7/8/2026, 3:20:19 PM
Summary
This paper addresses privacy constraints in Multi-Agent Path Finding (MAPF), where agents must coordinate to avoid collisions while keeping their routes confidential. It introduces two privacy types: planning-level privacy (hiding exact planned locations during the planning phase) and execution-level privacy (hiding locations during runtime due to limited sensing). The authors propose the k-Privacy Preserving MAPF (kPPMAPF) framework using mock agents to achieve planning-level privacy, adapt existing algorithms like PIBT and LaCAM for execution-level privacy, and introduce a post-processing technique to optimize solution cost while maintaining privacy guarantees.
Entities (10)
Relation Signals (6)
kPP โ uses โ Mock agents
confidence 90% ยท kPP works by having each agent create a set of kโ1 mock agents, each associated with a unique pair of initial and target locations.
kPP โ achieves โ Planning-level privacy
confidence 88% ยท We propose a general framework for obtaining planning-level privacy, which works by adding mock agents to the planning process.
PIBT โ adaptedfor โ Execution-level privacy
confidence 85% ยท We show how to adapt two popular MAPF algorithms, namely PIBT and LaCAM, such that they preserve execution-level privacy.
LaCAM* โ adaptedfor โ Execution-level privacy
confidence 85% ยท We show how to adapt two popular MAPF algorithms, namely PIBT and LaCAM, such that they preserve execution-level privacy.
Post-processing technique โ improves โ Sum of Costs
confidence 82% ยท Lastly, we propose a post-processing technique that allows the agents to reduce the sum of costs of the returned solution without losing any privacy.
DisCSP โ usedfor โ Secure mock agent assignment
confidence 78% ยท We can model the problem of choosing the mock agents in a privacy-preserving manner as a DisCSP.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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. While in all applications of MAPF the agents must not collide with each other, in some of them the agents may not wish to share their paths due to privacy constraints. In this work, we formulate two types of privacy constraints for MAPF and propose algorithms that preserve them. The first type of privacy we consider is planning-level privacy, which means that during planning, the agents cannot identify exactly the planned location of the other agents. We propose a general framework for obtaining planning-level privacy, which works by adding mock agents to the planning process. The second type of privacy we consider is execution-level privacy, which is relevant when agents have limited sensing capabilities. Execution-level privacy is preserved if none of the agents is allowed to sense the location of the other agents during execution. We show how to adapt two popular MAPF algorithms, namely PIBT and LaCAM, such that they preserve execution-level privacy. Lastly, we propose a post-processing technique that allows the agents to reduce the sum of costs of the returned solution without losing any privacy. We also implemented our algorithms and evaluated them empirically, showing that the proposed post-processing technique indeed improved cost significantly.
Tags
Links
- Source: https://arxiv.org/abs/2605.14119v1
- Canonical: https://arxiv.org/abs/2605.14119v1
Trouble viewing inline? Open PDF directly โ
Full Text
75,617 characters extracted from source content.
Expand or collapse full text
Privacy Preserving Multi Agent Path Finding Rotem Lev Lehman Ben Gurion University of the Negev Beโer Sheva, Israel levlerot@post.bgu.ac.il Roni Stern Ben Gurion University of the Negev Beโer Sheva, Israel sternron@bgu.ac.il Guy Shani Ben Gurion University of the Negev Beโer Sheva, Israel shanigu@bgu.ac.il ABSTRACT 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. While in all applications of MAPF the agents must not collide with each other, in some of them the agents may not wish to share their paths due to privacy constraints. In this work, we formulate two types of privacy constraints for MAPF and propose algorithms that preserve them. The first type of privacy we consider is planning-level privacy, which means that during planning, the agents cannot identify exactly the planned location of the other agents. We propose a general framework for obtaining planning- level privacy, which works by adding mock agents to the planning process. The second type of privacy we consider is execution-level privacy, which is relevant when agents have limited sensing capa- bilities. Execution-level privacy is preserved if none of the agents is allowed to sense the location of the other agents during execution. We show how to adapt two popular MAPF algorithms, namely PIBT and LaCAM, such that they preserve execution-level privacy. Lastly, we propose a post-processing technique that allows the agents to reduce the sum of costs of the returned solution without losing any privacy. We also implemented our algorithms and evaluated them empirically, showing that the proposed post-processing technique indeed improved cost significantly. KEYWORDS Multi Agent Path Finding, MAPF, Privacy ACM Reference Format: Rotem Lev Lehman, Roni Stern, and Guy Shani. 2026. Privacy Preserving Multi Agent Path Finding. In Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), Paphos, Cyprus, May 25 โ 29, 2026, IFAAMAS, 10 pages. https://doi.org/10.65109/ 1 INTRODUCTION The Multi-Agent Path Finding (MAPF) problem arises when mul- tiple mobile agents must each find a path from their respective start locations to their goal locations on a shared graph. The pri- mary requirement is that these paths are collision-free, meaning that no two agents occupy the same location or swap locations simultaneously. MAPF is motivated by a wide range of real-world applications, such as automated warehouse robotics, airport ground traffic management, and digital entertainment, where efficient and safe coordination of multiple agents is essential. Most work on MAPF has assumed centralized control and com- plete information sharing between the agents. This is suitable for Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), C. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.), May 25 โ 29, 2026, Paphos, Cyprus.ยฉ 2026 International Foundation for Autonomous Agents and Multiagent Systems (w.ifaamas.org). https://doi.org/10.65109/ many use cases, such as warehouse robots controlled by a single operating company. In this work, we consider a different setting, where the agents are controlled by different entities that must col- laborate to avoid collisions and optimize a shared objective function, yet still wish to keep some information private from each other. A primary motivation for such a setting is compartmentalization due to security concerns. For example, consider an emergency response scenario in a large city, where multiple organizationsโsuch as fire departments, police, and private security firmsโdeploy their own autonomous vehicles or drones to respond to incidents. While these organizations must coordinate to avoid traffic congestion and en- sure rapid response, they may not wish to reveal the exact locations, routes, or priorities of their units due to operational security or privacy regulations. More use-cases for privacy-preserving MAPF include coordinated trucks and drones of different logistics compa- nies, coordinating routes of human taxi drivers, and coordinating the movement of robots in shared environments. In this context, MAPF algorithms must enable safe and efficient multi-agent coordi- nation while preserving the confidentiality of each organizationโs sensitive information. This form of privacy-preserving collaborative multi-agent plan- ning has been studied in the context of other types of multi-agent planning problems, including Multi-Agent STRIPS [2,12,14,16], Distributed Constraints Optimization (DCOP) [4,6] and Distributed Constraint Satisfaction Problem (DisCSP) [29,30]. In this work we explore different types of privacy requirements one may consider in the context of MAPF and how one can achieve them. We distinguish between two types of privacy in MAPF: planning- level privacy and execution-level privacy. Planning-level privacy means that the agents cannot infer from the information they share during planning process any location and time any of the other agents are planning to visit. Execution-level privacy means that even if the agents are equipped with some sensing capabilities, they would still be unable to infer the location of the other agents during execution. Formally defining these types of privacy is the first contribution of this work. To obtain planning-level privacy, we propose a general frame- work that works by adding mock agents to the planning process. Each real agent is associated with several mock agents, each has a fictitious start and goal location. Any MAPF algorithm can then be used to plan for all agents, including both real and mock agents. We discuss the type of strong privacy one obtains with this mechanism and its weaknesses. Then, we show how one can obtain execution- level privacy in two popular MAPF algorithms, namely PIBT [20] and LaCAM โ [19], given prior knowledge about the sensing capa- bilities of the other agents. To preserve privacy, the real agent cannot directly manipulate the planning process to optimize its own cost over the costs of the paths of the mock agents, as this may leak information about its arXiv:2605.14119v1 [cs.MA] 13 May 2026 true path. However, we show that the cost of the real agent can be improved in a post-processing step that does not affect the privacy guaranties. In this post-processing step, we identify safe zones in the plan, which are locations and time steps where the real agent can deviate from its planned path without risking a collision or detection with other agents. We then use these safe zones to re-plan locally for the real agent, improving its cost while maintaining the overall privacy guaranties. Finally, we implemented our privacy-preserving algorithms and evaluated them empirically, showing the relation between the amount of privacy we aim for and overall efficiency. Also, we show when our post-processing can be very effective and when it does not add significant gains. Overall, this work paves the way for future research on privacy-preserving MAPF, highlighting the trade-offs between privacy, efficiency, and solution quality in MAPF. 2 BACKGROUND AND PROBLEM SETUP A classical MAPF problem withํagents is defined by a tuple โจํบ,ํ ,ํกโฉwhereํบ=(ํ,ํธ)is an undirected graph whose vertices are the possible locations agents may occupy, and every edge(ํฃ,ํข) โ ํธ represents that an agent can move fromํฃtoํขwithout passing through any other vertex. The functionsํ andํกmap each agent to its initial and desired destination locations, respectively. Time is discretized into time steps. In every time step, each agent can either wait in its current location or move to a location adjacent to its current location. A single-agent plan for an agentํis a sequence of actions (wait or move) that if performed starting fromํ (ํ)will end up inํก(ํ). A joint plan is a set of single-agent plans, one for each agent. For a joint planฮ , we denote byฮ ํ its constituent single-agent plan for agentํ, and denote byฮ ํ (ํก)as the vertex agent ํ is planned to occupy at timestep ํก according toฮ ํ . A pair of agentsํandํhave a vertex conflict in a joint planฮ if, according to their respective single-agent plansฮ ํ andฮ ํ , both agents are planned to occupy the same vertex at the same time. Similarly, agents have a swapping conflict in a joint plan if they are planned to swap locations over the same edge at the same time. A valid solution to a MAPF problem is a joint plan without any conflict. Several solution cost functions have been proposed for MAPF. The two most common are sum of costs (SOC) and makespan, which are the sum and max, respectively, over the lengths of the single-agent plans in the solution. Finding cost-optimal solution for either cost function is NP-Hard [25,31], and in directed graphs even finding a solution is NP-Hard [15]. Nevertheless, many algorithms have been proposed for solving classical MAPF [5,26]. A MAPF algorithm is complete if it will eventually find a valid solution if one exists, and is optimal if the found solution minimizes the cost function. Some MAPF planners are complete and optimal, such as CBS [23], others only complete, such as LaCAM [18], and others neither complete nor optimal yet are known to be very fast, such as PIBT [20]. Anytime MAPF algorithms, such as LaCAM โ [19], quickly find an initial solution and then continuously improve it as long as additional runtime is available. In this work, we build on PIBT and LaCAM โ and therefore describe them briefly below. PIBT [20] is a sequential configuration generator, where a con- figuration here is anํ-sized vector representing the location of each agent. In each time step, PIBT accepts a configuration of the agentsํ ํํํํ and generates a new configurationํ ํกํ corresponding to a possible valid move of all agents. An initial priority is set at each timestep for all of the agents based on their distance to their goal, where the closest agent that hasnโt already reached its goal gains the highest priority. In order to determineํ ํกํ , PIBT sequen- tially assigns a vertex to each agent while avoiding collisions. The order of assignment depends on the priority given to each agent, but before assigning a vertexํฃto agentํ ํ , PIBT first checks if โํ ํ โ ํ ํ :ํ ํํํํ [ํ ํ ]= ํฃ. If suchํ ํ exists, then it must apply that ํ ํกํ [ํ ํ ]โ ํฃbecause of the collision avoidance. Ifํ ํกํ [ํ ํ ]was not assigned yet, PIBT is run onํ ํ to try and move it fromํฃ, andํ ํ gains the priority ofํ ํ to enable it to move lower priority agents in order to clear the way forํ ํ . If it was unable to move to another location, PIBT backtracks and tries to assign the next best vertex from the neighbors of ํ ํํํํ [ํ ํ ] for ํ ํ . LaCAM โ [19] is a two level-search algorithm, where each node in the high level search holds the configuration and a constraint tree, and search throughout the nodes in a depth-first manner. The low- level search gradually grows the constraint tree, and picks the next constraint node to explore, using a breadth-first manner. Then, after picking both high-level and low-level nodes, LaCAM โ generates a new configuration using a configuration generator. The config- uration generator must satisfy the constraints from the low-level node. The authors of LaCAM โ chose to use PIBT as a configuration generator, and so we also use it as such in our work. In this work we also build on DisCSP [29,30], and so describe it briefly together with privacy preserving solvers. A DisCSP is a tupleโจํด,ํ,ํท,ํถ,ํผโฉ, where โข ํด=ํ 1 ,ํ 2 , . . .,ํ ํ is a finite set of autonomous agents. โข ํ=ํฅ 1 ,ํฅ 2 , . . .,ํฅ ํ is a finite set of variables. โข ํท= ํท 1 ,ํท 2 , . . .,ํท ํ where eachํท ํ is a finite domain of possible values for variable ํฅ ํ . โข ํถ=ํ 1 ,ํ 2 , . . .,ํ ํ where each constraint ํ ํ is defined over a subset of variables and specifies the set of allowed tuples for those variables. Constraints can be defined over variables owned by the same agent or by different agents. โข ํผ:ํ โ ํด. The functionํผassigns each variable to exactly one agent, meaning (1) Agentํผ(ํฅ ํ )is the owner of variable ํฅ ํ . (2) Each agent controls the value assignment of its own variables. The work in [30] proposes a secure privacy-preserving DisCSP algorithm that: (1) Uses public-key cryptography and multiple co- operating servers to perform the search process on encrypted infor- mation. (2) Ensures the distributed search (similar to chronological backtracking) does not leak private information of any agent. (3) Guarantees that neither other agents nor the servers can infer addi- tional details about private variable values beyond the final agreed solution. In other words, agents can collaboratively solve the con- straint problem and reach agreement on a solution while keeping each agentโs private information completely confidential. Problem setup and assumptions. In this work, we consider a group of agents faced with a classical MAPF problemโจํบ,ํ ,ํกโฉ. That is, each agentํis initially located in an initial locationํ (ํ)and aims to reach a target locationํก(ํ)while avoiding collisions with the other agents. The environment is static and the agentsโ actions are deterministic. Each agent is fully aware of the underlying graphํบ, yet it does not know the initial and target location of the other agents. To coordinate, the agents may send messages to each other directly and immediately. Thus, without any privacy considerations the agents could solve the problem by sending their initial and target locations to one of the agents; have that agent reconstruct the MAPF problem and use any MAPF algorithm to solve it; share the solution with all agents; and finally have all agents safely execute it. The fundamental challenge we focus on in this work is that each agent does not wish the agents to know where it plans to visit in every timestep on its way to its target. That is, for a MAPF solution ฮ , agentํ, and time stepํก, the private information agentํdoes not wish to disclose is the locationฮ ํ (ํก). Next, we consider two stages where such information can be revealed or inferred โ during planning and during execution โ and propose methods to preserve privacy in these stages. Our setting somewhat similar to prior work on distributed meth- ods for solving MAPF [8,9,22,27,28]. One such approach [3,9] has each agent plan independently, coordinating and replanning online with other agents that enter its field of view. In that scheme, and in general in existing decentralized MAPF algorithms, agents may know the partial path of other agents if they are close to each other during the runtime. Thus, they do not provide any privacy guarantees, which is our primary objective. 3 PLANNING-LEVEL PRIVACY During planning, agents may be able to infer some knowledge about the private information of other agents by analyzing the messages sent by each agent. We denote byํthe set of messages passed between the agents during the planning process. The agentsโ belief about agentํat timeํก, denoteํ ํ (ํ,ํก), is the set of locations agent ํmay occupy at timeํกaccording toํ. In other words, the agentsโ belief about agentํcaptures the uncertainty of the other agents regarding the true location ofํat timestampํก. The belief state of the agents is the vectorํ=(ํ 1 , . . .,ํ ํ )containing all the agentsโ beliefs. Definition 1 (k-Privacy). A belief stateํis said to preserve k- Privacy if for every agentํand time stepํก, it holds that|ํ ํก ํ (ํ)| โฅ ํ. Intuitively, this means that for every agentํand time stepํก, the messages sent during planning are not sufficient to allow the other agents to narrow down the possible location of agentํto fewer thanํpossible locations. Next, we consider the problem of finding a solution to a given MAPF problem while preservingํ-privacy during the planning process. We call this problem the k-Privacy Preserving MAPF (kPPMAPF) problem. Note that MAPF is a special case of a kPPMAPF problem, where ํ= 1. 3.1 k-Privacy Preserving MAPF Planner Now we describe the k-Privacy Preserving MAPF Planner (kPP), which is a general algorithm for solving the kPPMAPF problem. kPP works by having each agentํcreate a set ofํโ1 mock agents, each associated with a unique pair of initial and target locations. Then, the agents collaboratively solve a larger MAPF problem that includes non-conflicting single-agent plans for both real and mock agents. Each (real) agent then follows the single-agent plan created for it, discarding the plans created for the mock agents. Next, we describe kPP in more details. In kPP, the agents start by designating randomly one of the agents to be the planning agent. Then, each agentํperforms the steps described in Algorithm 1. First, it creates a set ofํpairs of initial and target locations, denoted AgGroup ํ . This set includes the pair(ํ (ํ),ํก(ํ)), i.e., the agentโs real initial and target locations, as well asํโ1 additional pairs. These pairs must be unique, i.e., different from(ํ (ํ),ํก(ํ)), from each other, and from the pairs used by the other (real) agents. Then, the agent shuffles these pairs randomly and shares them with all other agents (line 5 in Alg. 1). Next, agentํwaits until all agents have broadcast will receive the agents groups of all agents. At this point, ifํis the designated planning agent, then it creates a MAPF problem with the initial and target locations in all agent groups (a total ofํ ยท ํโagentsโ). Then, it calls any off-the-shelf MAPF solver to solve this MAPF problem, and broadcasts the solution to all the agents. Ifํis not the planning agent, then it waits for the solution to be broadcasted by the planning agent. Finally, agentํextracts from the solution created by the planning agent only the single-agent plan starting from ํ (ํ) and ending in ํก(ํ) (line 12). Figure 1a(left) illustrates a kPPMAPF problem with two agents and the solution created for it by kPP forํ=2. The mock agents are marked in green and orange and the dashed lines mark the plans created for them. 3.2 Choosing the Mock Agents A critical step in kPP is how each agent chooses the initial and target locations of its ํโ 1 mock agents (line 3). We consider an assignment of mock agents to have a collision be- tween two agentsํ, ํ, if there exists a tuple (real or mock)โจํ ํ ํ ,ํ ํ ํ โฉ in the group of locations of agentํ, and a tuple (real or mock) โจํ ํ ํ ,ํ ํ ํ โฉin the group of agentํ, whereํ ํ ํ = ํ ํ ํ โจํ ํ ํ =ํ ํ ํ . Note that if any collision is found between two assignments, we cannot find a valid plan for the overall kPPMAPF. Also note that if two agents collide in their published groups of locations, and one of them (ํ) changes its previously published setํby replacing a subset of locationsํฟ โ ํto be another set of size|ํฟ|, then all other agents can understand that its real tupleโจํ (ํ),ํ(ํ)โฉ โ ํ\ ํฟ. This reduces ํโs privacy toํ โ|ํฟ|privacy instead of the wantedํprivacy. So, Algorithm 1: kPP for agent ํ 1 AgGroup ํ โ (ํ (ํ),ํก(ํ)) 2 for ํ= 1 to ํ do 3 ํ (ํ ํ ),ํก(ํ ํ ) โchoose unique initial and target locations 4Add(ํ (ํ ํ ),ํก(ํ ํ )) to AgGroup ํ 5 Shuffle AgGroup ํ and broadcast it to all agents 6 Wait for all agents to broadcast their agents group 7 if ํ is the designated planning agent then 8ฮ โ solve for all agent groups 9Broadcastฮ to all agents 10 else 11ฮ โ Wait for a solution from the planning agent 12 Extract single-agent plan for(ํ (ํ),ํก(ํ)) 0 123 4 a0 0 a0 0 0 1234 a0 1 a0 1 0-3 4567 a1 0 a1 0 012 a1 1 a1 1 (a) kPPMAPF problem and the so- lution created for it by kPP. 0 1-234 5 a0 0 a0 0 0 12-345 a0 1 a0 1 0 12 3 4 567 8910 11 12 a1 0 a1 0 01-78 a1 1 a1 1 (b) ekPPMAPF problem. Dashed squares represent the FoV of ํ 0 1 ,ํ 1 0 at time step 3 of the plan. a0 0 a0 1 a1 0 a1 1 (c) FoV of each agent at time step 1 of the plan from figure 1b. 0 123 4 a0 0 a0 0 0 12-345 a0 1 a0 1 0 12 3 4 567 8910 11 12 a1 0 a1 0 012 a1 1 a1 1 (d) PPfPP solution with initial and extended safe zones at time step 2 of the fPP plan. Figure 1: Examples of kPPMAPF (1a), ekPPMAPF (1b), FoV (1c), and of PPfPP (1d) with 2 agents (ํ 0 andํ 1 ) andํ=2. Squares represents the initial location of each agent and stars represent the desired destination. The real agent of each group has a full line in the path and the mock agent has a dotted line. An X on the path of an agent marks that the agent waits in place in that spot for at least 1 timestep. The timestep of vertices in the plan appears near the vertex. In figure 1d the blue and red vertices correspond to the initial safe zones forํ 0 andํ 1 , respectively, while green and orange correspond to the extended safe zones. in order to keep the neededํprivacy criteria, the algorithm used to pick mock agents need to publish the actual groups of locations only once, and to not have collisions. We will now consider different options for selecting mock agents and discuss their pros and cons. 3.2.1 Choosing Mock Agents Randomly. One approach to do so is to have each agent choose its group of locations randomly. A limitation for this approach is that two agents may collide in their assignments, as seen above. We will now calculate the probability of such collision to occur. The probability of no collision in the assignment of mock agents for a specific pair of agents in a graph with|ํ|vertices, and a desire forํ-privacy, when each agent chooses mock agents randomly is calculated in the following way: Each agentํhas a predefined real tupleโจํ (ํ),ํ(ํ)โฉ, which do not collide with other agents real tuple. Then each agent choosesํ โ1 mock tuple, i.e. 2(ํโ1)vertices of theํโ1 mock tuples from the remaining|ํ|โ1 vertices, resulting in the following probability: ( |ํ|โ1โ2ํ 2(ํโ1) ) ( |ํ|โ1 2(ํโ1) ) . Therefore, The probability of no collisions in the assignment ofํagents is approximately: ยฉ ยญ ยซ |ํ|โ1โ2ํ 2(ํโ1) |ํ|โ1 2(ํโ1) ยช ยฎ ยฌ ( ํ 2 ) ํโโ,ํ>1 โโ 0 As can be seen, this approach can lead to collisions with higher probability as the number of agents planning grows. Next, we explain some other methods for choosing mock agents. 3.2.2 Choosing Mock Agents using a DisCSP. We suggest another approach for choosing the mock agents in a way that will both not collide with other agents and will preserve the privacy of each agent by not revealing the real (start, goal) tuple of each agent. We can model the problem of choosing the mock agents in a privacy- preserving manner as a DisCSP. Each agent will have 2(ํ โ1) variables, representing the start and goal of its mock agents, and two additional variables for the real start and goal. The domain of each variable is all possible locations in the graph (ํ). The public constraints are for agents to avoid conflicts. The private constraints of each agent are to ensure that its real start and goal are assigned to it. Solving this DisCSP will ensure that every agent will have its real start and goal in its k-sized group, and there will be no conflicts, while making sure that this assignment does not reveal any private information. The wanted privacy model here is to hide the private constraints of the agents, and make sure other agents cannot distinguish be- tween the real tuple of each agent and its mock tuples. This can be solved securely using the method in [30], since they make the search process in remote servers that do not know the values of the variables since they are encrypted, and the agents do not know any knowledge about the failed assignments that happens during the search process (which could reveal the collision between two agents groups), since they are not part of the search and only receive the final assignments for their groups. Hence, we can conclude that no agent can distinguish the other agents real start and goal vertices from their set of disclosed locations. Solving this DisCSP problem can be very expensive in large graphs, with many agents and large values of k, so one can think of using a different approach that we explain now. 3.2.3 Mock Agents Dispatcher. We suggest yet another approach of choosing the mock agents, by using an external dispatcher agent whose sole role is to centralize the process of generating a unique initial and target location pairs when requested to do so by an agent (line 3). This external dispatcher agent knows the real initial and target locations of all agents and makes sure they do not collide. This can be viewed as some loss of privacy. However, it is external to the path planning agents, and so it does not know the plans the agents end up selecting. Thus, unless the dispatcher collaborates with one of the agents, the amount of privacy lost is limited to the dispatcher knowing the start and goal locations of the agents. In order to motivate the use of the external dispatcher, consider a different problem setting, where the dispatcher maintains a large pool of tasks and assigns ํ candidate tasks to each agent, without knowing which of theํtasks the agent will actually commit to. This provides a natural way to generate indistinguishable alternatives without requiring plan-level information. The kPP algorithmโs behavior is independent of the mock agents selection method in use, and one can use whichever method it prefers. We chose to implement our experiments in section 6 using the external dispatcher method because of its simplicity. 3.3 Theoretical Analysis of kPP Due to space constraints, we prove informally, the main theoret- ical property of kPP, namely, that it outputs valid solutions that preserves ํ privacy. Theorem 1 (kPP Solves kPPMAPF problems). If the designated planning agent in kPP returns a valid MAPF solution, then kPP returns a valid kPPMAPF solution. Proof outline: A valid MAPF solution ensures there are no conflicts between all agents. This includes conflicts between the real agents and also conflicts between a real agent and the other (mock) agents in its agent group. This means that at any point in time the agents in an agent group occupyํdifferent locations. All messages sent between the agents are agnostic to who is the main agent and who is the mock agents within an agent group. Thus, the belief state will be the same regardless of who is the real agent. Thus, a conflict-free solution has been found andํ-privacy preserved. Unfortunately, kPP is not complete, since there could be a ran- domized agent group initial locations and targets that would make the original MAPF problem solvable but the new problem unsolv- able. Similarly, kPP is not optimal even if the designated planning agent uses an optimal MAPF algorithm. 4 EXECUTION-LEVEL PRIVACY The agents in MAPF may be equipped with sensors that allow them to sense the location of nearby agents. In such cases, the agents risk revealing their locations during execution, even if they execute a MAPF solution generated by a planning-level privacy preserving MAPF algorithm. Next, we formally describe the problem that arises in these cases and discuss how to ensure privacy is still preserved, even during execution. 4.1 Conflicting Field of Views We formalize the sensing capability of an agentํby a Field of View (FoV) functionํน ํ that maps every possibly locationํฃof agentํto the locations agentํcan sense when situated inํฃ. If an agent can sense the location of another agent during execution, i.e., it enters if FoV, then that agentโs privacy has been compromised. We refer to this as as FoV conflict and define it formally as follows. Definition 2 (FoV Conflict). A pair of single agent plansฮ ํ andฮ ํ assigned to agentsํandํ, respectively, are said to have a FoV conflict if there existsํกsuch that eitherฮ ํ (ํก) โ ํนํํ ํ (ฮ ํ (ํก))or ฮ ํ (ํก) โ ํนํํ ํ (ฮ ํ (ํก)). An ePPMAPF problem is defined by a tupleโจํ โ ,ํนโฉwhereํ โ is a classical MAPF problem, andํน 1 , . . .,ํน ํ is the agentsโ FoV functions. A solutionฮ for an ePPMAPF problem is called valid if it is a valid solution for the underlying MAPF problem (ํ โ ) and it has no FoV conflict. It is hard to motivate preserving privacy during execution but not during planning. Thus, for the rest of this work we require a valid ePPMAPF solution to also preserve ํ -privacy. Definition 3 (Runtime k-Privacy). An ePPMAPF solutionฮ preserves Runtime k-Privacy if the belief state generated from finding ฮ preserves k-Privacy and there are no ํนํํ conflicts inฮ . The ekPPMAPF problem is defined as the problem of finding a runtimeํ-privacy solution for a given MAPF problem, desired planning-level privacy ํ , and FoV functions. Definition 3 is important, since it makes the runtime stage, where agents are aware of the joint plan for all agents, k-privacy preserv- ing, since if the agentํ ํ sawํ ํ at vertexํฃduring the runtime, at timeํก, it ruins the entire belief state ofํ ํ not only forํ ํก ํ , but also for allํ ํก โฒ ํ |ํก โฒ โ ํก , sinceํ ํ can now understand in hindsight that the path related to theํฃthatํ ํ is traversing in the joint plan, is its real path. In a different case, if agentํ ํ traverses near vertexํฃat timeํกwhereํฃ โ ํ ํก ํ (ฮ )butํ ํ can see thatํ ํ is not inํฃat time ํก, thenํ ํ can reduce the belief state ofํ ํ to beํ ํก ํ โฒ โ ํ ํก ํ \ํฃ, and, again, it can do so for the entire path that is related toํฃin the joint path, and by doing so, it reduces the privacy ofํ ํ from ํ โ ํํํํฃํํํฆto(ํ โ1) โ ํํํํฃํํํฆ. This is why it is important to preserveํ ํขํํกํํํ ํโํํํํฃํํํฆwhen there are sensors in the agents and ํโ ํํํํฃํํํฆ is needed. Figure 1b illustrates an example of a ekPPMAPF problem and a valid solution for it forํ=2,ํ=2,โํฃ:ํน 0 (ํฃ)= ํน 1 (ํฃ)= ํข||ํข.ํฅ โ ํฃ.ํฅ| โค1 &|ํข.ํฆโ ํฃ.ํฆ| โค1. As can be seen, The plan from figure 1a is not valid for the ekPPMAPF problem, since the paths in that plan hasํนํํconflict. As a result a different path for ํ 1 0 is chosen, but in timestep 2, agentํ 0 1 must wait-in-place, since otherwise it will collide with agentํ 1 0 . As can be seen, theํนํํof the two agents do not contain the other agent, and so the plan is now valid. Figure 1c shows theํนํํof the agents at time step 1. Notice that theํนํํof agentsํ 0 0 andํ 0 1 contain the other agent, but it is fine since they are both in the same agent-group. Notice that kPPMAPF problem is a sub-problem of an ekPPMAPF problem, whereโํ ํ โํฃ ํน ํ (ํฃ)=ํฃ. A straightforward ekPPMAPF planner can be obtained by ex- tending the kPP, resulting in the Field-of-Viewํ-Privacy Preserving Planner (fPP). fPP follows the standard kPP framework but modi- fies the underlying MAPF planner to incorporate additionalํนํํ conflicts that prevent agents from entering each otherโs fields of view. Theseํนํํconflicts are enforced only between different agent groups, and not between sub-agents within the same group, since sub-agents represent hypothetical alternatives of a single real agent. Consequently, visibility among sub-agents of the same group does not compromise privacy during execution. Note that when selecting the agent groups in line 3 of algorithm 1, as seen in section 3.2, we need to consider a broader collision definition, which also takes into account that in each tuple of start, goal vertices the vertices are not in theํนํํof other agents tuples. 4.2 Theoretical Analysis of fPP By construction, fPP preserves runtimeํprivacy. As discussed in section 3.3, kPP is neither complete not optimal, and so fPP is also neither complete nor optimal. Section 5 proposes a post-processing plan improvement step that can be performed on top of fPP to reduce the cost of the solution returned without compromising the required runtime ํ privacy requirement. 4.3 Implementing fPP fPP requires theํํํused by it to avoid FoV conflicts with agents of different agent groups. In order to support it, one can alter available MAPF planners to support theํนํํ ํํํํํํํํกavoidance. Of course, there will be no conflict ifํ ํ ํ andํ ํ ํ which are in the same agent groupํ ํ will be in each otherโs FoV, and so the sub-solver we use should avoid considering this as a conflict. Next, we describe how to do so in two state-of-the-art MAPF planners:ํํผํตํ[20] and ํฟํํถํดํโ [17โ19]. PIBT is built to have a priority inheritance stage and a backtrack- ing stage, inside a loop. The priority inheritance means that if an agentํ ํ with higher priority wants to go to a vertexํฃwhere an agent with lower priorityํ ํ resides currently, then it will start a PIBT session forํ ํ in order for it to move fromํฃto some other vertex and letํ ํ go toํฃ, and in the process move other agents, even with higher priority thanํ ํ , but with lower priority thanํ ํ . If it cannot move to another location then it will backtrack andํ ํ will have to find a different location to go to. In order to supportํนํํ conflicts resolution, we donโt move only the agentํ ํ from its loca- tion, but all agents in the setํ ํ |ฮ ํ (ํก) โ ํน ํ (ํฃ)โจ ํฃ โ ํน ํ (ฮ ํ (ํก)) must move to clear the way forํ ํ , since otherwise there will be aํนํํconflict at time t. To do so we run PIBT on all of the set of agents in the field of view ofํฃ, and if one of them fail (cannot move from its current location), we backtrack all of the set (since they do not longer have the priority of ํ ํ ). LaCAM โ builds on PIBT to generate configuration. Thus, adapt- ing it to support execution-level privacy is straightforward - simply use the adapted PIBT described above. We note that LaCAM โ also includes a slight change to PIBT to support a swap operation which increases performance. We did not implement this in our work as it requires additional modifications that we leave to future work. 5 IMPROVING SOLUTION QUALITY A key property of a runtimeํ-privacy solution is that for every timestepํกand agentํ, all the locations planned for agentํand associatedํ โ1 mock agents will not be in the FoV of any other agent. We refer to such vertices, i.e., the vertices that are guaranteed to not be sensed by any other agents, as the safe zone of agentํat timestepํก. Each agent can choose a different plan for itself without coordinating with the other agents as long is the new plan only occupies vertices in corresponding safe zones. This can be beneficial, as the agent may now prioritize its single-agent plan over those of itsํ โ1 mock agents, potentially obtaining lower SOC for itself, without compromising privacy. Next, we discuss how this can be done. 5.1 Safe zones in ekPPMAPF plans In this section we define notions to be used in the post process for improving the plans originated from running fPP. Definition 4 (Agent Groupโs FoV). An agent groupํ ํ โs FoV in timestepํกon a given planฮ generated by fPP on an ekPPMAPF problem P, denoted ํนํํ ํก ํ (ฮ ), is the setํฃ|โํ ํ ํ ํฃ โ ํน ํ (ฮ ํ (ํก)). In other words,ํนํํ ํก ํ (ฮ )is the set of vertices that are in the FoV of any agent in the group of ํํํํ ํ in time ํก using the planฮ . Definition 5 (Initial Safe-Zone). The initial safe-zone of an agent groupํ ํ in a specific timestepํกon a given planฮ that was generated from running fPP on an ekPPMAPF problem P, denoted ํผํ ํก ํ (ฮ ), is the setํฃ|ํน ํ (ํฃ) โ ํนํํ ํก ํ (ฮ ). In other words,ํผํ ํก ํ (ฮ )is the set of vertices that all of the vertices in their FoV are in the agent groupโs FoV. Definition 6 (Separated Safe Zones). A set of safe-zonesํ(ฮ )= ํ ํ (ฮ )|โํ โ ํด , is called separated, if and only if: โํกโํ โ ํดโํฃ โ ํ ํก ํ (ฮ )โํโ ํยํข โ ํ ํก ํ (ฮ ) : ํข โ ํน ํ (ํฃ)||ํฃ โ ํน ํ (ํข). In other words, A set of safe-zonesํ(ฮ )is separated if all of the vertices in eachํ ํ (ฮ )are out of the field of view of each other in each timestep. Definition 7 (Symmetric Field of View function). A Field of View functionํนis considered symmetric, if and only ifโํฃ โ ํโํข โ ํน(ํฃ) : ํฃ โ ํน(ํข). Definition 8 (PathCost). A single agentํpath cost, denoted ํํํกโํถํํ ํก(ฮ ํ ), is the amount of actions performed by agentํinฮ ํ until it reaches ํ(ํ) and stays there. Definition 9 (Real Agent SoC). A real-agent SoC of an ekPPMAPF planฮ , denotedํ ํํํถ(ฮ ), is calculated as follows:ํ ํํํถ(ฮ ) โ ร ํ ํ โํด ํํํกโํถํํ ํก(ฮ [ํ ํ .ํํํํ_ํํํํํก]). In other words,ํ ํํํถ(ฮ )is the sum of costs of the real agentsโ paths. 5.2 Post-Processing fPP algorithm Algorithm 2 is run by a shared planner. It first calculates theํผํ, as de- fined in definition 5. Then using it, it calculates theํธํ, which is the extended safe zone. It does so by usingํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก ). ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )is a function for each agent, that defines the policy of the agent on picking the next vertex to add to its extended safe zoneํธํ ํก ํ . Then, each agent groupํ ํ can useํธํ ํ to calculate the best single agent plan for its real agent that passes only inside of theํธํ ํ (this is the FindPathForRealAgent method in line 7 in Alg. 2). In our implementation, it is done by usingํํผํ[21], since it handles well planning with safe intervals, which in our case where the safe intervals from ํธํ ํ . Definition 10 (Rules for Extending Safe Zone). The function ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )is a function thatํ ํ uses for extending the safe zoneํธํ ํก ํ . It must pick one vertexํฃto add toํธํ ํก ํ . It returnsํํ ํํธ if foundํฃthat was added toํธํ ํก ํ ,ํนํดํฟํํธotherwise, and it must follow the following rules: (1) ํฃ is a neighbor of someํข โ ํธํ ํก ํ . (2) โํ ํ ,ํฃโ ํธํ ํก ํ . (3) โํ ํ โ ํ ํ ,ยํข โ ํธํ ํก ํ : ํข โ ํน ํ (ํฃ)โจ ํฃ โ ํน ํ (ํข). (4)Using it must preserve the runtime k-Privacy ofํ,ฮ after running it. For example, a function that qualifies for all of the rules above is the functionํธํฅํกํํํํํํํํํํํํ ํํํํํํํฆdefined in algorithm 3. Algorithm 3 can be implemented distributively, by setting the same random seed and the order of agents to pass by in the for loop at line 13 to each agent for ensuring that they all result in the same ํธํ . Figure 1d shows an example for the initial and extended safe zones, and for the plan generated from the extended safe zones using the PPfPP algorithm. As can be seen, the fPP plan in figure 1b is not the same as the PPfPP plan in figure 1d. For example,ํ 0 0 waited at time step 1, in the fPP plan, since otherwise it would have a conflict withํ 0 1 which must wait at time step 2. Although, in the PPfPP we can see that the initial safe zone ofํ 0 contains the steps needed forํ 0 0 to continue without waiting until it reaches its goal. This reduces the path cost ofํ 0 , which its real agent is ํ 0 0 , to 4 instead of 5. Algorithm 2: Post-Processing (fPP) Solutions (PPfPP) 1 Input:ฮ : An ekPPMAPF solution 2 Output:ฮ โฒ refined for all agent groups 3 Function PPfPP: 4 ํผํ(ฮ ) โ initial safe zone as defined in definition 5 ; 5 ํธํ(ฮ ) โ ํธํฅํกํํํํํํํํํํํ(ํผํ(ฮ )) ; 6 foreach ํ ํ โ ํด do 7ํ ํ .ํนํํํํํํกโํนํํํ ํํํํดํํํํก(ํธํ ํ (ฮ )) ; 8 Function ExtendSafeZone(IS): 9ESโ IS ; 10 foreach ํก โ ํ do 11do 12ํํํํ โ ํํ ํํธ; 13foreach ํ ํ โ ํด do 14ํํํํํํ โ ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก ) ; 15ํํํํ โ ํํํํโงยฌํํํํํํ ; 16whileยฌํํํํ; 17 return ES ; Algorithm 3: Extend safe zone randomly. 1 Function ํ ํ .ํธํฅํกํํํํํํํํํํํํ ํํํํํํํฆ(ํธํ ํก ): 2 ํ โํฃ|โํข โ ํธํ ํก ํ : (ํข,ํฃ) โ ํธโจ(ํฃ,ํข) โ ํธ\ ํธํ ํก ํ ; 3 foreach ํ ํ โ ํ ํ do 4ํ โ ํ \ ํธํ ํก ํ \ ํธํ ํกโ1 ํ ; 5ํ โ ํ \ํฃ|โํข โ ํธํ ํก ํ : ํข โ ํน ํ (ํฃ)โจ ํฃ โ ํน ํ (ํข) ; 6 if |ํ|> 0 then 7ํฃ โ ํ ํํํํํํํํํ(ํ) ; 8ํธํ ํก ํ โ ํธํ ํก ํ โชํฃ ; 9returnํํ ํํธ ; 10 return ํนํดํฟํํธ ; ํ 1 1 on the other hand, cannot continue to its goal on time step 2 based on its initial safe zone, since it contains only the vertex it steps on in the fPP plan. But, the extended safe zone does contain its goal at time step 2, and so it can continue to it. This reduces the plan cost of ํ 1 , which its real agent is ํ 1 1 , to 2 instead of 8. 5.3 Theoretical Analysis of PPfPP In this section we will show that the extension of safe zones is safe, that PPfPP returns valid ekPPMAPF plans, and that the resulting plan cost is less or equal to the original plan. Theorem 2 (Initial safe-Zone Safeness). An initial safe-zone ํผํ(ฮ )calculated from definition 5, whenโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ) & ํน ํ is symmetric, is safe. Theorem 3 (Extended Safe-Zone Safeness). An extended safe- zoneํธํ(ฮ )calculated from runningํธํฅํกํํํํํํํํํํํin line 8 in algorithm 2 onํผํcalculated from definition 5, when the function ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )from line 14 follows the rules from defini- tion 10, whenโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)&ํน ํ is symmetric, is safe. Theorem 4 (PPfPP Solves ekPPMAPF Problems). Ifํธํwas calculated using aํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )function that follows the rules from definition 10, andโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)& ํน ํ is symmetric&โํข โ ํฃ.ํํํํโํํํํ :ํข โ ํน ํ (ํฃ), then PPfPP returns valid ekPPMAPF plans. The proofs for theorems 2, theorem 3, and theorem 4 are pretty straightforward, and hence are attached in the supplementary ma- terial of this paper. Even though kPPMAPF is a sub-problem of ekPPMAPF, we cannot run kPPMAPF plans inside the PPfPP algorithm to improve their plan cost, since in Theorem 4 we must have the neighbors of each vertex inside the FoV function in order for it to return valid plans (to avoid ํ ํคํํํํํ conflicts). Theorem 5 (PPfPP Improvesํ ํํํถ(ฮ )). Ifํธํwas calculated using aํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )function that follows the rules from definition 10, andโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)& ํน ํ is symmetric, andฮ โฒ is the result of running PPfPP on a valid ekPPMAPF planฮ , then ํ ํํํถ(ฮ โฒ ) โค ํ ํํํถ(ฮ ). The proof of theorem 5 is trivial as theํธํwill always contain the previous plan and SIPP is an optimal algorithm. 6 EXPERIMENTAL RESULTS In this section, we evaluate our algorithms on a standard MAPF benchmark [24] using the modified PIBT [20] and LaCAM โ [19] algorithms as described in Section 4.3. We ran our experiments 4-neighborhood grids from the standard grid-based MAPF benchmark [24]. Twelve grids were selected from this benchmark with different size and sparseness. The maps chosen to run experiments on, with their corresponding amount of vertices, are: (1) brc202d (|ํ|=43,151), (2) lt_gallowstemplar_n (|ํ|= 10,021), (3) maze-32-32-2 (|ํ|=666), (4) orz900d (|ํ|=96,603), (5) ost003d (|ํ|=13,214), (6) random-32-32-20 (|ํ|=819), (7) random-64-64-20 (|ํ|=3,270), (8) room-32-32-4 (|ํ|=682), (9) room-64-64-16 (|ํ|=3,646), (10) room-64-64-8 (|ํ|=3,232), (11) warehouse-20-40-10-2-1 (|ํ|=22,599), and (12) warehouse-20-40- 10-2-2 (|ํ|=38,756). In terms of sensing, we assumed an agent can sense nearby agent based on the following parametric and symmetric FoV function: ํน ํ ํ (ํฃ)=ํข||ํข.ํฅ โ ํฃ.ํฅ| โค ํ & |ํข.ํฆโ ํฃ.ํฆ| โค ํ(1) 6.1 Results In the first set of experiment, we varied the number of agents ํ=10,20, . . .,50, desiredํ-privacy values ofํ=1,2,3, and FoV sizesํ=1,2,and 3. Each setting was run 3 times with different random seeds, and was given 1 minute to finish. The experiments ran on a cluster of computers, each with 20 CPUs and 40GB of RAM, and in parallel with 4 processes running different instances. Figure 2 shows a cactus chart of the RSoC of the problem against the #solved problems for using both sub solvers LaCAM* and PIBT in fPP with different k values. It was analyzed over the entire experiment results, including all different agent amounts andํนํํ ํ values. The x axis represents the amount of solved instances, and the y axis represents the RSoC of the solved instance. As expected, increasingํdecreases the amount of solved instances, for example, in figure 2c, we saw that using LaCAM โ withํ=1 solved 56 instances,ํ=2 solved 37 andํ=3 solved 29. In most cases, using LaCAM โ as the sub-solver of fPP solved more instances, for example in figure 2a withํ=2, we saw that LaCAM โ solved 38 while PIBT solved only 28 instances. Notice that the RSoC of the instances that were solved by LaCAM โ and not by PIBT (the harder instances) was extremely high. This is due to the fact that LaCAM โ is an any-time algorithm that improves the SoC of the found plan when more time is given, so on harder problems it found an initial plan and improved it only a little in comparison to easier problems. This trend can be seen for example in figures 2a and 2c. Figure 3 shows a cactus chart similar to figure 2, but using differ- ent FoV radius values. Increasing the FoV radius drastically impacts both the amount of solved instances and the solution quality. For example in the map maze-32-32-2 in figure 3b the only solved in- stances were of FoV radius=0. We also see that in figure 3d it was not so drastically affected from the increase in FoV. We assume it is because of the many narrow corridors within the map that make the instances with FoV radius>0 have a very little amount ofํนํํ conflicts, since they can just follow each other in the corridor in a safe distance from each other and they will be able to pass without a conflict. Similar trends were observed in the other maps. We show these results for both figures 2 and 3 in the supplementary material. In the second set of experiments, we aimed to explore the impact of higher values ofํ. Thus, we limited the range of values for the other experiment parameters, namely we ran fPP on all maps withํ โ [2,10],ํ=10,ํ=1, and using PIBT and LaCAM โ as sub-solvers. Every experiment was performed 30 times for each configuration of parameters with different random seeds. For each instance solved by fPP under 1 minute, we ran the PPfPP algorithm with a timeout of 5 minutes. We ran this entire experiment on the cluster, with each map running in a different node. Each node ran with 40 CPUs for fPP and 50 CPUs for PPfPP and 60GB of RAM, in parallel, with 8 processes running different instances and 10 threads running in each process for calculating the ES in parallel Table1:AverageRSoCimprovement% ํ ํํํถ(ํ ํ)โํ ํํํถ(ํํ ํ) ํ ํํํถ(ํ ํ) โ100% (meanยฑstd, max and median (med)) of PPfPP over fPP, across domains with different k values. #S is the amount of solved instances by fPP (all instances also were also solved by PPfPP). * and ** marks significant improvement of PPfPP over fPP (Wilcoxon, p<0.05 and p<0.01 accordingly). fPP MS is the makespan of the original plan created by fPP. Each map shows the amount of vertices in it(|ํ|). Mapkํ ํํํถ ํผํํํํํฃํํํํํก%#Stime fPP meanยฑ stdmaxmed[s]MS brc202d | ํ | = 43 , 151 2 0.77ยฑ 2.47 โ 11.50 0.02 56 113.6 943.9 3 0.64ยฑ 1.65 โ 7.25 0.02 55 116.0 975.4 4 1.04ยฑ 2.69 โ 11.30 0.02 47 121.2 1022.4 5 1.06ยฑ 2.66 โ 11.27 0.00 40 125.3 1041.3 6 1.20ยฑ 2.68 โ 10.72 0.02 39 124.0 1040.9 7 1.80ยฑ 3.90 โ 12.90 0.03 42 131.0 1094.5 8 2.04ยฑ 4.45 โ 16.91 0.07 30 137.6 1170.1 9 3.21ยฑ 6.40 โ 22.83 0.11 25 143.4 1203.6 10 1.01ยฑ 2.69 โ 13.21 0.07 25 143.8 1312.6 random-64-64-20 | ํ | = 3 , 270 2 0.20ยฑ 1.05 โ 7.75 0.00 56 0.390.5 3 0.62ยฑ 1.89 โ 10.34 0.00 48 0.396.7 4 0.73ยฑ 1.84 โ 7.65 0.00 38 0.3100.3 5 1.33ยฑ 2.60 โ 10.00 0.23 29 0.4106.8 6 1.04ยฑ 2.30 โ 8.33 0.20 21 0.4120.4 7 0.70ยฑ 1.24 โ 4.85 0.19 19 0.4146.4 8 0.93ยฑ 1.88 โ 5.72 0.23 15 0.5151.8 9 2.97ยฑ 5.36 โ 18.32 0.16 12 0.7244.6 10 0.86ยฑ 1.55 โ 3.64 0.16 50.9294.6 Mean 2 0.50ยฑ 1.61 โ 11.50 0.00 518 19.5 293.3 3 0.68ยฑ 2.22 โ 25.74 0.00 440 22.3 336.9 4 0.49ยฑ 1.55 โ 11.30 0.00 360 24.6 374.7 5 0.93ยฑ 2.35 โ 19.11 0.02 289 26.4 408.3 6 0.83ยฑ 2.25 โ 17.06 0.00 244 30.2 451.8 7 1.04ยฑ 2.86 โ 18.33 0.03 202 37.7 507.6 8 1.06ยฑ 2.78 โ 16.91 0.04 176 36.2 518.6 9 1.66ยฑ 3.90 โ 22.83 0.05 137 38.6 548.7 10 0.71ยฑ 1.93 โ 13.21 0.05 119 41.5 630.2 over different time steps. The maps orz900d and maze-32-32-2 are not shown in the results because of different reasons. orz900d does not appear since it is a very large map (|ํ|=96,603) and when running it in PPfPP in our implementation it generates an out of memory exception on the node for many problems. maze-32-32-2 does not appear since no instance of it was solved by fPP when using ํ> 0. Table 1 shows the results of the experiment for two interesting maps brc202d, random-64-64-20 and the mean over all maps. The table contains results for both MAPF algorithms PIBT and LaCAM โ together since there were similar trends for each of them separately. A table like this is shown in the supplementary material for the rest of the maps. In almost allํvalue for each map, the RSoC improvement is statistically significant. In some cases, such as in ํ=9 in both maps, the maximal RSoC improvement was very 02040 # Solved Instances 0 20000 40000 60000 80000 100000 RSoC (a)ํํํ202ํ 2.55.07.510.012.515.0 # Solved Instances 0 1000 2000 3000 4000 5000 6000 7000 RSoC (b)ํํํงํ โ 32โ 32โ 2 01020304050 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (c) ํํํํํํโ 64โ 64โ 20 0102030405060 # Solved Instances 2000 4000 6000 8000 10000 RSoC (d)ํคํํํโํํขํ ํโ20โ40โ10โ2โ2 LaCAM* k 1LaCAM* k 2LaCAM* k 3PIBT k 1PIBT k 2PIBT k 3 Figure 2: Cactus chart of ํ ํํํถ for each configuration of ํ in each sub-solver(ํฟํํถํดํ/ํํผํตํ) over # of solved instances. 010203040 # Solved Instances 0 20000 40000 60000 80000 100000 RSoC (a)ํํํ202ํ 010203040 # Solved Instances 0 1000 2000 3000 4000 5000 6000 7000 RSoC (b)ํํํงํ โ 32โ 32โ 2 010203040 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (c) ํํํํํํโ 64โ 64โ 20 010203040 # Solved Instances 2000 4000 6000 8000 10000 RSoC (d)ํคํํํโํํขํ ํโ20โ40โ10โ2โ2 LaCAM* r 0LaCAM* r 1LaCAM* r 2LaCAM* r 3PIBT r 0PIBT r 1PIBT r 2PIBT r 3 Figure 3: Cactus chart of ํ ํํํถ for each configuration of ํนํํ in each sub-solver(ํฟํํถํดํ/ํํผํตํ) over # of solved instances. high (22.83% for brc202d and 18.32% for random-64-64-20). As theํ value grows, the mean improvement grows as well, as can be seen in both maps, and in the mean of all maps, notice that the median value also grows with k, although it is very small. This consists with our hypothesis where largerํvalues will result in larger RSoC improvement. The runtime of PPfPP depends directly on the map size, where larger maps take longer to generate the ES. This can be seen for example in map brc202d where|ํ|=43,151, the runtime is extremely high, in comparison to map random-64-64-20 where |ํ|=3,270, and the runtime there is below one second for all k values. The runtime also depends on the makespan of the original plan generated by fPP, where the higher the makespan, the higher the runtime of PPfPP. This is because we need to calculate ES for each time step in the original plan, and go over all of the vertices. It can be seen in both maps and in the mean over all maps. 7 RELATED WORK In the field of Collaborative Privacy Preserving Planning (cppp) there has been a lot of work regarding privacy in multi-agent plan- ning scenarios [2,11โ14,16]. It is a similar field, but privacy preserv- ing MAPF is a special case of the cppp general field. It is important to study privacy in MAPF as well, since it allows us to handle the MAPF case with better suited algorithms than the general purpose algorithms used in cppp. In the cppp field the privacy is measured by not disclosing the variables and actions of the world of each agent to the other agents (or disclose part of them keeping the other part private) - in privacy preserving MAPFโ which we properly define in this paper for the first time, the actions are known to all agents (move to any neighbor or stay in place). However, the vertices that each agent is in at any given time is a private knowledge that needs to be kept from other agents while not conflicting with other agents in the same time - which is a hard task to achieve. Brafman [2] suggests a strong type of privacy where a value of a variable is strongly private if the other agents cannot deduce its existence from the information available to them. In this paper we suggest a privacy preserving MAPF problem where we do not seek a form of fully strong privacy on the path of each agent, but we seek that the other agents cannot deduce the location of the agent in a specific time step exactly but from within a minimum of k possible values. Another well-studied privacy preserving field is the privacy preserving distributed constraint optimization problem (DCOP) [4,6,7,10], where the goal is to solve distributed combinatorial problems in which the variables of the problem are owned by differ- ent agents while keeping privacy over the constraints and variables of the different agents. In this paper, we focus on the privacy pre- serving MAPF problem we suggested, where, unlike privacy pre- serving DCOP, the goal is to plan paths for a set of agents, instead of optimizing some utility function. Privacy has rarely been mentioned in the context of MAPF. One exception is recent work on finding all optimal solutions in MAPF [1]. They state that finding all solutions can help keep privacy about the chosen paths. However, the privacy considered there is with respect to an external agent, and not of hiding the paths of agents from each other as we do in this work. 8 CONCLUSION AND FUTURE WORK This paper introduces a new field in MAPF where privacy is con- sidered. We defined two novel privacy preserving problems, the kPPMAPF which is a problem where agents must find paths that do not collide, without sharing their real path during planning, and the ekPPMAPF which is an extension of the kPPMAPF with the addition of also avoiding the paths of agents to be disclosed during the execution stage when there are limited sensors on the agents by keeping out of the field of view of other agents during planning. We also provide two novel algorithms to solve the new problems, kPP, which solves the kPPMAPF problem by introducing mock agents to confuse other agents during planning and the fPP, which extends the kPP in order to solve the ekPPMAPF problem by also adapting the sub-solver used to keep out of the field of view of agents in different groups. We also introduce the PPfPP algorithm, which improves the cost of plans generated for the ekPPMAPF problem by defining a concept of safe-zones where each agent group can walk freely in and re-plan for the single real agent inside of it. We also provide extensive theoretical and experimental eval- uation of our algorithms, showing they preserve k-privacy and Runtime k-privacy and that the PPfPP algorithm improves the cost of the ekPPMAPF plans resulted by fPP. In PPfPP, one can further research more complicated functions other than the random function suggested in algorithm 3, that follows the rules from definition 10, for improving the extension of safe zones, and maybe improve the ํ ํํํถ(ฮ ) even further. Another future research direction is to explore other sub-planners to use in the fPP algorithm, such as optimal MAPF planners, and see whether the PPfPP improves their cost significantly, and makes it closer to the optimal RSoC. In our work we used a vanilla version of PIBT which does not use the swap improvement introduced at [17]. A future research direction could be to support FoV in the swap operation of PIBT to improve the planning time of fPP while using LaCAM โ , and solving more instances while using PIBT. REFERENCES [1]Shahar Bardugo, Daniel Koyfman, and Dor Atzmon. 2025. Finding All Optimal So- lutions in Multi-Agent Path Finding. In International Symposium on Combinatorial Search. 20โ28. [2]Ronen I Brafman. 2015. A privacy preserving algorithm for multi-agent planning and search. In 24th International Joint Conference on Artificial Intelligence, IJCAI 2015. International Joint Conferences on Artificial Intelligence, 1530โ1536. [3]Stepan Dergachev and Konstantin Yakovlev. 2021. Distributed multi-agent naviga- tion based on reciprocal collision avoidance and locally confined multi-agent path finding. In IEEE International Conference on Automation Science and Engineering (CASE). 1489โ1494. [4]Boi Faltings, Thomas Lรฉautรฉ, and Adrian Petcu. 2008. Privacy guarantees through distributed constraint satisfaction. In 2008 IEEE/WIC/ACM International Confer- ence on Web Intelligence and Intelligent Agent Technology, Vol. 2. IEEE, 350โ358. [5]Ariel Felner, Roni Stern, Solomon Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan Sturtevant, Glenn Wagner, and Pavel Surynek. 2017. Search- based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In International Symposium on Combinatorial Search, Vol. 8. 29โ37. [6]Rachel Greenstadt, Barbara Grosz, and Michael D Smith. 2007. SSDPOP: improv- ing the privacy of DCOP with secret sharing. In International joint conference on Autonomous agents and multiagent systems (AAMAS). 1โ3. [7] Tal Grinshpoun and Tamir Tassa. 2016. P-SyncBB: A privacy preserving branch and bound DCOP algorithm. Journal of Artificial Intelligence Research 57 (2016), 621โ660. [8]Florence Ho, Rรบben Geraldes, Artur Gonรงalves, Bastien Rigault, Benjamin Sportich, Daisuke Kubo, Marc Cavazza, and Helmut Prendinger. 2020. Decentral- ized multi-agent path finding for UAV traffic management. IEEE Transactions on Intelligent Transportation Systems 23, 2 (2020), 997โ1008. [9]M Onur Keskin, Furkan Cantรผrk, Cihan Eran, and Reyhan Aydoฤan. 2024. Decen- tralized multi-agent path finding framework and strategies based on automated negotiation. Autonomous Agents and Multi-Agent Systems 38, 1 (2024), 10. [10]Pablo Kogan, Tamir Tassa, and Tal Grinshpoun. 2022. Privacy preserving DCOP solving by mediation. In International Symposium on Cyber Security, Cryptology, and Machine Learning. Springer, 487โ498. [11]Rotem Lev Lehman, Guy Shani, and Roni Stern. 2021. Partial disclosure of private dependencies in privacy preserving planning. In 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021. International Founda- tion for Autonomous Agents and Multiagent Systems (IFAAMAS), 1563โ1565. [12]Rotem Lev Lehman, Guy Shani, and Roni Stern. 2022. Reducing disclosed de- pendencies in privacy preserving planning. Autonomous Agents and Multi-Agent Systems 36, 2 (2022), 52. [13]Shlomi Maliah, Guy Shani, and Roni Stern. 2016. Stronger privacy preserving projections for multi-agent planning. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 26. 221โ229. [14] Shlomi Maliah, Guy Shani, and Roni Stern. 2017. Collaborative privacy preserving multi-agent planning: Planners and heuristics. Autonomous agents and multi- agent systems 31, 3 (2017), 493โ530. [15]Bernhard Nebel. 2024. The computational complexity of multi-agent pathfinding on directed graphs. Artificial Intelligence 328 (2024). [16]Raz Nissim and Ronen Brafman. 2014. Distributed heuristic forward search for multi-agent planning. Journal of Artificial Intelligence Research 51 (2014), 293โ332. [17] Keisuke Okumura. 2023. Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI). [18]Keisuke Okumura. 2023. LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI). [19]Keisuke Okumura. 2024. Engineering LaCAM โ : Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding. In Proceedings of International Con- ference on Autonomous Agents and Multiagent Systems (AAMAS). [20]Keisuke Okumura, Manao Machida, Xavier Dรฉfago, and Yasumasa Tamura. 2022. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. Artificial Intelligence (2022), 103752. https://doi.org/10.1016/j.artint.2022.103752 [21]Mike Phillips and Maxim Likhachev. 2011. Sipp: Safe interval path planning for dynamic environments. In 2011 IEEE international conference on robotics and automation. IEEE, 5628โ5635. [22] Poom Pianpak, Tran Cao Son, Phoebe O Toups Dugas, and William Yeoh. 2019. A distributed solver for multi-agent path finding problems. In International Con- ference on Distributed Artificial Intelligence (DAI). 1โ7. [23]Guni Sharon, Roni Stern, Ariel Felner, and Nathan R Sturtevant. 2015. Conflict- based search for optimal multi-agent pathfinding. Artificial intelligence 219 (2015), 40โ66. [24] Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, et al.2019. Multi- agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search. 151โ158. [25]Pavel Surynek. 2010. An Optimization Variant of Multi-Robot Path Planning Is Intractable. In AAAI. [26]Pavel Surynek. 2022. Problem Compilation for Multi-Agent Path Finding: a Survey.. In IJCAI. 5615โ5622. [27] Prasanna Velagapudi, Katia Sycara, and Paul Scerri. 2010. Decentralized priori- tized planning in large multirobot teams. In IEEE/RSJ International Conference on Intelligent Robots and Systems. 4603โ4609. [28]Hanlin Wang and Michael Rubenstein. 2020. Walk, stop, count, and swap: decen- tralized multi-agent path finding with theoretical guarantees. IEEE Robotics and Automation Letters 5, 2 (2020), 1119โ1126. [29]M. Yokoo, E.H. Durfee, T. Ishida, and K. Kuwabara. 1998. The distributed constraint satisfaction problem: formalization and algorithms. IEEE Trans- actions on Knowledge and Data Engineering 10, 5 (1998), 673โ685.https: //doi.org/10.1109/69.729707 [30]Makoto Yokoo, Koutarou Suzuki, and Katsutoshi Hirayama. 2002. Secure dis- tributed constraint satisfaction: Reaching agreement without revealing private information. In International Conference on Principles and Practice of Constraint Programming. Springer, 387โ401. [31]Jingjin Yu and Steven M. LaValle. 2013. Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs. In AAAI. Privacy Preserving Multi Agent Path Finding - Supplementary Material Rotem Lev Lehman Ben Gurion University of the Negev Beโer Sheva, Israel levlerot@post.bgu.ac.il Roni Stern Ben Gurion University of the Negev Beโer Sheva, Israel sternron@bgu.ac.il Guy Shani Ben Gurion University of the Negev Beโer Sheva, Israel shanigu@bgu.ac.il ACM Reference Format: Rotem Lev Lehman, Roni Stern, and Guy Shani. 2026. Privacy Preserving Multi Agent Path Finding - Supplementary Material. In Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), Paphos, Cyprus, May 25 โ 29, 2026, IFAAMAS, 6 pages. https: //doi.org/10.65109/ 1 THEOREMS AND PROOFS FOR PPFPP Definition 1 (Initial Safe-Zone). The initial safe-zone of an agent groupํ ํ in a specific timestepํกon a given planฮ that was generated from running fPP on an ekPPMAPF problem P, denoted ํผํ ํก ํ (ฮ ), is the setํฃ|ํน ํ (ํฃ) โ ํนํํ ํก ํ (ฮ ). Definition 2 (Agent Groupโs FoV). An agent groupํ ํ โs FoV in timestepํกon a given planฮ generated by fPP on an ekPPMAPF problem P, denoted ํนํํ ํก ํ (ฮ ), is the setํฃ|โํ ํ ํ ํฃ โ ํน ํ (ฮ ํ (ํก)). Definition 3 (Runtime k-Privacy). A MAPF solutionฮ pre- serves Runtime k-Privacy if the belief state generated from findingฮ preserves k-Privacy and there are no ํนํํ conflicts inฮ . Definition 4 (Separated Safe Zones). A set of safe-zonesํ(ฮ )= ํ ํ (ฮ )|โํ โ ํด , is called separated, if and only if: โํกโํ โ ํดโํฃ โ ํ ํก ํ (ฮ )โํโ ํยํข โ ํ ํก ํ (ฮ ) : ํข โ ํน ํ (ํฃ)||ํฃ โ ํน ํ (ํข). Definition 5 (Rules for Extending Safe Zone). The function ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )is a function thatํ ํ uses for extending the safe zoneํธํ ํก ํ . It must pick one vertexํฃto add toํธํ ํก ํ . It returnsํํ ํํธ if foundํฃthat was added toํธํ ํก ํ ,ํนํดํฟํํธotherwise, and it must follow the following rules: (1) ํฃ is a neighbor of someํข โ ํธํ ํก ํ . (2) โํ ํ ,ํฃโ ํธํ ํก ํ . (3) โํ ํ โ ํ ํ ,ยํข โ ํธํ ํก ํ : ํข โ ํน ํ (ํฃ)โฅํฃ โ ํน ํ (ํข). (4) Using it must preserve the runtime k-Privacy ofํ,ฮ after running it. Theorem 1 (Initial safe-Zone Safeness). An initial safe-zone ํผํ(ฮ )calculated from definition 1, whenโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ) & ํน ํ is symmetric, is safe. Proof.Given an ekPPMAPF problem P, a valid planฮ that solves P, and was returned by using fPP on P, an initial safe- zoneํผํ(ฮ )calculated from definition 1, andโํ ํ ,ํ ํ โ ํดโํฃ โ ํ :ํน ํ (ํฃ)= ํน ํ (ํฃ)&ํน ํ is symmetric. Letํ ํ ,ํ ํ โ ํด|ํ ํ โ ํ ํ ,ํก โ ํ. Also, letํฃ โ ํผํ ํก ํ (ฮ ). Assume negatively thatโํข โ ํผํ ํก ํ : ํข โ ํน ํ (ํฃ)โฅํฃ โ ํน ํ (ํข) , without loss of generality, assumeํข โ ํน ํ (ํฃ). Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), C. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.), May 25 โ 29, 2026, Paphos, Cyprus.ยฉ 2026 International Foundation for Autonomous Agents and Multiagent Systems (w.ifaamas.org). https://doi.org/10.65109/ From definition 1,ํข โ ํนํํ ํก ํ (ฮ ), hence from definition 2,โํ ํ ํ : ํข โ ํน ํ (ฮ ํ (ํก)), because thatํน ํ is symmetric,โฮ ํ (ํก) โ ํน ํ (ํข)and becauseํน ํ = ํน ํ โฮ ํ (ํก) โ ํน ํ (ํข). Because ofํข โ ํผํ ํก ํ (ฮ ), then ํน ํ (ํข) โ ํนํํ ํก ํ (ฮ ) โฮ ํ (ํก) โ ํนํํ ํก ํ (ฮ ), and so from definition 2, โํ ํ ํ :ฮ ํ (ํก) โ ํน ํ (ฮ ํ (ํก)). Butํ ํ ํ andํ ํ ํ are of different agent groups, and so this is a FoV conflictโfrom definition 3,ฮ does ํํํกpreserve Runtime k-Privacy, and soฮ is not a valid ekPPMAPF plan, in contradiction to the assumption thatฮ is a valid plan that solves P.โยํข โ ํผํ ํก ํ : ํข โ ํน ํ (ํฃ)โฅํฃ โ ํน ํ (ํข) โfrom definition 4 ํผํ(ฮ ) is considered safe.โก Theorem 2 (Extended Safe-Zone Safeness). An extended safe- zoneํธํ(ฮ )calculated from runningํธํฅํกํํํํํํํํํํํin line 8 in algorithm 1 onํผํcalculated from definition 1, when the function ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )from line 14 follows the rules from defini- tion 5, whenโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)&ํน ํ is symmetric, is safe. Proof.Given an ekPPMAPF problem P, a valid planฮ that solves P, and was returned by using fPP on P, an extended safe- zoneํธํ(ฮ )calculated from runningํธํฅํกํํํํํํํํํํํ, where the functionํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )from line 14 follows the rules from definition 5, andโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)& ํน ํ is symmetric. Letํ ํ ,ํ ํ โ ํด|ํ ํ โ ํ ํ ,ํก โ ํ. Also, letํฃ โ ํธํ ํก ํ (ฮ ),ํข โ ํธํ ํก ํ (ฮ ). There are four possible cases: Algorithm 1: Post-Processing (fPP) Solutions (PPfPP) 1 Input:ฮ : An ekPPMAPF solution 2 Output:ฮ โฒ refined for all agent groups 3 Function PPfPP: 4 ํผํ(ฮ ) โ initial safe zone as defined in definition 1 ; 5 ํธํ(ฮ ) โ ํธํฅํกํํํํํํํํํํํ(ํผํ(ฮ )) ; 6 foreach ํ ํ โ ํด do 7ํ ํ .ํนํํํํํํกโํนํํํ ํํํํดํํํํก(ํธํ ํ (ฮ )) ; 8 Function ExtendSafeZone(IS): 9ESโ IS ; 10 foreach ํก โ ํ do 11do 12ํํํํ โ ํํ ํํธ; 13foreach ํ ํ โ ํด do 14ํํํํํํ โ ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก ) ; 15ํํํํ โ ํํํํโงยฌํํํํํํ ; 16whileยฌํํํํ; 17 return ES ; โข ํฃ โ ํผํ ํก ํ (ฮ )&ํข โ ํผํ ํก ํ (ฮ ): From theorem 1 and definition 4, ํขโ ํน ํ (ํฃ) & ํฃโ ํน ํ (ํข). โข ํฃ โ ํผํ ํก ํ (ฮ )&ํขโ ํผํ ํก ํ (ฮ ): So in line 14 in algorithm 1, there was some iteration whereํขwas added toํธํ ํก ํ . In this iteration we calledํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )whereํผํ ํก ํ โ ํธํ ํก ํ , since it was set at line 9 to be ํผํ ํก ํ , andํขโ ํธํ ํก ํ since it was added in this iteration toํธํ ํก ํ . From definition 5, rule number 3 we can conclude thatํขโ ํน ํ (ํฃ) & ํฃโ ํน ํ (ํข). โข ํฃโ ํผํ ํก ํ (ฮ ) & ํข โ ํผํ ํก ํ (ฮ ): Same as the previous case. โข ํฃโ ํผํ ํก ํ (ฮ ) &ํขโ ํผํ ํก ํ (ฮ ): So, without loss of generality, there was an iteration in line 14 in algorithm 1, whereํฃwas added toํธํ ํก ํ , andํขwas not yet added toํธํ ํก ํ . This iteration is the same as the previous case, and soํขโ ํน ํ (ํฃ)&ํฃโ ํน ํ (ํข). As you can see, in all casesํขโ ํน ํ (ํฃ)&ํฃโ ํน ํ (ํข) โfrom definition 4 ํธํ(ฮ ) is considered safe.โก Theorem 3 (PPfPP Solves ekPPMAPF Problems). Ifํธํwas calculated using aํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก ) function that follows the rules from definition 5, andโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)& ํน ํ is symmetric&โํข โ ํฃ.ํํํํโํํํํ :ํข โ ํน ํ (ํฃ), then PPfPP returns valid ekPPMAPF plans. Proof.Given thatํธํin algorithm 1 is calculated using a ํ ํ .ํธํฅํกํํํํํํํํํํํ(ํธํ ํก )function that follows the rules from definition 5, andโํ ํ ,ํ ํ โ ํดโํฃ โ ํ:ํน ํ (ํฃ)= ํน ํ (ํฃ)& ํน ํ is symmetric&โํข โ ํฃ.ํํํํโํํํํ :ํข โ ํน ํ (ํฃ). Also given an ekPPMAPF problem P, a planฮ originated from running the fPP algorithm, and a planฮ โฒ that returned from running PPfPP onฮ . From theorem 2 we can conclude thatํธํ(ฮ )is safe. So โํ ํ โ ํด, if we find a plan forํ ํ .ํํํํ _ํํํํํกthat stays only in the safe-zoneํธํ ํ , it will not conflict with any otherํ ํ โ ํ ํ in the FoV. Also, there will be noํฃํํํกํํฅconflicts, because of rule number 2 in definition 5. Letํ ํ ,ํ ํ โ ํด:ํ ํ โ ํ ํ assume nega- tively thatโํก โ ํ: there is a swapping conflict betweenํ ํ and ํ ํ inฮ โฒ on time stepsํก โ1,ํก. Letํฃbe the vertexํ ํ is at time ํก โ1 onฮ โฒ andํขbe the vertexํ ํ is at timeํก โ1 onํํ โฒ . From the assumptions (โํ ํ โ ํดโํฃ โ ํโํข โ ํฃ.ํํํํโํํํํ :ํข โ ํน ํ (ํฃ)), โ ํข โ ํน ํ (ํฃ)&ํฃ โ ํน ํ (ํข) โin timeํก โ1 there is aํนํํconflict - but we proved (in this proof ) that there are noํนํํconflicts, so there is a contradiction,โยํก โ ํ: there is a swapping conflict be- tweenํ ํ andํ ํ inฮ โฒ on time stepsํกโ1,ํก โthere are noํ ํคํํํํํ conflicts in the resulting planฮ โฒ . Soฮ โฒ is a valid plan for P.โก 2 EXPERIMENTAL RESULTS In this section we show all experimental results not shown in the main paper. Trends are the same as in the main paper and so are not discussed here. 02040 # Solved Instances 0 20000 40000 60000 80000 100000 RSoC (a)ํํํ202ํ 01020304050 # Solved Instances 0 5000 10000 15000 20000 25000 30000 RSoC (b) ํํก_ํํํํํคํ ํกํํํํํํ_ํ 2.55.07.510.012.515.0 # Solved Instances 0 1000 2000 3000 4000 5000 6000 7000 RSoC (c)ํํํงํ โ 32โ 32โ 2 02040 # Solved Instances 25000 50000 75000 100000 125000 150000 175000 RSoC (d) ํํํง900ํ 01020304050 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (e) ํํ ํก003ํ 010203040 # Solved Instances 0 2000 4000 6000 8000 10000 RSoC (f) ํํํํํํโ 32โ 32โ 20 01020304050 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (g) ํํํํํํโ 64โ 64โ 20 0510152025 # Solved Instances 0 1000 2000 3000 4000 RSoC (h) ํํํโ 32โ 32โ 4 010203040 # Solved Instances 0 2000 4000 6000 8000 10000 12000 RSoC (i) ํํํโ 64โ 64โ 8 01020304050 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (j) ํํํโ 64โ 64โ 16 0102030405060 # Solved Instances 2000 4000 6000 8000 10000 RSoC (k)ํคํํํโํํขํ ํโ20โ40โ10โ 2โ 1 0102030405060 # Solved Instances 2000 4000 6000 8000 10000 RSoC (l)ํคํํํโํํขํ ํโ20โ40โ10โ 2โ 2 LaCAM* k 1LaCAM* k 2LaCAM* k 3PIBT k 1PIBT k 2PIBT k 3 Figure 1: Cactus chart of ํ ํํํถ for each configuration of ํ in each sub-solver(ํฟํํถํดํ/ํํผํตํ) over # of solved instances. 010203040 # Solved Instances 0 20000 40000 60000 80000 100000 RSoC (a)ํํํ202ํ 010203040 # Solved Instances 0 5000 10000 15000 20000 25000 30000 RSoC (b) ํํก_ํํํํํคํ ํกํํํํํํ_ํ 010203040 # Solved Instances 0 1000 2000 3000 4000 5000 6000 7000 RSoC (c)ํํํงํ โ 32โ 32โ 2 010203040 # Solved Instances 25000 50000 75000 100000 125000 150000 175000 RSoC (d) ํํํง900ํ 010203040 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (e) ํํ ํก003ํ 010203040 # Solved Instances 0 2000 4000 6000 8000 10000 RSoC (f) ํํํํํํโ 32โ 32โ 20 010203040 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (g) ํํํํํํโ 64โ 64โ 20 010203040 # Solved Instances 0 1000 2000 3000 4000 RSoC (h) ํํํโ 32โ 32โ 4 010203040 # Solved Instances 0 2000 4000 6000 8000 10000 12000 RSoC (i) ํํํโ 64โ 64โ 8 010203040 # Solved Instances 0 2500 5000 7500 10000 12500 15000 RSoC (j) ํํํโ 64โ 64โ 16 010203040 # Solved Instances 2000 4000 6000 8000 10000 RSoC (k)ํคํํํโํํขํ ํโ20โ40โ10โ 2โ 1 010203040 # Solved Instances 2000 4000 6000 8000 10000 RSoC (l)ํคํํํโํํขํ ํโ20โ40โ10โ 2โ 2 LaCAM* r 0LaCAM* r 1LaCAM* r 2LaCAM* r 3PIBT r 0PIBT r 1PIBT r 2PIBT r 3 Figure 2: Cactus chart of ํ ํํํถ for each configuration of ํนํํ in each sub-solver(ํฟํํถํดํ/ํํผํตํ) over # of solved instances. Table 1: Average RSoC improvement% ํ ํํํถ(ํ ํ)โํ ํํํถ(ํํ ํ) ํ ํํํถ(ํ ํ) โ100% (meanยฑstd, max and median (med)) of PPfPP over fPP, across domains with different k values. #S is the amount of solved instances by fPP (all instances also were also solved by PPfPP). * and ** marks significant improvement of PPfPP over fPP (Wilcoxon, p<0.05 and p<0.01 accordingly). fPP MS is the makespan of the original plan created by fPP. Each map shows the amount of vertices in it(|ํ|). This table contains part of the maps we ran on, and the other part is in the second table 2 which also contains the mean over all maps. Mapkํ ํํํถ ํผํํํํํฃํํํํํก%#Stime fPP meanยฑ stdmaxmed[s]MS brc202d |ํ|= 43,151 2 0.77ยฑ 2.47 โ 11.50 0.02 56 113.6 943.9 3 0.64ยฑ 1.65 โ 7.25 0.02 55 116.0 975.4 4 1.04ยฑ 2.69 โ 11.30 0.02 47 121.2 1022.4 5 1.06ยฑ 2.66 โ 11.27 0.00 40 125.3 1041.3 6 1.20ยฑ 2.68 โ 10.72 0.02 39 124.0 1040.9 7 1.80ยฑ 3.90 โ 12.90 0.03 42 131.0 1094.5 8 2.04ยฑ 4.45 โ 16.91 0.07 30 137.6 1170.1 9 3.21ยฑ 6.40 โ 22.83 0.11 25 143.4 1203.6 10 1.01ยฑ 2.69 โ 13.21 0.07 25 143.8 1312.6 lt_gallowstemplar_n |ํ|= 10,021 2 0.64ยฑ 1.66 โ 8.23 0.00 59 3.2245.2 3 0.88ยฑ 1.77 โ 8.02 0.14 50 3.2270.3 4 0.24ยฑ 0.84 โ 5.60 0.07 45 3.3284.4 5 0.87ยฑ 1.65 โ 5.14 0.14 34 3.7316.6 6 0.74ยฑ 1.75 โ 7.20 0.15 24 3.9348.0 7 0.70ยฑ 2.51 โ 12.87 0.09 26 3.8342.4 8 0.89ยฑ 2.06 โ 9.54 0.26 21 4.8421.0 9 2.06ยฑ 3.43 โ 10.30 0.36 12 5.0418.8 10 0.45ยฑ 1.13 โ 4.03 0.15 12 5.9508.2 ost003d |ํ|= 13,214 2 0.59ยฑ 1.84 โ 8.83 0.00 52 7.2346.6 3 1.19ยฑ 3.14 โ 13.15 0.05 49 7.0363.9 4 0.68ยฑ 1.88 โ 9.27 0.04 40 6.9375.8 5 1.22ยฑ 2.86 โ 10.38 0.06 30 7.9410.8 6 2.13ยฑ 4.02 โ 17.06 0.15 30 7.5401.2 7 1.29ยฑ 2.45 โ 6.89 0.13 18 7.8427.9 8 2.20ยฑ 4.54 โ 16.25 0.15 14 9.7518.4 9 2.49ยฑ 3.75 โ 10.33 0.20 14 9.0461.8 10 0.10ยฑ 0.06 โ 0.17 0.11 8 12.9 665.5 random-32-32-20 |ํ|= 819 2 0.64ยฑ 1.38 โ 4.83 0.00 43 0.048.3 3 2.14ยฑ 3.51 โ 10.66 0.41 30 0.161.5 4 0.78ยฑ 0.84 โ 3.33 0.50 19 0.1108.5 5 1.73ยฑ 2.66 โ 8.38 0.41 11 0.1192.6 6 0.14ยฑ 0.13 0.25 0.16 4 0.2286.5 random-64-64-20 |ํ|= 3,270 2 0.20ยฑ 1.05 โ 7.75 0.00 56 0.390.5 3 0.62ยฑ 1.89 โ 10.34 0.00 48 0.396.7 4 0.73ยฑ 1.84 โ 7.65 0.00 38 0.3100.3 5 1.33ยฑ 2.60 โ 10.00 0.23 29 0.4106.8 6 1.04ยฑ 2.30 โ 8.33 0.20 21 0.4120.4 7 0.70ยฑ 1.24 โ 4.85 0.19 19 0.4146.4 8 0.93ยฑ 1.88 โ 5.72 0.23 15 0.5151.8 9 2.97ยฑ 5.36 โ 18.32 0.16 12 0.7244.6 10 0.86ยฑ 1.55 โ 3.64 0.16 5 0.9294.6 room-32-32-4 |ํ|= 682 2 1.17ยฑ 1.61 โ 4.32 0.29 28 0.065.2 3 0.93ยฑ 2.08 โ 6.84 0.32 10 0.1123.9 Table 2: Average RSoC improvement% ํ ํํํถ(ํ ํ)โํ ํํํถ(ํํ ํ) ํ ํํํถ(ํ ํ) โ100% (meanยฑstd, max and median (med)) of PPfPP over fPP, across domains with different k values. #S is the amount of solved instances by fPP (all instances also were also solved by PPfPP). * and ** marks significant improvement of PPfPP over fPP (Wilcoxon, p<0.05 and p<0.01 accordingly). fPP MS is the makespan of the original plan created by fPP. Each map shows the amount of vertices in it(|ํ|). This is a complementary table for the rest of the maps not shown in table 1 including the mean over all maps. Mapkํ ํํํถ ํผํํํํํฃํํํํํก%#Stime fPP meanยฑ stdmaxmed[s]MS room-64-64-16 |ํ|= 3,646 2 0.95ยฑ 2.47 โ 11.21 0.00 56 0.6 164.0 3 1.06ยฑ 3.73 โ 25.74 0.14 50 0.5 172.4 4 0.50ยฑ 0.98 โ 3.51 0.11 36 0.6 180.5 5 1.80ยฑ 3.98 โ 19.11 0.19 27 0.7 196.7 6 1.13ยฑ 2.45 โ 11.09 0.11 22 0.8 242.2 7 2.76ยฑ 5.64 โ 18.33 0.24 12 0.9 258.7 8 2.02ยฑ 3.53 โ 9.80 0.33 11 0.8 239.5 9 0.08ยฑ 0.11 0.15 0.08 21.1 300.5 10 0.11ยฑ 0.08 0.21 0.10 42.2 635.5 room-64-64-8 |ํ|= 3,232 2 0.32ยฑ 1.11 โ 6.93 0.00 51 0.3 125.6 3 0.13ยฑ 0.14 โ 0.38 0.11 34 0.4 144.9 4 0.56ยฑ 1.68 โ 8.02 0.17 22 0.5 182.4 5 0.66ยฑ 1.29 โ 3.94 0.13 16 0.6 241.9 6 0.19ยฑ 0.19 โ 0.45 0.06 50.8 350.2 7 0.11ยฑํํํ0.11 0.11 10.5 197.0 warehouse-20-40-10-2-1 |ํ|= 22,599 2 0.00ยฑ 0.01 โ 0.08 0.00 59 11.5 341.2 3 0.00ยฑ 0.01 0.05 0.00 59 11.1 348.7 4 0.00ยฑ 0.02 โ 0.08 0.00 56 11.2 361.3 5 0.26ยฑ 1.25 โ 9.03 0.00 57 11.4 367.8 6 0.34ยฑ 1.17 โ 4.91 0.00 55 11.5 374.7 7 0.67ยฑ 2.16 โ 10.98 0.00 50 11.9 386.5 8 0.27ยฑ 1.06 โ 4.99 0.00 50 11.9 384.4 9 0.99ยฑ 2.39 โ 9.29 0.00 49 12.7 408.0 10 0.95ยฑ 2.14 โ 9.29 0.00 50 12.4 404.5 warehouse-20-40-10-2-2 |ํ|= 38,756 2 0.05ยฑ 0.22 โ 1.07 0.00 58 41.7 377.2 3 0.04ยฑ 0.17 โ 1.11 0.00 55 40.3 389.1 4 0.32ยฑ 1.27 โ 6.97 0.00 57 36.2 392.9 5 0.63ยฑ 1.75 โ 8.65 0.00 45 34.6 397.6 6 0.19ยฑ 0.60 โ 2.65 0.00 44 35.1 406.7 7 0.35ยฑ 1.46 โ 8.31 0.00 34 37.2 428.3 8 0.75ยฑ 1.73 โ 7.41 0.00 35 39.7 455.7 9 0.16ยฑ 0.65 โ 3.11 0.00 23 38.3 437.3 10 0.02ยฑ 0.03 โ 0.12 0.00 15 35.9 434.6 Mean 2 0.50ยฑ 1.61 โ 11.50 0.00 518 19.5 293.3 3 0.68ยฑ 2.22 โ 25.74 0.00 440 22.3 336.9 4 0.49ยฑ 1.55 โ 11.30 0.00 360 24.6 374.7 5 0.93ยฑ 2.35 โ 19.11 0.02 289 26.4 408.3 6 0.83ยฑ 2.25 โ 17.06 0.00 244 30.2 451.8 7 1.04ยฑ 2.86 โ 18.33 0.03 202 37.7 507.6 8 1.06ยฑ 2.78 โ 16.91 0.04 176 36.2 518.6 9 1.66ยฑ 3.90 โ 22.83 0.05 137 38.6 548.7 10 0.71ยฑ 1.93 โ 13.21 0.05 119 41.5 630.2