Dağıtık Problem Çözme
Dağıtık problem çözme, her birinin bilginin veya sorumluluğun bir kısmına sahip olduğu, kısmi sonuçlarını küresel bir çözüme dönüştürmek için iletişim kuran ve birleştiren birden çok ajan tarafından bir problemin nasıl çözülebileceğini inceler.
Tanım
Dağıtık problem çözme, her birinin yerel bilgiye veya alt problemlere sahip olduğu ve tutarlı bir genel çözüm üretmek için iletişim yoluyla koordine olduğu bir grup ajan tarafından bir problemin işbirlikçi çözümüdür.
Kapsam
Bu konu, merkezi bir denetleyiciyi paylaşmayan ajanlar arasındaki işbirlikçi problem çözmeyi; görev ve sonuç paylaşımını; eşzamansız geri izleme (asynchronous backtracking) gibi algoritmalarla dağıtık kısıt tatmini ve optimizasyonunu (DCSP/DCOP); ve iletişim ve gizlilik kısıtlamaları altında kısmi çözümlerin koordinasyonunu kapsamaktadır. Ayrıştırma, yerel hesaplama ve mesajlaşmanın küresel olarak tutarlı çözümler üretme biçimi ele alınmaktadır. Tamamen rekabetçi etkileşim ve teşvik tasarımı ise oyun teorisi ve mekanizma tasarımı kapsamında incelenmektedir.
Temel sorular
- Bir problem, kısmi görüşlere sahip ajanlar arasında nasıl ayrıştırılır ve dağıtılır?
- Ajanlar, küresel bir çözüm oluşturmak için görevleri ve ara sonuçları nasıl paylaşır?
- Değişkenler ve kısıtlamalar ajanlar arasında dağıldığında bir kısıt problemi nasıl çözülür?
- İletişim maliyeti ve yerel özerklik, çözüm kalitesine karşı nasıl dengelenir?
Anahtar kavramlar
- problem ayrıştırma
- görev paylaşımı ve sonuç paylaşımı
- dağıtık kısıt tatmini (DCSP)
- dağıtık kısıt optimizasyonu (DCOP)
- eşzamansız geri izleme (asynchronous backtracking)
- mesajlaşma
- yerel özerklik ve gizlilik
- küresel tutarlılık
Temel kuramlar
- Dağıtık kısıt tatmini ve optimizasyonu
- Dağıtık kısıt tatmini (DCSP) ve optimizasyonu (DCOP), kısıt problemlerini, değişkenlerin ve kısıtlamaların farklı ajanlar tarafından tutulduğu ortamlara genelleştirmektedir. Bu problemler, ajanların eşzamansız olarak değer atamalarını ve çakışma bilgilerini değiştirdiği algoritmalarla çözülmektedir.
- Görev paylaşımı ve sonuç paylaşımı
- İşbirlikçi dağıtık problem çözme, görevleri ayrıştırarak ve dağıtarak, ayrıca ajanların entegre ettiği kısmi sonuçları değiş tokuş ederek ilerlemektedir. Bu yaklaşım, bir grubun tek bir ajanın tek başına çözemeyeceği problemleri çözmesine olanak sağlamaktadır.
- Eşzamansız dağıtık arama
- Eşzamansız geri izleme (asynchronous backtracking) gibi algoritmalar, ajanların merkezi kontrol olmaksızın tutarlı bir küresel atama aramasına olanak tanımaktadır. Bu algoritmalar, yerel özerkliği korurken çakışmaları çözmek için öncelikli mesajlaşmayı kullanmaktadır.
Klinik önem
Dağıtık problem çözme, çoklu sensörlü gözetim ve takip, dağıtık zamanlama ve toplantı koordinasyonu, elektrik şebekesi ve trafik yönetimi gibi alanlara ve veri veya sorumluluğun doğal olarak ajanlar arasında dağıldığı, iletişim kısıtlamaları altında tutarlı bir çözüm bulması gereken her türlü ortama uygulanmaktadır.
Tarihçe
İşbirlikçi dağıtık problem çözme, dağıtık yapay zekanın kurucu temalarından biri olmuş ve 1980'lerde dağıtık sensör ağları ve kara tahta sistemleri üzerine yapılan çalışmalarla örneklendirilmiştir. Yokoo ve meslektaşları, 1990'larda dağıtık kısıt tatminini (distributed constraint satisfaction) formüle etmiş, dağıtık kısıt optimizasyonu (distributed constraint optimization) ise daha sonra işbirlikçi çoklu ajan karar verme için önemli bir çerçeve haline gelmiştir.
Öne çıkan isimler
- Edmund H. Durfee
- Victor R. Lesser
- Makoto Yokoo
- Daniel D. Corkill
İlgili konular
Temel eserler
- yokoo1998
- durfee1989
Sıkça sorulan sorular
- Dağıtık problem çözme, paralel hesaplamadan nasıl farklıdır?
- Paralel hesaplama genellikle bir problemi merkezi kontrol altında işlemciler arasında bölerek daha hızlı çalışmayı hedefler. Dağıtık problem çözme ise kendi yerel bilgisine ve muhtemelen gizlilik veya iletişim kısıtlamalarına sahip özerk ajanları varsaymaktadır; bu nedenle asıl zorluk sadece hız değil, koordinasyon ve tutarlı bir çözüme ulaşmaktır.
- Dağıtık kısıt optimizasyon problemi nedir?
- Değişkenlerin ve kısıtlamaların farklı ajanlara ait olduğu bir kısıt problemidir. Bu problemde ajanlar, sadece yerel olarak iletişim kurarak küresel bir amacı (toplam maliyeti minimize etmek gibi) optimize etmek için işbirlikçi bir şekilde değerler atamalıdır. Ajanlar arasındaki birçok işbirlikçi koordinasyon görevini modellemektedir.