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ı.