Arrow Research search

Author name cluster

Jiaoyang Li

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.

43 papers
1 author row

Possible papers

43

AAAI Conference 2026 Conference Paper

BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs

  • Yifan Su
  • Rishi Veerapaneni
  • Jiaoyang Li

Multi-Agent Path Finding (MAPF) requires computing collision-free paths for multiple agents in shared environment. Most MAPF planners assume that each agent reaches a specific location at a specific timestep, but this is infeasible to directly follow on real systems where delays often occur. To address collisions caused by agents deviating due to delays, the Temporal Plan Graph (TPG) was proposed, which converts a MAPF time dependent solution into a time independent set of inter-agent dependencies. Recently, a Bidirectional TPG (BTPG) was proposed which relaxed some dependencies into "bidirectional pairs" and improved efficiency of agents executing their MAPF solution with delays. Our work improves upon this prior work by designing an algorithm, BPTG-max, that finds more bidirectional pairs. Our main theoretical contribution is in designing the BTPG-max algorithm is locally optimal, i.e. which constructs a BTPG where no additional bidirectional pairs can be added. We also show how in practice BTPG-max leads to BTPGs with significantly more bidirectional edges, superior anytime behavior, and improves robustness to delays.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees

  • Tiannan Zhang
  • Rishi Veerapaneni
  • Shao-Hung Chan
  • Jiaoyang Li
  • Maxim Likhachev

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for a team of agents. Although several MAPF methods that solve full-horizon MAPF have completeness guarantees, very few MAPF methods that plan partial paths have completeness guarantees. Recent work introduced the Windowed Complete MAPF (WinC-MAPF) framework, which shows how windowed optimal MAPF solvers (e.g., SS-CBS) can use heuristic updates and disjoint agent groups to maintain completeness even when planning partial paths. A core limitation of WinC-MAPF is that it requires optimal MAPF solvers. Our main contribution is to extend WinC-MAPF by showing how we can use a bounded suboptimal solver while maintaining completeness. In particular, we design Dynamic Agent Grouping ECBS (DAG-ECBS) which dynamically creates and plans agent groups while maintaining that each agent group solution is bounded suboptimal. We prove how DAG-ECBS can maintain completeness in the WinC-MAPF framework and can improve scalability compared to windowed ECBS which does not have completeness guarantees. More broadly, our work serves as a blueprint for designing more MAPF methods that can use the WinC-MAPF framework

PDF Details DOI

AAAI Conference 2026 Conference Paper

FANoise: Singular Value-Adaptive Noise Modulation for Robust Multimodal Representation Learning

  • Jiaoyang Li
  • Jun Fang
  • Tianhao Gao
  • Xiaohui Zhang
  • Zhiyuan Liu
  • Chao Liu
  • Pengzhang Liu
  • Qixia Jiang

Representation learning is fundamental to modern machine learning, powering applications such as text retrieval and multimodal understanding. However, learning robust and generalizable representations remains challenging. While prior work has demonstrated that active noise injection, a form of data augmentation, can enhance encoding performance, most existing methods rely on heuristic or static noise, overlooking the dynamic nature of feature distributions during training. In this work, we systematically study the role of noise in representation learning from both gradient-based and feature distribution perspectives, using InfoNCE loss as a representative example. Focusing on multimodal representation learning, we propose FANoise, a novel feature-adaptive noise injection strategy. By leveraging the dynamics of contrastive learning, FANoise effectively mitigates the negative impacts of noise while preserving its benefits. Under this theoretically grounded framework, comprehensive experiments demonstrate that FANoise consistently improves overall performance on multimodal tasks across various base VLM models.

PDF Details DOI

AAMAS Conference 2026 Conference Paper

QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps

  • Cheng Qian
  • Yulun Zhang
  • Varun Bhatt
  • Matthew C. Fontaine
  • Stefanos Nikolaidis
  • Jiaoyang Li

We use the Quality Diversity (QD) algorithm with Neural Cellular Automata (NCA) to automatically evaluate Multi-Agent Path Finding (MAPF) algorithms by generating diverse maps. Previously, researchers typically evaluate MAPF algorithms on a set of specific, human-designed maps at their initial stage of algorithm design. However, such fixed maps may not cover all scenarios, and algorithms may overfit to the small set of maps. To seek further improvements, systematic evaluations on a diverse suite of maps are needed. In this work, we propose Quality-Diversity Multi-Agent Path Finding Performance EvaluatoR (QD-MAPPER), a general framework that takes advantage of the QD algorithm to comprehensively understand the performance of MAPF algorithms by generating maps with patterns, be able to make fair comparisons between two MAPF algorithms, providing further information on the selection between two algorithms and on the design of the algorithms. Empirically, we employ this technique to evaluate and comparethebehaviorofdifferenttypesofMAPFalgorithms, including search-based, priority-based, rule-based, and learning-based algorithms. Through both single-algorithm experiments and comparisons between algorithms, researchers can identify patterns that each MAPF algorithm excels and detect disparities in runtime or success rates between different algorithms. Our generated maps are available at https: //airtclick. github. io/qdmapper. Our code is available at https: //github. com/AirTClick/QD-MAPPER.

