Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

ابتدا، مایلم از ناظر اصلی خود دکتر کیانگ شن برای کمک، مشاوره و دوستی اش در سراسر این مدت تشکر کنم. همچنین از سرپرست دومم دکتر پیتر جارویس برای اشتیاق، کمک و دوستی بسیار سپاسگزارم. همچنین می‌خواهم از سایر اعضای گروه استدلال تقریبی و کیفی در ادینبورگ که به من کمک و الهام بخشیدند تشکر کنم. این پروژه توسط یک دانشجوی EPSRC با شماره جایزه 97305803 تامین شده است. بنابراین، مایلم از EPSRC برای حمایت از این کار تشکر کنم. با تشکر فراوان از کارکنان دانشگاه ادینبورگ برای همه کمک ها و حمایت هایشان و برای رفع سریع هر گونه مشکل فنی که من داشته ام. تمام خانواده من در طول تکمیل این کتاب مشوق و حمایت بوده اند، که برای همیشه مدیون آن هستم. یورک، آوریل 2003 یان میگل فهرست مطالب فهرست شکل ها XV 1 مقدمه. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 حل CSP های کلاسیک . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 2 کاربرد یونهای CSP کلاسیک. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. 3 محدودیت های CSP کلاسیک. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 3. 1 CSP انعطاف پذیر 6 1. 3. 2 CSP پویا . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 4 CSP قابل انعطاف پویا . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 5 برنامه ریزی انعطاف پذیر: یک برنامه DFCSP. . . . . . . . . . . . . . . . . . 8 1. 6 ساختار . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 7 مشارکت و اهمیت آنها 11 2 مسئله رضایت از محدودیت 13 2. 1 محدودیت ها و نمودارهای محدودیت. . . . . . . . . . . . . . . . . . . . . . . 13 2. 2 تکنیک های راه حل جستجوی درخت برای CSP کلاسیک. . . . . . . . . . 16 2. 2. 1 بک ترک . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. 2. 2 پرش به عقب . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 2. 3 پرش معکوس مبتنی بر درگیری. . . . . . . . . . . . . . . . . . . . . 19 2. 2. 4 Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

First, I would like to thank my principal supervisor Dr Qiang Shen for all his help, advice and friendship throughout. Many thanks also to my second supervisor Dr Peter Jarvis for his enthusiasm, help and friendship. I would also like to thank the other members of the Approximate and Qualitative Reasoning group at Edinburgh who have also helped and inspired me. This project has been funded by an EPSRC studentship, award num­ ber 97305803. I would like, therefore, to extend my gratitude to EPSRC for supporting this work. Many thanks to the staff at Edinburgh University for all their help and support and for promptly fixing any technical problems that I have had . My whole family have been both encouraging and supportive throughout the completion of this book, for which I am forever indebted. York, April 2003 Ian Miguel Contents List of Figures XV 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 Solving Classical CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 2 Applicat ions of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. 3 Limitations of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 3. 1 Flexible CSP 6 1. 3. 2 Dynamic CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 4 Dynamic Flexible CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 5 Flexible Planning: a DFCSP Application . . . . . . . . . . . . . . . . . . 8 1. 6 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 7 Contributions and their Significance 11 2 The Constraint Satisfaction Problem 13 2. 1 Constraints and Constraint Graphs . . . . . . . . . . . . . . . . . . . . . . . 13 2. 2 Tree Search Solution Techniques for Classical CSP . . . . . . . . . . 16 2. 2. 1 Backtrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. 2. 2 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 2. 3 Conflict-Directed Backjumping . . . . . . . . . . . . . . . . . . . . . 19 2. 2. 4 Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .