การวางแผนแบบคลาสสิกและ STRIPS

การวางแผนแบบคลาสสิกเป็นการแก้ปัญหาการค้นหาลำดับของการกระทำเพื่อบรรลุเป้าหมายในสภาพแวดล้อมที่เป็นไปตามที่กำหนด สามารถสังเกตได้ทั้งหมด และคงที่ โดยใช้การนำเสนอการกระทำแบบแยกส่วนตามสไตล์ STRIPS โดยมีเงื่อนไขเบื้องต้นและผลกระทบ

Definition

การวางแผนแบบคลาสสิกเป็นการค้นหาลำดับของการกระทำที่เป็นไปตามที่กำหนด ซึ่งเปลี่ยนสถานะเริ่มต้นที่ทราบทั้งหมดให้เป็นสถานะที่บรรลุเป้าหมาย โดยที่การกระทำแต่ละอย่างจะอธิบายด้วยเงื่อนไขที่ต้องเป็นจริงเพื่อให้สามารถนำไปใช้ได้ และการเปลี่ยนแปลงที่เกิดขึ้น

Scope

หัวข้อนี้ครอบคลุมถึงแบบจำลองการวางแผนแบบคลาสสิกและข้อสมมติฐาน (การกระทำที่เป็นไปตามที่กำหนด, การสังเกตได้ทั้งหมด, ตัวแทนเดี่ยว, เวลาที่เป็นอะตอม), การนำเสนอสถานะและการกระทำแบบ STRIPS และ ADL/PDDL, วิธีการแก้ปัญหาพื้นฐานของการค้นหาพื้นที่สถานะแบบเดินหน้า (progression) และถอยหลัง (regression) และการวางแผนแบบลำดับบางส่วน, และความซับซ้อนในการคำนวณของการวางแผนเชิงประพจน์ การชี้นำด้วยฮิวริสติกและกราฟการวางแผนจะกล่าวถึงในหัวข้อที่เกี่ยวข้อง และตัวแปรที่ไม่เป็นไปตามที่กำหนดหรือแบบความน่าจะเป็นจะอยู่นอกเหนือขอบเขต

Core questions

• ข้อสมมติฐานใดบ้างที่กำหนดแบบจำลองการวางแผนแบบคลาสสิก และเหมาะสมเมื่อใด?
• การนำเสนอแบบ STRIPS แยกสถานะออกเป็นประพจน์และการกระทำออกเป็นเงื่อนไขเบื้องต้นและผลกระทบการเพิ่ม/ลบได้อย่างไร?
• การค้นหาแบบเดินหน้าและการค้นหาแบบถอยหลังแตกต่างกันอย่างไรในฐานะกลยุทธ์การวางแผน?
• การวางแผนแบบคลาสสิกโดยทั่วไปมีความยากในการคำนวณเพียงใด?

Key concepts

• แบบจำลองที่เป็นไปตามที่กำหนดและสังเกตได้ทั้งหมด
• เงื่อนไขเบื้องต้นและผลกระทบของ STRIPS
• รายการเพิ่มและลบ
• PDDL และ ADL
• การค้นหาแบบเดินหน้า (progression)
• การค้นหาแบบถอยหลัง (regression)
• การวางแผนแบบลำดับบางส่วน
• ความซับซ้อนของการมีอยู่ของแผน

Key theories

การนำเสนอแบบ STRIPS

STRIPS อธิบายโลกในฐานะชุดของประพจน์ที่เป็นจริง และการกระทำแต่ละอย่างด้วยรายการเงื่อนไขเบื้องต้นพร้อมรายการเพิ่มและลบ ดังนั้นการใช้การกระทำจึงเป็นการเพิ่มและลบประพจน์เท่านั้น แบบจำลองแบบแยกส่วนนี้เป็นรากฐานของนักวางแผนแบบคลาสสิกเกือบทั้งหมด

การค้นหาแบบเดินหน้าและถอยหลัง

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

ความซับซ้อนของการวางแผน

การตัดสินใจว่าแผน STRIPS เชิงประพจน์มีอยู่หรือไม่นั้นเป็น PSPACE-complete โดยทั่วไป ซึ่งอธิบายอย่างเป็นทางการว่าทำไมการวางแผนจึงเป็นเรื่องยาก และกระตุ้นให้เกิดวิธีการแบบฮิวริสติกและโครงสร้างเพื่อให้สามารถนำไปใช้ได้จริง

Clinical relevance

การนำเสนอการวางแผนแบบคลาสสิกเป็นส่วนเชื่อมต่อทั่วไปสำหรับการวางแผนงานหุ่นยนต์ การประกอบอัตโนมัติและโลจิสติกส์ และการประยุกต์ใช้ใดๆ ที่การกระทำที่เป็นไปตามที่กำหนดจะต้องถูกจัดลำดับเพื่อบรรลุเป้าหมาย นักวางแผนแบบคลาสสิกที่ใช้ PDDL เป็นเครื่องมือหลักในสาขานี้และในการแข่งขัน International Planning Competitions

History

STRIPS ได้รับการพัฒนาที่ SRI ประมาณปี 1971 เพื่อควบคุมหุ่นยนต์ Shakey โดยนำเสนอแบบจำลองการกระทำแบบเงื่อนไขเบื้องต้น/ผลกระทบที่กำหนดการวางแผนแบบคลาสสิก การวางแผนแบบลำดับบางส่วนพัฒนาขึ้นในช่วงทศวรรษ 1970-80 Bylander ได้กำหนด PSPACE-completeness ของการวางแผนเชิงประพจน์ในปี 1994 และมาตรฐาน PDDL ได้รวมเกณฑ์มาตรฐานของสาขานี้ในภายหลัง

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

ข้อสมมติฐานของการวางแผนแบบคลาสสิกคืออะไร?

การวางแผนแบบคลาสสิกสมมติว่ามีตัวแทนเดี่ยวที่กระทำในสภาพแวดล้อมที่เป็นไปตามที่กำหนด สังเกตได้ทั้งหมด และคงที่ โดยมีการกระทำที่ใช้เวลาหนึ่งหน่วยและสถานะเริ่มต้นที่ทราบทั้งหมด การผ่อนคลายข้อสมมติฐานใดๆ เหล่านี้ เช่น การอนุญาตให้มีความไม่แน่นอนหรือการทำงานพร้อมกัน จะนำไปสู่ปัญหาการวางแผนที่ซับซ้อนมากขึ้นนอกเหนือจากแบบจำลองคลาสสิก

รายการเพิ่มและรายการลบของ STRIPS หมายถึงอะไร?

เมื่อมีการใช้การกระทำ STRIPS ประพจน์ในรายการเพิ่มจะกลายเป็นจริง และประพจน์ในรายการลบจะกลายเป็นเท็จ ประพจน์อื่นๆ ทั้งหมดจะไม่เปลี่ยนแปลง กฎการอัปเดตที่เรียบง่ายนี้ทำให้ STRIPS เป็นการนำเสนอที่กระชับและสะดวกในการคำนวณว่าการกระทำเปลี่ยนแปลงโลกอย่างไร