# prioritised_planning_completeness_optimality_and_complexity__6edb012b.pdf Prioritised Planning: Completeness, Optimality, and Complexity JONATHAN MORAG , Ben-Gurion University of the Negev, Israel YUE ZHANG, Monash University, Australia DANIEL KOYFMAN, Ben-Gurion University of the Negev, Israel ZHE CHEN, Monash University, Australia ARIEL FELNER, Ben-Gurion University of the Negev, Israel DANIEL HARABOR, Monash University, Australia RONI STERN, Ben-Gurion University of the Negev, Israel Prioritised Planning (PP) is a popular approach for multi-agent and multi-robot navigation. In PP, collision-free paths are computed for one agent at a time, following a total order over the agents, called a priority ordering. Many MAPF algorithms follow this approach or use it in some way, including several state-of-the-art MAPF algorithms, although it is known that PP is neither complete nor optimal. In this work, we characterise the space of problems a PP algorithm can solve, and define the search problem of identifying whether a given MAPF problem is in that space. We call this search problem Prioritised MAPF (P-MAPF) and investigate its computational complexity, showing that it is generally NP-hard. Then, we develop a novel efficient search algorithm called Path and Priority Search (Pa PS), which solves P-MAPF, providing guarantees of completeness and optimality. We next observe that PP algorithms operate with two primary degrees of freedom the choice of priority ordering, and the choice of individual paths for agents. Accordingly, we further divide P-MAPF into two planning problems corresponding to the two degrees of freedom. We call them Priority-Function Constrained MAPF (PFC-MAPF), where the path choice is fixed while the priority ordering is not, and Priority Constrained MAPF (PC-MAPF), where the priority ordering is fixed while the path choice is not. We analyse these problems as well, and show how Pa PS can be easily adapted to create algorithms that solve these problems optimally. We experiment with our algorithms in a range of settings, including comparisons with existing PP baselines. Our results show how the different degrees of freedom of PP-based algorithms affect their behaviour, and provide the first-known results for solution-quality optimality for PP-based algorithms on a popular MAPF benchmark set. The latter can be used as a lower bound for any PP algorithm. JAIR Track: Multi-Agent Path Finding JAIR Associate Editor: Erez Karpas JAIR Reference Format: Jonathan Morag, Yue Zhang, Daniel Koyfman, Zhe Chen, Ariel Felner, Daniel Harabor, and Roni Stern. 2025. Prioritised Planning: Completeness, Optimality, and Complexity. Journal of Artificial Intelligence Research 84, Article 21 (November 2025), 47 pages. doi: 10.1613/jair.1.19358 Corresponding Author. Authors Contact Information: Jonathan Morag, orcid: 0000-0002-3778-0018, moragj@post.bgu.ac.il, Ben-Gurion University of the Negev, Beer Sheva, Israel; Yue Zhang, orcid: 0009-0004-6091-7213, Yue.Zhang@monash.edu, Monash University, Melbourne , Australia; Daniel Koyfman, orcid: 0009-0004-6137-8602, koyfdan@post.bgu.ac.il, Ben-Gurion University of the Negev, Beer-Sheva, Israel; Zhe Chen, orcid: 0000-00020425-3131, zhe.chen@monash.edu, Monash University, Melbourne , Australia; Ariel Felner, orcid: 0000-0003-0065-2757, felner@bgu.ac.il, Ben-Gurion University of the Negev, Beer-Sheva, Israel; Daniel Harabor, orcid: 0000-0001-6828-7712, Daniel.Harabor@monash.edu, Monash University, Melbourne , Australia; Roni Stern, orcid: 0000-0003-0043-8179, roni.stern@gmail.com, Ben-Gurion University of the Negev, Beer-Sheva, Israel. This work is licensed under a Creative Commons Attribution International 4.0 License. 2025 Copyright held by the owner/author(s). doi: 10.1613/jair.1.19358 Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:2 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 1 Introduction Multi-Agent Path Finding (MAPF) is the problem of planning the movement of multiple agents in a shared environment, such that they do not collide with static obstacles in the environment and with each other (Stern et al. 2019). This problem manifests in applications such as automated warehouses (Li, Tinka, et al. 2021; Ma, Li, et al. 2017; Morag, Stern, et al. 2023; Varambally et al. 2022). Solving MAPF is NP-hard (Nebel 2020) for directed graphs and can be done in polynomial time in the special case of MAPF on undirected graphs (Daniel Kornhauser 1984). The problem graph is typically unweighted. In general, it is preferred that agents reach their targets as quickly as possible. Accordingly, the quality of a solution is usually measured by considering the sum of the lengths of all paths, known as the Sum-of-Costs (SOC). Finding solutions to MAPF problems with optimal (lowest) SOC is also NP-hard, even on undirected graphs (Yu and La Valle 2013). Academics and practitioners alike have been seeking ways to mitigate the computational complexity of MAPF. One commonly used approach to do so is Prioritised Planning (PP) (Erdmann and Lozano-PΓ©rez 1986). In PP for MAPF, paths are found for each agent, one at a time, following a given priority order P = {π‘Ž1 π‘Ž2 . . . π‘Žπ‘˜}. When planning for an agent, we aim for it to reach its target as quickly as possible, while avoiding the paths previously planned for the higher-priority agents. Many MAPF algorithms follow this approach, including algorithms that are applied in Robotics and AI (Li, Chen, Harabor, P. Stuckey, et al. 2021; Li, Chen, Harabor, P. J. Stuckey, et al. 2022; Ma, Harabor, et al. 2019; Silver 2005; Van Den Berg and Overmars 2005). PP algorithms are usually fast and scalable (Li, Chen, Harabor, P. Stuckey, et al. 2021), since a path for each agent is only planned once, and the quality of the returned solution is often close to optimal (Ma, Harabor, et al. 2019). Nevertheless, PP algorithms have two main drawbacks: (i) they are incomplete, i.e., they may fail to find any solution to a MAPF problem instance that is solvable; and (ii) they are suboptimal, i.e., the solutions they return have no quality guarantees. This raises the question that is the focus of this work: how to characterise the problems that can be solved by a PP algorithm and the quality of the solutions that it can return. To characterise the space of problems that can be solved by a PP algorithm and the space of solutions they may return, we define a PP algorithm according to the following two key design choices in all PP algorithms: Choice of Priority Ordering. That is, the order of agents according to which a PP algorithm will plan paths. The number of such orderings is factorial in the number of agents. Choice of Individual Paths. When planning a path for an agent π‘Žπ‘–, which of the individually optimal paths that avoid the higher-priority agents paths to choose from. The number of such paths depends on the topology of the problem graph 𝐺, the source and target locations 𝑠𝑖and 𝑑𝑖, and the paths of previous agents, but they are often numerous (Li, Harabor, P. J. Stuckey, Ma, et al. 2019). Correspondingly, we define a PP algorithm as a pairing of a priority ordering P and a path-function F , where the former specifies a total order over the agents and the latter is a function that chooses which specific optimal path to return for a given agent (given the higher-priority agents paths). The choice of which priority ordering P is known to have a significant effect on the odds of finding a solution and the quality of that solution. Accordingly, previous works have mainly focused on finding good orderings (Bennewitz et al. 2002; Ma, Harabor, et al. 2019; Zhang et al. 2022). We show, both theoretically and empirically, that the choices of both P and F are important. That is to say, some pairing of P and F may lead PP to fail to find a solution, or to find a low-quality (high-cost) solution. This is illustrated in Figure 1. In this example, the source vertex and target vertex of each agent π‘Žπ‘–are labelled 𝑠𝑖 and 𝑑𝑖, respectively. Vertices 𝑣1, 𝑣2, 𝑣3 are additional vertices in the graph without any special association. Consider a priority ordering P = {π‘Ž1 π‘Ž2 π‘Ž3}. Clearly, π‘Ž1 plans its shortest path from its source 𝑠1 to its target 𝑑1. Then, when it is π‘Ž2 s turn to plan, it will use some path-function F to select among several equivalent-cost paths to reach its target 𝑑2 while avoiding the path of π‘Ž1. To avoid conflicting with π‘Ž1, π‘Ž2 will have to move into 𝑠3, 𝑣3, or 𝑑3, and also perform one wait action. This still leaves π‘Ž2 with multiple paths (of cost 5 for π‘Ž2) to choose from. Let Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:3 Fig. 1. A MAPF problem with three agents that may be solved by PP under certain conditions. Vertices 𝑠𝑖and 𝑑𝑖indicate the source and target positions of agent 𝑖. us focus on three of these possible paths. The first path, [𝑠2,𝑠2, 𝑣2,𝑑2, 𝑣3,𝑑2], will result in an optimal (minimal) SOC for all agents (which is 13). The second path, [𝑠2, 𝑣2,𝑑2, 𝑣3, 𝑣3,𝑑2], causes additional waiting (+1) for agent π‘Ž3 (when π‘Ž2 passes in 𝑣2), resulting in a sub-optimal solution (a total SOC of 14). The third path, [𝑠2, 𝑣2,𝑠3,𝑠3, 𝑣2,𝑑2], produces a deadlock failure, since π‘Ž3 is not able to move away from 𝑠3, resulting in an unavoidable collision. Thus, the choice of individual paths is clearly crucial for the success of PP in this example. Alternatively, using a different priority ordering would change the set of paths that the agents can choose from, possibly increasing the cost of a solution or resulting in a failure. For example, any ordering where π‘Ž2 has the highest priority will result in a deadlock, as π‘Ž2 would occupy 𝑑2 indefinitely, blocking both other agents from reaching their targets. Then, we define the Prioritised MAPF (P-MAPF) problem, which is the problem of solving a MAPF problem with any PP algorithm using any choice of P and F . Any solution returned for P-MAPF is a solution that could be returned by a PP algorithm for some choice of P and F and vice versa. We analyse P-MAPF theoretically, showing that computing feasible P-MAPF solutions is NP-hard. We then propose a new algorithm, Path and Priority Search (Pa PS), which computes optimal solutions to P-MAPF problems and returns failure if no such solution exists. Pa PS is the first prioritised algorithm to have these guarantees. We then decompose P-MAPF into two separate problems, along the lines of PP s two degrees of freedom: The first problem is called Priority Constrained MAPF (PC-MAPF), and is the problem of finding a solution that is prioritised with respect to a specific, given, priority ordering P. We show Pa PS can easily be adapted into an optimal and complete algorithm for PC-MAPF, which we call Priority Constrained Search (PCS). We also propose a simple and sub-optimal algorithm, Prioritised Planning with Randomised A* (PPR ), which uses randomisation to sample the space of feasible PC-MAPF solutions. The second problem is called Priority-Function Constrained MAPF (PFC-MAPF), and is the problem of finding a solution that is prioritised with respect to any ordering, but where F is given as input. Here too, we show Pa PS can easily be adapted into an optimal and complete algorithm, this time for PFC-MAPF. We call this algorithm Priority-Function Constrained Search (PFCS). We further show that these problems are also NP-hard. In an empirical analysis, we compare our optimal and sub-optimal algorithms with each other, as well as with existing baselines, in terms of solution quality, runtime, and success rate. We show that our proposed methods can succeed where a PP algorithm fails, and we report first optimal solutions for a wide range of P-MAPF problems from recent literature. We also use a sampling-based approach to approximate a P-MAPF oracle that scales to more agents than Pa PS. We use this to show the potential of better path choice in PP and inspire future works that would leverage it. The rest of this paper is structured as follows. In section 2, we give background on MAPF and relevant algorithms, techniques, and data structures. Section 3 introduces and analyses P-MAPF. In section 4 we describe Pa PS and its properties. Section 5 introduces PFC-MAPF and PC-MAPF1, as well as algorithms for solving these problems. Section 6 presents an experimental evaluation of new and existing algorithms. In section 7 we give 1Our preliminary work on PC-MAPF was published in the Proceedings of the 17th International Symposium on Combinatorial Search (2024). Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:4 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern our conclusions and directions for future work, followed by acknowledgements in section 8. Finally, appendix A includes long complexity proofs which we skip in the main body of the paper, and appendix B includes extended results for our experiments. 2 Background and Definitions In this work, we consider the classic Multi-Agent Path Finding (MAPF) model from Stern et al. (2019). The input of a MAPF problem is a directed graph 𝐺= (𝑉, 𝐸) and a set of π‘˜agents. Each agent π‘Žπ‘–has an associated source location 𝑠𝑖 𝑉and target location 𝑑𝑖 𝑉, given as a source vector 𝑠and the target vector 𝑑, respectively. Time is discretised into time steps. At each time step π‘₯an agent at vertex 𝑣 𝑉can move to an adjacent vertex 𝑒 𝑉 in the graph (provided there exists an appropriate edge (𝑒, 𝑣) 𝐸) or wait at its current location. A path is a sequence of moves and waits that transition an agent π‘Žπ‘–from 𝑠𝑖to 𝑑𝑖, and its cost is the number of time steps required to traverse it. A conflict occurs when two agents π‘Žπ‘–and π‘Žπ‘—attempt to occupy the same vertex 𝑣 𝑉 at the same time π‘₯, called vertex conflict (denoted as π‘Žπ‘–,π‘Žπ‘—, 𝑣,π‘₯ ), or traverse the same edge (𝑒, 𝑣) 𝐸(or the inverse edge (𝑣,𝑒)) at the same time π‘₯, called edge conflict (denoted as π‘Žπ‘–,π‘Žπ‘—,𝑒, 𝑣,π‘₯ ). A solution πœ‹to the MAPF problem is a set of π‘˜paths, one for each agent. We say that a solution is valid (equivalently, feasible) if the paths are conflict-free. If a solution does not meet the definition above in any way, such as by containing conflicts or only mapping some of the agents to paths, we call it invalid (equivalently, infeasible). The cost of a solution is defined as the Sum-of-Costs (SOC), which is the sum of the path cost of each agent; i.e., Γπ‘˜ 𝑖=1 cost(πœ‹π‘–). An alternative, less commonly used cost function is Makespan. This function is simply the maximal path cost, and disregards all paths with a lower cost; i.e. maxπ‘˜ 𝑖=1 cost(πœ‹π‘–). We will only focus on SOC in this paper. A solution is called optimal if it has the lowest SOC of all valid solutions to a given problem. 2.1 Heuristic Search Heuristic Search is a common technique for quickly finding solutions to problems with large (even infinite) state spaces. A fundamental and widely used algorithm in this field is A (Hart et al. 1968). The following is a standard formulation of A , though many variations exist. A searches a search tree, where node 𝑛contains a state as described by the problem definition, and a reference to the node s parent node. The root of this tree is a node 𝑛𝐼initialised with the initial state I of the problem. A efficiently explores the search tree to find a sequence of state transitions, from I in 𝑛𝐼, to a desired goal state 𝐺, in a goal node 𝑛𝐺. In some problems, multiple goal states exist, in which case 𝐺is implicitly defined by a function that tests if a given state is considered a goal state. A cost function, commonly denoted 𝑔(𝑛), assigns a cost to the search node. 𝑔(𝑛) must be monotonic and non-decreasing, so the cost of a child node is never lower than that of its parent. A heuristic function, commonly denoted β„Ž(𝑛), estimates the minimal additional cost that must be added on top of 𝑔(𝑛) to eventually transition to a goal node 𝑛𝐺. In other words, β„Ž(𝑛) is an estimate of 𝑔(𝑛𝐺) 𝑔(𝑛), where 𝑔(𝑛𝐺) has minimal cost among goal nodes reachable from 𝑛. A performs a best-first search on the tree in the following manner: First, the root node is generated and inserted into a priority queue called OPEN. Then, we iteratively remove (pop) from OPEN the node 𝑛with a minimal 𝑓(𝑛) = 𝑔(𝑛) + β„Ž(𝑛). After removing the node, we expand it. A process in which we generate child nodes, one for each state that we may transition to from the current node s state, as defined by the problem formulation. We then insert these nodes into OPEN and continue to the next iteration. The search stops when we pop a goal node. We can then follow the chain of parent state references in these nodes, and return the sequence of state transitions from the initial state to the goal state. In some problems, the sequence of transitions can be discarded, as only the goal state is desired. To guarantee that the goal state that A finds is optimal, i.e., has minimal cost, the heuristic function β„Ž(𝑛) must be π‘Žπ‘‘π‘šπ‘–π‘ π‘ π‘–π‘π‘™π‘’. An admissible heuristic function is one that never overestimates the remaining cost to get to a goal state. In other words, if β„Ž(𝑛) is admissible, then for any node 𝑛, β„Ž(𝑛) 𝑔(𝑛𝐺) 𝑔(𝑛), where 𝑔(𝑛𝐺) has minimal Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:5 Fig. 2. (a) A P-MAPF problem with three agents (repeated from Figure 1 for convenience). Vertices 𝑠𝑖and 𝑑𝑖indicate the source and target positions of agent 𝑖. (b-d) The minimal MDD of each agent. (e) MDD of π‘Ž2 with +1 depth. cost among goal nodes reachable from 𝑛. Under certain conditions, A is also optimally efficient (Dechter and Pearl 1988). 2.2 Path Finding for Individual Agents Algorithms that solve MAPF often explicitly compute a shortest path for an individual agent π‘Žπ‘–from its source 𝑠𝑖to its target 𝑑𝑖, while also avoiding constraints (often arising from paths of other agents). A common way to achieve this, is by running an A search on a time-expanded version of the problem graph (Silver 2005). A state in this search is a tuple 𝑣,π‘₯ of vertex and time, and its neighbours are { 𝑒,π‘₯+ 1 | (𝑣,𝑒) 𝐸 𝑒= 𝑣}. If a neighbour state violates a constraint, it is discarded. The initial state (called a root) is the agent s source location and time 𝑠𝑖, 0 . A goal state is a state 𝑣,π‘₯ where 𝑣= 𝑑𝑖and no constraints on 𝑣prevent the agent from waiting there indefinitely after time π‘₯. We refer to this algorithm as Temporal A . Multi-Valued Decision Diagrams (MDDs) are used by algorithms that need to reason over the set of all equivalent paths of a given cost 𝑧(Sharon, Stern, Goldenberg, et al. 2013). An MDD for a given agent, subject to constraints, is a directed acyclic graph. It has a source node, corresponding to the agent s source location, and a sink node, corresponding to the agent s target location. Internal nodes of the MDD are the set of all graph vertices that appear on a path of cost 𝑧(called the depth of the MDD) from source to sink that satisfies the given constraints. An MDD that has a minimal depth while satisfying the agent s constraints is called optimal or minimal. In Figure 2, (b-d) shows the minimal (assuming no constraints) MDDs for the three agents in the problem shown in Figure 2(a). Figure 2(e) shows an MDD for agent π‘Ž2, with a depth of 3 instead of 2. Note how only one node has to be used for 𝑣2 at depth 2, even though two possible paths pass through it. To build an optimal MDD, a single-agent search is invoked to find paths for the given agent subject to the given constraints. Once all optimal paths are found, each location 𝑣reached at time step π‘₯on any optimal path is added as an MDD node 𝑣at depth π‘₯. We define the Cartesian product of a set of MDDs 𝑀= {π‘š1,π‘š2, . . . ,π‘š|𝑀|} as the set of all unique sets of paths (equivalently, solutions) that can be formed by taking one path from each MDD ( (𝑀) = π‘š1 π‘š2 π‘š|𝑀|). 2.3 MAPF Algorithms Approaches for solving MAPF can be roughly divided into optimal or sub-optimal algorithms, and into complete or incomplete algorithms. Optimal MAPF algorithms guarantee to return a solution with minimal cost, whereas Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:6 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Fig. 3. A MAPF problem that is solvable, but for which PP could never find a solution (ČÑp, NovΓ‘k, et al. 2015). Vertices 𝑠𝑖 and 𝑑𝑖indicate the source and target positions of agent 𝑖. sub-optimal algorithms do not. Complete MAPF algorithms guarantee to find a solution if one exists, and return no-solution if one does not exist. Incomplete algorithms might not return a solution even when one exists. Alternatively, an algorithm may be solution-complete, meaning it guarantees to find a solution if one exists, but might continue running indefinitely when no solution exists. An algorithm is sound if it only returns valid (feasible) solutions. Typically in MAPF, only sound algorithms are considered. Conflict Based Search (CBS) (Sharon, Stern, Felner, and N. R. Sturtevant 2015) is an optimal and solutioncomplete MAPF algorithm of particular relevance for this paper. CBS is a two-level search algorithm. In the low-level search, CBS invokes Temporal A to find an optimal path for each agent that satisfies all its constraints from the high-level search while ignoring other agents planned paths. The high-level search of CBS performs a best-first search on a binary search tree, known as the Constraint Tree (CT). Each node in the CT contains a set of paths, one path for each agent. Put together, these paths form a solution, though it may contain conflicts. During the search, CBS maintains a priority queue (OPEN) of unexplored CT nodes, which prioritises nodes with the lowest solution cost (SOC) for expansion. The root node of the CT is created by invoking the low-level search without constraints, once for each agent, creating a set of individually optimal paths that may conflict with each other. The root node is then inserted into OPEN. Next, CBS pops a CT node from OPEN, detects conflicts in the current solution and selects one conflict π‘Žπ‘–,π‘Žπ‘—, 𝑣,π‘₯ between a pair of agents (π‘Žπ‘–,π‘Žπ‘—) (assume a vertex conflict for simplicity). To resolve the conflicts, CBS expands the node and generates two child nodes. Each child node is assigned one new constraint, either π‘Žπ‘–, 𝑣,π‘₯ or π‘Žπ‘—, 𝑣,π‘₯ , prohibiting one of the two agents involved in the conflict from using the vertex at the time of the conflict. Each child node then runs a low-level search with the addition of the new constraint to compute a new path for the constrained agent. These nodes are then inserted into the priority queue. This process iterates until a node with no conflicts is popped from OPEN. Prioritised Planning (PP) (Erdmann and Lozano-PΓ©rez 1986; Silver 2005) is a general problem-solving technique popularly used to tackle MAPF and other similar coordination problems. PP assumes a total order over the agents, and then proceeds to compute paths for the agents, one by one, in the specified order. For each agent in its turn, PP computes an individually optimal path that avoids the paths of preceding (equivalently, higher-priority) agents. Note that it does not matter whether the order is given as input or revealed on the fly, so long as each agent knows the paths of the agents that preceded it in the order. PP does not provide any completeness or optimality/sub-optimality guarantees. Among all MAPF problems that have feasible solutions, only a subset is solvable using PP. Moreover, when PP fails, it is unknown whether a feasible solution exists that satisfies the given priority order, or any other order (Ma, Harabor, et al. 2019). The example in Figure 3 shows a solvable MAPF problem instance that PP nevertheless can not solve. In this instance, there are two agents, π‘Ž1 and π‘Ž2, starting at 𝑠1 and 𝑠2 respectively, and going to 𝑑1 and 𝑑2 respectively. To solve this instance, the agents must swap their positions relative to each other in the corridor i.e., π‘Ž1 must be right of π‘Ž2. Clearly, in any valid solution, one of the agents will have to move up into 𝑣1, while the other will have to wait in place to allow the first agent to reach 𝑣1 without colliding at 𝑣2. PP will never find such a solution. Instead, the first agent will plan to move to its target without stopping, trapping the other agent in a dead-end and causing an unavoidable Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:7 collision. One way to view this deficiency is to say that in some cases, agents must exchange priorities on the fly, as they advance, rather than have static priorities. When planning for a single agent, PP may discover that there exist multiple equivalent-cost paths to the target. The decision of which path to choose is handled by tie-breaking during search, often arbitrarily, such that one path is selected. 2.4 MAPF Variations One advantage of PP is that its simplicity allows it to easily be extended to support non-standard definitions of MAPF. While this work focuses on the classic formulation of MAPF, many variations on the problem have been suggested. The following is a non-comprehensive list of MAPF variations: Weighted Graphs. In the classic MAPF formulation, the problem graph is unweighted, and agents move "instantly" between vertices, in the span of one time step. Some works considered weighted graphs, where traversing an edge may take multiple time steps (BartΓ‘k et al. 2018). Continuous Time. Instead of using discrete time steps, some formulations use continuous time to allow a more expressive state description (Andreychuk et al. 2022; Walker 2022). Kinematics. Unlike classic MAPF, where any traversal of an edge takes the same amount of time, the kinematics of agent movements, such as acceleration and deceleration, are sometimes considered (HΓΆnig et al. 2016). This is typically combined with continuous time. Agent Shape. Agents typically occupy a single vertex at a time. Previous works considered agents that have physical shapes such as circles, spheres, hexagons, etc. in metric space (Li, Surynek, et al. 2019; Walker 2022), or agents that occupy an arbitrary continuous set of vertices (Atzmon, Zax, et al. 2020). Online and Lifelong. A common extension of MAPF describes a problem that continues over time, potentially indefinitely. Here, new tasks or new agents are revealed over time, while existing tasks are eventually completed or existing agents leave the problem (Li, Tinka, et al. 2021; Morag, Felner, et al. 2022; Ε vancara et al. 2019). These formulations are often further extended by giving agents pickup-and-delivery tasks where they must visit one location to pick up a package, and then another location to deliver it (Ma, Li, et al. 2017). In these problems, throughput, in the form of the number of tasks completed over time, is measured instead of SOC. Robustness. Various strategies were introduced for prevention of, or recovery from, failures in planning (Morag, Stern, et al. 2023) and execution (Atzmon, Stern, Felner, N. R. Sturtevant, et al. 2020; Atzmon, Stern, Felner, Wagner, et al. 2020; Ma, Kumar, et al. 2017; Shahar et al. 2021) of MAPF solutions. 3 Prioritised MAPF In this work, we aim to characterise the space of MAPF problems that a PP algorithm can solve. As a preliminary, we formalise what a PP algorithm is. We defined a PP algorithm by a pair P, F . P, referred to as the priority order, is a total order over the set of agents, i.e., a relation where for any pair of agents π‘Žπ‘–and π‘Žπ‘—, either π‘Žπ‘– π‘Žπ‘—or π‘Žπ‘— π‘Žπ‘–. F , referred to as the path-function, is a function that accepts as input a pair of vertices 𝑣𝑠, 𝑣𝑑 𝑉and a set of constraints (usually, the paths of higher-priority agents), and outputs a shortest path from 𝑣𝑠to 𝑣𝑑that avoids the given constraints. A PP algorithm P, F iterates over the agents according to the priority order (P) and finds a path for each agent using F . To characterise the space of MAPF problems that a PP algorithm can solve, we also define the following concepts. A MAPF solution πœ‹is priority-constrained w.r.t. P if for every agent π‘Žπ‘–, the cost of the plan πœ‹(π‘Žπ‘–) is smaller than or equal to the cost of any path for π‘Žπ‘–that avoids conflicts with the paths in πœ‹of the higher-priority agents. This means that the paths assigned in πœ‹for agents whose priority is lower than π‘Žπ‘–did not prevent Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:8 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern assigning π‘Žπ‘–with a lower cost path.2 A MAPF solution is called prioritised if it is priority-constrained w.r.t. at least one priority order over the agents. Theorem 1. A MAPF problem is solvable by a PP algorithm iff there exists a prioritised solution for this problem. Proof. (PP Prioritised) PP plans agents one by one, from highest priority to lowest priority, as specified by some P. Each agent π‘Žπ‘—takes an individually optimal path but must avoid the previously planned paths of higher-priority agents {π‘Žπ‘–| π‘Žπ‘– π‘Žπ‘—}. Removing the path of π‘Žπ‘—cannot improve the arrival time of any π‘Žπ‘–, since the path of each π‘Žπ‘–is a shortest path computed independently of π‘Žπ‘—. Thus, the path of each π‘Žπ‘–and π‘Žπ‘—is valid, and the solution as a whole is prioritised. (Prioritised PP) By definition, there exists an ordering P where the paths of any two agents π‘Žπ‘–,π‘Žπ‘—| 𝑖 𝑗 P are such that the path of π‘Žπ‘–is independent of any constraints introduced by π‘Žπ‘—. Therefore, there exists a path function F for which this path is returned for π‘Žπ‘–when that agent is planned by PP, according to P. A direct corollary of Theorem 1 is that if a MAPF problem does not have a prioritised solution, then PP cannot solve this problem and vice versa. Next, we consider the challenge of identifying whether a given MAPF problem has a prioritised solution, i.e., whether it can be solved by a PP algorithm. We call the problem of finding a prioritised solution for a MAPF problem, the Prioritised MAPF (P-MAPF) problem. 3.1 Properties of P-MAPF An algorithm is called P-MAPF-complete if, given a P-MAPF problem, it guarantees to find a prioritised solution if one exists, or return no solution if no such solution exists. Theorem 2. The decision problem of whether a prioritised solution exists is NP-hard on directed graphs. The proof for Theorem 2 is in appendix A.1. Specific sub-classes of MAPF problem instances might be devised, where the equivalent P-MAPF problem instances are all solvable. A prominent example is well-formed instances (ČÑp, NovΓ‘k, et al. 2015; ČÑp, VokΕ™Γ­nek, et al. 2015), where the sources and targets of all agents are positioned such that each agent has at least one path that does not visit the source or target location of any other agent. Given such an instance, we can pair any ordering with a path-function that explicitly prohibits (via additional constraints) each agent from visiting any of the source and target locations of all other agents. The resulting PP algorithm is guaranteed to produce a solution, though the added constraints may result in longer paths. An intuitive explanation of this guarantee is that each agent can, in the worst case, stay at its source location until all higher-priority agents have finished moving into their target locations, and then move into its own target location. Of course, not all MAPF instances are well-formed. Seeing as how some MAPF instances are not solvable with PP, it would be desirable to know, given a MAPF instance, if it can be solved by PP. If the instance can not be solved using PP, then attempting to do so would be a fruitless endeavour, and we could instead use some other MAPF algorithm. However, Theorem 2 implies that given an arbitrary MAPF problem instance, discovering if it is possible to solve it using PP is a problem in NP-hard. Therefore, we likely can not easily make such recommendations for arbitrary MAPF instances. Beyond the question of whether a problem can be solved by a PP algorithm, one may also ask about the quality, i.e., the cost of the solution a PP algorithm may return. It is easy to see that the lowest-cost solution that can be returned by a PP algorithm is a solution to the corresponding P-MAPF problem, that has the smallest cost among all prioritised solutions. Such a solution is referred to as a P-MAPF-optimal solution. Theorem 3. The optimisation problem of P-MAPF is NP-hard on undirected graphs. 2Ma, Harabor, et al. (2019) referred to a priority-constrained solution as a solution that is consistent with the priority order. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:9 The proof for Theorem 3 is in appendix A.2. It is easy to see that for every P-MAPF problem there exists an analogous MAPF problem where the input is identical, but the returned solution may not be prioritised. Hence, for any P-MAPF-optimal solution, there exists a corresponding MAPF solution with an equal or smaller cost. Similarly, if a MAPF problem is unsolvable, then the corresponding P-MAPF problem is also unsolvable. However, the reverse is not true; i.e., for an unsolvable P-MAPF problem there may exist a valid MAPF solution. A straightforward approach for optimal P-MAPF is to alternate between enumerating all options for which agent should be next in the ordering, and enumerating all optimal constrained paths for the current agent in the ordering. We can do so using a search tree, which would start with an empty root node. The root would then split on the choice of agent. Since the root is empty, all agents in the problem are valid options for being next (first) in the ordering, so we create π‘˜child agent nodes , one for each agent. Each of these nodes would then split on the choice of path for the newly added agent, creating a child path node for each possible path that is optimal (shortest) while avoiding the paths of previous agents. We will then split each of these nodes on the choice of the next agent, which may be any agent that has not yet appeared in the branch. Thus, each node will have π‘˜ 1 child nodes. This process will continue in each branch of the tree, until all agents have been added and a path has been chosen for each. The resulting tree would have a depth of 2π‘˜, with alternating layers of agent nodes and path nodes. A trivial algorithm for P-MAPF would therefore be to search this tree by expanding nodes in a best-first order (smallest SOC). We call this algorithm Exhaustive Prioritised Planning (EPP). EPP guarantees to eventually find a P-MAPF-optimal solution and eventually terminate if no such solution exists. The main disadvantage is a large branching factor, as the number of ways to order π‘˜agents is π‘˜!, and even within a single ordering, many individually-optimal paths can exist for each agent. Note that Priority-Based Search (PBS) (Ma, Harabor, et al. 2019), a popular prioritised MAPF algorithm, does not search this tree, and is neither optimal nor complete for P-MAPF. PBS only searches over the space of (partial) orderings, without systematically exploring the space of path-functions. Additionally, PBS uses a depth-first search strategy on its search tree. Even if we were to run PBS with a best-first search, it would not guarantee optimality (on PBS s search space), as its use of partial orderings creates negative-cost edges. In the next section, we introduce a new and computationally efficient optimal algorithm for P-MAPF called Path and Priority Search (Pa PS). 4 The Path and Priority Search Algorithm (Pa PS) Path and Priority Search (Pa PS) is a novel search algorithm that solves P-MAPF problems. The primary insight behind Pa PS is to use MDDs in place of paths. This allows Pa PS to efficiently reason about sets of all shortest paths of an agent (subject to constraints), rather than inefficiently enumerate them. Pa PS is a two-level search algorithm. The high-level of Pa PS explores a novel search tree that gradually adds agents while branching over possible agent orderings (similarly to EPP) and over conflicts between MDDs of agents. The low-level of Pa PS finds MDDs for individual agents, resolving conflicts by avoiding constraints imposed by the high-level search. Pa PS is similar in broad strokes to CBS (Sharon, Stern, Felner, and N. R. Sturtevant 2015), but differs from it in several important ways: (1) Pa PS stores a set of paths for each agent (in an MDD) in every search node, while CBS stores only a single path per agent. (2) A node in the Pa PS high-level search tree may include paths of only a subset of the agents. The root of the search tree does not include any path, and Pa PS gradually adds agents (and their paths) as the search tree is generated. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:10 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Algorithm 1 Pa PS Input: a problem instance 𝐺,π‘˜,𝑠,𝑑, , a heuristic function 𝐻 1: OPEN priority-queue 2: root an empty PT node 3: OPEN.insert(root) 4: while OPEN not empty do 5: n OPEN.pop() 6: if |𝑛.M| = π‘˜and 𝑛.M is conflict free then 7: return solution from n.M 8: else if 𝑛.M is conflict free then 9: Expand On Agents(𝑛) 10: else 11: Expand On Conflict(𝑛) 12: return no-solution (3) Pa PS has two expand operations. The first is a binary split similar to that of CBS. The second creates one child node for each agent not yet added in the expanded node. (4) To resolve a conflict, Pa PS employs a novel type of constraint that favours high-priority agents, and it never generates nodes where the cost of these agents increases. Next, we describe Pa PS in full detail. 4.1 High-level Search At the high-level, Pa PS conducts a best-first search over the Priority Tree (PT); which is a search tree where each node 𝑛has the following fields: 𝑛.Pπ‘Ÿa total ordering over a subset of the agents. 𝑛.c - The identity of the lowest priority agent according to 𝑛.Pπ‘Ÿ. We refer to this agent as the current agent of 𝑛, and denote it by π‘Žπ‘. 𝑛.M - a mapping of the agents in 𝑛.Pπ‘Ÿto MDDs, where each agent is mapped to a single MDD. 𝑛.constraints - a set of constraints relevant for node 𝑛. We say that a search node 𝑛in the PT contains disjoint MDDs if no two MDDs in 𝑛.M contain the same node (vertex and time) or edge (pair of vertices and time). When 𝑛.M is disjoint, each agent mapped to an MDD in 𝑛.M can reach its target without any collisions by following any path in its MDD. In other words, the Cartesian product (𝑛.M) is a set of conflict-free sets of paths. If 𝑛contains disjoint MDDs, then we consider 𝑛to be conflict-free. Otherwise, we consider 𝑛to have a conflict. Algorithm 1 shows the pseudo code for the high-level search. We use a priority queue, OPEN, to determine the order of node expansions. To initialise the search, we generate an empty (all fields set to 𝑛𝑒𝑙𝑙or ) root node and insert it to OPEN (lines 2, 3). Nodes in OPEN are ordered according to 𝑓(𝑛) = g(n) + h(n), where 𝑔(𝑛) is the sum of depths of all MDDs in 𝑛.M and β„Ž(𝑛) is a heuristic function that estimates the remaining solution cost. We describe two such heuristics in Section 4.5. Let 𝑛denote the most recently popped node. If 𝑛is conflict-free and covers all agents, then it is a goal node, and the search is done (line 6). This means each agent can reach its target without any collisions by following any path in its MDD. The Cartesian product of all MDDs in the node (𝑛.M) is thus a set of feasible solutions to the Pa PS problem instance. We can now choose any arbitrary solution from (M) and return it (line 7). If 𝑛does not meet the criteria of a goal node, Pa PS continues the search using the generate and expand functions described next. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:11 Algorithm 2 Expand On Agents Input: parent node 𝑝 1: updated Constraints 𝑝.constraints 2: Add all critical resources of 𝑝.𝑀(𝑐) to updated Constraints 3: for 𝑖 {1, . . . ,π‘˜} | (𝑖 𝑝.𝑐) 𝑝.Pr do 4: Pr 𝑝.Pr {𝑝.𝑐 𝑖} 5: Generate(𝑖, a copy of 𝑝.𝑀, a copy of updated Constraints, Pr) 4.1.1 Expand. There are two types of expand operations in Pa PS: Expand On Agents (Algorithm 1, line 9) and Expand On Conflict (Algorithm 1, line 11). The former occurs when all MDDs in the expanded node are disjoint, i.e., there is no conflict between them. The latter occurs when a conflict is detected between the current MDDs. We describe both below. Expand On Agents (Algorithm 2). At this point, we can conclude that we are done with the current agent 𝑝.𝑐, as it does not conflict with agents that have a higher priority. This brings us to the main difference between the way CBS and Pa PS resolve conflicts. To preserve the priority, in Pa PS we do not allow a higher-priority agent to increase its cost. This is enforced as follows. Critical resources are single nodes or edges of the MDD, the removal of which would introduce a cut i.e., make it so there is no path from the source to the sink node of the MDD. In particular, the agent s target at any time past the depth of the MDD (the MDD s sink) is a critical resource, since agents stay at their targets indefinitely. Before we can add any new agents, we add all critical resources of the MDD of the current agent p.M(c) to the constraints (line 2). This ensures that a conflict with a critical resource of a high-priority agent will never occur in the PT. Thus, no lower-priority (upcoming) agents will be able to cut this MDD. We can then move on to addressing agents that we have not yet planned for. We expand 𝑝by adding a new agent to the priority ordering, assigning it the lowest priority among current agents (line 4). To ensure we cover all possible orderings, we branch and create a separate child node for each agent that is not already in 𝑝.Pr (line 3). Expand On Conflict (Algorithm 3). The MDDs 𝑝.𝑀inside a parent node 𝑝may have an internal conflict. This conflict is a tuple comprising two agents and a contested resource; e.g., a vertex conflict π‘Žhi,π‘Žπ‘, 𝑣,π‘₯ (line 1). One agent is always the current agent, π‘Žπ‘; the other agent is always a higher-priority agent π‘Žhi Pπ‘Ÿπ‘Žπ‘. The conflicting resource (vertex or edge) appears in the MDDs of both. There may exist multiple conflicts between the current agent and multiple higher-priority agents, in which case we pick the conflict with the earliest time. To resolve the conflict we call the Expand On Conflict procedure (Algorithm 1, line 11). This procedure branches at the parent node 𝑝and produces two child nodes. To resolve the current conflict, in each child node we will first directly constrain π‘Žhi, and then later indirectly constrain π‘Žπ‘. The left child will have a positive constraint π‘Žhi, 𝑣,π‘₯ , which says π‘Žhi must occupy vertex 𝑣at time π‘₯; i.e., 𝑀𝐷𝐷hi[𝑑] = {𝑣} (line 3). We enforce this by using the Restrict function (line 7) to create a sub-graph of the MDD 𝑀(hi) that only contains paths that satisfy the constraint. This is done by taking the sub-graph of the MDD that is rooted at (𝑣,π‘₯) and connecting it to all paths from the root that lead to (𝑣,π‘₯) (by searching back from (𝑣,π‘₯) to the MDD s root). Other paths are deleted from the MDD. The right child will have a negative constraint π‘Žhi, 𝑣,π‘₯ , which says that π‘Žhi must not occupy vertex 𝑣at time π‘₯; i.e., 𝑣 𝑀(hi)[π‘₯] (line 4). Here too we use Restrict, which in this case will remove 𝑣from 𝑀(hi). Then, as a result, any vertex that is not pointing to, or is not pointed to by, any other vertex is iteratively removed. The procedure of splitting by creating a positive and a negative constraint on the same agent is known as disjoint splitting (Li, Harabor, P. J. Stuckey, Felner, et al. 2019) for CBS. During the restrict operation, if new critical resources are identified in the updated 𝑀(π‘Žhi), then we preemptively constrain all lower-priority agents from conflicting with these critical resources (line 8, 9). Note that 𝑀(π‘Žπ‘) might currently be violating some of these new constraints. This will be handled in the generate function. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:12 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Algorithm 3 Expand On Conflict Input: parent node 𝑝 1: conf earliest conflict in 𝑝.𝑀 2: π‘Žhi conf .π‘Žhi 3: pos π‘Žhi, conf .𝑣, conf .π‘₯ 4: neg π‘Žhi, conf .𝑣, conf .π‘₯ 5: for r {pos, neg} do 6: 𝑀 a copy of 𝑝.𝑀 7: M(hi).Restrict(r) 8: constraints all new critical resources of M(hi) as constraints 9: constraints constraints 𝑝.constraints 10: Generate(𝑝.𝑐, 𝑀, constraints, 𝑝.Pr) Algorithm 4 Generate Input: index of current agent 𝑐, mapping of MDDs 𝑀, constraints set constraints, ordering prefix Pr 1: 𝑛 Pr,𝑐, 𝑀, constraints // initialize a new node 2: if 𝑛.𝑀(𝑐) = 𝑛𝑒𝑙𝑙 𝑛.𝑀(𝑐) violates any constraint in 𝑛.constraints then 3: 𝑛.𝑀(𝑐) low Level(π‘Žπ‘,π‘π‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘π‘ ) 4: if 𝑛.𝑀(𝑐) = no-solution then 5: Return 6: OPEN.insert(n) Generate (Algorithm 4). This function is invoked as a consequence of expanding (splitting) a parent node 𝑝 (Alg. 2 line 5, Alg. 3 line 10). It first initialises a new PT node with the given current agent, MDDs, constraints, and ordering prefix (line 1). Next, if 𝑀(𝑐) (the MDD of the current agent) has not been created yet (when arriving from Expand On Agents), or if 𝑀(𝑐) violates some constraints (might happen when arriving from Expand On Conflict), then Generate calls the low-level search to build 𝑀(𝑐) while satisfying the constraints (line 3). Note that in the latter case (𝑀(𝑐) already existed), the new 𝑀(𝑐) might have a larger depth (and thus cost) than the MDD it replaced. If the low-level search finds that no valid MDD exists given the current constraints, this node is pruned (lines 4-5). Finally, we add the new node to OPEN (line 6). 4.2 Low-Level Search The low-level search for Pa PS generates MDDs. This search is required to return the MDD representing all shortest paths for an agent to reach its target while obeying given constraints. This can be done using A to search the space of vertices and time, while avoiding constraints by not generating nodes that do not satisfy them. This is a typical way to plan paths in MAPF. However, instead of stopping as soon as a goal node is found, as is sufficient when searching for a single path, we must continue searching until all search nodes with 𝑓(𝑛) = 𝐢 (optimal cost) are expanded. During this search, we keep track of all parents of each A node, to maintain all equivalent length paths to each node. We can then construct the MDD using this information. For the sake of efficiency, when the agent already has an MDD, but the set of constraints imposed on this agent has changed since it was built, we may try to amend this MDD rather than build one from scratch. In this case, we remove from the MDD any path that violates one of the new constraints. If this procedure removes all paths from source to sink in the MDD, we search for a new MDD as described above. Otherwise, we can use the amended MDD, as it now obeys all current constraints. The amended MDD would have the same depth (cost) as the original MDD, while a new MDD will have a higher depth (cost). Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:13 Fig. 4. The PT for the problem in Figure 1, excluding expansions on conflicts. 4.3 Pa PS Example Figures 4 and 5, when put together, show the PT for the problem in Figure 1. We shall first discuss Figure 4, which gives a high-level view of how the PT contains all viable orderings of the agents, and how Pa PS searches them. Then we will examine Figure 5, which shows in detail how conflicts are resolved. The PT, illustrated in Figure 4, starts with an empty root node (a). In each node, we write the newly added agent and the cost (g) of the node. Generated nodes have a solid border, while invalid nodes that were not generated have a dashed border. Goal nodes are marked with a star. The root node is inserted into OPEN, and immediately popped and expanded. This generates three nodes (b-d), for each possible choice of highest-priority agent. We insert these into OPEN, pop (c) since it has the lowest cost (𝑔= 2), and expand it. Both child nodes (g) and (h) are immediately discarded, as the low-level detects there is no possible path for either agent to reach its target given the constraints imposed by π‘Ž2. We then expand node (d), adding either π‘Ž1 or π‘Ž2 as the next agent in the priority order after π‘Ž3. We continue expanding nodes in order of minimal cost (b), (j), (i), (f), and (e). Finally, we end up with three nodes with a cost of 𝑔= 13: (l) and (m) are both conflict-free and therefore possible goal nodes. If we choose to expand one of them, we will then finish the search. Conversely, (k) contains a conflict, so finding a solution with the ordering π‘Ž1 π‘Ž2 π‘Ž3 will require further work. We abstract this procedure away in subtree (o), and explain how this is done in the following example. Figure 5 focuses on a subtree of the PT for the problem in Figure 1, where the ordering is {π‘Ž1 π‘Ž2 π‘Ž3}. The figure only shows new or changed MDDs and new constraints in each node, and we limit our focus to vertex constraints. We also indicate the chosen conflict for nodes with conflicts. We start by generating node (b) as a child node of the root (a), by adding agent π‘Ž1. 𝑀(1), the minimal (and unconstrained) MDD for π‘Ž1 is added. All vertices in 𝑀(1) are critical resources, as removing any one of them would introduce a cut to the MDD. Thus, negative constraints on all lower-priority agents are now added to π‘π‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘π‘ , preventing any conflicts with these vertices. Next, we are done with 𝑀(1), and there are no conflicts since there is only one MDD, so we expand this node, generating child node (e), where agent π‘Ž2 is added, creating the ordering prefix {π‘Ž1 π‘Ž2}. Next, we add 𝑀(2), the minimal MDD for π‘Ž2 that obeys the current constraints. We check for conflicts with 𝑀(1) and find that there are none, so we are done with 𝑀(2). Therefore, we add constraints for its only critical resource, π‘Ž2,𝑑2, 5+ . Next, we generate node (k), creating the ordering {π‘Ž1 π‘Ž2 π‘Ž3}. We then build 𝑀(3) while obeying the current Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:14 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Fig. 5. A part of the PT for the problem in Figure 1, focusing on the ordering {π‘Ž1 π‘Ž2 π‘Ž3}. constraints, and detect that it has multiple conflicts with 𝑀(2) (not shown). We choose the conflict π‘Ž2,π‘Ž3, 𝑣2, 1 (other choices are possible). We expand the node (k), generating two child nodes. The left child (o.1) receives the positive constraint π‘Ž2, 𝑣2, 1 . This constraint is applied to 𝑀(2), removing any path that does not include vertex 𝑣2 at time 1. This introduces a new critical resource, so we add the constraint π‘Ž2, 𝑣2, 1 , and update 𝑀(3) to accommodate it, resulting in a cost (𝑔) of 14. We insert (o.1) into OPEN. The right child (o.2) receives the negative constraint π‘Ž2, 𝑣2, 1 . 𝑀(2) is restricted accordingly, new critical resources are detected, and their corresponding constraints are added. 𝑀(3) remains unchanged since the new constraints do not affect any resource that it uses. (o.2) is inserted to OPEN, and immediately popped, as its cost is 13, making it the current minimum. We expand Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:15 (o.2), generating (o.3) and (o.4), but (o.3) is pruned since the constraints it adds result in a deadlock where it is impossible for π‘Ž3 to reach its target. Next, (o.4) is popped from OPEN, and since it contains no conflicts (the MDDs are disjoint), it is considered a goal node. We return the path [𝑠1, 𝑣1,𝑠2, 𝑣2,𝑑2,𝑑1] for π‘Ž1, [𝑠3, 𝑣2,𝑑2,𝑑3] for π‘Ž3, and arbitrarily choose between the paths [𝑠2,𝑠2, 𝑣2,𝑠3, 𝑣2,𝑑2] and [𝑠2,𝑠2, 𝑣2,𝑑2,𝑑3,𝑑2] for π‘Ž2. Note that had the problem contained some other agent π‘Ž4, (o.4) would not have been a goal node yet. Instead, we would have next expanded (o.4) by adding π‘Ž3 π‘Ž4, building an MDD 𝑀(4), checking for conflicts, etc. Additionally, note that node (o.1) may still be expanded, and indeed the subtree rooted in it contains a solution. However, that solution is sub-optimal. 4.4 Pa PS Properties Lemma 1. The PT is finite. Proof. Starting from any node in the PT, putting more constraints on the MDD 𝑀(𝑖) of a higher-priority agent π‘Žπ‘– π‘Žπ‘will eventually (down the branch) either result in no MDD for π‘Žπ‘(a dead-end), or no conflicts between 𝑀(𝑖) and 𝑀(𝑐). This is because 𝑀(𝑖) will eventually degenerate into a single path (a list rather than a directed acyclic graph). The number of constraints we might put on π‘Žπ‘–before it becomes a single path is finite, limited by the initial size of 𝑀(𝑖). This translates to a set of constraints (stemming from all parts of 𝑀(𝑖) being critical resources) on 𝑀(𝑐), preventing conflicts with any component of 𝑀(𝑖). Crucially, this set includes a constraint on 𝑑𝑖that starts when π‘Žπ‘–arrives at 𝑑𝑖and lasts indefinitely, preventing 𝑀(𝑐) from conflicting with it. This allows us to detect when π‘Žπ‘is indefinitely prevented from reaching 𝑑𝑐because π‘Žπ‘–is blocking 𝑑𝑖. Thus, this set of constraints will either force us to find an MDD 𝑀(𝑐) that does not conflict with 𝑀(𝑖), or make it impossible for π‘Žπ‘to reach its target. Extending this logic to all higher-priority agents, we see that we can only add a finite number of constraints in any branch of the tree, and that adding these constraints either leads to a dead-end, or to a disjoint set of MDDs, at which point we can add another agent to the ordering. The number of agents is also finite, so eventually, as we traverse down the PT, there will be no more agents to add. Thus, all traversals down the PT will eventually reach either a dead-end or a goal node, making the PT finite. Theorem 4. Pa PS is sound and complete for P-MAPF Proof. A solution is permitted by a PT node 𝑛if its paths obey all constraints in n.constraints. A solution is represented by a node if it is included in the Cartesian product of all MDDs in the node. Notice that if for any arbitrary P-MAPF problem instance, (i) the set of all goal nodes in the PT together permit all valid solutions to the P-MAPF instance, and (ii), none of them represents an invalid solution, then Pa PS is sound and complete for P-MAPF. The following proof by induction will prove as much by showing that both properties are maintained whenever we split nodes while building the PT. The basic idea of the proof is that nodes only represent prioritised solutions, goal nodes only represent valid solutions, and that the tree starts by permitting all prioritised solutions and never discards any as it branches. The induction is split into two: The first induction proves that adding new agents (Expand On Agents) to a node that has no conflicts maintains both properties. The second induction proves that splitting by adding constraints to resolve a conflict (Expand On Conflict) maintains both properties. Induction 1: Base Case. When the root node is generated, there are no MDDs, and thus the constraints set is empty. Therefore, all valid solutions are permitted at this point (i). Additionally, since no solution is explicitly represented yet, all represented solutions are valid (and accordingly, prioritised) (ii). Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:16 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Induction Hypothesis. Assume a parent PT node 𝑝that contains |𝑝.𝑀| disjoint MDDs. Also assume that all solutions it represents are prioritised solutions for the set of |𝑝.𝑀| agents that correspond to the MDDs, though not necessarily for the entire problem, as it may contain more agents. Induction Step. When splitting 𝑝on agents, in each child node 𝑛, we: 1. Add constraints corresponding to the critical resources of the MDD p.M(p.c). (i) Some of the solutions permitted by 𝑝are not permitted by 𝑛. However, none of the lost solutions are prioritised, as they would all involve a lower-priority agent causing a higher-priority agent (𝑝.𝑐) to increase its cost. 2. Add a new agent 𝑛.𝑐to the ordering prefix 𝑛.Pπ‘Ÿas the new current (lowest-priority thus far) agent, and we create an MDD n.M(n.c) for it. (ii) The new MDD n.M(n.c) is built to have the minimal possible depth while avoiding existing constraints, all of which are critical resources of the existing MDD of some higher-priority agent. Thus, all represented solutions are prioritised (though not necessarily valid), as the cost of the new agent s paths can not be reduced. In the case that with the addition of the new agent 𝑛.𝑐, the node has come to contain all agents, and that the MDD of the new agent does not conflict with those of existing agents, then all represented solutions are valid. That is because they have a path for each agent, are prioritised, and contain no conflicts. In such a case, we have generated a goal node. Note that this step will not always lead us back to the hypothesis above. Instead, when the MDD of the new agent 𝑛.𝑐conflicts with MDDs of existing agents, we will instead arrive at the base case of induction 2. Induction 2: Base Case. When a new agent 𝑝.𝑐is added, properties (i) and (ii) are maintained according to the first induction. A special case of adding a new agent, which forms the base case for this induction, is when the MDD of the new agent has conflicts with one of the previous MDDs. Since this is just a special case, both properties also hold here. Induction Hypothesis. Assume a parent PT node 𝑝that contains |𝑝.𝑀| 1 disjoint MDDs and also a |𝑝.𝑀|th MDD, 𝑝.𝑀(𝑐), which has conflicts with some of the higher-priority MDDs. Induction Step. (i) When the MDD of a higher-priority agent (not 𝑝.𝑐) is constrained, no prioritised solutions are lost. Observe the set of paths covered by the MDD before constraining it any path either uses the constrained resource, or does not use it. Therefore, the union of the sets of paths represented by the positively (left child node) and negatively (right child node) constrained versions of the MDD is equal to the set of paths represented by the original MDD. Thus, any path permitted in a parent node is also permitted in one of its child nodes. (ii) After the current MDD (𝑀(𝑐)) is updated to obey the new constraints (avoid the new critical resources), all solutions in the new set of solutions represented by this node are prioritised. This is because the updated MDD is built to contain all paths that have a minimal depth given the current constraints (just as in the induction step of induction 1). Each child node 𝑛we generate at this step may now either have conflicts between 𝑐and higher-priority agents, or not have any. If a conflict exists, we return to the hypothesis step of this induction. If a conflict does not exist, we return to the hypothesis step of induction 1, or, if 𝑛already contains all agents, then 𝑛is a goal node, and all solutions it represents are prioritised and conflict-free. Thus, both the addition of new MDDs and the addition of new constraints maintain the property that all represented solutions are prioritised, and never eliminate any prioritised solutions from the PT. In particular, goal nodes represent prioritised solutions that are also valid. Any algorithm that systematically explores the PT Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:17 and only returns goal nodes will be sound and complete for P-MAPF. In the worst case, Pa PS will eventually explore the entire PT, which is finite (Lemma 1). Thus, Pa PS is sound and complete for P-MAPF. Theorem 5. Pa PS with an admissible heuristic is P-MAPF-optimal Proof. First, let us examine the optimality of the search without a heuristic function. The cost function (𝑔(𝑛)) is monotonically non-decreasing: When expanding on a conflict, we constrain the MDD of one of the higher-priority agents; however, the depth of that MDD may not decrease. If new critical resources arise as a result, the current MDD may only increase in depth, as it was already minimal given the parent s constraints. When expanding on agents, we add a new MDD for a new agent that was not covered by the parent node. This action only increases the cost of the child node. Thus, we see that by always expanding the node 𝑛with the minimal 𝑔(𝑛) from OPEN in a best-first-search manner, the first goal node we expand will have minimal cost. Finally, adding an admissible heuristic to such a cost function maintains the optimality guarantee (Hart et al. 1968). 4.5 Heuristic Functions We propose two heuristic functions for the high level of Pa PS. H1 is a simple heuristic that sums the lengths of the shortest path (while ignoring constraints) of each agent not yet in the node. 𝐻1 = 𝑖>|𝑀| cost(min Path(i)) This function can be computed in a preprocessing phase, stored in memory, and then quickly retrieved. Lemma 2. H1 is admissible: H1 sums the minimal depths of the MDDs of agents not represented in the node, so the real cost accrued when adding each agent may not be smaller. H2 uses a single-agent search algorithm to find the shortest path (while considering constraints but ignoring other agents) for each agent not yet in the node. 𝑖>|𝑀| cost(min Path(i, constraints)) These single-agent searches may be done efficiently using modern algorithms such as SIPP (Phillips and Likhachev 2011) or JPST (Hu et al. 2022). We used SIPP in our implementation. Another advantage of this heuristic is that it can detect cases where, given the current constraints in the node, it is already impossible to find a path for one of the upcoming agents. In this case, we prune the node. H2 is more informed than H1, but requires more online computations. Lemma 3. H2 is admissible: H2 finds the minimal depth that an MDD for an agent may have given current constraints. Adding more constraints may only increase this cost. Thus, when each agent is eventually added, the cost of its MDD will not be smaller than the cost found by H2. 4.6 Pruning Equivalent States Detecting independence between agents is a popular approach for easing the computational difficulty of MAPF (Sharon, Stern, Felner, and N. Sturtevant 2012; Sharon, Stern, Felner, and N. R. Sturtevant 2015; Standley 2010). Existing approaches usually assume independence optimistically, but must continuously re-examine this assumption as they solve the problem. This is because concluding that two (or more) agents are entirely independent in the problem, and will never interfere with each other, is very difficult. Let us call these supposedly Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:18 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern independent agents π‘Ž1 and π‘Ž2. Some third agent, π‘Ž3 may always induce either π‘Ž1, π‘Ž2, or both, to change their paths, causing π‘Ž1 and π‘Ž2 to conflict and become dependent. Fortunately, in P-MAPF, we can make stronger observations regarding independence. The feature of P-MAPF that enables this is that lower-priority agents have a very limited capacity to influence higher-priority agents, as the latter will never increase their cost. Next, we will show how to use this characteristic to detect and prune states in the PT which are functionally equivalent. We use a form of Partial Order Reduction (Godefroid 1996) in Pa PS, which only applies to a node 𝑛that has only disjoint MDDs; i.e., a node that would be expanded using Algorithm 2. If some other node 𝑛 has the same set of MDDs (n.M = n .M), then we can conclude they are equivalent meaning the sub-trees rooted at each node are identical. Thus, one of the nodes can be discarded. Note that two agents may never be assigned the same MDD (even in different PT nodes), since the source location of each agent, and thus the source node of any MDD assigned to it, is unique. Importantly, this pruning can be done even when the nodes contain different priority orderings (𝑛.Pπ‘Ÿ 𝑛 .Pπ‘Ÿ), so long as the MDDs are identical. We can do this, since Pa PS never considers the ordering between the higher-priority MDDs in a node, and would thus generate an identical subtree under each of these nodes. This process can also be viewed as merging two total orderings into one partial ordering which adequately represents both. Note that we can only say these two total orderings are equivalent subject to their respective constraints that were applied to resolve conflicts, as those created the MDDs which we use to check for equivalency. Formally, n.M = n .M = (𝑛 𝑛 ) As an example, consider a case where the root node is expanded, and among its child nodes exists a node 𝑛1 where π‘Ž1 has the highest priority, and a node 𝑛2 where π‘Ž2 has the highest priority. The MDDs that they were each assigned just so happen to be disjoint (perhaps because the agents are very distant from each other). In this case, if we expand 𝑛1 by adding π‘Ž2, or we expand 𝑛2 by adding π‘Ž1, we will have the same MDDs, just ordered differently. All agents added later will conflict with or avoid these MDDs with no regard to the internal ordering between π‘Ž1 and π‘Ž2, so these are duplicate nodes. In this case, a potentially large subtree (either the child of 𝑛1 or the child of 𝑛2) can be pruned. More involved cases may occur when MDDs conflict. For example, we might arrive at the ordering prefix π‘Ž1 π‘Ž2, and see that the MDDs of π‘Ž1 and π‘Ž2 conflict. We will then split the node and add constraints to resolve their conflicts. Then, once the conflicts are resolved, π‘Ž3, which happens to be independent of π‘Ž1 and π‘Ž2, will be added without any conflicts. Let us call this node 𝑛. In another branch of the tree, π‘Ž3 will be given the highest priority, then π‘Ž1 will be added next without any conflicts, and then π‘Ž2 will be added, conflicting with π‘Ž1. Here too, we will split to resolve the conflicts between the MDDs of π‘Ž1 and π‘Ž2. The conflicts will be resolved in the same manner that led to node 𝑛, since we assume for the purpose of this example that π‘Ž3 is completely independent of π‘Ž1 and π‘Ž2. Thus, we will reach a node 𝑛 , which contains the same set of MDDs as node 𝑛, and we will prune it. We note that such duplicates do not happen often in dense problems, but can happen in sparse environments. 5 Studying PP with Random Restarts Recall that in basic PP a single priority ordering P is used, as well as a single path-function F . In many practical implementations, PP is executed multiple times. A popular implementation fixes the path-function F , and PP is run multiple times with different priority orders P. This is known as PP with Random Restarts (PP-RR) (Bennewitz et al. 2002). In this section, we characterise the space of MAPF problems PP-RR can solve. We also characterise the space of MAPF problems that can be solved with the less-studied complementing algorithm, in which the priority order is fixed and the path function is varied. Figure 6 illustrates the relationship between these solution spaces. The outside white area is the solution-space of a given MAPF problem instance. The blue and yellow inner circles will be explained below. The union of these Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:19 Fig. 6. Relations of the solution spaces MAPF, P-MAPF, PC-MAPF, and PFC-MAPF. circles is the P-MAPF solution space. The intersection of the two inner circles (in green) is the solution returned by a single PP algorithm defined by a single pair of P, F . 5.1 Path-Function Constrained MAPF The Path-Function Constrained MAPF (PFC-MAPF) problem (Figure 6, blue circle) is defined by a tuple 𝐺,π‘˜,𝑠,𝑑, F where 𝐺is a graph; π‘˜is the number of agents; 𝑠and 𝑑are the source and target vectors, mapping each agent to its initial and final location in 𝐺. We call a solution πœ‹path-function constrained w.r.t. a path-function F if all paths match the mapping in F ; i.e., we could recreate πœ‹by ordering the agents in some order P, and then iterate over the agents according to that order, deriving a path πœ‹π‘–for an agent π‘Žπ‘–using F and adding that path (as constraints) to the input of F for all subsequent agents. Formally: P πœ‹π‘– πœ‹| πœ‹π‘–= F (𝑠𝑖,𝑑𝑖, {πœ‹π‘— πœ‹|𝑖 𝑗 P}) A solution πœ‹to the PFC-MAPF problem is a prioritised MAPF solution that is path-function constrained w.r.t. the given function F . An algorithm is called path-function-complete if, given a PFC-MAPF problem, it guarantees to find a pathfunction-constrained solution if one exists or return no solution if no such solution exists. Theorem 6. The decision problem of whether a PFC-MAPF solution exists is NP-hard on directed graphs. The proof for Theorem 6 is in appendix A.3. A solution to a PFC-MAPF problem is called path-function-optimal if it has the smallest cost among all path-function-constrained solutions. Theorem 7. The optimisation problem of PFC-MAPF is NP-hard on undirected graphs. The proof for Theorem 7 is in appendix A.4. Observation 1. The optimisation problem of PFC-MAPF is NP-hard on directed graphs. As the solution space of PFC-MAPF is a subset of the solution space of P-MAPF, it naturally follows from Theorem 1 that the solutions to PFC-MAPF problems are equivalent to the solutions that may be computed by PP with a given path-function F to the equivalent MAPF problems. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:20 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 5.2 Priority Constrained MAPF The Priority Constrained MAPF3 (PC-MAPF) problem (Figure 6, yellow circle) is defined by a tuple 𝐺,π‘˜,𝑠,𝑑, P where 𝐺is a graph; π‘˜is the number of agents; 𝑠and 𝑑are the source and target vectors, mapping each agent to its initial and final location in 𝐺; P is a total order (priority) over the set of agents. Note that here, unlike in PFC-MAPF, the path-function is not given in advance. A solution πœ‹to the PC-MAPF problem is a set of paths, one for each agent, that is also priority-constrained w.r.t. to P (which was given as input). A solution to a PC-MAPF problem is called priority-optimal w.r.t. P if it has the smallest cost among all priority-constrained solutions w.r.t. P. An algorithm is called priority-complete w.r.t P if, given a PC-MAPF problem, it guarantees to find a priority-constrained solution if one exists or return no solution if no such solution exists. As the solution space of PC-MAPF is a subset of the solution space of P-MAPF, it naturally follows from Theorem 1 that the solutions to PC-MAPF problems are equivalent to the solutions that may be computed by PP with a given priority ordering P to the equivalent MAPF problems. Theorem 8. The decision problem of whether a priority-constrained solution exists is NP-hard on undirected graphs. In appendix A.5 we prove theorem 8, stating that deciding whether a solution to a PC-MAPF problem instance exists is NP-hard. This puts PC-MAPF and MAPF in the same complexity class. Moreover, PC-MAPF is potentially harder than MAPF on undirected graphs, as the decision problem for those is polynomial for MAPF (Daniel Kornhauser 1984). Observation 2. The decision problem of PC-MAPF in directed graphs and the corresponding optimisation problems both in directed and undirected graphs are NP-hard. 5.3 Finding Constrained MAPF Solutions To find optimal solutions to either PC-MAPF or PFC-MAPF, we propose Priority Constrained Search (PCS) and Path-function constrained Search (PFCS), which are adaptations of Pa PS to solve PC-MAPF and PFC-MAPF, respectively. PCS receives as input a PC-MAPF problem 𝐺,π‘˜,𝑠,𝑑, P and returns a priority-optimal solution for it. PCS operates identically to Pa PS, with one alteration when splitting on agents, PCS only generates a single child node, where the added agent is the next agent according to P. PFCS receives as input a PFC-MAPF problem 𝐺,π‘˜,𝑠,𝑑, F and returns a path-function-optimal solution for it. PFCS operates identically to Pa PS, with one alteration the low-level search generates a single optimal path using F , instead of an MDD of all optimal paths. A single path is a special case of an MDD, so this path can be handled by the rest of the algorithm in the same manner any arbitrary MDD is handled. The same heuristic functions used in Pa PS may also be used in PCS and PFCS. Observe that PCS and PFCS search the same search space as Pa PS, but restrict it to eliminate solutions iff they are not valid given their problem inputs (priority ordering, or path-function, respectively). Thus, it is clear to see that given that Pa PS is P-MAPF complete and optimal, so too are PCS and PFCS priority complete and optimal, and path-function complete and optimal, respectively. In Figure 5, we focused on a subtree of the PT restricted to a single ordering. Therefore, that example is also as an example of PCS on the same problem, when given the ordering P = {π‘Ž1 π‘Ž2 π‘Ž3}. Solving PFC-MAPF suboptimally can be done using PP-RR (which uses a fixed path-function F but randomises the priority ordering P of agents every iteration). Clearly, PP-RR cannot be used to solve PC-MAPF suboptimally, since the priority order is fixed. As an alternative, we fixed the priority ordering P but randomised F in order to choose between different paths with equal costs. We call this simple and scalable algorithm Prioritised Planning 3Our preliminary work on this problem was published in the Proceedings of the 17th International Symposium on Combinatorial Search (2024). Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:21 Table 1. Summary of how the algorithms relate to the choice of ordering and path-function. Note that the left column relates to the PFC-MAPF problem, the top row relates to the PC-MAPF problem while the entire table relates to P-MAPF Path-Function Fixed Sub-Optimal Optimal Fixed PP PPR* PCS PC-MAPF Sub-Optimal PP-RR - Ordering Optimal PFCS - Pa PS, EPP PFC-MAPF P-MAPF with Randomised A (PPR ). The main advantage of PPR is that given P, PPR repeatedly samples from the space of possible priority-constrained solutions, while PP considers only one. Both PP and PPR are incomplete, and neither provides any guarantees on the quality of returned solutions. 6 Experimental Results Table 1 summarises how the different algorithms in this paper relate to the choice of ordering P and path-function F . "Fixed" means P and/or F are given as input. "Sub-Optimal" refers to algorithms that search for a good P or F and return the best solution they discover within the allotted planning time, providing no guarantees on its quality. "Optimal" relates to algorithms that systematically find the best P and/or F . The combination of fixed P and fixed F is a single execution of the basic PP algorithm. We also marked which algorithm maps to which of the problems we defined in this paper, using the same colouring as in Figure 6. We address the empty brackets of this table in the discussion (section 7). We implemented our optimal algorithms: Pa PS, PCS, and PFCS with H1 and H2, as well as our suboptimal algorithms: PPR , PP-RR, and PP. Our code and data are available online at: www.github.com/J-morag/MAPF /releases/tag/25.JAIR.PP. The first iteration for PPR and PP-RR was made to run identically to PP. We also created an algorithm that randomises both the ordering (like PP-RR) and the path-function (like PPR ), but found that its performance in practice was very similar to that of PP-RR. We experimented using a grid-based MAPF benchmark from Stern et al. (2019). For each map, we used 25 different scenarios, each with 8 MAPF problem instances. In each instance, we varied the number of agents from 5 to 40, increasing by 5. We converted the MAPF instances into P-MAPF instances for Pa PS, into PFC-MAPF instances for PFCS and PP-RR, and into PC-MAPF instances for PCS and PPR . For PC-MAPF instances, we used the order that agents appear in the benchmark as the instance s priority ordering. For PFC-MAPF instances, we implemented path-functions as follows: We assign A nodes with identifier numbers, and when deciding which of a set of equal nodes (same 𝑓()) to expand next, we choose the one with the minimal identifier. We derive these numbers from a deterministic pseudo-random number generator. This number generator is reset every time A is used, and resetting it with a different seed produces a different path-function. We present results on a diverse set of maps from the benchmark. We ran our experiments on Linux virtual environments, on a cluster of AMD EPYC 7763 CPUs, with 16GB RAM each. We used Open Java Runtime 18 (JRE 18) to run our code. 6.1 Coverage and Runtime Figure 7 (additional results in appendix B) shows the runtime of each algorithm (𝑦-axis) as a factor of the number of successes (π‘₯-axis), where for each algorithm (separately) we ordered the instances in increasing order of their runtime. Thus, when examining a specific point on an algorithm s line, we can say "the algorithm would solve this many instances if its runtime were limited to this many seconds". We count a success if either the algorithm found a solution, or it proved that the problem is unsolvable. Naturally, proving an instance is unsolvable only Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:22 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 0 25 50 75 100 125 150 175 200 Coverage up to 60s PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s random-64-64-20 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s room-32-32-4 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s room-64-64-8 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s maze-32-32-4 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 20 40 60 80 100 120 140 160 Coverage up to 60s maze-128-128-1 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s warehouse-10-20-10-2-1 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 Coverage up to 60s warehouse-20-40-10-2-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s lt_gallowstemplar_n PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS Fig. 7. Max runtime per instance, as a factor of coverage. applies to the complete algorithms, and each of those considers a different problem as unsolvable P-MAPF problems for Pa PS, PC-MAPF problems for PCS, and PFC-MAPF problems for PFCS. For PPR and PP-RR, the runtime until the first solution was found is used on the 𝑦-axis. This is because they always use all the allowed runtime to attempt to improve the solution. Comparing Pa PS with the two proposed heuristics, Pa PS-H2 often solves more problems in less time (The H2 curve is below the H1 curve). For example, in map warehouse-10-20-10-2-1, Pa PS-H2 achieves 121 successes, whereas Pa PS-H1 only succeeded on 72 problems. For PCS and PFCS we always used H2. In most maps, the difference was smaller, but it was never better to use H1. Therefore, we only use H2 below. We next compare the different suboptimal algorithms. As could be expected, PP, PP-RR, and PPR take the same amount of runtime to find the first solution. Consequently, their lines mostly overlap in the plots (at the bottom). However, in cases where PP fails to find a solution, PPR and PP-RR continue to run and often eventually find a solution. For example, in maze-32-32-4, PP solved 126 instances, PPR solved 191 instances, and PP-RR solved 200 instances. Clearly, algorithms with stronger guarantees had fewer successes and required more time. Pa PS had the least successes, followed by PFCS and PCS, with the suboptimal algorithms achieving significantly more successes. In maps where many of the instances were unsolvable (with the given ordering), PCS was able to succeed much more often. For example, this happened in maze-128-128-1, which is a maze map comprised of many corridors that are one vertex wide. The reason is that in 66% of this map s instances, PCS was able to exhaust the search space and prove that those instances were unsolvable. Table 2 shows how many of the PC-MAPF instances were proved unsolvable by PCS. Note that it is possible that more instances are unsolvable, but PCS was unable to prove so within the runtime limit. In all other maps, PCS did not prove any instances were unsolvable. Therefore, PCS had partial success in proving unsolvability. By Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:23 Table 2. Number of PC-MAPF instances proven by PCS to be unsolvable with the default priority ordering. empty-8-8 maze-128-128-1 maze-128-128-2 maze-32-32-2 maze-32-32-4 room-32-32-4 room-64-64-8 3 (2%) 132 (66%) 3 (2%) 18 (9%) 22 (11%) 15 (8%) 23 (12%) contrast, PFCS and Pa PS are also theoretically capable of proving instances are unsolvable under their respective problem definitions, but neither was able to do so within the runtime limit in our experiments. Thus, they had no success in proving unsolvability. In the worst case, PFCS and Pa PS need to go over 𝐾! priority orderings in order to prove unsolvability, and the time limit did not allow that. 6.2 Solution Costs We compare the solution costs of Pa PS, PCS, PFCS, PP, PPR and PP-RR in Figure 8 (additional results in appendix B). For heuristics, we use H2, as the previous experiment suggests it is never detrimental to use it. The π‘₯-axis is the best known lower-bound on the cost of each MAPF problem, extracted from an online tracker (Shen et al. 2023). This is usually the optimal MAPF cost. The MAPF bound is also a lower bound on the cost of all our other problems. Among different problems on the same map, a larger bound generally implies more agents, longer paths, and more interference between agents, and thus implies a more difficult problem. The 𝑦-axis shows the ratio between the SOC of a solution and the best-known bound on the cost (as given by the tracker). If an algorithm failed to solve an instance, it simply has no marker that corresponds to that instance. To make the figures easier to read, we merge every 10 solutions of each algorithm, by showing a single marker corresponding to their average SOC and average best bound. In comparing PP and Pa PS, it is clear to see that PP often finds solutions with a significantly higher cost. The trend was a clear increase in the ratio of the costs of their solutions as the number of agents increased. For example, in empty-8-8, on instances solved by both Pa PS and PP, the average ratio of their costs was 1.04 with 5 or 10 agents, 1.07 with 15 agents, and 1.13 with 20 agents. Pa PS usually found solutions with costs equal to, or very close to, those of optimal solutions to the equivalent MAPF problems. Of course, these solutions are all optimal P-MAPF solutions. This demonstrates that PP has the potential to find optimal MAPF solutions, even though in its basic form of a single run, it often does not. Nevertheless, our experiment is limited by the limited scaling of Pa PS. We shall revisit this point in section 6.3. Both PPR and PP-RR provided a balance of solution quality and scalability. PPR was able to find solutions with lower SOC than those found by PP, though often not as low as those found by PCS. Similarly, PP-RR was able to find solutions with significantly lower SOC than those found by PP, though often not as low as those found by PFCS. PP-RR consistently found better solutions than PPR , but the differences were limited. For example, in room-64-64-8, PPR solutions had on average 2.3% higher SOC. These results imply that the choice of ordering is more important than the choice of path-function for finding high-quality (low cost) solutions. However, it seems the gap between PPR and PP-RR, given the same amount of runtime, is usually not large. 6.3 P-MAPF-Optimal Approximation for Numerous Agents Our results showed that PP often produces poor quality solutions, or fails to find them altogether. We saw that choosing better individual paths, either through sampling with PPR , or through optimal search using PCS, can greatly improve the quality of solutions, even without varying the prioritisation. We further saw that the commonly used PP-RR can find even higher quality solutions given the same amount of runtime, and that optimal PFC-MAPF solutions found by PFCS were close in cost to optimal MAPF solutions. This raises the question how much could we improve PP-RR by always using the optimal path-function for each ordering? Answering this question is difficult in practice because it is difficult to find the exact optimal path-function. When the number of Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:24 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 50 100 150 1.00 SOC/Best Bound PP-RR Pa PS PCS PFCS 500 1000 1500 2000 1.00 SOC/Best Bound random-64-64-20 PP-RR Pa PS PCS PFCS 250 500 750 1000 1250 1.00 SOC/Best Bound room-32-32-4 PP-RR Pa PS PCS PFCS 1000 2000 3000 1.00 SOC/Best Bound room-64-64-8 PP-RR Pa PS PCS PFCS 500 1000 1500 2000 1.00 SOC/Best Bound maze-32-32-4 PP-RR Pa PS PCS PFCS 2500 5000 7500 10000 1.00 SOC/Best Bound maze-128-128-1 PP-RR Pa PS PCS PFCS 1000 2000 3000 4000 1.00 SOC/Best Bound warehouse-10-20-10-2-1 PP-RR Pa PS PCS PFCS 2000 4000 6000 8000 1.000 SOC/Best Bound warehouse-20-40-10-2-2 PP-RR Pa PS PCS PFCS 2000 4000 6000 1.00 SOC/Best Bound lt_gallowstemplar_n PP-RR Pa PS PCS PFCS Fig. 8. The cost of solutions, relative to the best known lower bound on the cost of optimal solutions to the equivalent MAPF problems. agents is low, most algorithms perform well enough, and the differences in solution quality are small. The more interesting results will be those of higher numbers of agents. However, our relevant optimal solvers, PCS and Pa PS, only scale to about 10 to 40 agents. To bridge this gap, we propose an approximation of optimal path choice. We run PP-RR with a budget of 150 orderings and no time limit, and we attempt to solve each ordering 50 times, using different random path-functions. We shall call this algorithm PP-RR-50. We compare the solutions found in this manner with those found by PP-RR (always using the same path-function, attempting each ordering just once). We only include instances where both solvers had found a solution starting from the first iteration, and we only use instances that were solved starting from the first ordering. We use the highest number of agents available in the benchmark and solved successfully, up to 100 agents. We plot the results of this experiment on the left column of Figure 9, where the horizontal axis is the number of attempted orderings, and the vertical axis is the mean ratio between the SOC of a solution and the best-known bound on the cost. The shading around each line is the standard error of the mean. We only include instances Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:25 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound empty-8-8.map (32 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved empty-8-8.map (32 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound random-64-64-20.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved random-64-64-20.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound room-64-64-8.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved room-64-64-8.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound maze-32-32-4.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved maze-32-32-4.map (100 Agents) PP-RR PP-RR-50 Fig. 9. Suboptimality of solutions and Success Rate of PP-RR with 1 or 50 path-functions, as a factor of the number of orderings attempted. solved by both algorithms since the first ordering. The results show that the cost graph approaches a plateau as we try more and more orderings, as each additional ordering attempted is less likely to find a solution better than the current best. This is reasonable if we assume attempting a random ordering samples uniformly from the set of all PFC-MAPF solutions to the problem, then the more we sample, the less likely we are to find a solution that is better than all previous samplings. Of course, this process can potentially be shortened by employing heuristic methods of guessing which orderings would produce good solutions. However, this is not our focus. Instead, we see here that this process can also be shortened through finding better path-functions for the same orderings. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:26 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound random-64-64-20.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved random-64-64-20.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound room-64-64-8.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved room-64-64-8.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound maze-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved maze-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound room-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved room-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 Fig. 10. Suboptimality of solutions and Success Rate of PP-RR with 1 or 50 path-functions, as a factor of the number of PP runs (pairs of ordering and path-function). Indeed, we see that PP-RR-50 consistently found better solutions. This held true not only for the first orderings attempted, where improvements are easy, but even after more than 100 orderings. The right column of Figure 9 shows the success rate (the number of solved instances divided by the total number of instances) as a factor of the number of orderings attempted. The shaded area is the standard error. Here we see similar trends to those we saw with solution costs, though more subtle. By using 50 path-functions per ordering, we were able to find solutions earlier in terms of the number of orderings attempted. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:27 These results should not be interpreted to mean that trying 50 path-functions (using PP-RR-50) is a better use of runtime than trying new orderings. In fact, it was more often, though not always, more beneficial to attempt a new random ordering rather than re-try the same ordering with a new random path-function. Figure 10 shows an effort-based comparison of the benefits of trying random orderings versus random path-functions. It is organised in the same manner as Figure 9, except that the π‘₯-axis is now the number of PP runs (pairs of ordering and path-function) attempted. We gave each solver a budget of 300 runs, which translates into different numbers of orderings and path-functions, depending on the solver. PP-RR-50 is an extreme example of preferring to explore path-functions over orderings, so we add two solvers that represent more reasonable middle grounds PP-RR-2 and PP-RR-3, which try 2 or 3 path-functions respectively, for each ordering. For both solution cost and coverage, PP-RR-50 performed worse in most cases, though in some examples, like room-64-64-8 with more than 116 runs, it had the best cost. The other three solvers performed similarly to each other in terms of solution cost, with no clear winner. In terms of coverage, trying fewer path-functions (and more orderings instead) was sometimes advantageous, though differences were quite small. For example, on maze-32-32-4 with 110 runs, PP-RR-3 had 16% coverage, PP-RR-2 had 20% coverage, and PP-RR had 24% coverage. One notable counter-example is maze-32-32-4, where PP-RR-2 had better coverage than PP-RR, and PP-RR-3 had the best coverage, indicating there are some conditions under which finding a good path-function can be more important for coverage than the choice of ordering. None of the instances on this map was solved by any algorithm on the first run, so we only display the solution cost results of instance number 1. These results motivate the need to find a good path-function given an ordering, or find both in conjunction. This is a wide topic that is left for future work. Possible approaches include heuristic methods and machine learning. 7 Discussion and Future Work Prioritised Planning (PP) is a widely popular method to simplify and tackle Multi-Agent Path Finding (MAPF). In this work, we studied PP. To this end, we defined the concept of a PP algorithm, as a pair P, F . P, referred to as the priority order, is a total order over the set of agents. F , referred to as the path-function, is a function that accepts as input a pair of vertices 𝑣𝑠, 𝑣𝑑 𝑉and a set of constraints, and outputs a shortest path from 𝑣𝑠to 𝑣𝑑that avoids the given constraints. The path-function is a concept new to this work. We described a hierarchy of the problems solved by PP. This hierarchy starts with Prioritised MAPF (P-MAPF), which includes all solutions to a MAPF problem that could be found by PP. It is then further divided into two problems. The first problem is Path-Function Constrained MAPF (PFC-MAPF), which includes all P-MAPF solutions that choose individually optimal paths using a given path-function. PFC-MAPF is the problem that most textbook implementations of PP solve, as most prior works only dealt with modifying P. The second problem is Priority Constrained MAPF (PC-MAPF), which includes all P-MAPF solutions that are constrained to a specific priority ordering. Solutions to PC-MAPF are required by important industrial applications. We gave a first analysis characterising the complexity of the problems we formalised. Table 3 summarises these results. We showed that P-MAPF, PC-MAPF, and PFC-MAPF are all generally in NP-hard. This result is somewhat unintuitive, as PP algorithms are usually used to make the difficult MAPF problem easier to solve, sacrificing completeness and solution quality for low runtime. One may assume that this speed-up is achieved precisely because PP algorithms limit the space of solutions they can find to the space of solutions to P-MAPF problems, potentially missing some MAPF solutions. Yet, this is evidently not the case, as we have shown P-MAPF is at least as hard as MAPF. At this time, the complexity of the problems of finding feasible P-MAPF and PFC-MAPF solutions on undirected graphs remains an open question. However, we proved that the more general problem of finding feasible (P-MAPF or PFC-MAPF) solutions on directed graphs is in NP-hard. We found that surprisingly, Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:28 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Table 3. Summary of complexity results for the problems associated with PP. Each problem formulation is divided into the problems of finding feasible or optimal solutions on directed or undirected graphs. Known MAPF results are included for reference. P-MAPF MAPF Directed Undirected Directed Undirected Feasible NP-hard (Theorem 2) ? NP-hard (Nebel 2020) Poynomial (Daniel Kornhauser 1984) Optimal NP-hard (Theorem 3/2) NP-hard (Theorem 3) NP-hard (Yu and La Valle 2013) NP-hard (Yu and La Valle 2013) PC-MAPF PFC-MAPF Directed Undirected Directed Undirected Feasible NP-hard (Theorem 8) NP-hard (Theorem 8) NP-hard (Theorem 6) ? Optimal NP-hard (Theorem 8) NP-hard (Theorem 8) NP-hard (Theorem 7/6) NP-hard (Theorem 7) PC-MAPF is potentially a harder problem than MAPF, as finding feasible solutions on undirected graphs is in NP-hard for PC-MAPF, whereas it can be done in polynomial time for MAPF. These three problems can be solved using a broad family of PP algorithms. Unfortunately, PP algorithms suffer two notable drawbacks: 1. The quality of the solutions they return is unbounded sub-optimal, and it is not clear if solutions can be further improved. 2. PP can produce deadlock failures, leaving practitioners without explanation or recourse. We developed algorithms to solve these problems: Pa PS, which is complete and optimal for P-MAPF. PFCS, which is complete and optimal for PFC-MAPF. PCS, which is complete and optimal for PC-MAPF. PPR , which solves PC-MAPF sub-optimally, but quickly. We evaluated our algorithms against existing baselines on a range of common MAPF problems, and showed that Pa PS, PCS, and PFCS can succeed where PP fails. We gave tighter bounds for the quality of P-MAPF, PC-MAPF, and PFC-MAPF solutions, and optimally solved many associated problem instances for the first time. Together, these results give guidance to practitioners using PP in real applications. When PP fails, Pa PS can help explain the reasons for that failure, and when PP succeeds, Pa PS can be used to improve solution quality. In this work, we focused on optimal algorithms, creating Pa PS, PFCS, and PCS. We also investigated some options for suboptimal algorithms, creating PPR , and comparing it with PP-RR. Most existing related algorithms, and indeed many MAPF algorithms, fall into the category of fixed F with sub-optimal P. This leaves open the question of how algorithms that are sub-optimal in regard to both F and P would behave. Such an algorithm would map to the empty middle bracket in Table 1. We created a naive implementation of such an algorithm by taking PP-RR and randomising the F every time one is needed to generate a path, as in PPR . In practice, this algorithm behaved similarly to PP-RR, so we did not include it in our results. In another experiment, we approximated how this algorithm would have behaved if, instead of choosing F randomly, it had chosen F to complement the current P. We made this approximation using a computationally expensive, brute-force approach. Our experiment showed that this can significantly improve the performance of PP-RR in both success rate and Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:29 solution quality, for the same number of attempted Ps. We believe finding a computationally efficient function to approximate a near-optimal F choice could be a promising avenue for future work. Naturally, other approaches besides PP-RR could also be applied to create algorithms in this bracket of sub-optimal F with sub-optimal P. The remaining brackets in Table 1, corresponding to the combinations of sub-optimal F with optimal P or of optimal F with sub-optimal P, are hard to define, and their usefulness is questionable. Other directions for future work could be to consider applying speed-up techniques from the CBS family of algorithms to Pa PS, PCS, and PFCS. Additionally, we believe that relaxing the termination criteria of these algorithms can lead to new types of PP algorithms with different tradeoffs and guarantees. Another interesting use for Pa PS would be to use it to generate training data for machine learning algorithms that generate priority orderings (Zhang et al. 2022), as those rely on learning from many examples of priority orderings that produce high-quality solutions. 8 Acknowledgements This work was supported by the Israel Science Foundation (ISF) grant #909/23 awarded to Ariel Felner, the United States-Israel Binational Science Foundation (BSF) grant #2021643 awarded to Ariel Felner, and by BSF grant #2018684 and ISF grant #1238/23 to Roni Stern. Part of this work was performed while Jonathan Morag was on a research visit to Monash University. Research at Monash is partially funded by The Australian Research Council under grant DP200100025 and by a gift from Amazon. A. Andreychuk, K. Yakovlev, P. Surynek, D. Atzmon, and R. Stern. 2022. Multi-agent pathfinding with continuous time. Artificial Intelligence, 305, 103662. D. Atzmon, R. Stern, A. Felner, N. R. Sturtevant, and S. Koenig. 2020. Probabilistic robust multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30, 29 37. D. Atzmon, R. Stern, A. Felner, G. Wagner, R. BartΓ‘k, and N.-F. Zhou. 2020. Robust multi-agent path finding and executing. Journal of Artificial Intelligence Research, 67, 549 579. D. Atzmon, Y. Zax, E. Kivity, L. Avitan, J. Morag, and A. Felner. 2020. Generalizing multi-agent path finding for heterogeneous agents. In: Proceedings of the International Symposium on Combinatorial Search. Vol. 11, 101 105. R. BartΓ‘k, J. Γ­. Ε vancara, and M. Vlk. 2018. A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs. In: Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, 748 756. M. Bennewitz, W. Burgard, and S. Thrun. 2002. Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots. Robotics and autonomous systems, 41, 2-3, 89 99. M. ČÑp, P. NovΓ‘k, A. Kleiner, and M. Seleck y. 2015. Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE transactions on automation science and engineering, 12, 3, 835 849. M. ČÑp, J. VokΕ™Γ­nek, and A. Kleiner. Apr. 2015. Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures. (Apr. 2015). P. S. Daniel Kornhauser Gary Miller. 1984. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: FOCS. R. Dechter and J. Pearl. 1988. The optimality of A*. Springer. M. A. Erdmann and T. Lozano-PΓ©rez. 1986. On multiple moving objects. In: Proceedings of the 1986 IEEE International Conference on Robotics and Automation, San Francisco, California, USA, April 7-10, 1986. IEEE, 1419 1424. doi:10.1109/ROBOT.1986.1087401. P. Godefroid. 1996. Partial-order methods for the verification of concurrent systems: an approach to the state-explosion problem. Springer. P. E. Hart, N. J. Nilsson, and B. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4, 2, 100 107. W. HΓΆnig, T. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, and S. Koenig. 2016. Multi-agent path finding with kinematic constraints. In: Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 26, 477 485. S. Hu, D. D. Harabor, G. Gange, P. J. Stuckey, and N. R. Sturtevant. 2022. Multi-agent path finding with temporal jump point search. In: Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 32, 169 173. J. Li, Z. Chen, D. Harabor, P. Stuckey, and S. Koenig. 2021. Anytime multi-agent path finding via large neighborhood search. In: IJCAI. J. Li, Z. Chen, D. Harabor, P. J. Stuckey, and S. Koenig. 2022. MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search. In: AAAI. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:30 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern J. Li, D. Harabor, P. J. Stuckey, A. Felner, H. Ma, and S. Koenig. 2019. Disjoint splitting for multi-agent path finding with conflict-based search. In: Proceedings of the international conference on automated planning and scheduling. Vol. 29, 279 283. J. Li, D. Harabor, P. J. Stuckey, H. Ma, and S. Koenig. 2019. Symmetry-breaking constraints for grid-based multi-agent path finding. In: Proceedings of the AAAI conference on artificial intelligence 01. Vol. 33, 6087 6095. J. Li, P. Surynek, A. Felner, H. Ma, T. S. Kumar, and S. Koenig. 2019. Multi-agent path finding for large agents. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33, 7627 7634. J. Li, A. Tinka, S. Kiesel, J. W. Durham, T. K. S. Kumar, and S. Koenig. May 2021. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. (May 2021). H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig. 2019. Searching with consistent prioritization for multi-agent path finding. In: AAAI. Vol. 33, 7643 7650. H. Ma, T. S. Kumar, and S. Koenig. 2017. Multi-agent path finding with delay probabilities. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 31. H. Ma, J. Li, T. Kumar, and S. Koenig. Jan. 2017. Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks. (Jan. 2017). J. Morag, A. Felner, R. Stern, D. Atzmon, and E. Boyarski. 2022. Online multi-agent path finding: New results. In: Proceedings of the International Symposium on Combinatorial Search. Vol. 15, 229 233. J. Morag, R. Stern, and A. Felner. 2023. Adapting to planning failures in lifelong multi-agent path finding. In: Proceedings of the International Symposium on Combinatorial Search 1. Vol. 16, 47 55. B. Nebel. 2020. On the computational complexity of multi-agent pathfinding on directed graphs. In: Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30, 212 216. M. Phillips and M. Likhachev. 2011. Sipp: Safe interval path planning for dynamic environments. In: 2011 IEEE international conference on robotics and automation. IEEE, 5628 5635. T. Shahar, S. Shekhar, D. Atzmon, A. Saffidine, B. Juba, and R. Stern. 2021. Safe multi-agent pathfinding with time uncertainty. Journal of Artificial Intelligence Research, 70, 923 954. G. Sharon, R. Stern, A. Felner, and N. Sturtevant. 2012. Meta-agent conflict-based search for optimal multi-agent path finding. In: Proceedings of the International Symposium on Combinatorial Search 1. Vol. 3, 97 104. G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant. 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial intelligence, 219, 40 66. G. Sharon, R. Stern, M. Goldenberg, and A. Felner. 2013. The increasing cost tree search for optimal multi-agent pathfinding. Artificial intelligence, 195, 470 495. B. Shen, Z. Chen, M. A. Cheema, D. D. Harabor, and P. J. Stuckey. 2023. Tracking Progress in Multi-Agent Path Finding. (2023). doi:10.48550/ar Xiv.2305.08446. D. Silver. 2005. Cooperative Pathfinding. In: AIIDE. T. Standley. 2010. Finding optimal solutions to cooperative pathfinding problems. In: Proceedings of the AAAI conference on artificial intelligence 1. Vol. 24, 173 178. R. Stern et al.. 2019. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. In: So CS, 151 158. J. Ε vancara, M. Vlk, R. Stern, D. Atzmon, and R. BartΓ‘k. 2019. Online multi-agent pathfinding. In: Proceedings of the AAAI conference on artificial intelligence. Vol. 33, 7732 7739. J. P. Van Den Berg and M. H. Overmars. 2005. Prioritized motion planning for multiple robots. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 430 435. S. Varambally, J. Li, and S. Koenig. 2022. Which MAPF Model Works Best for Automated Warehousing? In: So CS. https://www.autostoresyst em.com/. T. T. Walker. 2022. Multi-Agent Pathfinding in Mixed Discrete-Continuous Time and Space. Ph.D. Dissertation. University of Denver. J. Yu and S. La Valle. 2013. Structure and intractability of optimal multi-robot path planning on graphs. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 27, 1443 1449. S. Zhang, J. Li, T. Huang, S. Koenig, and B. Dilkina. 2022. Learning a priority ordering for prioritized planning in multi-agent path finding. In: Proceedings of the International Symposium on Combinatorial Search 1. Vol. 15, 208 216. A Complexity Proofs In this section, we provide complexity proofs that were too long to include in the main body of the paper. We adapt ideas from the proofs made by Yu and La Valle (2013) and use the same terminology. Accordingly, π‘₯is used to refer to variable agents rather than time steps, while π‘˜refers to the cost (SOC) of a solution. The following proofs are based on a reduction from 3SAT. 3SAT is an NP-complete problem that receives a formula 𝐹and outputs whether or not the formula is satisfiable. The formula 𝐹is a conjunctive normal form (CNF) consisting of Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:31 𝑛variables π‘₯𝑖and π‘šclauses 𝑐𝑗such that each clause has exactly three literals. Each literal in the clauses can be a negated or unnegated form of a variable. A.1 Proof of Theorem 2 Fig. 11. Reduction from 3SAT to P-MAPF for the instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . The red vertices are the source vertices and the blue vertices are the targets. Theorem 2. The decision problem of whether a prioritised solution exists is NP-hard on directed graphs. Proof. We prove Theorem 2 by a reduction from the 3SAT problem. We create a corresponding P-MAPF problem with 2𝑛+ π‘šagents on a directed graph 𝐺. The set of agents is: 𝐴= {π‘₯1, . . . ,π‘₯𝑛,𝑐1, . . . ,π‘π‘š, 𝑓1, . . . , 𝑓𝑛} The π‘₯𝑖agents are called variable agents, the 𝑐𝑗agents are called clause agents, and the 𝑓𝑖 s are called filler agents. We construct the graph similarly to Yu and La Valle (2013). The most significant difference is that we use a directed graph. First, we construct a simple gadget for each variable π‘₯𝑖called a mouse gadget. For π‘₯𝑖, we create a vertex 𝑣π‘₯𝑖 that represents its source vertex. We connect two vertices to the source vertex through directed edges, and then join these vertices with more directed edges to the target vertex 𝑣 π‘₯𝑖. The agent can traverse through either the top or the bottom paths (vertices) to reach its target. Let these two paths be the 𝑖-th upper and lower paths. This section of the gadget is the body of the mouse. Next, for each clause, we add a clause agent 𝑐𝑗whose source is vertex 𝑣𝑐𝑗. This vertex is connected through directed edges to three paths that represent the literals in the clause of 𝑐𝑗. If a literal is unnegated (resp., negated), then 𝑣𝑐𝑗is connected to the 𝑖-th upper (resp., lower) path in the gadget that belongs to 𝑣π‘₯𝑖. The target vertices for the clause agents are created as follows: A path of length π‘šis added by connecting a directed edge from vertex 𝑣 π‘₯𝑖to the start of the new path. The path itself is comprised only of directed edges. The first vertex in the path is the target vertex of agent π‘π‘š(𝑣 π‘π‘š) followed by the target vertex of agent π‘π‘š 1 (𝑣 π‘π‘š 1) and so on, until the end of the path where the target vertex of agent 𝑐1 (𝑣 𝑐1) is located. We add each filler agent 𝑓𝑖as follows. We create an additional edge (the tail of the mouse) from 𝑣𝑓𝑖, which is the source vertex of 𝑓𝑖, to 𝑣π‘₯𝑖. The target vertex of 𝑓𝑖is 𝑣 𝑓𝑖. We add these target vertices by extending the path of Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:32 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern clause target vertices, connecting 𝑣 𝑐1 to 𝑣 π‘“π‘šwith a directed edge, then 𝑣 π‘“π‘što 𝑣 π‘“π‘š 1 and so on, until the end of the path where the target vertex of agent 𝑓1 (𝑣 𝑓1) is located. Figure 11 shows the complete graph for the P-MAPF problem constructed from 3SAT instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . A red vertex represents the source vertex of an agent, and a blue vertex is the target vertex. The construction we defined limits the set of priority orderings over the agents for which a solution exists. The construction of the filler (𝑓) and clause (𝑐) targets forces the following in order for filler and clause agents not to block each other while sitting at their targets. The filler agents must be ordered according to their index. The clause agents must similarly be ordered according to their index. Additionally, all filler agents must precede all clause agents. Thus, 𝑓1 𝑓2 . . . 𝑓𝑛 𝑐1 𝑐2 π‘π‘š. The positioning of the variable (π‘₯) agents targets forces each variable agent π‘₯𝑖to have lower priority than its corresponding filler agent 𝑓𝑖. Otherwise, the variable agent would enter its target too early and block the filler agent from advancing towards its target. Thus, 𝑖𝑓𝑖 π‘₯𝑖. Each clause agent 𝑐𝑗must have higher priority than at least one variable agent π‘₯𝑖that appears in clause 𝑐𝑗. The specific prioritisation is part of the solution to the problem. If the 3SAT instance is satisfiable, each variable π‘₯𝑖receives an assignment of truth value π‘₯𝑖. If π‘₯𝑖is true (resp., false), then let agent π‘₯𝑖take the lower (resp., upper) path of the body of the mouse gadget. The path that was not chosen is free to transit for the clause and filler agents corresponding to the π‘₯𝑖variable. The filler agents will move through in order of their priority. The path-function will choose for the filler agents to take the upper or lower path according to the π‘₯𝑖assignment (opposite to the path taken by the corresponding variable agent). The clause agents will similarly move in order of their own prioritisation, following the filler agents as soon as they clear a path. Since the assignment satisfies the 3SAT instance, we are guaranteed that each clause agent has at least one path free to transit. The variable agents will move a single step into their paths and wait there, as they are forced to avoid the paths of higher-priority agents. Finally, each variable agent will move into its own target as soon as the relevant filler and clause agents have moved past it. This solution respects a priority that obeys the restrictions listed above. Specifically, the ordering 𝑓1 𝑓2 . . . 𝑓𝑛 𝑐1 𝑐2 π‘π‘š π‘₯1 π‘₯2 π‘₯𝑛 will always be correct. If P-MAPF has a solution, then each clause agent was assigned a path to its target. For each clause agent, there are up to three options for this path, each passing through some gadget corresponding to a variable that appears in the clause. Each variable agent π‘₯𝑖has two possible paths, and is forced to take the path opposite to that taken by its relevant clause and filler agents. If no clause agent passes through the variable agent s gadget, then this choice is determined solely by the filler agent and does not affect whether the assignment satisfies the 3SAT instance. Each filler agent similarly has two possible paths. By choosing a path, it forces the variable agent to advance rather than wait at its source vertex. If agent π‘₯𝑖uses the lower (resp. upper) path, let π‘₯𝑖= π‘‘π‘Ÿπ‘’π‘’(resp. false). Since clause agents can pass through the upper path if they contain a variable π‘₯𝑖or through the lower path if they contain its negation π‘₯𝑖, and each clause agent passed through exactly one such path, then for each clause, at least one variable resolves to true. Thus, the resulting assignment satisfies the 3SAT instance. A.2 Proof of Theorem 3 Theorem 3. The optimisation problem of P-MAPF is NP-hard on undirected graphs. Proof. We prove Theorem 3 by closely following a reduction from the 3SAT problem proposed by Yu and La Valle (2013), and showing it can similarly be used for P-MAPF. To start the reduction, we create a P-MAPF problem corresponding to the 3SAT instance with 𝑛+ π‘šagents on an undirected graph 𝐺. The set of agents is: 𝐴= {π‘₯1, . . . ,π‘₯𝑛,𝑐1, . . . ,π‘π‘š} Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:33 Fig. 12. Reduction from 3SAT to optimal MAPF, for the instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} (Yu and La Valle 2013). The red vertices are the source vertices and the blue vertices are the targets. We apply this reduction to P-MAPF and PFC-MAPF. The π‘₯𝑖agents are called variable agents, the 𝑐𝑗agents are called clause agents. For each variable π‘₯𝑖, we create a vertex 𝑣π‘₯𝑖that represents its source vertex. We connect two paths of length π‘š+ 2 to the source vertex, and join their ends such that the target is at the end vertex 𝑣 π‘₯𝑖. The agent can traverse along either of the two paths to reach its target in π‘š+ 2 steps. Let these two paths be the 𝑖-th upper and lower paths. Next, for each clause, we add a clause agent 𝑐𝑗whose source is vertex 𝑣𝑐𝑗. This vertex is connected to three paths that represent the literals in the clause of 𝑐𝑗. If a literal is unnegated (resp., negated), then 𝑣𝑐𝑗is connected to the 𝑖-th upper (resp., lower) path at a vertex of distance 𝑗from 𝑣π‘₯𝑖. The target vertices for the clause agents are created as follows: A path of length π‘šis added, where one end of the path is connected to the source vertex 𝑣π‘₯𝑖. The connected vertex is the target vertex of agent π‘π‘š(𝑣 π‘π‘š) followed by the target vertex of agent π‘π‘š 1 (𝑣 π‘π‘š 1) and so on, until the end of the path where the target vertex of agent 𝑐1 (𝑣 𝑐1) is located. Figure 12 shows the complete graph for the P-MAPF problem constructed from 3SAT instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . A red vertex represents the source vertex of an agent, and a blue vertex is the target vertex. To prove the difficulty of solving P-MAPF optimally, we must ask the question "does a solution with cost π‘˜ exist for a given P-MAPF problem instance?". We set π‘˜:= (𝑛+ π‘š)(π‘š+ 2), meaning all agents reach their targets without performing any wait actions. If the 3SAT instance is satisfiable, each variable π‘₯𝑖receives an assignment of truth value π‘₯𝑖. There exists a path-function F as follows. If π‘₯𝑖is true (resp., false), then let agent π‘₯𝑖take the lower (resp., upper) path to its target. The path that was not chosen is left unused, or transited in the opposite direction by one or more of the clause agents corresponding to the π‘₯𝑖variable. This means that all variable agents and clause agents can start moving at time step zero and arrive at their targets at time step π‘š+ 2. Thus, any ordering P will produce a solution given F , as no agent takes a path that interferes with the preferred path of another agent. Thus, if the 3SAT instance is satisfiable, the P-MAPF instance has a solution with the optimal cost (𝑛+ π‘š)(π‘š+ 2). If the P-MAPF instance has a solution with cost (𝑛+ π‘š)(π‘š+ 2), then each agent has a path that arrives at its target without waiting. This means each variable agent π‘₯𝑖must move exclusively through either its lower or Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:34 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern upper path, preventing any clause agent 𝑐𝑗from taking the same path in the opposite direction, but leaving the other path free for 𝑐𝑗to traverse. If agent π‘₯𝑖uses the lower (resp. upper) path, let π‘₯𝑖= π‘‘π‘Ÿπ‘’π‘’(resp. false). Thus, the resulting assignment satisfies the 3SAT instance. A.3 Proof of Theorem 6 Fig. 13. Reduction from 3SAT to PFC-MAPF for the instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . The red vertices are the source vertices and the blue vertices are the targets. Theorem 6. The decision problem of whether a PFC-MAPF solution exists is NP-hard on directed graphs. Proof. We prove Theorem 6 by reduction from the 3SAT. To start the reduction, we create a PFC-MAPF problem corresponding to the 3SAT instance with 4π‘šagents on a directed graph 𝐺. The set of agents is: 𝐴= {π‘₯𝑖,𝑗| π‘₯𝑖 𝑐𝑗} { π‘₯𝑖,𝑗| π‘₯𝑖 𝑐𝑗} {𝑐1, . . . ,π‘π‘š} The 𝑐𝑗agents are called clause agents. The π‘₯𝑖,𝑗agents are called unnegated literal agents. The 𝑖index corresponds to the identity of the variable in the 3SAT instance, and the 𝑗index corresponds to the clause where a literal of the π‘₯𝑖variable appears. The π‘₯𝑖,𝑗agents are called negated literal agents, and are the same as the literal agents, except that they correspond to negated literals that appear in clauses. For variables that only appear in their unnegated (resp. negated) form, we only need to create the corresponding unnegated (resp. negated) literal agent. For each clause, we add a clause agent 𝑐𝑗whose source is vertex 𝑣𝑐𝑗. For each unnegated literal agent π‘₯𝑖,𝑗(resp. negated literal agent π‘₯𝑖,𝑗), we create a vertex 𝑣π‘₯𝑖,𝑗(resp. 𝑣 π‘₯𝑖,𝑗) that represents its source vertex. We connect each 𝑣𝑐𝑗to each of the 𝑣π‘₯𝑖,𝑗(resp. 𝑣 π‘₯𝑖,𝑗) vertices corresponding to unnegated (resp. negated) literals in clause 𝑐𝑗. For each variable π‘₯𝑖, we create two sequences of vertices called the π‘₯𝑖sequence and the π‘₯𝑖sequence. The Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:35 number of vertices in each sequence corresponds to the number of unnegated (for the π‘₯𝑖sequence) or negated (for the π‘₯𝑖sequence) literals that exist for variable π‘₯𝑖. Each vertex in sequence π‘₯𝑖(resp. π‘₯𝑖) is the target vertex 𝑣 π‘₯𝑖,𝑗(resp. 𝑣 π‘₯𝑖,𝑗) of an unnegated literal agent π‘₯𝑖,𝑗(resp. negated literal agent π‘₯𝑖,𝑗). These target vertices are sequenced such that the first corresponds to the literal that belongs to the clause with the maximal index 𝑗, and each subsequent target vertex corresponds to a literal that belongs to a clause with a smaller index 𝑗. The edges in the sequence are directed edges. We connect, using a directed edge, each unnegated (resp. negated) literal source vertex 𝑣π‘₯𝑖,𝑗(resp. 𝑣 π‘₯𝑖,𝑗) to the first vertex in both sequence π‘₯𝑖and π‘₯𝑖. For example, if there are 4 literals for variable π‘₯𝑖, π‘₯𝑖,1, π‘₯𝑖,3, π‘₯𝑖,4, and π‘₯𝑖,1, then we will create two sequences of vertices. The sequence of target vertices of unnegated literals will be 𝑣 π‘₯𝑖,4 𝑣 π‘₯𝑖,3 𝑣 π‘₯𝑖,1. The sequence of target vertices of negated literals will consist only of 𝑣 π‘₯𝑖,1. Lastly, we connect the end of each sequence π‘₯𝑖(resp. π‘₯𝑖), again via a directed edge, to a target vertex 𝑣 𝑐𝑗for each clause agent 𝑐𝑗whose clause contains a literal whose target vertex is in π‘₯𝑖(resp. π‘₯𝑖). Note that sequences can be empty, in the event that some variable π‘₯𝑖only has unnegated literals or only has negated literals. In this case, we will connect the vertex 𝑣π‘₯𝑖,𝑗(resp. 𝑣 π‘₯𝑖,𝑗) of the existing literal π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) directly to the clause target vertex 𝑣 𝑐𝑗that would have otherwise been connected to the end of sequence π‘₯𝑖(resp. π‘₯𝑖). Next, we define the path-function F : The construction guarantees that each literal agent will only ever have one shortest path that avoids constraints, so we do not need to define it further for literal agents. Clause agents prefer to traverse a sequence π‘₯𝑖if the complementing π‘₯𝑖sequence has constraints associated with it, and vice versa; i.e., if literal agent π‘₯𝑖,𝑗has already planned when clause agent 𝑐𝑗plans, then the π‘₯𝑖sequence is considered a preferred sequence. Naturally, if a clause agent 𝑐𝑗can reach a sequence that has constraints, then that sequence will not appear as part of a shortest path for 𝑐𝑗. If 𝑐𝑗can move through multiple sequences of the same length whose complementing sequences have constraints, then the sequence with the minimal index (𝑖) among them is preferred. If 𝑐𝑗is not connected to any sequence whose complementing sequence has constraints, then it prefers to take an π‘₯𝑖(unnegated) sequence. If 𝑐𝑗can go through multiple such sequences, it will choose the one with the minimal index (𝑖). The preference towards paths with lower 𝑖is made for completeness, and does not affect the construction. Figure 13 shows the complete graph for the PFC-MAPF problem constructed from 3SAT instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . A red vertex represents the source vertex of an agent, and a blue vertex is the target vertex. If the 3SAT instance is satisfiable, each variable π‘₯𝑖receives an assignment of truth value π‘₯𝑖. There exists a total order P over the agents as follows: All unnegated literal agents associated with a variable receiving a true assignment have the highest priority. All negated literal agents associated with a variable receiving a false assignment similarly have the highest priority. The prioritisation between these two groups is unimportant, but we shall give priority to the unnegated literal agents for convenience. Within each group, higher prioritisation is given to a literal agent with a smaller 𝑗(clause) index. Next in the priority order are all clause agents, and then all remaining literal agents. Within these remaining literal agents, higher prioritisation is given to a literal agent with a smaller 𝑗(clause) index. This describes a partial ordering, but any totalization of this partial ordering will serve our purpose. Formally: P = {{π‘₯𝑖,1 . . . π‘₯𝑖,π‘š| π‘₯𝑖= true} { π‘₯𝑖,1 . . . π‘₯𝑖,π‘š| π‘₯𝑖= false} {𝑐1 . . .π‘π‘š} {π‘₯𝑖,1 . . . π‘₯𝑖,π‘š| π‘₯𝑖= false} { π‘₯𝑖,1 . . . π‘₯𝑖,π‘š| π‘₯𝑖= true}} The basic idea of this proof is that literal agents can only wait at their source vertices, and that once any unnegated (resp. negated) literal agent π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) starts moving, it permanently blocks sequence π‘₯𝑖(resp. π‘₯𝑖). This means any clause agent connected to π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) can only reach its own target through sequence π‘₯𝑖(resp. π‘₯𝑖), or through a literal related to a different variable (if the clause contains such literals). Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:36 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern All unnegated (resp. negated) literal agents associated with a variable receiving a true (resp. false) assignment immediately start moving into their respective sequences of targets. In sequences containing multiple targets, the agents will wait at their source vertex and move into the sequence in increasing order of their 𝑗index. Each clause agent will move through the shortest sequence that it can reach and is not blocked by constraints. Without loss of generality, let us assume one shortest sequence. If some π‘₯𝑖= true (resp. π‘₯𝑖= false) appears in the clause associated with agent 𝑐𝑗, then agent 𝑐𝑗can wait at its source vertex until agent π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) clears vertex 𝑣π‘₯𝑖,𝑗 (resp. 𝑣 π‘₯𝑖,𝑗). Then, 𝑐𝑗can move through sequence π‘₯𝑖(resp. π‘₯𝑖), as the literal agents whose targets appear in sequence π‘₯𝑖(resp. π‘₯𝑖) are still waiting at their source vertices. 𝑐𝑗may have to wait until other clause agents that move through the same sequence clear the first vertex in the sequence, but this will not prevent 𝑐𝑗from reaching its target, only delay it. As soon as all clause agents that move through sequence π‘₯𝑖(resp. π‘₯𝑖) have cleared it, the literal agents π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) that connect to it will start moving into the sequence in order of their 𝑗index. With that, all agents have been assigned paths to their targets. Thus, if the 3SAT instance is satisfiable, the PFC-MAPF instance has a solution. If PFC-MAPF has a solution, then each clause agent was assigned a path to its target. For each clause agent, this path passes through one of (up to) three sequences corresponding to the negated (resp. unnegated) version of an unnegated (resp. negated) literal that appears in the clause. Each literal agent π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) can only reach its target through one sequence of vertices, with the number of wait actions that it will have to perform depending how many clause agents traverse this sequence, and how many other literals have their targets in this sequence. All unnegated (resp. negated) literal agents π‘₯𝑖,𝑗(resp. π‘₯𝑖,𝑗) must have moved into and blocked sequence π‘₯𝑖(resp. π‘₯𝑖) before any clause agent 𝑐𝑗may traverse the complementing sequence π‘₯𝑖(resp. π‘₯𝑖). Therefore, we can see that for every variable π‘₯𝑖, either sequence π‘₯𝑖or π‘₯𝑖(and not both) was traversed by clause agents, giving us an assignment of π‘₯𝑖= false or π‘₯𝑖= true, respectively. For every variable π‘₯𝑖where neither sequence π‘₯𝑖nor π‘₯𝑖 was traversed by any clause agent, any assignment would suffice, so we arbitrarily assign π‘₯𝑖= true. Thus, the resulting assignment satisfies the 3SAT instance. A.4 Proof of Theorem 7 Theorem 7. The optimisation problem of PFC-MAPF is NP-hard on undirected graphs. Proof. We prove Theorem 7 by following a reduction from the 3SAT problem proposed by Yu and La Valle (2013), and showing it can similarly be used for PFC-MAPF. This proof is similar to the proof presented in appendix A.2, except that the path-function F is now handled as part of the reduction. To start the reduction, we create a PFC-MAPF problem corresponding to the 3SAT instance with 𝑛+ π‘šagents on an undirected graph 𝐺. The set of agents is: 𝐴= {π‘₯1, . . . ,π‘₯𝑛,𝑐1, . . . ,π‘π‘š} The π‘₯𝑖agents are called variable agents, the 𝑐𝑗agents are called clause agents. For each variable π‘₯𝑖, we create a vertex 𝑣π‘₯𝑖that represents its source vertex. We connect two paths of length π‘š+ 2 to the source vertex, and join their ends such that the target is at the end vertex 𝑣 π‘₯𝑖. The agent can traverse along either of the two paths to reach its target in π‘š+ 2 steps. Let these two paths be the 𝑖-th upper and lower paths. We will refer to the circuit that each such pair of paths creates as the 𝑖-th gadget. Next, for each clause, we add a clause agent 𝑐𝑗whose source is vertex 𝑣𝑐𝑗. This vertex is connected to three paths that represent the literals in the clause of 𝑐𝑗. If a literal is unnegated (resp., negated), then 𝑣𝑐𝑗is connected to the 𝑖-th upper (resp., lower) path at a vertex of distance 𝑗from 𝑣π‘₯𝑖. The target vertices for the clause agents are created as follows: A path of length π‘šis added, where one end of the path is connected to the source vertex 𝑣π‘₯𝑖. The connected vertex is the target vertex of agent π‘π‘š(𝑣 π‘π‘š) followed by the target vertex of agent π‘π‘š 1 (𝑣 π‘π‘š 1) and so on, until the end of the path where the target vertex of agent 𝑐1 (𝑣 𝑐1) is located. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:37 Lastly, we define the path-function F : We will only regard paths that do not include wait actions, as we only discuss optimal solutions in this proof. We can thus leave F undefined for paths that include wait actions. All variable agents prefer to take the lower path. All clause agents prefer to traverse paths belonging to gadgets that have constraints imposed by the variable agent associated with them; i.e., if variable agent π‘₯𝑖has already planned when the clause agent plans, then the 𝑖-th gadget is considered a preferred gadget. Naturally, if a clause agent 𝑐𝑗 is connected to a path that has constraints, then that path will not appear as a shortest path for 𝑐𝑗. Similarly, if 𝑐𝑗 is connected to both the lower and upper paths of the 𝑖-th gadget, and variable agent π‘₯𝑖has taken the upper (resp. lower) path, then the upper (resp. lower) 𝑐𝑗path will not appear as a shortest path for 𝑐𝑗. 𝑐𝑗will thus traverse the lower (resp. upper) path. If 𝑐𝑗is connected to multiple gadgets with constraints, then the gadget with the minimal index (𝑖) among them is preferred. If 𝑐𝑗is not connected to any gadget with constraints, then it prefers to take a lower path if it is connected to one. Otherwise, it will have to take an upper path. If 𝑐𝑗is connected to multiple lower (resp. upper) paths, it will choose the one with minimal index (𝑖). The preference towards paths with lower 𝑖is made for completeness, and does not affect the construction. Figure 12 shows the complete graph for the PFC-MAPF problem constructed from 3SAT instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . A red vertex represents the source vertex of an agent, and a blue vertex is the target vertex. To prove the difficulty of solving PFC-MAPF optimally, we must ask the question "does a solution with cost π‘˜exist for a given PFC-MAPF problem instance?". We set π‘˜:= (𝑛+ π‘š)(π‘š+ 2), meaning all agents reach their targets without performing any wait actions. If the 3SAT instance is satisfiable, each variable π‘₯𝑖receives an assignment of truth value π‘₯𝑖. There exists a total order P over the agents where all variable agents associated with a true assignment have the highest priority, followed by all clause agents, and then all variable agents associated with a false assignment. This describes a partial ordering, but any totalization of this partial ordering will serve our purpose. Formally: P = {{π‘₯𝑖| π‘₯𝑖= true} {𝑐1 . . .π‘π‘š} {π‘₯𝑖| π‘₯𝑖= false}} All variable agents corresponding to true variables take their lower paths, leaving their upper paths empty, and so those will be traversed by corresponding clause agents. Clause agents that do not connect to the upper path of any true agent must therefore connect to the lower path of at least one variable agent assigned false, since the clause must contain a negation of some π‘₯𝑖= false variable for the 3SAT instance to still be satisfiable. The variable agents assigned false then take upper paths if some clause agent traversed their lower path. Otherwise, they will take the empty lower path. This means that all variable agents and clause agents can start moving at time step zero and arrive at their targets at time step π‘š+ 2. Thus, if the 3SAT instance is satisfiable, the PFC-MAPF instance has a solution with the optimal cost (𝑛+ π‘š)(π‘š+ 2). If the PFC-MAPF instance has a solution with cost (𝑛+ π‘š)(π‘š+ 2), then each agent has a path that arrives at its target without waiting. This means each variable agent π‘₯𝑖must move exclusively through either its lower or upper path, preventing any clause agent 𝑐𝑗from taking the same path in the opposite direction, but leaving the other path free for 𝑐𝑗to traverse. If agent π‘₯𝑖uses the lower (resp. upper) path, let π‘₯𝑖= π‘‘π‘Ÿπ‘’π‘’(resp. false). Thus, the resulting assignment satisfies the 3SAT instance. A.5 Proof of Theorem 8 Theorem 8. The decision problem of whether a priority-constrained solution exists is NP-hard on undirected graphs. Proof. We prove Theorem 8 by a reduction from the 3SAT problem. We create a corresponding PC-MAPF problem with 2𝑛+ π‘šagents on an undirected graph 𝐺. The set of agents is: 𝐴= {π‘₯1, . . . ,π‘₯𝑛,𝑐1, . . . ,π‘π‘š, 𝑓1, . . . , 𝑓𝑛} Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:38 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern Fig. 14. Reduction from 3SAT to PC-MAPF for the instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . The red vertices are the source vertices, and the blue vertices are the targets. The π‘₯𝑖agents are called variable agents, the 𝑐𝑗agents are called clause agents, and the 𝑓𝑖 s are called filler agents. We construct the graph exactly like Yu and La Valle (2013) and expand upon it to prove our theorem. First, we construct a simple gadget for each variable π‘₯𝑖called a mouse gadget. For π‘₯𝑖, we create a vertex 𝑣π‘₯𝑖that represents its source vertex. We connect two paths of length π‘š+ 2 to the source vertex, and join their ends such that the target is at the end vertex 𝑣 π‘₯𝑖. The agent can traverse along either of the two paths to reach its target in π‘š+ 2 steps. Let these two paths be the 𝑖-th upper and lower paths. This section of the gadget is the body of the mouse. We create an additional path of length π‘š+ 2 (the tail of the mouse) such that the last node of the path is 𝑣π‘₯𝑖. We add a filler agent 𝑓𝑖to the first vertex of that path and call it 𝑣𝑓𝑖. The target vertex of 𝑓𝑖is 𝑣π‘₯𝑖. Next, for each clause, we add a clause agent 𝑐𝑗whose source is vertex 𝑣𝑐𝑗. This vertex is connected to three paths that represent the literals in the clause of 𝑐𝑗. If a literal is unnegated (resp., negated), then 𝑣𝑐𝑗is connected to the 𝑖-th upper (resp., lower) path at a vertex of distance 𝑗from 𝑣π‘₯𝑖. The target vertices for the clause agents are created as follows: A path of length π‘šis added, where one end of the path is connected to the source vertex 𝑣π‘₯𝑖. The connected vertex is the target vertex of agent π‘π‘š(𝑣 π‘π‘š) followed by the target vertex of agent π‘π‘š 1 (𝑣 π‘π‘š 1) and so on, until the end of the path where the target vertex of agent 𝑐1 (𝑣 𝑐1) is located. Lastly, we define the total order over the set of agents 𝐴: P = {𝑓1 . . . 𝑓𝑛 π‘₯1 . . . π‘₯𝑛 𝑐1 . . . π‘π‘š} Note that agent 𝑓1 has the highest priority and agent π‘π‘šhas the lowest priority. All filler agents must arrive at their target on time step π‘š+ 2, as they have higher priority over clause and variable agents. Figure 14 shows the complete graph for the PC-MAPF problem constructed from 3SAT instance {π‘₯1,π‘₯2,π‘₯3,π‘₯4}, {(π‘₯1 π‘₯3 π‘₯4) ( π‘₯1 π‘₯2 π‘₯4) ( π‘₯2 π‘₯3 π‘₯4)} . A red vertex represents the source vertex of an agent, and a blue vertex is the target vertex. Note that 𝑣π‘₯𝑖is both red and blue as it is the source vertex of agent π‘₯𝑖and the target vertex of agent 𝑓𝑖. If the 3SAT instance is satisfiable, each variable π‘₯𝑖receives an assignment of truth value π‘₯𝑖. If π‘₯𝑖is true (resp., false), then let agent π‘₯𝑖take the lower (resp., upper) path of the body of the mouse gadget. The path that was not chosen is free to transit for the clause agents corresponding to the π‘₯𝑖variable. This means that all variable agents Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:39 and clause agents can start moving at time step zero and arrive at their targets at time step π‘š+ 2. Thus, vertices 𝑣π‘₯𝑖are free at time step π‘š+ 2 for all agents 𝑓𝑖to arrive at their target. Since all agents can reach their targets within their individually optimal time, they do not violate the total order P. If PC-MAPF has a solution, then all clause agents have an optimal path to their target. Since the filler agents must reach their targets at time step π‘š+ 2 then agent π‘π‘šhas to be at its vertex target 𝑣 π‘π‘šat time step π‘š+ 2 and at time step π‘š+ 1 at one of the vertices 𝑣π‘₯𝑖. Any delay in the arrival of a clause agent π‘π‘šwould prevent it from arriving at vertex 𝑣 π‘π‘šat time step π‘š+ 2, and thus agent π‘π‘šwill be blocked by the filler agents. Variable agents π‘₯𝑖also cannot delay the path of the clause agents, and so they need to choose the opposite path to the clause agents path in the body of the mouse gadget. If agent π‘₯𝑖uses the lower (resp. upper) path, let π‘₯𝑖= π‘‘π‘Ÿπ‘’π‘’(resp. false). Thus, the resulting assignment satisfies the 3SAT instance. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:40 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern B Extended Results 0 25 50 75 100 125 150 175 Coverage up to 60s Berlin_1_256 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 20 40 60 80 100 120 Coverage up to 60s PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s empty-16-16 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s empty-32-32 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s empty-48-48 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s maze-32-32-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 Coverage up to 60s maze-128-128-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s maze-128-128-10 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s random-32-32-10 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s random-32-32-20 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s random-64-64-10 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s random-64-64-20 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s room-64-64-16 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s warehouse-10-20-10-2-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 0 25 50 75 100 125 150 175 200 Coverage up to 60s warehouse-20-40-10-2-1 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS Fig. 15. Additional results for max runtime per instance, as a factor of coverage. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:41 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) Berlin_1_256 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 Number of Agents Coverage (%) PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) empty-16-16 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) empty-32-32 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) empty-48-48 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) random-64-64-20 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) lt_gallowstemplar_n PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) maze-32-32-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) maze-32-32-4 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) maze-128-128-1 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) maze-128-128-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) maze-128-128-10 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) random-32-32-10 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) random-32-32-20 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) random-64-64-10 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) random-64-64-20 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) room-32-32-4 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) room-64-64-8 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) room-64-64-16 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) warehouse-10-20-10-2-1 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) warehouse-10-20-10-2-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) warehouse-20-40-10-2-1 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS 5 10 15 20 25 30 35 40 Number of Agents Coverage (%) warehouse-20-40-10-2-2 PP-RR Pa PS_H1 Pa PS_H2 PCS PFCS Fig. 16. Results for coverage as a factor of the number of agents. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:42 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 2500 5000 7500 10000 1.000 SOC/Best Bound Berlin_1_256 PP-RR Pa PS PCS PFCS 5000 10000 15000 20000 1.000 SOC/Best Bound PP-RR Pa PS PCS PFCS 2500 5000 7500 10000 1.000 SOC/Best Bound PP-RR Pa PS PCS PFCS 100 200 300 400 1.00 SOC/Best Bound empty-16-16 PP-RR Pa PS PCS PFCS 200 400 600 800 1.00 SOC/Best Bound empty-32-32 PP-RR Pa PS PCS PFCS 500 1000 1.00 SOC/Best Bound empty-48-48 PP-RR Pa PS PCS PFCS 1000 2000 3000 4000 1.00 SOC/Best Bound PP-RR Pa PS PCS PFCS 2500 5000 7500 10000 1.000 SOC/Best Bound PP-RR Pa PS PCS PFCS 500 1000 1500 2000 1.000 SOC/Best Bound maze-32-32-2 PP-RR Pa PS PCS PFCS 5000 10000 15000 20000 1.00 SOC/Best Bound maze-128-128-2 PP-RR Pa PS PCS PFCS 2500 5000 7500 10000 1.000 SOC/Best Bound maze-128-128-10 PP-RR Pa PS PCS PFCS 250 500 750 1000 1.00 SOC/Best Bound random-32-32-10 PP-RR Pa PS PCS PFCS 250 500 750 1000 1.00 SOC/Best Bound random-32-32-20 PP-RR Pa PS PCS PFCS 500 1000 1500 2000 1.00 SOC/Best Bound random-64-64-10 PP-RR Pa PS PCS PFCS 500 1000 1500 2000 1.00 SOC/Best Bound random-64-64-20 PP-RR Pa PS PCS PFCS 1000 2000 3000 4000 1.00 SOC/Best Bound room-64-64-16 PP-RR Pa PS PCS PFCS 1000 2000 3000 4000 1.00 SOC/Best Bound warehouse-10-20-10-2-2 PP-RR Pa PS PCS PFCS 2000 4000 6000 8000 1.000 SOC/Best Bound warehouse-20-40-10-2-1 PP-RR Pa PS PCS PFCS Fig. 17. Additional results for the cost of solutions, relative to the best known lower bound on the cost of optimal solutions to the equivalent MAPF problems. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:43 10 20 30 40 Number of Agents 1.000 1.002 1.004 1.006 1.008 1.010 1.012 1.014 1.016 SOC/Best Bound Berlin_1_256 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound PP-RR Pa PS PCS PFCS 10 20 30 Number of Agents SOC/Best Bound PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound empty-16-16 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 SOC/Best Bound empty-32-32 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents 1.000 1.005 1.010 1.015 1.020 1.025 1.030 1.035 SOC/Best Bound empty-48-48 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound random-64-64-20 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents 1.000 1.005 1.010 1.015 1.020 1.025 1.030 1.035 1.040 SOC/Best Bound PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound lt_gallowstemplar_n PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents 1.000 1.025 1.050 1.075 1.100 1.125 1.150 1.175 SOC/Best Bound maze-32-32-2 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound maze-32-32-4 PP-RR Pa PS PCS PFCS 10 20 Number of Agents SOC/Best Bound maze-128-128-1 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound maze-128-128-2 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound maze-128-128-10 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound random-32-32-10 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound random-32-32-20 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound random-64-64-10 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound random-64-64-20 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound room-32-32-4 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound room-64-64-8 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 SOC/Best Bound room-64-64-16 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound warehouse-10-20-10-2-1 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound warehouse-10-20-10-2-2 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents 1.000 1.005 1.010 1.015 1.020 1.025 1.030 1.035 SOC/Best Bound warehouse-20-40-10-2-1 PP-RR Pa PS PCS PFCS 10 20 30 40 Number of Agents SOC/Best Bound warehouse-20-40-10-2-2 PP-RR Pa PS PCS PFCS Fig. 18. Results for the cost of solutions, relative to the best known lower bound on the cost of optimal solutions to the equivalent MAPF problems, as a factor of the number of agents. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:44 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound Berlin_1_256.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved Berlin_1_256.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound Boston_0_256.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved Boston_0_256.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound 1e 5+1 brc202d.map (5 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved brc202d.map (5 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound den312d.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved den312d.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound den520d.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved den520d.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound empty-16-16.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved empty-16-16.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound empty-32-32.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved empty-32-32.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound empty-48-48.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved empty-48-48.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound empty-8-8.map (32 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved empty-8-8.map (32 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound ht_chantry.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved ht_chantry.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound ht_mansion_n.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved ht_mansion_n.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound lak303d.map (30 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved lak303d.map (30 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound lt_gallowstemplar_n.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved lt_gallowstemplar_n.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound maze-128-128-1.map (5 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved maze-128-128-1.map (5 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound maze-128-128-10.map (30 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved maze-128-128-10.map (30 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound maze-128-128-2.map (9 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved maze-128-128-2.map (9 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound maze-32-32-2.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved maze-32-32-2.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound maze-32-32-4.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved maze-32-32-4.map (100 Agents) PP-RR PP-RR-50 Fig. 19. Additional results for suboptimality of solutions and Success Rate of PP-RR with 1 or 50 path-functions, as a factor of the number of orderings attempted. Part 1. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:45 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound ost003d.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved ost003d.map (50 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound Paris_1_256.map (30 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved Paris_1_256.map (30 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound random-32-32-10.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved random-32-32-10.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound random-32-32-20.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved random-32-32-20.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound random-64-64-10.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved random-64-64-10.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound random-64-64-20.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved random-64-64-20.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound room-32-32-4.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved room-32-32-4.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound room-64-64-16.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved room-64-64-16.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound room-64-64-8.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved room-64-64-8.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound warehouse-10-20-10-2-1.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved warehouse-10-20-10-2-1.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound warehouse-10-20-10-2-2.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved warehouse-10-20-10-2-2.map (100 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound warehouse-20-40-10-2-1.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved warehouse-20-40-10-2-1.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound warehouse-20-40-10-2-2.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved warehouse-20-40-10-2-2.map (70 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean SOC / Best Bound w_woundedcoast.map (9 Agents) PP-RR PP-RR-50 0 20 40 60 80 100 120 140 Number of Orderings Mean Solved w_woundedcoast.map (9 Agents) PP-RR PP-RR-50 Fig. 20. Additional results for suboptimality of solutions and Success Rate of PP-RR with 1 or 50 path-functions, as a factor of the number of orderings attempted. Part 2. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. 21:46 Morag, Zhang, Koyfman, Chen, Felner, Harabor & Stern 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound Berlin_1_256.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved Berlin_1_256.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound Boston_0_256.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved Boston_0_256.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound den312d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved den312d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound den520d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved den520d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound empty-16-16.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved empty-16-16.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound empty-32-32.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved empty-32-32.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound empty-48-48.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved empty-48-48.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound empty-8-8.map (32 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved empty-8-8.map (32 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound ht_chantry.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved ht_chantry.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound ht_mansion_n.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved ht_mansion_n.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound lak303d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved lak303d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound lt_gallowstemplar_n.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved lt_gallowstemplar_n.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound maze-128-128-10.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved maze-128-128-10.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound maze-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved maze-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 Fig. 21. Additional results for suboptimality of solutions and Success Rate of PP-RR with 1 or 50 path-functions, as a factor of the number of PP runs attempted. Part 1. Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025. Prioritised Planning: Completeness, Optimality, and Complexity 21:47 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound ost003d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved ost003d.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound random-32-32-10.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved random-32-32-10.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound random-32-32-20.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved random-32-32-20.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound random-64-64-10.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved random-64-64-10.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound random-64-64-20.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved random-64-64-20.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound room-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved room-32-32-4.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound room-64-64-16.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved room-64-64-16.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound room-64-64-8.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved room-64-64-8.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound warehouse-10-20-10-2-1.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved warehouse-10-20-10-2-1.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound warehouse-10-20-10-2-2.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved warehouse-10-20-10-2-2.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound warehouse-20-40-10-2-1.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved warehouse-20-40-10-2-1.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean SOC / Best Bound warehouse-20-40-10-2-2.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 0 50 100 150 200 250 300 Number of PP Runs Mean Solved warehouse-20-40-10-2-2.map (100 Agents) PP-RR PP-RR-2 PP-RR-3 PP-RR-50 Fig. 22. Additional results for suboptimality of solutions and Success Rate of PP-RR with 1 or 50 path-functions, as a factor of the number of PP runs attempted. Part 2. Received 01 June 2025; accepted 06 October 2025 Journal of Artificial Intelligence Research, Vol. 84, Article 21. Publication date: November 2025.