Điều khiển và cài đặt tìm kiếm trong không gian trạng thái

anh chấp và do đó cũng sẽ xác định con đường tìm kiếm và lời giải riêng. 5. Có cơ hội cho điều khiển heuristic của quá trình tìm kiếm. 6. Theo dõi và giải thích: Tính module của các luật và bản chất lặp lại trong quá trình thực thi làm cho nó dễ dàng theo dõi hơn trong một hệ sinh. Ở mỗi giai đoạn của chu trình nhận dạng – hành động, luật được chọn có thể được hiện ra. Vì mỗi luật ứng với một đoạn của quá trình giải toán nên nội dung luật sẽ giải thích đầy đủ ý nghĩa về trạng thái và hành động hiện hành của hệ thống đó. 7. Tính độc lập ngôn ngữ: Mô hình điều khiển hệ sinh không phụ thuộc vào cách thể hiện đã được chọn cho các luật và cho bộ nhớ làm việc miễn là cách thể hiện đó hỗ trợ cho việc đối sánh mẫu. 90 Võ Huỳnh Trâm – Trần Ngân Bình Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái 8. Mô hình hóa việc giải các bài toán của con người: Đây là một trong những ứng dụng đầu tiên của hệ sinh, chúng vẫn còn được dùng làm mô hình cho họat động của con người trong nhiều nghiên cứu khoa học về nhận thức. III KIẾN TRÚC BẢNG ĐEN (BLACKBOARD ARCHITECTURE) Kiến trúc bảng đen là cơ chế điều khiển cuối cùng được giới thiệu trong chương này. Kiến trúc bảng đen mở rộng các hệ sinh bằng cách cho phép chúng ta sắp xếp bộ nhớ làm việc thành các module riêng, mỗi module tương ứng với một luật sinh khác nhau. Kiến trúc này cũng cho phép chúng ta tích hợp các tập luật sinh khác nhau vào một cấu trúc toàn cục duy nhất. Một kiến trúc bảng đen bao gồm: 1. Bảng đen (Blackboard): Là một số cơ sở dữ liệu toàn cục tập trung dùng để trao đổi thông tin giữa các nguồn tri thức không đồng bộ độc lập, tập trung vào các mặt có liên quan của một bài toán cụ thể. 2. Các nguồn tri thức (Knowledge source) KSi: Lấy dữ liệu của mình từ bảng đen, xử lý các dữ liệu đó rồi trả kết quả về cho bảng đen để các nguồn tri thức khác sử dụng. Mỗi KSi đều độc lập theo ý nghĩa là một quá trình riêng biệt, hoạt động theo các đặc trưng riêng, và khi sử dụng một hệ thống đã xử lý hoặc có nhiều bộ xử lý, nó sẽ độc lập với các quá trình xử lý khác của bài toán. Hệ thống không đồng bộ ở chỗ từng KSi sẽ bắt đầu hoạt động của mình khi nào tìm thấy các dữ liệu đầu vào thích hợp được công bố trên bảng đen. Khi kết thúc công việc xử lý của mình, nó sẽ gửi kết quả đi và chờ dữ liệu đầu vào mới. 3. Bộ lập lịch trình (scheduler): Tổ chức việc cấp tài nguyên và truy cập bảng đen của các nguồn tri thức. Hình sau trình bày một sơ đồ về kiểu thiết kế bảng đen: Hình 5.7 – Kiến trúc bảng đen Bảng đen toàn cục KS1 KS2 KSi KSn Võ Huỳnh Trâm – Trần Ngân Bình 91 Giáo Trình Trí Tuệ Nhân Tạo Kiến trúc bảng đen dùng trong việc tổ chức một chương trình lớn, lần đầu tiên được giới thiệu trong công trình nghiên cứu HEARSAY-II (Erman và cộng sự, Reddy–1976). HEARSAY–II là một chương trình hiểu lời nói, đầu tiên nó được thiết kế dưới dạng nền cho một cơ sở dữ liệu thư viện về những bài báo khoa học. Những người sử dụng thư viện này phải nói với máy tính những câu như: “Có bài báo nào của Feigenbaum và Feldman hay không?” và máy tính sẽ trả lời câu hỏi đó bằng những thông tin lấy từ cơ sở dữ liệu của thư viện. Quá trình hiểu tiếng nói đòi hỏi chúng ta phải tích hợp một số quá trình khác nhau, có những yêu cầu về kiến thức và thuật toán rất khác nhau, và độ phức tạp có thể tăng theo hàm mũ. Những quá trình xử lý tín hiệu, nhận biết âm vị, âm tiết, từ, phân tích cú pháp và phân tích ngữ nghĩa sẽ chế ngự ràng buộc lẫn nhau khi diễn giải câu nói. Kiến trúc bảng đen đã cho phép HEARSAY-II tọa độ hóa một số nguồn tri thức khác nhau dùng trong công việc phức tạp này. Kiến trúc bảng đen thường được tổ chức theo hai chiều. Với HEARSAY-II hai chiều đó là thời gian khi lời nói được tạo ra và mức độ phân tích lời nói. Mỗi mức độ phân tích được xử lý bởi một lớp các nguồn tri thức: KS1 - Dạng sóng của tín hiệu âm thanh KS2 - Các âm vị hay các đoạn âm của tín hiệu âm thanh KS3 - Các âm tiết mà các âm vị đó có thể tạo ra KS4 - Các từ khi được phân tích bởi một KS KS5 - Các từ khi được phân tích bởi một KS khác KS6 - Loại KS dùng để phát ra các chuỗi từ KS7 - Loại KS dùng để đặt các chuỗi từ vào trong câu Trong việc xử lý lời nói, dạng sóng của tín hiệu âm thanh được đưa vào ở mức độ thấp nhất. Các nguồn tri thức dùng cho việc xử lý ở mức này đều được hiệu lực hóa và gởi các kết quả diễn dịch của chúng cho bảng đen, để sau đó sẽ được chọn lấy ra bởi một quá trình thích hợp. Vì ngôn ngữ nói thường có nhiều chỗ tối nghĩa nên có thể có nhiều giả thiết tranh chấp nhau ở từng mức trong kiến trúc. Các nguồn kiến thức ở mức cao hơn sẽ làm rõ nghĩa cho các giả thiết tranh chấp này. Sự phân tích của HEARSAY-II không thể xem đơn giản như một mức thấp tạo ra dữ liệu và sau đó các mức cao hơn là phân tích. Quá trình phức tạp hơn nhiều. Nếu KS ở một mức không thể xử lý dữ liệu được đưa đến, thì KS đó có thể yêu cầu KS đã gời dữ liệu cho nó quay lại với cách xử lý khác hay tạo ra giả thiết khác về dữ liệu đó. Ngoài ra, nhiều KS khác nhau có thể đồng thời hoạt động trên nhiều phần khác nhau của lời nói. Tất cả các quá trình này đều đồng bộ và hướng dữ liệu, chúng hoạt động khi có dữ liệu vào, tiếp tục hoạt động cho đến khi hoàn thành xong nhiệm vụ và sau đó gởi kết quả đi rồi chờ nhiệm vụ tiếp theo. Bộ lập lịch trình là một trong các KS, sẽ quản lý việc truy cập giữa các KS nếu không có KS nào hoạt động, bộ lập lịch trình sẽ quyết định nhiệm vụ đó kết thúc và đóng lại. Khi chương trình HEARSAY-II có một cơ sở dữ liệu khoảng 1000 từ, nó làm việc hoàn toàn tốt mặc dù hơi chậm. Khi cơ sở dữ liệu mở rộng hơn, dữ liệu dùng cho các nguồn tri thức này sẽ trở nên rất phức tạp đến mức khó quản lý. HEARSAY-III (Balzer và cộng sự - 1980, 92 Võ Huỳnh Trâm – Trần Ngân Bình Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái Erman và cộng sự - 1981) là sự tổng quát hóa phương pháp mà HEARSAY-II đã dùng. Chiều thời gian của HEARSAY-II không còn cần thiết nữa, nhưng nhiều KS ứng với các mức phân tích thì vẫn giữ nguyên. Bảng đen dùng cho HEARSAY-III được hoạch định để tương tác với một cơ sở dữ liệu quan hệ đa năng. Thực vậy, HEARSAY-III là một khung chung dùng để thiết kế các hệ chuyên gia. Một thay đổi quan trọng trong HEARSAY-III là chia bộ lập lịch trình thành một công cụ điều khiển riêng cho bảng đen. TỔNG KẾT CHƯƠNG V: Chương V đã trình bày một số các thuật toán cũng như các mô hình, kiến trúc phổ biến dùng điều khiển và cài đặt quá trình tìm kiếm trong không gian trạng thái như: tìm kiếm đệ quy, mô hình hệ sinh, kiến trúc bảng đen, … cùng với các bài toán minh họa cho từng giải thuật rất cụ thể. Trong chương VI tiếp theo, chúng ta sẽ thảo luận việc giải quyết vấn đề tri thức chuyên sâu mà điển hình là thiết kế các hệ chuyên gia. IV BÀI TẬP CHƯƠNG V V.1. Trước tình hình dịch cúm gà gần đây, Bộ y tế có đưa ra một số hướng dẫn về thực phẩm an toàn (safe) dưới dạng một tập hợp biểu thức vị từ như sau: R1. vegetable(X) ∨ fruit(X) ⇒ safe(X) R2. beef(X) ∨ porc(X) ∨ lamb(X) ⇒ meat(X) R3. meat(X) ∧ low_fat(X) ⇒ low_risk(X) R4. contains_fat(X,Y) ∧ (Y<20%) ⇒ low_fat(X) R5. certified(X) ∨ low_risk(X) ⇒ safe(X) a) Vẽ đồ thị AND/OR cho biết “thực phẩm an toàn”. b) Nếu biết lượng chất béo có trong thịt bò (contains_fat) là nhỏ hơn 20%, biểu diễn các bước suy diễn theo hệ sinh – tìm kiếm hướng dữ liệu để chứng tỏ “thịt bò là thực phẩm an toàn”. Võ Huỳnh Trâm – Trần Ngân Bình 93 Giáo Trình Trí Tuệ Nhân Tạo V.2. Vẽ đồ thị AND/OR cho các quá trình suy diễn tiến và suy diễn lùi dùng trong hệ tư vấn dưới đây: Hệ tư vấn cho việc chọn hình thức giải trí trong kỳ nghĩ của bạn. Các đề nghị khác nhau mà hệ có thể cung cấp là: ngắm cảnh, trượt tuyết, tắm nắng, bơi lội, lướt ván. Tập luật suy diễn bao gồm: R1. IF thích_nắng THEN nghỉ_vùng_biển R2. IF không_thích_nắng AND chơi_thể thao THEN nghỉ_vùng_núi R3. IF không_thích_nắng AND không_chơi_thể thao THEN ngắm_cảnh R4. IF nghỉ_vùng_núi AND ngân_sách_nhỏ THEN ngắm_cảnh R5. IF nghỉ_vùng_núi AND ngân_sách_không_nhỏ THEN trượt_tuyết R6. IF nghỉ_vùng_biển AND không_chơi_thể thao THEN tắm_nắng R7. IF nghỉ_vùng_biển AND chơi_thể thao AND ngân_sách nhỏ THEN bơi_lội R8. IF nghỉ_vùng_biển AND chơi_thể thao AND ngân_sách_không_nhỏ THEN lướt_ván 1) Suy diễn tiến dùng dữ liệu: Nam, rất thích chơi thể thao, không thích ánh nắng và có ngân sách không nhỏ. 2) Suy diễn lùi và trả lời các câu hỏi phát sinh từ hệ thống trên dữ liệu sau: Hoa, rất thích chơi thể thao, thích ánh nắng mặt trời và chỉ có ngân sách nhỏ. 94 Võ Huỳnh Trâm – Trần Ngân Bình Võ Huỳnh Trâm – Trần Ngân Bình 95 Chương V................................................................................................................................79 ĐIỀU KHIỂN VÀ CÀI ĐẶT TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI.......79 I. TÌM KIẾM DỰA TRÊN CƠ SỞ ĐỆ QUI.................................................................80 I.1. Tìm kiếm đệ quy ...............................................................................................80 I.2. Tìm kiếm hướng mẫu (Pattern – directed search) .............................................81 II. HỆ THỐNG LUẬT SINH (HỆ SINH – PRODUCTION SYSTEM) .......................83 II.1. Định nghĩa hệ sinh ............................................................................................83 II.2. Một số ví dụ về hệ sinh .....................................................................................85 II.3. Điều khiển tìm kiếm trong các hệ sinh..............................................................87 II.4. Những ưu điểm của hệ sinh dùng cho trí tuệ nhân tạo......................................90 III. KIẾN TRÚC BẢNG ĐEN (BLACKBOARD ARCHITECTURE) ......................91 BÀI TẬP CHƯƠNG V ............................................................................................93