Haku

Comparing Path-Finding Algorithms and Machine Learning Model

QR-koodi

Comparing Path-Finding Algorithms and Machine Learning Model

This thesis focused on comparing A-star algorithm and some of its variants against Q-learning and Proximal Policy Optimization algorithms in terms of path finding and in game development perspective. Both Q-learning and proximal policy algorithm are reinforcement learning algorithms which is a subsection of machine learning. The goal of the thesis was to analyse the viability of using reinforcement learning in path finding in game development instead of traditional algorithms and discover the strengths and weaknesses of each method and possible future developments. The thesis subject was a personal topic of interest of the writer. At first the thesis introduced different kinds of path finding techniques in game development like navigation mesh and way-points based navigation. It described the A-star algorithm in detail using pseudocode and compared the standard algorithm to different A star variants, for example D-star lite. Next, the author described the basics of machine learning, neural networks and reinforcement learning using Markov Decision process before going deeper into Q-learning algorithm and proximal policy algorithm. After this the thesis described experiments done using a Minigrid library in order to gather knowledge and data regarding the differences of the algorithms. During the thesis a simple simulation game was developed where a deep reinforcement learning agent needs to navigate though a simple maze from start to end position. The simulation game was used in experiments to gather knowledge and performance data of the algorithms. The chapters described the different types of scenarios developed and the results for each algorithm. At the end of the thesis the author had conclusions of the results and ideas for future development. The main conclusion was that using reinforcement learning for path finding is not viable because of the complexity and cost of the training. A-Star was also significantly more performant finding the path. However, author suggested studying alternative deep reinforcement learning algorithms which might yield better results. Author also explained that it might make sense to use reinforcement learning in other areas of the game development.

Tallennettuna:
Kysy apua / Ask for help

Sisältöä ei voida näyttää

Chat-sisältöä ei voida näyttää evästeasetusten vuoksi. Nähdäksesi sisällön sinun tulee sallia evästeasetuksista seuraavat: Chat-palveluiden evästeet.

Evästeasetukset