Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái
Chương V
ĐIỀU KHIỂN VÀ CÀI ĐẶT TÌM KIẾM
TRONG KHÔNG GIAN TRẠNG THÁI
Nội dung chính: Trong chương này, các kỹ thuật sâu hơn cho việc cài đặt các thuật toán
tìm kiếm sẽ được trình bày một cách chi tiết. Trước hết là tìm kiếm đệ quy (recursive search)
– một phương pháp thực hiện tìm kiếm sâu kèm theo lần ngược với cách thức tự nhiên và
ngắn gọn. Tìm kiếm đệ quy được tăng cường nhờ sử dụng sự hợp nhất (unification) để tìm
kiếm các không gian trạng thái do các biểu thức của phép tính vị từ sinh ra. Sự kết hợp này
cho ta thuật toán tìm kiếm hướng mẫu (pattern – directed search). Phần tiếp theo trong nội
dung chương V giới thiệu mô hình hệ sinh (production system) – một cấu trúc tổng quát để
giải các bài toán hướng mẫu, nó được sử dụng khá nhiều không những để mô hình hóa việc
giải quyết các vấn đề của con người, mà còn để xây dựng các hệ chuyên gia và những ứng
dụng Trí tuệ nhân tạo khác. Cuối cùng, một cách giải bài toán trí tuệ nhân tạo khác cũng
được đề cập đến – kiến trúc bảng đen (blackboard architecture).
Mục tiêu cần đạt : Sau chương này, sinh viên có thể :
¾ Vận dụng thuật toán tìm kiếm đệ quy kết hợp lần ngược trên không gian trạng thái.
¾ Hiểu thuật toán hướng mẫu khi thực hiện việc tìm kiếm trong không gian trạng thái.
¾ Vận dụng hệ sinh cho một bài toán.
¾ Hiểu các ưu điểm của hệ sinh
¾ Hiểu các ứng dụng kiến trúc bảng đen trong GQVĐ.
Kiến thức tiên quyết : Lý thuyết đồ thị, Các thuật toán tìm kiếm trên đồ thị, Lý thuyết trò
chơi, …
Tài liệu tham khảo :
[1] George F. Luger, William A. Stubblefield – Albuquerque – Artificial Intelligence
– Wesley Publishing Company, Inc – 1997 (Chapter 4)
[2] Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu trúc
và chiến lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần II)
[3] Recursion: http://cs-people.bu.edu/dbuzan/cs112/lab5/lab5.html
[4] Blackboard Architecture: http://www.nb.net/~javadoug/bb.htm
Võ Huỳnh Trâm – Trần Ngân Bình
79
Giáo Trình Trí Tuệ Nhân Tạo
I TÌM KIẾM DỰA TRÊN CƠ SỞ ĐỆ QUI
I.1 Tìm kiếm đệ quy
Một chuyển đổi trực tiếp của thuật toán tìm kiếm sâu thành dạng đệ quy sẽ minh họa cho sự
tương đương của đệ quy và lặp lại đơn giản. Thuật toán này sử dụng các biến toàn cục closed
và open để duy trì danh sách các trạng thái:
Function Depthsearch; % open và closed toàn cục
Begin
If open rỗng then trả lời (thất bại);
Trạng thái hiện hành := phần tử đầu tiên của open;
If trạng thái hiện hành là trạng thái đích
then trả lời (thành công)
Else
begin
Open := open - phần tử đầu tiên của open;
Closed := closed + trạng thái hiện hành;
For mỗi trạng thái con của trạng thái hiện hành do
If chưa có trong closed hay open % xây dựng ngăn xếp
then bổ sung con đó vào đầu danh sách open
end;
Tìm kiếm sâu; % đệ quy
End;
Tìm kiếm sâu như vừa được trình bày sẽ không sử dụng hết sức mạnh của phép đệ quy. Nó
vẫn còn khả năng đơn giản hóa thủ tục bằng cách sử dụng chính phép đệ quy (thay gì một
danh sách open) để sắp xếp các trạng thái trong không gian trạng thái. Trong phiên bản này
của thuật toán, một danh sách closed toàn cục sẽ được dùng để phát hiện các trạng thái lặp
lại, còn danh sách open thì tiềm ẩn trong các mẩu tin hoạt động của môi trường đệ quy.
Function Depthsearch (trạng thái hiện hành); % closed toàn cục
Begin
If trạng thái hiện hành là trạng thái đích then
trả lời (thành công);
For mỗi trạng thái hiện hành có con chưa được kiểm tra do
begin
Con := con chưa được kiểm tra kế tiếp;
If con không phải là thành viên của closed
then if depthsearch (con) = thành công
then trả lời (thành công);
end;
Trả lời (thất bại);
End; % tìm kiếm đã đến cùng
Thay vì phát sinh tất cả các con của một trạng thái và đưa chúng vào danh sách open, thuật
toán này phát sinh mỗi lần một con và tìm kiếm theo phép đệ quy các nút cháu của từng con
đó trước khi phát sinh các anh em của nó. Thuật toán này sẽ gán một thứ tự cho các bước
80 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
phát sinh trạng thái. Trong tìm kiếm theo đệ quy đối với một trạng thái con, nếu có một con
nào đó của trạng thái này là đích, thuật toán đệ quy sẽ trả lời thành công và bỏ qua tất cả các
trạng thái anh em. Ngược lại, các trạng thái anh em kế tiếp được phát sinh. Cứ như vậy thuật
toán sẽ tìm kiếm toàn bộ đồ thị lần lượt theo từng độ sâu một.
Thuật toán đệ quy cho phép bỏ qua danh sách open trong suốt quá trình thực hiện. Cơ chế
mà một ngôn ngữ lập trình sử dụng để cài đặt đệ quy là dùng mẩu tin hoạt động (activation
record) cho từng lần gọi đệ quy. Quá trình lần ngược sẽ tác động khi tất cả các con cháu của
một trạng thái không phải là đích, làm cho bước đệ quy đó thất bại. Việc thực hiện đệ quy
cho phép lập trình viên thu hẹp tầm nhìn của họ vào một trạng thái duy nhất cùng với các
con của nó thay vì phải duy trì một danh sách open gồm nhiều trạng thái.
Tìm kiếm trong không gian trạng thái là một quá trình đệ quy. Để tìm đường đi từ trạng thái
hiện hành đến đích, bạn chuyển đến một trạng thái con và thực hiện phép đệ quy. Nếu trạng
thái con đó không dẫn đến đích, bạn thử lần lượt các trạng thái anh em của nó. Phép đệ quy
sẽ chia một bài toán lớn và khó (tìm kiếm khắp không gian) thành các bài toán nhỏ và đơn
giản hơn (phát sinh các con của một trạng thái) và áp dụng chiến lược đệ quy cho từng bài
toán nhỏ đó. Quá trình cứ tiếp tục như vậy cho đến khi phát hiện được đích hoặc hết không
gian.
I.2 Tìm kiếm hướng mẫu (Pattern – directed search)
Trong phần này chúng ta sẽ áp dụng tìm kiếm đệ quy vào không gian các suy diễn logic, kết
quả sẽ là một thủ tục tìm kiếm tổng quát dùng cho phép tính vị từ.
Giả sử cần phải viết một thuật toán để xác định xem một biểu thức phép tính vị từ cho trước
có phải là kết quả logic của môt tập các khẳng định nào đó hay không. Thuật toán này phải
tìm một trình tự suy diễn tạo nên biểu thức đích. Thuật toán sẽ đề nghị một tìm kiếm hướng
mục tiêu với câu hỏi ban đầu tạo nên đích và các modus ponens xác định các chuyển tiếp
giữa các trạng thái. Cho trước một đích, thuật toán sẽ dùng phương pháp đồng nhất để chọn
các phép kéo theo có kết luận phù hợp với đích đó. Sau khi đồng nhất đích với kết luận của
phép kéo theo và đã áp dụng các thay thế vừa suy ra được, tiền đề của phép kéo theo sẽ trở
thành một đích mới gọi là đích phụ (subgoal). Sau đó thuật toán sẽ thực hiện đệ quy đối với
đích phụ này. Nếu đích phụ phù hợp với một sự kiện trong cơ sở tri thức, cuộc tìm kiếm kết
thúc. Chuỗi suy diễn dẫn từ đích ban đầu đến các sự kiện cho trước sẽ chứng minh đích xuất
phát là đúng.
Phiên bản hoàn chỉnh của thuật toán tìm kiếm hướng mẫu có thể trả lời một tập các đồng
nhất thỏa mãn từng đích phụ là:
Võ Huỳnh Trâm – Trần Ngân Bình
81
Giáo Trình Trí Tuệ Nhân Tạo
Function pattern_search(current_goal);
Begin
If current_goal ∈ closed then return fail
else Thêm current_goal vào 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 (q → p):
begin
áp dụng phép thế đồng nhất mục tiêu vào tiền đề (q);
pattern_search (q);
if pattern_search thành công
then return hợp của tập phép thế của p và q;
else return fail;
end;
current_goal có dạng (p1∧ p2 …):
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;
current_goal có dạng (p1∨ p2…):
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;
82 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
II HỆ THỐNG LUẬT SINH (HỆ SINH –
PRODUCTION SYSTEM)
II.1 Định nghĩa hệ sinh
Hệ sinh là một mô hình tính toán quan trọng trong trí tuệ nhân tạo về cả hai mặt: thực hiện
các thuật toán tìm kiếm và mô hình hóa việc giải các bài toán của con người.
Một hệ sinh được định nghĩa bởi:
1. Tập luật sinh (Production rules): Mỗi luật sinh có dạng condition → action (điều
kiện → hành động). Phần điều kiện của luật là một mẫu cho biết khi nào thì có thể áp
dụng luật. Phần hành động quy định các bước giải toán tương ứng điều kiện.
2. Bộ nhớ làm việc (Working memory): Chứa một mô tả về trạng thái hiện thời của
bài toán trong quá trình suy luận. Mô tả này là một mẫu sẽ được đối sánh với phần
điều kiện của một luật sinh để chọn ra bước giải thích hợp. Khi phần điều kiện của
luật phù hợp với nội dung trong bộ nhớ làm việc, hành động phát sinh từ điều kiện đó
sẽ được thực hiện làm thay đổi nội dung bộ nhớ làm việc.
3. Chu 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.
Cấu trúc điều khiển của một hệ sinh khá đơn giản: Bộ nhớ làm việc được khởi đầu với mô tả
của bài toán. Trạng thái hiện hành của việc giải bài toán được duy trì dưới dạng một tập các
mẫu trong bộ nhớ làm việc. Các mẫu này được đối sánh với phần điều kiện của các luật sinh,
các luật có điều kiện phù hợp với mẫu trong bộ nhớ làm việc được gọi là tập luật tranh chấp
(conflict set). Sau đó một trong các luật sinh này sẽ được chọn và được kích hoạt. Để kích
hoạt một luật, phần hành động của nó được thục hiện và làm thay đổi nội dung bộ nhớ làm
việc. Chu trình điều khiển sẽ lặp lại với nội dung đã được thay đổi trong bộ nhớ làm việc.
Quá trình này kết thúc khi nội dung của bộ nhớ làm việc không còn phù hợp với điều kiện
của luật nào nữa.
Một quá trình giải quyết tranh chấp (conflict resolution) sẽ chọn một luật từ tập luật tranh
chấp để kích hoạt. Chiến lược giải quyết tranh chấp có thể rất đơn giản như chọn luật đầu
tiên có điều kiện phù hợp hoặc có thể dựa vào các heuristic chọn luật phức tạp. Đây là một
khâu quan trọng để các hệ sinh có thể đưa khả năng điều khiển heuristic vào một thuật toán
tìm kiếm.
Một sơ đồ của hệ sinh được mô tả như hình sau:
Võ Huỳnh Trâm – Trần Ngân Bình
83