Research
Long-term decision making for multiple agents

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.

• See [AAMAS2019a] [AAAI2019b] [AAMAS2017] [AAMAS2016] [AAAI2016].

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.

• See [IEEE2017] [IJCAI2017] [IROS2016] [ICAPS2016]

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.

• See [AAAI2017] and an earlier work on POMDP planning [AAAI2015].

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.

• See [IJCAI2018a] and [AAMAS2018].

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.

• See [AAAI2019a].

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.

• See [AIIDE2017] and a survey paper [AAAI2016 Workshop].

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.

• See [ICAPS2019] [AAMAS2019] [AAAI2019c] [AAAI2019d] [ICAPS2018].

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

• See [IJCAI2018b].