Lập kế hoạch và điều độ thời gian

Lập kế hoạch và điều độ thời gian mở rộng việc lập kế hoạch để xử lý các hành động cần thời gian, có thể chạy đồng thời và tiêu thụ tài nguyên hạn chế, tạo ra các kế hoạch không chỉ xác định phải làm gì mà còn xác định khi nào phải làm.

Definition

Lập kế hoạch thời gian tạo ra một kế hoạch trong đó các hành động có thời lượng và có thể chồng chéo, tuân theo các ràng buộc về thời gian và tài nguyên; điều độ gán thời gian bắt đầu (và tài nguyên) cho một tập hợp các hoạt động sao cho tất cả các ràng buộc, chẳng hạn như thứ tự, thời hạn và năng lực, được thỏa mãn.

Scope

Chủ đề này bao gồm việc lập kế hoạch và điều độ với thời gian và tài nguyên rõ ràng: các hành động có thời lượng, tính đồng thời và các ràng buộc về thời gian, việc biểu diễn và giải các mạng ràng buộc thời gian (chẳng hạn như bài toán thời gian đơn giản) và đại số khoảng của Allen, cũng như sự tích hợp giữa lập kế hoạch với điều độ các hoạt động bị ràng buộc tài nguyên. Nó đề cập đến cách tính khả thi về thời gian và tài nguyên được suy luận cùng với việc lựa chọn hành động. Lập kế hoạch cổ điển thuần túy không có tài nguyên được đề cập trong các chủ đề liên quan.

Core questions

• Các hành động có thời lượng và điều kiện bắt đầu và kết thúc của chúng được biểu diễn như thế nào?
• Các ràng buộc thời gian giữa các sự kiện được mô hình hóa và kiểm tra tính nhất quán như thế nào?
• Các tài nguyên hạn chế được phân bổ giữa các hoạt động đồng thời như thế nào?
• Việc lập kế hoạch (quyết định hành động nào) và điều độ (quyết định khi nào) được kết hợp hoặc tách rời như thế nào?

Key concepts

• các hành động có thời lượng
• tính đồng thời và chồng chéo
• các ràng buộc thời gian
• bài toán thời gian đơn giản
• đại số khoảng của Allen
• các ràng buộc tài nguyên
• điều độ
• thời hạn và thời gian hoàn thành

Key theories

Mạng ràng buộc thời gian

Các ràng buộc thời gian định lượng giữa các điểm thời gian có thể được biểu diễn dưới dạng một mạng lưới mà tính nhất quán và các giới hạn chặt chẽ nhất của nó được tính toán hiệu quả cho bài toán thời gian đơn giản, cung cấp xương sống lý luận thời gian cho nhiều công cụ lập kế hoạch và điều độ.

Đại số khoảng cho thời gian định tính

Đại số khoảng của Allen nắm bắt các mối quan hệ định tính có thể có giữa các khoảng thời gian (trước, trong, chồng chéo, v.v.) và hỗ trợ lý luận về kiến thức thời gian khi thời gian chính xác không được biết.

Tích hợp lập kế hoạch với điều độ

Các vấn đề thực tế đòi hỏi phải lựa chọn hành động và gán thời gian và tài nguyên cho chúng cùng lúc; lý thuyết lập kế hoạch tự động coi các hành động có thời lượng, tính đồng thời và các ràng buộc tài nguyên là các phần mở rộng kết hợp lựa chọn hành động với điều độ dựa trên ràng buộc.

Clinical relevance

Lập kế hoạch và điều độ thời gian là rất cần thiết trong các hoạt động của tàu vũ trụ và robot tự hành, lập kế hoạch sản xuất và dự án, lập kế hoạch vận tải và nhân sự, và bất kỳ môi trường nào mà các hoạt động có thời gian, đồng thời, bị giới hạn tài nguyên phải được phối hợp; các hệ thống như vậy đã lập kế hoạch hoạt động cho các nhiệm vụ không gian thực tế.

History

Lý luận thời gian định tính được Allen hình thức hóa bằng đại số khoảng (1983), và các mạng ràng buộc thời gian định lượng được Dechter, Meiri và Pearl hình thức hóa (1991). Những nền tảng này, cùng với các mô hình hành động có thời lượng được thêm vào PDDL vào đầu những năm 2000, đã cho phép các công cụ lập kế hoạch thời gian được sử dụng trong các ứng dụng như kiểm soát tàu vũ trụ tự hành.

Key figures

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

Seminal works

• dechter1991
• allen1983

Frequently asked questions

Sự khác biệt giữa lập kế hoạch và điều độ là gì?

Lập kế hoạch quyết định hành động nào cần thực hiện để đạt được mục tiêu, trong khi điều độ quyết định khi nào các hành động đó xảy ra và chúng sử dụng tài nguyên nào, với các ràng buộc về thứ tự và năng lực. Nhiều vấn đề thực tế đòi hỏi cả hai, và lập kế hoạch thời gian tích hợp lựa chọn hành động với lý luận về thời gian và tài nguyên.

Bài toán thời gian đơn giản là gì?

Bài toán thời gian đơn giản là một mạng ràng buộc thời gian trong đó mỗi ràng buộc giới hạn sự khác biệt giữa hai điểm thời gian bằng một khoảng. Tính nhất quán của nó và các giới hạn ngụ ý chặt chẽ nhất có thể được tính toán hiệu quả, điều này làm cho nó trở thành một cốt lõi thực tế cho lý luận thời gian trong các công cụ lập kế hoạch và điều độ.