Multi-agent path finding
The Multi-Agent Path Finding (MAPF) problem is about finding the paths for multiple agents from a source vertex to a target vertex. The key is to design and implement a collision-free algorithm with consideration of different types of constraints. It has many real-life applications, especially in th...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/165898 |
| _version_ | 1811694568467333120 |
|---|---|
| author | Feng, Qingyu |
| author2 | Tang Xueyan |
| author_facet | Tang Xueyan Feng, Qingyu |
| author_sort | Feng, Qingyu |
| collection | NTU |
| description | The Multi-Agent Path Finding (MAPF) problem is about finding the paths for multiple agents from a source vertex to a target vertex. The key is to design and implement a collision-free algorithm with consideration of different types of constraints. It has many real-life applications, especially in the robotics and path planning fields.
A state-of-art optimal algorithm Conflict-Based Search (CBS) is studied and implemented. It has two levels, the high-level search makes use of a constraint tree to detect conflicts between agents and generates constraints for agents while the low-level search will find optimal paths for each agent. A more general form and an enhancement of CBS, Meta-Agent Conflict-Based Search (MA-CBS), is able to perform a merge action of agents based on merge policy. It is considered as a framework constructed over any complete and optimal MAPF low-level solver. However, the (MA-) CBS does not perform very well on large maps, to improve the search speed, Safe Interval Path Planning, a path planning algorithm that uses a concept of safe interval to ensure collision avoidance while optimizing the path for agents, is studied.
This Final Year Project focuses on the study and implementation of CBS, MA-CBS, and SIPP algorithms. An innovative combination of the CBS and SIPP algorithm is also explored.
Experiments are carried out for CBS, MA-CBS, and SIPP algorithms. The results show that the (MA-) CBS algorithm with A* as a low-level solver can produce an optimal solution. The combination of the CBS and SIPP algorithm can largely improve the success rate and reduce the calculation time by 100 times. |
| first_indexed | 2024-10-01T07:09:39Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/165898 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:09:39Z |
| publishDate | 2023 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1658982023-04-21T15:36:48Z Multi-agent path finding Feng, Qingyu Tang Xueyan School of Computer Science and Engineering ASXYTang@ntu.edu.sg Engineering::Computer science and engineering The Multi-Agent Path Finding (MAPF) problem is about finding the paths for multiple agents from a source vertex to a target vertex. The key is to design and implement a collision-free algorithm with consideration of different types of constraints. It has many real-life applications, especially in the robotics and path planning fields. A state-of-art optimal algorithm Conflict-Based Search (CBS) is studied and implemented. It has two levels, the high-level search makes use of a constraint tree to detect conflicts between agents and generates constraints for agents while the low-level search will find optimal paths for each agent. A more general form and an enhancement of CBS, Meta-Agent Conflict-Based Search (MA-CBS), is able to perform a merge action of agents based on merge policy. It is considered as a framework constructed over any complete and optimal MAPF low-level solver. However, the (MA-) CBS does not perform very well on large maps, to improve the search speed, Safe Interval Path Planning, a path planning algorithm that uses a concept of safe interval to ensure collision avoidance while optimizing the path for agents, is studied. This Final Year Project focuses on the study and implementation of CBS, MA-CBS, and SIPP algorithms. An innovative combination of the CBS and SIPP algorithm is also explored. Experiments are carried out for CBS, MA-CBS, and SIPP algorithms. The results show that the (MA-) CBS algorithm with A* as a low-level solver can produce an optimal solution. The combination of the CBS and SIPP algorithm can largely improve the success rate and reduce the calculation time by 100 times. Bachelor of Engineering (Computer Science) 2023-04-16T04:32:51Z 2023-04-16T04:32:51Z 2023 Final Year Project (FYP) Feng, Q. (2023). Multi-agent path finding. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/165898 https://hdl.handle.net/10356/165898 en SCSE22-0224 application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering Feng, Qingyu Multi-agent path finding |
| title | Multi-agent path finding |
| title_full | Multi-agent path finding |
| title_fullStr | Multi-agent path finding |
| title_full_unstemmed | Multi-agent path finding |
| title_short | Multi-agent path finding |
| title_sort | multi agent path finding |
| topic | Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/165898 |
| work_keys_str_mv | AT fengqingyu multiagentpathfinding |