Research
Long-term decision making for multiple agents

See my research statement.

Overview

Teams of agents often have to constantly assign tasks among themselves and then plan collision-free paths to the task locations. For example, together with researchers from NASA's Ames research center, I envision a future in which autonomous aircraft towing vehicles tow aircraft all the way from the runways to their gates (and vice versa), thereby reducing pollution, energy consumption, congestion, and human workload. With support from Amazon Robotics and Alibaba, I tackle computational problems arising in challenging scenarios in which hundreds of robots navigate autonomously in warehouses to move inventory pods all the way from their storage locations to the inventory stations that need the products they store (and vice versa).

The coordination problems for these agents are NP-hard in general, yet one must assign tasks and find high-quality collision-free paths for them in real-time. I therefore study different versions of task-assignment (TA) and multi-agent pathfinding (MAPF) problems, their complexities, algorithms for solving them, and their applications. My work unifies tools and techniques from the artificial intelligence, robotics, operations research, and theoretical computer science communities to establish an algorithmic foundation for making fast and good decisions to coordinate the long-term task- and path-planning operations for real-world multi-agent systems at a scale of hundreds of agents and thousands of tasks.

  • Tutorial slides on a subset of my research at Cainiao, Alibaba: [pdf]
  • AI Matters article on Multi-Agent Path Finding for general audience: [link]
  • Survey on a subset of my research at IJCAI-2016 workshop: [link]
  • Blue-sky research on autonomous airport surface operations: [link]

Robust Long-Term Task and Path Planning for Large-Scale Multi-Agent Systems (Thesis Research)

I formalize and study novel problem formulations, e.g., Combined Task Assignment and Path Finding (TAPF) and Multi-agent Pickup and Delivery (MAPD), that capture both the task- and path-planning aspects of the coordination problems in these multi-agent systems. I then establish an algorithmic framework that exploits the combinatorial structure of the problems, allows for efficient and effective solutions for the whole system, and utilizes domain-specific environmental characteristics to ensure the robustness for the long-term autonomy of these systems. As an example, this framework scales to 250 robots and 2,000 tasks (Figure 1) using 10 seconds of runtime on a laptop computer. It results from three phases of my thesis work, which leverage insights and tools from (1) operations research and theoretical computer science to characterize the computational difficulty and capture the combinatorial structure, (2) AI to provide algorithmic solutions that are efficient and effective by exploiting the combinatorial structure, and (3) robotics to ensure system robustness.

A Hierarchical Framework for Plan Generation and Execution in Multi-Robot Systems

Together with other robotic researchers, we develop a hierarchical framework for coordinating task- and motion-level operations in multi-robot systems. Our framework is based on the idea of using simple temporal networks to simultaneously reason about precedence/causal constraints required for task-level coordination and simple temporal constraints required to take some kinematic constraints of robots into account. In the plan-generation phase, the framework provides a computationally scalable method for generating plans that achieve high-level tasks for groups of robots and take some of their kinematic constraints into account. In the plan-execution phase, the framework provides a method for absorbing an imperfect plan execution to avoid time-consuming re-planning in many cases. We use the multi-robot path-planning problem as a case study to present the key ideas behind our framework for the long-term autonomy of multi-robot systems.

Uncertainty, Tasks with Deadlines, and Prioritized Planning in Multi-Agent/Robot Systems

For systems with uncertain kinematics and dynamics, I develop a planning and execution algorithmic framework for robust plan execution under uncertainty. It uses a probabilistic model of uncertainty in agent motions and robust plan-execution policies, that together bridge the gap between planning algorithms and the imperfection in plan execution by simultaneously reasoning about precedence/causal constraints required for task-level coordination and temporal constraints required for motion-level coordination. It also avoids intensive communication between robots when used in a distributed setting.

For tasks with temporal constraints, I formalize the problem of Multi-Agent Path Finding with Deadlines and study the complexity of solving it optimally. Despite the NP-hardness of the problem, I develop several optimal algorithms that scale to dozens of robots in minutes and can eventually be used in real-world applications, e.g., to maximize profits for robots catching deadlines of the shipping orders in an automated warehouse or to minimize loss for robots evacuating before a disaster occurs in inclement or adversarial conditions in an extraterrestrial exploration.

For large-scale systems that require real-time path-planning computation of high-quality solutions, I develop a novel prioritized path-planning framework for multi-agent systems that scales to 600 agents in 30 seconds of runtime and produces close-to-optimal solutions.

In addition to existing real-world multi-robot systems, I also generalize my framework to many different application domains, e.g., planning for video game characters and other domains that involve decision making for multiple agents.

Improvements to Multi-Agent Path-Finding Algorithms

Together with researchers from other areas, we have found great success in improving the efficiency of multi-agent path-finding algorithms by combining combinatorial search techniques with techniques for solving integer linear programming, Boolean satisfiability, and constraint satisfaction problems and leveraging insights from robotics to exploit the problem structure.

We have also developed an anytime bounded-suboptimal seach framework that also improves multi-agent path-finding algorithms by leveraging incremental search techniques.


More coming...

Image

More coming...

Image

More coming...

Image

More coming...

Image