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

Kazemy, Omid Khorsand (2018) Hybrid generalized multi-agent pathfinding: a hierarchical method using ASP. [Thesis]

[thumbnail of Restricted to Repository staff only until 24.01.2021] PDF (Restricted to Repository staff only until 24.01.2021)
Restricted to Repository staff only

Download (40MB) | Request a copy


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.
Item Type: Thesis
Additional Information: Yükseköğretim Kurulu Tez Merkezi Tez No: 488367.
Uncontrolled Keywords: Multi-agent pathfinding. -- Multi-robot routing. -- Autonomous warehouses. -- Answer Set Programming. Çoklu etmenler için yol bulma. -- Çözüm kümesi programlama.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 10 May 2018 15:10
Last Modified: 26 Apr 2022 10:23
URI: https://research.sabanciuniv.edu/id/eprint/34776

Actions (login required)

View Item
View Item