HÀNG ĐỢI

1
CÁC KỸ THUẬT TÌM KIẾM HEURISTIC
HEURISTIC SEARCH TECHNIQUES
2
NỘI DUNG
Sinh ra và Kiểm thử (Generate-And-Test)
Leo đồi (Hill-Climbing)
Tìm kiếm Tốt nhất Đầu tiên (Best-First Searche)
Suy giảm vấn đề (Problem Reduction)
Thỏa mãn ràng buộc (Constraint Satisfaction)
Phân tích Means-Ends (Means-Ends Analysis)
3
SINH RA VÀ KIỂM THỬ (1)
(Generate-And-Test)
Sinh ra một bước giải có thể (sinh ra một điểm trong không gian trạng thái / sinh ra một đường đi xuất phát từ trạng thái khởi đầu)
Kiểm thử « đạt tới lời giải chưa » (so sánh điểm được sinh ra / đầu mút cuối của đường đi với các trạng thái đích)
Nếu một lời giải được tìm thấy, thoát, nếu không quay lại bước 1.
4
SINH RA VÀ KIỂM THỬ (2)
(Generate-And-Test)
Toán tử « sinh ra » là toán tử có tính hệ thống, bao gồm tất cả các toán tử có thể, thuật toán là thuật toán vét cạn
Toán tử « sinh ra » là một sự « sinh ra » ngẫu nhiên, không có gì đảm bảo có thể tìm thấy lời giải.
Toán tử « sinh ra » là có hệ thống nhưng một số « điểm » được sinh ra không được « khai thác » vì bị « cảm thấy » không dẫn đến đích. Việc đánh giá « khả năng một điểm được sinh ra nằm trên đường đi lời giải » được cho bởi một hàm heuristic
Tổ hợp phương pháp « sinh ra và thử » với các kỹ thuật « hạn chế không gian » khác thường cho ra một giải pháp hiệu quả
5
LEO ĐỒI
(Hill-Climbing)
Một biến thể của thuật toán « sinh ra và kiểm thử », trong đó sự phản hồi từ thủ tục « kiểm thử » được sử dụng để trợ giúp « thủ tục sinh » / « toán tử sinh » quyết định « hướng » di chuyển trong không gian tìm kiếm
Hàm kiểm thử được tăng cường một hàm heuristic (hàm mục tiêu), hàm này ước lượng trạng thái được xét « cách đích bao xa », thủ tục sinh khai thác thông tin này để quyết định hướng « triển khai »
Leo đồi thường được dùng khi có sẵn một « hàm heuristic tốt », nhưng không có sẵn tri thức hữu dụng khác
6
LEO ĐỒI ĐƠN GIẢN (1)
(Simple Hill-Climbing)
Đánh giá trạng thái khởi đầu. Nếu nó là trạng thái đích, thoát, nếu không xét nó như trạng thái hiện hành
Lặp lại đến tận khi tìm thấy một lời giải hoặc đến tận khi không tìm thấy « toán tử » mới nào có thể áp dụng lên trạng thái hiện hành:
Chọn một toán tử chưa được áp dụng đối với trạng thái hiện hành, áp dụng nó để sinh ra một trạng thái mới NS
Đánh giá trạng thái mới NS
Nếu NS là một trạng thái đích, return NS và thoát
Nếu NS không là đích nhưng « tốt hơn » trạng thái hiện hành, lấy NS làm trạng thái hiện hành
Nếu NS không tốt hơn trạng thái hiện hành, tiếp tục vòng lặp
7
LEO ĐỒI ĐƠN GIẢN (2)
(Simple Hill-Climbing)
Hàm đánh giá là « phương tiện » để đưa « tri thức nhiệm vụ cụ thể » vào quá trình điều khiển
Hàm đánh giá là « độ đo » tính tốt hơn của một trạng thái so với trạng thái khác

