News

About

Research Opportunities

Recent Service

Teaching

Education

Miscellaneous

Recent Publications

• Priority-Based Search for the Virtual Network Embedding Problem.
  Yi Zheng, Hang Ma, Sven Koenig, Erik Kline and T. K. Satish Kumar.
  International Conference on Automated Planning and Scheduling (ICAPS), Prague, Czech Republic, July 2023.
  [ bibtex]

  @inproceedings{ZhengICAPS23,
   author = {Yi Zheng and Hang Ma and Sven Koenig and Erik Kline and T. K. Satish Kumar},
   booktitle = {International Conference on Automated Planning and Scheduling},
   pages = {(in print)},
   title = {Priority-Based Search for the Virtual Network Embedding Problem},
   year = {2023}
  }

• Intelligent Planning for Large-Scale Multi-Agent Systems.
  Hang Ma.
  AI Magazine 43(4), December 2022.
  [ pdf] [ abstract] [ bibtex] [ publisher]

  This article summarizes the New Faculty Highlights talk with the same title at AAAI 2021. Intelligent agents such as different types of robots will soon become an integral part of our daily lives. In real-world multi-agent systems, the most fundamental challenges are assigning tasks to multiple agents (task-level coordination problems) and planning collision-free paths for the agents to task locations (motion-level coordination problems). This article surveys four directions of our research on using intelligent planning techniques for the above multi-agent coordination problems.

  @article{MaAIM22,
   author = {Hang Ma},
   journal = {AI Magazine},
   number = {4},
   pages = {376--382},
   title = {Intelligent Planning for Large-Scale Multi-Agent Systems},
   volume = {43},
   year = {2022}
  }

• Multi-Goal Multi-Agent Pickup and Delivery.
  Qinghong Xu, Jiaoyang Li, Sven Koenig and Hang Ma.
  IEEE/RSJ International Conference on Intelligent Robots and System (IROS), Kyoto, Japan, October 2022.
  [ pdf] [ abstract] [ bibtex] [ video]

  In this work, we consider the Multi-Agent Pickup-and-Delivery (MAPD) problem, where agents constantly engage with new tasks and need to plan collision-free paths to execute them. To execute a task, an agent needs to visit a pair of goal locations, consisting of a pickup location and a delivery location. We propose two variants of an algorithm that assigns a sequence of tasks to each agent using the anytime algorithm Large Neighborhood Search (LNS) and plans paths using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search (PBS). LNS-PBS is complete for well-formed MAPD instances, a realistic subclass of MAPD instances, and empirically more effective than the existing complete MAPD algorithm CENTRAL. LNS-wPBS provides no completeness guarantee but is empirically more efficient and stable than LNS-PBS. It scales to thousands of agents and thousands of tasks in a large warehouse and is empirically more effective than the existing scalable MAPD algorithm HBH+MLA*. LNS-PBS and LNS-wPBS also apply to a more general variant of MAPD, namely the Multi-Goal MAPD (MG-MAPD) problem, where tasks can have different numbers of goal locations.

  @inproceedings{XuIROS22,
   author = {Qinghong Xu and Jiaoyang Li and Sven Koenig and Hang Ma},
   booktitle = {{IEEE/RSJ} International Conference on Intelligent Robots and System},
   pages = {in press},
   title = {Multi-Goal Multi-Agent Pickup and Delivery},
   year = {2022}
  }

• Graph-Based Multi-Robot Path Finding and Planning.
  Hang Ma.
  Current Robotics Reports, June 2022.
  [ pdf] [ abstract] [ bibtex] [ publisher]

  Purpose of Review Planning collision-free paths for multiple robots is important for real-world multi-robot systems and has been studied as an optimization problem on graphs, called multi-agent path finding (MAPF). This review surveys different categories of classic and state-of-the-art MAPF algorithms and different research attempts to tackle the challenges of generalizing MAPF techniques to real-world scenarios. Recent Findings Solving MAPF problems optimally is computationally challenging. Recent advances have resulted in MAPF algorithms that can compute collision-free paths for hundreds of robots and thousands of navigation tasks in seconds of runtime. Many variants of MAPF have been formalized to adapt MAPF techniques to different real-world requirements, such as considerations of robot kinematics, online optimization for real-time systems, and the integration of task assignment and path planning. Summary Algorithmic techniques for MAPF problems have addressed important aspects of several multi-robot applications, including automated warehouse fulfillment and sortation, automated train scheduling, and navigation of non-holonomic robots and quadcopters. This showcases their potential for real-world applications of large-scale multi-robot systems.

  @inproceedings{MaCRR22,
   author = {Hang Ma},
   booktitle = {Current Robotics Reports},
   pages = {1--8},
   title = {Graph-Based Multi-Robot Path Finding and Planning},
   year = {2022}
  }

• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding.
  Xinyi Zhong, Jiaoyang Li, Sven Koenig and Hang Ma.
  IEEE International Conference on Robotics and Automation (ICRA), Philadelphia, PA, May 2022.
  [ pdf] [ abstract] [ bibtex] [ video]

  We formalize and study the multi-goal task assignment and pathfinding (MG-TAPF) problem from theoretical and algorithmic perspectives. The MG-TAPF problem is to compute an assignment of tasks to agents, where each task consists of a sequence of goal locations, and collision-free paths for the agents that visit all goal locations of their assigned tasks in sequence. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent pathfinding problem and solve the MG-TAPF problem optimally and bounded-suboptimally. We experimentally compare these algorithms on a variety of different benchmark domains.

  @inproceedings{ZhongICRA22,
   author = {Xinyi Zhong and Jiaoyang Li and Sven Koenig and Hang Ma},
   booktitle = {IEEE International Conference on Robotics and Automation},
   pages = {10731--10737},
   title = {Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding},
   year = {2022}
  }

• Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search.
  Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Hang Ma, Graeme Gange and Sven Koenig.
  Artifical Intelligence (AIJ) 301, December 2021.
  [ pdf] [ abstract] [ bibtex] [ publisher] [ github]

  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}
  }

Full list of publications