Lập kế hoạch HTN khác với lập kế hoạch cổ điển như thế nào?

Lập kế hoạch cổ điển tìm kiếm bất kỳ chuỗi hành động nào đạt đến trạng thái mục tiêu, chỉ sử dụng các điều kiện tiên quyết và hiệu ứng của hành động. Lập kế hoạch HTN thay vào đó bắt đầu từ các tác vụ cần hoàn thành và phân tách chúng bằng các phương pháp mã hóa cách thức, theo thủ tục, các tác vụ đó thường được thực hiện, vì vậy nó dựa vào kiến thức miền phong phú hơn.

Tại sao lập kế hoạch HTN có thể không quyết định được?

Bởi vì các phương pháp có thể phân tách một tác vụ phức hợp thành các mạng lưới bao gồm các tác vụ phức hợp khác, quá trình phân tách có thể đệ quy vô hạn, giống như một ngữ pháp tạo ra các dẫn xuất dài tùy ý. Ở dạng tổng quát, việc quyết định xem có tồn tại một sự phân tách hợp lệ hay không do đó là không quyết định được.

Lập kế hoạch mạng lưới tác vụ phân cấp

Lập kế hoạch mạng lưới tác vụ phân cấp (HTN) giải quyết vấn đề bằng cách phân tách đệ quy các tác vụ cấp cao thành các tác vụ con bằng cách sử dụng thư viện các phương pháp, thay vì tìm kiếm trực tiếp trên các hành động nguyên thủy để đạt được trạng thái mục tiêu.

Tìm chủ đề với PaperMindSắp ra mắtFind papers & topics

Tools & resources

Tải xuống bản trình chiếu

Learn & explore

VideoSắp ra mắt

Definition

Lập kế hoạch HTN biểu diễn một vấn đề dưới dạng một mạng lưới tác vụ ban đầu cần được thực hiện và một tập hợp các phương pháp để phân tách các tác vụ phức hợp thành các tác vụ con; một giải pháp là một sự phân tách thành các hành động nguyên thủy, có thể thực thi, tuân thủ các ràng buộc của phương pháp.

Scope

Chủ đề này bao gồm mô hình lập kế hoạch HTN: các tác vụ (nguyên thủy và phức hợp), các phương pháp chỉ định cách phân tách một tác vụ phức hợp thành các tác vụ con, và quy trình lập kế hoạch tinh chỉnh một mạng lưới tác vụ ban đầu cho đến khi chỉ còn lại các hành động nguyên thủy có thể thực thi. Nó đề cập đến tính biểu cảm và độ phức tạp của lập kế hoạch HTN so với lập kế hoạch cổ điển và các công cụ lập kế hoạch HTN đáng chú ý. Mô hình lập kế hoạch cổ điển, dựa trên trạng thái mục tiêu được đề cập trong các chủ đề liên quan; lập kế hoạch HTN thay vào đó mã hóa kiến thức miền thủ tục.

Core questions

Các phương pháp mã hóa kiến thức miền về cách hoàn thành các tác vụ phức hợp như thế nào?
Sự phân tách tác vụ khác với việc tìm kiếm trạng thái mục tiêu trong lập kế hoạch cổ điển như thế nào?
Tính biểu cảm và độ phức tạp tính toán của lập kế hoạch HTN so với lập kế hoạch cổ điển là gì?
Các ràng buộc về thứ tự và điều kiện tiên quyết giữa các tác vụ con được xử lý như thế nào trong quá trình phân tách?

Key concepts

tác vụ nguyên thủy và phức hợp
phương pháp và phân tách
mạng lưới tác vụ
ràng buộc thứ tự
kiến thức miền thủ tục
tính biểu cảm của HTN
phân tách tác vụ có thứ tự
SHOP2

Key theories

Phân tách tác vụ bằng phương pháp: Lập kế hoạch HTN thay thế tìm kiếm theo mục tiêu bằng phân tách đệ quy: các tác vụ phức hợp được mở rộng thành mạng lưới các tác vụ con thông qua các phương pháp cho đến khi tất cả các tác vụ đều là nguyên thủy, cho phép mã hóa trực tiếp chuyên môn của con người về cách thực hiện các tác vụ.
Tính biểu cảm và độ phức tạp của lập kế hoạch HTN: Lập kế hoạch HTN biểu cảm hơn đáng kể so với lập kế hoạch STRIPS cổ điển; ở dạng tổng quát, sự tồn tại của kế hoạch có thể không quyết định được, và các dạng hạn chế chiếm các lớp phức tạp cao hơn, phản ánh sức mạnh của phân tách dựa trên phương pháp.
Các công cụ lập kế hoạch phân tách tác vụ có thứ tự: Các công cụ lập kế hoạch HTN thực tế như SHOP2 lập kế hoạch bằng cách phân tách các tác vụ theo thứ tự chúng sẽ được thực thi, điều này cho phép chúng đánh giá các điều kiện tiên quyết dựa trên các trạng thái được xác định đầy đủ và kết hợp kiến thức miền phong phú một cách hiệu quả.

Clinical relevance

Lập kế hoạch HTN được sử dụng rộng rãi trong các trường hợp đã biết và phải tuân theo các quy trình chuyên môn, chẳng hạn như lập kế hoạch quy trình sản xuất, hoạt động quân sự và hậu cần, tổng hợp dịch vụ web, và tạo trò chơi và câu chuyện, bởi vì các phương pháp cho phép các chuyên gia miền mã hóa các cách tiêu chuẩn để hoàn thành các tác vụ.

History

Lập kế hoạch phân cấp có nguồn gốc từ NOAH của Sacerdoti và các hệ thống phân cấp trừu tượng vào những năm 1970. Erol, Hendler và Nau đã chính thức hóa lập kế hoạch HTN và phân tích độ phức tạp của nó vào đầu những năm 1990, và các công cụ lập kế hoạch SHOP và SHOP2 (khoảng năm 2000-2003) đã biến lập kế hoạch HTN có thứ tự thành một công nghệ thực tế và được sử dụng rộng rãi.

Key figures

Dana Nau
Kutluhan Erol
James Hendler
Earl D. Sacerdoti
Austin Tate

Seminal works

erol1994
nau2003

Frequently asked questions

Lập kế hoạch HTN khác với lập kế hoạch cổ điển như thế nào?: Lập kế hoạch cổ điển tìm kiếm bất kỳ chuỗi hành động nào đạt đến trạng thái mục tiêu, chỉ sử dụng các điều kiện tiên quyết và hiệu ứng của hành động. Lập kế hoạch HTN thay vào đó bắt đầu từ các tác vụ cần hoàn thành và phân tách chúng bằng các phương pháp mã hóa cách thức, theo thủ tục, các tác vụ đó thường được thực hiện, vì vậy nó dựa vào kiến thức miền phong phú hơn.
Tại sao lập kế hoạch HTN có thể không quyết định được?: Bởi vì các phương pháp có thể phân tách một tác vụ phức hợp thành các mạng lưới bao gồm các tác vụ phức hợp khác, quá trình phân tách có thể đệ quy vô hạn, giống như một ngữ pháp tạo ra các dẫn xuất dài tùy ý. Ở dạng tổng quát, việc quyết định xem có tồn tại một sự phân tách hợp lệ hay không do đó là không quyết định được.