8
LEO ĐỒI DỐC ĐỨNG (Steepest-Ascent HC) / TÌM KIẾM GRADIENT
Đánh giá trạng thái khởi đầu. Nếu nó là trạng thái đích, thoát, nếu không xét nó như trạng thái hiện hành
Lặp lại đến tận khi tìm thấy một lời giải hoặc đến tận khi trạng thái hiện hành không thay đổi:
SUCC = một successor của trạng thái hiện hành (CURRENT)
For (mỗi toán tử có thể áp dụng vào trạng thái hiện hành)
Áp dụng toán tử lên trạng thái hiện hành để sinh ra một trạng thái mới
Đánh giá trạng thái mới. Nếu nó là một trạng thái đích, return nó và thoát. Nếu không, so sánh với SUCC, nếu nó tốt hơn, đặt SUCC là trạng thái này
Nếu SUCC tốt hơn CURRENT, đặt CURRENT = SUCC
9
THUẬT TOÁN LEO ĐỒI (1)
(Hill-Climbing)
Thuật toán leo đồi có thể kết thúc mà không tìm thấy một trạng thái đích, chỉ đạt tới một trạng thái từ nó không một trạng thái tốt hơn nào được sinh ra:
Cực trị địa phương (Local Optimum)




10
THUẬT TOÁN LEO ĐỒI (2)
(Hill-Climbing)
Cao nguyên (Plateau)




Chỏm (Ridge)
(chỉ với một phép toán, không cho ra trạng thái « tốt hơn », nhưng với một vài phép toán có thể chuyển đến trạng thái « tốt hơn » )
11
THUẬT TOÁN LEO ĐỒI (3)
(Hill-Climbing)
Một vài giải pháp xử lý các vấn đề này:
Quay lui « một vài bước » trước đó và thử đi theo một hướng khác. Để thực thi chiến lược này, duy trì một danh sách các bước đã trải qua. Giải pháp này đặc biệt phù hợp để xử lý tình huống « Local Optima »
Tạo ra một « bước nhảy đột phá » theo một hướng: để chuyển sang một « vùng » mới trong không gian tìm kiếm. Phù hợp để xử lý tình huống « Plateau »
Áp dụng nhiều hơn một toán tử để nhận được một trạng thái sau đó mới kiểm thử. Phù hợp để xử lý tình huống « Ridge »
12
MÔ PHỎNG SỰ TÔI LUYỆN (1)
(Simulated Annealing)
Đánh giá trạng thái khởi đầu. Nếu nó là trạng thái đích, thoát, nếu không xét nó như trạng thái hiện hành
Khởi động BEST-SO-FAR đối với trạng thái hiện hành
Khởi động T tương ứng với « lịch biểu tôi luyện »
Lặp lại đến tận khi tìm thấy một lời giải hoặc đến tận khi không có toán tử mới nào có áp dụng vào trạng thái hiện hành:
Chọn một toán tử chưa được áp dụng vào trạng thái hiện hành, áp dụng nó để sản sinh ra một trạng thái mới (NS)
Đánh giá trạng thái mới
13
MÔ PHỎNG SỰ TÔI LUYỆN (2)
(Simulated Annealing)
Tính E = (giá trị trạng thái hiện hành) – (giá trị trạng thái NS)
Nếu NS là một trạng thái đích, return NS và thoát
Nếu NS không là đích nhưng tốt hơn trạng thái hiện hành, lấy NS làm trạng thái hiện hành, đặt BEST-SO-FAR cho NS.
Nếu NS không tốt hơn trạng thái hiện hành, NS sẽ được lấy làm trạng thái hiện hành với xác suất:

(Gọi một hàm sinh số ngẫu nhiên để sinh ra một số r [0, 1], nếu r < p thì lấy NS làm làm trạng thái hiện hành)
Duyệt lại T khi cần thiết tương ứng với « lịch biểu tôi luyện »
Return BEST-SO-FAR

