Navigasyon sistemlerinde zamana bağlı engel modeli ile en iyi rota planlaması

Abstract

Engeller bulundukları yolun erişilebilirlik maliyetini arttırdığı için zamana bağlı uygulama alanlarında iletişime/ulaşıma etki etmektedir. Halihazırdaki çalışmalarda, engeller iki farklı yaklaşıma bağlı olarak modellenmektedir. En temel yaklaşımda, engellerin yol ağında kalıcı olduğu kabul edilmektedir ve en iyi rota planı hesaplamasında engelin bulunduğu yol topolojik olarak dikkate alınmamaktadır. Diğer yaklaşımda ise sadece konumu ve boyutu değişen engellerin zamana bağlı maliyetleri dikkate alınmaktadır. Ancak farklı özelliklere sahip tüm engellerin zamana bağlı maliyetini hesaplayan bir yaklaşım önerilmemektedir. Bu çalışmada statik, süreli, periyodik, hareketli ve dinamik engeller olmak üzere beş farklı kategoriyi içeren zamana bağlı evrensel bir engel modeli önerilmiştir. Engelden kaçınan rota planını hesaplamak için Engelden Kaçınan Rotalama (EKR) algoritması, engelin zamana bağlı maliyetini dikkate alan rota planını hesaplamak için ise Engel Farkında Rotalama (EFR) algoritması geliştirilmiştir. Her iki algoritma da Dijkstra algoritmasının genişletilmiş bir versiyonudur. EFR algoritması ile EKR algoritmasının karşılaştırmalı deney sonuçları sunulmuştur. Deney sonuçları zamana bağlı olarak engelleri dikkate alan algoritmanın, engelden kaçınan algoritmaya göre daha iyi sonuçlar ürettiğini göstermiştir.

Obstacles increase the reachability cost of the road they belong, thus they affect the communication/navigation in time-dependent application areas. In current studies, obstacles are modeled based on two different approaches. Typically, obstacles are modeled as persistent objects in road networks and they are topologically disregarded in the planning algorithms. The other approach only regarded the time-dependent costs of obstacles changing its location and size. However, a time dependent common obstacle model is not presented. In this study, a time dependent common obstacle model containing five different categories including as static, periodic, temporary, moving and dynamic obstacles is proposed. Obstacle Avoid Routing (EKR) algorithm to calculate obstacle avoiding route plan, and Obstacle Aware Routing (EFR) algorithm to calculate the route plan considering the time dependent cost of the obstacles, are developed. Both algorithms are an extended version of the Dijkstra algorithm. Experimental comparison of EKR algorithm and EFR algorithm results are presented with time dependent common obstacle model. Experimental results showed that obstacle aware algorithm produces better cost than the obstacle avoiding algorithm.