News

2021-08 Honored to receive funding from the Canada Foundation for Innovation's (CFI) John R. Evans Leaders Fund (JELF) to work on motion-coordination and human-robot interaction problems! Thank you, CFI! Read SFU FAS news and SFU CS news.
2021-08 Honored to receive an ICAPS Best Dissertation Award for my dissertation!
2021-08 Our demo on winning the 2020 Flatland Challenge won a ICAPS 2021 People's Choice Best System Demonstration Award! Our demo video is lots of fun!
2021-08 An Artificial Intelligence Journal paper on symmetry reasoning for Multi-Agent Path Finding is available!
2021-03 Honored to receive an IFAAMAS Victor Lesser Distinguished Dissertation Award Runner-Up for my dissertation!
2021-03 Paper accepted to ICRA 2021!
2021-02 Two papers accepted to ICAPS 2021!
2021-02 Honored to be featured in AAAI New Faculty Highlights! Watch my talk here.
2020-12 Advised Team An_Old_Driver won both Round 1 and Round 2 of the NeurIPS-20 Flatland Challenge (see our ICAPS paper for technical details)!
2020-01 Paper accepted to ICAPS 2020!
2020-01 Paper accepted to AAMAS 2020!
2019-12 Joined the School of Computing Science at Simon Fraser University as an Assistant Professor!


About

I am an Assistant Professor in Computing Science at Simon Fraser University and director of the Autonomous Intelligence and Robotics (AIRob) lab.

My interests are mainly in artificial intelligence, robotics, and machine learning. Specifically, I am interested in topics on automated planning, multi-agent/robot systems, spatio-temporal and constraint reasoning, and applications of probabilistic methods and other topics related to graphs, combinatorial optimization, and algorithms.

Research Opportunities

photo by TourismVancouver

I am always looking for self-motivated students at all levels. See my research highlights here or watch my AAAI-21 New Faculty Highlights talk below to learn more about my research.

If you are interested in working with me on AI, robotics, and multi-agent/robot systems, please mention my name in your application to the SFU CS graduate program. Applicants should also refer to the SFU CS graduate program page for more information on the admission requirements and application deadlines.

The SFU main campus is located on the Burnaby Mountain, 12 miles from downtown Vancouver.

Recent Service

Conference and Workshop Organization

Conference Area Chair and (Senior) Program Committee Member

  • AAAI Conference on Artificial Intelligence (AAAI) 2022, 2021, 2020
  • International Joint Conference on Artificial Intelligence (IJCAI) 2021 (SPC), 2020, 2019
  • International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2021, 2020, 2019
  • International Conference on Automated Planning and Scheduling (ICAPS) 2021
  • International Conference of the Florida Artificial Intelligence Research Society (FLAIR) 2021
  • ACM/SIGGRAPH conference on Motion, Interaction and Games (MIG) 2021
  • International Symposium on Multi-Robot and Multi-Agent Systems (MRS) 2021 (AC)
  • International Symposium on Combinatorial Search (SoCS) 2020

Journal Editing

Teaching

Education

  • 2014 to 2019, Ph.D. Computer Science, University of Southern California
  • 2012 to 2014, M.Sc. Computer Science, McGill University
  • 2010 to 2012, B.Sc. (First Class with Distinction) Computing Science, Simon Fraser University
  • 2008 to 2010, B.Eng. Computer Science and Technology, Zhejiang University

Miscellaneous

