برنامهریزی شبکه وظایف سلسلهمراتبی
برنامهریزی شبکه وظایف سلسلهمراتبی (HTN) مسائل را با تجزیه بازگشتی وظایف سطح بالا به زیروظایف با استفاده از کتابخانهای از روشها حل میکند، به جای جستجوی مستقیم در میان اقدامات اولیه برای رسیدن به یک وضعیت هدف.
Definition
برنامهریزی HTN یک مسئله را به عنوان یک شبکه اولیه از وظایف قابل انجام و مجموعهای از روشها برای تجزیه وظایف ترکیبی به زیروظایف نمایش میدهد؛ یک راهحل، تجزیهای به اقدامات اولیه و قابل اجرا است که محدودیتهای روشها را رعایت میکند.
Scope
این موضوع پارادایم برنامهریزی HTN را پوشش میدهد: وظایف (اولیه و ترکیبی)، روشهایی که نحوه تجزیه یک وظیفه ترکیبی به زیروظایف را مشخص میکنند، و فرآیند برنامهریزی که یک شبکه وظیفه اولیه را تا زمانی که فقط اقدامات اولیه قابل اجرا باقی بمانند، اصلاح میکند. این موضوع به بیانپذیری و پیچیدگی برنامهریزی HTN نسبت به برنامهریزی کلاسیک و برنامهریزهای برجسته HTN میپردازد. مدل برنامهریزی کلاسیک و مبتنی بر وضعیت هدف در موضوعات مرتبط مورد بررسی قرار میگیرد؛ برنامهریزی HTN به جای آن دانش دامنه رویهای را کدگذاری میکند.
Core questions
- چگونه روشها دانش دامنه را در مورد نحوه انجام وظایف ترکیبی کدگذاری میکنند؟
- تجزیه وظایف چگونه با جستجو به سمت یک وضعیت هدف در برنامهریزی کلاسیک تفاوت دارد؟
- بیانپذیری و پیچیدگی محاسباتی برنامهریزی HTN در مقایسه با برنامهریزی کلاسیک چیست؟
- محدودیتهای ترتیب و پیششرط در میان زیروظایف در طول تجزیه چگونه مدیریت میشوند؟
Key concepts
- وظایف اولیه و ترکیبی
- روشها و تجزیه
- شبکههای وظیفه
- محدودیتهای ترتیب
- دانش دامنه رویهای
- بیانپذیری HTN
- تجزیه وظیفه مرتب
- SHOP2
Key theories
- تجزیه وظیفه با روشها
- برنامهریزی HTN جستجوی هدفگرا را با تجزیه بازگشتی جایگزین میکند: وظایف ترکیبی از طریق روشها به شبکههایی از زیروظایف گسترش مییابند تا زمانی که همه وظایف اولیه شوند، که امکان کدگذاری مستقیم تخصص انسانی در مورد نحوه انجام وظایف را فراهم میکند.
- بیانپذیری و پیچیدگی برنامهریزی HTN
- برنامهریزی HTN به طور قطعی بیانپذیرتر از برنامهریزی کلاسیک STRIPS است؛ در شکل کلی آن، وجود طرح میتواند غیرقابل تصمیمگیری باشد، و اشکال محدود آن به کلاسهای پیچیدگی بالاتری تعلق دارند، که قدرت تجزیه مبتنی بر روش را منعکس میکند.
- برنامهریزهای تجزیه وظیفه مرتب
- برنامهریزهای عملی HTN مانند SHOP2 با تجزیه وظایف به ترتیبی که اجرا خواهند شد، برنامهریزی میکنند، که به آنها اجازه میدهد پیششرطها را در برابر وضعیتهای کاملاً مشخص ارزیابی کرده و دانش دامنه غنی را به طور کارآمدی در خود جای دهند.
Clinical relevance
برنامهریزی HTN به طور گستردهای در مواردی که رویههای تخصصی شناخته شده و باید دنبال شوند، مانند برنامهریزی فرآیندهای تولید، عملیات نظامی و لجستیک، ترکیب خدمات وب، و تولید بازی و داستان، استفاده میشود، زیرا روشها به کارشناسان دامنه اجازه میدهند تا روشهای استاندارد انجام وظایف را کدگذاری کنند.
History
برنامهریزی سلسلهمراتبی به NOAH ساکردوتی و سلسلهمراتب انتزاعی در دهه 1970 بازمیگردد. ارول، هندلر و نائو برنامهریزی HTN را در اوایل دهه 1990 رسمی کردند و پیچیدگی آن را تحلیل کردند، و برنامهریزهای SHOP و SHOP2 (حدود 2000-2003) برنامهریزی HTN مرتب را به یک فناوری عملی و پرکاربرد تبدیل کردند.
Key figures
- Dana Nau
- Kutluhan Erol
- James Hendler
- Earl D. Sacerdoti
- Austin Tate
Related topics
Seminal works
- erol1994
- nau2003
Frequently asked questions
- برنامهریزی HTN چه تفاوتی با برنامهریزی کلاسیک دارد؟
- برنامهریزی کلاسیک به دنبال هر توالی عملی است که به یک وضعیت هدف میرسد، و فقط از پیششرطها و اثرات عملیات استفاده میکند. برنامهریزی HTN به جای آن از وظایفی که باید انجام شوند شروع میکند و آنها را با استفاده از روشهایی که نحوه انجام معمول آن وظایف را به صورت رویهای کدگذاری میکنند، تجزیه میکند، بنابراین به دانش دامنه غنیتری متکی است.
- چرا برنامهریزی HTN میتواند غیرقابل تصمیمگیری باشد؟
- زیرا روشها میتوانند یک وظیفه ترکیبی را به شبکههایی تجزیه کنند که شامل وظایف ترکیبی بیشتری هستند، فرآیند تجزیه میتواند به طور نامحدود بازگشتی باشد، بسیار شبیه به گرامری که اشتقاقات دلخواه طولانی تولید میکند. بنابراین، در شکل کلی آن، تصمیمگیری در مورد وجود یک تجزیه معتبر غیرقابل تصمیمگیری است.