PDF

AAAI Conference 2025 Conference Paper

LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding

  • Yutong Wang
  • Tanishq Duhan
  • Jiaoyang Li
  • Guillaume Sartoretti

Multi-Agent Path Finding (MAPF) is a critical component of logistics and warehouse management, which focuses on planning collision-free paths for a team of robots in a known environment. Recent work introduced a novel MAPF approach, LNS2, which proposed to repair a quickly-obtainable set of infeasible paths via iterative re-planning, by relying on a fast, yet lower-quality, priority-based planner. At the same time, there has been a recent push for Multi-Agent Reinforcement Learning (MARL) based MAPF algorithms, which let agents learn decentralized policies that exhibit improved cooperation over such priority planning, although inevitably remaining slower. In this paper, we introduce a new MAPF algorithm, LNS2+RL, which combines the distinct yet complementary characteristics of LNS2 and MARL to effectively balance their individual limitations and get the best from both worlds. During early iterations, LNS2+RL relies on MARL for low-level re-planning, which we show eliminates collisions much more than a priority-based planner. There, our MARL-based planner allows agents to reason about past and future/predicted information to gradually learn cooperative decision-making through a finely designed curriculum learning. At later stages of planning, LNS2+RL adaptively switches to priority-based planning to quickly resolve the remaining collisions, naturally trading-off solution quality and computational efficiency. Our comprehensive experiments on challenging tasks across various team sizes, world sizes, and map structures consistently demonstrate the superior performance of LNS2+RL compared to many MAPF algorithms, including LNS2, LaCAM, and EECBS. In maps with complex structures, the advantages of LNS2+RL are particularly pronounced, with LNS2+RL achieving a success rate of over 50% in nearly half of the tested tasks, while that of LaCAM and EECBS falls to 0%.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Multi-Agent Motion Planning for Differential Drive Robots Through Stationary State Search

  • Jingtian Yan
  • Jiaoyang Li

Multi-Agent Motion Planning (MAMP) finds various applications in fields such as traffic management, airport operations, and warehouse automation. In many of these environments, differential drive robots are commonly used. These robots have a kinodynamic model that allows only in-place rotation and movement along their current orientation, subject to speed and acceleration limits. However, existing Multi-Agent Path Finding (MAPF)-based methods often use simplified models for robot kinodynamics, which limits their practicality and realism. In this paper, we introduce a three-level framework called MASS to address these challenges. MASS combines MAPF-based methods with our proposed stationary state search planner to generate high-quality kinodynamically-feasible plans. We further extend MASS using an adaptive window mechanism to address the lifelong MAMP problem. Empirically, we tested our methods on the single-shot grid map domain and the lifelong warehouse domain. Our method shows up to 400% improvements in terms of throughput compared to existing methods.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

  • Hongzhi Zang
  • Yulun Zhang
  • He Jiang
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Jiaoyang Li

We study the problem of optimizing a guidance policy capable of dynamically guiding the agents for lifelong Multi-Agent Path Finding based on real-time traffic patterns. Multi-Agent Path Finding (MAPF) focuses on moving multiple agents from their starts to goals without collisions. Its lifelong variant, LMAPF, continuously assigns new goals to agents. In this work, we focus on improving the solution quality of PIBT, a state-of-the-art rule-based LMAPF algorithm, by optimizing a policy to generate adaptive guidance. We design two pipelines to incorporate guidance in PIBT in two different ways. We demonstrate the superiority of the optimized policy over both static guidance and human-designed policies. Additionally, we explore scenarios where task distribution changes over time, a challenging yet common situation in real-world applications that is rarely explored in the literature.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Speedup Techniques for Switchable Temporal Plan Graph Optimization

  • He Jiang
  • Muhan Lin
  • Jiaoyang Li

Multi-Agent Path Finding (MAPF) focuses on planning collision-free paths for multiple agents. However, during the execution of a MAPF plan, agents may encounter unexpected delays, which can lead to inefficiencies, deadlocks, or even collisions. To address these issues, the Switchable Temporal Plan Graph provides a framework for finding an acyclic Temporal Plan Graph with the minimum execution cost under delays, ensuring deadlock- and collision-free execution. Unfortunately, existing optimal algorithms, such as Mixed Integer Linear Programming and Graph-Based Switchable Edge Search (GSES), are often too slow for practical use. This paper introduces Improved GSES, which significantly accelerates GSES through four speedup techniques: stronger admissible heuristics, edge grouping, prioritized branching, and incremental implementation. Experiments conducted on four different map types with varying numbers of agents demonstrate that Improved GSES consistently achieves over twice the success rate of GSES and delivers up to a 30-fold speedup on instances where both methods successfully find solutions.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Windowed MAPF with Completeness Guarantees

  • Rishi Veerapaneni
  • Muhammad Suhail Saleem
  • Jiaoyang Li
  • Maxim Likhachev

