Stanford Research Institute Problem Solverหรือที่รู้จักกันในชื่อย่อSTRIPSเป็นตัววางแผนอัตโนมัติที่พัฒนาโดยRichard FikesและNils Nilssonในปี 1971 ที่SRI International [ ^{1 ] ต่อ}มาชื่อเดียวกันนี้ถูกนำมาใช้เพื่ออ้างถึงภาษาทางการของข้อมูลป้อนเข้าสำหรับตัววางแผนนี้ ภาษานี้เป็นพื้นฐานสำหรับภาษาส่วนใหญ่ที่ใช้ในการแสดง ตัวอย่างปัญหา การวางแผนอัตโนมัติที่ใช้ในปัจจุบัน ภาษาดังกล่าวโดยทั่วไปเรียกว่าภาษาการกระทำบทความนี้อธิบายเฉพาะภาษาเท่านั้น ไม่ใช่ตัววางแผน

อินสแตนซ์ของ STRIPS ประกอบด้วย:

• สถานะเริ่มต้น;
• การระบุสถานะเป้าหมาย – สถานการณ์ที่ผู้วางแผนพยายามไปให้ถึง;
• ชุดของการกระทำ โดยแต่ละการกระทำจะประกอบด้วยสิ่งต่อไปนี้:
  • เงื่อนไขเบื้องต้น (สิ่งที่ต้องมีให้พร้อมก่อนที่จะดำเนินการ)
  • เงื่อนไขหลังการดำเนินการ (สิ่งที่ถูกกำหนดขึ้นหลังจากดำเนินการเสร็จสิ้นแล้ว)

ในทางคณิตศาสตร์ อินสแตนซ์ของ STRIPS คือควอดรูเพิลซึ่งแต่ละองค์ประกอบมีความหมายดังต่อไปนี้: ${\displaystyle \langle P,O,I,G\rangle }$

1. ${\displaystyle P}$คือชุดของเงื่อนไข (เช่นตัวแปรเชิงประพจน์ )
2. ${\displaystyle O}$คือชุดของตัวดำเนินการ (เช่น การกระทำ) โดยที่ตัวดำเนินการแต่ละตัวเป็นควอดรูเพิล(quadruple) ซึ่งแต่ละองค์ประกอบเป็นชุดของเงื่อนไข ชุดทั้งสี่นี้ระบุตามลำดับว่า เงื่อนไขใดบ้างที่ต้องเป็นจริงเพื่อให้การกระทำนั้นสามารถดำเนินการได้ เงื่อนไขใดบ้างที่ต้องเป็นเท็จ เงื่อนไขใดบ้างที่กลายเป็นจริงโดยการกระทำ และเงื่อนไขใดบ้างที่กลายเป็นเท็จ${\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle }$
3. ${\displaystyle I}$คือสถานะเริ่มต้น ซึ่งกำหนดเป็นชุดของเงื่อนไขที่เป็นจริงในตอนเริ่มต้น (เงื่อนไขอื่นๆ ถือว่าเท็จ)
4. ${\displaystyle G}$คือข้อกำหนดของสถานะเป้าหมายซึ่งกำหนดเป็นคู่ของเงื่อนไข โดยเงื่อนไขใดเป็นจริงและเท็จตามลำดับ เพื่อให้สถานะนั้นถือว่าเป็นสถานะเป้าหมาย${\displaystyle \langle N,M\rangle }$

แผนสำหรับกรณีการวางแผนดังกล่าว คือลำดับของตัวดำเนินการที่สามารถดำเนินการได้จากสถานะเริ่มต้นและนำไปสู่สถานะเป้าหมาย

ในทางทฤษฎี สถานะคือชุดของเงื่อนไข: สถานะหนึ่งๆ จะถูกแทนด้วยชุดของเงื่อนไขที่เป็นจริงในสถานะนั้น การเปลี่ยนผ่านระหว่างสถานะต่างๆ จะถูกจำลองโดยฟังก์ชันการเปลี่ยนผ่าน ซึ่งเป็นฟังก์ชันที่แมปสถานะต่างๆ ไปสู่สถานะใหม่ที่เกิดขึ้นจากการดำเนินการต่างๆ เนื่องจากสถานะต่างๆ ถูกแทนด้วยชุดของเงื่อนไข ดังนั้นฟังก์ชันการเปลี่ยนผ่านที่เกี่ยวข้องกับอินสแตนซ์ STRIPS จึงเป็นฟังก์ชัน ${\displaystyle \langle P,O,I,G\rangle }$

${\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},}$

