Olasılıksal Yol Haritası
Probabilistic Roadmap · Ayrıca şöyle bilinir: PRM, Roadmap Method
Olasılıksal Yol Haritası (PRM) yöntemi, rastgele konfigürasyonlar örnekleyerek ve çarpışmasız ise bunları birbirine bağlayarak yapılandırılmış uzayda geçerli yolların önceden hesaplanmış bir grafiğini (yol haritası) oluşturan bir hareket planlama algoritmasıdır. Kavraki ve arkadaşları tarafından 1996 yılında tanıtılan PRM, yol haritası oluşturma maliyetini birçok sorgu üzerinden amorti ederek çoklu sorgu planlama senaryolarında güçlüdür.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Aynı ortamda birçok hareket planlama sorgusunu (100'ler-1000'ler) yanıtlamanız gerektiğinde PRM kullanın; yol haritası oluşturma maliyetini amorti eder. Tekrarlanan sorgularla depo otomasyonu veya CAD sistemleri gibi senaryolar için idealdir. Tek bir hızlı sorgu gerekiyorsa (RRT daha hızlıdır) veya ortam sık sık değişiyorsa (yol haritası geçersiz hale gelir) PRM'den kaçının.
Güçlü yönler & sınırlılıklar
- Çoklu sorgu senaryoları için uygundur; yol haritası yeniden kullanımı oluşturma maliyetini amorti eder.
- Karmaşık engellere sahip yüksek boyutlu uzaylarda iyi çalışır.
- Yeterli örnekle asimptotik olarak optimaldir.
- Basit temel mekanikler (örnekleme, en yakın komşular, grafik arama).
- Kinodinamik planlama ve non-holonomik kısıtlamalara genişletilebilir.
- Yüksek başlangıç hesaplama maliyeti; ilk sorgudan önce yol haritası oluşturma süresi.
- Bellek kullanımı yol haritası boyutuna göre artar (karmaşık görevler için 1000'ler-100.000'ler düğüm).
- Yüksek boyutlarda en yakın komşu sorguları yavaş olabilir.
- Dar geçitleri kaçırabilir; dikkatli parametre ayarı gerektirir.
- Ortam değişirse yol haritası yeniden oluşturulmalıdır.
SSS
PRM'yi hangi parametreler kontrol eder: örnek sayısı N ve komşuluk yarıçapı k?
N grafik yoğunluğunu kontrol eder; daha fazla örnek kapsama alanını iyileştirir ancak maliyeti artırır. N = 1000 ile başlayın ve yol haritası kalitesi iyileşene kadar ikiye katlayın. k (en yakın komşular) kenar yoğunluğunu kontrol eder; tipik değerler k = 10-30. Daha büyük k bağlantıyı artırır ancak hesaplama maliyetini O(N log N) artırır. Uyarlanabilir örnekleme, az keşfedilmiş bölgelerde daha fazla örnek ekler.
PRM yol haritamın bağlantısının kesildiğini nasıl tespit edebilirim?
Yol haritasını oluşturduktan sonra bağlantıyı kontrol edin: her düğümü bir bağlı bileşen kimliği ile etiketleyin (BFS/DFS kullanarak). Başlangıç ve hedef farklı bileşenlerdeyse, yol haritası bağlantısızdır. Bileşen sınırları yakınında daha fazla örnek ekleyin veya boşlukları kapatmak için k'yi artırın.
PRM dar geçitleri nasıl ele alır?
Standart PRM dar geçitlerde başarısız olur; rastgele örnekleme nadiren dar alanların içine konfigürasyonlar bulur. Çözümler: (1) Gauss örneklemesi (engellere yakın örnekleme), (2) deformasyon tabanlı yöntemler (yol haritasını engellere doğru çekme), (3) karma mod örnekleme (rastgele ve çarpışma tabanlı örneklemeyi birleştirme). Bu teknikler zorlu bölgelere örnekleri odaklar.
Mevcut bir yol haritasına artımlı olarak sorgu ekleyebilir miyim?
Evet, bu PRM'nin önemli bir avantajıdır: yol haritası oluşturulduktan sonra, yeni sorgular başlangıç/hedefi grafiğe bağlayarak yanıtlanır. Yeniden oluşturmaya gerek yoktur. Bir sorgu bağlanamazsa, yeni yol haritası örnekleri ekleyebilir (yenile) veya grafik topolojisini uyarlayabilirsiniz.
Kaynaklar
- Kavraki, L. E., Svestka, P., Latombe, J. C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566-580. DOI: 10.1109/70.508439 ↗
- Overmars, M. H., & Svestka, P. (1992). A probabilistic learning approach to motion planning. Proceedings of the Fourth Workshop on Algorithmic Foundations of Robotics, 19-37. link ↗
- LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press. link ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Probabilistic Roadmap. ScholarGate. https://scholargate.app/tr/control-theory/probabilistic-roadmap
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Model Predictive ControlKontrol teorisi↔ karşılaştır
- Hızlı Keşfeden Rastgele AğaçKontrol teorisi↔ karşılaştır