Tài liệu Trí tuệ nhân tạo

ĨS . ĐINH MẠNH TƯÒNG TRÍ TUỆ NHÂN TẠO Q p NHÀ XUẤT BẢN KHOA H Ọ C V À KỸ THUẬT HÀ NÔI - 2002 M Ụ C LỤ C Trang IẨ)1 N Ó I Đ Ẩ U ............................................................................................................................................. " NliẬt> M Ó N ................................................................................................................. 9 Phồn I GIẢI Q U Y Ế T VẤN Đ Ể BANG TÌM K IE M Chương 1. CÁC CHIẾN lA/ỢC TÌM KIẾM M Ù .............................................19 1.1. ííiểu diỗn vấn dề trong không gian trạng t h á i ................................19 1.2. Các chiến lược lìm k i ế m .......................................................................22 1.3. Cát chiến lược lìm kiếm m ù ................................................................ 2õ 1.3. ]. Tìm kiếm theo bề r ộ n g ....................................................... 26 1.3.2. Tìm kiếm theo độ s â u ........................................................ 28 1.3.3. Các trạ n g ihái l ặ p .............................................................. 29 1.3.4. Tìm kiôrn sâu l ặ p .................................................................30 1.4. í^iy vấn dề vế các vấn để con. Tìm kiếm trên đồ thị và/hoặc ....31 1.4.1. Quy vấn để vể các vấn đề c o n .......................................... 31 1.4.2. ĩ)ồ thị v à /h o ặ c .......................................................................34 ] .4.3. Tìin kiếm trên đồ thị v à / h o ặ c .......................................... 38 Chương 2. C Á r C m Ế N LƯỢC TÌM KIẾM k i n h N í l H í Ệ M .....................40 2.1. lỉàm (tánh giá và tìm kiếm kinh n g h i ệ m ........................................ 40 2:1. Tìm kiếni tô’t nhrấl - (ỉầu t i è n ..............................................................42 2.3. Tìm kiếm leo (ỉồi....................................................................................44 2. \. Tìm kiếm b e a m ......................................................................................45 Chương. 3 ('ÁC C ỉ l l Ế N L.ƯỢ(" TÌM KlẾ M T ố l ư u .......................................47 3.1. Tìm dường đi ngắn n h ấ t ...................................................................... 47 3.1.1. T h u ậ t toán A * ......................................................................... 49 3.1.2. T h u ậ t toán tìm kiêm n h á n h - và -c ậ n ........................... 52 3.2. Tìm dôì iượng tốt n h ấ t ........................................................................ 54 3.2.1. Tìm kiếm leo d ồ i .....................................................................54 4 ________ ___________ _ ___ ______________________________________ TRÍ TUỆ N H Â N T Ạ O 3.2.2. Tìm kiếm g r a d i e n t .................................................................. f)6 3.2.3. Tìni kiếm mô phỏng luyện k i m ................ .......................... 56 3.3. Tìm kiếm mô Ị)hỏng sự liên hóa. T h u ậ t toán di truyền ..............58 Chương 4. TÌM KIẾM c ó Đ ố l T H Ử ................................ .................................... 4.1. Cây trò chời và tìm kiếm trên cây trò c h ơ i .................................... 66 4.2. Chiến lược M in im a x ............................................................................. 69 4.3. Phương pháỊ) cắt cụt alpha - b e ta ...........................................................75 Phồn II T R I T H Ứ C VÀ L Ậ P LU Ậ N Chương 5. LOGIC MỆNH Đ Ể .............................................. ..............................80 5.1. Biểu diễn tri thức................................. ..................................................80 5.2. Cú pháp và ngữ nghĩa của logic mệnh đề.......................................82 Õ.2.1. Cú p h á p ......................................................................................82 Õ.3.2. Ngữ n g h ĩ a ........ .................... ................... ............................... 83 5.3. Dạng chuẩn t ấ c .......................................................................................86 5.3.1. Sự tưởng đương của các công t h ứ c .... ............................... 86 0.3.2. Dạng chuẩn t ắ c .........................................................................87 5.3.3. Các câu Horn .............................................................................88 5.4. Luật suy d i ễ n .......................................................................................... 88 5.5. Luật phân ^ ả i. chứng minh bác bỏ bàng luật phân g i á i ............. 92 Chương 6. LOGIC VỊ TỪ CẤP M Ộ T ................................................................ 96 6.1. Cú pháp và ngữ nghĩa của logic vỊ từ cấp m ộ t ........................... í)7 6.1.1. Cú p h á p .......................................................................................97 6.1.2. Ngử n g h í a ..................................................................................... ......... 99 6.2. Chuẩn hoá các công thức.................................................................... 102 6.3. Các luạl suy d i ễ n ................................................................................105 6.4. Thuật toán hợp nhâ^t................................................................ ........ 108 6.5. Chứng minh bằn^ luật phán g i ả i ..................................................... 112 6.6. Các chiến lược phân g i ả i .....................................................................117 G.6.1. Chiên lược phân giải theo bể r ộ n g ................................ 119 6.6.2. Chiên lược p h ân giải sử d ụn g lập hỗ trỢ..................... 119 6.6.3. Chiến lược tuyến t í n h ....................................................... 121 6.7. Sử dụng logic vị từ cấp một để biểu diễn tri t h ứ c .....................121 6.7.1. Vị từ b ằ n g ............................................................................. 122 M Ụ C L Ụ C ____________________________________________________ __________________________ ___________________________ 5 (>.7.2. Dỉuih sách và các ịỉhÓỊ) tf)í'm tì‘ón cianh s á c h ............... 122 ().s. Xây (iựn^ (’(ỉ sỏ tri thức.........................................................................126 B.9. Cài đặt i'd sớ tri thức....................................................................... 129 (ì.9.1. ('àĩ ([ạt các h ạ n g lliức và (‘ác c â u Ị)hán t ử ..................... 130 (ì.9.2. Cài tiặt cơ sỏ tri thứr,.,......................................................... 133 Chương 7. lilỂU DIỂN TRI TỈỈỨC' n o i ('A(' LUẬT VÀ LẬP LUẬN..IMG 7.1. Hiêu tliỄn t n thứí' hdi :ÍU' liiậl nêu - t h ì ................................................ 136 7.2. ỉ.ậị) liỉộn úôn và lỘỊ) luận lùi tron^ các hộ dựa tréĩì l u ậ t .........138 7.1^. 1. LẠị) luận í-iôn............................................................................ 138 7.2.2. LẠị) luận l ù i ............................................................................... 141 I.Ạịì luận lùi Ìihiì íim kiêm trôn dồ thì v à / h o ặ c ........... 143 7.3. Thù tục lạp luận t iế n ........................................... ............................. 145 7.3.1. Thu tục F o r j ' h a i n ............................................................. 146 7.3.2. Thủ tục r e t o ............................................................................. 149 7..Ỉ.3. Ilộ hành (ỉộng dựa trôn l u ậ t ........... ................................. 155 7.1. Thu lục lập luậìi lù i ....................... ....................................................157 7 ."). Hi e u d i ễ n Iri t h ứ c k h ô n g chắ(' c h ã n ......................................................161 7.6. Hộ lập trình logic................................................................................ 163 7.7. llộ chuyên ..................................................................................... 165 Chương 8. l o c k ; KHỒNC đ ơ n đ i ệ u ....................................................... 168 K. 1. I.Ạị) kiậỉi có thê xem xél lại và lopc không đơn diộu .................... 168 5.2. \)'ãv íiiỏm cúa logic không dơiì diộu.................................................170 HM mặc đ ị n h ............... ...................................................................172 8.-1. (ỉiá íhiêt thê giới dóng....................................................................... 177 B.T). Hỏ sun;; vị l ừ ...............................................................................................179 8.(ỳ ỉỉạn (‘hô [)hạiìì v i ............... ........................................................................ 181 Chư(ỉng9. LƯOl N C Ử N C H ỈA V À Ỉ I Ệ K Ỉ Ỉ Ư N í;......................................... 184 9.1 X^ỎỈI ĨÌỊ^Í mỏ là khái n i ệ m ................ ............................................. 184 9.2. Lưới ìi^nỉ ng h ĩa.................................................................................... 187 9.:i K huĩi^................................................ ................................................... Ỉ93 Chương 10. TKI THỨC KHv3NG ( ’Ỉ1Á(^ (;HẢN........................................ 198 10.1. Klìỏn^^ chắc chan và biểu diỗn.............................................. ......198 10.2. Một số khíú niộnì cơ bản của ly thuyôt xác s u ấ t ....................... 200 10. ^ Mạii^ xác suáì................................................................................ 6 ________________________________________________________ 10.3.1. 10.3.2. 10.3.3. 10.3.4. _ T R Í TUỆ N HÂNi T Ạ O Định nghĩa m ạng xác s u ấ t ...............................................209 Vấn đê lậ]) luận trong m ạng xác s u â \ ..........................212 Khả năng biểu diễn của m ạng xác s u ấ l .................... 211 Sự độc lập của các biến trong m ạ n g xác suất............ ‘j l 6 10.4. Suy diễn trong mạng có câu trúc c â y ........................................... ’3 18 10.5. Mạng kết nôì đ đ n .............................................................................. 'J2õ 10.6. Suy diễn trong mạng đa kết n ô i .................................................... 232 10.6.2. Biên đổi m ạng đa kết nôi th à n h m ạng kết nôi đơn 233 10.6.3. Phương pháp mô phỏng ngẫu n h i ê n ........................... 234 10.7. Lý thuyết quyết đ ịn h ........................................................................- 3 9 Chương 11. LOGIC MỜ VÀ LẬP L U Ậ N XẤP x ỉ ............................................ 1!46 11.1. Tập m ò .................................................................................................247 11.1.1. Khái niệm tập m ò .............................................................. 2!47 11.1.2. Một sô khái niệm cơ bản liên quan tới tập m ờ .......21Õ1 11.1.3. Tính mò và tính ngẫu n h i ê n ........................................... 21Õ4 11.1.4. Xác định các hàm t h u ộ c ................................................... 2;55 11.2. Các phép toán trên tập mò............................................................260 11.2.1. Các phép toán chuẩn trên tập m ò ................................ 2:60 11.2.2, Các phép toán khác trên tập m ò .................................... 2:62 11.3. Quan hệ mờ và nguyên lý mở r ộ n g ................................................ 267 11.3.1. Q uan hệ m ờ .......................................................................2!67 11.3.2. Hợp t h à n h của các q u an hệ m ờ ..................................2Ỉ68 11.3.3. Nguyên lý mở rộ n g ..........................................................2;70 11.4. Logic mò...............................................................................................271 11.4.1. Biến ngôn ngữ và mệnh đê m ò ................................... 2:71 11.4.2. Các mệnh dề mò hỢp i h a n h ............................................ 2:74 11.4.3. Kéo theo mờ - L uậl if-then m ò ................................ 2:75 11.4.4. Luật Modus - Ponens tổng (ịu át................................ 2!79 14.5. Hệ mờ.......................................................................................... ......2Ỉ81 14.5.1. Kiến trúc của hệ m ờ ....................................................... 2ĩ82 14.5.2. Cớ sở luật mờ.................................................................... 2:8.'i 14.5.3. Bộ suy diễn m ờ................................................................ 2:84 H.5,4. Mò h ó a .................., ............................................................2;86 11.Õ.5. Khử m ò ...............................................................................2:88 11.Õ.6. Hệ mờ là hệ tính xấ|) xi' vạn n ă n g .............................2:89 TÀI LIÊU THAM K H Ả O .....................................................................................2:90 LÒI N Ó I ĐẨU Trí tuộ n h â n tạo (TTNT) là một lĩỉih vực của khoa học máy tính, nghiên cứu sự thiêt k ế các lá(‘ nh ân thông minh (“Computational intelligence IS the study 0 Í' the design of intelligent agents'’)- Các áp dụng của T T N T rất đa dạng và phong phú, hiện nay đã có nhiều hệ ihông minh ra đòi: các hệ chuyên gia, các hệ điều khiên tự động, các robot, các hệ dịch tự động các ngôn ngữ tự nhiên, các hệ n h ặ n dạng, các chướng Lrình chơi cò,... Kỹ t h u ậ t của T T N T đã được sử dụng trong việc xây dựng các hệ mểm nhằm tạo ra các hộ môm m an g yếu tô^ thông minh, linh hoạt và tiộn dụng, ở nước ta, trong các năm gần đây, T T N T đã được (lưa vào chương Irình giảng dạy cho sinh viên các năm cuôì ngành Tin học và Công nghệ thông tin. Cuôn sách này được hình th à n h trẽn cơ sở í‘ác giáo Irình T T N T mà chúng tôi đã giảng dạy cho sinh viên và cho các lớp cao học n g à n h Tin học và Công nghệ thông tin trong các nám học từ 1997 tdi nay, tại khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, nay là khoa Công nghệ. Đại học Quốc gia Hà nội. Cuôn sách này được viết như một cuôn n h ậ p môn về T T N T , đôi tượng phục vụ chủ yếu của nó là sinh viên các ngành Tin học và Công Iighộ thỏìig lin. Nội d ư n g c u ỏ n sach góm hai phấn: • Phần /; Gidi quyết vấn đế hằng tim kiếm. Trong ph ần nằy, chúng tôi trình bày các phương pháp biểu diền vấn đề và các kỹ th ụ ậ t t^rụ lỹiện%. Ọíự. ậặ,c Jữiệt^là tìm kiêm kinh nghiộm (heuristic search), được sử dụng thưòng xuyên trong nhiều lĩnh vực ìighiên cứu của TTN T. • Phần 2: Biển dién tri thức và láp luận. P h ầ n này đề cập đên các ngôn ngữ biểu diễn t n thức, đặc biột là các logic và các phường pháp IẠị) luận trong mỗi ngôn ngữ biểu diễn t n thức. Các kỹ th u ậ t biếu diỗn tri thức và lập luận đóng vai trò q u an trọng trong việc thiết các hệ thông minh. ®______________________________________________________________ ______ TRÌ TUỆ N H Â N L Ạ O Tuy nhiên với mong muôn cuỏn sách này có Ihê clùii^^ làin tài hiịni tharn khảo cho một phạm vi rộn^^ rãi các độc giầ, C’húnfí tôi cô t n ii!', bày một cách hệ thống cáo khái niệm và các kỹ tliuật cơ bán cua 7 7 ’Av7’. n h à m s n ip (’ho độc giả có cơ sỏ dể di vào nghipn cứu các lĩnli vựr c h u v ô n sá u của T T N T . chăng liạn nhu’ lậỊ) kê hoạch (Ị)lanMìiig), họ(' niiá\' (machine learning), nhìn máy (computer V i s i o n ) , hiếu ngôn ngừ tụ Iihiiôn ( n a tu ra l language underslanding). Hai ngôn ngữ thao lác ký hiộu dược sử dụng nhiều trong lập trì nh T T N T là Lisp và Prolog. Trong các sách viết về T T N r các năm gần điây. một sô tác gui, chăng h ạ n trong [5] và [7], dã sử d ụ n g Common List) (lô mô tả t h u ậ t loán. Trong [20], các táo giả lại sử dụng Prolog để biểu diiễii t h u ậ t toán, ơ nước ta. các ngôn ngữ Lisp và ỉ^rolog được lì n^ưòi đên, vì vậy chúng tôi biêu ciiỗn các th u ậ t toán troiig sách này theo i:’ái('h Iruyên thông. Tức là chúng tôi sử dụng các cấu trúc điểu khiến ( t u ầ n tiự, điều kiện, lặp) mà mọi ngưòi quen biết. ĐặL biệt, chúng tôi sử dụng c:ấu Irúc l o o p d o đê biếu diễn rằng, được thực Ihiiộn lặp. Toán tứ e x i t đê thoát khỏi vòng lặp, còn toán tử s t o p dê dừn;^ sụ thực hiện th u ật Loán. Khi cài đ ặ l các th u ậ t toán, các bạii có ihể lựa c hiọn một trong các ngôn ngữ sau để sử dụng: Common LisỊ), Scheme, Prolog, Smalltalk, C " hoặc ML (xem [28]). C h ú n g tôi xin chân th à n h cảm dn giáo sư Nguyễn Văn Hiệu, clhủ nhiệm khoa Công ngiiộ, Đại học Quốc gia Hà nộ] đã tạo diểu kiên th luận !ợi cho chúng tôi viết cuôn sách này. ( uôn sách chắc chắn không tráiih khỏi những thiôu sót. Chúng' ttôi mong n h ậ n được sự góp ý của độc giíi. Thư fíÓỊj ý xin gửi vổ Nhà .\:u;í'ú bần Khoa học và Kỹ t h u ậ t - 70 T rầ n Filing Đạo Hà Nội. Tá c gìiả NHẬP MÔN TRÍ TUỆ NHÂN TẠO LÀ GÌ? T h u ậ t Uị;ử t r i t u ệ n h a n tạ o (ai’tilicial intelligence) dược J o h n Mí^Carthy dưa ra hội Jiat) t) Daỉ-liiìouíh vào mùa hè 1956. Trong hộì iháo lìàv có inậl cấc Ií‘n tu.)i nối tiỏn^ như Marvin Minsky. Claude Shannon. Nallianiel Rufhos((‘ỉ\ Ai’thiu' Samuel Allen Newell và H erbert Simofi- Trưóc hội th;i 0 ĩìày. từ nãiii 1952 A rth u r Samuel đã viết ('huídng ífìiìh (‘hơi cò. Sanìut*] (iã bác 1)0 tư tướng cho ràng máy tíi)h chỉ C'ó tliỏ làm dưỢc cái nià ÌV/ẠUÚ ta l)áo nó làm. vì chương Irình của Sam uel có tho học đô chdi iòí hdn ngiíòi viỏl I‘a ỉìó. Đôn liội thảo nàv, Alien Newell và Herbert Simon (‘ÙIÌK t-iA viêl (‘hương trìn h lỘỊ) luạn vối lên gọi "the logic lh(H)rist’'. Chư(jng tỉ‘ình í‘ua VIÌC ông có khá năng chứng minh liaia lìôt (,‘á(‘ (ÌỊiih lý (‘luùiíì*r 2 ('Unn "PnnciỊìia Matheniaiics’' của Russell và \VhìU‘lu‘a(l. Tl’oiig liội íhrio ỏ Darliiìouth. các nhà nghiên cứu (ÌA tháo ìuẠìi va vạcli ra các pliưdii^ huVín^ nịíhìôiì ('ứu của lĩiìli vực Trí tuệ' ììhân tạo (TTNT). Vì vậy. hội thao í‘i Darlmoutli. mua hò 1956 đưỢc xem là thời tiiốin I'íi dờì ihực sự cưa Hiìli vực ìighiỏiì cứu TTNT . Ti’on^ c‘ác sáí’h VUM xế T T N T ìi;uìì ^^Ììì (!ây. các tác Riả đã dưa ra nhi ồu tlỊnh n^^hĩa vổ T T N T . ('luinu tòi dan ra dây một sô (iịnh lìghìa; • "Sự nghiõn í ứu t‘á(‘ náii^^ lực trí ÍIIỘ llìỏng qua viộc sử dụng các ni(j liình tính {()[]]{' (“'[’lu* siudv oC ini'iital faculties through the use of (‘oinpiUnlional iìK)(i(‘ls" (’liam iak and McDoi'mott. 1985). • "Xííhệ lliuẠi tạo ra các iníiV tliực hiện các chức năiig dòi hỏi sự thông minh khi dưỢc thục hiộiì bơi con ngưòi” ("The a r t of Croat ịn g inachinos ihal Ị)(*rfornì vvh(‘ii Ị)í*ríbnìK^ :1 by Ị)(‘()Ị)le" functions that K u r z w e i l . 199 0). require 10 _________________________ ____________________ TRÍ TUỆ N H Ã N T Ạ O • "l.ĩnh vựí’ nghiên cứu tìm cách ^Mai tlìícli và mô Ị)hóng các h àn h VI t l i ò n g ìiiinh t r o n g t h u ậ t n^ữ -ác (Ịuá t r ì n h t í n h toán" (“A fie ld oí’ s t u d y t h a t s e o k s to exỊ)lain ai d e m u l a t e in te l lig e n t , b e h a v i o r in te rm s of computational processes” - Schalkoff, 1990). • “Sự nghiên cứu các tính toán để có ih ể n h ậ n thức, lập luận và hành động' ("The study of comf utations th a t make it possible to p e r c e i v e , r e a s o n , a n d a c t ” - VVin-;ton. 1 9 9 2 ). • “Một n h á n h của khoa học máy 'inh Hên quan tới sự lự cỉộng hoá các hành V] thông m in h ” (“The branch of computer science th at IS concerned with the automation of intelligent behavior" - Luger and Stubblefield, 1993). Saư đây là một sô^ định nghĩa gần đây nhất: • '^TTNT là sự thiôt kê và nghiên cứu các chương trình máy tín h ứng xử một cách thông minh. Các chương trình này được xây dựng dể thực hiện các h àn h VI mà khi ơ ngưòì hoặc dộng vật chúng La xem là thông mmh" (“Artificial Intelligence IS th e design and study of computer programs th a t behave intelligently. These p)rograms are constructed to perform as would a h u m a n or an anim al whose behvior we consider intelligent” - Dean. Allen and Aloi monos. 1995). • "'TTNT là sự nghiên cứu các táf' nhân tồn lại trong môi trưòrìg, nhặn Ihửc va hanh động" ("Artificial Intelligence IS the sluciy of agents that exists in an environment and perccMve and act” Russell and Norvig, 1995). • ^'TTNT là sự nghiên cứu (“ComỊ)utational thiôt kô các tác Iihân thôiig min h’' Intelligence is tho study of the desigìì oỉ’ intelligent agents" - Poole. Mackworth and Goebel. 1998). Hiện nay nhiểu nhà nghiên cứu quan niệm rằng, T T N T là lĩnh vực nghiên cứu sự thiốt k ế các t á c n h â n t h ô n g m i n h (intelligent agenit). Tác n h â n thông minh là b ất cứ cái gì lồn tại trong môi trưòng và hàinh động một cách thông minh (Một câu hỏi được đặt ra: h àn h động như t,hố nào thì đưỢc xom là thông minh?). rN H Ậ P M Ò N 11 Mục tiêu khoa học cúa T T N T là hiôu (lược bản chất của các h à n h vi tthỏn^ minh. Mục lié^u thực tiỗìi. ('ông nghẹ cúa T T N T là xây dựng nên (các hộ thỏiìg minh, các máy ihỏnK minh, l^hưổng pháp luận nghiên cứu (ỏ đây c ũ n g tưdng tự như khi chving ta nghiên cứu đê hiêu đưỢc các in^uyôĩi lý bay. rồi ihiêt kê nên các máy biêt bay (máy bay). Máy bay I kh ô ii g [)hái là sự m ô Ị)hỏng con c h i m , s o n g nó có k h ả n ă n g b a y t h ậ m c h í Ibay lot hơn chim. Mộl sô ngành khoa học khác:, chấng hạn như T n ê t học, Tâm lý học (Củng quan tâm nghiên cứu eác n á n g lựí* dưỢc xem là thông minh cua con ]người. Song khác VỚI Triêt học và Tâm lý học, T T N l là một ngành của khoa học máy tính - nghiên cứu xử lý thông tin bàng máy tính, do đó T T N T đ ặ t ra mục tiêu nghiên cứu: làm th ế nào thể hiện được các h à n h 'vi thông m in h bằng t h u ậ t loán, rồi nghiêĩ\ cứu các phương pháp cài đ ặ t .các chương irình có thể thực hiộn dược các h àn h VI thông minh. N h ư vậy íchúng ta cần xây dựng các mô hình lính toán (computational models) Ị)hục vụ c h o việc giải thích, mô tá các h à n h VI t h ô n g m m h b á n g t h u ậ t toán, tiếp theo chúng ta cẩn chỉ ra Líiìh hiệu quả. tính khả thi của t h u ậ t toán thực hiện một nhiệm vụ, và đưa ra các phương pháp cài đặt. TÀC NHÂN THÒNG MINH Tác n h â n (agent) là bất cứ c á i gì hànli dộng trong môi trường. Các tác n h â n có ih ể là con ngưòi. con sâu, cơn chó, các robot, infobot, ... Mục tiéu của T T N T là nghiên cứu vh t hiết kế các lác lìhân ihông minh: các t á c n h ân tồn tại trong môi trư ờ n g và hành động một cách thông minh. Tồn tại Irong môi trường, nê lì tác nhân thông minh cân có khả n ăng n h ậ n thức được môi trường. C h ẳ n g hạn, con người có thê nhận ihức dưỢc môi trường nhờ tai. m ắt và các ỉgiác quan khác. Đô n h ận thức (ỉược môi tr ường các robot sẽ dưỢc tr a n ^ 1) ị cát' bộ c ả m n h ậ n (s(Misors). iló là cár i h i ế t bị vật !ý, cháng hạn c a m o r a . các máy đo dạc, ... Các lác n h â n ihiông minh cần cố rác hô tá c d S n g (effectors) dê đưa ra các h à n h dộng đíáp ứng môi trường. Với con ngưòi, dó là chân, tay và các bộ p h ận khác ciiia thân thổ. Với các robot, (ỉỏ CC) thô là các cánh tay robot, ... 12 T R Í TUỆ N H À N T Ạ O Mỏi t r ư ờ n g C á c thòng tin đến từ mỏi trướng T á c nhán thòng minh C á c h àn h đỏnq -------------- —— la có thể xtMii tác nhân như một hộp đen. (iau vào là các thông tin Iihận thức từ môi trường, đầu ra là các lìàiih dộng ihícỉi ứng VỎI môi trường, như trong hình trên. lìây íĩiò, chúng ta xét xem cần |)hầi c à i đ ậ t v à o h ê n t i - o n g hỘỊ) d e n c á i g ì d e h à n h d ộ i i ^ ĩ d ầ u r a l à hỢỊ) lý, t h í c h ứng VỚI các ihóníĩ Ún (ỉầu vào. Tác nhân cầii có bộ nhớ đô lu’11 ịíiữ các tri thức cluing vể lĩnh vực. vố môi u-ường mà nó dược thiêt kô dê hoạt dộng trong lĩnh vực đó, troiig môi trường dó. Cháii^^ hạn, (ỉô'i với robot lái laxi, I n thức vế môi trường ma I’obol cần có là các tri thức vổ mạng lưỏi giao thông Irong tliànli Ịihỏ vổ luật lộ giao thông, ... Dôi với các hộ chuyên gia trỢ giÚỊ) chán (loán bệnh, các t n thức cầii lưu là các tri ihức của các bác isĩ vè' bệnh lý. vê các Ị)hương án (ỉiểu ti-Ị. ... Bộ nhớ của tác nhân còn để p;hi lại các‘ t n Ih ứ r inới mà lác n h â n I'út ra dược trong (]uá trình hoạt động Lrong môi trường. Trong nhiểu trường hcij), IIÓ cũng cần lưu lại vốL của các Lrạng Ihái của môi Irường, bới vì hành dộng Lhích hỢ|) mà nó cáii dưa ra kh ô n g chỉ phụ thuộc vào Irạng thái hiện lại của môi trường mà còn Ị)hụ thuộc vào các ti'iing thái của môi trường trong (Ịuá khứ. C húng ta cần trang bị cho tác nhân một cliưring trình: chuofifi trinh tác nhón (iiKenl program). Chươiiíí Irình này là sự mô la Ih u ậ l loáii k ố l hỢp các thong lin về trạng thái của môi Irường với các t n Uiửc ciã dươc lưu dô cho ra hành động thích ứng. Ray fĩiờ. chúng la tra lời câu hổi: ‘Vác tác nhân như tliê nào thì (ìược xom là thôii^í minh?” hang (.lịnh nghĩa vổ thông minh của Tufin^r Ihừ HỊỊhiệiii Turing (Turing test). THỬ NGHIỆM TURING Alan Turing (19Õ0) dã xác định các h àn h vi thông minh như là c.ác h à n h VI trong các nhiệm vụ n h ận thức đạt tới mức dộ có ihê dáiih lử a dược con người. NHẬP M Ô N ________________ _________ ___________________________________ 13 Sau dây là (lạng tông q u á t của thử nghiệm Turing. Một người hỏi là con ngưòi ngồi ở một phòng. ỉ)ối tác của Iigười hỏi là một máy tính được dật ở một phòng khác. Hai bôn trao (lối thông tin với nhau thông qua các phương tiộn tru y ề n tin hiệii dại. Nêu máy tính có thê làm cho người hỏi tương lầm là có ngưòi khác dang nói chuyện vói mình ihì máy tính được xem là thông minh. Bây giò cliúng la xét xem. dê thực hiện dược các hành VI được xem là Ihông minh, các lác n hân thông minh (TNTM) cần có khả năng gì? • T N T M cần có khả năng ghi nhớ tri thức và lập luận. Nó sử dụng các t n thức đã lưu trử. và bàng lậị) luận để r ú t ra các kết luận đáp ứng các câu hỏi mà người hỏi đăt ra. Bièu diễn tri thức và láp luún ià lĩnh vực nghiên cứu trung tâm của TTNT. • Ngưòi hỏi có thể đặl câu hỏi bầng ngôn ngữ tự nhiên, chẳng hạn liêng Anh, Vì vậy. T N T M cần có khả n ăn g hiểu ngôn ngữ tự nhiên. íliéu ngôn ngữ tự nhién (natural language understanding) là một lĩr.h vực nghiên cứu quan trọng cúa TTN T. • Ngưòi hỏi có thể đưa ra một số hoàn eảnh và các h à n h động cần tiên h à n h tương ứng vỏi mỗi hoàn cảnh đó. rồi đưa ra một hoàn cánh mới và hỏi tác nhân cần phai làm gì trong hoàn cành đó, Để tra Irti đưỢc râu hỏi này. T N T M rần có khả năng học dế có th ể dua ra h à n h động thích ứng với hoàn cảnh mới. / /f c máy (machine learning) là một lĩnh vực nghiên cứu của T 7 N T đang phát t n ế n m ạnh mẽ và có nhiều ứng dụng trong các lĩrh vực khác nhau, chang hạii trong k h á m phá tri thức và khai th.ic dữ liệu. • Nịrười hỏi có thế dưa ra một sô hình ảnh vê các đôi tượng và kiểm lrf. khá năng nhận biếl các đối tượiig dó của TNTM . y t i i ì máy (computer Vision) là lĩnh vực nghiên cứu để máv tính có thè hiểu dược cấu trúc và các tính chất của các đối tượng trong không gian ba chiều từ các hình ả n h hai chiêu. 14_____________ _ _ _ _ ____________________________________________ TRÍ TUỆ N H Ả N T Ạ O • Khi dưỢc rho các nhiệm vụ cần thực hiện. T N T M cần có khà uíìuịỊ s u y ra các mục clích cần ctạl dược và dưa ra một clãy cár hành dộnịĩ mà nó cẩn thựí* hiộn íìể đạl dưựo các mục dích dỏ. (}ua trình này được gọi là lập kô hoạch. Lạp kẻ hoạch (planning) là một lĩnh vực nghiên cửu (Ịuan irọiig của TT N T . BIỂU DIỄN VÀ LẬP LUẬN Khi gặp một vấn dế cần giái quyêt. một nhiộm vụ cần ihựi' hiện, điều dầu tiên chúng ta phải làm là cán phải biếu diễn vấn đề. cần phài xác định cái gì tạo th à n h lòi ^lải (nghiộm) cúa vấn đề. và sau dó mới cH tìm t h u ậ t toán tính nghiệm, c ấ n lưu ý rằng, biếu diền vâ'n đế đóng vai trò q u an trọng trong việc giải quvêt một vấn để. Trong nhiểu Irơòng hỢp. khi ch ú n g ta chọn được cách biểu diễn thích hỢp cho một Vt^n đổ thì vấn đề h ầ u nh ư đã được giải quyôt. Chúng ta có thể biểu diễn nhiều vấn đê bằng cách xác dịnh trạ n g thái đích cần dạt tới và các h à n h dộng làm biôn đôì các 1 1 'ạng thái của t h ế giới. Khi đó việc tìm nghiệm của vấn đế đưỢc quy về việc tìm kiỏm một dãv các hàn h dộng dẫn tới trạng Lhái đích. Chú V tìm kiôm đóng vai trò quan trọng trong việc giải quyết vân dể và trong nlìiểu lĩnh vực nghiên cúu của T T N 7 \ chẳng h ạ n như trong học máy và lập k ế hoạch. Vì vậy. Ị)hẩn I của sách này dàỉìh cho việc t r ì n h b à y Ị)hương p h á p bi ểu di ễn v â n dề t r o n g k h ô n g g i a n tí*ạng thái và nghiên cứu các chiôn lược tìm kiôm. Thực tế cho tliấy rằng, đế thực hiệỉi dược các nhiộm vụ khó k h ăn và phức tạp. con ngưòi cần sử dụng một khôi lượng lớn tri thức vổ lĩnh vực liên quan. Một câu hỏi dược iỉặt ra: li'i thức là gì? Mộl cách khôiig liình Lhức. ch ú n g ta hiểu tri Ihức là thông lin liên quan tới một đôi iưỢng. inộl hoàn cảnh, một lình vực. Đổ máy tính có thể lưu trữ được tri thức, sử dụng đừỢc Iri tliức, chúng la cần tìm các phương Ị)háp biểu diễn tri ihức. Lập luận tự dóng dưỢc hiểu là quá trình lính toán trên các bieu diễn Iri thức, mả khi cho dầu vào là các biếu diễn tri thức, chúng ta n h ậ n (ỉượư đầu ra lá các biểu diễn tri thức mối. Mục tiêu tr u n g tám của T T N T là n ghiên cứu thiết k ế các hệ thông minh, nó lưu trữ tri thức về lĩnh vực và có khả n a n g đưa ra hành động thírh ứng bằng lậ]) luận dựa trôn các tri NHẬP MÒN ______________ _____________________________________________________________________________________15 Lhức đã lưu Lrữ và các thông Ún thu n hận từ môi trưòng. Do đó, vấn để I r u n g tâm mà chúng ta đế cập đến trong sách này là vấn đệ biểu diễn t n ihửc và lậ[) luận. Chúng ta SC nghiên cứu các mô hình biểu diễn tri thức khác nhau và các phương pháp lập luận Irong mỗi mô hình đó. C Á C ÁP DỤNG Các áp dụng của T T N T là rất đa dạng; các hộ điểu khiển tự động các quá trìn h sán xuất công nghiệp; các robot làm việc trong các môi trường đặc biệt, ch ẳn g hạn các robot thám hiểm các hành tmh; các robot làm việc trong các diều kiện nguy hiểm đên tính m ạng con người; các hệ chuyên gia trong các lĩnh vực; các hệ dịch tự động; các hệ n h ậ n dạng; các mfobot làm việc trong môi trường th u ầ n tuý thông tin; các chương trình chơi cờ; ... Sau đây chúng ta sẽ trìn h bày một vài áp dụng. Qua các ví dụ này, chúng ta muốn chi' ra n h ủ n g vấn dề cần giải quyết khi chúng ta định xẵ>’ dựng một hệ thông mmh. • Robot đưa thư Giả sử chúng ta muôn thiếl k ế một robot để phân phát thư, các gói nhỏ và phục vụ cà phê trong toà nhà làm việc của một công ty. Đương nhiên là robot phải được tr a n g bị các bộ cảm n h ậ n để có thể “n h ìn ” và “nghe”, ch ẳn g h ạ n video camera, các thiêt bị thu th a n h , ... Nó cần có các bộ p h ận thực hiện h à n h động, chẳng h ạ n bánh xe để chuyển động, “cánh tay” để n h ặ t lên, đ ặt xuống các đồ vật.... Các thông tin đến từ môi trường ở đây là các hình ảnh và âm thanh, ... mà robot th u đưỢc nhò các bộ cảm nhận. Khi n h ận đưỢc mệnh lệnh, chẪng hạn “m an g cà phê cho giám đốc”, nó phải đưa ra một dãy h à n h động đáp ứ n g môi trường n h ằm đạt đưỢc đích: có cà phê cho ông giám đô"c. Các tri Ihức mà robot cần biết trước và được lưu trong cơ sở tri thức của robot là cấu trúc của toà nhà: gồm có mấy tầng, các phòng trong mỗi tầng và h à n h lang được bố trí ra sao, th a n g máy ở đâu; các đô'i tượng mà robot có th ể gặp trong toà nhà, ai làm việc ở đâu, cà phê ở phòng nào, ... Cơ sở t n thức của robot còn có thể chứa các tri thức cho biết các hoàn cảnh mà robot thường gặp và các h à n h động m à robot cần thực hiện ________________________________________________________________________________________________ TRÌ TUỆ N H Ẩ N T Ạ O trong mỗi hoàn cảnh đó. ... Các tri ihức n h ư thố cần dưỢc biểu diễn mội cách thích hợp sao cho t h u ậ n tiện cho việc lưu trữ. tìm kiê'm và suy diễn. Từ các thông tin hình anh, robot cần có khả n ă n g hiểu dưỢc VÍÌC dôi iưỢng, phân biệt được các đôi tượng mà nó gặp để có thể suy ra các liành động Ihích hỢp cần thực hiện. Robot cần có khả n ă n g hiểu dưỢc các mộnh lệnh bang ngỏn ngữ tụ nhiôn: từ đó suy ra các đích inà nó cần đạt tới. Kill có nhiều mục đích cần đạt tới. robot cần có khá nãng lậỊ) k ế hoạch để đ ạt được các mục đích đó. Robot cần có khả n ần g tìm đường di (íôì ưu nhất) giữa các vị trí trong toà nhà. từ các thông tm vể sự bô^ trí và chức năng của các phòng và các hộ p h ận Lrong toà nhà. Chúng ta cũng cần tra n g bị cho robot có khả n ăn g học để có thể rú t kinh nghiệm , khái quát hoá từ thực tiễn trong quá trình phục vụ. và do đó khi gặp các hoàn cảnh mới nó có Lhể đưa ra các hành động thích hỢp. • Hệ cỉiuvén gia trongy học Các hộ chuyên gia y học có mục đích trỢ giúp các bác sĩ trong ch u ẩn đoán bệnh và điều trị. Môi trưòng của các hệ chuvên gia này là ngưòi bệnh. Các thông tin đến từ môi trưòng là các triộu chứng của ìigưòi bệnh, các kết quả xét nghiệm từ ngưòi bệnh. Cơ sở tri thức của các hệ chuyôn gia này là các tri thức của các bác sĩ về bộnh lý, các t n thức này thưòng được biểu diễn dưới dạng các luật i f ~ tl\on. Chẳng hạn, Feigenhaur. R uchanann và Shoi'tiffe đã p h á t triốn hệ MYCIN để chẩn đoán bệnh nhiễm trù n g máu. Cơ sở ỉuậl của hộ MYCIN chứa khoảng 450 luật, mỗi luật gắn với một mức dộ chắc chắn (điểu này phù hỢp với tính chất của các kết luận y học). Hộ MYCIN có khả n án g làm việc tôt như các bác sĩ giỏi trong lĩnh vực. Các hệ chuyên gia này có khá nàng suy diễn dể từ các triệu chứng, các kết quả xét nghiệm người bệnh và sử dụng các luật trong cơ sở luộl để suy ra các kết luận vể bệnh. Nó cũng có khả n á n g gỢi ý cần kiểm tra cái gì. cần xét nghiệm cái gì ớ ngưòi bộnh. Củng n h ư các bác sĩ. các hộ chuyên gia này có khả nản g giải thích các kết luận mà nó đả đưa ra, nỏ có th ể cho c h ú n g ta biêt tại sao nó đi đến kết luận như thô. .Phần I CIÁI ỌUYÊT VẤN ĐẾ BANG TÌM KIÉM \ ’:t ì dĩ' Ùm lụòni. một ('ác'h lôiiịí (Ịuat. vó thê hiẽu la tìm một tu()iiu tỉioa mãn inôl sô đoi lioi nào lio. tron^ mộl lạ|) họ'Ị) rộng iớn các (lỏi lú(.ng. ('húii^^ la có t!iỏ ké ra fál nhiều vấn dề mà VIỘC giai quyêl nó duội’ (11 ,y vế v;Vn dế tìm kiêm. ('n ' trò ('h(íi. chản^^ h ạ n cờ \'ua. ('(i carỏ có t h ê x o m nliií v a ii (lổ tìm k i é i n . T i ’o n ' ’ s ô i ' â t n l i u n i n ư ớ c (li CỈLÍỢC Ị ) l ú ‘Ị) t h ự c I n ộ n , t a Ị ) h á i t ì m ra các iníóc d (lần tỏi lình Lhế kếl cuộc mà ta là ngúời ihắng. ('hang ininh (lịiili lý cũn^' fó Uiê xem như vấn đố lìm kiếm, ( ’ho một tập cái liỏn c!ể và các luật suy diễn, trong Irưòng hỢ]) này mục tiêu của la là ti;n r:; mộl cliứng minh (một dãy các luậl siiy (ỉiên tliíỢc ap dụiig) dè dưa (lùn CÔII^^ thức mà ta C'iin chứng minh. 'I'i’)ng (.■ác lĩnli vực Iiịíhiôn cứu cúa In' tuệ Iihân tạo. chúng ta thường xnyrii line i l i . i i cl ỏì d ; ' i u V('ii v â ' n cl ổ t ì m k i ố t i i . i ì ặ c b i ệ t t r o n g l ậ p k ô h o ạ c h v à tìm kiếm ctóns vai trò (luaii IrọTiíí. 'I'f)ng |)han này clunig ta sẽ Iighiêii cứu các kỹ thu ật tìni kiêm (■() t)iin (IvỢc áp dụiiịí dổ giiii quyốl các vấn (lề và clược áp (iụng rộng fai 1 roii^ (i'ic lĩnh vực nghiên cứu khác cúa trí luệ nhân tạo. (^hung ta lan luỢt n*:hién cứu các kỹ ih u ậ t sau: • Các kỹ ih u ậ t tìm k'ếm mù, trong dó chung ta không có hiếu biôt "ì vổ các dối tượng dỏ’ hướng dẫn tìm kiếm mà chi đơn thuần là Kem xél ihco một h.£ ihốiig nào dú ưít cá các dôi tưỢng đế phát hiện ra đốiịiưỢỊ-ig cần tìm. ■' ' ■ ÍIM X , j l 8 ___________ ____________________________________________________________________________________TRÍ TUỆ N H Ả N T Ạ O • ( ’ác kỳ t h u ậ t thii kii'in kiiih riịíhiộm (tìm kiốni híHiristu') t r o i i” (ló chung ta (lựa vào kinh nịíhi(Mii và sự liieu hiốl C'ua ('húng ta vế v á n (Ic c ẩ n ị í i á i (Ị Uv ỏ t ilỏ x â \ ' ( Ỉ Ị i i i ^ n ô n h à m (láiih "líi hiíớn^' (iần s ự tìm k iê m , • ('ac kỹ th u ậ t tìm kiêm tôi liu. • Các Ị)hLfơng pháỊi Um kiêni có (lcVi thủ. tức là CÍIC chiêìi lược tìm kiếm nước di Irong các trò chơi hai ngưò). cháng hạn ccVvLia, cờ tướng, cờ carỗ. r tu in ì G I Á I Q U Y Ẻ T V Â N Đ Ê B Ă N G TÌM KIÊM 19 CH Ư Ơ N G 1 C Á C C H iẾ N L Ư Ợ C TÌM KIẾM MÙ Ti'ong chương này. ch ú n g ta sỗ nghiôn cứu t‘ác chiến ỉược tìm kiếm mu (blind search): tìm kiô^m theo bổ rộng (l)readth-íirst search) và Lìm kiêm theo độ sAu (clepth-firsl sear('h). Hiệu quá của ^ác phưi^ng phốp íinì kiêm này củng sẽ được ciánh giá. 1-1. BIỂU DIỄN VẤN ĐỂ TRONG KHÒNG GIAN TRẠNG THÁI Một khi chúng ta muôn giái 'juyôt một vân dề nào dó bằng tìm k i ỏ m . i l á u t i ò n t a p h á i x á c d ị n h k h ỏ i i g g i a n t ì m ki ôì n. K h ô n g g i a n t ì m kiỏm bao gồm tấi cả các dôi t ư ợ n g mà ta cần quan Lam lìni kiêm. N ó có ihố là không gian lien lục. c h ă n g hạn không gian cíxc véctờ thực n chiều; nó cĩmụ; có thô là không gian các đôì tưỢng ròi rạc. Trong mục này ta sỗ xét viộc biổu diễn mộl vấn đế trong không gian irạng Lhái. sao cho việc giải quyôt vân đổ đưỢc qiiv vẽ việc tìm kiém ti'ong k h ô n g g i a n t r ạ n g th ái. Mọl Ị)hạni V] rộn^ lớìì các vấn dố, dặc biẹt các câu dô, các trò chơi, có í liỏ mô l;’ì bầ!ìg‘ sứ (ỉụng khái inộni trạng tl\ái và toán lử (phép biến ílòi trạ n g llìái). Chang hạn. một, khách du lịch (‘ó trong lay bíín dồ ĩTĩạng lưới giao thòng nôi (‘ác tliành phò trong mộL vùng ìãnh ihố (liình 1.1), du khách (lang ở thanh Ị)hô.4 và aiìh ta muôn tìm đưòiiịỊ đi tới ih ă m thành phó /ỉ. Ti'oni^^ bài toán này. các ih à n h plió cỏ Irong bản đồ là các trạng thai, ih à n h phỏ A là Irạiig thái baĩì dáu. B là Irạng thái kết thúc. Khi d a n " ỏ một th à n h phô. chắng hạn ơ th à n h phô^ D anh ta có thể đi theo cá(‘ con đường de lới cá(‘ Inành phô^ c . F và G. Các con đưòng nôi các Lhành Ị)hcí sẽ được biểu diễn bơi các toán tử. Một toán tử biến đổi một trạng thái t h à n h một trạ n g Lhái khác. Chang hạn. ở trạ n g ihái D sẽ có ba to:ni tií ciẫn t r ạ n '4 thni D tỏi các Irạn g iháì c . F và G. Vấn để của du 20 __________________________________ ________ ^__________________________________TRÍ TUỆ N H Â N Ĩ Ạ O * khâcỉi bây giờ sõ là tìm một dãy toán tử clể (lưa t r ạ n g thủi ban (!au A tfi t r ạ n g thái kết llìúcB. Một ví dụ khác, trong Irò chơi cò VIUI. mỗi cách bô trí í’á(’ íỊuân trê.i bàn cờ là niộí trạng thái. Trạng thái l)an dầu là sụ sáị) XÔỊ) (‘ác quaJii 1ÚJ bắt dầu cuộc rhdi. Mỗi nưóc di hỢp lộ là một loan lủ. nó hiỏn clỏi một cảnh huông trên bàn cò t h à n h một cánh huông khác. N h ư vậy muôn biêu diỗn một Víín để trong không gian t r ạ n g thiai, ta cần xác định các yẽu tô sau: • T rạ n g tlìái ban dầu. • Một tập hỢp các toán lử. Trong đó mỗi toán tứ mô tá một h à iìli dộng hoặc một phép biến dổi có the đưa mộl trạiìg thái lói rnộL tr ạ n g ihái khác. Tập hợp tâ t cả các Irang thái có Lliể đ ạ t tới tií tr ạ n g thái ban dầu bàng cách á]) dụng một dày toán tử lập tlià n li không gian Irạng thái của vấn dề. Ta sõ ký hiệu khôiìg gian trạng thái là b\ trạng thái ban d ầ u líi //(J (W() e U) . M ỗ i l o á n t ử R có Lhể x e i n n h ư m ộ t á n h x ạ R : u ~ > u Xói ch u n g R là một ánh xạ không xác định khắp nơi trên u. • Mộl tậ}) hỢp T các trạiig thái kôL ihúc (trạng thái dích). T là t ậ p con của không gian u . Trong vấĩi dể của du khách trên, chỉ có một t r ạ n g ihái đích- dó là th à n h p h ô / ỉ . N h ư n g Irong nhiều v ấ n để (chẳng hạn các loại cờ) có thế có nhiều t r ạ n g thái dích và tíci không thế xác địĩih trước dược các trạ n g ihái đích. Nói chun^i Iron^ Ị)hần lớn các vấn dề hay, ta chỉ có Lhể mô lầ các trangí t h á i đích là các t r ạ n g thái thỏa m à n một sô điểu kiộn nào đó. Khi ch ủ n g ta bieu diỗn một vân dê thông qua các trạng thái và cáíC loáíi tử. thì VIỘC tìm n g h iệm của bài toán dưỢc quy vổ viộc lìm dường đii từ trạng thái l)aiì dầu tríi tỉ'ạng thái dích. (Một đường đi li’ong khôỉngỊ gian tr ạ n g tlúu là một tlày toáìì lu d ẩ n một trạng tỉìái lởi một trạng thiáìi khác). C húng ta có thể biểu diễn không gian trạiig thái hằng dò thị (lịnhi hưống. trong dó mỗi đỉnh của đổ thị iương ứng với một trạ n g ihái. Siếui có toán tử R biôn dổi trạ n g ihái u th à n h trạng thái V, thì có cung gíánì n h ã n R di lừ đỉnh u tới đỉnh V. Khi đó mộl đưòng đi trong không ííiíanì t r ạ n g thái sẽ là một đường đi trong đồ thị này.