Recent Publications

  • 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.
    @article{LiAIJ21,
     author = {Jiaoyang Li and Daniel Harabor and Peter J. Stuckey and Hang Ma and Graeme Gange and Sven Koenig},
     journal = {Artifical Intelligence},
     pages = {103574},
     title = {Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search},
     volume = {301},
     year = {2021}
    }

  • We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories based on (1) controllability (the set of agents that they can plan paths for at each time) and (2) rationality (the quality of paths they plan) and study the relationships between them. We perform a competitive analysis for each category of online MAPF algorithms with respect to commonlyused objective functions. We show that a naive algorithm that routes newly-revealed agents one at a time in sequence achieves a competitive ratio that is asymptotically bounded from both below and above by the number of agents with respect to flowtime and makespan. We then show a counterintuitive result that, if rerouting of previously-revealed agents is not allowed, any rational online MAPF algorithms, including ones that plan optimal paths for all newly-revealed agents, have the same asymptotic competitive ratio as the naive algorithm, even on 2D 4-neighbor grids. We also derive constant lower bounds on the competitive ratio of any rational online MAPF algorithms that allow rerouting. The results thus provide theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.
    @inproceedings{MaICAPS21,
     author = {Hang Ma},
     booktitle = {International Conference on Automated Planning and Scheduling},
     pages = {234--242},
     title = {A Competitive Analysis of Online Multi-Agent Path Finding},
     year = {2021}
    }

  • 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-theart 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 collisionfree paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.
    @inproceedings{LiICAPS21,
     author = {Jiaoyang Li and Zhe Chen and Yi Zheng and Shao-Hung Chan and Daniel Harabor and Peter J. Stuckey and Hang Ma and Sven Koenig},
     booktitle = {International Conference on Automated Planning and Scheduling},
     pages = {477--485},
     title = {Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge},
     year = {2021}
    }

  • Multi-Agent Path Finding (MAPF) is essential to large-scale robotic systems. Recent methods have applied reinforcement learning (RL) to learn decentralized polices in partially observable environments. A fundamental challenge of obtaining collision-free policy is that agents need to learn cooperation to handle congested situations. This paper combines communication with deep Q-learning to provide a novel learning based method for MAPF, where agents achieve cooperation via graph convolution. To guide RL algorithm on long-horizon goal-oriented tasks, we embed the potential choices of shortest paths from single source as heuristic guidance instead of using a specific path as in most existing works. Our method treats each agent independently and trains the model from a single agent’s perspective. The final trained policy is applied to each agent for decentralized execution. The whole system is distributed during training and is trained under a curriculum learning strategy. Empirical evaluation in obstacle-rich environment indicates the high success rate with low average step of our method.
    @inproceedings{MaICRA21,
     author = {Ziyuan Ma and Yudong Luo and Hang Ma},
     booktitle = {IEEE International Conference on Robotics and Automation},
     pages = {(in press)},
     title = {Distributed Heuristic Multi-Agent Path Finding with Communication},
     year = {2021}
    }

  • We consider two new classes of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.
    @inproceedings{LiICAPS20,
     author = {Jiaoyang Li and Graeme Gange and Daniel Harabor and Peter J. Stuckey and Hang Ma and Sven Koenig},
     booktitle = {International Conference on Automated Planning and Scheduling},
     pages = {193--201},
     title = {New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding},
     year = {2020}
    }

  • In this paper, we formalize and study the Moving Agents in Formation (MAiF) problem, that combines the tasks of finding short collision-free paths for multiple agents and keeping them in close adherence to a desired formation. Previous work includes controller-based algorithms, swarm-based algorithms, and potential-field-based algorithms. They usually focus on only one or the other of these tasks, solve the problem greedily without systematic search, and thus generate costly solutions or even fail to find solutions in congested environments. In this paper, we develop a two-phase search algorithm, called SWARM-MAPF, whose first phase is inspired by swarm-based algorithms (in open regions) and whose second phase is inspired by multi-agent path-finding (MAPF) algorithms (in congested regions). In the first phase, SWARM-MAPF selects a leader among the agents and finds a path for it that is sufficiently far away from the obstacles so that the other agents can preserve the desired formation around it. It also identifies the critical segments of the leader’s path where the other agents cannot preserve the desired formation and the refinement of which has thus to be delegated to the second phase. In the second phase, SWARM-MAPF refines these segments. Theoretically, we prove that SWARM-MAPF is complete. Empirically, we show that SWARM-MAPF scales well and is able to find close-to-optimal solutions.
    @inproceedings{LiAAMAS20,
     author = {Jiaoyang Li and Kexuan Sun and Hang Ma and Ariel Felner and T. K. Satish Kumar and Sven Koenig},
     booktitle = {International Conference on Autonomous Agents and Multiagent Systems},
     pages = {726--734},
     title = {Moving Agents in Formation in Congested Environments},
     year = {2020}
    }

  • Full list of publications