zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Hệ thống thông minh: Phần 4 - Lập kế hoạch

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:62

Báo xấu

2
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Hệ thống thông minh: Phần 4 - Lập kế hoạch" bao gồm các nội dung chính sau đây: Kế hoạch & lập kế hoạch ; các kỹ thuật lập kế hoạch; các hệ lập kế hoạch. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Hệ thống thông minh: Phần 4 - Lập kế hoạch

LẬP KẾ HOẠCH PLANNING 1
NỘI DUNG • Kế hoạch & lập kế hoạch (Plan & Planning) • Các kỹ thuật lập kế hoạch (planning techniques) • Các hệ lập kế hoạch (Planning systems) 2
KẾ HOẠCH & LẬP KẾ HOẠCH • Các hệ thống thông minh phát sinh vấn đề lập kế hoạch: – Các hệ robot thông minh (Intelligent Robot Systems): robot navigation, path planning, Goal-Oriented robot programming – Các bộ giải quyết vấn đề (Problems Solvers): theorem proving, game playing – Các bộ sinh chương trình tự động (Automated Program Generators) – Các bộ xử lý ngôn ngữ tự nhiên (Natural Language Processors) 3
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) – Các hệ chuyên gia (Expert Systems): Hệ hỗ trợ quyết định (decision support system), Lập kế hoạch quản trị (management planning) – Chế tạo tích hợp máy tính (Computer Integrated Manufacturing): các hệ lập kế hoạch sản xuất (production planning systems), các hệ lập lịch biểu xí nghiệp (factory scheduling systems), các hệ chế tạo linh hoạt (flexible manufacturing systems), các hệ chế tạo tự động hoá (automated manufacturing systems) – Distributed Agents: agent coordination, agent cooperation 4
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) • Lập kế hoạch cổ điển (classical planning): – World (environment): trong đó một hệ thống vận động bao gồm tập tất cả các thực thể có thể tác động/ bị tác động bởi hệ thống và các tính chất của chúng. • Trạng thái thế giới (world state) chỉ sự mô tả đầy đủ của các thực thể và các tính chất tại một thời điểm cụ thể (snapshot). • Hành động khi được áp dụng làm biến đổi thế giới từ một trạng thái sang một trạng thái khác. Dãy trạng thái thế giới được gọi là lịch sử thế giới (world history/ chronicle) – Hành động (action): sự thay phiên tiến triển của trạng thái tinh thần / trạng thái thể chất và tinh thần phối hợp dẫn đến hiệu quả quan sát được trên thế giới bên ngoài. • Có một tập hợp các hành động hệ thống có khả năng thực hiện và không thể chia nhỏ thành các thành phần đơn giản hơn và được gọi là các hành động nguyên thuỷ (primitive actions) 5
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) – Toán tử (operator): biểu diễn các lớp hành động tương tự. Toán tử là một mô tả đầy đủ tham số hoá của một hành động. Nó chứa thông tin liên quan đến định danh hành động, tình huống (trạng thái thế giới) trong đó nó có thể áp dụng và hiệu quả của việc áp dụng nó. – Đích (goal): được mô tả như tính chất mong muốn của trạng thái thế giới. Nhiệm vụ của hệ thống là biến đổi trạng thái thế giới hiện hành sang trạng thái đích. – Kế hoạch (plan): công thức hoá chi tiết và hệ thống các hành động. Nó là một tập các hành động (toán tử) nhóm lại trong một cấu trúc mệnh lệnh xác định. Cấu trúc có thể là dãy, chọn lựa, lặp, đệ quy, song song, và ở dạng không tiền định. Một kế hoạch có thể được phân tích thành các kế hoạch con. Kế hoạch con lại có thể được phân tích thành các kế hoạch con nhỏ hơn, … 6
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) Một kế hoạch được gọi là có thể áp dụng được đối với trạng thái hiện hành nếu nó có thể được thực hiện đầy đủ bắt đầu từ trạng thái này Một kế hoạch được gọi là một lời giải của một vấn đề nếu áp dụng nó lên trạng thái hiện hành dẫn đến trạng thái đích Có nhiều kế hoạch lời giải cho một vấn đề. Các lời giải được đánh giá và sắp thứ tự dựa trên các độ đo hiệu quả – Thực hiện kế hoạch (plan execution): quá trình thực hiện một kế hoạch khả thi của hệ thống – Lập kế hoạch (planning): Đã cho tập các hành động nguyên thuỷ, các toán tử, và mô hình thế giới hiện hành cùng với một đích, lập kế hoạch là quá trình công thức hoá một kế hoạch khả thi và đạt được đích khi thực hiện. 7
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) Trí tuệ của hệ thống được phản ánh qua khả năng sản sinh kế hoạch hiệu quả/ tối ưu (tính hiệu quả, tối ưu được định nghĩa tuỳ theo lĩnh vực ứng dụng) 8
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) • Lập kế hoạch thực tế (practical planning): lập kế hoạch cổ điển khi được xét trong ngữ cảnh thế giới thực phải xét thêm một chiều khác và được gọi là lập kế hoạch thực tế – Thời gian, lập lịch biểu và các ràng buộc: tất cả các môi trường thực đều bao hàm chiều thời gian. Do vậy quá trình lập kế hoạch và các kế hoạch được sinh ra phải được chiếu lên thời gian. Lập kế hoạch gắn hành động với chu kỳ thời gian được gọi là lập lịch biểu. Sự việc trở nên phức tạp hơn khi các ràng buộc thời gian được đặt ra (deadline, ưu tiên, …) 9
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) – Thời gian thực (real time): trong thế giới thực, đích đến ngẫu nhiên, hệ thống phải đáp ứng trong thời gian thực, lập kế hoạch, lập lại kế hoạch và thực hiện kế hoạch liên tục đáp ứng đòi hỏi trả lời trong thời gian thực. (quá trình điều khiển) – Giám sát thực hiện (execution monitoring): môi trường thực đặc trưng bởi tính không chắc chắn, không thể tiên đoán, xảy ra lỗi. Trong trường hợp lý tưởng, thế giới thay đổi đúng như hệ thống , sử dụng mô hình thế giới của nó, tiên đoán. Trong thực tế, trạng thái thế giới thực trở nên không tương thích với trạng thái mô hình thế giới, sự thực hiện kế hoạch sẽ thất bại. 10
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) hệ thống phải giám sát sự thực hiện của kế hoạch, cập nhật mô hình thế giới khi một biến cố không mong đợi xảy ra và rà soát lại kế hoạch hiện hành để đáp ứng các điều kiện mới. – Phân cấp (hierarchy): ba mức xử lý trong hệ thống: lập kế hoạch, lập lịch biểu, giám sát. Mỗi mức có thể gồm vài mức mức con tạo ra một sự phân cấp. Lượng trí tuệ được đòi hỏi giảm dần từ lập kế hoạch đến giám sát. – Metaplanning và học: metaplanning đặc trưng trí tuệ và tri thức dẫn dắt quá trình lập kế hoạch. lập kế hoạch hiệu quả đòi hỏi hệ thống có khả năng thu lượm tri thức lập kế hoạch từ môi trường của nó và kinh nghiệm của nó, quá trình này được gọi là học. Học cung cấp cho hệ thống tính thích nghi và cấu trúc trong năng động 11
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) 12
KẾ HOẠCH & LẬP KẾ HOẠCH (cont.) – Lĩnh vực multiagent: trong thực tế, thế giới là tập hợp của các agents (các hệ thống thông minh, không nhất thiết đồng nhất), một số trong đó hợp tác với nhau, một số là đối thủ của nhau và một số khác đơn giản là không quan tâm gì đến nhau. Lập kế hoạch trong lĩnh vực multi-agent là vấn đề rất khó. Trong lĩnh vực như vậy, lập kế hoạch không chỉ được thiết lập trên cơ sở cá nhân mà còn phải tổng quát hoá trên một nhóm – lập kế hoạch phân tán. Các khái niệm hợp tác agent, niềm tin agent, ý định agent, liên lạc agent, deadlock giao thoa hành động … phát sinh và làm tăng độ phức tạp 13
CÁC KỸ THUẬT LẬP KẾ HOẠCH • Biểu diễn tri thức: Một vấn đề quan trọng trong mọi hệ thống thông minh là phương pháp biểu diễn tri thức trong hệ thống. Tính hiệu quả của hệ thống không chỉ phụ thuộc vào chất lượng tri thức mà còn phụ thuộc vào phương pháp cấu trúc tri thức – Mô hình hình thức: dùng để mô tả và phân tích các cách tiếp cận khác nhau – Phép tính vị từ bậc nhất (first-order predicate calculus): cách tiếp cận đơn giản nhất để biểu diễn tri thức 14
CÁC KỸ THUẬT LẬP KẾ HOẠCH (cont.) trạng thái thế giới được biểu diễn bởi một tập các công thức được định dạng tốt (well-formed formulas – wff), nó xác định các tính chất của trạng thái Một toán tử có thể được biểu diễn như một bộ ba danh sách wff: • Danh sách tiền điều kiện (precondition list) • Danh sách thêm (add list) • Danh sách xoá (delete list) danh sách thứ nhất xác định điều kiện của thế giới mà toán tử có thể áp dụng. Các danh sách thêm và xoá chứa các thông tin về hiệu quả của toán tử và trạng thái mới của thế giới (trạng thái nhận được bằng cách thêm vào các vị từ của add list và xoá đi từ nó các vị từ có trong delete list) 15
CÁC KỸ THUẬT LẬP KẾ HOẠCH (cont.) Phương pháp biểu diễn dựa trên STRIPS – STanford Research Institute Problem Solver Phương pháp tiếp cận này dựa trên hai giả thiết: Giả thiết thế giới khép kín (closed world assumption): mọi tính chất phủ định của thế giới là đúng đến tận khi dạng không phủ định được phát biểu tường minh trong trạng thái thế giới hiện hành Giả thiết STRIPS: trạng thái thế giới không thay đổi đến tận khi một hành động xác định tường minh một số thay đổi trong nó hạn chế: bỏ sót yếu tố thời gian – Phép tính tình huống (situation calculus): tình huống (situation): là một “cảnh chụp” (snapshot) của thế giới tại một thời điểm 16
CÁC KỸ THUẬT LẬP KẾ HOẠCH (cont.) Phép tính tình huống cung cấp một ngôn ngữ cho xác định tri thức tình huống bằng cách lấy các tình huống như các đối tượng trong lĩnh vực và được mô tả trong thuật ngữ logic fluent: là một hàm tương ứng với một tính chất của thế giới, cho một tình huống, fluent trả lại giá trị của tính chất trong tình huống này. vị từ trong phép tính tình huống được dùng để xác định các phát biểu về các giá trị của các fluent trong tình huống bắc cầu tình huống (situation transition) được xác định trong thuật ngữ hàm kết quả: một hành động thực hiện trong một tình huống cụ thể trả lại tình huống kết quả – Logic thời gian (temporal logic): đưa vào các toán tử thời gian, mô tả các tính chất của lịch sử thế giới. 17
CÁC KỸ THUẬT LẬP KẾ HOẠCH (cont.) Các biến cố ngoài, các hành động đồng thời, các hành động chồng chéo có thể được biểu diễn. logic thời gian là phương pháp tự nhiên nhất và tiện lợi nhất để biểu diễn môi trường thế giới thực • Tổng hợp kế hoạch: – Lập kế hoạch phụ thuộc & độc lập lĩnh vực: Phân biệt hai phương pháp này dựa trên lĩnh vực ứng dụng của hệ thống. phương pháp phụ thuộc lĩnh vực: hệ thống tận dụng tri thức lĩnh vực và sử dụng heuristic lĩnh vực để điều khiển các hoạt động phương pháp độc lập lĩnh vực: lập kế hoạch dựa trên cơ chế tổng quát, hạn chế sử dụng tri thức lĩnh vực cố gắng kết hợp tri thức vào trong hệ thống 18
CÁC KỸ THUẬT LẬP KẾ HOẠCH (cont.) – Lập kế hoạch tuyến tính & phi tuyến: Phân biệt dựa trên giả thiết về tính tuyến tính: “cho một đích, nó có thể được phân tích thành các đích con, một kế hoạch con có thể được xây dựng cho mỗi đích con, kế hoạch cuối cùng có thể được tạo ra bằng cách tổ hợp các kế hoạch con này một cách tuần tự”. Giả thiết chỉ đúng trong trường hợp đích có thể phân tích tuyến tính thành các đích con. Trong trường hợp tổng quát, có các tương tác mạnh giữa các đích con, cũng như vậy với các kế hoạch con vậy thì lập kế hoạch tuyến tính là không thể. Trong trường hợp đó, lập kế hoạch phải xen kẽ các đích con và các kế hoạch con  lập kế hoạch phi tuyến 19
CÁC KỸ THUẬT LẬP KẾ HOẠCH (cont.) – Lập kế hoạch thứ tự bộ phận & thứ tự toàn phần Phân biệt dựa trên nguyên lý: “các chọn lựa được lấy tại bất kỳ thời điểm nào là các lựa chọn cần thiết, các lựa chọn khác bị trì hoãn lâu như có thể”. Một kế hoạch được biểu diễn, tại thời điểm bất kỳ, như một tập các toán tử được sắp thứ tự toàn phần (lập kế hoạch thứ tự toàn phần) hoặc như một tập các toán tử được sắp thứ tự bộ phận (lập kế hoạch thứ tự bộ phận) – Chứng minh định lý: Phương pháp tiếp cận đơn giản nhất. Lập kế hoạch được xem như khả năng chứng minh sự tồn tại của một dãy hành động đạt tới đích. Các cách tiếp cận suy diễn khác là tổng hợp kế hoạch sử dụng các điều kiện bổ xung, đệ quy, lặp 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.