Jiaoyang Li

I am currently on the 2021-2022 academic job market.

I am a fifth year Ph.D. student in Computer Science at University of Southern California. My advisor is Professor Sven Koenig. I received my B.Eng degree from Department of Automation, School of Information Science and Technology, Tsinghua University. I am interested in a variety of topics related to Artificial Intelligence, such as combinatorial algorithms, heuristic search, scheduling and planning for robotics and transportation. My current research focuses on the coordination of large teams of mobile robots. You can find my CV here.

News

Show more
  • [2021.04] Our MAPF-LNS paper was accepted to IJCAI 2021.
  • [2021.02] Our Flatland paper and CBICS paper were accepted to ICAPS 2021.
  • [2021.02] I gave 2 virtual talks on our EECBS paper and RHCR paper at AAAI 2021.
  • [2020.12] Our team "An_Old_Driver" won both Round 1 and Round 2 of the 2020 Flatland Challenge, a rail scheduling competition. I gave a virtual talk at the NeurIPS 2020 competation track.
  • [2020.12] 4 papers accepted to AAAI 2021.
  • [2020.10] 2 virtual talks at ICAPS 2020.
  • [2020.05] 2 virtual talks at SoCS 2020.
  • [2020.05] 2 virtual talks at AAMAS 2020.
  • [2020.04] Our paper "Multi-Agent Path Finding with Mutex Propogation" received the outstanding student paper award at ICAPS 2020.
  • [2020.04] 2 papers accepted to IJCAI 2020.
  • [2020.02] Visiting the Optimization Research Group for 6 months at Monash University, Melbourne, VIC, Australia.
  • [2020.02] A talk at EAAI 2020 in New York, NY, USA.
  • [2020.01] 2 papers accepted to ICAPS 2020.
  • [2020.01] A paper and an extended abstract accepted to AAMAS 2020.
  • [2019.11] Visited Prof. Ariel Felner's group for 2 weeks at Ben-Gurion University, Be'er Sheva, Israel.
  • [2019.10] A talk at the Amazon Research Awards – Robotics Symposium in Boston, MA, USA.
  • [2019.08] 2 talks at IJCAI 2019 in Macau, China.
  • [2019.07] 2 talks at ICAPS 2019 in Berkeley, CA, USA.
  • [2019.05] Summer research intern at Amazon Robotics, Seattle, WA, USA.
  • [2019.05] A paper accepted to IJCAI 2019.
  • [2019.03] Received a Technology Commercialization Award from the USC Stevens Center for Innovation Technology.
  • [2019.02] 2 short papers accepted to ICAPS 2019.
  • [2019.01] 2 spotlight talks at AAAI 2019 in Honolulu, Hawaii, USA.
  • [2019.01] A paper and an extended abstract accepted to AAMAS 2019.
  • [2018.12] Visited Prof. Ariel Felner's group for 3 weeks at Ben-Gurion University, Be'er Sheva, Israel.
  • [2018.11] 3 papers accepted to AAAI 2019.
  • [2018.04] A paper accepted to IJCAI 2018.
  • [2018.01] An extended abstract accepted to AAMAS 2018.
  • [2018.01] A short paper accepted to ICAPS 2018.
  • [2017.08] PhD student at USC!

Research

Recent advances in robotics have laid the foundation for building large-scale multi-agent systems. However, how to coordinate the robots intelligently is a difficult problem because the joint-state space increases exponentially with the number of agents. To tackle this challenge, I started with one fundamental problem called Multi-Agent Path Finding (MAPF), which is to plan collision-free paths on a graph for a team of agents while minimizing their travel times. My research concentrates on developing AI techniques to bridge the gap between MAPF and real-world applications. My main contributions are summarized as follows:

Symmetry Breaking for MAPF

One of the reasons MAPF problems are so hard to solve is due to a phenomena called pairwise path symmetry, which occurs when two agents have many equivalent paths, all of which appear promising, but which are pairwise incompatible because they result in a collision. The symmetry arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for currently state-of-the-art MAPF algorithms that employ heuristic search, such as Conflict-based Search (CBS). To break symmetries, we propose a variety of constraint-based reasoning techniques, to detect the symmetries as they arise and to efficiently eliminate, in a single branching step, all permutations of two currently assigned but pairwise incompatible paths.

Highlights: The addition of the symmetry-reasoning techniques proposed in [3] can reduce the number of expanded nodes and runtime of the optimal algorithm CBS by up to 4 orders of magnitude and thus can handle up to 30 times more agents than possible before within one minute.