Traditional multi-agent path finding (MAPF) methods try to compute entire collision free start-goal paths, with several algorithms offering completeness guarantees. However, computing partial paths offers significant advantages including faster planning, adaptability to changes, and enabling decentralized planning. Methods that compute partial paths employ a "windowed" approach and only try to find collision free paths for a limited timestep horizon. While this improves flexibility, this adaptation introduces incompleteness; all existing windowed approaches can become stuck in deadlock or livelock. Our main contribution is to introduce our framework, WinC-MAPF, for Windowed MAPF that enables completeness. Our framework leverages heuristic update insights from single-agent real-time heuristic search algorithms and agent independence ideas from MAPF algorithms. We also develop Single-Step Conflict Based Search (SS-CBS), an instantiation of this framework using a novel modification to CBS. We show how SS-CBS, which only plans a single step and updates heuristics, can effectively solve tough scenarios where existing windowed approaches fail.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution

  • Yifan Su
  • Rishi Veerapaneni
  • Jiaoyang Li

The Multi-Agent Path Finding (MAPF) problem involves planning collision-free paths for multiple agents in a shared environment. The majority of MAPF solvers rely on the assumption that an agent can arrive at a specific location at a specific timestep. However, real-world execution uncertainties can cause agents to deviate from this assumption, leading to collisions and deadlocks. Prior research solves this problem by having agents follow a Temporal Plan Graph (TPG), enforcing a consistent passing order at every location as defined in the MAPF plan. However, we show that TPGs are overly strict because, in some circumstances, satisfying the passing order requires agents to wait unnecessarily, leading to longer execution time. To overcome this issue, we introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG), which allows switching passing orders during execution to avoid unnecessary waiting time. We design two anytime algorithms for constructing a BTPG: BTPG-naïve and BTPG-optimized. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

  • Yulun Zhang
  • He Jiang
  • Varun Bhatt
  • Stefanos Nikolaidis
  • Jiaoyang Li

We study how to use guidance to improve the throughput of lifelong Multi-Agent Path Finding (MAPF). Previous studies have demonstrated that, while incorporating guidance, such as highways, can accelerate MAPF algorithms, this often results in a trade-off with solution quality. In addition, how to generate good guidance automatically remains largely unexplored, with current methods falling short of surpassing manually designed ones. In this work, we introduce the guidance graph as a versatile representation of guidance for lifelong MAPF, framing Guidance Graph Optimization as the task of optimizing its edge weights. We present two GGO algorithms to automatically generate guidance for arbitrary lifelong MAPF algorithms and maps. The first method directly optimizes edge weights, while the second method optimizes an update model capable of generating edge weights. Empirically, we show that (1) our guidance graphs improve the throughput of three representative lifelong MAPF algorithms in eight benchmark maps, and (2) our update model can generate guidance graphs for as large as 93 x 91 maps and as many as 3, 000 agents. We include the source code at: https: //github. com/lunjohnzhang/ggo_public. All optimized guidance graphs are available online at: https: //yulunzhang. net/publication/zhang2024ggo.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints

  • Yu Quan Chong
  • Jiaoyang Li
  • Katia Sycara

This paper examines the Task Assignment and Path Finding with Precedence and Temporal Constraints (TAPF-PTC) problem. We augment Conflict-Based Search (CBS) to generate task assignments and collision-free paths that adhere to precedence and temporal constraints for agents to maximize a user-defined objective.

PDF

IJCAI Conference 2024 Conference Paper

Scalable Mechanism Design for Multi-Agent Path Finding

  • Paul Friedrich
  • Yulun Zhang
  • Michael Curry
  • Ludwig Dierks
  • Stephen McAleer
  • Jiaoyang Li
  • Tuomas Sandholm
  • Sven Seuken

Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. This problem is computationally complex, especially when dealing with large numbers of agents, as is common in realistic applications like autonomous vehicle coordination. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. Adding to the complexity, agents might act in a self-interested and strategic way, possibly misrepresenting their goals to the MAPF algorithm if it benefits them. Although the field of mechanism design offers tools to align incentives, using these tools without careful consideration can fail when only having access to approximately optimal outcomes. In this work, we introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms. We test our mechanisms on realistic MAPF domains with problem sizes ranging from dozens to hundreds of agents. We find that they improve welfare beyond a simple baseline.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding

  • Zhe Chen
  • Daniel Harabor
  • Jiaoyang Li
  • Peter J. Stuckey

Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Although many works appear on this topic, all current algorithms struggle as the number of agents grows. The principal reason is that existing approaches typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations. Empirically, we report large improvements in solution quality for one-short MAPF and in overall throughput for lifelong MAPF.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Arbitrarily Scalable Environment Generators via Neural Cellular Automata

  • Yulun Zhang
  • Matthew Fontaine
  • Varun Bhatt
  • Stefanos Nikolaidis
  • Jiaoyang Li

