Kontrol Mühendisliği Temel Bilgileri: Yol Planlaması — A*, Dijkstra, RRT, RRT* ve PRM

Contents — find the section you need

Bir robotu başlangıç noktasından hedefe taşımak nadiren düz bir çizgi çizmek anlamına gelir. Kullanılabilir bir plan, duvarları, geçiş genişliğini, robotun kapladığı alanı, dönüş sınırlarını, konum belirsizliğini, güncel olmayan haritaları, hareket eden insanları ve durma mesafesini hesaba katmalıdır. Yol planlaması nereye gidileceğini seçer; yörünge oluşturma ve kontrol, dinamikler altında bu rotayı nasıl takip edeceğine karar verir. Güvenli bir yığın, bu sorumlulukları birbirinden ayrı tutarken sınırlarını da paylaşır.

Bu giriş, ızgara Dijkstra ve A algoritmalarını sürekli uzaylı RRT, RRT ve PRM algoritmalarıyla karşılaştırır. Engel şişirmesi, sezgisel yöntemler, örnekleme, karmaşıklık, SLAM/Nav2 entegrasyonu, uygulama kontrolleri ve bağımsız güvenlik davranışını açıklar. Bitişik katmanlar için Görsel SLAM Girişi, ROS 2 Girişi ve Sensör Füzyonu Girişi'ne bakın.

Pratik Sonuç

Dijkstra algoritması, pozitif ağırlıklı grafiklerde en kısa yolu garanti eder ancak hedefle ilgisi olmayan yönlerde genişler. A* algoritması, aynı optimumluğu korurken kabul edilebilir bir sezgisel yöntemle genişlemeyi yönlendirir.
RRT algoritması, yüksek boyutlu sürekli uzaylarda hızlı bir şekilde uygulanabilir bir yol bulma eğilimindedir. RRT*, örnekler arttıkça, komşu ve yeniden bağlantı maliyeti eklenerek optimum bir yola yaklaşır. PRM algoritması, yeterince statik bir uzayda birçok sorgu üzerinden yol haritası oluşturmayı amortize eder.
Şişirilmemiş bir harita üzerinden en kısa yol, yarıçapı, yerelleştirme hatası ve durma mesafesi olan bir robot için çarpışma yoludur.
Geri dönen bir rota, güvenliğin kanıtı değildir. Harita güncelliği, yerel algılama, izleme hatası, dinamik engeller, yeniden planlama gecikmesi ve acil durdurma bağımsız olarak ele alınmalıdır.

Algoritma seçmeden önce serbest alanı tanımlayın

Durum uzayını $\mathcal X$ , engel uzayını $\mathcal X_{obs}$ ve serbest alanı $\mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs}$ olarak tanımlayalım. Bir yol $\sigma:[0,1]\to\mathcal X_{free}$ , $x_s$ 'ü $x_g$ 'e $\sigma(0)=x_s,\sigma(1)=x_g$ ile bağlar. 2 boyutlu bir nokta robotu $x=(x,y)$ kullanır; bir araç yön $\theta$ , hız ve direksiyon ekler; bir manipülatör tüm eklem açılarını içerir. Durumu basitleştirmek arama maliyetini azaltır, ancak aşağı akıştaki aracın gerçekleştiremeyeceği eğriler üretebilir.

Engel şişirme, engelleri genişleterek sonlu bir robotu nokta aramasına dönüştürür. Burada $r_{loc}$ , belirtilmemiş bir ortalama hata yerine, tanımlanmış bir güven seviyesi için seçilen bir yarıçap gibi, belirtilen bir belirsizlik terimi olmalıdır. Kavramsal minimum değer şöyledir:

r_{inflate}=r_{robot}+r_{loc}+r_{safe}

burada $r_{robot}$ gövde yarıçapını, konum belirsizliğini önceki terim temsil eder ve $r_{safe}$ izleme/durdurma marjını ifade eder. Gerçekte, marj harita çözünürlüğüne, sensör kör noktalarına, yaklaşan nesnenin hızına ve frenleme kabiliyetine göre değişir. Çok az marj çarpışmaya neden olur; çok fazla marj ise geçiş yollarını imkansız hale getirir.

Diyagram: Duskcoil, ölçülmekten ziyade kavramsal. Hücre boyutu ve şişirme, gerçek bir robot ayak izinden, belirsizlikten ve çalışma aralığından türetilmelidir.

Izgara arama: Dijkstra ve A*

