Author name cluster

Jonathan Morag

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AAMAS Conference 2026 Conference Paper

The Reachability Objective in Multi-Agent Path Finding

Noy Gabay
Jonathan Morag
Ariel Felner
Roni Stern

Multi-Agent Path Finding (MAPF) is the problem of path planning for multiple agents while avoiding collisions. In MAPF, each agent must reach a designated target location and stay there. We consider a different objective: each agent must reach its target, but it may move away afterwards. We call this MAPF with Reachability Objective (MAPF-RO). Despite compelling real-world use cases, few prior works have explicitly studied MAPF-RO. We propose several efficient and complete algorithms for MAPF-RO, based on stateof-the-art MAPF algorithms. Experimental results show that using MAPF-RO algorithms instead of classic MAPF algorithms yields huge benefits in terms of runtime and solvability, solving in some cases problems with 1, 000 more agents than baseline approaches. Then, we show a reduction that allows using our MAPF-RO to solve MAPF with Unassigned Agents, a recent practical variant of MAPF in which only a subset of the agents are assigned targets.

PDF

JAIR Journal 2025 Journal Article

Prioritised Planning: Completeness, Optimality, and Complexity

Jonathan Morag
Yue Zhang
Daniel Koyfman
Zhe Chen
Ariel Felner
Daniel Harabor
Roni Stern

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 (PaPS), 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 PaPS 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.

PDF Details DOI

SoCS Conference 2024 Conference Paper

Prioritised Planning with Guarantees

Jonathan Morag
Yue Zhang 0048
Daniel Koyfman
Zhe Chen 0016
Ariel Felner
Daniel Harabor
Roni Stern

Prioritised Planning (PP) is a family of incomplete and sub-optimal algorithms for multi-agent and multi-robot navigation. In PP, agents compute collision-free paths in a fixed order, one at a time. Although fast and usually effective, PP can still fail, leaving users without explanation or recourse. In this work, we give a theoretical and empirical basis for better understanding the underlying problem solved by PP, which we call Priority Constrained MAPF (PC-MAPF). We first investigate the complexity of PC-MAPF and show that the decision problem is NP-hard. We then develop Priority Constrained Search (PCS), a new algorithm that is both complete and optimal with respect to a fixed priority ordering. We experiment with PCS in a range of settings, including comparisons with existing PP baselines, and we give first-known results for optimal PC-MAPF on a popular benchmark set.

Details

SoCS Conference 2023 Conference Paper

Adapting to Planning Failures in Lifelong Multi-Agent Path Finding

Jonathan Morag
Roni Stern
Ariel Felner

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents operating in the same environment. In Lifelong MAPF (LMAPF), these agents continuously receive new destinations, and the task is to constantly update their paths while optimizing for a high throughput over time. Therefore, many MAPF sub-problems must be solved over time in order to solve a single LMAPF problem. LMAPF problems manifest in real-world applications, such as automated warehouses, where strict responsiveness requirements limit the amount of time allocated to planning. MAPF algorithms occasionally fail to produce a plan within the allotted time. We propose a system design for LMAPF that is robust to such planning failures. Then, we explore different approaches to avoid planning failures, reduce their severity, and handle them when they occur. In particular, we describe and analyze different Fail Policies that are applied when planning failures occur and ensure collisions and unnecessary degradation of throughput are avoided. To our knowledge, while such Fail Policies are used in practice in the industry, they have yet to be researched academically.

Details

SoCS Conference 2022 Conference Paper

Online Multi-Agent Path Finding: New Results

Jonathan Morag
Ariel Felner
Roni Stern
Dor Atzmon
Eli Boyarski

Online MAPF extends the classical Multi-Agent Path Finding problem (MAPF) by considering a more realistic problem in which new agents may appear over time. As online solvers are not aware of which agents will join in the future, the notion of snapshot-optimal was defined, where only current knowledge is considered. In this paper, we perform an extensive comparison between oracle-optimal solutions (where the solver is preinformed of future agents), snapshot-optimal solutions, and suboptimal solutions obtained by prioritised planning.

Details

SoCS Conference 2021 Conference Paper

Studying Online Multi-Agent Path Finding

Jonathan Morag
Roni Stern
Ariel Felner
Dor Atzmon
Eli Boyarski

Multi-agent path finding (MAPF) is the problem of planning a set of non-conflicting plans on a graph, for a set of agents. Online MAPF extends MAPF by considering a more realistic problem in which new agents may appear over time. While planning, an online solver does not know whether and which agents will join in the future. Therefore, in online problems the notion of snapshot-optimal was defined, where only current knowledge is considered. The quality of such a solution may be weaker than the quality of a solution to an equivalent offline MAPF problem (offline-optimality), where the solver is preinformed of all the agents that will appear in the future. In this paper we explore, theoretically and empirically, the quality of snapshot-optimal solutions compared to offline-optimal solutions.

Details

SoCS Conference 2020 Conference Paper

Generalizing Multi-Agent Path Finding for Heterogeneous Agents

Dor Atzmon
Yonathan Zax
Einat Kivity
Lidor Avitan
Jonathan Morag
Ariel Felner

Multi-Agent Path Finding (MAPF) is the problem of finding non-colliding paths for multiple agents. The classical problem assumes that all agents are homogeneous, with a fixed size and behavior. However, in reality agents are heterogeneous, with different sizes and behaviors. In this paper, we generalize MAPF to G-MAPF for the case of heterogeneous agents. We then show how two previous settings of large agents and k-robust agents are special cases of G-MAPF. Finally, we introduce G-CBS, a variant of the Conflict-Based Search (CBS) algorithm for G-MAPF, which does not cause significant extra overhead.

Details