การวางแผนอัตโนมัติ
การวางแผนอัตโนมัติเป็นสาขาหนึ่งของปัญญาประดิษฐ์ที่เกี่ยวข้องกับการคำนวณลำดับของการกระทำที่เปลี่ยนสถานะเริ่มต้นของโลกไปสู่สถานะเป้าหมายที่ต้องการ โดยมีคำอธิบายที่เป็นทางการของการกระทำที่มีอยู่
Definition
การวางแผนอัตโนมัติคือการคำนวณแผน — ชุดของการกระทำที่จัดลำดับ (หรือจัดลำดับบางส่วน) — ที่สามารถพิสูจน์ได้ว่าบรรลุเป้าหมายจากสถานะเริ่มต้น โดยมีแบบจำลองว่าการกระทำแต่ละอย่างเปลี่ยนแปลงสถานะของโลกอย่างไร
Scope
ขอบเขตนี้ครอบคลุมการนำเสนอของปัญหาการวางแผน (สถานะ, การกระทำที่มีเงื่อนไขเบื้องต้นและผลกระทบ, เป้าหมาย) และอัลกอริทึมที่ใช้ในการแก้ปัญหาเหล่านั้น: การวางแผนแบบคลาสสิกในโดเมนที่กำหนดได้และสังเกตได้ทั้งหมด, วิธีการกราฟการวางแผนและการค้นหาแบบฮิวริสติก, การวางแผนเครือข่ายงานแบบลำดับชั้น, และการขยายไปสู่เวลา, ทรัพยากร, และการจัดตารางเวลา. ครอบคลุมรูปแบบมาตรฐานเช่น STRIPS และ PDDL และความซับซ้อนของการวางแผน. การวางแผนภายใต้ความไม่แน่นอนของความน่าจะเป็นเชื่อมโยงกับการให้เหตุผลภายใต้ความไม่แน่นอน, และการเรียนรู้แบบจำลองการกระทำหรือนโยบายจากข้อมูลเป็นส่วนหนึ่งของสาขาย่อยการเรียนรู้ของเครื่องจักร.
Sub-topics
Core questions
- การกระทำ สถานะ และเป้าหมายถูกนำเสนออย่างกระชับเพียงพอที่จะอธิบายโดเมนขนาดใหญ่ได้อย่างไร?
- ปัญหาการวางแผนถูกค้นหาอย่างมีประสิทธิภาพได้อย่างไร แม้จะมีปริภูมิสถานะที่ใหญ่มากแบบเอ็กซ์โพเนนเชียล?
- ฮิวริสติกที่ยอมรับได้และให้ข้อมูลถูกสร้างขึ้นโดยอัตโนมัติจากคำอธิบายโดเมนได้อย่างไร?
- แผนสามารถจัดโครงสร้างเป็นลำดับชั้นได้อย่างไร และข้อจำกัดด้านเวลาและทรัพยากรถูกรวมเข้าด้วยกันได้อย่างไร?
Key concepts
- สถานะ, การกระทำ, เป้าหมาย
- เงื่อนไขเบื้องต้นและผลกระทบ
- STRIPS และ PDDL
- การค้นหาปริภูมิสถานะแบบเดินหน้าและถอยหลัง
- กราฟการวางแผน
- ฮิวริสติกที่ไม่ขึ้นกับโดเมน
- เครือข่ายงานแบบลำดับชั้น
- การวางแผนเชิงเวลาและการจัดตารางเวลา
Key theories
- การนำเสนอการกระทำแบบ STRIPS
- รูปแบบ STRIPS อธิบายการกระทำด้วยเงื่อนไขเบื้องต้นและผลกระทบการเพิ่ม/ลบเหนือชุดของข้อเสนอ ซึ่งให้การนำเสนอที่กระชับและแยกส่วนที่ทำให้การวางแผนเป็นการค้นหาผ่านสถานะเชิงสัญลักษณ์ แทนที่จะเป็นการแจกแจงสถานะโลกที่ชัดเจน
- การค้นหาแบบฮิวริสติกที่ไม่ขึ้นกับโดเมนสำหรับการวางแผน
- ผู้วางแผนสมัยใหม่กำหนดให้การวางแผนเป็นการค้นหาแบบฮิวริสติกและสร้างฮิวริสติกโดยอัตโนมัติจากคำอธิบายปัญหา ตัวอย่างเช่น โดยการละเลยผลกระทบการลบหรือการใช้ประโยชน์จากโครงสร้างเชิงสาเหตุ ซึ่งช่วยให้ได้ประสิทธิภาพทั่วไปที่แข็งแกร่ง
- การวางแผนเป็นลำดับชั้นของประเภทปัญหา
- การวางแผนครอบคลุมสเปกตรัมตั้งแต่การวางแผนแบบกำหนดคลาสสิกไปจนถึงรูปแบบลำดับชั้น เชิงเวลา และมีข้อจำกัดด้านทรัพยากร ซึ่งแต่ละรูปแบบมีการนำเสนอและความซับซ้อนที่เป็นลักษณะเฉพาะ จัดระเบียบในทฤษฎีมาตรฐานของการวางแผนอัตโนมัติ
Clinical relevance
การวางแผนอัตโนมัติถูกนำไปใช้ในหุ่นยนต์และระบบอัตโนมัติ, การปฏิบัติการยานอวกาศและภารกิจ, โลจิสติกส์และห่วงโซ่อุปทาน, การผลิต, และการสร้างเกมและเรื่องเล่า; ผู้วางแผนที่ได้มาจากเทคนิคเหล่านี้ได้ควบคุมยานอวกาศอัตโนมัติจริงและประสานงานเวิร์กโฟลว์ที่ซับซ้อน
History
การวางแผนอัตโนมัติเริ่มต้นด้วย STRIPS สำหรับหุ่นยนต์ Shakey ที่ SRI ประมาณปี 1971 โดยกำหนดให้การวางแผนเป็นการพิสูจน์ทฤษฎีจากคำอธิบายการกระทำ. สาขาได้พัฒนาผ่านการวางแผนแบบลำดับบางส่วน, ความก้าวหน้าของ Graphplan (1995), และการเพิ่มขึ้นของผู้วางแผนการค้นหาแบบฮิวริสติกที่ไม่ขึ้นกับโดเมนที่รวดเร็วและมาตรฐาน PDDL ตั้งแต่ปลายทศวรรษ 1990 เป็นต้นไป ซึ่งติดตามผ่านการแข่งขันการวางแผนนานาชาติ.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- การวางแผนอัตโนมัติแตกต่างจากการค้นหาทั่วไปอย่างไร?
- การวางแผนอัตโนมัติเป็นรูปแบบหนึ่งของการค้นหา แต่ทำงานจากคำอธิบายการกระทำที่เป็นการประกาศและแยกส่วน (เงื่อนไขเบื้องต้นและผลกระทบ) แทนที่จะเป็นฟังก์ชันผู้สืบทอดที่ไม่ชัดเจน โครงสร้างนี้ช่วยให้ผู้วางแผนสามารถสร้างฮิวริสติกและให้เหตุผลเกี่ยวกับการกระทำที่เกี่ยวข้องได้โดยอัตโนมัติ ซึ่งการค้นหาทั่วไปไม่สามารถทำได้
- PDDL คืออะไร?
- PDDL หรือ Planning Domain Definition Language เป็นภาษามาตรฐานสำหรับอธิบายโดเมนและปัญหาการวางแผน — วัตถุ, เพรดิเคต, การกระทำ, สถานะเริ่มต้น และเป้าหมาย ช่วยให้ผู้วางแผนที่ไม่ขึ้นกับโดเมนสามารถเปรียบเทียบกันได้บนเกณฑ์มาตรฐานทั่วไป เช่นในการแข่งขันการวางแผนนานาชาติ