14
MÔ PHỎNG SỰ TÔI LUYỆN (3)
(Simulated Annealing)
Để thực thi thuật toán « duyệt lại », cần chọn một « lịch biểu tôi luyện » có ba/bốn thành phần:
Giá trị khởi đầu được dùng làm « nhiệt độ » ban đầu của hệ thống
Tiêu chuẩn giảm dùng để quyết định khi nào giảm « nhiệt độ » hệ thống
Lượng nhiệt giảm cho mỗi lần giảm « nhiệt độ »
Giá trị « thoát »: khi « nhiệt độ » giảm đến giá trị này thì « thoát »
15
TÌM KIẾM TỐT NHẤT ĐẦU TIÊN (1)
(Best-First Search)
Ý tưởng của tìm kiếm tốt nhất đầu tiên là lặp lại bước sau:
Chọn nút « hứa hẹn nhất » trong tập các nút được sinh ra: Sử dụng một hàm heuristic (hàm đo « tính hứa hẹn » của mỗi nút)
Triển khai nút được chọn: áp dụng các luật sinh/ toán tử sinh để sinh ra các successor của nó. Nếu một trong các successor này là đích, thoát, nếu không thêm các successor này vào tập các nút được sinh ra. Lặp lại bước 1.
16
TÌM KIẾM TỐT NHẤT ĐẦU TIÊN (2)
(Best-First Search)
Thuật toán tìm kiếm tốt nhất đầu tiên sử dụng:
OPEN: Các nút được sinh ra, giá trị hàm ưu tiên của nút đã được tính, nhưng chưa được triển khai, được tổ chức như một hàng ưu tiên (độ ưu tiên là giá trị hàm heuristic của nút)
CLOSED: Các nút đã được triển khai
Hàm heuristic f’, ước lượng « giá trị » của mỗi nút được sinh ra, f’ là một xấp xỉ của một hàm f cho ra đánh giá thực của nút
Trong nhiều ứng dụng, f’ được phân tích thành hai thành phần: g và h’.
Hàm g là độ đo « giá » phải trả để đi từ trạng thái khởi đầu đến trạng thái hiện hành (tổng giá của việc áp dụng các quy tắc sinh được áp dụng dọc theo đường đi đến nút hiện hành).
Hàm h’ là một ước lượng giá bổ xung để « đi » từ trạng thái hiện hành đến một trạng thái đích
17
TÌM KIẾM TỐT NHẤT ĐẦU TIÊN (3)
(Best-First Search)
OPEN = {Start}
Lặp lại đến tận khi tìm thấy một đích hoặc OPEN trở nên rỗng
Rút ra nút tốt nhất trong OPEN
Sinh ra các successor của nó
For mỗi successor do
Nếu nó chưa được sinh ra, đánh giá nó, thêm nó vào OPEN, ghi nhớ « cha » của nó
Nếu nó đã được sinh ra, thay đổi « cha » nếu đường đi mới tốt hơn đường đi cũ, cập nhật giá để đạt tới nút này và tới các successor
18
Tìm kiếm tốt nhất đầu tiên (4) - (Best-First Search)
THUẬT TOÁN A*
Khởi động:
OPEN = {Start}; g(Start) = 0; h’(Start) = …; CLOSED ={}
Đến tận khi tìm thấy một nút đích lặp lại thủ tục sau:
Nếu không còn nút nào trong OPEN thông báo FAIL
Khác đi,
Chọn nút trong OPEN với giá trị f’ thấp nhất, gọi nó là BEST_NODE
Xóa nó khỏi OPEN
Đặt nó vào CLOSED
Kiểm tra nó có phải nút đích không? Nếu đúng, thông báo lời giải và thoát. Nếu không, sinh ra các successor của BEST_NODE. Đối với mỗi successor tiến hành các công việc sau:
19
Tìm kiếm tốt nhất đầu tiên (4) - (Best-First Search)
THUẬT TOÁN A*
Đặt « nối kết cha » của successor trỏ về BEST_NODE
Tính g(successor)=g(BEST_NODE)+giá đi từ BEST_NODE đến successor
Kiểm tra trong OPEN có nút nào trùng với successor? Nếu có, gọi nút đó là OLD, vứt bỏ successor, thêm OLD vào danh sách các successor của BEST_NOED. Nếu đường đi đến successor vừa tìm thấy có giá thấp hơn giá của đường đi tốt nhất hiện thời đến OLD, đặt lại « nối kết cha » của OLD về BEST_NODE, ghi lại giá tốt hơn vào g(OLD), cập nhật f’(OLD)
Nếu successor không trùng với nút nào trong OPEN, kiểm tra successor có trùng với nút nào CLOSED không? Nếu có, gọi nút đó là OLD, thêm OLD vào danh sách các successor của BEST_NODE. Nếu đường đi đến successor vừa tìm thấy có giá thấp hơn giá của đường đi tốt nhất hiện thời đến OLD, đặt lại « nối kết cha » của OLD về BEST_NODE, ghi lại giá tốt hơn vào g(OLD), cập nhật f’(OLD), lan truyền sự thay đổi này đến các « hậu duệ » của OLD, sự lan truyền này dừng lại tại các nút không successor hoặc các nút sự lan truyền đến nó không làm tốt hơn đánh giá hiện có của nút.
Nếu successor chưa có cả trong OPEN lẫn CLOSED, đặt nó vào OPEN, thêm nó vào danh sách các successor của BEST_NODE, tính f’(successor)
20
TÍNH CHẤT CỦA THUẬT TOÁN A*
E là một không gian trạng thái, @1 và @2 là hai thuật toán A* có thể áp dụng vào E. h’1 và h’2 là hai heuristic tương ứng. Ta nói rằng thuật toán @2 được thông tin tốt hơn @1 nếu n, không là trạng thái đích: h’1(n) < h’2(n)
Nếu thuật toán A* @2 được thông tin tốt hơn thuật toán A* @1 thì mỗi trạng thái được triển khai bởi @2 khi áp dụng nó vào E cũng được triển khải bởi @1 khi áp dụng nó vào E. Tập hợp các trạng thái của đồ thị tìm kiếm kết thúc nhận được bởi @2 chứa trong tập hợp các trạng thái của đồ thị tìm kiếm kết thúc nhận được bởi @1
21
VÍ DỤ 8-PUZZLE
Trạng thái khởi đầu Trạng thái đích