โดยที่คือเซตของเซตย่อยทั้งหมดของและดังนั้น คือเซตของสถานะที่เป็นไปได้ทั้งหมด ${\displaystyle 2^{P}}$${\displaystyle P}$

ฟังก์ชันการเปลี่ยนสถานะสามารถกำหนดได้ดังนี้ โดยใช้สมมติฐานแบบง่ายๆ ว่าการกระทำต่างๆ สามารถดำเนินการได้เสมอ แต่จะไม่มีผลใดๆ หากไม่ตรงตามเงื่อนไขเบื้องต้น: ${\displaystyle \operatorname {succ} }$${\displaystyle C\subseteq P}$

${\displaystyle \operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )}$	=${\displaystyle (C\backslash \delta )\cup \gamma }$	ถ้าและ${\displaystyle \alpha \subseteq C}$${\displaystyle \beta \cap C=\varnothing }$
	=${\displaystyle C}$	มิฉะนั้น

ฟังก์ชันนี้สามารถขยายไปสู่ลำดับของการกระทำได้โดยใช้สมการเวียนเกิดต่อไปนี้: ${\displaystyle \operatorname {succ} }$

${\displaystyle \operatorname {succ} (C,[\ ])=C}$

${\displaystyle \operatorname {succ} (C,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])}$

แผนสำหรับอินสแตนซ์ STRIPS คือลำดับของการกระทำที่ทำให้สถานะที่ได้จากการดำเนินการตามลำดับจากสถานะเริ่มต้นเป็นไปตามเงื่อนไขเป้าหมาย กล่าวอย่างเป็นทางการคือ เป็นแผนหากเป็นไปตามเงื่อนไขสองข้อต่อไปนี้: ${\displaystyle [a_{1},a_{2},\ldots ,a_{n}]}$${\displaystyle G=\langle N,M\rangle }$${\displaystyle F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])}$

${\displaystyle N\subseteq F}$

${\displaystyle M\cap F=\varnothing }$

ภาษาข้างต้นนั้นแท้จริงแล้วคือ เวอร์ชัน เชิงประพจน์ของ STRIPS ในทางปฏิบัติ เงื่อนไขมักเกี่ยวข้องกับวัตถุ ตัวอย่างเช่น ตำแหน่งของหุ่นยนต์สามารถจำลองได้ด้วยภาคแสดง และหมายความว่าหุ่นยนต์อยู่ในห้องที่ 1 ในกรณีนี้ การกระทำสามารถมีตัวแปรอิสระซึ่งมีการกำหนดปริมาณเชิงการมีอยู่โดยปริยาย กล่าวอีกนัยหนึ่ง การกระทำแสดงถึงการกระทำเชิงประพจน์ที่เป็นไปได้ทั้งหมดที่สามารถได้มาจากการแทนที่ตัวแปรอิสระแต่ละตัวด้วยค่า ${\displaystyle ที่}$${\displaystyle ที่ห้อง(room1)}$

ในภาษาที่อธิบายไว้ข้างต้น สถานะเริ่มต้นถือว่าทราบอย่างสมบูรณ์: เงื่อนไขที่ไม่อยู่ในนั้นจะถือว่าเท็จทั้งหมด อย่างไรก็ตาม นี่มักเป็นข้อสมมติฐานที่จำกัด เนื่องจากมีตัวอย่างตามธรรมชาติของปัญหาการวางแผนที่สถานะเริ่มต้นไม่เป็นที่รู้จักอย่างสมบูรณ์ จึงมีการพัฒนาส่วนขยายของ STRIPS เพื่อจัดการกับสถานะเริ่มต้นที่ทราบเพียงบางส่วน ${\displaystyle I}$

ลิงตัวหนึ่งอยู่ที่ตำแหน่ง A ในห้องทดลอง มีกล่องอยู่ที่ตำแหน่ง C ลิงตัวนี้ต้องการกล้วยที่ห้อยลงมาจากเพดานที่ตำแหน่ง B แต่ต้องขยับกล่องและปีนขึ้นไปบนกล่องเพื่อเอื้อมถึงกล้วย

สถานะเริ่มต้น: ที่ (A), ระดับ (ต่ำ), กล่องที่ (C), กล้วยที่ (B) เป้าหมาย: มี (กล้วย) 

