Thu, Jun 16, 2022 @ 04:00 PM - 06:00 PM
PhD Candidate: Jiaoyng Li
Efficient and Effective Techniques for Large-Scale Multi-Agent Path Finding
Sven Koenig, T. K. Satish Kumar, Satyandra K. Gupta, Nora Ayanian , and Brian C. Williams.
There is no doubt that robots will play a crucial role in the future and need to work as a team in increasingly more complex applications. Advances in robotics have laid the hardware foundations for building large-scale multi-robot systems, such as for mobile robots, vehicles, and drones. But how to coordinate robots intelligently is a difficult problem. In this dissertation, I introduce planning algorithms for solving this challenge with a focus on one fundamental problem: letting a large team of agents navigate without collisions in congested environments while minimizing their travel times. I present techniques based on heuristic search, symmetry breaking, and stochastic local search that can efficiently and effectively coordinate hundreds of agents with rigorous guarantees of completeness and even optimality and thousands of agents with good empirical performance (although no theoretical guarantees). These techniques speed up optimal and bounded-suboptimal algorithms by up to four orders of magnitude without sacrificing their theoretical guarantees and improve the solution quality of non-optimal algorithms by up to thirty-six times.
Audiences: Everyone Is Invited
Contact: Lizsl De Leon