Hàm đánh giá f’(m) = số ô số của trạng thái m không ở vị trí đúng của nó so với trạng thái đích
f’(trạng thái khởi đầu) = 4
f’(trạng thái đích) = 0
22
VÍ DỤ 8-PUZZLE

f’=4
f’=3
f’=5
f’=5
23
VÍ DỤ 8-PUZZLE
f’=3
f’=3
f’=3
f’=4
24
VÍ DỤ 8-PUZZLE
f’=3
f’=2
f’=4
25
VÍ DỤ 8-PUZZLE
f’=2
f’=1
f’=0
f’=2
26

f’=4
f’=3
f’=3
f’=3
f’=4
27
SUY GIẢM VẤN ĐỀ (1)
(Problem Reduction)
Phân tích vấn đề thành các vấn đề con nhỏ hơn
Mỗi vấn đề con, đến lượt nó, lại được phân tích thành các vấn đề con nhỏ hơn …
Cứ như vậy đến khi đạt tới vấn đề con, lời giải của nó có thể được tìm thấy ngay (vấn đề sơ cấp)
Sự phân tích/ suy giảm này có thể được biểu diễn bởi một đồ thị định hướng, được gọi là đồ thị AND-OR:
Mỗi vấn đề được biểu diễn bởi một nút của đồ thị
Biểu diễn mối quan hệ «  vấn đề cha được giải quyết nếu một tập các vấn đề con của nó cùng phải được giải quyết » bởi một tập các cung từ cha đến các con tương ứng, các cung này được nhóm lại bởi một cung tròn. Nhóm các cung này được gọi là cung AND
Biểu diễn mối quan hệ «  vấn đề cha được giải quyết nếu chỉ cần giải quyết một vấn đề con » bởi một cung đơn từ cha đến con và được gọi là cung OR
28
SUY GIẢM VẤN ĐỀ (2) - (Problem Reduction)
ĐỒ THỊ AND-OR
Có một xe hơi
ăn trộm một xe hơi
Kiếm đủ tiền
Mua một xe hơi
Làm việc
Để dành tiền
Cướp nhà băng
29
SUY GIẢM VẤN ĐỀ (3) - (Problem Reduction)
THUẬT TOÁN
Khởi động GRAPH bởi một nút khởi đầu
Lặp lại đến tận khi nút khởi đầu được gán nhãn SOLVED (giải được) hoặc đến tận khi giá của nó vượt quá FUTILITY:
Duyệt đồ thị, bắt đầu từ nút khởi đầu, theo đường đi tốt nhất hiện hành, tính gộp « giá » của các nút chưa được triển khai hoặc được gán nhãn SOLVED trên đường đi này
Lấy một nút chưa được triển khai, triển khai nó. Nếu nó không có successor, gán FUTILITY cho nó. Nếu nó có successor, thêm các successor vào đồ thị, tính f’ của mỗi successor. Nếu f’ của nút nào có giá trị 0, gán cho nút đó nhãn SOLVED.
Thay đổi f’ của nút vừa được triển khai. Lan truyền ngược sự thay đổi này về nút khởi đầu. Nếu một nút chứa một cung, các hậu duệ của nó tất cả được gán nhãn SOLVED, gán nhãn cho nó là SOLVED. Tại mỗi nút được viếng thăm trong quá trình lan truyền ngược, chọn cung « hứa hẹn » nhất đánh dấu nó như là một phần của đường đi tốt nhất hiện hành.
30
SUY GIẢM VẤN ĐỀ (4) - (Problem Reduction)
VÍ DỤ
A (5)
B (2)
C (4)
D (5)
E (2)
F (2)
G (5)
H (2)
J (4)
K (3)
L (5)
I (2)
M ()
N (0)
O (0)
P ()
Q (0)
R ()
S (0)
T ()
U (0)
V ()
L ()
J (0)
K ()
D ()
E (0)
B (0)
H (0)
C (0)
A (0)
31
SUY GIẢM VẤN ĐỀ (4) - (Problem Reduction)
THUẬT TOÁN AO*
Khởi động GRAPH với chỉ một nút khởi đầu, gọi nút này là INIT. Tính h’(INIT).
Đến tận khi INIT được gán nhãn SOLVED hoặc h’(INIT) vượt quá FUTILITY, lặp lại thủ tục sau:
Lần theo vết các cung được gán nhãn từ INIT, chọn một nút chưa được triển khai nằm trên dường đi này. Gọi nút này là NODE.
Sinh ra các successor của NODE. Nếu NODE không có successor, gán h’(NODE) = FUTILITY ( ~ NODE không giải được). Nếu NODE có successor, đối với mỗi SUCC của NODE, không là một tổ tiên của NODE, làm các việc sau:
Thêm SUCC vào đồ thị
Nếu SUCC là một nút kết thúc, gán nhãn nó là SOLVED, gán h’(SUCC) = 0
Nếu SUCC không là nút kết thúc, tính h’(SUCC)
32
SUY GIẢM VẤN ĐỀ (5) - (Problem Reduction)
THUẬT TOÁN AO*
Lan truyền ngược thông tin mới phát hiện: Khởi động S = {NODE}. Lặp lại thủ tục sau đến tận khi S rỗng:
Chọn trong S một nút không hậu duệ nào của nó trong GRAPH xuất hiện trong S. Nếu không có nút nào như thế, chọn một nút bất kỳ trong S. Gọi nút được chọn là CURRENT, xóa CURRENT khỏi S.
Tính « giá » của mỗi cung xuất ra từ CURRENT. Giá của mỗi cung bằng tổng các h’ mỗi nút cuối của cung cộng với giá của cung. gán h’(CURRENT) = Min({các giá của cung xuất ra từ CURRENT})
Đánh dấu đường đi tốt nhất xuất phát từ CURRENT bằng cách đánh dấu cung có giá tối thiểu.
Gán nhãn CURRENT là SOLVED nếu tất cả các nút nối với nó qua cung được đánh dấu đều được gán nhãn SOLVED.
Nếu CURRENT được gán nhãn SOLVED hoặc giá của CURRENT thay đổi. Thêm các tổ tiên của CURRENT vào S
33
THỎA MÃN RÀNG BUỘC (1)
(Constraint Satisfaction)
Nhiều vấn đề AI có thể được xem như vấn đề thỏa mãn ràng buộc: Đích là phát hiện trạng thái thỏa mãn một tập các ràng buộc đã cho.
VD:




Sự thỏa mãn ràng buộc thường làm giảm khối lượng tìm kiếm
Thỏa mãn ràng buộc là một thủ tục tìm kiếm hoạt động trong không gian các tập ràng buộc:
+
Số học mật mã (CriptArithmetic)
Ràng buộc:
Mỗi chữ tương ứng với một chữ số 0 .. 9
Các chữ khác nhau tương ứng với các chữ số khác nhau
Các chữ số làm thỏa mãn phép cộng
34
THỎA MÃN RÀNG BUỘC (2)
(Constraint Satisfaction)
Trạng thái khởi đầu chứa các ràng buộc được cho trong mô tả vấn đề
Một trạng thái đích là trạng thái đã bị ràng buộc « đủ », « đủ » được định nghĩa tùy thuộc vấn đề. Ví dụ, trong câu đố « mật mã số học » « đủ » có nghĩa là mỗi chữ được gán một chữ số duy nhất.
Thỏa mãn ràng buộc là quá trình hai bước:
Đầu tiên, các ràng buộc được phát hiện và được lan truyền xa như có thể.
Sau đó, nếu vẫn chưa có lời giải, bắt đầu tìm kiếm. Đoán một sự kiện, thêm vào ràng buộc mới, lan truyền ràng buộc …
35
THỎA MÃN RÀNG BUỘC (3) - (Constraint Satisfaction)
Thuật toán
Lan truyền các ràng buộc sẵn có: Đặt OPEN = tập tất cả các đối tượng cần phải gán trị (trong lời giải). Tiến hành các bước sau đến tận khi gặp mâu thuẫn hoặc OPEN rỗng:
Chọn một đối tượng OB trong OPEN. Tăng cường tập các ràng buộc trên OB
Nếu tập này khác với tập đã được gán cho OB trong lần kiểm tra trước hoặc OB lần đầu tiên được kiểm tra, thêm vào OPEN tất cả các đối tượng chia sẻ các ràng buộc với OB
Xóa OB khỏi OPEN
Nếu hợp các ràng buộc được phát hiện ở trên xác định lời giải, thông báo lời giải và thoát
Nếu hợp các ràng buộc được phát hiện ở trên xác định một mâu thuẫn, thông báo thất bại
36
THỎA MÃN RÀNG BUỘC (4) - (Constraint Satisfaction)
Thuật toán
Nếu 2. và 3. không xảy ra, Lặp lại đến tận khi tìm thấy một lời giải hoặc tất cả các lời giải có thể bị loại bỏ:
Chọn một đối tượng chưa được xác định giá trị, chọn một phương pháp tăng cường ràng buộc trên đối tượng
Gọi đệ quy thỏa mãn ràng buộc với tập hiện hành các ràng buộc được tăng cường thêm qua bước a)
37
THỎA MÃN RÀNG BUỘC (3) - (Constraint Satisfaction)
VÍ DỤ







