Lập kế hoạch cổ điển và STRIPS

Lập kế hoạch cổ điển giải quyết vấn đề tìm kiếm một chuỗi các hành động để đạt được mục tiêu trong một môi trường xác định, có thể quan sát đầy đủ, tĩnh, sử dụng biểu diễn hành động kiểu STRIPS được phân tích theo các điều kiện tiên quyết và hiệu ứng.

Definition

Lập kế hoạch cổ điển tìm kiếm một chuỗi các hành động xác định biến đổi một trạng thái ban đầu đã biết đầy đủ thành một trạng thái thỏa mãn mục tiêu, trong đó mỗi hành động được mô tả bởi các điều kiện phải đúng để nó được áp dụng và những thay đổi mà nó tạo ra.

Scope

Chủ đề này bao gồm mô hình lập kế hoạch cổ điển và các giả định của nó (hành động xác định, khả năng quan sát đầy đủ, một tác nhân duy nhất, thời gian nguyên tử), các biểu diễn trạng thái và hành động của STRIPS và ADL/PDDL, các phương pháp giải cơ bản của tìm kiếm không gian trạng thái tiến (progression) và lùi (regression) và lập kế hoạch thứ tự một phần, và độ phức tạp tính toán của lập kế hoạch mệnh đề. Hướng dẫn heuristic và đồ thị lập kế hoạch được đề cập trong chủ đề liên quan, và các biến thể không xác định hoặc xác suất nằm ngoài phạm vi.

Core questions

• Những giả định nào định nghĩa mô hình lập kế hoạch cổ điển, và khi nào chúng phù hợp?
• Biểu diễn STRIPS phân tích một trạng thái thành các mệnh đề và một hành động thành các điều kiện tiên quyết và các hiệu ứng thêm/xóa như thế nào?
• Tìm kiếm tiến (progression) và lùi (regression) khác nhau như thế nào với tư cách là các chiến lược lập kế hoạch?
• Độ khó tính toán của lập kế hoạch cổ điển nói chung là bao nhiêu?

Key concepts

• mô hình xác định, có thể quan sát đầy đủ
• điều kiện tiên quyết và hiệu ứng STRIPS
• danh sách thêm và xóa
• PDDL và ADL
• tìm kiếm tiến (forward)
• tìm kiếm lùi (backward)
• lập kế hoạch thứ tự một phần
• độ phức tạp tồn tại kế hoạch

Key theories

Biểu diễn STRIPS

STRIPS mô tả thế giới như một tập hợp các mệnh đề đúng và mỗi hành động bằng một danh sách điều kiện tiên quyết cộng với danh sách thêm và xóa, do đó việc áp dụng một hành động chỉ đơn giản là thêm và loại bỏ các mệnh đề; mô hình được phân tích này là nền tảng của gần như tất cả các công cụ lập kế hoạch cổ điển.

Tìm kiếm tiến và lùi

Các kế hoạch cổ điển có thể được tìm thấy bằng cách tìm kiếm tiến từ trạng thái ban đầu áp dụng các hành động có thể áp dụng (progression) hoặc lùi từ mục tiêu tính toán các mục tiêu phụ đã hồi quy (regression), với lập kế hoạch thứ tự một phần nới lỏng cam kết về một thứ tự hành động tổng thể.

Độ phức tạp của lập kế hoạch

Việc quyết định xem một kế hoạch STRIPS mệnh đề có tồn tại hay không là PSPACE-complete nói chung, giải thích một cách chính thức tại sao lập kế hoạch lại khó và thúc đẩy các phương pháp heuristic và cấu trúc để làm cho nó thực tế.

Clinical relevance

Các biểu diễn lập kế hoạch cổ điển là giao diện chung cho lập kế hoạch nhiệm vụ robot, lắp ráp và hậu cần tự động, và bất kỳ ứng dụng nào mà các hành động xác định phải được sắp xếp theo trình tự để đạt được mục tiêu; các công cụ lập kế hoạch cổ điển dựa trên PDDL là những công cụ chủ chốt của lĩnh vực này và của các Cuộc thi Lập kế hoạch Quốc tế.

History

STRIPS được phát triển tại SRI vào khoảng năm 1971 để điều khiển robot Shakey, giới thiệu mô hình hành động điều kiện tiên quyết/hiệu ứng định nghĩa lập kế hoạch cổ điển. Lập kế hoạch thứ tự một phần trưởng thành vào những năm 1970-80, Bylander đã thiết lập tính PSPACE-complete của lập kế hoạch mệnh đề vào năm 1994, và tiêu chuẩn PDDL sau đó đã thống nhất các tiêu chuẩn của lĩnh vực này.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

Các giả định của lập kế hoạch cổ điển là gì?

Lập kế hoạch cổ điển giả định một tác nhân duy nhất hoạt động trong một môi trường xác định, có thể quan sát đầy đủ và tĩnh, với các hành động mất một đơn vị thời gian và một trạng thái ban đầu đã biết đầy đủ. Việc nới lỏng bất kỳ giả định nào trong số này, ví dụ như cho phép sự không chắc chắn hoặc đồng thời, dẫn đến các vấn đề lập kế hoạch phong phú hơn ngoài mô hình cổ điển.

Danh sách thêm và danh sách xóa của STRIPS có nghĩa là gì?

Khi một hành động STRIPS được áp dụng, các mệnh đề trong danh sách thêm của nó trở thành đúng và những mệnh đề trong danh sách xóa của nó trở thành sai; tất cả các mệnh đề khác không thay đổi. Quy tắc cập nhật đơn giản này là điều làm cho STRIPS trở thành một biểu diễn nhỏ gọn và thuận tiện về mặt tính toán về cách các hành động thay đổi thế giới.