In recent years, finding a path for a moving agent has become relevant to many real-world applications, including autonomous driving cars, moving robots, and flying drones. Finding the optimal (shortest) path can be calculated by Heuristic Search algorithms, such as the well-known A* algorithm. These algorithms use heuristics, which estimate the distance to the destination, to intelligently guide the search and quickly return a solution. In automated warehouses and many other applications, multiple agents exist. In such cases, often, the agents must coordinate to solve the problem. For instance, the agents may need to avoid collisions, which occur when two agents are simultaneously at the same location. In this talk, I will discuss two common problems of finding a plan (a set of paths) for multiple moving agents.
The first is called Multi-Agent Path Finding (MAPF). MAPF is the problem of finding a plan for moving a group of agents from their initial locations to their destinations without collisions. Conflict-Based Search is the state-of-the-art algorithm for calculating an optimal MAPF plan. While the plan is collision-free, in some cases, following this plan may not be possible due to unexpected events that delay some of the agents. Therefore, I will introduce different ways to create a robust MAPF plan that can be followed without causing collisions, even if such delays occur.
The second problem is called Multi-Agent Meeting (MAM), where the task is to find an optimal meeting location for multiple agents and paths to that location. MAM is a challenging problem as, in contrast to MAPF, the destination of the agents is not specified. Therefore, estimating the distance to the destination is not trivial when Heuristic Search is used to solve MAM. Nevertheless, MM* is a heuristic search algorithm that can do so. Moreover, I will present CF-MAM, the version of MAM that, similarly to MAPF, does not allow collisions.
Dor Atzmon is a postdoctoral research associate at the department of Computer Science at Royal Holloway, University of London. He received his BSc, MSc, and Ph.D. in Software and Information Systems Engineering from Ben-Gurion University. His research interests include heuristic search, optimization problems, automated planning, and game-playing.