We study the problem of generating arbitrarily large environments to improve the throughput of multi-robot systems. Prior work proposes Quality Diversity (QD) algorithms as an effective method for optimizing the environments of automated warehouses. However, these approaches optimize only relatively small environments, falling short when it comes to replicating real-world warehouse sizes. The challenge arises from the exponential increase in the search space as the environment size increases. Additionally, the previous methods have only been tested with up to 350 robots in simulations, while practical warehouses could host thousands of robots. In this paper, instead of optimizing environments, we propose to optimize Neural Cellular Automata (NCA) environment generators via QD algorithms. We train a collection of NCA generators with QD algorithms in small environments and then generate arbitrarily large environments from the generators at test time. We show that NCA environment generators maintain consistent, regularized patterns regardless of environment size, significantly enhancing the scalability of multi-robot systems in two different domains with up to 2, 350 robots. Additionally, we demonstrate that our method scales a single-agent reinforcement learning policy to arbitrarily large environments with similar patterns. We include the source code at https: //github. com/lunjohnzhang/warehouse env gen nca public.

PDF Details

AIJ Journal 2023 Journal Article

Conflict-tolerant and conflict-free multi-agent meeting

  • Dor Atzmon
  • Ariel Felner
  • Jiaoyang Li
  • Shahaf Shperberg
  • Nathan Sturtevant
  • Sven Koenig

In the Multi-Agent Meeting problem (MAM), the task is to find the optimal meeting location for multiple agents, as well as a path for each agent to that location. Among all possible meeting locations, the optimal meeting location has the minimum cost according to a given cost function. Two cost functions are considered in this research: (1) the sum of all agents paths' costs to the meeting location (SOC) and (2) the cost of the longest path among them (MKSP). MAM has many real-life applications, such as choosing a gathering point for multiple traveling agents (humans, cars, or robots). In this paper, we divide MAM into two variants. In its basic version, MAM allows multiple agents to occupy the same location, i. e. , it is conflict tolerant. For MAM, we introduce MM*, a Multi-Directional Heuristic Search algorithm, that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed for MM*, and experiments demonstrate the benefits of MM*. As agents may be embodied in the world, a solution to MAM may contain conflicting paths, where more than one agent occupies the same location at the same time. The second variant of the MAM problem is called Conflict-Free Multi-Agent Meeting (CF-MAM), where the task is to find the optimal meeting location for multiple agents (as in MAM) as well as conflict-free paths (in the same manner as the prominent Multi-Agent Path Finding problem (MAPF)) to that location. For optimally solving CF-MAM, we introduce two novel algorithms, which combine MAM and MAPF solvers. We prove the optimality of both algorithms and compare them experimentally, showing the pros and cons of each algorithm. 1

Details DOI

AAAI Conference 2023 Conference Paper

Intelligent Planning for Large-Scale Multi-Robot Coordination

  • Jiaoyang Li

Robots will play a crucial role in the future and need to work as a team in increasingly more complex applications. Advances in robotics have laid the hardware foundations for building large-scale multi-robot systems. But how to coordinate robots intelligently is a difficult problem. We believe that graph-search-based planning can systematically exploit the combinatorial structure of multi-robot coordination problems and efficiently generate solutions with rigorous guarantees on correctness, completeness, and solution quality. We started with one problem that is central to many multi-robot applications. Multi-Agent Path Finding (MAPF) is an NP-hard problem of planning collision-free paths for a team of agents while minimizing their travel times. We addressed the MAPF problem from both (1) a theoretical perspective by developing efficient algorithms to solve large MAPF instances with completeness and optimality guarantees via a variety of AI and optimization technologies, such as constraint reasoning, heuristic search, stochastic local search, and machine learning, and (2) an applicational perspective by developing algorithmic techniques for integrating MAPF with task planning and execution for various multi-robot systems, such as mobile robot coordination, traffic management, drone swarm control, multi-arm assembly, and character control in video games. This paper is part of the AAAI-23 New Faculty Highlights.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Intersection Coordination with Priority-Based Search for Autonomous Vehicles

  • Jiaoyang Li
  • The Anh Hoang
  • Eugene Lin
  • Hai L. Vu
  • Sven Koenig

The development of connected and autonomous vehicles opens an opportunity to manage intersections without signals. One promising approach is to use a central autonomous intersection manager to optimize the movement of the vehicles in the intersection. Existing work uses Mixed Integer Linear Programming (MILP) to find optimal solutions for this problem but is time-consuming and cannot be applied in real-time. On the other hand, the coordination of the vehicles is essentially a Multi-Agent Path Finding (MAPF) problem, for which dozens of efficient algorithms have been proposed in recent years. Inspired by these MAPF algorithms, we propose a three-level algorithm called PSL to solve the intersection coordination problem. Theoretically, PSL is complete and polynomial-time in the number of vehicles. Empirically, PSL runs significantly faster with only a slight compromise in the solution quality than the optimal MILP method. It also generates significantly better solutions with a slightly larger runtime than the traditional First-Come-First-Served strategy.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Multi-Robot Coordination and Layout Design for Automated Warehousing

  • Yulun Zhang
  • Matthew C. Fontaine
  • Varun Bhatt
  • Stefanos Nikolaidis
  • Jiaoyang Li

