Klasik Planlama ve STRIPS
Klasik planlama, belirlenimci, tamamen gözlemlenebilir ve statik bir ortamda, eylemlerin ön koşullar ve etkilerle faktörlenmiş STRIPS tarzı gösterimini kullanarak bir hedefe ulaşmak için bir eylem dizisi bulma sorununu ele almaktadır.
Tanım
Klasik planlama, tamamen bilinen bir başlangıç durumunu hedefi karşılayan bir duruma dönüştüren belirlenimci eylemler dizisi aramaktadır; burada her eylem, uygulanması için geçerli olması gereken koşullar ve yaptığı değişiklikler ile tanımlanmaktadır.
Kapsam
Bu konu, klasik planlama modelini ve varsayımlarını (belirlenimci eylemler, tam gözlemlenebilirlik, tek bir ajan, atomik zaman), durumların ve eylemlerin STRIPS ve ADL/PDDL gösterimlerini, ileri (ilerleme) ve geri (gerileme) durum-uzay aramasının ve kısmi sıralı planlamanın temel çözüm yöntemlerini ve önermeli planlamanın hesaplama karmaşıklığını kapsamaktadır. Sezgisel rehberlik ve planlama grafikleri ilgili konuda ele alınmakta olup, belirlenimci olmayan veya olasılıksal varyantlar kapsam dışıdır.
Temel sorular
- Klasik planlama modelini hangi varsayımlar tanımlamaktadır ve bunlar ne zaman uygun olmaktadır?
- STRIPS gösterimi bir durumu önermelere ve bir eylemi ön koşullara ve ekleme/silme etkilerine nasıl faktörlemektedir?
- İlerleme ve gerileme araması, planlama stratejileri olarak nasıl farklılık göstermektedir?
- Klasik planlama genel olarak hesaplama açısından ne kadar zordur?
Anahtar kavramlar
- belirlenimci, tamamen gözlemlenebilir model
- STRIPS ön koşulları ve etkileri
- ekleme ve silme listeleri
- PDDL ve ADL
- ilerleme (ileri) araması
- gerileme (geri) araması
- kısmi sıralı planlama
- plan varlığı karmaşıklığı
Temel kuramlar
- STRIPS gösterimi
- STRIPS, dünyayı bir dizi doğru önerme olarak ve her eylemi bir ön koşul listesi ile ekleme ve silme listeleriyle tanımlamaktadır; bu sayede bir eylemi uygulamak basitçe önermeleri eklemekte ve kaldırmaktadır. Bu faktörlenmiş model, neredeyse tüm klasik planlayıcıların temelini oluşturmaktadır.
- İlerleme ve gerileme araması
- Klasik planlar, başlangıç durumundan ileriye doğru uygulanabilir eylemleri uygulayarak (ilerleme) veya hedeften geriye doğru gerilemiş alt hedefleri hesaplayarak (gerileme) bulunabilmektedir. Kısmi sıralı planlama ise toplam eylem sıralamasına olan bağlılığı gevşetmektedir.
- Planlamanın karmaşıklığı
- Önermeli bir STRIPS planının var olup olmadığına karar vermek genel olarak PSPACE-tamdır (PSPACE-complete); bu durum, planlamanın neden zor olduğunu resmi olarak açıklamakta ve onu pratik hale getirmek için sezgisel ve yapısal yöntemleri teşvik etmektedir.
Klinik önem
Klasik planlama gösterimleri, robot görev planlaması, otomatik montaj ve lojistik ile belirlenimci eylemlerin bir hedefe ulaşmak için sıralanması gereken her türlü uygulama için ortak bir arayüz sağlamaktadır. PDDL tabanlı klasik planlayıcılar, bu alanın ve Uluslararası Planlama Yarışmaları'nın temel araçları olarak kabul edilmektedir.
Tarihçe
STRIPS, 1971 civarında SRI'da Shakey robotunu kontrol etmek amacıyla geliştirilmiş olup, klasik planlamayı tanımlayan ön koşul/etki eylem modelini tanıtmıştır. Kısmi sıralı planlama 1970'ler ve 1980'lerde olgunlaşmış, Bylander 1994 yılında önermeli planlamanın PSPACE-tamlığını (PSPACE-completeness) ortaya koymuş ve PDDL standardı daha sonra alanın kıyaslama noktalarını birleştirmiştir.
Öne çıkan isimler
- Richard E. Fikes
- Nils J. Nilsson
- Tom Bylander
- Earl D. Sacerdoti
İlgili konular
Temel eserler
- fikes1971
- bylander1994
Sıkça sorulan sorular
- Klasik planlamanın varsayımları nelerdir?
- Klasik planlama, belirlenimci, tamamen gözlemlenebilir ve statik bir ortamda hareket eden tek bir ajanın varlığını, eylemlerin birim zaman aldığını ve başlangıç durumunun tamamen bilindiğini varsaymaktadır. Bu varsayımlardan herhangi birini gevşetmek, örneğin belirsizliğe veya eşzamanlılığa izin vermek, klasik modelin ötesinde daha zengin planlama problemlerine yol açmaktadır.
- STRIPS ekleme listesi ve silme listesi ne anlama gelmektedir?
- Bir STRIPS eylemi uygulandığında, ekleme listesindeki önermeler doğru olmakta ve silme listesindeki önermeler yanlış olmaktadır; diğer tüm önermeler değişmeden kalmaktadır. Bu basit güncelleme kuralı, STRIPS'i eylemlerin dünyayı nasıl değiştirdiğine dair kompakt ve hesaplama açısından uygun bir gösterim haline getirmektedir.