Hammersley Sampling

Rastgele çalışmasını istediğimiz ama o kadar rastgele çalışmasını istemediğimiz bazı algoritmalar oluyor :) . Uniform oluşturduğumuz rastgele sayılar bazen işimizi görmüyor, bazen de zaten önceden elimizde olan kısıtlarla olasılık uzayını daraltmak istiyoruz. Bu gibi durumlarda quasi-random denilen, pseudo-random'ın da daha az rastgelesi sayıları kullanıyoruz.

Hammersley Sampling böyle sayıları üretebildiğimiz bir yöntem. Başlangıçta \(d\) boyutlu uzayda noktalar üretebilmek için \(d-1\) asal sayıya ihtiyaç var. Üreteceğimiz nokta sayısını da önceden bilmek lazım. \(i.\) noktanın 1. boyutu için üreteceğimiz sayı \(\frac{i}{n}\) oluyor. \(k. (k > 1)\) boyut için de şu yöntemi kullanıyoruz;

\(i\) sayısını, \(p_k\) sayı tabanında \(a_1a_2a_3...a_n\) şeklinde gösterdiğimizi düşünelim. Üreteceğimiz sayı

\[\Phi(i) = \frac{a_n}{p_k} + \frac{a_{n-1}}{{p_k}^2}+\frac{a_{n-2}}{{p_k}^3}..\]

ve ürettiğimiz nokta da

\[r(i) = (\frac{i}{N}, \Phi_1(i), \Phi_2(i)...)\]

olacak.

Yani örnek vermek gerekirse, elimizdeki asal sayılar \(p = (2, 3)\) olsun ve  \(N=10\) sayıdan \(i=5.\) sayıyı üretiyor olalım. Buradan

\[r_1(5) = \frac{5}{10} = \frac{1}{2}\]

olacak. 2 tabanında \(5 = 101\) olduğuna göre

\[r_2(5) = \frac{1}{8} + \frac{1}{2} = \frac{5}{8} \]

olacak. Son olarak, 3 tabanında \(5 = 12\) olduğuna göre

\[r_3(5) = \frac{1}{9} + \frac{2}{3} = \frac{7}{9}\]

olacak. Bu yöntemle 3 boyutlu uzayda \(r(5) = (\frac{1}{2},\frac{5}{8},\frac{7}{9})\) örneğini ürettik.

hammersley

p = (2) asal sayı kümesi ile üretilmiş Hammersley sayıları.

Bu yöntem ile RRT ya da PRM gibi algoritmaları çalıştıracaksak artık rastgele noktaları sadece Hammersley noktalarından seçeceğiz. Her şeyi süper hale getiren bir yöntem değil tabii ama makalelerden gördüğüm kadarıyla, özellikle engellerden kaçtığımız haritalar için baya kullanışlı.

 

Voronoi Diyagramları ve Python

Voronoi Diyagramları kullanım alanı çok geniş olabilecek bir konu. Wikipedia'da sanatsal işlerde kullanıldığı bile yazıyor. Benim şimdiye kadar tek kullandığım ve gayet işime yarayan kullanımı ise olasılık dağılımlarının gösterimi.

Belirli bir olasılık dağılımından rastgele nokta üreterek çalışan yöntemlerde (sample based) her dağılım kullanışlı olmayabiliyor. Robot hareketinde rastgele olarak yolu bulmaya çalışırken bu rastgeleliğin yarı-rastgele (quasi-random) olmasını sağlamaya çalışıyoruz. Hareket için uniform dağılım kullanacak olursak Voronoi diyagramı aşağıdaki gibi oluyor;

uniform_voronoi

Bu grafik bize 2 şeyi gösterebilir; birincisi sol alttaki gibi sıkışık alanlar oluşabilir, örnek sayımız sınırlı olduğunda buralarda takılıp kalabiliriz. İkincisi ise üst taraflardaki gibi büyük Voronoi hücreleri oluşabilir. Hücre ne kadar büyükse o noktaya yakın bir başka nokta da o kadar uzak demek, dolayısıyla nokta ulaşılabilir olmayabilir.

Üstteki grafiği de Python'da çizdirdim. Scipy + matplotlib ile uniform dağılımın Voronoi diyagramını oluşturmak için çok fazla kod yazmaya gerek kalmadı;

OptimizationTestSuite

Optimizasyon problemlerinde kullanılan algoritmaların (genetik algoritmalar, hill climbing, particle swarm optimization vs) test edilmesinde kullanılan bazı örnek fonksiyonlar var. Bunlar

