Planlama Grafikleri ve Sezgisel Yöntemler
Planlama grafikleri ve alandan bağımsız sezgisel yöntemler, erişilebilirliği kompakt bir şekilde analiz ederek ve bir durumdan hedefe olan mesafeyi otomatik olarak tahmin ederek klasik planlamayı hızlandıran tekniklerdir.
Tanım
Planlama grafiği, erişilebilirliği yaklaşık olarak belirlemek için önerme ve eylem seviyelerini mutex kısıtlamalarıyla birleştiren katmanlı bir yapıdır; planlama sezgisel yöntemleri ise genellikle bu tür yapılardan veya silme-gevşetilmiş problemlerden hesaplanan, bir durumdan hedefe ulaşma maliyetini tahmin eden fonksiyonlardır.
Kapsam
Bu konu, Graphplan tarafından tanıtılan planlama grafiği veri yapısını; önermelerin ve eylemlerin seviyelerini ve hangi olguların ve eylemlerin birlikte gerçekleşemeyeceğini gösteren karşılıklı dışlama (mutex) ilişkilerini; ve modern sezgisel arama planlayıcılarını yönlendiren gevşetilmiş problemlerden (özellikle silme etkilerini göz ardı ederek) türetilen alandan bağımsız sezgisel yöntemler ailesini kapsamaktadır. Erişilebilirlik bilgisinin nasıl hesaplandığı ve arama sürecini yönlendirmek için nasıl kullanıldığı ele alınmaktadır. Temel klasik planlama modeli ilgili konuda incelenmektedir.
Temel sorular
- Bir planlama grafiği, erişilebilir önermeleri ve eylemleri seviye seviye nasıl temsil eder?
- Mutex ilişkileri nelerdir ve olgular ile eylemler arasındaki uyumsuzluğu nasıl yakalarlar?
- Silme-gevşetme, kabul edilebilir veya bilgilendirici planlama sezgisel yöntemlerini türetmek için nasıl kullanılır?
- Bu sezgisel yöntemler, planlamayı verimli bir sezgisel aramaya nasıl dönüştürür?
Anahtar kavramlar
- planlama grafiği
- önerme ve eylem seviyeleri
- karşılıklı dışlama (mutex)
- Graphplan
- silme-gevşetme
- h-max ve h-add sezgisel yöntemleri
- FF sezgisel yöntemi ve gevşetilmiş planlar
- sezgisel ileri arama
Temel kuramlar
- Planlama grafiği ve Graphplan
- Graphplan, her seviyede hangi önermelerin ve eylemlerin erişilebilir olduğunu ve hangi çiftlerin karşılıklı olarak dışlayıcı olduğunu kompakt bir şekilde kodlayan bir planlama grafiği oluşturur, daha sonra bu yapı üzerinden geriye doğru arama yaparak bir plan çıkarır ve planlamayı önemli ölçüde hızlandırmaktadır.
- Silme-gevşetme sezgisel yöntemleri
- Eylemlerin silme etkilerini göz ardı etmek, çözülmesi çok daha kolay olan gevşetilmiş bir planlama problemi ortaya çıkarır; bu gevşetmeyi çözmenin maliyeti, ileri aramayı yönlendiren bilgilendirici, genellikle kabul edilebilir sezgisel yöntemler (h-max ve h-add ve FF sezgisel yöntemi gibi) sağlamaktadır.
- Sezgisel arama planlaması
- Güncel klasik planlayıcılar, otomatik olarak türetilmiş sezgisel yöntemleri en iyi-ilk veya açgözlü arama ile ve tercih edilen operatörler gibi geliştirmelerle birleştirerek çeşitli alanlarda güçlü genel amaçlı performans elde etmektedir.
Klinik önem
Planlama grafikleri ve silme-gevşetme sezgisel yöntemleri, robotik, lojistik ve otonom kontrol alanlarında kullanılan, yarışma kazanan planlayıcıların temel teknolojisidir. Bu teknolojiler, alandan bağımsız planlayıcıların, el yapımı arama rehberliği olmaksızın büyük problemleri hızla çözmesini sağlamaktadır.
Tarihçe
Blum ve Furst'ün Graphplan'ı (1995, dergi versiyonu 1997) planlama grafiğini tanıtmış ve planlama hızında devrim yaratmıştır. 1990'ların sonları ve 2000'li yıllar, silme-gevşetme sezgisel yöntemlerinin yükselişine tanıklık etmiştir. FF planlayıcısı (Hoffmann ve Nebel, 2001) ve daha sonra Fast Downward (Helmert, 2006) ile sezgisel ileri arama, baskın yaklaşım olarak yerleşmiştir.
Öne çıkan isimler
- Avrim L. Blum
- Merrick L. Furst
- Jörg Hoffmann
- Bernhard Nebel
- Malte Helmert
İlgili konular
Temel eserler
- blum1997
- hoffmann2001
Sıkça sorulan sorular
- Bir planlama grafiğinde mutex nedir?
- Bir mutex (karşılıklı dışlama) ilişkisi, aynı seviyede aynı anda geçerli olamayacak veya uygulanamayacak iki önermeyi veya iki eylemi işaretler; örneğin, bir eylem diğerinin bir önkoşulunu sildiği için. Mutex'ler, planlama grafiğini gerçek erişilebilirliğin daha sıkı bir yaklaşımı haline getirmektedir.
- Silme etkilerini göz ardı etmek neden faydalı bir sezgisel yöntem sağlar?
- Silme etkileri olmaksızın, bir hedefe ulaşmak asla başka bir hedefi geri almaz, bu nedenle gevşetilmiş problem çözülmesi çok daha kolaydır ve orijinalinden asla daha zor değildir. Gevşetilmiş planın maliyeti bu nedenle gerçek maliyetin bir alt sınırı veya bilgilendirilmiş bir tahminidir, bu da onu aramayı yönlendirmek için etkili bir sezgisel yöntem haline getirmektedir.