Negatif olmayan kenar maliyetine sahip $G=(V,E)$ grafiği için $c(u,v)\ge0$ , Dijkstra, bilinen en düşük başlangıç maliyetine sahip yerleşmemiş düğümü tekrar tekrar yerleştirir $g(n)$ ve komşularını gevşetir. Yerleştirildikten sonra, $g$ değeri en kısadır. İkili bir yığınla, temsili bir karmaşıklık $O((|V|+|E|)\log|V|)$ 'dir. En kısa grafik mesafesini garanti eder, ancak hedef bilgisi olmadan, geniş bir şekilde yayılma eğilimindedir.

A*, düğümleri şu şekilde sıralar:

f(n)=g(n)+h(n)

burada $h(n)$ , kalan maliyetin alt sınırıdır. Kabul edilebilir bir sezgisel, gerçek kalan maliyeti asla abartmaz; bu durumda A* optimal kalır. Manhattan mesafesi 4 bağlantılı ızgaralara uygundur, Öklid veya Chebyshev ile ilgili mesafe ise 8 bağlantılı harekete uygun olabilir. Tutarlı bir sezgisel ayrıca $h(n)\le c(n,n')+h(n')$ 'i karşılar ve yeniden genişlemeyi azaltır.

Ağırlıklı A*, sezgiseli ölçeklendirir $w>1$ tarafından, optimumluk pahasına daha hızlı bir şekilde uygulanabilir bir rota aramak için kullanılır. Bu, açıkça belirtilirse sağlam bir operasyonel takas olabilir. Kenar maliyeti sadece uzunluğu değil, şişirilmiş engel riskini, açıklığı, dönüşü, enerjiyi veya araziyi de kodlayabilir. Çıktı daha sonra minimum tanımlanmış maliyettir, mutlaka minimum geometrik uzunluk değildir.

Sürekli ve yüksek boyutlu uzaylar: RRT, RRT*, PRM

İnce ızgaralar, altı eklemli bir kol konfigürasyon uzayında veya araç pozisyon uzayında patlar. RRT, serbest uzaydan $x_{rand}$ örnekleri alır, en yakın ağaç düğümünü $x_{near}$ bulur, ona doğru sınırlı bir mesafe yönlendirir, çarpışma kontrolleri yapar ve $x_{new}$ ekler. Olasılıksal olarak tamamlanmıştır: yeterli örneklemle, uygulanabilir bir rota bulma olasılığı, bir rota mevcut olduğunda bire yaklaşır. Kısa bir ilk rotayı garanti etmez.

RRT*, yakındaki köşeler arasında en düşük maliyetli ebeveyni seçer ve komşuları yeni bir düğüm aracılığıyla yeniden bağlar. Daha ucuz olduğunda köşeyi seçin. Asimptotik olarak en uygunudur, sonlu zaman en uygunu değildir; komşu arama, çarpışma testleri ve yeniden bağlantı kurma işlemleri hesaplama gücü tüketir. Kaliteyi "en uygun" sözü vermek yerine, operasyonel son teslim tarihinde ölçün.

PRM, serbest konfigürasyonları örnekler ve yakındaki çarpışmasız çiftleri yeniden kullanılabilir bir yol haritasına bağlar. Ön işlemenin amortize edilebilmesi nedeniyle statik bir fabrika veya tekrarlanan kol sorgusu ortamında caziptir. Dinamik engeller kenarları geçersiz kılar. Dar geçitler, tekdüze örnekleme için zordur, bu nedenle engel sınırına, yola yönelik veya göreve dayalı örneklemeler gerekebilir.

Diyagram: Duskcoil, basitleştirilmiş. Örnekleme, çarpışma kontrolü ve bağlantı, performans ölçümü veya nihai üretim yolu değildir.

Yöntem	Alan / temsili maliyet	Sonuç özelliği	Uygunluk	Ana hata modu
Dijkstra	grafik, $O((V+E)\log V)$	en kısa negatif olmayan maliyetli yol	sezgisel yok, tam maliyet alanı	hedeften uzaklaşarak genişler
A*	grafik; en kötü durum karşılaştırılabilir	kabul edilebilir $h$ ile en kısa yol	tek ızgara sorgusu	$h$ 'u aşırı tahmin etme, düşük maliyetler
RRT	sürekli; örneklemeye bağlı	olasılıksal olarak tamamlanmış	hızlı uygulanabilir yüksek D rotası	dar geçitler, kaba çarpışma kontrolleri
RRT*	sürekli; yeniden kablolama ek yükü	asimptotik olarak optimal	zaman varken iyileştirme	son tarih/çalışma süresi
PRM	ön işleme artı sorgu	Örnekleme koşullarıyla olasılıksal olarak tamamlanmış	statik tekrarlanan sorgular	dinamik uzayda eski kenarlar

