การวางแผนและการจัดตารางเวลาเชิงเวลา

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมการวางแผนและการจัดตารางเวลาโดยมีเวลาและทรัพยากรที่ชัดเจน: การกระทำที่มีระยะเวลา การเกิดขึ้นพร้อมกันและข้อจำกัดเชิงเวลา การนำเสนอและการแก้ปัญหาเครือข่ายข้อจำกัดเชิงเวลา (เช่น ปัญหาเชิงเวลาอย่างง่าย) และพีชคณิตช่วงเวลาของอัลเลน (Allen's interval algebra) และการบูรณาการการวางแผนกับการจัดตารางเวลากิจกรรมที่มีข้อจำกัดด้านทรัพยากร โดยจะกล่าวถึงวิธีการให้เหตุผลเกี่ยวกับความเป็นไปได้ของเวลาและทรัพยากรควบคู่ไปกับการเลือกการกระทำ การวางแผนแบบคลาสสิกที่ปราศจากทรัพยากรอย่างแท้จริงจะกล่าวถึงในหัวข้อที่เกี่ยวข้อง

Core questions

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

Key concepts

• การกระทำที่มีระยะเวลา
• การเกิดขึ้นพร้อมกันและการทับซ้อน
• ข้อจำกัดเชิงเวลา
• ปัญหาเชิงเวลาอย่างง่าย
• พีชคณิตช่วงเวลาของอัลเลน
• ข้อจำกัดด้านทรัพยากร
• การจัดตารางเวลา
• กำหนดเวลาและระยะเวลาดำเนินการทั้งหมด

Key theories

เครือข่ายข้อจำกัดเชิงเวลา

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

พีชคณิตช่วงเวลาสำหรับเวลาเชิงคุณภาพ

พีชคณิตช่วงเวลาของอัลเลนรวบรวมความสัมพันธ์เชิงคุณภาพที่เป็นไปได้ระหว่างช่วงเวลา (ก่อน, ระหว่าง, ทับซ้อน, และอื่นๆ) และสนับสนุนการให้เหตุผลเกี่ยวกับความรู้เชิงเวลาเมื่อเวลาที่แน่นอนไม่เป็นที่ทราบ

การบูรณาการการวางแผนกับการจัดตารางเวลา

ปัญหาที่สมจริงต้องมีการเลือกการกระทำและกำหนดเวลาและทรัพยากรพร้อมกัน; ทฤษฎีการวางแผนอัตโนมัติถือว่าการกระทำที่มีระยะเวลา การเกิดขึ้นพร้อมกัน และข้อจำกัดด้านทรัพยากรเป็นการขยายที่เชื่อมโยงการเลือกการกระทำกับการจัดตารางเวลาตามข้อจำกัด

Clinical relevance

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

History

การให้เหตุผลเชิงเวลาเชิงคุณภาพได้รับการกำหนดเป็นทางการโดยพีชคณิตช่วงเวลาของอัลเลน (Allen's interval algebra) (ค.ศ. 1983) และเครือข่ายข้อจำกัดเชิงเวลาเชิงปริมาณโดย Dechter, Meiri, และ Pearl (ค.ศ. 1991) รากฐานเหล่านี้ ร่วมกับแบบจำลองการกระทำที่มีระยะเวลาที่เพิ่มเข้ามาใน PDDL ในช่วงต้นทศวรรษ 2000 ทำให้เกิดเครื่องมือวางแผนเชิงเวลาที่ใช้ในการประยุกต์ใช้ เช่น การควบคุมยานอวกาศอัตโนมัติ

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

ความแตกต่างระหว่างการวางแผนและการจัดตารางเวลาคืออะไร?

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

ปัญหาเชิงเวลาอย่างง่ายคืออะไร?

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