Hybrid generalized multi-agent pathfinding: a hierarchical method using ASP

Official URL: http://risc01.sabanciuniv.edu/record=b1669814 (Table of Contents)

Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, without colliding with any obstacles. Multi-agent pathfinding (MAPF) also aims to plan such routes for each agent such that no two agents collide with each other. MAPF is an intractable problem, because agents must avoid the collision with each other. We study a generalized version of MAPF (GMAPF) in the context of robotics (i.e., autonomous warehouses), where multiple robots must visit some locations (e.g., to collect some items) on the way to their destinations without colliding with any obstacles in the environment. In this thesis, we introduce a novel method to solve GMAPF problems using the expressive logic-based language of Answer Set Programming (ASP) and the efficient ASP solvers. Moreover, to ensure that the robots follow collision-free trajectories, we introduce an intelligent method for feasibility checks and their integration to our ASP-based approach to GMAPF. To further improve the scalability of our method to solve hybrid GMAPF problems, we introduce a hierarchical method to handle problem instances over large environments. Based on that, we introduce a greedy algorithm handle instances with large number of robots We experimentally evaluate our methods over randomly generated problem instances, to show the scalability of our hierarchical and greedy methods, and usefulness of ASP-based hybrid pathfinding.