Research

Since August 2021, I have worked as a research assistant in Prof. Sven Koenig’s IDM Lab at USC.

Research interests

My research focuses on fundamental algorithms that help large teams of autonomous agents behave intelligently and safely in dynamic environments. My prior work centered on Multi-Agent Path Finding (MAPF), especially generalizable techniques to identify and break symmetries across MAPF variants (large-agent MAPF and k-robust MAPF).

General MAPF

In a general MAPF problem, we are given a two-dimensional grid where each cell is either an obstacle (e.g., a wall) or free. Each agent has a start and a goal. At each timestep, an agent moves to an adjacent free cell or waits. The task is to return a feasible plan that routes every agent to its goal without conflicts while minimizing the total time over all agents.

MAPF appears in robotics, games, vehicle routing, and more. In automated warehouses, for example, robots fetch items from shelves and bring them to packing stations—often hundreds of robots at once, so collisions must be prevented. That setting maps cleanly to MAPF: each robot is an agent with a start (current pose) and goal (shelf or station).

Large Agent MAPF (LA-MAPF)

LA-MAPF is a variant of traditional MAPF. Unlike traditional MAPF where each agent occupies a single point on the 2-dimensional graph, LA-MAPF agents have a geometric shape, i.e. height and width.

Publication

Mutex Propagation in Multi-Agent Path Finding for Large Agents
Han Zhang, Yutong Li, Jiaoyang Li, T. K. Satish Kumar and Sven Koenig
The 15th Annual Symposium on Combinatorial Search (SoCS 2022)

Abstract: Mutex propagation and its concomitant symmetry-breaking techniques are known to be useful in Multi-Agent Path Finding (MAPF) with single-point agents. In this paper, we show that they can be easily generalized to richer MAPF problems. In particular, we demonstrate its application in MAPF with “Large” Agents (LA-MAPF). Here, agents can occupy multiple points at the same time according to their fixed shapes and sizes. While existing rule-based symmetry-breaking techniques are difficult to generalize from single-point agents to large agents, mutex-based symmetry-breaking techniques can be generalized easily. In a Conflict-Based Search (CBS) framework for LA-MAPF, we also develop a mutex-based conflict selection strategy to further enhance the efficiency of search. Through experiments on various maps, we show that our techniques significantly improve MC-CBS, a state-of-the-art optimal LA-MAPF algorithm, in terms of both success rate and runtime.

Visualization

Please refer to the MAPF Visualizer page for a visualization tool I created.

Other academic interest

Aside from my research area, I’m also a huge fan of theory of computation. I took Prof. Aaron Cote’s CSCI 475: Theory of Computation in Spring 2022, and wrote a project paper titled AKS algorithm: a poly-time decider for primality on the groundbreaking AKS primality testing algorithm.