Events Calendar

Planning paths for Multiple Agents - Talk by Guni Sharon

Speaker: Guni Sharon, Ben-Gurion University, Information Systems Engineering Department

Title: Planning paths for Multiple Agents

Abstract: Pathfinding for a single agent in a map is a well-known problem with applications in GPS applications, robotics, digital entertainment, and automated planning. This problem can be solved optimally in polynomial time, and current techniques are able to find paths in graphs with hundreds of millions of intersections within seconds. In my talk I will present the multi-agent path finding (MAPF) problem, where the task is to plan paths for a group of agents in a joint state space. Applications of MAPF include motion planning for a team of robots, traffic management, evacuation from danger zones, video games and warehouse management. Unlike its single-agent counterpart, solving MAPF optimally is an NP-Hard problem, whose complexity grows roughly exponentially with the number of agents. The ncreased complexity stems from the hard constraint that agents must not be assign overlapping paths (the agents must never collide with each other).

Despite the NP-Hardness of MAPF, current techniques are able to solve MAPF optimally for more than a hundred agents. I will survey several of these techniques, manly: extensions to the A* search algorithm, decomposing a complex MAPF into a sequence of easier problems and reducing MAPF to other known problems. I will attempt to characterize the domains on which each of the techniques performs well. Lastly, I will show that by allowing a small, bounded, amount of suboptimality, problems with more than 250 (!!) agents can be solved.

Guni Sharon is a PHD student at Ben-Gurion University, Israel. He is part of a research group led by Prof. Ariel Felner and Dr. Roni Stern. He obtained his B.Sc. and M.Sc. degrees from the Information Systems Engineering Dpt. at Ben-Gurion University. Guni’s main research interests lie in heuristic search and optimization. Guni presented several novel techniques for solving the Multi-Agent Pathfinding problem. His interests also cover Real-Time Search and Constraint Programing

Location: Kaprielian Hall (KAP) - 146

Audiences: Everyone Is Invited

Contact: Lizsl De Leon