การดำเนินการ: // เคลื่อนที่จาก X ไปยัง Y _Move(X, Y)_ เงื่อนไขเบื้องต้น: ที่(X), ระดับ(ต่ำ) เงื่อนไขหลังการดำเนินการ: ไม่ใช่ At(X), At(Y) // ปีนขึ้นไปบนกล่อง _ปีนขึ้น(ตำแหน่ง)_ เงื่อนไขเบื้องต้น: ที่ (ตำแหน่ง), กล่องที่ (ตำแหน่ง), ระดับ (ต่ำ) เงื่อนไขหลังการดำเนินการ: ระดับ (สูง) ไม่ใช่ระดับ (ต่ำ) // ปีนลงจากกล่อง _ปีนลง(ตำแหน่ง)_ เงื่อนไขเบื้องต้น: ที่ (ตำแหน่ง), กล่องที่ (ตำแหน่ง), ระดับ (สูง) เงื่อนไขหลังการดำเนินการ: ระดับ (ต่ำ) ไม่ใช่ระดับ (สูง) // ย้ายลิงและกล่องจากแกน X ไปยังแกน Y _MoveBox(X, Y)_ เงื่อนไขเบื้องต้น: At(X), BoxAt(X), Level(low) เงื่อนไขหลังการดำเนินการ: BoxAt(Y), ไม่ใช่ BoxAt(X), At(Y), ไม่ใช่ At(X) // เอากล้วยไป _TakeBananas(Location)_ เงื่อนไขเบื้องต้น: ที่ (ตำแหน่ง), กล้วยที่ (ตำแหน่ง), ระดับ (สูง) เงื่อนไขหลังการดำเนินการ: มี (กล้วย) 

การตัดสินใจว่ามีแผนใด ๆ สำหรับอินสแตนซ์ STRIPS เชิงประพจน์หรือไม่นั้นเป็นปัญหาPSPACE-completeข้อจำกัดต่าง ๆ สามารถนำมาใช้เพื่อตัดสินใจว่ามีแผนอยู่หรือไม่ในเวลาพหุนามหรืออย่างน้อยก็ทำให้เป็นปัญหาNP-complete ^{[ 2 ]}

ในปัญหาลิงกับกล้วยหุ่นยนต์ลิงต้องดำเนินการตามลำดับเพื่อไปถึงกล้วยที่อยู่บนเพดาน การกระทำเพียงครั้งเดียวทำให้เกิดการเปลี่ยนแปลงเล็กน้อยในเกม เพื่อลดความซับซ้อนของกระบวนการวางแผน จึงควรคิดค้นการกระทำเชิงนามธรรม ซึ่งไม่มีอยู่ในคำอธิบายกฎปกติ^{[ 3 ]}การกระทำระดับสูงประกอบด้วยการกระทำระดับต่ำและสามารถบรรลุเป้าหมายระดับสูงได้ ข้อดีคือความซับซ้อนในการคำนวณต่ำกว่า และตัวแก้ปัญหาสามารถวางแผนงานที่ยาวขึ้นได้

การระบุตัวดำเนินการมาโครใหม่สำหรับโดเมนสามารถทำได้ด้วย การ เขียนโปรแกรมเชิงพันธุกรรม^{[ 4 ]}แนวคิดคือ ไม่ใช่การวางแผนโดเมนเอง แต่ในขั้นตอนก่อนหน้า จะมีการสร้างฮิวริสติกส์ที่ช่วยให้สามารถแก้ปัญหาโดเมนได้เร็วขึ้นมาก ในบริบทของการเรียนรู้แบบเสริมแรงตัวดำเนินการมาโครเรียกว่าตัวเลือก คล้ายกับคำจำกัดความภายในการวางแผน AI แนวคิดคือ การจัดเตรียมการสรุปเชิงเวลา (ครอบคลุมช่วงเวลาที่ยาวนานขึ้น) และแก้ไขสถานะของเกมโดยตรงในเลเยอร์ที่สูงกว่า^{[ 5 ]}

• ภาษาอธิบายการกระทำ (ADL)
• การวางแผนอัตโนมัติ
• เครือข่ายงานแบบลำดับชั้น
• ภาษากำหนดขอบเขตการวางแผน (PDDL)
• ความผิดปกติของซัสส์แมน

• C. Bäckström และ B. Nebel (1995). ผลลัพธ์ความซับซ้อนสำหรับการวางแผน SAS+ ปัญญาประดิษฐ์เชิงคำนวณ 11:625-656
• T. Bylander (1991). ผลลัพธ์ความซับซ้อนสำหรับการวางแผน ในรายงานการประชุมนานาชาติร่วมครั้งที่สิบสองว่าด้วยปัญญาประดิษฐ์ (IJCAI'91)หน้า 274-279
• Russell, Stuart J. ; Norvig, Peter (2003), ปัญญาประดิษฐ์: แนวทางสมัยใหม่ (ฉบับที่ 2), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2