Đồ thị lập kế hoạch và các hàm heuristic

Đồ thị lập kế hoạch và các hàm heuristic độc lập với miền là những kỹ thuật đã làm cho việc lập kế hoạch cổ điển trở nên nhanh chóng, bằng cách phân tích khả năng tiếp cận một cách nhỏ gọn và tự động ước tính khoảng cách từ một trạng thái đến mục tiêu.

Definition

Đồ thị lập kế hoạch là một cấu trúc phân lớp xen kẽ các cấp độ mệnh đề và hành động với các ràng buộc loại trừ lẫn nhau (mutex) để xấp xỉ khả năng tiếp cận; các hàm heuristic lập kế hoạch là các hàm, thường được tính toán từ các cấu trúc như vậy hoặc từ các bài toán được nới lỏng xóa, ước tính chi phí để đạt được mục tiêu từ một trạng thái.

Scope

Chủ đề này bao gồm cấu trúc dữ liệu đồ thị lập kế hoạch được giới thiệu bởi Graphplan, bao gồm các cấp độ mệnh đề và hành động cũng như các mối quan hệ loại trừ lẫn nhau (mutex) nắm bắt những sự kiện và hành động nào không thể xảy ra đồng thời, và họ các hàm heuristic độc lập với miền được suy ra từ các bài toán được nới lỏng (đáng chú ý là bỏ qua các hiệu ứng xóa) thúc đẩy các bộ lập kế hoạch tìm kiếm heuristic hiện đại. Nó đề cập đến cách thông tin khả năng tiếp cận được tính toán và sử dụng để hướng dẫn tìm kiếm. Mô hình lập kế hoạch cổ điển cơ bản được đề cập trong chủ đề liên quan.

Core questions

• Đồ thị lập kế hoạch biểu diễn các mệnh đề và hành động có thể đạt được theo từng cấp độ như thế nào?
• Các mối quan hệ loại trừ lẫn nhau (mutex) là gì, và chúng nắm bắt sự không tương thích giữa các sự kiện và hành động như thế nào?
• Việc nới lỏng xóa được sử dụng như thế nào để suy ra các hàm heuristic lập kế hoạch chấp nhận được hoặc có tính thông tin?
• Các hàm heuristic này biến việc lập kế hoạch thành tìm kiếm heuristic hiệu quả như thế nào?

Key concepts

• đồ thị lập kế hoạch
• các cấp độ mệnh đề và hành động
• loại trừ lẫn nhau (mutex)
• Graphplan
• nới lỏng xóa
• các hàm heuristic h-max và h-add
• heuristic FF và các kế hoạch được nới lỏng
• tìm kiếm tiến heuristic

Key theories

Đồ thị lập kế hoạch và Graphplan

Graphplan xây dựng một đồ thị lập kế hoạch mã hóa một cách nhỏ gọn các mệnh đề và hành động nào có thể đạt được ở mỗi cấp độ và cặp nào loại trừ lẫn nhau, sau đó trích xuất một kế hoạch bằng cách tìm kiếm ngược thông qua cấu trúc này, làm tăng tốc độ lập kế hoạch đáng kể.

Các hàm heuristic nới lỏng xóa

Việc bỏ qua các hiệu ứng xóa của các hành động tạo ra một bài toán lập kế hoạch được nới lỏng dễ giải quyết hơn nhiều; chi phí giải quyết sự nới lỏng này cung cấp các hàm heuristic có tính thông tin, thường là chấp nhận được (chẳng hạn như h-max và h-add và heuristic FF) để hướng dẫn tìm kiếm tiến.

Lập kế hoạch tìm kiếm heuristic

Các bộ lập kế hoạch cổ điển tiên tiến kết hợp các hàm heuristic được suy ra tự động với tìm kiếm tốt nhất hoặc tìm kiếm tham lam và các cải tiến như các toán tử ưu tiên, đạt được hiệu suất tổng quát mạnh mẽ trên nhiều miền khác nhau.

Clinical relevance

Đồ thị lập kế hoạch và các hàm heuristic nới lỏng xóa là công nghệ cốt lõi của các bộ lập kế hoạch chiến thắng trong các cuộc thi được sử dụng trong robot học, hậu cần và điều khiển tự động, nơi chúng cho phép các bộ lập kế hoạch độc lập với miền giải quyết các bài toán lớn một cách nhanh chóng mà không cần hướng dẫn tìm kiếm thủ công.

History

Graphplan của Blum và Furst (1995, phiên bản tạp chí 1997) đã giới thiệu đồ thị lập kế hoạch và cách mạng hóa tốc độ lập kế hoạch. Cuối những năm 1990 và những năm 2000 chứng kiến sự ra đời của các hàm heuristic nới lỏng xóa, với bộ lập kế hoạch FF (Hoffmann và Nebel, 2001) và sau đó là Fast Downward (Helmert, 2006) đã thiết lập tìm kiếm tiến heuristic như là phương pháp chủ đạo.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

Mutex trong đồ thị lập kế hoạch là gì?

Mối quan hệ mutex (loại trừ lẫn nhau) đánh dấu hai mệnh đề hoặc hai hành động không thể cùng tồn tại hoặc được áp dụng ở cùng một cấp độ, ví dụ vì một hành động xóa một điều kiện tiên quyết của hành động kia. Mutex làm cho đồ thị lập kế hoạch trở thành một xấp xỉ chặt chẽ hơn về khả năng tiếp cận thực sự.

Tại sao việc bỏ qua các hiệu ứng xóa lại đưa ra một hàm heuristic hữu ích?

Nếu không có hiệu ứng xóa, việc đạt được một mục tiêu không bao giờ làm mất đi một mục tiêu khác, vì vậy bài toán được nới lỏng dễ giải quyết hơn nhiều và không bao giờ khó hơn bài toán gốc. Do đó, chi phí của kế hoạch được nới lỏng là một cận dưới hoặc ước tính có thông tin về chi phí thực tế, làm cho nó trở thành một hàm heuristic hiệu quả để hướng dẫn tìm kiếm.