Loading...
Search
| Friend's email | |
| Your name | |
| Your email | |
| enter code | |
This page was sent successfuly
Digital Object List
Bookmark
Review List
23 viewed
برنامه ریزی زمانی با استفاده از ارضاپذیری
محجوب، علی Mahjoob, Ali
- Type of Document: M.Sc. Thesis
- Language: Farsi
- Document No: 43867 (19)
- University: Sharif University of Technology
- Department: Computer Engineering
- Advisor(s): Ghassem Sani, Gholamreza
- Abstract:
- Automated Planning is an active research area in Artificial Intelligence. In Classical planning, for simplicity, time is considered as the order of actions in plan. In temporal planning, due to the importance of time in real world problems, this simplifying assumption is not considered, and time is explicitly used in the planning process. Most of current methods for temporal planning are extensions of classical planning methods to include the explicit definition of time. Planning using Satisfiability is used as an efficient method to find optimal solutions for classical planning problems. In this dissertation, a temporal planner based on Satisfiability has been developed. This planner, as we named it, PLANET, can find optimal solutions for temporal planning. There are, in general, two models to describe temporal planning: Conservative and Non-Conservative. The latter, in which the problems with Required Concurrency are also considered, is a more general form of the former. PLANET can solve non-conservative temporal planning problems, too. In addition, in this dissertation, a new method is proposed to extend classical planning graph for temporal planning. The resulting temporal planning graph, is constructed in a simpler way than that of previous methods, and is also usable for non-conservative temporal planning. In order to improve the performance of PLANET, the so-called Mutex relations extracted from the graph are appended to the Satisfiability encoding. Also, a lower bound for the plan’s Makespan is estimated using the graph, and used as a starting point for the search process. The experimental results show that the performance of PLANET is comparable with that of non-optimal temporal planners
- Keywords:
- Temporal Planning ; Satisfiability-based Planning ; Temporal Planning Graph
-
محتواي پايان نامه
- view
- فصل 1 مقدمه
- فصل 2 پیش زمینه
- 2-1 برنامهریزی کلاسیک
- شکل (2-1) مسأله ناسازگاری سازمن
- 2-2 برنامهریزی زمانی
- 2-2-1 برنامهریزی زمانی محافظهکارانه
- شکل (2-2) مثالی از برنامهریزی زمانی محافظهکارانه
- 2-2-2 برنامهریزی زمانی غیرمحافظهکارانه
- جدول (2-1) کنش مدتدار در PDDL2.1
- شکل (2-3) مثالی از دامنه کبریت و فیوز (دارای همزمانی اجباری).
- شکل (2-4) گانت چارت یک برنامه از دامنه کبریت و فیوز (با فرض ε مساوی 0.01).
- 2-2-1 برنامهریزی زمانی محافظهکارانه
- 2-3 برنامهریزی مبتنی بر گراف
- 2-3-1 رابطه دو به دو ناسازگاری
- جدول (2-2) دو به دو ناسازگاری برای کنشها
- جدول (2-3) دو به دو ناسازگاری برای گزارهها
- 2-3-2 استخراج برنامه با جستجو در گراف
- 2-3-1 رابطه دو به دو ناسازگاری
- 2-4 برنامهریزی با استفاده از ارضاپذیری
- شکل (2-5) ساختار کلی یک برنامهریز مبتنی بر ارضاپذیری
- 2-4-2 ترجمه به روش کدگذاری موازی
- جدول (1-1) عبارتهای کدگذاری موازی برای برنامهریزی کلاسیک
- 2-4-3 سایر کدگذاریها برای برنامهریزی کلاسیک
- 2-4-4 استخراج برنامه از جواب حل کننده ارضاپذیری
- 2-5 برنامهریزی با جستجوی اکتشافی
- 2-1 برنامهریزی کلاسیک
- فصل 3 کارهای پیشین در برنامهریزی زمانی
- 3-1 برنامهریزی زمانی با جستجو در فضای وضعیت
- 3-2 برنامهریزی زمانی با جستجو در فضای برنامه
- 3-3 برنامهریزی زمانی مبتنی بر گراف
- 3-4 برنامهریزی زمانی به روش ارضاپذیری
- 3-4-1 برنامهریز T-SATPLAN
- 3-4-2 برنامهریز STEP
- 3-4-3 برنامهریز IT-SAT
- فصل 4 برنامهریز زمانی پیشنهاد شده
- 4-1 روشهای ضمنی و صریح برای توصیف زمان
- 4-2 تعریف زمان به صورت عدد صحیح
- 4-3 روش ساخت گراف برنامهریزی زمانی
- 4-4 تبدیل مسأله برنامهریزی به ارضاپذیری
- جدول (4-1) متغیرهای کدگذاری ارضاپذیری پیشنهادی
- جدول (4-2) عبارتهای کدگذاری ارضاپذیری پیشنهادی
- 4-5 استخراج برنامه از پاسخ حلکننده ارضاپذیری
- 4-6 الگوریتم اصلی برنامهریز PLANET
- فصل 5 نتایج تجربی
- 5-1 نتایج تجمیع شده
- جدول (5-1) نتایج تجمیع شده برنامهریزها
- جدول (5-2) نتایج تجمیع شده برنامهریزها در دامنههای دارای همزمانی اجباری
- 5-2 توصیف دامنههای مسابقات IPC سال 2011
- 5-2-1 دامنه برنامهریزی خدمه
- 5-2-2 دامنه آسانسورها
- 5-2-3 دامنه کاشیها
- 5-2-4 دامنه کبریت و فیوز
- 5-2-5 دامنه سفارشهای باز
- 5-2-6 دامنه چاپگر چندموتوره
- 5-2-7 دامنه پارکینگ
- 5-2-8 دامنه بازی میخ و حفره
- شکل (5-1) وضعیت آغازین تخته در مسائل 1 و 20 دامنه بازی میخ و حفره
- 5-2-9 دامنه بازی سوکوبان
- 5-2-10 دامنه ذخیرهسازی
- 5-2-11 دامنه کارگاه ماشینی زمانی
- 5-2-12 دامنه بچرخان و بازکن
- 5-3 توصیف دامنههای مسابقات IPC سال 2004
- 5-3-1 دامنه فرودگاه
- 5-3-2 دامنه ماهواره
- 5-3-3 دامنه دنیای لولهها
- 5-4 توصیف دامنههای مسابقات IPC سال 2002
- 5-4-1 دامنه انبارگاهها
- 5-4-2 دامنه آمایش راننده
- 5-4-3 دامنه سیارهنوردها
- 5-4-4 دامنه هواپیمایی زینو
- 5-5 توصیف سایر دامنهها
- 5-5-1 دامنه کبریت و فیوز توسعه یافته
- 5-5-2 دامنه آمایش شیفتی راننده
- 5-1 نتایج تجمیع شده
- فصل 6 نتیجهگیری و پیشنهاد
- مراجع
- پیوست الف: نتایج مشروح برنامهریزها در هر دامنه
- جدول (6-1) نتایج در دامنه خدمه
- جدول (6-2) نتایج در دامنه آسانسورها
- جدول (6-3) نتایج در دامنه کاشیها
- جدول (6-4) نتایج در دامنه کبریت و فیوز
- جدول (6-5) نتایج در دامنه سفارشهای باز
- جدول (6-6) نتایج در دامنه چاپگر چندموتوره
- جدول (6-7) نتایج در دامنه پارکینگ
- جدول (6-8) نتایج در دامنه بازی میخ و حفره
- جدول (6-9) نتایج در دامنه سوکوبان
- جدول (6-10) نتایج در دامنه ذخیرهسازی
- جدول (6-11) نتایج در دامنه کارگاه ماشینی زمانی
- جدول (6-12) نتایج در دامنه بچرخان و بازکن
- جدول (6-13) نتایج در دامنه فرودگاه
- جدول (6-14) نتایج در دامنه ماهواره
- جدول (6-15) نتایج در دامنه دنیای لولهها
- جدول (6-16) نتایج در دامنه انبارگاهها
- جدول (6-17) نتایج در دامنه آمایش راننده
- جدول (6-18) نتایج در دامنه سیارهنوردها
- جدول (6-19) نتایج در دامنه هواپیمایی زینو
- جدول (6-20) نتایج در دامنه کبریت و فیوز توسعه یافته
- جدول (6-21) نتایج در دامنه آمایش شیفتی راننده
- واژهنامه فارسی به انگلیسی
- واژهنامه انگلیسی به فارسی