Suboptimal conflict based search for multi agent pathfinding

Download

index.pdf

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

217
views

100
downloads

Multiagent pathﬁnding is a problem faced in many ﬁelds 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,weproposedamethodthatimprovestheConﬂict 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-efﬁcient 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

Suggestions

OpenMETU
Core

MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives Oral, Tugcem; Polat, Faruk (2016-01-01) The need for determining a path from an initial location to a target one is a crucial task in many applications, such as virtual simulations, robotics, and computer games. Almost all of the existing algorithms are designed to find optimal or suboptimal solutions considering only a single objective, namely path length. However, in many real life application path length is not the sole criteria for optimization, there are more than one criteria to be optimized that cannot be transformed to each other. In this...
Using Generative Adversarial Nets on Atari Games for Feature Extraction in Deep Reinforcement Learning Aydın, Ayberk; Sürer, Elif (2020-10-05) Deep Reinforcement Learning (DRL) has been successfully applied in several research domains such as robot navigation and automated video game playing. However, these methods require excessive computation and interaction with the environment, so enhancements on sample efficiency are required. The main reason for this requirement is that sparse and delayed rewards do not provide an effective supervision for representation learning of deep neural networks. In this study, Proximal Policy Optimization (PPO) algo...
Schedulability analysis of real-time multi-frame co-simulations on multi-core platforms Ahsan, Muhammad Uzair; Oğuztüzün, Mehmet Halit S.; Department of Computer Engineering (2020) For real-time simulations, the fidelity of simulation does not depend only on the functional accuracy of simulation but also on its timeliness. It is helpful for developers if we can analyze and verify that a simulation will always meet its timing requirements while keeping an acceptable level of accuracy. Abstracting the simulated processes simply as software tasks allows us to transform the problem of verifying timeliness into a schedulability analysis problem where tasks are checked if they are schedulab...
Design and implementation of shared memory and hybrid communication models for portico RTI Özen, Serkan; Temizer, Selim; Department of Computer Engineering (2014) As distributed simulations became a new trend in the simulation world by the end of 1990s, a need for standards that provide rules for intercommunication of complex simulation systems has appeared. High Level Architecture (HLA) has been proposed by the United States Department of Defense (DOD) and has become a widely-used standard for the intercommunication of distributed simulations. The software that implements the HLA standard is called run-time infrastructure (RTI). Various closed and open source RTIs e...
A control system using behaviour hierarchies and neuro-fuzzy approach Arslan, Dilek; Alpaslan, Ferda Nur; Department of Computer Engineering (2005) In agent based systems, especially in autonomous mobile robots, modelling the environment and its changes is a source of problems. It is not always possible to effectively model the uncertainity and the dynamic changes in complex, real-world domains. Control systems must be robust to changes and must be able to handle these uncertainties to overcome this problem. In this study, a reactive behaviour based agent control system is modelled and implemented. The control system is tested in a navigation task usin...

Citation Formats

İ. Y. Karabulut, “Suboptimal conflict based search for multi agent pathfinding,” Thesis (M.S.) -- Graduate School of Natural and Applied Sciences. Computer Engineering., Middle East Technical University, 2019.