مشکل‌گشای مؤسسه تحقیقاتی استنفورد

مشکل‌گشای موسسه تحقیقاتی استنفورد که با نام اختصاری آن STRIPS شناخته می شود، یک برنامه ریز خودکار است که توسط ریچارد فِیکس و نیلز نیلسون در سال 1971 در SRI International توسعه یافت. ^[۱] همین نام بعداً برای اشاره به زبان رسمی مخصوص ورودی‌های این برنامه‌ریز استفاده شد. این زبان، پایه بسیاری از زبان‌ها برای پدیدآوری نمونه‌های مشکل برنامه‌ریزی خودکار است که امروزه مورد استفاده قرار می‌گیرند. چنین زبان هایی معمولاً به عنوان زبان‌های عملی شناخته می‌شوند. این مقاله فقط زبان را توصیف می کند، نه برنامه ریز را.

یک نمونه STRIPS از موارد زیر تشکیل شده است:

یک حالت اولیه؛
مشخصات حالات هدف(یعنی حالاتی که برنامه ریز در تلاش است به آنها برسد.)
مجموعه ای از اعمال(برای هر عمل نیز موارد زیر باید موجود باشند:
- پیش شرط (آنچه باید قبل از انجام عمل رخ داده باشد)؛
- پس شرایط (آنچه پس از انجام عمل رخ خواهد داد).

از نظر ریاضی، یک نمونه STRIPS یک چهارتایی مرتب است به صورت $\langle P,O,I,G\rangle$ ، که در آن داریم:

$P$ مجموعه ای از شرایط (متغیرهای گزاره‌ای ) است.
$O$ مجموعه‌ای از عملگرها (اعمال) است. هر عملگر خودش یک چهارتایی مرتب است $\langle \alpha ,\beta ,\gamma ,\delta \rangle$ ، هر عنصر مجموعه ای از شرایط است. این چهار مجموعه مشخص می کنند کدام شرایط باید درست باشد تا عمل قابل اجرا باشد، کدام نادرست باشد، کدام یک پس از اجرای عمل حقیقت می‌یابند و کدام یک نادرست شود.
$I$ حالت اولیه است، به عنوان مجموعه شرایطی که در ابتدا درست هستند(همه موارد دیگر نادرست فرض می شوند) داده می شود.
$G$ مشخصات حالت هدف است. این به صورت زوج مرتب $\langle N,M\rangle$ داده می شود و مشخص می‌کند به ترتیب کدام شرایط درست یا نادرست هستند تا بتوان در ادامه یک حالت را به عنوان حالت هدف در نظر گرفت.

یک نمونه از این نوع برنامه‌ریزی، دنباله‌ای از عملگرها است که می توانند از حالت اولیه اجرا و به حالت هدف منتهی شوند.

یک نمونه از حل مسئله با STRIPS

یک میمون در مکان A در یک آزمایشگاه قرار دارد. یک جعبه در مکان C وجود دارد. میمون موزهایی را می‌خواهد که در مکان B از سقف آویزان شده‌اند، اما باید جعبه را حرکت داده و بر روی آن برود تا دستش به موزها برسد. حل این مسئله با STRIPS به صورت زیر خواهد بود:

Initial state: At(A), Level(low), BoxAt(C), BananasAt(B)
Goal state:    Have(bananas)

Actions:
               // move from X to Y
               _Move(X, Y)_
               Preconditions:  At(X), Level(low)
               Postconditions: not At(X), At(Y)
               
               // climb up on the box
               _ClimbUp(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(low)
               Postconditions: Level(high), not Level(low)
               
               // climb down from the box
               _ClimbDown(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(high)
               Postconditions: Level(low), not Level(high)
               
               // move monkey and box from X to Y
               _MoveBox(X, Y)_
               Preconditions:  At(X), BoxAt(X), Level(low)
               Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
               
               // take the bananas
               _TakeBananas(Location)_
               Preconditions:  At(Location), BananasAt(Location), Level(high)
               Postconditions: Have(bananas)

منابع

↑ Richard E. Fikes, Nils J. Nilsson (Winter 1971). "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving" (PDF). Artificial Intelligence. 2 (3–4): 189–208. CiteSeerX 10.1.1.78.8292. doi:10.1016/0004-3702(71)90010-5.

[1] Richard E. Fikes, Nils J. Nilsson (Winter 1971). "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving" (PDF). Artificial Intelligence. 2 (3–4): 189–208. CiteSeerX 10.1.1.78.8292. doi:10.1016/0004-3702(71)90010-5.

[۱]