With the rapid progress in Multi-Agent Path Finding (MAPF), researchers have studied how MAPF algorithms can be deployed to coordinate hundreds of robots in large automated warehouses. While most works try to improve the throughput of such warehouses by developing better MAPF algorithms, we focus on improving the throughput by optimizing the warehouse layout. We show that, even with state-of-the-art MAPF algorithms, commonly used human-designed layouts can lead to congestion for warehouses with large numbers of robots and thus have limited scalability. We extend existing automatic scenario generation methods to optimize warehouse layouts. Results show that our optimized warehouse layouts (1) reduce traffic congestion and thus improve throughput, (2) improve the scalability of the automated warehouses by doubling the number of robots in some cases, and (3) are capable of generating layouts with user-specified diversity measures.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Anytime Multi-Agent Path Finding via Machine Learning-Guided Large Neighborhood Search

  • Taoan Huang
  • Jiaoyang Li
  • Sven Koenig
  • Bistra Dilkina

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for a team of agents in a common environment. MAPF is NP-hard to solve optimally and, in some cases, also bounded-suboptimally. It is thus timeconsuming for (bounded-sub)optimal solvers to solve large MAPF instanc¡es. Anytime algorithms find solutions quickly for large instances and then improve them to close-to-optimal ones over time. In this paper, we improve the current state-ofthe-art anytime solver MAPF-LNS, that first finds an initial solution fast and then repeatedly replans the paths of subsets of agents via Large Neighborhood Search (LNS). It generates the subsets of agents for replanning by randomized destroy heuristics, but not all of them increase the solution quality substantially. We propose to use machine learning to learn how to select a subset of agents from a collection of subsets, such that replanning increases the solution quality more. We show experimentally that our solver, MAPF-ML-LNS, significantly outperforms MAPF-LNS on the standard MAPF benchmark set in terms of both the speed of improving the solution and the final solution quality.

PDF Details

AAAI Conference 2022 Conference Paper

Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding

  • Shao-Hung Chan
  • Jiaoyang Li
  • Graeme Gange
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents that minimize the sum of path costs. EECBS is a leading two-level algorithm that solves MAPF bounded-suboptimally, that is, within some factor w of the minimum sum of path costs C∗. It uses focal search to find bounded-suboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. EES keeps track of a lower bound LB on C∗ to find paths whose sum of path costs is at most w · LB in order to solve MAPF bounded-suboptimally. However, the costs of many paths are often much smaller than w times their minimum path costs, meaning that the sum of path costs is much smaller than w ·C∗. In this paper, we therefore propose Flexible EECBS (FEECBS), which uses a flex(ible) distribution of the path costs (that relaxes the requirement to find bounded-suboptimal paths on the low level) in order to reduce the number of collisions that need to be resolved on the high level while still guaranteeing to solve MAPF bounded suboptimally. We address the drawbacks of flex distribution via techniques such as restrictions on the flex distribution, restarts of the high-level search with EECBS, and low-level focal-A* search. Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.

PDF Details

AAAI Conference 2022 Conference Paper

MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search

  • Jiaoyang Li
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of planning collision-free paths for multiple agents in a shared environment. In this paper, we propose a novel algorithm MAPF- LNS2 based on large neighborhood search for solving MAPF efficiently. Starting from a set of paths that contain collisions, MAPF-LNS2 repeatedly selects a subset of colliding agents and replans their paths to reduce the number of collisions until the paths become collision-free. We compare MAPF- LNS2 against a variety of state-of-the-art MAPF algorithms, including Prioritized Planning with random restarts, EECBS, and PPS, and show that MAPF-LNS2 runs significantly faster than them while still providing near-optimal solutions in most cases. MAPF-LNS2 solves 80% of the random-scenario instances with the largest number of agents from the MAPF benchmark suite with a runtime limit of just 5 minutes, which, to our knowledge, has not been achieved by any existing algorithms.

PDF Details

AAMAS Conference 2022 Conference Paper

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences

  • Han Zhang
  • Jingkai Chen
  • Jiaoyang Li
  • Brian C. Williams
  • Sven Koenig

With the rising demand for deploying robot teams in autonomous warehouses and factories, the Multi-Agent Path Finding (MAPF) problem has drawn more and more attention. The classical MAPF problem and most of its variants focus on navigating agent teams to goal locations while avoiding collisions. However, they do not take into account any precedence constraints that agents should respect when reaching their goal locations. Planning with precedence constraints is important for real-world multi-agent systems. For example, a mobile robot can only pick up a package at a station after it has been delivered by another robot. In this paper, we study the Multi-Agent Path Finding with Precedence Constraints (MAPF-PC) problem, in which agents need to visit sequences of goal locations while satisfying precedence constraints between the goal locations. We propose two algorithms for solving this problem systematically: Conflict-Based Search with Precedence Constraints (CBS-PC) is complete and optimal, and Priority-Based Search with Precedence Constraints (PBS-PC) is incomplete but more efficient in finding near-optimal solutions in practice. Our experimental results show that CBS-PC scales to dozens of agents and hundreds of goal locations and precedence constraints, and PBS-PC scales to hundreds of agents, around one thousand goal locations, and hundreds of precedence constraints.

