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]

[img]PDF (Restricted to Repository staff only until 24.01.2021) - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

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.

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
ID Code:34776
Deposited By:IC-Cataloging
Deposited On:10 May 2018 15:10
Last Modified:10 May 2018 15:10

Repository Staff Only: item control page