กราฟการวางแผนและฮิวริสติกส์

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

Definition

กราฟการวางแผนคือโครงสร้างแบบชั้นที่สลับระดับของข้อเสนอและการกระทำกับข้อจำกัด mutex เพื่อประมาณการเข้าถึง; ฮิวริสติกส์การวางแผนคือฟังก์ชัน ซึ่งมักจะคำนวณจากโครงสร้างดังกล่าวหรือจากปัญหาที่ผ่อนคลายการลบ ซึ่งประมาณค่าใช้จ่ายในการเข้าถึงเป้าหมายจากสถานะหนึ่ง

Scope

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

Core questions

• กราฟการวางแผนแสดงข้อเสนอและการกระทำที่เข้าถึงได้ทีละระดับได้อย่างไร?
• ความสัมพันธ์แบบ mutex คืออะไร และมันจับความไม่เข้ากันระหว่างข้อเท็จจริงและการกระทำได้อย่างไร?
• การผ่อนคลายการลบถูกนำมาใช้เพื่อสร้างฮิวริสติกส์การวางแผนที่ยอมรับได้หรือให้ข้อมูลได้อย่างไร?
• ฮิวริสติกส์เหล่านี้เปลี่ยนการวางแผนให้เป็นการค้นหาแบบฮิวริสติกส์ที่มีประสิทธิภาพได้อย่างไร?

Key concepts

• กราฟการวางแผน
• ระดับของข้อเสนอและการกระทำ
• การกีดกันร่วมกัน (mutex)
• Graphplan
• การผ่อนคลายการลบ
• ฮิวริสติกส์ h-max และ h-add
• ฮิวริสติกส์ FF และแผนที่ผ่อนคลาย
• การค้นหาแบบฮิวริสติกส์ไปข้างหน้า

Key theories

กราฟการวางแผนและ Graphplan

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

ฮิวริสติกส์การผ่อนคลายการลบ

การละเลยผลกระทบจากการลบของการกระทำทำให้เกิดปัญหาการวางแผนที่ผ่อนคลายซึ่งง่ายต่อการแก้ไขมาก ค่าใช้จ่ายในการแก้ไขการผ่อนคลายนี้ให้ฮิวริสติกส์ที่มีข้อมูล ซึ่งมักจะยอมรับได้ (เช่น h-max และ h-add และฮิวริสติกส์ FF) ซึ่งนำทางการค้นหาไปข้างหน้า

การวางแผนการค้นหาแบบฮิวริสติกส์

ตัววางแผนแบบคลาสสิกที่ทันสมัยที่สุดรวมฮิวริสติกส์ที่ได้มาโดยอัตโนมัติกับการค้นหาแบบ best-first หรือ greedy และการปรับปรุงเช่น preferred operators ซึ่งทำให้ได้ประสิทธิภาพทั่วไปที่แข็งแกร่งในโดเมนที่หลากหลาย

Clinical relevance

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

History

Graphplan ของ Blum และ Furst (1995, ฉบับวารสาร 1997) ได้นำเสนอกราฟการวางแผนและปฏิวัติความเร็วในการวางแผน ช่วงปลายทศวรรษ 1990 และ 2000 ได้เห็นการเพิ่มขึ้นของฮิวริสติกส์การผ่อนคลายการลบ โดยมีตัววางแผน FF (Hoffmann และ Nebel, 2001) และต่อมา Fast Downward (Helmert, 2006) ได้สร้างการค้นหาแบบฮิวริสติกส์ไปข้างหน้าให้เป็นแนวทางที่โดดเด่น

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

Mutex ในกราฟการวางแผนคืออะไร?

ความสัมพันธ์แบบ mutex (mutual exclusion) จะทำเครื่องหมายข้อเสนอสองข้อหรือการกระทำสองอย่างที่ไม่สามารถเกิดขึ้นพร้อมกันหรือนำไปใช้ในระดับเดียวกันได้ เช่น เพราะการกระทำหนึ่งลบเงื่อนไขเบื้องต้นของอีกการกระทำหนึ่ง Mutex ทำให้กราฟการวางแผนเป็นการประมาณการเข้าถึงที่แท้จริงที่กระชับยิ่งขึ้น

เหตุใดการละเลยผลกระทบจากการลบจึงให้ฮิวริสติกส์ที่มีประโยชน์?

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