Depoda çoklu AGV işbirliğinin küresel yol planlama algoritması üzerine araştırma
Pratik uygulamalarda, bir depoda birden çok AGV'nin işbirliği vazgeçilmez bir parçadır ve birden çok AGV'nin ortak taşıma sürecinde eş zamanlı yol planlaması, desteklemek için belirli bir algoritma gerektirir.Bu makale, bir depodaki birden çok AGV ile işbirliği yapar. Yol planlaması doğrultusunda algoritma araştırması yapmak, analiz etmek ve ilkesini ve gerçekleştirilmesini tanıtmak.
2. Analiz
Her şeyden önce, geçmişimiz lojistik depoda belirlenir ve AGV'mizin karşılaştığı sahneleri anlamak için depoda ortak olan depo girişi, toplama ve teslimat gibi belirli görev ayrıntılarını analiz ederiz.
Geleneksel yöntem genellikle statik rafları kullanır.Arama girerken, mallar belirlenen raflara taşınır ve raflara manuel olarak yerleştirilir.Ayrılırken, siparişe uygun ürünleri seçmek ve paketlemek için belirlenen raflara manuel olarak giderler.GV'nin tanıtılmasından sonra mod gerçekleşecektir. Değiştirin, depodaki belirlenmiş depolama alanı ve toplama alanını planlayacağız.AGV, siparişleri içeren rafları dinamik olarak toplama alanına taşıyacak, elle veya robotik toplama için sırada bekleyen sipariş toplama sepetine paketlenecek ve toplama işlemini tamamlayacaktır. Ardından rafı belirlenen konuma taşıyın.
Bu nedenle, AGV'nin piyasaya sürülmesinden sonra, karşılaştığımız sorun, verimliliği en üst düzeye çıkarmak, birden fazla AGV ile tıkanıklık ve çarpışmalardan nasıl kaçınılacağı, her AGV için daha iyi bir yürüyüş rotasının nasıl planlanacağı ve her bir AGV'nin en düşük maliyeti nasıl harcamasının sağlanacağıdır. , Daha fazla görevi tamamlamak bu makalenin odak noktası olacaktır.
3. Sorun çözme
Yol planlamada birden fazla robotu optimum hale getirmek için, tek bir araba için bir yol planlarken diğer arabaların sürüş rotasını düşünmekten ve ardından en uygun sürüş planını seçmekten başka bir şey değildir. Ayrıca dış mekan sahnesinden farklı olarak, depodaki troley yolunu planlıyoruz ve tüm yol tasarlanarak sorunumuz aşağıdaki gibi demonte edilebiliyor:
(1) Depodaki yolun tasarımı;
(2) Diğer arabaların yol sürüş durumunu elde edin;
(3) Olası yol tıkanıklığını tanımlayın;
(4) En kısa yolu planlamak;
(5) Trafik kontrolü.
3.1 Depoda yol tasarımı
Bazı yaygın yol tasarımları Şekil 1 ve Şekil 2'de gösterilmektedir. Bunlar, gerçek uygulama senaryolarına göre düzenlenmiştir.Eklenen faktörler arasında ambarın yapısı, mal türleri vb. Yer alır ve en uygun tasarım, gerçek testlere veya simülasyonlara göre seçilir.
Şekil 1: V şeklindeki yol tasarımı
Şekil 2: Tic-Tac şeklindeki yol tasarımı
3.2 Diğer arabaların yol sürüş durumunu öğrenin
Global yol planlamasına ulaşmak için, troley'nin konumu ve çalışma durumu her an elde edilmelidir.Bu nedenle, troley ile stabil bir iletişim sistemi kurulmalıdır.Genellikle, TCP ile bağlantı kurmak ve troleyi sağlamak için uygun bir WIFI kanalı seçmek için kablosuz bir yerel alan ağı kullanılır. Küresel yol planlama sistemi ile sağlam iletişim.
3.3 Olası yol tıkanıklığını tanımlayın
Deponun yol planlaması tamamlandıktan sonra göz önünde bulundurulması gereken ilk etken olası yol tıkanıklığıdır.Genellikle, tramvay depoda düz bir hat üzerinde yürür.Dönmesi gerektiğinde yerinde durmalı ve yerinde 90 ° veya 180 ° döndükten sonra düz bir çizgide yürümeye devam etmelidir. , Yani her dönüşün mevcut yol tıkanıklığına neden olma şansı var. Ayrıca aynı yoldaki trafik hacminin fazla olması yol sıkışıklığına da neden olacaktır.Kavşaklarda araçlarla karşılaşma durumuna ek olarak, yol sıkışıklığı, dönüş, karşılama araçları ve büyük trafik hacmine neden olan üç yaygın olası durum vardır.
3.4 En kısa yolu planlama
En kısa yol planlaması, küresel yol planlamasının özüdür.Haritadaki bir konumdan başka bir konuma gitmek için, ortada engeller vardır ve olası yol tıkanıklığı dikkate alındığında, başlangıç noktasından hedef noktaya olan yolu bulmak için bir yol arama algoritması kullanılmalıdır. Yaygın arama yolu algoritmaları, en geniş ilk algoritma, derinlik ilk algoritması, Dijkstra algoritması, A * algoritması vb. İçerir. Genişlik ilk algoritması ve derinlik ilk algoritması, ağaç yapısının en kısa yolu veya en küçük ağırlık senaryosunu çözmesi için uygundur, Dijkstra algoritması genellikle yapının en kısa yolunu çözmek için kullanılır ve A * algoritması, statik yol ağındaki en kısa yol için en etkili doğrudan arama yöntemidir.
Her algoritmanın kendi uygulama senaryosu vardır.Global yol planlama senaryomuz için haritamızın bir raster haritasına dönüştürülmesi daha kolaydır ve A * algoritmasının, raster haritadaki en kısa yolu aramada bariz avantajları vardır ve değişiklik yapmak uygundur. Yol tıkanıklığı senaryolarımızın değerlendirilmesiyle birlikte, tercih edilen en kısa yol algoritması olarak A * algoritmasını kullanır ve ardından küresel yol planlamasını analiz edip uygularız.
3.5 Trafik kontrolü
Trafik kontrolü ağırlıklı olarak arabaların ve paralel akış senaryolarının karşılanmasında kullanılır.Bir yandan araç çarpışmalarını önlemek için diğer yandan kavşaklarda arabalarla karşılaşmak daha yaygındır.Zayıf kullanım, araç kilitlenmesine ve araçların birbirini beklemesine yol açacak ve bu da görevin tamamlanmasını imkansız hale getirecektir. Planlamanın temel algoritması olan ortak toplantı sahnesi Şekil 3'te gösterilmektedir.
Resim 3: Kavşakta karşılama arabası
4. Çekirdek algoritmanın uygulanması
Yol planlama algoritmasının özü, esas olarak en kısa yol planlaması ve trafik kontrolüdür Burada, en kısa yol planlama algoritması ve trafik kontrol algoritması analiz edilecek ve ardından tam bir küresel yol planlama algoritmaları seti tasarlanacaktır.
En kısa yolu planlamak için 4.1 A * algoritması
A * algoritması, grafik teorisinde en uygun ağacı bulmaya benzer.Genellikle belirli bir yol seçmenin yol maliyetini dikkate alır. Geçilebilecek tüm yollar arasında, her zaman diğer herhangi bir geçilebilir yola kıyasla en düşük maliyetli olan bir yol vardır. . Grafik teorisinde en iyi yolu bulurken, her yolun maliyeti bilinir ve sabittir, ancak en iyi yolu çözmek için A * algoritması kullanıldığında, aynı düğümün maliyeti farklı olsa da, farklı yolları izler. Evet, sezgisel yol bulmanın özü budur.
Bu yöntemi kullanırken, asıl problem önce soyutlanır ve problemdeki her bir öğe, başlangıç noktası, hedef nokta ve ortaya çıkan engeller dahil olmak üzere bir matris şeklinde temsil edilir. Yol bulma açısından, asıl sorunun soyut olarak bir matris ile temsil edildiğini ve ardından yol bulma sürecinin matrisin çalışmasını simüle ederek gerçekleştirildiğini yavaş yavaş bulacağız.
Temel fikir, başlangıç noktasının merkez olduğu, hemen etrafındaki 8 noktanın işaretçi tarafından ona işaret edildiği, çevreleyen noktalarda en iyi yol noktasının seçildiği ve merkez noktası olarak henüz işaretçi teması kurmamış çevreleyen noktalardaki (uygulanabilir) Evet, bu daha sonra açıklanacaktır) İşaretçiyle üzerine gelin ve en iyi yol noktasını seçin ve ardından bu noktayı merkez olarak çevreleyen noktalarda bir hedef nokta olana kadar yolu bulun, böylece aranan yollar işaretçi ile tek tek bağlanır. Son olarak, bu noktaların çıktısını alarak, bulunacak yoldur.
Aşağıdakiler temel olarak A * algoritmasının yol bulma sürecini aşağıdaki yönlerden adım adım analiz eder:
(1) Asıl problemi bir matris gösterimine soyutlayın
Soyutlanmış matris Şekil 4'te gösterilmektedir, burada yeşil alan başlangıç noktasını, kırmızı alan hedef noktayı, ortadaki mavi alan engelleri (geçilmez dağlar veya nehirler gibi) ve siyah alan bir yolun oluşturulabileceği alanı temsil etmektedir.
(2) Merkezde başlangıç noktası olan sonraki düğümü bulun
Şekil 5'te görüldüğü gibi başlangıç noktasına çok yakın olan 8 nokta aradıkları yol üzerindeki sonraki noktalardır ve ortadaki mevcut nokta işaretçi şeklinde komşu noktaların ebeveyn düğümü olarak kullanılır. . Bu 8 nokta için, yol bulma için bir sonraki başlangıç noktası olarak hangi nokta seçilmelidir? A * algoritmasında iki liste oluşturulmuştur, biri açık listedir (mevcut noktanın tüm ulaşılabilir noktalarını saklamak için kullanılır (kapalı liste hariç) Ortadaki nokta, engel noktası)), diğeri kapalı listedir (ulaşılan noktalar burada saklanır ve kapalı listedeki noktalar bir sonraki yol bulma işleminde tekrar kontrol edilmeyecektir ki bu da yol bulmayı gösterir. Çizgiler kesişmeyecek).
(3) Sonraki düğümü seçin
Başlangıç noktasını kapalı listeye ekleyin ve sonraki yol bulma işleminde artık kontrol etmeyin.Bir sonraki adım, bu 8 noktadan birini bir sonraki yol noktası olarak seçmektir.Seçim ilkesi, en düşük yol maliyetine sahip düğümü bulmaktır.
Ağırlığı F, F = G + H ile temsil edilir
G, oluşturulan yol boyunca başlangıç noktasından belirtilen kareye hareket etmenin yol maliyetini temsil ettiğinde; Şekil 6'da gösterildiği gibi, başlangıç noktası merkez olmak üzere diyagonal yönde 8 nokta vardır. Yukarı, aşağı, sola ve sağa hareket etmenin maliyeti 10'dur ve çapraz maliyet 2 * 10'dur, bu da yaklaşık 14'tür.
H, yolun geçerli noktasından bitiş noktasına kadar olan seyahat yolu maliyetini temsil ettiğinde Hesaplama yöntemi, geçerli nokta ile hedef nokta arasındaki yatay ve dikey karelerin sayısının toplamıdır ve ardından sonucu 10 ile çarpmaktadır.
Şekil 7'den görülebileceği gibi, başlangıç noktasının sağ noktasının ağırlığı F en küçüktür, dolayısıyla bir sonraki yol noktası olarak alınır.
(4) Aramaya devam et
Yol noktasını açık listeden silin ve kapalı listeye ekleyin. Bu noktanın yanındaki 8 noktayı kontrol edin (kapalı listedeki noktaları veya geçilemez noktaları göz ardı edin) ve bunları açık listeye ekleyin.Açık listeye eklenmemiş noktalar varsa, ara noktalar bu tür noktaların ana düğümleri olarak alınır. Ve açık listeye ekleyin.
Tüm uygun bitişik noktalar zaten açık listede ise, her bir bitişik nokta için geçerli yol maliyetinin önceki yol noktasından bu bitişik noktaya olan yoldan daha düşük olup olmadığını kontrol edin. Değilse, hiçbir şey yapmayın (şekilde gösterildiği gibi) 8) Yeni oluşturulan yol G değerine göre orijinal başlangıç noktasından hemen altındaki noktaya: G1 = 10 + 10 = 20 ve orijinal yol G değeri G2 = 14, yani yeni oluşturulan yolun G değeri orijinal yoldan daha yüksek G değeri büyüktür ve H değerleri aynıdır (aynı nokta), bu nedenle orijinal yolun F değeri yeni oluşturulan yolun F değerinden daha küçüktür İşlem yapılmaz ve sonraki yol bulmaya devam edilir. Öyleyse, bitişik karenin ana düğümünü, yeni oluşturulan yolun hareket maliyetinin daha düşük olduğunu gösterecek şekilde seçili kareye değiştirin.
(5) Bir önceki arama işlemini sonuna kadar tekrarlayın
Arama süreci iki durumda sona erer: Birincisi, hedef noktanın kapalı listeye eklenmesi, aramanın normal şekilde sona ermesi ve yolun bulunmasıdır. Diğer bir durum ise, hedef noktanın bulunmaması, ancak açık listenin boş olması, yani başlangıç noktasından hedef noktasına kadar olan yolun bulunamaması ve aramanın sona ermesidir.
Arama işlemi Şekil 9'da gösterilmektedir. Başlangıç noktasından hedef noktaya kadar tutarlı bir yol olduğu görülebilir, bu da A * algoritmasının aranan yol olduğu anlamına gelir. Başlangıç noktasından bitiş noktasına giden yolu vurgulamak için yol noktasına kırmızı bir nokta ekleyin.
Tüm yol bulma süreci şu şekilde organize edilir:
1) Başlangıç ızgarası açık listeye eklenir;
2) Aşağıdaki görevleri tekrarlayın:
a) Açık listede en düşük F değerine sahip noktayı bulun. Biz buna mevcut nokta diyoruz;
b) Kapalı listeye ekleyin;
c) Sonraki 8 tablodaki her nokta için
* Fena değilse veya zaten kapalı listede ise, atlayın. Bunun tersi şu şekildedir:
* Açık listede yoksa ekleyin. Geçerli noktayı bu ızgaranın ana düğümü olarak alın. Bu noktada F, G ve H değerlerini kaydedin;
* Zaten açık listede ise, yeni yolun daha iyi olup olmadığını kontrol etmek için G değerini referans olarak kullanın. Daha düşük bir G değeri, daha iyi bir yol anlamına gelir. Eğer öyleyse, bu noktanın ebeveyn düğümünü geçerli noktaya değiştirin ve bu noktanın G ve F değerlerini yeniden hesaplayın. Değişiklikten sonra açık listeyi tekrar F değerine göre sıralamanız gerekir. Değilse, işaretçi noktasını değiştirmeye ve daha sonra G ve F değerlerini yeniden hesaplamaya gerek yoktur;
3) Aramayı bırakın, iki durum vardır:
* Hedef nokta kapalı listeye eklendiğinde, yol bulunur ve arama normal olarak sona erer;
* Hedef nokta bulunamadı, ancak açık liste boş ve şu anda uygun bir yol bulunamıyor, arama sona eriyor;
4) Yolu kaydedin. Hedef noktadan başlayarak, başlangıç noktasına dönene ve yolun çıktısını verene kadar her noktanın işaretçisi boyunca hareket edin.
4.2 Kilitleme Mekanizmasına Dayalı Trafik Kontrolü
Araç yol planlaması tamamlandıktan sonra birden fazla otomobil aynı anda yürümeye başlayacak.Çoklu yollardaki arabaların karşılaşması kaçınılmazdır.Arabalarla buluşurken araçlar çoğunlukla takip edecek, birbirlerine, kavşaklara veya T-kavşaklara gideceklerdir. Çarpışmalardan kaçınmak için sensörler olacaktır. Kavşaklar ve T şeklindeki yollar arasındaki çarpışmaları önlemek için, arabalarla buluşurken ızgara kilitlenecektir, yani:
(1) Her araba bir adım yürür ve öndeki iki adımın noktasını kilitler;
(2) Araç kilitlendiğinde, haritanın kilitlenecek noktasının kilitlendiği tespit edilir, ardından iki araba hangi önceliğin daha yüksek olduğunu, hangisinin önce gittiğini ve diğer arabanın durup beklediğini görmek için anlaşır;
(3) Arabanın kilidi geçtikten sonra açılır ve beklerken, seyahat etmek üzere olduğu noktada yeniden kilitlenebilir ve ileriye doğru yürümeye devam edebilir;
(4) Döngü, her adımda kilitlenmiştir.
4.3 Küresel yol planlaması
Tramvayın mevcut yolunu planlarken, en iyi genel planlama sonucunu karşılamak için yol tıkanıklığını dikkate alarak en kısa yolu planlayın.A * algoritmasını kullanın ve yeni yolun daha iyi olup olmadığını kontrol etmek için G değerini kullanın. Haritadaki diğerini değiştirin. Aracın planladığı yol noktasının G değerini artırarak aynı yolu aramaktan kurtulmaya çalışabilirsiniz.Aynı sebeple aracın dönmesi gerektiğinde bir sonraki noktanın G değeri de artırılarak planlanan yol mümkün olduğunca dönmekten kaçınır. En yüksek genel verimliliği ve en iyi küresel yolu elde ettiğiniz görülüyor.
Ayrıca yol planlaması statik olarak planlanmış bir yol olduğundan, araçların çarpışmamasını sağlamak için her araç için aynı anda trafik kontrolünde araçların kilitlenmesi gerekmektedir.
5. Özet
Bu makale temel olarak depodaki çoklu AGV işbirliğinin küresel yol planlamasını inceler ve olası bir uygulama algoritmasını sunar Depodaki yol tasarımı perspektiflerinden ve tıkanıklık hususlarından, basit küresel yol planlamasının dikkate alınması gerekir. Rota planlama ve trafik kontrol stratejilerinin detaylı analizi ve uygulama tasarımı. (Makale IT Magazine Baijiahao'dan geliyor)
Geçmiş seçimler
Daha heyecan verici makaleler okumak için aşağıdaki anahtar kelimelere tıklayın
