Lập kế hoạch tự động
Lập kế hoạch tự động là một nhánh của trí tuệ nhân tạo liên quan đến việc tính toán các chuỗi hành động nhằm chuyển đổi trạng thái ban đầu của thế giới thành trạng thái mục tiêu mong muốn, dựa trên mô tả hình thức về các hành động có sẵn.
Definition
Lập kế hoạch tự động là việc tính toán một kế hoạch—một tập hợp các hành động được sắp xếp (hoặc sắp xếp một phần)—mà có thể chứng minh được là đạt được một mục tiêu từ trạng thái ban đầu, dựa trên một mô hình về cách mỗi hành động thay đổi trạng thái của thế giới.
Scope
Lĩnh vực này bao gồm việc biểu diễn các vấn đề lập kế hoạch (trạng thái, hành động với điều kiện tiên quyết và hiệu ứng, mục tiêu) và các thuật toán giải quyết chúng: lập kế hoạch cổ điển trong các miền xác định, có thể quan sát đầy đủ, các phương pháp đồ thị lập kế hoạch và tìm kiếm heuristic, lập kế hoạch mạng lưới tác vụ phân cấp, và mở rộng sang thời gian, tài nguyên và lập lịch. Nó xử lý các hình thức tiêu chuẩn như STRIPS và PDDL và độ phức tạp của việc lập kế hoạch. Lập kế hoạch trong điều kiện bất định xác suất kết nối với suy luận trong điều kiện bất định, và việc học các mô hình hành động hoặc chính sách từ dữ liệu thuộc về phân ngành học máy.
Sub-topics
Core questions
- Làm thế nào để các hành động, trạng thái và mục tiêu được biểu diễn đủ gọn để mô tả các miền lớn?
- Làm thế nào để vấn đề lập kế hoạch được tìm kiếm hiệu quả mặc dù không gian trạng thái lớn theo cấp số nhân?
- Làm thế nào để các heuristic chấp nhận được và có thông tin được suy ra tự động từ mô tả miền?
- Làm thế nào để các kế hoạch có thể được cấu trúc theo phân cấp, và làm thế nào để các ràng buộc về thời gian và tài nguyên được tích hợp?
Key concepts
- trạng thái, hành động, mục tiêu
- điều kiện tiên quyết và hiệu ứng
- STRIPS và PDDL
- tìm kiếm không gian trạng thái tiến và lùi
- đồ thị lập kế hoạch
- heuristic độc lập miền
- mạng lưới tác vụ phân cấp
- lập kế hoạch và lập lịch theo thời gian
Key theories
- Biểu diễn hành động STRIPS
- Hình thức STRIPS mô tả các hành động bằng các điều kiện tiên quyết và các hiệu ứng thêm/xóa trên một tập hợp các mệnh đề, cung cấp một biểu diễn gọn gàng, có yếu tố hóa giúp việc lập kế hoạch trở thành một tìm kiếm thông qua các trạng thái biểu tượng thay vì liệt kê các trạng thái thế giới rõ ràng.
- Tìm kiếm heuristic độc lập miền cho lập kế hoạch
- Các công cụ lập kế hoạch hiện đại coi lập kế hoạch là tìm kiếm heuristic và tự động suy ra các heuristic từ mô tả vấn đề, ví dụ bằng cách bỏ qua các hiệu ứng xóa hoặc khai thác cấu trúc nhân quả, cho phép đạt được hiệu suất tổng quát mạnh mẽ.
- Lập kế hoạch như một hệ thống phân cấp các lớp vấn đề
- Lập kế hoạch bao gồm một phổ từ lập kế hoạch xác định cổ điển đến các biến thể phân cấp, theo thời gian và bị ràng buộc tài nguyên, mỗi loại có các biểu diễn và độ phức tạp đặc trưng, được tổ chức trong lý thuyết tiêu chuẩn về lập kế hoạch tự động.
Clinical relevance
Lập kế hoạch tự động được ứng dụng trong robot và hệ thống tự hành, hoạt động tàu vũ trụ và nhiệm vụ, hậu cần và chuỗi cung ứng, sản xuất, và tạo trò chơi và câu chuyện; các công cụ lập kế hoạch được phát triển từ các kỹ thuật này đã điều khiển các tàu vũ trụ tự hành thực tế và điều phối các quy trình làm việc phức tạp.
History
Lập kế hoạch tự động bắt đầu với STRIPS cho robot Shakey tại SRI vào khoảng năm 1971, định hình lập kế hoạch như một quá trình chứng minh định lý dựa trên mô tả hành động. Lĩnh vực này đã phát triển thông qua lập kế hoạch thứ tự một phần, bước đột phá Graphplan (1995), và sự trỗi dậy của các công cụ lập kế hoạch tìm kiếm heuristic độc lập miền nhanh chóng và tiêu chuẩn PDDL từ cuối những năm 1990 trở đi, được theo dõi thông qua các Cuộc thi Lập kế hoạch Quốc tế.
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
- Lập kế hoạch tự động khác với tìm kiếm tổng quát như thế nào?
- Lập kế hoạch tự động là một dạng tìm kiếm, nhưng nó hoạt động từ một mô tả khai báo, có yếu tố hóa về các hành động (điều kiện tiên quyết và hiệu ứng) thay vì một hàm kế nhiệm không rõ ràng. Cấu trúc này cho phép các công cụ lập kế hoạch tự động suy ra các heuristic và suy luận về những hành động nào có liên quan, điều mà tìm kiếm chung không thể làm được.
- PDDL là gì?
- PDDL, Ngôn ngữ Định nghĩa Miền Lập kế hoạch, là một ngôn ngữ tiêu chuẩn để mô tả các miền và vấn đề lập kế hoạch—các đối tượng, vị từ, hành động, trạng thái ban đầu và mục tiêu. Nó cho phép so sánh các công cụ lập kế hoạch độc lập miền trên một tiêu chuẩn chung, như trong các Cuộc thi Lập kế hoạch Quốc tế.