A Tool for grid based map generation and path planning

Abstract

ÖZET Sayısal haritalar üzerinde iki nokta arasında yolculuk edecek bir robotun engellerden kaçınarak, en uygun yolu bulmasını sağlayan çeşitli yol planlama algoritmaları bulunmaktadır. Bu zor problem üzerinde çalışan birçok araştırmacı vardır. Bununla birlikte sayısal haritalar üzerinde örnek problem teşkil edecek ve çözüm sağlayacak yeterli düzeyde araç bulunmamaktadır. DimaG-2P diye adlandırdığımız araçla, sayısal bir harita oluşturulabilmesi ve yol planlama probleminin çözülebilmesi amaçlanmıştır. Hatta, bu araca, değişik arazi tiplerinden oluşan sanal bir çevrede yol planlama algoritmalarının çözüme nasıl yaklaştığının izlenebilmesine imkan tanıyan bir özellik de eklenmiştir. DimaG-2P kullanıcı dostu bir arayüze sahiptir. Kullanıcılar sanal bir harita yaratabilir, görüntülüyebilir yada haritayı değiştirebilirler. Başlangıç ve hedef noktalarım belirlenerek, örnek problemler yaratılabilir. DimaG-2P, her bir arazi tipi için daha önceden belirlenmiş ağırlık değişkenlerini kullanarak, seçili bir harita üzerinde A* veya GA (Genetik Algoritma - Genetic Algorithms) kullanarak yol planlama sorunlarım çözmektedir. GA'nın kullanımının gerekliliğini gösteren teorik analizler yapılmıştır. Her bir algoritmadaki ilgili değişkenler kullanıcı arayüzünden tammlanabilmektedir. Sanal robotun sekiz yönde haraket kabiliyeti olduğu varsayılmıştır. Nesne yönelimli tasarım sayesinde, yeni yaklaşımlar veya hareket tipleri DimaG-2P içerisine kolayca gömülebilmektedir. Aracın çalışmasını doğrulamak ve sonuçlan hızlı bir şekilde elde edebilmek için, A* için farklı buluşsal yaklaşımlar ve veri yapılan gerçeklenmiştir. DimaG-2P kullanılarak birçok farklı ortam yaratılmış ve bu sanal ortamlarda bütün buluşsal metodlar ve farklı GA uzmanlan test edilmiştir. Deneysel sonuçlar beklentileri karşılayarak, A* 'm doğru çalıştığım göstermiş ve GA'nın yol planlama için gelecek vaad eden bir yaklaşım olduğunu ortaya koymuştur. XV

ABSTRACT There is a variety of path planning algorithms for finding the optimal path for a robot to travel between two points on a digital map, avoiding the obstacles along the way. Being a hard problem to deal with, many scientists are involved in this problem. Yet, there are not many tools for solving this problem. Another difficulty in this problem is to create problem instances on discrete maps. A tool named as DimaG-2P (Discrete map Generator and Path Planning), is designed for both generating discrete maps and solving path planning problem. Furthermore, as a utility, visualization is added to follow how the related algorithms advance towards a solution in a virtual environment consisting of multi terrain types. The DimaG-2P has a very user friendly interface. Users can create, display and modify a virtual map. By setting start and target points, problem instances can be created. DimaG-2P attacks path planning problem using either A* or Genetic Algorithms (GAs) on a selected map with predefined cost values assigned for each terrain type. Theoretical analyses are presented, supporting the use of GAs. All the parameters related to both of the approaches are configurable by the user. The agent is assumed to be able to move in all eight directions. Due to the object oriented design, new approaches or movement types can be embedded into DimaG-2P easily. In order to verify the tool and obtain the result fast, different heuristics and data structures are implemented for A*. Using DimaG-2P, several different virtual environments are created and these heuristics and different GA operators are tested on these virtual environments. Empirical results maintained the expectations, establishing that A* works correctly and GA is a promising approach for solving path planning. XTV