Author name cluster

Shao-Hung Chan

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.

18 papers

2 author rows

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

Truncated Counterfactual Learning for Anytime Multi-Agent Path Finding

Thomy Phan
Shao-Hung Chan
Sven Koenig

Anytime multi-agent path finding (MAPF) is a promising approach to scalable and collision-free path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood Search (LNS), is the current state-of-the-art approach where a fast initial solution is iteratively optimized by destroying and repairing selected paths, i.e., a neighborhood, of the solution. Delay-based MAPF-LNS has demonstrated particular effectiveness in generating promising neighborhoods via seed agents, according to their delays. Seed agents are selected using handcrafted strategies or online learning, where the former relies on human intuition about underlying structures, while the latter conducts black-box optimization, ignoring any structure. In this paper, we propose Truncated Adaptive Counterfactual K-ranked LEarning (TACKLE) to select seed agents via informed online learning by leveraging handcrafted strategies as human intuition. We show theoretically that TACKLE dominates its handcrafted and black-box learning counterparts in the limit. Our experiments demonstrate cost improvements of at least 60% in instances with one thousand agents, compared with state-of-the-art anytime solvers.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic

Thomy Phan
Benran Zhang
Shao-Hung Chan
Sven Koenig

Anytime multi-agent path finding (MAPF) is a promising approach to scalable and collision-free path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood Search (LNS), is the current state-of-the-art approach where a fast initial solution is iteratively optimized by destroying and repairing selected paths of the solution. Current MAPF-LNS variants commonly use an adaptive selection mechanism to choose among multiple destroy heuristics. However, to determine promising destroy heuristics, MAPF-LNS requires a considerable amount of exploration time. As common destroy heuristics are stationary, i.e., non-adaptive, any performance bottleneck caused by them cannot be overcome by adaptive heuristic selection alone, thus limiting the overall effectiveness of MAPF-LNS. In this paper, we propose Adaptive Delay-based Destroy-and-Repair Enhanced with Success-based Self-learning (ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS. ADDRESS applies restricted Thompson Sampling to the top-K set of the most delayed agents to select a seed agent for adaptive LNS neighborhood generation. We evaluate ADDRESS in multiple maps from the MAPF benchmark set and demonstrate cost improvements by at least 50% in large-scale scenarios with up to a thousand agents, compared with the original MAPF-LNS and other state-of-the-art methods.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Counterfactual Online Learning for Open-Loop Monte-Carlo Planning

Thomy Phan
Shao-Hung Chan
Sven Koenig

Monte-Carlo Tree Search (MCTS) is a popular approach to online planning under uncertainty. While MCTS uses statistical sampling via multi-armed bandits to avoid exhaustive search in complex domains, common closed-loop approaches typically construct enormous search trees to consider a large number of potential observations and actions. On the other hand, open-loop approaches offer better memory efficiency by ignoring observations but are generally not competitive with closed-loop MCTS in terms of performance - even with commonly integrated human knowledge. In this paper, we propose Counterfactual Open-loop Reasoning with Ad hoc Learning (CORAL) for open-loop MCTS, using a causal multi-armed bandit approach with unobserved confounders (MABUC). CORAL consists of two online learning phases that are conducted during the open-loop search. In the first phase, observational values are learned based on preferred actions. In the second phase, counterfactual values are learned with MABUCs to make a decision via an intent policy obtained from the observational values. We evaluate CORAL in four POMDP benchmark scenarios and compare it with closed-loop and open-loop alternatives. In contrast to standard open-loop MCTS, CORAL achieves competitive performance compared with closed-loop algorithms while constructing significantly smaller search trees.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search

Shao-Hung Chan
Zhe Chen
Dian-Lun Lin
Yue Zhang
Daniel Harabor
Sven Koenig
Tsung-Wei Huang
Thomy Phan

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for multiple agents in a shared environment while improving the solution quality. The state-of-the-art anytime MAPF algorithm is based on Large Neighborhood Search (MAPF- LNS), which is a combinatorial search algorithm that iteratively destroys and repairs a subset of collision-free paths. In this paper, we propose Destroy-Repair Operation Parallelism for MAPF-LNS (DROP-LNS), a parallel framework that performs multiple destroy and repair operations concurrently to explore more regions of the search space and improve the solution quality. Unlike MAPF-LNS, DROP-LNS is able to exploit multiple threads during the search. The results show that DROP-LNS outperforms the state-of-the-art anytime MAPF algorithms, namely MAPF-LNS and LaCAM*, with respect to solution quality when terminated at the same runtime.

PDF

IJCAI Conference 2024 Conference Paper

Theoretical Study on Multi-objective Heuristic Search

Shawn Skyler
Shahaf Shperberg
Dor Atzmon
Ariel Felner
Oren Salzman
Shao-Hung Chan
Han Zhang
Sven Koenig

This paper provides a theoretical study on Multi-Objective Heuristic Search. We first classify states in the state space into must-expand, maybe-expand, and never-expand states and then transfer these definitions to nodes in the search tree. We then formalize a framework that generalizes A* to Multi-Objective Search. We study different ways to order nodes under this framework and their relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions.

PDF Details DOI

SoCS Conference 2023 Conference Paper

Greedy Priority-Based Search for Suboptimal Multi-Agent Path Finding

Shao-Hung Chan
Roni Stern
Ariel Felner
Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment, while minimizing their sum of travel times. Since solving MAPF optimally is NP-hard, researchers have explored algorithms that solve MAPF suboptimally but efficiently. Priority-Based Search (PBS) is the leading algorithm for this purpose. It finds paths for individual agents, one at a time, and resolves collisions by assigning priorities to the colliding agents and replanning their paths during its search. However, PBS becomes ineffective for MAPF instances with high densities of agents and obstacles. Therefore, we introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques that speed up GPBS further, namely partial expansions, target reasoning, induced constraints, and soft restarts. We show that GPBS with all these improvements has a higher success rate than the state-of-the-art suboptimal algorithm for a 1-minute runtime limit, especially for MAPF instances with small maps and dense obstacles.

Details

IJCAI Conference 2023 Conference Paper

Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities

Oren Salzman
Ariel Felner
Carlos Hernández
Han Zhang
Shao-Hung Chan
Sven Koenig

In the multi-objective shortest-path problem we are interested in computing a path, or a set of paths that simultaneously balance multiple cost functions. This problem is important for a diverse range of applications such as transporting hazardous materials considering travel distance and risk. This family of problems is not new with results dating back to the 1970's. Nevertheless, the significant progress made in the field of heuristic search resulted in a new and growing interest in the sub-field of multi-objective search. Consequently, in this paper we review the fundamental problems and techniques common to most algorithms and provide a general overview of the field. We then continue to describe recent work with an emphasis on new challenges that emerged and the resulting research opportunities.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Multi-objective Search via Lazy and Efficient Dominance Checks

Carlos Hernández
William Yeoh
Jorge A. Baier
Ariel Felner
Oren Salzman
Han Zhang
Shao-Hung Chan
Sven Koenig

Multi-objective search can be used to model many real-world problems that require finding Pareto optimal paths from a specified start state to a specified goal state, while considering different costmetrics such as distance, time, and fuel. The performance of multi-objective search can be improved by making dominance checking—an operation necessary to determine whether or not a path dominates another—more efficient. This was shown in practice by BOA*, a state-of-the-art bi-objective search algorithm, which outperforms previously existing bi-objective search algorithms in part because it adopts a lazy approach towards dominance checking. EMOA*, a recent multi-objective search algorithm, generalizes BOA* to more-than-two objectives using AVL trees for dominance checking. In this paper, we first propose Linear-Time Multi-Objective A* (LTMOA*), an multi-objective search algorithm that implements a more efficient dominance checking than EMOA* using simple data structures like arrays. We then propose an even lazier approach towards dominance checking, and the resulting algorithm, LazyLTMOA*, distinguishes from EMOA* and LTMOA* by removing the dominance checking during node generation. Our experimental results show that LazyLTMOA* outperforms EMOA* by up to an order of magnitude in terms of runtime.

PDF Details DOI

SoCS Conference 2023 Conference Paper

Must-Expand Nodes in Multi-Objective Search [Extended Abstract]

Shawn Skyler
Shahaf S. Shperberg
Dor Atzmon
Ariel Felner
Oren Salzman
Shao-Hung Chan
Han Zhang 0018
Sven Koenig

This extended abstract presents a theoretical analysis of node expansions in Multi-Objective Search. We define three categories of nodes, Must-Expand Nodes, Maybe-Expand Nodes, and Never-Expand Nodes. Our analysis establishes that regardless of the Ordering Function or Multi-Objective Search algorithm used, any Multi-Objective Search algorithm must expand all Must-Expand Nodes, some or none of Maybe-Expand Nodes, and none of Never-Expand Nodes. In addition, we conduct experimental evaluations of various Ordering Functions, revealing that they all expand the same number of nodes and compare their efficiency at finding solutions at various stages of the search.

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

SoCS Conference 2022 Conference Paper

On Merging Agents in Multi-Agent Pathfinding Algorithms

Eli Boyarski
Shao-Hung Chan
Dor Atzmon
Ariel Felner
Sven Koenig

In Multi-Agent Pathfinding (MAPF), the task is to find non-colliding paths for a set of agents. This paper focuses on search-based MAPF algorithms from the Conflict-Based Framework, which is introduced here. A common technique in such algorithms is to merge a group of dependent agents into a meta-agent and plan non-colliding paths for the meta-agent using a low-level MAPF sub-solver. We analyze the patterns that emerge when agents are merged in an arbitrary order. We then introduce policies for choosing which agents or meta-agents to merge to achieve improved efficiency in three algorithms: Independence Detection (ID) and Improved Conflict-Based Search (ICBS), which are optimal, and Priority-Based Search (PBS), which is a fast suboptimal algorithm. Experimental results show a significant improvement in efficiency

Details

SoCS Conference 2021 Conference Paper

A Hierarchical Approach to Multi-Agent Path Finding

Han Zhang 0018
Mingze Yao
Ziang Liu 0002
Jiaoyang Li 0001
Lucas Terr
Shao-Hung Chan
T. K. Satish Kumar
Sven Koenig

Solving Multi-Agent Path Finding (MAPF) instances optimally is NP-hard, and existing optimal and bounded suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP is able to solve as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.

Details

SoCS Conference 2021 Conference Paper

ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding

Shao-Hung Chan
Jiaoyang Li 0001
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. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.

Details

ICAPS Conference 2021 Conference Paper

Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

Jiaoyang Li 0001
Zhe Chen 0016
Yi Zheng 0010
Shao-Hung Chan
Daniel Harabor
Peter J. Stuckey
Hang Ma 0001
Sven Koenig

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale rail networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF or, in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

Details

SoCS Conference 2021 Conference Paper

Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

Jiaoyang Li 0001
Zhe Chen 0016
Yi Zheng 0010
Shao-Hung Chan
Daniel Harabor
Peter J. Stuckey
Hang Ma 0001
Sven Koenig

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale railway networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF, or in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

Details

IROS Conference 2019 Conference Paper

Multi-Layer Environmental Affordance Map for Robust Indoor Localization, Event Detection and Social Friendly Navigation

Ping-Tsang Wu
Chee-An Yu
Shao-Hung Chan
Ming-Li Chiang
Li-Chen Fu

In this paper, we propose a novel system architecture called multi-layer environmental affordance map for social and service companion robots. Based on this architecture, robots can organize the perception and inference information efficiently and generate social friendly navigation strategies. In other words, robots are able to strengthen their perception and inference abilities to interact with domestic environment and users under our efficient framework. The main feature of this architecture is that the relations between layers can be viewed as affordances to improve the accuracy and the robustness of the detection and inference. The results show that our architecture achieves robust indoor localization, scene localization, human event detection and socially friendly navigation in real time under limited computational resource.

Details

IROS Conference 2018 Conference Paper

Distributed Deep Reinforcement Learning based Indoor Visual Navigation

Shih-Hsi Hsu
Shao-Hung Chan
Ping-Tsang Wu
Kun Xiao
Li-Chen Fu

Recently, as the rise of deep reinforcement learning, it not only can help the robot to convert the complicated environment scene to motor control command directly but also can accomplish the navigation task properly. In this paper, we propose a novel structure, where the objective is to achieve navigation in large-scale indoor complex environment without pre-constructed map. Generally, it requires good understanding of such indoor environment to make complex spatial perception possible, especially when the indoor space consists of many walls and doors which might block the view of robot leading to complex navigation path. By the proposed distributed deep reinforcement learning in different local regions, our method can achieve indoor visual navigation in the aforementioned large-scale environment without extra map information and human instruction. In the experiments, we validate our proposed method by conducting highly promising navigation tasks both in simulation and real environments.

Details