SLAM, Nav2 ve yerel planlama

SLAM bir harita ve pozisyon tahmini sağlar, ancak bir planlayıcının zaman damgasıyla hizalanmış dönüşümlere ve net bir doluluk/maliyet anlamına ihtiyacı vardır. Döngü kapanması veya yeniden konumlandırma, harita çerçevesindeki pozisyonu değiştirebilir; eski bir rotayı takip etmeye devam etmek güvenli olmayabilir. Belirsizlik, konumlandırma sıfırlama ve harita güncelleme olaylarını yeniden planlama kurallarına besleyin; bkz. Görsel SLAM Temel Bilgileri.

Nav2 benzeri bir ROS 2 mimarisinde, küresel bir maliyet haritası ve planlayıcı büyük ölçekli bir rota seçerken, yerel bir maliyet haritası ve denetleyici yakındaki engelleri ve hızı ele alır. Küresel bir A* bir koridor seçebilir; yerel katman bir kişinin etrafından geçmek, durmak veya dolanmak zorundadır. Tamamen yerel bir katman çıkmaz sokağa sıkışabilir. Planlayıcıyı, kontrolörünü, kurtarmayı, harita güncelleme hızlarını, son teslim tarihlerini ve öncelikleri açıkça tanımlayın. ROS 2 Primer'de açıklanan ROS 2 taşıma mekanizması gerçek zamanlı veya güvenlik garantisi sağlamaz.

Dağıtımdan önce, yük, sensör görüş alanı, maksimum hız/yavaşlama, yerelleştirme hatası ve harita çözünürlüğü dahil olmak üzere ayak izini ölçün. Dar geçitlerde gerçek açıklığı test edin. Planlanan yolları sürekli hareket ve kinematiklere karşı çarpışma kontrolünden geçirin: bir ızgara rotası, diferansiyel tahrik, araba veya kolun yapamayacağı şekillerde hücreler arasında dönebilir.

Dinamik engeller için, algılama tazeliğini, göreceli hızı, fren mesafesini ve yeniden planlama süresini ölçün; bir planlayıcı geciktiği için asla hareket etmeye devam etmeyin. Bilinmeyen kişileri, delikleri, şeffaf engelleri ve sensör arızasını otomatik olarak hücreleri serbest bırakmak yerine güvenlik durumları olarak ele alın. Rota yoksa, yerel yol güvenli değilse, kovaryans çok büyükse, harita güncel değilse veya izleme hatası zarfını aşıyorsa yavaşlayın, durun veya devredin. Acil durdurma, planlayıcı çıktısından bağımsız olarak çalışmalıdır.

Uygulama Kontrol Listesi ve Güvenlik

Durum uzayını, ayak izini, çerçeveleri, harita çözünürlüğünü ve bilinmeyen hücrelerin anlamını tanımlayın.
Şişirme işlemine yerelleştirme hatası, hız ve durma mesafesini dahil edin; gerçek dar geçitleri test edin.
Sezgisel kabul edilebilirliği doğrulayın veya kasıtlı olarak gevşetilen garantiyi belgeleyin.
Örnekleme planlayıcıları için çarpışma kontrolü çözünürlüğünü, rastgele tohumu, son tarihi ve çözümsüz davranışı kaydedin.
Yeniden yerelleştirme, harita değişiklikleri, sensör kaybı, dinamik engeller ve iletişim gecikmesini ekleyin.
Rota yok, eski harita ve izleme sapması olayları için güvenli bir durma ve teşhis edilebilir bir kayıt yolu doğrulayın.

Referanslar

Anlayışınızı Kontrol Edin

Bir araç herhangi bir engelsiz çizgiyi takip edebilir mi?

Araç ayak izi ve dönüş kısıtlamaları önemlidir. Bir nokta için bir yol, araç için mutlaka uygulanabilir değildir.

Try it in the browser

Lab Change the conditions in a browser experimentNav2'nin bir yolu var ancak hareket etmiyor: bir teşhis iş akışı

Kontrol Mühendisliği Temel Bilgileri: Yol Planlaması — A, Dijkstra, RRT, RRT ve PRM