Events Calendar

Thesis Proposal - Jiaoyang Li

Title:

Efficient and Effective Multi-Agent Path Finding via Heuristic Search, Symmetry Breaking, and Large Neighborhood Search


Time:

2:00-3:30pm PST, May 10 (Monday)

Committee: Sven Koenig, Nora Ayanian, Bistra Dilkina, T. K. Satish Kumar, Satyandra K. Gupta, and Brian Williams (MIT)

Zoom link:

https://usc.zoom.us/j/96942890548?pwd=SkFzQm80cHNOMHBPQXZBa1N3eVZvZz09


Abstract:

Recent advances in robotics have laid the foundation for building large-scale multi-agent systems. One fundamental task in many multi-agent systems is to navigate teams of agents in a shared environment to their target locations without colliding with obstacles or other agents. Applications include evacuation, formation control, object transportation, traffic management, search and rescue, autonomous driving, drone swarm coordination, video game character control, and large-scale warehouse automation, to list a few. One well-studied abstract model for this problem is known as Multi-Agent Path Finding (MAPF). MAPF is NP-hard to solve optimally (or, in some cases, even bounded-suboptimally) in general. Existing algorithms for solving MAPF either have limited scalability, generate costly solutions, or fail to find any solutions for hard MAPF problems. I propose to develop fundamental techniques for solving MAPF more efficiently and effectively that exploit the combinatorial structure of the MAPF problem and combine ideas from both AI and OR. In particular, I design admissible heuristics by cost partitioning (ideas from the AI planning community) to speed up optimal MAPF algorithms. I also develop symmetry-breaking constraints (ideas from the constraint programming community) to eliminate symmetries in optimal MAPF solving. For future work, I plan to learn inadmissible heuristics (ideas from the heuristic search community) to speed up bounded-suboptimal MAPF algorithms and build an anytime MAPF framework via large neighborhood search (ideas from the constraint programming and operations research communities) to improve the success rate and the solution quality of non-optimal MAPF algorithms.

WebCast Link: https://usc.zoom.us/j/96942890548?pwd=SkFzQm80cHNOMHBPQXZBa1N3eVZvZz09

Audiences: Everyone Is Invited

Contact: Lizsl De Leon