\[f(x) = \sum\limits_{i=1}^{n} {x_i}^{2}\]

gibi basit bir fonksiyondan

\[f(x_1, x_2) = -\frac{1+cos(12\sqrt{{x_1}^2 + {x_2}^2})}{\frac{1}{2}({x_1}^2 + {x_2}^2) + 2}\]

fonksiyonu gibi kıl bir fonksiyona kadar çeşitli zorluklarda değişebiliyor (Bu fonksiyonların bahsedildiği makale buradan okunabilir).

Makaledeki 20 kadar fonksiyonun çeşitli algoritmalarla test edilmesini basitleştirmek için OptimizationTestSuite diye bir proje oluşturdum. Başlangıç olarak da içine Hill Climbing algoritmasını ve De Jong fonksiyonunu (ilk fonksiyon) koydum. Diğer problemleri ve algoritmaları eklemeye devam edeceğim.

Bu arada 2. fonksiyona kıl dememin sebebi, fonksiyonun \([-5.12, 5.12]\) aralığında çizilmiş aşağıdaki grafiğinden anlaşılabilir :) :

drop_wave

 

WA* - Yeni Harita

Bir önceki WA* denemesini uniform oluşturulmuş bir harita üzerinde yapmıştım. Yaşar Safkan haritamın tipini beğenmeyince oturdum haritaya elle 1-2 engel koydum :) . Ne kadar karmaşık oldu bilmiyorum ama harita ve A*'ın haritada bulduğu yol aşağıdaki gibi oldu;

A* algoritması. Yol uzunluğu = 33.89, node sayısı = 246.

A* algoritması. Yol uzunluğu = 33.89, node sayısı = 246.

\(W = 8\) verilmiş WA* ise aşağıdaki gibi çalıştı;

WA* (W = 8) algoritması. Uzunluk 36.87, node sayısı = 34.

WA* (W = 8) algoritması. Uzunluk 36.87, node sayısı = 34.

Son olarak \(W = 2\) WA* ise aşağıdaki gibi sonuç verdi.

WA* (W = 2) algoritması. Yol uzunluğu = 34.04, node sayısı = 39.

WA* (W = 2) algoritması. Yol uzunluğu = 34.04, node sayısı = 39.

Yine çok büyük fark çıkmadı ama en azından WA*'ı en kısa yoldan saptırabildim.

WA*

WA*, Planning as heuristic search makalesinde denk geldiğim, orada da referans olarak Heuristics kitabının verildiği bir A* optimizasyonu. Linkteki makalede ve diğer bir çok kaynakta heuristic inflation yöntemi olarak da geçiyor.

A* en iyi sonucu bulan fakat performans konusunda sıkıntısı olan bir algoritma. En iyi sonucu bulmanın çok da önemli olmadığı gerçek hayat problemleri için ise WA* önerilmiş. WA*'ın adındaki W, klasik

\[f(x) = g(x) + h(x)\]

denkleminin

\[f(x) = g(x) + W \times h(x), W \ge 1\]

haline getirilmesinden geliyor. Makalede de belirtildiği üzere, \(W\) arttıkça sonuca daha çabuk ulaşıyoruz fakat bulduğumuz çözüm en iyi çözümden uzaklaşıyor. Bir ilginç nokta ise, \(W\) ile bulacağımız yeni yolun uzunluğu, en iyi yolun uzunluğunun en fazla \(W\) katı oluyor.

30 senelik makalede yanlış olacak değil tabii ki ama ben yine de, en azından sonuçları görebilmek için \(100 \times 100\)'lük uniform bir haritada denemeler yaptım. Örnek harita üzerinde A*'ın bulduğu sonuç aşağıdaki gibi;

a_star

100 x 100'lük haritada A*'ın verdiği sonuç. Uzunluk = 145.279, işlenen düğüm sayısı = 1918.

\(W=4\) verilmiş WA* ise aşağıdaki gibi bir sonuç bulacak.

a_star_hinf_4

100 x 100'lük haritada WA*'ın (W=4) verdiği sonuç. Uzunluk = 147.622, işlenen düğüm sayısı = 113.

Örnek haritada bulunan yol uzunlukları çok değişmese de işlenen düğüm sayısı çok azaldı.

Bu algoritma, özellikle tutarlı heuristic fonksiyonları ile kullanıldığında yol uzunluğunu \(W\) ile sınırlaması özelliği ile ömürboyu planlama algoritmaları ve anytime algoritmalarda epey kullanılıyor.