News

About

Research Opportunities

Recent Service

Teaching

Education

Miscellaneous

Recent Publications

• Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics.
  Jingtao Tang and Hang Ma.
  IEEE Robotics and Automation Letters (RA-L) 8(10), October 2023.
  [ pdf] [ abstract] [ bibtex] [ video] [ publisher] [ github]

  We investigate time-optimal Multi-Robot Coverage Path Planning (MCPP) for both unweighted and weighted terrains, which aims to minimize the coverage time, defined as the maximum travel time of all robots. Specifically, we focus on a reduction from MCPP to Min-Max Rooted Tree Cover (MMRTC). For the first time, we propose a Mixed Integer Programming (MIP) model to optimally solve MMRTC, resulting in an MCPP solution with a coverage time that is provably at most four times the optimal. Moreover, we propose two suboptimal yet effective heuristics that reduce the number of variables in the MIP model, thus improving its efficiency for large-scale MCPP instances. We show that both heuristics result in reduced-size MIP models that remain complete (i.e., guaranteed to find a solution if one exists) for all MMRTC instances. Additionally, we explore the use of model optimization warm-startup to further improve the efficiency of both the original MIP model and the reduced-size MIP models. We validate the effectiveness of our MIP-based MCPP planner through experiments that compare it with two state-of-the-art MCPP planners on various instances, demonstrating a reduction in the coverage time by an average of $27.65%$ and $23.24%$ over them, respectively.

  @article{TangRAL23,
   author = {Jingtao Tang and Hang Ma},
   journal = {IEEE Robotics and Automation Letters},
   number = {10},
   pages = {6491--6498},
   title = {Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics},
   volume = {8},
   year = {2023}
  }

• SACHA: Soft Actor-Critic with Heuristic-Based Attention for Partially Observable Multi-Agent Path Finding.
  Qiushi Lin and Hang Ma.
  IEEE Robotics and Automation Letters (RA-L) 8(8), August 2023.
  [ pdf] [ abstract] [ bibtex] [ publisher] [ github]

  Multi-Agent Path Finding (MAPF) is a crucial component for many large-scale robotic systems, where agents must plan their collision-free paths to their given goal positions. Recently, multi-agent reinforcement learning has been introduced to solve the partially observable variant of MAPF by learning a decentralized single-agent policy in a centralized fashion based on each agent's partial observation. However, existing learning-based methods are ineffective in achieving complex multi-agent cooperation, especially in congested environments, due to the non-stationarity of this setting. To tackle this challenge, we propose a multi-agent actor-critic method called Soft Actor-Critic with Heuristic-Based Attention (SACHA), which employs novel heuristic-based attention mechanisms for both the actors and critics to encourage cooperation among agents. SACHA learns a neural network for each agent to selectively pay attention to the shortest path heuristic guidance from multiple agents within its field of view, thereby allowing for more scalable learning of cooperation. SACHA also extends the existing multi-agent actor-critic framework by introducing a novel critic centered on each agent to approximate $Q$-values. Compared to existing methods that use a fully observable critic, our agent-centered multi-agent actor-critic method results in more impartial credit assignment and better generalizability of the learned policy to MAPF instances with varying numbers of agents and types of environments. We also implement SACHA(C), which embeds a communication module in the agent's policy network to enable information exchange among agents. We evaluate both SACHA and SACHA(C) on a variety of MAPF instances and demonstrate decent improvements over several state-of-the-art learning-based MAPF methods with respect to success rate and solution quality.

  @article{LinRAL23,
   author = {Qiushi Lin and Hang Ma},
   journal = {IEEE Robotics and Automation Letters},
   number = {8},
   pages = {2377--3766},
   title = {SACHA: Soft Actor-Critic with Heuristic-Based Attention for Partially Observable Multi-Agent Path Finding},
   volume = {8},
   year = {2023}
  }

• 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.
  [ pdf] [ abstract] [ bibtex]

  The Virtual Network Embedding (VNE) problem is a constrained optimization problem. It arises in the context of allocating resources on heterogeneous physical networks to provide end-to-end computing services. In this paper, we introduce a new solver, called VNE-PBS, that uses priority-based search (PBS) for solving the VNE problem. VNE-PBS uses a prioritized heuristic search algorithm that explores the space of all possible priority orderings using a systematic depth-first search. The solver is inspired by the success of PBS for the Multi-Agent Path Finding (MAPF) problem and the similarities between the VNE and MAPF problems. We show that VNE-PBS significantly outperforms competing methods on various benchmark instances for both the offline and online versions of the VNE problem.

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

• Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses.
  Baiyu Li and Hang Ma.
  IEEE Robotics and Automation Letters (RA-L) 8(6), June 2023.
  [ pdf] [ abstract] [ bibtex] [ video] [ publisher]

  We introduce a new problem formulation, Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD), which models the multi-robot shelf rearrangement problem in automated warehouses. DD-MAPD extends both Multi-Agent Pickup and Delivery (MAPD) and Multi-Agent Path Finding (MAPF) by allowing agents to move beneath shelves or lift and deliver a shelf to an arbitrary location, thereby changing the warehouse layout. We show that solving DD-MAPD is NP-hard. To tackle DD-MAPD, we propose MAPF-DECOMP, an algorithmic framework that decomposes a DD-MAPD instance into a MAPF instance for coordinating shelf trajectories and a subsequent MAPD instance with task dependencies for computing paths for agents. We also present an optimization technique to improve the performance of MAPF-DECOMP and demonstrate how to make MAPF-DECOMP complete for well-formed DD-MAPD instances, a realistic subclass of DD-MAPD instances. Our experimental results demonstrate the efficiency and effectiveness of MAPF-DECOMP, with the ability to compute high-quality solutions for large-scale instances with over one thousand shelves and hundreds of agents in just minutes of runtime.

  @article{LiRAL23,
   author = {Baiyu Li and Hang Ma},
   journal = {IEEE Robotics and Automation Letters},
   number = {6},
   pages = {3701--3708},
   title = {Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses},
   volume = {8},
   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 = {9964--9971},
   title = {Multi-Goal Multi-Agent Pickup and Delivery},
   year = {2022}
  }

Full list of publications