Ierarxik vazifalar tarmog'i - Hierarchical task network

Yilda sun'iy intellekt, ierarxik vazifalar tarmog'ini rejalashtirish (HTN) ga yondashuv avtomatlashtirilgan rejalashtirish bunda harakatlar orasidagi bog'liqlik ierarxik tuzilgan tarmoqlar shaklida berilishi mumkin.

Rejalashtirish muammolari ierarxik vazifalar tarmog'i yondashuvida quyidagi vazifalar to'plamini taqdim etish orqali ko'rsatiladi:

  1. ning harakatlariga taxminan mos keladigan ibtidoiy (boshlang'ich holat) vazifalar STRIPS;
  2. oddiy vazifalar to'plamidan iborat deb qarash mumkin bo'lgan murakkab vazifalar (oraliq holat);
  3. maqsadlariga taxminan mos keladigan maqsad vazifalari (maqsad holati) STRIPS, lekin umumiyroq.

Keyinchalik HTN muammosini hal qilish - bu boshlang'ich vazifalar tarmog'idan murakkab vazifalarni o'zlarining oddiy vazifalar to'plamiga ajratish va buyurtma cheklovlarini kiritish orqali olinadigan ibtidoiy vazifalar ketma-ketligi.

Ibtidoiy vazifa - bu bajariladigan holat, uning old shartini qo'llab-quvvatlagan holda to'g'ridan-to'g'ri bajarilishi mumkin bo'lgan harakat. Murakkab vazifa - bu ibtidoiy yoki mavhum bo'lishi mumkin bo'lgan qisman tartiblangan qo'shimcha vazifalar to'plamidan tashkil topgan murakkab vazifadir. Maqsad vazifasi - bu shartni qondirish vazifasi. Ibtidoiy va boshqa vazifalarning farqi shundaki, ibtidoiy harakatlar to'g'ridan-to'g'ri bajarilishi mumkin. Murakkab va maqsadli vazifalar ikkalasi ham ibtidoiy harakatlar ketma-ketligini talab qiladi; ammo, maqsad vazifalari bajarilishi kerak bo'lgan shartlar bo'yicha belgilanadi, murakkab vazifalar esa faqat quyida keltirilgan vazifalar tarmog'i orqali boshqa vazifalar bo'yicha belgilanishi mumkin.

Vazifalar orasidagi cheklovlar (ierarxik) vazifalar tarmoqlari deb nomlangan tarmoqlar ko'rinishida ifodalanadi. Vazifalar tarmog'i - bu vazifalar va ular orasidagi cheklovlar to'plamidir. Bunday tarmoq boshqa birlashma yoki maqsad vazifasini amalga oshirish uchun dastlabki shart sifatida ishlatilishi mumkin. Shunday qilib, ma'lum bir vazifani faqat boshqa bir qator harakatlar (tarmoqda aytib o'tilganlar) bajarilgan taqdirda va ular ular orasidagi cheklovlar (tarmoq tomonidan ko'rsatilgan) qondiriladigan tarzda amalga oshirilgan taqdirdagina amalga oshirish mumkinligini bildirish mumkin. . Juda keng qo'llanilgan ierarxik vazifalar tarmoqlarini namoyish etish uchun ma'lum bir rasmiylik TAEMS.

Domenga bog'liq bo'lmagan eng taniqli HTN-rejalashtirish tizimlarining ba'zilari:

  • Nonlin, birinchi HTN rejalashtirish tizimlaridan biri.[1]
  • SIPE-2[2]
  • O-reja, ochiq rejalashtirish me'morchiligi[3]
  • UMCP, birinchi ishonchli va to'liq HTN rejalashtirish tizimlari.[4]
  • I-X / I-reja[5]
  • SHOP2, HTN-rejalashtiruvchisi Merilend universiteti, kollej parki.[6]
  • PANDA, gibrid rejalashtirish uchun mo'ljallangan tizim, Germaniyaning Ulm universitetida ishlab chiqilgan HTN rejalashtirishning kengaytmasi. [7]
  • HTNPlan-P, imtiyozga asoslangan HTNni rejalashtirish.[8]

HTNni rejalashtirish nisbatan aniqroq ifodalangan STRIPS, umumiy holatda qarorga kelmaydigan darajada.[9] Biroq, ma'lum bo'lgan murakkabliklar bilan HTNni rejalashtirishning ko'plab sintaktik cheklashlari hal qilinadi To'liq emas ga 2-EXPSPACE tugallangan,[10] va ba'zi HTN muammolari samarali tarzda tuzilishi mumkin PDDL, STRIPSga o'xshash til.[11]

Shuningdek qarang

Adabiyotlar

  1. ^ Nonlin
  2. ^ Devid E. Uilkins. "SIPE-2: Interaktiv rejalashtirish va bajarish tizimi". Sun'iy intellekt markazi. Xalqaro SRI. Olingan 2013-06-13.
  3. ^ O-reja
  4. ^ UMCP
  5. ^ I-X / I-reja
  6. ^ DO'KON2
  7. ^ PANDA
  8. ^ HTNPlan-P
  9. ^ Erol, Kutluhan; Xendler, Jeyms; Nau, Dana S. (1996). "HTT rejalashtirish uchun murakkablik natijalari" (PDF). Matematika va sun'iy intellekt yilnomalari. Springer. 18: 69–93. Olingan 8 fevral 2015.
  10. ^ Alford, Ron; Berxer, Paskal; Aha, Devid (iyun 2015). HTNni rejalashtirish uchun qat'iy chegaralar (PDF). Avtomatlashtirilgan rejalashtirish va rejalashtirish bo'yicha 25-xalqaro konferentsiya (ICAPS) materiallari. Olingan 8 fevral 2015.
  11. ^ Alford, Ron; Kuter, Ugur; Nau, Dana S. (iyul 2009). HTN-larni PDDL-ga tarjima qilish: kichik miqdordagi domen bilimlari uzoq yo'lni bosib o'tishi mumkin (PDF). Sun'iy intellekt bo'yicha yigirma birinchi xalqaro qo'shma konferentsiya (IJCAI). Olingan 8 fevral 2015.