Multi-agent path finding

In the multi-agent path finding (MAPF) problem, we are given a set of agents, each with a start and goal position. The task is to find paths for all agents while avoiding any collision. In the k-Robust multi-agent path finding (kR-MAPF) problem, possible delays of agents are also taken into consid...

Full description

Saved in:
Bibliographic Details
Main Author: Jia, Xiaochen
Other Authors: Tang Xueyan
Format: Final Year Project
Language:English
Published: Nanyang Technological University 2021
Subjects:
Online Access:https://hdl.handle.net/10356/148068
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-148068
record_format dspace
spelling sg-ntu-dr.10356-1480682021-04-22T12:10:55Z Multi-agent path finding Jia, Xiaochen Tang Xueyan School of Computer Science and Engineering ASXYTang@ntu.edu.sg Engineering::Computer science and engineering In the multi-agent path finding (MAPF) problem, we are given a set of agents, each with a start and goal position. The task is to find paths for all agents while avoiding any collision. In the k-Robust multi-agent path finding (kR-MAPF) problem, possible delays of agents are also taken into consideration. Conflict-Based Search (CBS) is one of the state-of-the-art optimal MAPF algorithms. It has two levels. The high level divides a MAPF problem into multiple single-agent path finding (SAPF) problems. The low level solves those SAPF problems. k-Robust Conflict-Based Search (kR-CBS) is a variant of CBS specific to kR-MAPF problems. It has an improved version called Improved k-Robust Conflict-Based Search (IkR-CBS). The focus of this Final Year Project is on the study, implementation as well as improvement of CBS and IkR-CBS. In Chapter 1, an introduction to all the problems and algorithms concerned in this project is provided and the project scope is defined. In Chapter 2, my implementation of CBS and IkR-CBS is presented and explained. In Chapter 3, two innovative methods, MA-IkR-CBS & Floating Range Constraints, are introduced to improve the algorithm performance. Experiments are conducted to show that these two methods improve the performance by up to 20% & 7% respectively. Bachelor of Engineering (Computer Science) 2021-04-22T12:10:55Z 2021-04-22T12:10:55Z 2021 Final Year Project (FYP) Jia, X. (2021). Multi-agent path finding. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/148068 https://hdl.handle.net/10356/148068 en SCSE20-0029 application/pdf Nanyang Technological University
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering
spellingShingle Engineering::Computer science and engineering
Jia, Xiaochen
Multi-agent path finding
description In the multi-agent path finding (MAPF) problem, we are given a set of agents, each with a start and goal position. The task is to find paths for all agents while avoiding any collision. In the k-Robust multi-agent path finding (kR-MAPF) problem, possible delays of agents are also taken into consideration. Conflict-Based Search (CBS) is one of the state-of-the-art optimal MAPF algorithms. It has two levels. The high level divides a MAPF problem into multiple single-agent path finding (SAPF) problems. The low level solves those SAPF problems. k-Robust Conflict-Based Search (kR-CBS) is a variant of CBS specific to kR-MAPF problems. It has an improved version called Improved k-Robust Conflict-Based Search (IkR-CBS). The focus of this Final Year Project is on the study, implementation as well as improvement of CBS and IkR-CBS. In Chapter 1, an introduction to all the problems and algorithms concerned in this project is provided and the project scope is defined. In Chapter 2, my implementation of CBS and IkR-CBS is presented and explained. In Chapter 3, two innovative methods, MA-IkR-CBS & Floating Range Constraints, are introduced to improve the algorithm performance. Experiments are conducted to show that these two methods improve the performance by up to 20% & 7% respectively.
author2 Tang Xueyan
author_facet Tang Xueyan
Jia, Xiaochen
format Final Year Project
author Jia, Xiaochen
author_sort Jia, Xiaochen
title Multi-agent path finding
title_short Multi-agent path finding
title_full Multi-agent path finding
title_fullStr Multi-agent path finding
title_full_unstemmed Multi-agent path finding
title_sort multi-agent path finding
publisher Nanyang Technological University
publishDate 2021
url https://hdl.handle.net/10356/148068
_version_ 1698713672353841152