PDF

AIJ Journal 2022 Journal Article

Multi-agent path finding with mutex propagation

  • Han Zhang
  • Jiaoyang Li
  • Pavel Surynek
  • T.K. Satish Kumar
  • Sven Koenig

Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in CBS, a popular optimal search-based MAPF algorithm, as well as in MDD-SAT, an optimal satisfiability-based MAPF algorithm. Mutex propagation provides CBS with the ability to break symmetries in MAPF and provides MDD-SAT with the ability to make stronger inferences than unit propagation. While existing work identifies a limited form of symmetries and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH-RCT, a state-of-the-art variant of CBS, with respect to the success rate. We also show that MDD-SAT with mutex propagation often performs better than MDD-SAT with respect to the success rate.

Details DOI

AAAI Conference 2022 Conference Paper

Shard Systems: Scalable, Robust and Persistent Multi-Agent Path Finding with Performance Guarantees

  • Christopher Leet
  • Jiaoyang Li
  • Sven Koenig

Modern multi-agent robotic systems increasingly require scalable, robust and persistent Multi-Agent Path Finding (MAPF) with performance guarantees. While many MAPF solvers that provide some of these properties exist, none provides them all. To fill this need, we propose a new MAPF framework, the shard system. A shard system partitions the workspace into geographic regions, called shards, linked by a novel system of buffers. Agents are routed optimally within a shard by a local controller to local goals set by a global controller. The buffer system novelly allows shards to plan with perfect parallelism, providing scalability. A novel global controller algorithm can rapidly generate an inter-shard routing plan for thousands of agents while minimizing the traffic routed through any shard. A novel workspace partitioning algorithm produces shards small enough to replan rapidly. These innovations allow a shard system to adjust its routing plan in real time if an agent is delayed or assigned a new goal, enabling robust, persistent MAPF. A shard system’s local optimality and optimized inter-shard routing bring the sum-ofcosts of its solutions to single-shot MAPF problems to between 25% and 70% of optimal on a diversity of workspaces. Its scalability allows it to plan paths for thousands of agents in seconds. If any of their goals change or move actions fails, a shard system can replan in under a second.

PDF Details

IJCAI Conference 2021 Conference Paper

Anytime Multi-Agent Path Finding via Large Neighborhood Search

  • Jiaoyang Li
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for multiple agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms that can solve large problems but usually find low-quality solutions. In this paper, we consider a third approach that combines the best of both worlds: anytime algorithms that quickly find an initial solution using efficient MAPF algorithms from the literature, even for large problems, and that subsequently improve the solution quality to near-optimal as time progresses by replanning subgroups of agents using Large Neighborhood Search. We compare our algorithm MAPF-LNS against a range of existing work and report significant gains in scalability, runtime to the initial solution, and speed of improving the solution.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Anytime Multi-Agent Path Finding via Large Neighborhood Search

  • Jiaoyang Li
  • Zhe Chen
  • Daniel Harabor
  • Peter J. Stuckey
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for a cooperative team of moving agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms (including prioritized and rule-based algorithms) that can solve very large practical problems but usually find low-quality solutions. In this paper, we consider a third approach that combines both advantages: anytime algorithms that quickly find an initial solution, including for large problems, and that subsequently improve the solution to near-optimal as time progresses. To improve the solution, we replan subsets of agents using Large Neighborhood Search, a popular meta-heuristic often applied in combinatorial optimization. Empirically, we compare our algorithm MAPF-LNS to the state-of-the-art anytime MAPF algorithm anytime BCBS and report significant gains in scalability, runtime to the first solution, and speed of improving solutions.

PDF

AAAI Conference 2021 Conference Paper

EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

  • Jiaoyang Li
  • Wheeler Ruml
  • Sven Koenig

Multi-Agent Path Finding (MAPF), i. e. , finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a leading two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.

PDF Details

AAAI Conference 2021 Conference Paper

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

  • Jiaoyang Li
  • Andrew Tinka
  • Scott Kiesel
  • Joseph W. Durham
  • T. K. Satish Kumar
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF, where agents are constantly engaged with new goal locations, such as in large-scale automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1, 000 agents (= 38. 9% of the empty cells on the map) for simulated warehouse instances, significantly outperforming existing work.

PDF Details

AIJ Journal 2021 Journal Article

