Suboptimal conflict based search for multi agent pathfinding

Date

2019

Author

Karabulut, İlhan Yoldaş

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

3
views

0
downloads

Multiagent pathfinding is a problem faced in many fields including computer games, simulation software, and robotics. These applications generally require complete and real-time solutions. The class of methods which solves the problem optimally and completely spends much more time than real-time solutions. The algorithms to solve the problem within expected time limits, are mostly incomplete and do not guarantee anoptimumsolution. Inthisthesis,weproposedamethodthatimprovestheConflict Based Search algorithm which is complete and optimum. In this way, we combined the features of two different classes of solutions to develop an algorithm that can be used in real-life problems. Using a heuristic-based approach, we developed an algorithm which is complete, time-efficient and producing near-optimal solutions. We compared our method with CBS and suboptimal algorithms experimentally and showed the advantage of our proposed method.

Subject Keywords

Computer algorithms., Keywords: Path Finding, Multiagent Agent Path Findig, Search-Based Solutions,Optimal Solvers, Suboptimal Solvers.

URI

http://etd.lib.metu.edu.tr/upload/12624303/index.pdf
https://hdl.handle.net/11511/44180

Collections

Graduate School of Natural and Applied Sciences, Thesis