Suboptimal conflict based search for multi agent pathfinding

Download
2019
Karabulut, İlhan Yoldaş
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.

Suggestions

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.