İTÜDERGİSİ/d, Cilt 7, Sayı 5 (2008)

Yazı Büyüklüğü:  Küçük  Orta  Büyük

Gerçek zamanlı çoklu-robot çoklu-hedef problemi için artımlı atama yöntemi

Sanem SARIEL, Nadia ERDOĞAN, Tucker BALCH

Özet


Bu çalışmada, Çoklu-Robot Çoklu-Hedef Ataması problemi için bir gerçek zamanlı görev seçme ve atama yöntemi önerilmektedir. Çoklu-Robot Çoklu-Hedef Ataması problemi, literatürde iyi bilinen ve tüm veri kümeleri için en iyi çözümlerin polinomsal algoritmalarla bulunamadığı MTSP (Multiple Traveling Salesman Problem) probleminin her bir hedefin en az bir robot tarafından ziyaret edilmesini gerektiren değişik bir uyarlamasıdır. Bu problem için farklı eniyileme amaç fonksiyonları tanımlanabilir (Örn. yürütme zamanını iyileme, robotların toplam yollarını iyileme, vb.). Bu makalede, bu problemin gerçek dünya versiyonu ele alınıp, yürütme zamanında ortaya çıkabilecek problemler irdelenmiştir. Çoklu-robot sistemlerinin ortaklaşa çalışmalarında karşılaşılan en büyük güçlükler, görevlerin yürütme zamanının önceden kesin olarak tahmin edilememesi, yürütme süresince değişebilen maliyet değerleri ile belirsizlik ve tutarsızlıklardan kaynaklanır. Bu çalışmada, yürütme zamanı kısıtlamalarını da aşmak üzere etkin bir dinamik görev seçim ve atama yöntemi önerilmekte ve önerilen yöntemin, hem benzetim ortamlarında hem de gerçek robotlar üzerinde yapılan testlerle başarım analizi yapılmaktadır. Önerilen yöntem, yürütme zamanında oluşabilecek birçok hataya karşı dayanıklı olarak sistemin güncel durumuna göre artımlı ve dağıtılmış bir görev ataması gerçekler. Gerçek zamanlı yürütmeye uygun şekilde iletişim gereksinimleri minimumda tutulmaya çalışılmıştır. Gerçeklenen testler yöntemin bilgi-işlemsel açıdan etkin ve düşük maliyetli, sistemin hatalara karşı dayanıklı olmasını sağlayacak şekilde çalıştığını gösterir niteliktedir.

 

Anahtar Kelimeler: Çoklu-robot sistemleri, gerçek zamanlı çoklu-robot çoklu-hedef atama, artımlı görev seçimi, dinamik görev atama, hataya dayanıklılık.


Tam Metin: PDF