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.
- [2021/08] I was selected to participate in the Rising Stars in EECS 2021 workshop at MIT.
- [2021.08] Our system demonstration on railway planning received the People’s Choice Best System Demonstration Award at ICAPS 2021. Check out our video here.
- [2021.05] I received a WISE Merit Award from USC.
- [2021.05] I received a Computer Science Best Research Assistant Award from USC.
- [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!
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:
- Improving the scalability of MAPF algorithms:
- Developing symmetry breaking techniques to reduce the search space.
- Introducing informed heuristics to conflict-based search to guide the search direction.
- Applying MAPF to various multi-agent systems:
- Applying MAPF to automated warehousing.
- Applying MAPF to traffic management.
- Applying MAPF to multi-robot systems with heterogeneous and nonholonomic robots.
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  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:  rectangle symmetry,  corridor and target symmetries,  generalized rectangle, target, and corridor symmetry reasoning,  automatic symmetry reasoning by mutex propagation (ICAPS’20 outstanding student paper),  mutex propagation for SAT-based MAPF,  symmetry reasoning for k-robust MAPF, and  symmetry reasoning with bounded-suboptimal CBS.
Heuristics for MAPF with Conflict-Based Search
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  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  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.
Lifelong MAPF for Automated Warehousing
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  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.
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  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 .
MAPF for Heterogeneous and Nonholonomic Robots
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:  agents of different shapes,  agents of high-dimensional, nonlinear, and nonholonomic dynamics, and  agents that move in formation.