Pairwise symmetry reasoning for multi-agent path finding search

  • Jiaoyang Li
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma
  • Graeme Gange
  • Sven Koenig

Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that asks us to plan collision-free paths for a team of cooperative agents. In this work, we show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry, which occurs when two agents have many different paths to their target locations, all of which appear promising, but every combination of them results in a collision. We identify several classes of pairwise symmetries and show that each one arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for current state-of-the-art (bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints to eliminate all permutations of pairwise colliding paths in a single branching step. We implement these ideas in the context of a leading optimal MAPF algorithm CBS and show that the addition of the symmetry reasoning techniques can have a dramatic positive effect on its performance — we report a reduction in the number of node expansions by up to four orders of magnitude and an increase in scalability by up to thirty times. These gains allow us to solve to optimality a variety of challenging MAPF instances previously considered out of reach for CBS.

Details DOI

AAAI Conference 2021 Conference Paper

Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances

  • Jingkai Chen
  • Jiaoyang Li
  • Chuchu Fan
  • Brian C. Williams

We present a scalable and effective multi-agent safe motion planner that enables a group of agents to move to their desired locations while avoiding collisions with obstacles and other agents, with the presence of rich obstacles, high-dimensional, nonlinear, nonholonomic dynamics, actuation limits, and disturbances. We address this problem by finding a piecewise linear path for each agent such that the actual trajectories following these paths are guaranteed to satisfy the reach-andavoid requirement. We show that the spatial tracking error of the actual trajectories of the controlled agents can be precomputed for any qualified path that considers the minimum duration of each path segment due to actuation limits. Using these bounds, we find a collision-free path for each agent by solving Mixed Integer-Linear Programs and coordinate agents by using the priority-based search. We demonstrate our method by benchmarking in 2D and 3D scenarios with ground vehicles and quadrotors, respectively, and show improvements over the solving time and the solution quality compared to two state-of-the-art multi-agent motion planners.

PDF Details

AAAI Conference 2021 Conference Paper

Symmetry Breaking for k-Robust Multi-Agent Path Finding

  • Zhe Chen
  • Daniel D. Harabor
  • Jiaoyang Li
  • Peter J. Stuckey

During Multi-Agent Path Finding (MAPF) problems, agents can be delayed by unexpected events. To address such situations recent work describes k-Robust Conflict-Based Search (k-CBS): an algorithm that produces a coordinated and collision-free plan that is robust for up to k delays for any agent. In this work we introduce a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of colliding agents. We give a thorough description of the new constraints and report large improvements to success rate in a range of domains including: (i) classic MAPF benchmarks, (ii) automated warehouse domains, and (iii) on maps from the 2019 Flatland Challenge, a recently introduced railway domain where k-robust planning can be fruitfully applied to schedule trains.

PDF Details

IJCAI Conference 2020 Conference Paper

Iterative-Deepening Conflict-Based Search

  • Eli Boyarski
  • Ariel Felner
  • Daniel Harabor
  • Peter J. Stuckey
  • Liron Cohen
  • Jiaoyang Li
  • Sven Koenig

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF). CBS variants typically compute MAPF solutions using some form of A* search. However, they often do so under strict time limits so as to avoid exhausting the available memory. In this paper, we present IDCBS, an iterative-deepening variant of CBS which can be executed without exhausting the memory and without strict time limits. IDCBS can be substantially faster than CBS due to incremental methods that it uses when processing CBS nodes.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Multi-Directional Heuristic Search

  • Dor Atzmon
  • Jiaoyang Li
  • Ariel Felner
  • Eliran Nachmani
  • Shahaf Shperberg
  • Nathan Sturtevant
  • Sven Koenig

In the Multi-Agent Meeting problem (MAM), the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Heuristic Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed, and experiments demonstrate the benefits of MM*.

PDF Details DOI

AAMAS Conference 2019 Conference Paper

A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results

  • Jiangxing Wang
  • Jiaoyang Li
  • Hang Ma
  • Sven Koenig
  • T. K. Satish Kumar

In this paper, we adopt a new perspective on the Multi-Agent Path Finding (MAPF) problem and view it as a Constraint Satisfaction Problem (CSP). A variable corresponds to an agent, its domain is the set of all paths from the start vertex to the goal vertex of the agent, and the constraints allow only conflict-free paths for each pair of agents. Although the domains and constraints are only implicitly defined, this new CSP perspective allows us to use successful techniques from CSP search. With the concomitant idea of using matrix computations for calculating the size of the reduced domain of an uninstantiated variable, we apply Dynamic Variable Ordering and Rapid Random Restarts to the MAPF problem. In our experiments, the resulting simple polynomial-time MAPF solver, called Matrix MAPF solver, either outperforms or matches the performance of many state-of-the-art solvers for the MAPF problem and its variants.

PDF

IJCAI Conference 2019 Conference Paper

Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search

  • Jiaoyang Li
  • Ariel Felner
  • Eli Boyarski
  • Hang Ma
  • Sven Koenig

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Path Finding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependencies between agents. Empirically, CBS with either new heuristic significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50.

PDF Details

AAAI Conference 2019 Conference Paper

