Yerel benzetim modellerinde kalabalığın genel gezinim bilgisinin kullanım biçimlerinin ve katkılarının araştırılması
Investigation on usage types and contributions of global navigation information of the crowd in the local simulation models
Yazar: CUMHUR YİĞİT ÖZCAN
Danışman: PROF. DR. EBRU AKÇAPINAR SEZER ; DR. MURAT HACIÖMEROĞLU
Hacettepe Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2017
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Benzetim = Simulation ; Benzetim modeli = Simulation model ; Benzetim sistemi = Simulation system ; Benzetim tekniği = Simulation technique ; Benzetim yöntemi = Simulation method ; Bilgisayar grafikleri = Computer graphics ; Bilgisayar oyunları = Computer games ; Kalabalık = Crowd ; Yol planlama = Path planning

Özet:
Kalabalık gezinimi, kalabalık benzetimi alanındaki oldukça zorlu problemlerden birisidir. Gezinim problemi için ilk olarak kalabalıktaki her bir bireyi ayrı ayrı ele alan ve onların kısa vadeli hareketlerini planlayan yerel gezinim yöntemleri önerilmiştir. Daha sonra kalabalığa bir bütün olarak yaklaşan geniş çaplı gezinim yöntemleri ve bu iki türün başarılı olduğu unsurları bir araya getirmeyi hedefleyen karma gezinim yöntemleri geliştirilmiştir. Karma gezinim yöntemleri çoğunlukla daha fazla işlem yapmaları gerektiği için daha maliyetli yöntemler olmakla birlikte, maliyet makul bir seviyede tutulabildiğinde yerel ve geniş çaplı yöntemlerden çok daha başarılı sonuçlar üretebilmektedirler.
Gezinim yöntemlerinin başarımı benzetimdeki bireylerin hedeflerine mümkün olan en az çabayı harcayarak varmalarına bağlıdır. Bunun için benzetim ortamında farklı yönlere gitmeye çalışan bireylerin sebep dolduğu sıkışıklıkların en aza indirgenmesi ve kalabalığın bir akış içerisinde hareket etmesi gerekmektedir. Bu amaca ulaşılabilmesi için bireylerin geniş çaplı yol planlarının sadece benzetim ortamında bulunan sabit engeller değil diğer bireylerin anlık konumları ve geleceğe yönelik planları da dikkate alınarak yapılması gerekmektedir.
Bu tez çalışmasında diğer bireylerin genel gezinim bilgisinin hareket doğrultularını da içerecek şekilde çıkarılıp benzetim ortamında saklandığı ve sonrasında diğer bireyler tarafından geniş çaplı yol planlama aşamasında kullanıldığı iki yeni benzetim yöntemi önerilmiştir.
Bu yöntemlerden ilki olan Potansiyel Bilgisi Kullanımıyla Geniş Çaplı Yol Planlama Yöntemi'nde kalabalığın genel gezinim bilgisi potansiyel değerlerle temsil edilmektedir. Geniş çaplı yol planları potansiyel bilgiye dönüştürülürken ve bu bilginin geniş çaplı yol planlamada kullanılmasında bazı sezgisel kararlar verilmiştir. Yapılan geniş çaplı yol planları yerel bir gezinim yöntemiyle birleştirilerek kullanılmıştır. Sadece yerel bir gezinim yöntemi kullanılan bir sistemle yapılan karşılaştırmalı testler genel gezinim bilgisinin yerel gezinim yönteminde yol gösterici olarak kullanılmasının gezinim başarımını büyük oranda arttırdığını göstermiştir. Bu yöntem ayrıca benzetim ortamında bir akış yaratarak olası çarpışmaların sayısını en aza indirgediği için yerel gezinim yönteminin işlem maliyetini büyük oranda düşürmüştür.
Geliştirilen ikinci yöntem ise Zaman Tabanlı Geniş Çaplı Yol Planlama Yöntemi'dir. Bu yöntemde geniş çaplı yol planları zaman tabanlı olarak yapıldığı için gerek kalabalığın genel gezinim bilgisinin çıkarılması gerekse bu bilginin kullanılması süreçleri potansiyel tabanlı yönteme göre çok daha belirleyici şekilde gerçekleştirilmiştir. Geniş çaplı yol planlarının zaman tabanlı olarak yapılabilmesi için makine öğrenmesi yöntemlerinden faydalanılmıştır.
Makine öğrenmesi yöntemlerinde kullanılmak üzere bir mikro benzetim ortamından öğrenme verisi toplanmış ve daha sonra bu verinin tamamı kullanılarak eğitilen modeller orta ve makro ölçekteki gerçek benzetim senaryolarında test edilmiştir. Dolayısı ile bu tez çalışmasında öğrenmeye dayalı yöntemlerin geniş çaplı yol planlamada kullanılma şekliyle ilgili geleneksel makine öğrenmesi yaklaşımından farklı yeni bir uygulama şeması da önerilmiş olmaktadır.
Zaman tabanlı yöntemin başarımı potansiyel tabanlı yöntemle yapılan karşılaştırmalı testlerle ölçülmüştür. Sonuçlar zaman tabanlı yöntemin daha iyi bir gezinim sistemi olduğunu ancak görece biraz daha fazla işlem gücü gerektirdiğini göstermiştir.

Abstract:
Crowd navigation is one of the quite challenging problems in crowd simulation. Local navigation methods that consider each agent in crowd individually and plan their short term movements have been initially proposed for the navigation problem. Later, global navigation methods that approach the crowd as a whole and hybrid navigation methods that aim combining successful elements of these two types have been developed. Although hybrid navigation methods are more costly as they need to do more calculations, provided that the cost can be kept at a reasonable degree they can produce much more successful results than local and global methods.
Performance of navigation methods is dependent on the agents in simulation to reach their destinations by making the least effort possible. For this purpose, congestions that are caused by agents who try to move in different directions should be minimalized and the crowd should move in a flow. To achieve this goal global path plans of agents should to be made by considering not only the static obstacles in the simulation environment but also other agents' instantaneous positions and their future plans.
Within this thesis study two new navigation methods have been proposed in which the global navigation information is extracted and stored on simulation environment in a way to include their movement direction and then used by other agents in global path planning phase.
In the Global Path Planning Using Potential Information Method, which is the first one of these methods, global navigation information is represented by potential values. Certain heuristic decisions are made while global path plans are being transformed to potential information and while this information is being used in global path planning. Global path plans that have been made are used in combination with a local navigation method. Comparative tests with a system that uses only a local navigation method have shown that utilizing global navigation information as a guide in local navigation method improves navigation performance remarkably. Besides, this method considerably reduces operation cost of the local navigation method as it minimalizes number of possible collisions by creating a flow in simulation environment.
Second method that is developed is the Time Based Global Path Planning Method. Since global path plans are made on time basis in this method, both extraction of global navigation information of the crowd and usage of this information are carried out in a much more deterministic way in comparison to the potential based method. Machine learning methods are utilized to be able to make global path plans on time basis.
Learning data to be used in machine learning methods is collected from a micro simulation environment and then the models that are trained by using whole of this data are tested on simulation scenarios in medium and macro scale. Therefore a new application schema that differs from traditional machine learning approach about the way learning based methods are used in global path planning is also proposed within this thesis study.
Performance of the time based method is evaluated by comparative tests with the potential based method. Results show that time based method is a better navigation system although it requires slightly more processing power.