Hiyerarşik Görev Ağı Planlaması
Hiyerarşik görev ağı (HTN) planlaması, bir hedef duruma ulaşmak için doğrudan ilkel eylemler üzerinde arama yapmak yerine, yüksek seviyeli görevleri bir yöntem kütüphanesi kullanarak özyinelemeli olarak alt görevlere ayrıştırarak problemleri çözmektedir.
Tanım
HTN planlaması, bir problemi gerçekleştirilecek görevlerin başlangıç ağı ve bileşik görevleri alt görevlere ayrıştırmak için bir dizi yöntem olarak temsil etmektedir; bir çözüm, yöntemlerin kısıtlamalarına uyan, ilkel, yürütülebilir eylemlere ayrıştırmadır.
Kapsam
Bu konu, HTN planlama paradigmasını kapsamaktadır: görevler (ilkel ve bileşik), bileşik bir görevin alt görevlere nasıl ayrıştırılacağını belirten yöntemler ve başlangıçtaki görev ağını yalnızca yürütülebilir ilkel eylemler kalana kadar iyileştiren planlama süreci. Klasik planlamaya göre HTN planlamasının ifade gücü ve karmaşıklığı ile dikkate değer HTN planlayıcıları ele alınmaktadır. Klasik, hedef durum tabanlı planlama modeli ilgili konularda işlenmektedir; HTN planlaması ise prosedürel alan bilgisini kodlamaktadır.
Temel sorular
- Yöntemler, bileşik görevlerin nasıl gerçekleştirileceğine dair alan bilgisini nasıl kodlamaktadır?
- Görev ayrıştırması, klasik planlamada bir hedef duruma doğru aramadan nasıl farklılaşmaktadır?
- HTN planlamasının ifade gücü ve hesaplama karmaşıklığı klasik planlamaya kıyasla nasıldır?
- Alt görevler arasındaki sıralama ve ön koşul kısıtlamaları ayrıştırma sırasında nasıl ele alınmaktadır?
Anahtar kavramlar
- ilkel ve bileşik görevler
- yöntemler ve ayrıştırma
- görev ağları
- sıralama kısıtlamaları
- prosedürel alan bilgisi
- HTN ifade gücü
- sıralı görev ayrıştırması
- SHOP2
Temel kuramlar
- Yöntemlerle görev ayrıştırması
- HTN planlaması, hedef odaklı aramayı özyinelemeli ayrıştırma ile değiştirmektedir: bileşik görevler, tüm görevler ilkel hale gelene kadar yöntemler aracılığıyla alt görev ağlarına genişletilmekte, bu da görevlerin nasıl gerçekleştirileceğine dair insan uzmanlığının doğrudan kodlanmasına olanak tanımaktadır.
- HTN planlamasının ifade gücü ve karmaşıklığı
- HTN planlaması, klasik STRIPS planlamasından kesinlikle daha ifade gücüne sahiptir; genel formunda plan varlığı karar verilemez olabilir ve kısıtlı formları daha yüksek karmaşıklık sınıflarına girmektedir, bu da yöntem tabanlı ayrıştırmanın gücünü yansıtmaktadır.
- Sıralı görev ayrıştırma planlayıcıları
- SHOP2 gibi pratik HTN planlayıcıları, görevleri yürütülecekleri sıraya göre ayrıştırarak planlama yapmaktadır; bu da ön koşulları tam olarak belirlenmiş durumlara göre değerlendirmelerine ve zengin alan bilgisini verimli bir şekilde dahil etmelerine olanak tanımaktadır.
Klinik önem
HTN planlaması, uzman prosedürlerin bilindiği ve takip edilmesi gereken üretim süreç planlaması, askeri ve lojistik operasyonlar, web hizmeti kompozisyonu, oyun ve hikaye üretimi gibi alanlarda yaygın olarak kullanılmaktadır, çünkü yöntemler alan uzmanlarının görevleri gerçekleştirmenin standart yollarını kodlamasına olanak tanımaktadır.
Tarihçe
Hiyerarşik planlama, 1970'lerde Sacerdoti'nin NOAH'ına ve soyutlama hiyerarşilerine dayanmaktadır. Erol, Hendler ve Nau, 1990'ların başında HTN planlamasını resmileştirmiş ve karmaşıklığını analiz etmiştir. SHOP ve SHOP2 planlayıcıları (yaklaşık 2000-2003 yılları arasında) sıralı HTN planlamasını pratik ve yaygın olarak kullanılan bir teknoloji haline getirmiştir.
Öne çıkan isimler
- Dana Nau
- Kutluhan Erol
- James Hendler
- Earl D. Sacerdoti
- Austin Tate
İlgili konular
Temel eserler
- erol1994
- nau2003
Sıkça sorulan sorular
- HTN planlaması klasik planlamadan nasıl farklıdır?
- Klasik planlama, yalnızca eylemlerin ön koşullarını ve etkilerini kullanarak bir hedef duruma ulaşan herhangi bir eylem dizisini aramaktadır. HTN planlaması ise, gerçekleştirilecek görevlerden başlamakta ve bu görevlerin prosedürel olarak normalde nasıl yapıldığını kodlayan yöntemleri kullanarak onları ayrıştırmaktadır, bu nedenle daha zengin alan bilgisine dayanmaktadır.
- HTN planlaması neden karar verilemez olabilir?
- Yöntemler, bileşik bir görevi daha fazla bileşik görev içeren ağlara ayrıştırabildiğinden, ayrıştırma süreci sınırsızca özyinelemeli olabilir, tıpkı keyfi uzunlukta türetmeler üreten bir dilbilgisi gibi. Bu nedenle, genel formunda geçerli bir ayrıştırmanın var olup olmadığına karar vermek karar verilemezdir.