Kompleks dış ortamlar için sezgisel güzergah planlama algoritmaları

Abstract

Bu tezde a) A* algoritmasının kompleks harita kurguları için genellenmesi ve b) A* algoritmasının geliştirilerek düğüm keşfeden seviye tabanlı yeni bir versiyonunun (DS-A*) gene kompleks dış ortamlar için önerilmesi konularında çalışmalar yapılmıştır. Gerçek hayatta karşımıza çıkan dış mekanlarda güzergah belirleme probleminde arazi yapıları önemli ölçüde çeşitlilik göstermektedir. A* algoritması vasıtasıyla bu tip karmaşık ortamlarda en uygun güzergahın bulunabilmesi amacıyla bu algoritmanın tadil edilmesi önemlidir. Öte yandan A* algoritmasının en önemli handikaplarından birisi ölçeklendirilebilir olmamasıdır. Haritalar büyüdükçe A* algoritmasının güzergah hesaplama yükü ve haliyle hesaplama için gereken zaman üstel şekilde artmaktadır. Seviye kümesi algoritmasının seviye özelliği, Dijkstra algoritmasının yeni düğümleri keşfetme yöntemi ve A* algoritmasının sezgiselliği hibritlenerek bu tezde önerilen DS-A* algoritması, A* algoritmasının performansında önemli iyileştirmeler sağlamıştır.

In this thesis, we study a) generalization of A* algorithm for complex environments and b) a new version of A* node detecting and level based version is proposed for quicker route planning for complex map scenarios. In real world, there is a significant variation in landscapes of maps. It is important to modify this algorithm in order to find the most suitable route in such complex environments via A* algorithm. On the other hand, one of the disadvantages of A* algorithm is that it is not scalable. As the maps grow, the calculation load of A* algorithm and the time required for route estimation increases rapidly. The level feature of the level set algorithm, the method of discovering new nodes of Dijkstra algorithm and the intuition behind A* algorithm are adopted and the proposed DS-A* algorithm provided significant improvements over the performance of A* algorithm.