Multi-agent path finding (part A)
Multi-Agent Path Finding algorithm has become a topic that has been actively researched in the field of Artificial Intelligence. As the technology advances each year, many of our process has been automated and are being carried out by robot agents to complete the tasks. Single-agent path finding alg...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/138430 |
| _version_ | 1811695845890850816 |
|---|---|
| author | Ong, Wei Hua |
| author2 | Tang Xueyan |
| author_facet | Tang Xueyan Ong, Wei Hua |
| author_sort | Ong, Wei Hua |
| collection | NTU |
| description | Multi-Agent Path Finding algorithm has become a topic that has been actively researched in the field of Artificial Intelligence. As the technology advances each year, many of our process has been automated and are being carried out by robot agents to complete the tasks. Single-agent path finding algorithms such as A* focus on a single agent environment where it is unable to be used in a multiple agent environment to provide a solution to solve the multi-agent path finding problem. In this FYP, we use an algorithm, Conflict-Based Search algorithm (CBS), a multi-agent path finding algorithm that uses A* search for low-level searching and heuristic constraints in the high-level searching to solve multi-agent path finding problems. The aim is to find an optimal path for multi-agent path finding problem in grid maps of different dimensions. We employed CBS algorithm to search for multi-agent path finding solution. This algorithm is used to get the time taken for the generation of the optimal path in different scenarios of the grid maps. Our experiments show that the algorithm performs better with fewer agents given an adequate number of obstacles in the map. With a bigger dimension of the map, the algorithm can have a bigger pool of possibility in planning an optimal path for the agents in the map. |
| first_indexed | 2024-10-01T07:29:57Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/138430 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:29:57Z |
| publishDate | 2020 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1384302020-05-06T02:50:29Z Multi-agent path finding (part A) Ong, Wei Hua Tang Xueyan School of Computer Science and Engineering Parallel and Distributed Computing Centre asxytang@ntu.edu.sg Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity Multi-Agent Path Finding algorithm has become a topic that has been actively researched in the field of Artificial Intelligence. As the technology advances each year, many of our process has been automated and are being carried out by robot agents to complete the tasks. Single-agent path finding algorithms such as A* focus on a single agent environment where it is unable to be used in a multiple agent environment to provide a solution to solve the multi-agent path finding problem. In this FYP, we use an algorithm, Conflict-Based Search algorithm (CBS), a multi-agent path finding algorithm that uses A* search for low-level searching and heuristic constraints in the high-level searching to solve multi-agent path finding problems. The aim is to find an optimal path for multi-agent path finding problem in grid maps of different dimensions. We employed CBS algorithm to search for multi-agent path finding solution. This algorithm is used to get the time taken for the generation of the optimal path in different scenarios of the grid maps. Our experiments show that the algorithm performs better with fewer agents given an adequate number of obstacles in the map. With a bigger dimension of the map, the algorithm can have a bigger pool of possibility in planning an optimal path for the agents in the map. Bachelor of Engineering (Computer Science) 2020-05-06T02:48:56Z 2020-05-06T02:48:56Z 2020 Final Year Project (FYP) https://hdl.handle.net/10356/138430 en SCSE19-0142 application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity Ong, Wei Hua Multi-agent path finding (part A) |
| title | Multi-agent path finding (part A) |
| title_full | Multi-agent path finding (part A) |
| title_fullStr | Multi-agent path finding (part A) |
| title_full_unstemmed | Multi-agent path finding (part A) |
| title_short | Multi-agent path finding (part A) |
| title_sort | multi agent path finding part a |
| topic | Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity |
| url | https://hdl.handle.net/10356/138430 |
| work_keys_str_mv | AT ongweihua multiagentpathfindingparta |