Relevant publications: [1] rectangle symmetry, [2] corridor and target symmetries, [3] generalized rectangle, target, and corridor symmetry reasoning, [4] automatic symmetry reasoning by mutex propagation (ICAPS’20 outstanding student paper), [5] mutex propagation for SAT-based MAPF, [6] symmetry reasoning for k-robust MAPF, and [7] symmetry reasoning with bounded-suboptimal CBS.

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for MAPF. However, existing variants of CBS do not use any heuristics that estimate future work. Introducing admissibles heuristics to guide the high-level search of CBS can significantly reduce the size of the CBS search tree and its runtime. Introducing more informed but potentially inadmissible heuritics to guide the high-level search of bounded-suboptimal CBS with Explicit Estimation Search can further reduce the size of its search tree and its runtime.

Highlights: The addition of the admissible heuristics proposed in [2] can reduce the number of expanded nodes and runtime of CBS by up to a factor of 50 and thus an handle up to 3 times more agents than possible before within one minute. The bounded-suboptimal MAPF algorithm proposed in [3] can find solutions that are provably at most 2% worse than optimal with 1,000 agents in one minute, while, on the same map, state-of-the-art optimal algorithms can handle at most 200 agents.

Relevant publications: [1] CG heuristicy for CBS, [2] DG and WDG heuristics for CBS, and [3] inadmissible heuristic for bounded-suboptimal CBS.

Lifelong MAPF for Automated Warehousing

Traditional single-agent solver
Our MAPF solver

Today, in automated warehouses, mobile robots already autonomously move inventory pods or flat packages from one location to another. Finding low-cost paths for the robots in real-time is essential for the effectiveness of such systems. However, MAPF is only the “one-shot” variant of the actual problem in many applications. Typically, after an agent reaches its goal location, it does not stop and wait there forever. Instead, it is assigned a new goal location and required to keep moving, which is referred to as lifelong MAPF and characterized by agents constantly being assigned new goal locations. There are two challenges in this problem, namely how to assign tasks to agents and how to decompose the lifelong problem to one-shot MAPF problems.

Highlights: The RHCR algorithm propoased in [3] can produce high-quality solutions for 1,000 agents (= 38.9% of the empty cells on the map) for simulated warehouse instances. The left videos show the performance of 800 agents on the same map with tradional single-agent solver and RHCR.

Relevant publications: [1] MAPF with online task assignment, [2] MAPF with offline task assignment, [3] rolling-horizon collision resolution, and [4] column generation for tasks with time windows.

MAPF for Traffic Management

MAPF can also be used for traffic manangement for autonomous vehicle, trains, or airplanes. This can reduce traffic congestion, energy consumption, and air pollution. The main challenges of applying MAPF to traffic management systems are two-fold. First, the systems are neither perfect nor deterministic. For example, the environment might cause unexpected disturbances, the communication network might not be stable, the agents might have incomplete knowledge of the environment, and the agents might not be able to execute their deterministic MAPF plans perfectly. We need to take such uncertainties into account during path planning and generate robust plans. Second, the sysmtem needs to operate thousands of (or even more) agents in real-time, so extremely efficient MAPF algorithms are required.

Highlights: The MAPF-based software we developed for the NeurIPS’20 Flatland Challenge in [1] can plan collision-free paths for more than 3000 agents within a few minutes and deliver deadlock-free actions in real-time during execution that are robust to unexpexted delays. It outperformed all other solutions, including all reinforcement learning solutions, to win the overall first place in both rounds. A comparison of our solution with top reinforcement learning solutions can be found in [2].

Relevant publications: [1] railway planing and replaning (winner of the NeurIPS’20 Flatland Challenge), [2] railway planing and replaning with MAPF and MARL, and [3] airport taxiway planning.

MAPF for Heterogeneous and Nonholonomic Robots

Mobile robot team
Multi-arm assembly

Agents in MAPF are unrealistic and homogeneous, in the sense that each agent occupies exactly one vertex at any timestep and traverses exactly one edge or wait at its current vertex from one timestep to the next one. In the real world, however, agents might be of different shapes and have different kinematic constraints. Moreover, agents sometimes are required to move to their goal locations while maintaining a desired formation (i.e., spatial pattern), in order to reduce the system cost, increase the robustness and efficiency of the system. Notably, in addition to the traditional mobile robots/drones that naviage in a 2D/3D space, MAPF can be also used for planning trajectories for robotic arms! See the demo on the left (the work is under review at RAL/ICRA2022).

Relevant publications: [1] agents of different shapes, [2] agents of high-dimensional, nonlinear, and nonholonomic dynamics, and [3] agents that move in formation.