Ký hiệu các số mang của cột i là Ci ( i = 1, 2, 3 )
Ci = 0 hoặc 1
Số học mật mã (CriptArithmetic)
Ràng buộc:
Mỗi chữ tương ứng với một chữ số 0 .. 9
Các chữ khác nhau tương ứng với các chữ số khác nhau
Các chữ số làm thỏa mãn phép cộng
+
38
THỎA MÃN RÀNG BUỘC (4) - (Constraint Satisfaction)
VÍ DỤ
Các quy tắc để lan truyền ràng buộc sinh ra các ràng buộc sau:
M = 1
S= 8 hoặc 9
O = 0
N = E+1
C2 = 1
N + R > 8
E <> 9
Không có thêm ràng buộc !
39
THỎA MÃN RÀNG BUỘC (4) - (Constraint Satisfaction)
VÍ DỤ
Để tiến triển thực hiện « phương pháp đoán »:
E = 2; lan truyền ràng buộc mới này ta nhận được tập các ràng buộc:
N = 3
R = 8 hoặc 9
2 + D = Y hoặc 2 + D = 10 + Y
…
40
THỎA MÃN RÀNG BUỘC (5) - (Constraint Satisfaction)
VÍ DỤ
M = 1
S= 8 hoặc 9
O = 0
N = E+1
C2 = 1
N + R > 8
E <> 9
E = 2
N = 3
R = 8 hoặc 9
2+D = Y hoặc
2+D = 10+Y
2+D = Y
N+R = 10 + E
R = 9
S = 8
C1=0
D=8+Y
(D = 8 V D = 9)
C1=1
Y=0
Y=1
D=8
D=9
…
…
…
…
41
PHÂN TÍCH MEANS- ENDS (1)
Các chiến lược tìm kiếm được giới thiệu có thể dùng cho suy diễn tiến / lui. Hướng duy diễn phải được chọn.
Kỹ thuật phân tích means-ends cho phép thực thi chiến lược trộn hai hướng suy diễn.
Quá trình phân tích means-ends tập trung vào việc phát hiện sự sai khác giữa trạng thái hiện hành và trạng thái đích. Mỗi khi sự sai khác được tách ra, chọn một toán tử để làm giảm đi sự sai khác này.
Toán tử được chọn có thể không áp dụng được vào trạng thái hiện hành. Ta dựng lên vấn đề con: tìm một trạng thái mà toán tử có thể áp dụng được. Như vậy, ta có một dây chuyền lùi, trong đó các toán tử được chọn, và sau đó dựng lên các đích con để xác lập các tiền điều kiện của các toán tử (operator subgoaling).
42
PHÂN TÍCH MEANS- ENDS (2)
Tuy nhiên, toán tử được chọn không sinh ra trạng thái đích mong muốn, ta có vấn đề con thứ hai: Đem từ trạng thái được sinh ra đến đích.
Quá trình phân tích means-ends có thể được áp dụng đệ quy
Sự sai khác có thể được gán một độ ưu tiên, sai khác với độ ưu tiên cao được xét trước sai khác với độ ưu tiên thấp
43
PHÂN TÍCH MEANS- END (3)
THUẬT TOÁN
Means-Ends-Analysis(CURRENT, GOAL)
So sánh CURRENT với GOAL, nếu không có sự sai khác giữa chúng, return
Nếu có sự sai khác, chọn sự sai khác quan trọng nhất làm giảm sự sai khác này bằng các hoạt động sau đến tận khi thành công / thất bại:
Chọn một toán tử chưa được thử nghiệm O có thể áp dụng đối với sai khác hiện hành. Nếu không chọn được, return FAIL
Thử áp dụng O đối với CURRENT. Sinh ra mô tả của hai trạng thái O_Start, trạng thái trong đó các tiền điều kiện của O được thỏa mãn và O_Result, trạng thái kết quả của áp dụng O vào O_Start
Nếu (FIRST_PART  Means-Ends-Analysis(CURRENT, O_START)) và
(LAST_PART  Means-Ends-Analysis(O_Result, GOAL)) thành công then return SUCC và kết quả là kết nối FIRST_PART và LAST_PART

C O_START O_RESULT G
O
44
PHÂN TÍCH MEANS- END (4)
VÍ DỤ
ROBOT NỘI TRỢ
Các toán tử cho phép với các tiền điều kiện và kết quả
45
PHÂN TÍCH MEANS- END (5)
VÍ DỤ
Nhiệm vụ của robot là di chuyển một cái bàn và hai chiếc ly được đặt trên bàn từ vị trí a sang vị trí b.
Trạng thái ban đầu:
at(robot, c), at(bàn, a), on(ly1, bàn), on(ly2, bàn)
Trạng thái đích:
at(robot, x), at(bàn, b), on(ly1, bàn), on(ly2, bàn)
Sự sai khác giữa trạng thái đích và trạng thái ban đầu là vị trí của cái bàn, hai toán tử làm giảm đi sự sai khác này là PUSH và CARRY …