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...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
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 |