Bài giảng Trí tuệ nhân tạo - Chương 5: Điều khiển và cài đặt cho TK-KGTT - Trần Ngân Bình

Chương 5 – Điều Khiển & Cài Đặt cho TK–KGTT Giáo viên: Trần Ngân BìnhChương 5. p.2Nội DungGiải thuật tìm kiếm đệ qui (Recursive-based search)Có thể cài đặt tìm kiếm sâu với quay lui một cách đệ qui.Kết hợp phép đồng nhất để tạo ra giải thuật TK hướng mẫu.Là cơ sở của ngôn ngữ PROLOG.Giải thuật tìm kiếm hướng mẫu (Pattern search)Cài đặt tìm kiếm trên đồ thị Và/HoặcTách biệt tri thức giải quyết vấn đề khỏi việc điều khiển tìm kiếm.Hệ thống luật sinh (Production system)Tìm kiếm được điều khiển theo kiểu hướng mẫuMô phỏng quá trình giải quyết vấn đề của con ngườiTách biệt tri thức và điều khiểnTách biệt tri thức giải quyết vấn đề khỏi các dữ kiện bài toán cụ thể trong bộ nhớ làm việcKiến trúc bảng đen (Blackboard architecture)Chương 5. p.3Giải thuật Đệ Qui cho TK Sâu % Recusive call% Teminating condition% Loop detectionChương 5. p.4Tìm Kiếm Hướng MẫuFunction pattern_search(current_goal);Begin	if current_goal  closed then	 return fail 	else add current_goal to closed;	while còn dữ kiện hoặc luật đồng nhất do 	begin case	 - current_goal đồng nhất với 	dữ kiện:	 return tập phép thế;	 - current goal là ¬p:	 pattern_search(p);	 if pattern_search thất bại	then return {}	 else return fail	- current_goal đồng nhất với kết luận của luật (p ← q):	 begin	áp dụng phép thế 	đồng nhất mục tiêu 	vào tiền đề (p);	pattern_search (p);	if pattern_search 	thành công	 return hợp của tập 	 	 phép thế của p và q;	else return fail;	 end;.Chương 5. p.5Tìm Kiếm Hướng Mẫu- current_goal có dạng (p1): begin	repeat cho mỗi pi 	pattern_search(pi); 	until không còn thành phần pi 	nào hoặc thành công; 	if pattern_search thành công 	then return {phép thế};	else return fail;end;return fail;End.- current_goal có dạng (p1): begin	for mỗi thành phần pi do	begin 	 pattern_search(pi);	 if pattern_search thất bại then 	return fail;	 else áp dụng các phép thế vào 	các pi còn lại;	end;	if pattern_search thành công cho 	tất cả các pi then 	return hợp của các tập phép thế;	else return fail;end;Chương 5. p.6Một số vấn đề về biễu diễn luậtP  Q	Q 	 PIf giả thuyết then kết luận	Q If 	 PIf điều kiện then hành động 	Q :-	 PIf tiền đề then hệ quả	Q when PĐôi khi có một số ràng buộc như:Không cho phép: p  q  rKhông cho phép: p  qKhông cho phép: p  r  qCác lượng tử biến được xóa bỏ khi:Các biến xuất hiện ở cả hai vế của luật kết hợp với lượng tử phổ biến.Các biến xuất hiện trong tiền đề của luật chỉ kết hợp với lượng tử tồn tại.Chương 5. p.7Định Nghĩa Hệ Thống Luật SinhMột hệ thống luật sinh được định nghĩa bởi:Tập hợp các luật sinh (production rules): 	mỗi luật sinh có dạng:	 condition  actionBộ nhớ làm việc (Working memory): chứa các mô tả về trạng thái hiện hành của ‘thế giới’ trong quá trình suy luậnChu trình nhận dạng – hành động (recognize-act cycle): là cấu trúc điều khiển của hệ sinh.Một số khái niệm:Luật khả thi (enable rule): là luật có các điều kiện đối sánh với các mẫu trong bộ nhớ làm việc.Tập tranh chấp (conflict set): là tập hợp tất cả các luật khả thi.Giải quyết tranh chấp (conflict resolution): chọn một luật trong tập tranh chấp để thi hành.Chương 5. p.8Kiến Trúc của Hệ SinhProduction memory (rules)Working memory (data)MATCHConflict Set (enable rules)CONFLICT RESOLUTIONEXECUTE (fire rule)Control cycleChangesChương 5. p.9Một Hệ Thống Luật Sinh Đơn GiảnCơ chế điều khiển: lặp lại cho đến khi mẫu trong bộ nhớ làm việc không còn khớp với điều khiển của bất kỳ luật sinh nào.Figure 5.4:	Trace of a simple production system.Chương 5. p.10Trò chơi ô đố 8-puzzle (1)Figure 5.5: The 8-puzzle as a production system.Chương 5. p.11Trò chơi ô đố 8-puzzle (2)Figure 5.6: The 8-puzzle searched by a production system with loop detection and depth bound 5Chương 5. p.12Trò chơi đường đi quân mã (1)Các bước đi hợp lệ của quân mã123456789Đánh số các ô trong bàn cờ 3x3RULE#CONDITIONACTION1Quân mã ở ô 1Di chuyển đến ô 82Quân mã ở ô 1Di chuyển đến ô 63Quân mã ở ô 2Di chuyển đến ô 94Quân mã ở ô 2Di chuyển đến ô 75Quân mã ở ô 3Di chuyển đến ô 46Quân mã ở ô 3Di chuyển đến ô 87Quân mã ở ô 4Di chuyển đến ô 98Quân mã ở ô 4Di chuyển đến ô 39Quân mã ở ô 6Di chuyển đến ô 110Quân mã ở ô 6Di chuyển đến ô 711Quân mã ở ô 7Di chuyển đến ô 212Quân mã ở ô 7Di chuyển đến ô 613Quân mã ở ô 8Di chuyển đến ô 314Quân mã ở ô 8Di chuyển đến ô 115Quân mã ở ô 9Di chuyển đến ô 216Quân mã ở ô 9Di chuyển đến ô 4Chương 5. p.13Figure 5.7: A production system solution to the 3  3 knight’s tour problem.Cơ chế điều khiển:Áp dụng luật đầu tiên tìm được mà không tạo vòng lặp (không đi lại ô đã đi qua).Cho phép quay lui VD: Tìm 1 con đường để quân mã đi từ vị trí 1 đến vị trí 2Trò chơi đường đi quân mã (2)Chương 5. p.14Điều Khiển TK Trong Hệ SinhChọn lựa giữa tiếp cận hướng từ dữ liệu hay hướng từ mục tiêu.Điều khiển được mã hóa trong cấu trúc các luật (tạo khả năng sử dụng heuristic)	if engine does not turn over	And the lights don’t come on	then check the batteryCơ chế điều khiển - là phương pháp chọn lựa luật để thi hành:Khúc xạ (refraction)Mới xảy ra (recency)Tính chi tiết (specificity)Thứ tự các luật được lưu trữ.Lưu ý: thứ tự của các điều kiệnChương 5. p.15Tìm Kiếm Hướng Từ Dữ LiệuFigure 5.9:	Data-driven search in a production system.Chương 5. p.16Tìm Kiếm Hướng Từ Mục TiêuFigure 5.10:	Goal-driven search in a production system.Chương 5. p.17Cơ Chế Điều khiểnKhúc xạ (refraction): một khi luật được chọn, nó sẽ không được chọn lại cho đến khi các điều kiện của nó trong bộ nhớ làm việc được thay đổi.Mới xảy ra (recency): chọn những luật khớp với các mẫu được thêm vào gần đây nhất.Tính chi tiết (specificity): chọn luật có chứa nhiều điều kiện hơn.Thứ tự các luật được lưu trữ: chọn luật khả thi đầu tiên.Chương 5. p.18Ưu Điểm của Hệ Thống Luật SinhTách biệt rõ ràng giữa tri thức và điều khiểnCung cấp một Ánh xạ tự nhiên vào TK trên KGTTMô-đun hóa các luật sinhTìm kiếm được điều khiển theo kiểu hướng mẫuTạo cơ hội sử dụng heuristic trong việc điều khiển TKCho phép lần vết và diễn giảiĐộc lập ngôn ngữLà một mô hình hợp lý mô tả việc giải quyết vấn đề của con người. Là một công cụ quan trọng để xây dựng các hệ chuyên giaChương 5. p.19Kiến Trúc Bảng ĐenMột bảng đen là một cơ sở các dữ liệu toàn cục tập trung cho sự giao tiếp giữa các tài nguyên tri thức không đồng bộ độc lập nhau tập trung vào các khía cạnh liên quan của một vấn đề nào đó.Các thành phần:Bảng đen (blackboard): là một cơ sở dữ liệu tập trung toàn cụcCác tài nguyên tri thức (Knowledge Source): độc lập không đồng bộ giao tiếp với nhau thông qua bảng đen.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: thể hiện cơ chế điều khiển (focus of attention).Bảng đen toàn cụcKS1KS2KSiKSnChương 5. p.20Ví dụ Hearsay IIMục đích: Thông dịch các câu nói với một lượng từ vựng và văn phạm giới hạn,  1000 words, 17 từ có thể theo sau bởi một từ khácGiải pháp: Tìm kiếm một không gian các phần lời giải được ghi nhận trong một cây phân cấp trừu tượng được thực hiện với một bảng đen.Tìm kiếm: tìm kiếm có cơ hộiTrên xuống + dưới lên (đưa ra giả thuyết và kiểm tra)Cơ chế điều khiển thông qua lập lịch cho các tài nguyên tri thức. (VD: Ban đầu các tài nguyên mức thấp có độ ưu tiên cao hơn, sau đó đến các tài nguyên ở mức cao có độ ưu tiên cao hơn.)Chương 5. p.21Ưu Điểm của Kiến Trúc Bảng đenMở rộng của các hệ thống luật sinh: cho phép tổ chức bộ nhớ làm việc vào các module riêng, mỗi module tương ứng với các tập con luật sinh khác nhau.Cho phép tổ chức và phối hợp nhiều chương trình giải quyết vấn đề trong một cấu trúc toàn cục duy nhất.Thích hợp cho việc thực thi chương trình trong một môi trường tính toán phân tán, đa bộ xử lý.Hổ trợ mạnh mẽ cho những ứng dụng tri thức có cấu trúc cao và mang tính cơ hội.