Multi-Agent Path Finding for Large Agents

  • Jiaoyang Li
  • Pavel Surynek
  • Ariel Felner
  • Hang Ma
  • T. K. Satish Kumar
  • Sven Koenig

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a twolevel tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e. g. , a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as “large” agents because they can occupy multiple points at the same time. In this paper, we formalize and study LA- MAPF, i. e. , MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MC- CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

PDF Details

AAAI Conference 2019 Conference Paper

Searching with Consistent Prioritization for Multi-Agent Path Finding

  • Hang Ma
  • Daniel Harabor
  • Peter J. Stuckey
  • Jiaoyang Li
  • Sven Koenig

We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time.

PDF Details

AAAI Conference 2019 Conference Paper

Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding

  • Jiaoyang Li
  • Daniel Harabor
  • Peter J. Stuckey
  • Hang Ma
  • Sven Koenig

We describe a new way of reasoning about symmetric collisions for Multi-Agent Path Finding (MAPF) on 4-neighbor grids. We also introduce a symmetry-breaking constraint to resolve these conflicts. This specialized technique allows us to identify and eliminate, in a single step, all permutations of two currently assigned but incompatible paths. Each such permutation has exactly the same cost as a current path, and each one results in a new collision between the same two agents. We show that the addition of symmetry-breaking techniques can lead to an exponential reduction in the size of the search space of CBS, a popular framework for MAPF, and report significant improvements in both runtime and success rate versus CBSH and EPEA* – two recent and state-of-the-art MAPF algorithms.

PDF Details

AAMAS Conference 2019 Conference Paper

Task and Path Planning for Multi-Agent Pickup and Delivery

  • Minghua Liu
  • Hang Ma
  • Jiaoyang Li
  • Sven Koenig

We study the offline Multi-Agent Pickup-and-Delivery (MAPD) problem, where a team of agents has to execute a batch of tasks with release times in a known environment. To execute a task, an agent has to move first from its current location to the pickup location of the task and then to the delivery location of the task. The MAPD problem is to assign tasks to agents and plan collision-free paths for them to execute their tasks. Online MAPD algorithms can be applied to the offline MAPD problem, but do not utilize all of the available information and may thus not be effective. Therefore, we present two novel offline MAPD algorithms that improve a state-of-the-art online MAPD algorithm with respect to task planning, path planning, and deadlock avoidance for the offline MAPD problem. Our MAPD algorithms first compute one task sequence for each agent by solving a special traveling salesman problem and then plan paths according to these task sequences. We also introduce an effective deadlock avoidance method, called “reserving dummy paths. ” Theoretically, our MAPD algorithms are complete for well-formed MAPD instances, a realistic subclass of all MAPD instances. Experimentally, they produce solutions of smaller makespans and scale better than the online MAPD algorithm in simulated warehouses with hundreds of robots and thousands of tasks.

PDF

IJCAI Conference 2018 Conference Paper

Multi-Agent Path Finding with Deadlines

  • Hang Ma
  • Glenn Wagner
  • Ariel Felner
  • Jiaoyang Li
  • T. K. Satish Kumar
  • Sven Koenig

We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without colliding with each other. We first show that MAPF-DL is NP-hard to solve optimally. We then present two classes of optimal algorithms, one based on a reduction of MAPF-DL to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network and the other one based on novel combinatorial search algorithms. Our empirical results demonstrate that these MAPF-DL solvers scale well and each one dominates the other ones in different scenarios.

PDF Details

AAMAS Conference 2018 Conference Paper

Multi-Agent Path Finding with Deadlines: Preliminary Results

  • Hang Ma
  • Glenn Wagner
  • Ariel Felner
  • Jiaoyang Li
  • T. K. Satish Kumar
  • Sven Koenig

We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.

PDF

AAMAS Conference 2017 Conference Paper

Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks

  • Hang Ma
  • Jiaoyang Li
  • T. K. Satish Kumar
  • Sven Koenig

The multi-agent path-finding (MAPF) problem has recently received a lot of attention. However, it does not capture important characteristics of many real-world domains, such as automated warehouses, where agents are constantly engaged with new tasks. In this paper, we therefore study a lifelong version of the MAPF problem, called the multiagent pickup and delivery (MAPD) problem. In the MAPD problem, agents have to attend to a stream of delivery tasks in an online setting. One agent has to be assigned to each delivery task. This agent has to first move to a given pickup location and then to a given delivery location while avoiding collisions with other agents. We present two decoupled MAPD algorithms, Token Passing (TP) and Token Passing with Task Swaps (TPTS). Theoretically, we show that they solve all well-formed MAPD instances, a realistic subclass of MAPD instances. Experimentally, we compare them against a centralized strawman MAPD algorithm without this guarantee in a simulated warehouse system. TP can easily be extended to a fully distributed MAPD algorithm and is the best choice when real-time computation is of primary concern since it remains efficient for MAPD instances with hundreds of agents and tasks. TPTS requires limited communication among agents and balances well between TP and the centralized MAPD algorithm.

PDF
v2026.09.13