Luận văn Nghiên cứu planning để giải bài toán xác định lộ trình

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC LUẬN VĂN CỬ NHÂN TIN HỌC NGHIÊN CỨU PLANNING ĐỂ GIẢI BÀI TOÁN XÁC ĐỊNH LỘ TRÌNH GVHD: Th.S. Nguyễn Phương Thảo SVTH: Trần Thuỷ Tiên 9912704 Trần Hồng Thái 9912071 TP. HỒ CHÍ MINH, 2003 Nghiên cứu planning để giải bài toán xác định lộ trình 1 Lời mở đầu Từ trước đến nay có rất nhiều bài toán được đặt ra, cần nghiên cứu cách giải quyết. Những bài toán khó nhất vẫn là những bài toán thực tế của cuộc sống. Với sự phát triển mạnh mẽ của công nghệ thông tin như hiện nay, các bài toán thường được đưa vào máy tính để xử lí. Đa số các bài toán được giải quyết bằng cách áp dụng trí thông minh nhân tạo (Artificial Intelligent (AI)). Thuật ngữ “planning” được sử dụng trong AI khi bài toán là bài toán thế giới thực được gọi là AI planning. Con người thường có thói quen dự định một việc gì đó trước khi làm và hầu như con người biết có những hành động nào để đạt được những dự định đó. Để giúp máy tính làm việc như con người, nghĩa là biết những hành động nào có thể đi đến mục tiêu, ta cần cung cấp tri thức cho nó. Tri thức ở đây rất đa dạng, để máy tính “hiểu” được môi trường xung quanh nó như thế nào là việc rất khó khăn. Một máy tính có những trang thiết bị hiện đại nhất vẫn không thể cảm nhận hết những thay đổi của môi trường. Tuy nhiên, đối với một bài toán cụ thể nào đó, máy tính chỉ cần ghi nhận những tri thức liên quan. Với những tri thức đó bộ lập kế hoạch sẽ giúp máy tính biết cần hành động thế nào để đạt được mục tiêu bằng cách đưa ra những kế hoạch tương ứng lấy từ tri thức sẵn có. Trong lĩnh vực AI, lập kế hoạch là vấn đề khá mới so với nhận dạng, xử lí ảnh, xử lí ngôn ngữ, xử lí âm thanh,…đã được nghiên cứu rất nhiều. Nhưng lập kế hoạch có sức mạnh rất lớn trong việc tiếp cận và giải quyết những vấn đề thực tế trong cuộc sống như: chế tạo robot làm việc nhà: biết đi chợ, quét dọn nhà cửa,…; robot tự động làm việc ở những vị trí khá nguy hiểm cho con người như nhà cao tầng hay ngoài không gian,…Một sức mạnh khác của lập kế hoạch tạo ra những robot có thể phản ứng với những biến đổi bất thường của môi trường. Vì trong tự nhiên, chỉ có những động thực vật Nghiên cứu planning để giải bài toán xác định lộ trình 2 mới có thể làm điều này. Trong luận văn này, lập kế hoạch được sử dụng để giải quyết bài toán xác định lộ trình trong thành phố Hồ Chí Minh. Với các tri thức cần cập nhật như luật đi đường, xuất hiện các sự cố gây tắt nghẽn giao thông ở đoạn đường nào, các trường học, bệnh viện, nhà thờ, trụ sở nhà nước, cây xăng, sân vận động, rạp chiếu phim,… được đặt tại đâu. Bộ lập kế hoạch có thể giúp tìm ra những con đường tốt nhất về thời gian, tốc độ, nhiên liệu,…để đến mục tiêu với tri thức được cập nhật thường xuyên. Nghiên cứu planning để giải bài toán xác định lộ trình 3 Lời cảm ơn Chúng em xin chân thành cảm ơn thầy Lê Hoài Bắc và cô Nguyễn Phương Thảo đã tận tình hướng dẫn và giúp đỡ chúng em trong quá trình thực hiện đề tài, cùng toàn thể quý thầy cô khoa Công nghệ thông tin trường Đại Học Khoa Học Tự Nhiên đã tận tình chỉ bảo, truyền đạt những kiến thức quý báo để chúng em làm hành trang vào đời. Chúng em xin chân thành cảm ơn tất cả bạn bè đã động viên và giúp đỡ vượt qua những khó khăn để hoàn thành luận văn này. Đặt biệt, chúng con xin cảm ơn các bậc cha mẹ và những người thân đã hết lòng nuôi nấng dạy dỗ để chúng con có được ngày hôm nay. Do còn hạn chế về nhiều mặt nên luận văn còn nhiều thiếu sót, chúng em kính mong quý thầy cô cùng bạn bè đóng góp ý kiến để chúng em có thể khắc phục, hoàn thiện hơn. Thành phố Hồ Chí Minh Tháng 7 – 2003 Nghiên cứu planning để giải bài toán xác định lộ trình 4 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... Nghiên cứu planning để giải bài toán xác định lộ trình 5 NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... Nghiên cứu planning để giải bài toán xác định lộ trình 6 MỤC LỤC PHẦN I: CƠ SỞ LÝ THUYẾT TRONG LẬP KẾ HOẠCH............................ 11 Lịch sử lập kế hoạch ......................................................................................... 12 CHƯƠNG 1:CÁC KHÁI NIỆM CƠ BẢN....................................................... 16 1 CÁC THUẬT NGỮ CHUNG TRONG LẬP KẾ HOẠCH...................... 16 2 BẢN CHẤT CỦA VẦN ĐỀ LẬP KẾ HOẠCH....................................... 18 3 MỘT SỐ ỨNG DỤNG CỦA LẬP KẾ HOẠCH TRONG THỰC TẾ..... 19 3.1. Robot sắp xếp các khối ......................................................................... 19 3.2. Robot mua hàng hoá ............................................................................. 20 CHƯƠNG 2:CÁC ĐỐI TƯỢNG TRONG LẬP KẾ HOẠCH......................... 22 1 AGENT ..................................................................................................... 22 1.1. Khái niệm .............................................................................................. 22 1.2. Hành động của agent............................................................................. 23 1.3. Agent program ...................................................................................... 26 1.4. Các yếu tố để xây dựng agent program................................................. 28 1.5. Cấu trúc agent ....................................................................................... 29 1.6. Các loại agent ........................................................................................ 30 1.6.1. Agent phản xạ đơn giản ........................................................................ 30 1.6.2. Agent lưu vết môi trường...................................................................... 32 1.6.3. Agent dựa trên mục tiêu........................................................................ 34 1.6.4. Agent dựa trên tính hiệu quả ................................................................. 35 2 MÔI TRƯỜNG ......................................................................................... 37 2.1. Khái niệm .............................................................................................. 37 2.2. Các loại môi trường và thuộc tính của nó ............................................. 38 2.2.1. Môi trường tiếp cận được và không tiếp cận được ............................... 38 Nghiên cứu planning để giải bài toán xác định lộ trình 7 2.2.2. Môi trường xác định và không xác định ............................................... 38 2.2.3. Môi trường episodic và nonepisodic..................................................... 38 2.2.4. Môi trường tĩnh và động ....................................................................... 39 2.2.5. Môi trường rời rạc và liên tục ............................................................... 39 CHƯƠNG 3:CÁC LÝ THUYẾT LIÊN QUAN ĐẾN LẬP KẾ HOẠCH........ 42 1 GIẢI TOÁN BẰNG PHƯƠNG PHÁP TÌM KIẾM ................................. 42 1.1. Agent giải quyết bài toán ...................................................................... 42 1.1.1. Mô tả ..................................................................................................... 42 1.1.2. Ví dụ...................................................................................................... 43 1.1.3. Chương trình agent giải quyết bài toán đơn giản.................................. 43 1.2. Thiết lập bài toán................................................................................... 44 1.2.1. Các kiểu bài toán................................................................................... 45 1.2.1.1. Bài toán trạng thái đơn...................................................................... 45 1.2.1.2. Bài toán đa trạng thái ........................................................................ 46 1.2.1.3. Bài toán ngẫu nhiên........................................................................... 46 1.2.1.4. Bài toán khảo sát ............................................................................... 47 1.2.2. Định nghĩa bài toán và giải pháp .......................................................... 47 1.2.3. Đo mức độ thực thi của việc giải toán .................................................. 48 1.2.3.1. Các phương pháp đo độ thực thi ....................................................... 48 1.2.3.2. Ví dụ.................................................................................................. 49 1.2.4. Chọn trạng thái và hành động ............................................................... 49 1.3. Tìm kiếm giải pháp ............................................................................... 51 1.3.1. Tạo các chuỗi hành động ...................................................................... 51 1.3.2. Cấu trúc dữ liệu của cây tìm kiếm ........................................................ 54 2 GIỚI THIỆU NGÔN NGỮ MÔ TẢ BÀI TOÁN..................................... 56 2.1. Sự trình bày, suy luận và logic.............................................................. 57 Nghiên cứu planning để giải bài toán xác định lộ trình 8 2.1.1. Sự trình bày ngôn ngữ ........................................................................... 57 2.1.2. Suy luận................................................................................................. 59 2.2. Logic mệnh đề....................................................................................... 60 2.2.1. Cú pháp ................................................................................................. 60 2.2.2. Ngữ nghĩa.............................................................................................. 61 2.3. Logic trật tự đầu tiên ............................................................................. 61 2.3.1. Cú pháp và ngữ nghĩa ........................................................................... 62 2.3.2. Các ví dụ ............................................................................................... 63 2.3.3. Lượng từ................................................................................................ 64 2.3.4. Những ký hiệu đặt biệt trong tập hợp, danh sách và số học ................. 65 2.3.5. Phép tính tình huống ............................................................................. 66 CHƯƠNG 4:CÁC VẤN ĐỀ TRONG LẬP KẾ HOẠCH................................ 69 1 GIỚI THIỆU AGENT LẬP KẾ HOẠCH ĐƠN GIẢN............................ 69 2 TỪ GIẢI QUYẾT BÀI TOÁN ĐẾN LẬP KẾ HOẠCH.......................... 70 3 LẬP KẾ HOẠCH SỬ DỤNG PHÉP TÍNH TÌNH HUỐNG ................... 75 4 NGÔN NGỮ STRIPS: NGÔN NGỮ TRÌNH BÀY CƠ BẢN TRONG LẬP KẾ HOẠCH.............................................................................................. 77 4.1. Mô tả trạng thái và mục tiêu ................................................................. 77 4.2. Mô tả hành động ................................................................................... 78 4.3. Không gian ngữ cảnh và không gian kế hoạch ..................................... 80 4.4. Trình bày kế hoạch................................................................................ 81 4.5. Giải pháp ............................................................................................... 85 CHƯƠNG 5:THUẬT TOÁN PARTIAL-ORDER-PLANNING (POP).......... 88 1 MÔ TẢ ...................................................................................................... 88 1.1. Ý tưởng thuật toán................................................................................. 88 1.2. Chi tiết thuật toán .................................................................................. 89 Nghiên cứu planning để giải bài toán xác định lộ trình 9 2 VÍ DỤ........................................................................................................ 90 2.1. Mô tả bài toán ....................................................................................... 90 2.2. Áp dụng thuật toán POP cho bài toán ................................................... 91 CHƯƠNG 6:MÔ HÌNH LẬP KẾ HOẠCH PHÂN Rà PHÂN CẤP ............ 100 1 PHÂN Rà PHÂN CẤP TOÁN TỬ ........................................................ 100 1.1. Đặt vấn đề ........................................................................................... 100 1.2. Phân rã phân cấp là gì? ....................................................................... 100 1.3. Ví dụ.................................................................................................... 101 1.4. Các vấn đề cần quan tâm đối với lập kế hoạch phân rã phân cấp....... 102 1.4.1. Mở rộng ngôn ngữ STRIPS ................................................................ 102 1.4.2. Thuật toán HD-POP ............................................................................ 103 2 PHÂN TÍCH MÔ HÌNH PHÂN Rà PHÂN CẤP.................................. 106 2.1. Giải pháp thuận và giải pháp nghịch................................................... 107 2.2. Ví dụ.................................................................................................... 110 2.3. Sự phân rã và dùng chung................................................................... 112 PHẦN 2:ỨNG DỤNG LẬP KẾ HOẠCH TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI..................................................................................................................... 115 1 GIỚI THIỆU BÀI TOÁN ....................................................................... 115 2 Ý TƯỞNG............................................................................................... 115 3 CÀI ĐẶT AGENT .................................................................................. 116 4 CÁC CHIẾN LƯỢC ............................................................................... 116 5 KẾT QUẢ THỰC NGHIỆM .................................................................. 119 5.1. Chiến lược 2 và bộ lập kế hoạch truy hồi ........................................... 125 5.2. Chiến lược 3 và bộ lập kế hoạch truy hồi ........................................... 131 6 SO SÁNH LẬP TRÌNH KẾ HOẠCH VÀ LẬP TRÌNH THEO LÝ THUYẾT ĐỒ THỊ .......................................................................................... 136 6.1. Thuật toán DijkstraMoore................................................................... 136 Nghiên cứu planning để giải bài toán xác định lộ trình 10 6.2. Đối với lập trình kế hoạch................................................................... 136 PHẦN 3: TỔNG KẾT ..................................................................................... 139 1 NHỮNG GÌ Đà LÀM ĐƯỢC................................................................ 139 2 NHỮNG GÌ CHƯA LÀM ĐƯỢC.......................................................... 139 3 HƯỚNG PHÁT TRIỂN.......................................................................... 140 TÀI LIỆU THAM KHẢO............................................................................... 141 Nghiên cứu planning để giải bài toán xác định lộ trình 11 PHẦN I: CƠ SỞ LÝ THUYẾT TRONG LẬP KẾ HOẠCH CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CHƯƠNG 2: CÁC ĐỐI TƯỢNG TRONG LẬP KẾ HOẠCH CHƯƠNG 3: CÁC LÝ THUYẾT LIÊN QUAN ĐẾN LẬP KẾ HOẠCH CHƯƠNG 4: CÁC VẤN ĐỀ TRONG LẬP KẾ HOẠCH CHƯƠNG 5: THUẬT TOÁN PARTIAL-ORDER-PLANNING (POP) CHƯƠNG 6: MÔ HÌNH LẬP KẾ HOẠCH PHÂN Rà PHÂN CẤP Nghiên cứu planning để giải bài toán xác định lộ trình 12 PHẦN I: CƠ SỞ LÝ THUYẾT TRONG LẬP KẾ HOẠCH Lịch sử lập kế hoạch Nguồn gốc của AI planning một phần xuất phát từ việc giải quyết bài toán (problem solving) qua sự tìm kiếm trong không gian trạng thái và những kỹ thuật phối hợp khác như suy diễn bài toán và sự phân tích “means-ends”, đặt biệt được nhấn mạnh trong GPS (General Problem Solver) của Newell và Simon (1961). Một phần xuất phát từ việc chứng minh định lý và tính toán ngữ cảnh, AI planning được nhấn mạnh trong hệ chứng minh định lý QA3 (Green, 1969). Sự ra đời của planning được thúc đẩy bởi nhu cầu về robot. Năm 1971, Fikes và Nilsson xây dựng hệ lập kế hoạch quan trọng đầu tiên STRIPS mô tả sự tương tác của ba ảnh hưởng này. STRIPS được thiết kế như thành phần lập kế hoạch của phần mềm cho dự án robot Shakey ở Học viện nghiên cứu quốc tế Stanford (SRI). Cấu trúc điều khiển toàn thể của nó được mô hình theo GPS và sử dụng QA3 như là thủ tục con để thiết lập điều kiện tiên quyết của hành động. Năm 1986, Lifschitz đưa ra những phê bình chi tiết và sự phân tích chính thức đối với hệ thống STRIPS. Năm 1992, Bylander thể hiện việc lập kế hoạch đơn giản theo dạng STRIPS, đó là PSPACE hoàn chỉnh. Nghiên cứu planning để giải bài toán xác định lộ trình 13 Năm 1993, Fikes và Nilsson tiến hành triển lãm lịch sử trên dự án STRIPS, và chỉ ra cái nhìn tổng quan về mối quan hệ của nó với những kết quả lập kế hoạch gần đây. Trong nhiều năm, sự lộn xộn của những thuật ngữ bao trùm lĩnh vực lập kế hoạch: • Năm 1987, Genesereth và Nilsson sử dụng thuật ngữ linear để chỉ trật tự tổng thể và nonlinear chỉ trật tự cục bộ. • Năm 1975, Sacerdoti sử dụng linear để chỉ thuộc tính mà ta gọi là không thể xen kẻ. Với tập các mục tiêu con cho trước, bộ lập kế hoạch không xen kẻ này có thể tìm thấy những kế hoạch để giải quyết mỗi mục tiêu con, nhưng sau đó bộ lập kế hoạch chỉ có thể liên kết chúng bằng cách đặt các bước của kế hoạch con trước hay sau các bước của những kế hoạch khác. Ở thập niên 70, nhiều bộ lập kế hoạch là không xen kẻ được, nên chúng không hoàn chỉnh – chúng không luôn luôn tìm ra giải pháp mặc dù giải pháp đó tồn tại. Năm 1975, Waldinger giới thiệu cách lập kế hoạch hồi quy mục tiêu, cách này tiến đến kế hoạch trật tự tổng thể được sắp xếp lại để tránh sự mâu thuẩn giữa các mục tiêu con. Năm 1974, cách này cũng được sử dụng bởi bộ lập kế hoạch WARPLAN của Warren. WARPLAN là bộ lập kế hoạch đầu tiên sử dụng ngôn ngữ lập trình logic (Prolog). Năm 1975, Tate với bộ lập kế hoạch INTERPLAN cho phép xen kẽ tuỳ ý các bước kế hoạch để vượt qua Sussman. Năm 1975, 1977, Sacerdoti đưa ra bộ lập kế hoạch NOAH đi tiên phong trong việc xây dựng những kế hoạch trật tự cục bộ, và nó được khai thác kỹ lưỡng trong hệ NONLIN của Tate (1977), và giữ lại cấu trúc khái niệm của bộ lập kế hoạch INTERPLAN. NONLIN cũng là bộ lập kế Nghiên cứu planning để giải bài toán xác định lộ trình 14 hoạch đầu tiên sử dụng thuật toán rõ ràng để xác định những điều kiện đúng sai ở những điểm khác nhau trong kế hoạch cục bộ. Năm 1987, Chapman đưa ra TWEAK chính thức là hệ lập kế hoạch thứ tự cục bộ. Chapman cung cấp sự phân tích chi tiết, bao gồm việc chứng minh tính hoàn chỉnh và khó khăn của việc thiết lập những bài toán lập kế hoạch khác nhau và các thành phần con của nó. Thuật toán POP sử dụng trong luận văn này dựa trên thuật toán SNLP do Soderland và Weld đưa ra năm 1991, thuật toán này là một cài đặt của bộ lập kế hoạch mô tả bởi McAllester và Rosenblitt năm 1991. Năm 1986, tại hội thảo Timberline đã trình bày những bài báo quan trọng về lập kế hoạch. Reading in Planning (Allen và những người khác, 1990) là tập hợp nhiều bài báo tốt nhất trong lĩnh vực này. Planning and Control (Dean và Wellman, 1991) là sách giáo khoa hay giới thiệu tổng quát về lập kế hoạch, và điều đặt biệt chú ý ở đây là vì nó tạo ra một kết quả đặt biệt để kết hợp những kỹ thuật AI planning cổ điển với lý thuyết điều khiển cổ điển và hiện đại, sự suy luận, lập kế hoạch tương tác và giám sát thực thi. Năm 1994, Weld cung cấp cái nhìn đặt sắc về các thuật toán lập kế hoạch hiện đại. Nghiên cứu planning tập trung vào AI vì đây là điểm xuất phát của nó, những bài báo về planning đóng vai trò chủ đạo trong những tạp san và hội nghị AI, nhưng cũng có những hội nghị đặt biệt dành riêng cho planning, như hội nghị Timberline, hội nghị DARPA, 1990 với những tiếp cận mới như lập kế hoạch, lập lịch và điều khiển hay những hội nghị quốc tế về các hệ AI Planning. Nghiên cứu planning để giải bài toán xác định lộ trình 15 CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN 1. Các thuật ngữ chung trong lập kế hoạch 2. Bản chất của vấn đề lập kế hoạch 3. Một số ứng dụng của lập kế hoạch trong thực tế Nghiên cứu planning để giải bài toán xác định lộ trình 16 CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN 1 CÁC THUẬT NGỮ CHUNG TRONG LẬP KẾ HOẠCH Agent - Tác nhân Là những gì nhận thức từ môi trường xung quanh qua cơ quan cảm giác và phản ứng trở lại môi trường qua cơ quan phản ứng. Ví dụ: con người, robot,... Percept - Tri thức Là kết quả nhận thức của agent đối với môi trường xung quanh. State - Trạng thái Là những ảnh chụp nhanh trong mỗi thời điểm cụ thể. Action - Hành động Là những phản ứng của agent đối với môi trường, hành động là nguyên nhân của sự thay đổi trạng thái. Goal state - Trạng thái mục tiêu Trạng thái cuối cùng agent cần đạt được sau khi thực hiện kế hoạch. Initial state - Trạng thái ban đầu Nghiên cứu planning để giải bài toán xác định lộ trình 17 Trạng thái ban đầu agent có trước khi thực hiện bất kỳ hành động nào. Agent program - Chương trình tác nhân Đoạn chương trình cụ thể cài đặt cho một agent cụ thể Environment - Môi trường Là tất cả những gì xung quanh agent, cung cấp tri thức cho agent và nhận những phản ứng của agent. World state - Trạng thái môi trường Trạng thái môi trường xung quanh agent được xác định trong những thời điểm cụ thể. Plan - Kế hoạch Là chuỗi hành động do agent tạo ra và được thực thi bởi agent. Operator - Toán tử Tập các ký hiệu mô tả hành động của agent, đồng thời mô tả các điều kiện và kết quả của hành động. Plan library - Thư viện kế hoạch Tập luật về các hành động của agent, đây là tập các kế hoạch, thư viện tuy không đầy đủ tất cả các kế hoạch nhưng thư viện này có thể cập nhật thường xuyên. Các kế hoạch trong thư viện thường có dạng If … then … Nghiên cứu planning để giải bài toán xác định lộ trình 18 State space - Không gian trạng thái Bao gồm những trạng thái có thể có của agent khi thực hiện hành động. Đối với bài toán cụ thể, không gian trạng thái là hữu hạn. Plan space - Không gian kế hoạch Chứa những kế hoạch của agent. Không giống như thư viện kế hoạch, không gian kế hoạch có thể trùng lắp. Vì thế không gian kế hoạch thường vô hạn. Solution - Giải pháp Là những kế hoạch thu được mục tiêu. Causal link - Liên kết nhân quả Là những liên kết tất yếu, khi thực hiện hành động này chắc chắn thu được trạng thái kia. 2 BẢN CHẤT CỦA VẦN ĐỀ LẬP KẾ HOẠCH Lập kế hoạch cũng là một cách tiếp cận để giải quyết bài toán như bao cách tiếp cận khác. Tuy nhiên, điều khác biệt của lập kế hoạch so với những cách tiếp cận đó là nó tạo ra một agent để xử lí và thực thi hành động trong môi trường cụ thể của bài toán. Agent này có cơ quan cảm giác để cảm nhận và cập nhật tri thức từ môi trường và có cơ quan phản ứng để thực thi các hành động mà agent đưa ra. Điều quan trọng nhất Nghiên cứu planning để giải bài toán xác định lộ trình 19 trong agent này là bộ lập kế hoạch, bộ lập kế hoạch tiếp nhận tri thức, xử lí và đưa ra những kế hoạch phù hợp. Trong luận văn này, do sự giới hạn về nhiều mặt, chúng tôi không thể xây dựng các cơ quan cảm giác và cơ quan phản ứng, chỉ xây dựng bộ lập kế hoạch tổng quát của agent. 3 MỘT SỐ ỨNG DỤNG CỦA LẬP KẾ HOẠCH TRONG THỰC TẾ 3.1. Robot sắp xếp các khối Bài toán như sau: có tập hợp các khối lập phương trên bàn. Các khối có thể sắp xếp thành đống, nhưng chỉ có một khối có thể nằm trên một khối khác. Một cánh tay robot có thể nhấc một khối lên và di chuyển đến vị trí khác: lên trên bàn hay lên trên một khối khác. Trong một thời điểm cánh tay chỉ có thể nhấc một khối, vì vậy nó không thể nhấc một khối đang ở dưới một khối khác. Mục tiêu sẽ luôn luôn là xây dựng một hay nhiều đống các khối, cụ thể là giới hạn khối nào trên khối nào. Ví dụ, trạng thái ban đầu của các khối như sau: Hình 1.1. Trạng thái ban đầu của các khối trong bài toán sắp xếp các khối Nghiên cứu planning để giải bài toán xác định lộ trình 20 Mục tiêu là: khối C trên khối A và khối B trên bàn. Hình 1.2. Mục tiêu của bài toán sắp xếp các khối Kế hoạch như sau: 3.2. Robot mua hàng hoá Có một robot đang ở nhà, chủ nhà cần mua một bếp ga, cà chua và nước tương. Bộ lập kế hoạch phải lập ra kế hoạch để robot đến cửa hàng điện máy mua bếp ga, đến siêu thị mua nước tương và cà chua sao cho nhanh nhất về thời gian hay ít tốn kém nhất về tiền bạc và quay về nhà. Nhấc B ê Đặt xuống Nhấc C ê Đặt lên khối A Nghiên cứu planning để giải bài toán xác định lộ trình 21 CHƯƠNG 2: CÁC ĐỐI TƯỢNG TRONG LẬP KẾ HOẠCH 1. Agent 2. Môi trường Nghiên cứu planning để giải bài toán xác định lộ trình 22 CHƯƠNG 2: CÁC ĐỐI TƯỢNG TRONG LẬP KẾ HOẠCH 1 AGENT 1.1. Khái niệm Agent là các vật có khả năng nhận thức được môi trường xung quanh nó qua các cơ quan cảm giác và tác động lại môi trường qua các cơ quan phản ứng. Hình 2.1 thể hiện sự tương tác giữa agent và môi trường xung quanh nó qua các cơ quan cảm giác và cơ quan phản ứng. Ví dụ: − Agent con người có mắt, tai và các cơ quan khác là cơ quan cảm giác, còn tay, chân, miệng và các phần cơ thể khác là các cơ quan phản ứng. cơ quan vận động môi trường → ? cơ quan cảm iá tri thức hành động Hình 2.1 agent tương tác với môi trường qua cơ quan cảm giác và cơ quan phản ứng  Nghiên cứu planning để giải bài toán xác định lộ trình 23 − Agent robot với camera và các bộ dò tìm là cơ quan cảm giác, các động cơ khác là cơ quan phản ứng. − Agent phần mềm mã hoá những dòng bit thành tri thức và hành động của nó. Không có những đặt trưng rõ ràng để chia môi trường thành agent và non-agent. Ví dụ, cái đồng hồ có thể là agent, cũng có thể là non-agent. Bình thường nó là một agent có ý thức luôn hành động đúng nghĩa là luôn chạy đúng giờ. Nhưng khi ta đi từ Việt Nam sang Nhật, nếu đồng hồ là một agent có ý thức nó phải tự động tăng hai giờ nữa, nhưng thực tế không phải vậy. Lúc này đồng hồ chỉ là vật vô tri, ta gọi nó là non-agent. 1.2. Hành động của agent Agent có ý thức luôn hành động đúng, hành động đúng làm cho agent thành công. Vấn đề đặt ra là sự thành công của agent được đánh giá như thế nào và khi nào? Để đánh giá như thế nào là một agent thành công các chuyên gia đưa ra nguyên tắt độ đo thực thi. Độ đo này đánh giá mức độ hành động của agent. Ví dụ, một robot dỡ hàng, độ đo hợp lí sẽ đo số hàng hoá dỡ được trong một ca 8 giờ. Độ đo tinh vi hơn còn xét đến năng lượng tiêu thụ (xăng, dầu,…) và tiếng ồn phát ra. Tuy nhiên, không có độ đo cố định nào phù hợp với tất cả các agent. Đánh giá khi nào là rất quan trọng. Qua đó có thể biết agent nào làm việc nhanh, agent nào lười biếng. Các chuyên gia luôn muốn tạo ra một agent sáng suốt. Agent này biết trước kết quả của những hành động mà nó thực hiện, nhưng điều này không khả thi trong thực tế. Vì các agent thường thực hiện hành động mà không biết kết quả thế nào. Trừ khi nó thực hiện một “quẻ bói”. Tuy nhiên, sẽ khả thi hơn để tạo ra một agent có ý thức, loại agent này thực Nghiên cứu planning để giải bài toán xác định lộ trình 24 hiện hành động mà nó cho là đúng, dựa vào tác động của ngữ cảnh, những kết quả có thể không như mong muốn. Tóm lại, để biết một agent hoạt động tốt hay không ở một thời điểm nào đó, ta dựa vào 4 yếu tố sau: • Độ đo thực thi định nghĩa mức độ thành công. • Tất cả mọi điều mà agent nhận thức được từ trước đến nay. Lịch sử tri thức hoàn chỉnh này được gọi là chuỗi nhận thức. • Những gì mà agent biết về môi trường. • Những hành động mà agent có thể thực thi. Một agent là một ánh xạ từ những chuỗi nhận thức sang các hành động. Giả sử rằng hành vi của agent chỉ phụ thuộc vào chuỗi nhận thức của nó, thì bất kỳ một agent cụ thể nào cũng có thể được mô tả bằng một bảng gồm các hành động tương ứng với mỗi chuỗi nhận thức. (Đối với hầu hết các agent, bảng này gồm một danh sách rất dài – vô hạn, trừ khi nó được giới hạn chiều dài của chuỗi nhận thức được xem xét.) Danh sách này được gọi là một ánh xạ từ các chuỗi nhận thức sang các hành động. Nói chung, chúng ta có thể tìm thấy ánh xạ mô tả chính xác agent bằng cách thử tất cả các chuỗi nhận thức và ghi lại các hành động tương ứng mà agent thực hiện. (Nếu agent sử dụng các giá trị ngẫu nhiên, thì phải thử những chuỗi nhận thức vài lần để lấy giá trị trung bình về hành vi của agent.). Một ánh xạ thể hiện một agent và ánh xạ lí tưởng sẽ thể hiện agent lí tưởng. Để thiết kế agent lí tưởng cần xác định những hành động mà agent phải thực hiện dựa trên chuỗi tri thức đã có. Tuy nhiên, không nhất thiết phải tạo một bảng chi tiết cho mọi chuỗi nhận thức. Ta có thể định nghĩa một ánh xạ cụ thể mà không cần phải liệt kê tường tận nó. Xét ví dụ sau: một agent đơn giản là hàm tính Nghiên cứu planning để giải bài toán xác định lộ trình 25 căn bậc 2. Chuỗi nhận thức của agent này là chuỗi các thao tác gõ phím biểu diễn một số thực. Hành động là thể hiện một số lên màn hình. Phép ánh xạ lí tưởng khi agent nhận được một số x dương, hành động đúng hiển thị một số z dương ứng với z2 ≈ x, với độ chính xác là 15 chữ số thập phân. Như đã nói phép ánh xạ không yêu cầu người thiết kế phải xây dựng chính xác một bảng gồm căn bậc 2 của các số. Và hàm căn bậc 2 cũng không cần phải sử dụng bảng thì mới hành động chính xác. Bảng sau đây thể hiện sự ánh xạ lí tưởng và chương trình đơn giản được cài đặt theo phương pháp Newton. Ví dụ căn bậc hai trên đã cho ta thấy mối quan hệ giữa phép ánh xạ lí tưởng và việc thiết kế agent lí tưởng với những tác vụ rất hạn chế. Tuy rằng bảng mô tả thì rất lớn nhưng chương trình lại nhỏ gọn. Điều này nói lên rằng, ta có thể thiết kế các agent tốt, nhỏ gọn, cài đặt phép ánh xạ lý tưởng cho những ngữ cảnh tổng quát hơn: các agent có thể giải quyết các nhiệm vụ không giới hạn, trong các môi trường không giới hạn. Nhận thức x Hành động z 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 : 1.000000000000000 1.018808848170152 1.095445115010332 1.140175425099138 1.183215956619923 1.224744871391589 1.264911064067352 1.303840481040530 1.341640786499874 1.378404875209022 : function SQRT(x) z = 1.0 repeat until |z2 – x| < 10-15 z = z – (z2 - x)/(2z) end return z Nghiên cứu planning để giải bài toán xác định lộ trình 26 1.3. Agent program Agent program là một hàm cài đặt phép ánh xạ agent từ nhận thức sang hành động. Để thiết kế một agent program, ta phải đưa ra được những nhận thức và hành động của nó, những mục tiêu và độ đo thực thi mà ta muốn agent đạt được và môi trường agent sẽ hoạt động. Xem ví dụ về các loại agent sau đây: Loại agent Tri thức Hành động Mục đích Môi trường Hệ thống chẩn đoán y khoa Các triệu chứng và các câu trả lời của bệnh nhân Hỏi, kiểm tra và trị bệnh Bệnh nhân khoẻ mạnh, giá cả tối thiểu Bệnh nhân, bệnh viện Hệ thống phân tích ảnh vệ tinh Cường độ thay đổi của các pixel, màu sắc In ảnh theo phân loại Hoàn thành việc phân loại Ảnh từ vệ tinh trên quỹ đạo của nó Dạy Tiếng Anh giao tiếp Các từ được nhập vào In bài tập, gợi ý, sữa lỗi Điểm tối đa của sinh viên trong bài kiểm Sinh viên Các agent thông minh thường được xây dựng theo một sườn chung, cụ thể là, nhận tri thức từ môi trường và tạo ra hành động. Ví dụ một agent program rất đơn giản: Nghiên cứu planning để giải bài toán xác định lộ trình 27 Mỗi agent sử dụng vài cấu trúc dữ liệu bên trong, chúng sẽ được cập nhật mỗi khi tri thức mới được đưa vào. Hai vấn đề cần lưu ý khi xây dựng agent program: − Thứ nhất, mặc dù phép ánh xạ agent được định nghĩa là một hàm từ các chuỗi nhận thức đến các hành động, nhưng agent program chỉ nhận các nhận thức đơn giản làm đầu vào của nó. Chuỗi nhận thức được tạo trong bộ nhớ. − Thứ hai, agent có thể không thể hiện độ đo thực thi. Vì độ đo thực thi thường được dùng để điều chỉnh hành vi của agent, nên ta vẫn có thể có những hành vi phù hợp mà không cần tri thức rõ ràng về độ đo thực thi. Agent program đơn giản nhất là dùng bảng tra. Nó thao tác bằng cách lưu toàn bộ chuỗi tri thức trong bộ nhớ và sử dụng chỉ mục trong bảng chỉ đến những hành động tương ứng cũng được lưu trong bảng. Tuy nhiên, agent này có các khuyết điểm sau: a) Đối với một bài toán đơn giản agent cũng cần một bảng chỉ mục rất lớn. b) Để xây dựng bảng tra, người thiết kế phải mất rất nhiều thời gian. c) Agent không tự động, vì tất cả những hành động tốt nhất người thiết kế đã tính toán và xây dựng sẵn cho agent. Vì vậy, nếu môi function AGENT(nhận thức) returns hành động static: bộ nhớ, bộ nhớ lưu nhận thức và hành động của agent đối với môi trường bộ nhớ – CẬP NHẬT TRI THỨC(bộ nhớ, tri thức) hành động – CHỌN HÀNH ĐỘNG TỐT NHẤT(bộ nhớ) bộ nhớ – CẬP NHẬT HÀNH ĐỘNG(bộ nhớ, hành động) return hành động Nghiên cứu planning để giải bài toán xác định lộ trình 28 trường thay đổi trong những tình huống không dự đoán trước thì agent sẽ thất bại. d) Thậm chí nếu ta cho agent cơ chế tự học để có mức độ tự động nào đó thì agent cũng phải học mãi mãi những giá trị đúng cho tất cả các entry của bảng. 1.4. Các yếu tố để xây dựng agent program Xây dựng agent program phụ thuộc vào rất nhiều yếu tố. Do đó, agent program thường được tạo ra cho một bài toán cụ thể. Các yếu tố quan trọng nhất là: a) Nhận thức, để có được nhận thức về môi trường agent phải trang bị các cơ quan phản ứng phù hợp b) Hành động c) Mục tiêu d) Môi trường cụ thể mà agent hành động. Agent phải quen thuộc với con người, nghĩa là nó phải nhận thức và hành động như thói quen của con người. Thường có thể dự đoán trước tình huống, trước khi con người nhắc nhở. Ví dụ, để xây dựng agent lái taxi tự động cần xác định được các yêu cầu sau: Loại agent Nhận thức Hành động Mục tiêu Môi trường Tài xế taxi Camera, đồng hồ tốc độ, GPS, hệ thống định vị, mirophone Lái xe, tăng tốc, thắng lại, trao đổi với hành khách An toàn, nhanh, đúng luật, giao thông thuận tiện, thuận lợi tối đa đường phố, các kiểu giao thông khác nhau, khách bộ hành, hành khách Nghiên cứu planning để giải bài toán xác định lộ trình 29 Agent này có các yêu cầu chất lượng như: xác định đúng vị trí, tiêu tốn năng lượng ít nhất, thời gian hay chi phí lưu thông ít nhất hoặc cả hai, khả năng vi phạm luật giao thông là nhỏ nhất, và không làm phiền đến những người lái khác, an toàn và tiện nghi cho hành khách là lớn nhất, thuận lợi tối đa. Dĩ nhiên, với các mục tiêu có mâu thuẩn này ta phải thỏa thuận để giải quyết. Yếu tố cuối cùng khi thiết kế agent này là agent sẽ hoạt động trong môi trường như thế nào, trong các con đường nội thành hay ngoài xa lộ? Ở nơi có đầy tuyết hay hầu như không có tuyết. Nó luôn chạy bên phải hay ta muốn nó đủ tinh vi để biết nên lái xe bên phải hay bên trái như ở Anh hay Nhật? Rõ ràng môi trường được giới hạn càng hẹp thì càng dễ dàng thiết kế bài toán. 1.5. Cấu trúc agent Giả sử agent program chạy trên vài thiết bị máy tính được gọi là kiến trúc. Chương trình được chọn phải là chương trình mà kiến trúc chấp nhận và chạy được. Kiến trúc thường là một máy tính thuần tuý hoặc có thể là những phần cứng cụ thể phục vụ cho những tác vụ nào đó, như xử lí ảnh camera hay lọc tín hiệu âm thanh. Kiến trúc cũng có thể chứa những phần mềm phục vụ cho việc lập trình cấp cao. Nói chung kiến trúc đưa nhận thức thu được từ cơ quan cảm giác vào chương trình, chạy chương trình và cho phép các hành động của chương trình lựa chọn cơ quan phản ứng khi nó được tạo ra. Mối quan hệ giữa agent, kiến trúc và chương trình được tóm tắt như sau: agent = kiến trúc + chương trình Khi có tri thức mới vào, agent program cập nhật chúng vào các cấu trúc dữ liệu. Các cấu trúc dữ liệu này sẽ được thao tác bởi các hàm thực hiện Nghiên cứu planning để giải bài toán xác định lộ trình 30 quyết định của agent để tạo ra hành động, sau đó các hành động này sẽ được đưa vào kiến trúc để thực thi. 1.6. Các loại agent Xây dựng agent là cài đặt sự ánh xạ từ nhận thức sang hành động. Với mỗi khía cạnh khác nhau có các loại agent program khác nhau. Có 4 loại agent: • Agent phản xạ đơn giản • Agent lưu giữ sự kiện • Agent dựa trên mục tiêu • Agent dựa trên tiện ích 1.6.1. Agent phản xạ đơn giản Loại agent này sử dụng bảng tra để lưu giữ những hành động phản hồi của tri thức và bảng tra này thường rất lớn. Ví dụ như đầu vào từ một camera có tốc độ 50 meagbyte/giây (25 khung/giây, 1000×1000 pixel với 8 bit màu và 8 bit thông tin) thì bảng tra trong một giờ sẽ là 260×60×50M mục. Tuy nhiên, các thành phần trong bảng có thể được tóm tắt bằng cách ghi lại các liên kết nhập/xuất chắc chắn xuất hiện thường xuyên. Ví dụ, nếu xe phía trước thắng, đèn thắng của nó bật lên, người lái xe phải chú ý điều này và chuẩn bị thắng. Nói cách khác, dữ liệu vào lập ra điều kiện “Xe phía trước thắng” tạo ra sự liên kết với hành động “chuẩn bị thắng”. Những liên kết này được gọi là luật điều kiện-hành động hay luật ngữ cảnh-hành động, hay luật if…then…. Ví dụ: if xe trước thắng then chuẩn bị thắng Nghiên cứu planning để giải bài toán xác định lộ trình 31 Hình 2.2 thể hiện cấu trúc của một agent phản xạ đơn giản ở dạng biểu đồ, thể hiện cách các luật điều kiện-hành động cho phép agent thực hiện sự kết nối từ tri thức đến hành động. Hình chữ nhật thể hiện trạng thái hiện hành bên trong quá trình quyết định của agent, hình oval thể hiện thông tin nền sử dụng trong quá trình này. Agent program của agent phản xạ có thể được cài đặt như sau: function AGENT PHẢN XẠ ĐƠN GIẢN(tri thức) returns hành động static: tập luật, tập các luật điều kiện – hành động trạng thái – CHUẨN HOÁ ĐẦU VÀO(tri thức) luật – TÌM LUẬT PHÙ HỢP(trạng thái, tập luật) hành động – LẤY HÀNH ĐỘNG (luật) return hành động Agent phản xạ đơn giản. Hoạt động bằng cách tìm kiếm các luật có các điều kiện phù hợp với ngữ cảnh hiện tại (do tri thức định nghĩa), sau đó thực hiện những hành động liên quan đến luật đó. Agent Cơ quan cảm giác Môi trường như thế nào? Bây giờ, tôi nên thực hiện hành động nào? Các luật điều kiện- hành động Cơ quan phản ứng M ôitrường Hình 2.2. Cấu trúc dạng biểu đồ của một agent phản xạ đơn giản Nghiên cứu planning để giải bài toán xác định lộ trình 32 Hàm CHUẨN HOÁ ĐẦU VÀO tạo ra sự mô tả trạng thái hiện hành từ những tri thức. Hàm TÌM LUẬT PHÙ HỢP trả về luật đầu tiên được tìm thấy trong tập luật phù hợp với trạng thái đã mô tả. Agent này rất dễ cài đặt, nhưng khả năng của nó rất hạn chế vì những nguyên nhân sau: a) Agent sử dụng tập luật do người thiết kế tạo ra trước, nên agent chỉ có thể phản ứng theo những gì có sẵn trong tập luật. Khi môi trường có những thay đổi ngoài dự kiến, agent không biết phải hành động thế nào . b) Bảng tra thường quá lớn, agent phải tìm kiếm khá lâu để có được luật phù hợp. 1.6.2. Agent lưu vết môi trường Agent phản xạ đơn giản chỉ làm việc khi tri thức đầu vào phù hợp với những gì đã thiết kế. Trong những trường hợp có quá nhiều tri thức gần giống nhau, chẳng hạn xe không chỉ có đèn thắng mà còn đèn sau, đèn quẹo trái, đèn quẹo phải,… agent phản xạ đơn giản phải lưu trữ sẵn tất cả các trạng thái bên trong đã sắp xếp để lựa chọn hành động. Agent phản xạ theo môi trường giải quyết vấn đề này bằng cách cập nhật thông tin trạng thái bên trong. Nó yêu cầu agent program chứa hai loại tri thức. Một là, thông tin về sự phát triển của môi trường độc lập với agent. Hai là, thông tin về những hành động của agent ảnh hưởng đến môi trường. Hình 2.3 biểu diễn cấu trúc của agent phản xạ, thể hiện sự liên kết giữa tri thức hiện tại và trạng thái trước để tạo ra những mô tả được cập nhật của trạng thái hiện hành. Nghiên cứu planning để giải bài toán xác định lộ trình 33 Agent program của agent phản xạ theo môi trường có thể được cài đặt như sau: Trong agent program trên, hàm CẬP NHẬT TRẠNG THÁI tạo ra sự mô tả trạng thái mới bên trong cùng với việc giải thích tri thức mới để làm rõ hơn những tri thức đang tồn tại về trạng thái, nó sử dụng thông tin về cách môi trường phát triển để lưu giữ những phần không nhìn thấy của function AGENT PHẢN XẠ THEO MÔI TRƯỜNG (tri thức) returns hành động static: trạng thái, mô tả trạng thái hiện tại của môi trường tập luật, tập luật điều kiện-hành động trạng thái – CẬP NHẬT TRẠNG THÁI(trạng thái, tri thức) luật – TÌM LUẬT PHÙ HỢP(trạng thái, tập luật) hành động – LẤY HÀNH ĐỘNG(luật) trạng thái – CẬP NHẬT TRẠNG THÁI(trạng thái,hành động) return hành động Agent phản xạ với trạng thái bên trong. Nó làm việc bằng cách tìm luật mà điều kiện của nó phù hợp với trạng thái hiện tại (do tri thức và trạng thái bên trong định nghĩa) sau đó thực hiện hành động tương ứng với luật đó. Cơ quan cảm iá Môi trường như thế nào? Bây giờ tôi nên thực hiện hành động nào? Trạng thái Môi trường tiến triển như thế nào? Hành động của tôi làm gì? Các luật điều kiện- hành động Cơ quan phản ứ Agent M ôitrường Hình 2.3 Agent phản xạ với các trạng thái bên trong Nghiên cứu planning để giải bài toán xác định lộ trình 34 môi trường, và cũng để biết về những hành động của agent làm gì đối với trạng thái môi trường đó. 1.6.3. Agent dựa trên mục tiêu Một agent biết về trạng thái của môi trường không phải luôn quyết định được mình phải làm gì. Ví dụ, khi đến giao lộ, taxi có thể rẽ trái, phải hay đi thẳng. Quyết định đúng sẽ phụ thuộc vào nơi mà taxi muốn đến. Hay nói cách khác, cùng với sự mô tả trạng thái hiện hành, agent cần thông tin mục tiêu đã sắp xếp, các thông tin này mô tả ngữ cảnh yêu cầu, ví dụ nơi đến của hành khách. Agent liên kết thông tin này với thông tin kết quả của những hành động có khả năng thực hiện, để chọn những hành động đạt được mục tiêu. Đôi khi việc phối hợp này rất đơn giản, kết quả phù hợp ngay với mục tiêu chỉ với một hành động đơn giản. Nhưng đôi khi lại rất phức tạp, agent phải xem xét một chuỗi dài những hành động lẩn quẩn để tìm con đường đi đến mục tiêu. Việc thực hiện quyết định của agent này về cơ bản khác với các luật điều kiện-hành động, vì nó phải xét đến tương lai – các câu hỏi đặt ra như là “Cái gì sẽ xảy ra nếu tôi làm như vậy?” và “Điều đó có làm tôi hài lòng không?”. Trong việc thiết kế agent phản xạ các câu hỏi này không được sử dụng tường minh, vì người thiết kế đã tính trước những hành động chính xác trong những trường hợp khác nhau. Ví dụ, agent phản xạ sẽ thắng lại khi thấy đèn thắng của xe trước bật lên. Nhưng agent dựa trên mục tiêu lập luận rằng, khi thấy đèn thắng của xe trước bật lên, nó sẽ đi chậm lại, mục tiêu là không có sự va chạm giữa các xe. Mặc dù agent này kém hiệu quả hơn, nhưng nó tinh vi hơn. Nó có thể tự động cập nhật tri thức mới một cách hiệu quả khi môi trường thay đổi để phù hợp với điều kiện mới. Trong khi đó agent phản xạ phải viết lại một số lớn các luật điều kiện-hành động. Vì vậy nó có thể đạt được các mục đích khác nhau bằng cách tiếp cận các hành vi mới. Nghiên cứu planning để giải bài toán xác định lộ trình 35 Hình 2.4 thể hiện cấu trúc của agent dựa trên mục tiêu. 1.6.4. Agent dựa trên tính hiệu quả Chỉ những mục tiêu thôi chưa đủ để agent tạo ra những hành vi có hiệu quả cao. Ví dụ, có rất nhiều chuỗi hành động để taxi đi đến nơi cần đến, như vậy ta thu được mục tiêu, nhưng có cái nhanh hơn, có cái an toàn hơn, chắc chắn hơn, rẽ hơn, .v.v… Các mục tiêu chỉ đưa ra sự phân biệt đơn thuần giữa hai trạng thái “hài lòng” và “không hài lòng”. Trong khi đó, độ đo mức độ thực thi tổng quát sẽ so sánh sự khác nhau giữa những trạng thái môi trường, qua đó có thể xác định agent hài lòng như thế nào khi thực hiện các chuỗi hành động đó. Bởi vì “hài lòng” không có cơ sở Trạng thái Môi trường tiến triển như thế nào? Hành động của tôi làm gì? Các mục tiêu Cơ quan cảm giác Bây giờ môi trường như thế nào? Sẽ như thế nào nếu tôi thực hiện hành động A? Bây giờ tôi nên thực hiện hành động nào? Cơ quan phản ứng Agent M ôitrường Hình 2.4. Agent với mục tiêu tường minh Nghiên cứu planning để giải bài toán xác định lộ trình 36 khoa học, nên thuật ngữ thông thường nói rằng, nếu môi trường này tốt hơn môi trường kia thì nó mang lại hiệu quả cao hơn cho agent. Tính hiệu quả là một độ đo mức độ hài lòng của agent. Xác định chính xác tính hiệu quả sẽ giúp đưa ra các quyết định hợp lí trong các trường hợp khó khăn. Đó là, khi các mục tiêu mâu thuẫn nhau, agent chỉ thu được vài mục tiêu (ví dụ, tốc độ và an toàn), tính hiệu quả giúp chỉ ra những thỏa thuận thích hợp hay khi có những mục tiêu mà agent khó có thể đạt được, tính hiệu quả có thể đưa ra các cách mà khả năng thành công có thể ảnh hưởng xấu đến mục tiêu. Agent có tính hiệu quả rõ ràng có thể thực hiện các quyết định hợp lý, nhưng cũng phải so sánh các hiệu quả đã thu được bởi các chuỗi hành động khác nhau. Mặc dù vậy, nếu chỉ với các mục tiêu thô, cũng có thể làm cho agent lựa chọn hành động đúng hướng nếu nó phù hợp với mục tiêu. Đôi khi, chức năng hiệu quả có thể chuyển thành tập các mục tiêu. Như vậy, những quyết định do agent dựa trên mục tiêu thực hiện cũng tương ứng với những quyết định do agent dựa trên tính hiệu quả thực hiện. Nghiên cứu planning để giải bài toán xác định lộ trình 37 Hình 2.5 thể hiện cấu trúc tổng quát của một agent dựa trên tính hiệu quả. 2 MÔI TRƯỜNG 2.1. Khái niệm Môi trường là tất cả những gì xung quanh agent, cung cấp nhận thức cho agent và agent tác động trở lại môi trường qua những hành động của nó. Trong môi trường này, ngoài agent được quan sát còn có nhiều agent khác. Trạng thái Môi trường tiến triển như thế nào? Hành động của tôi làm gì? Hiệu quả Cơ quan phản ứng Môi trường như thế nào? Sẽ như thế nào nếu tôi thực hiện hành động A? Bây giờ tôi nên thực hiện hành động nào? Cơ quan phản ứng Agent M ôitrường Hình 2.5. Agent dựa trên tính hiệu quả hoàn chỉnh Tôi hài lòng thế nào với trạng thái này? Nghiên cứu planning để giải bài toán xác định lộ trình 38 2.2. Các loại môi trường và thuộc tính của nó 2.2.1. Môi trường tiếp cận được và không tiếp cận được Môi trường gọi là tiếp cận được đối với một agent nào đó, nếu các công cụ cảm biến của nó có thể truy cập đến trạng thái hoàn chỉnh của môi trường đó. Môi trường có thể được tiếp cận một cách hiệu quả nếu các cơ quan cảm biến của agent có thể dò tìm tất cả các khía cạnh phù hợp để lựa chọn hành động. Môi trường tiếp cận được rất thuận lợi bởi vì agent không cần phải lưu bất kỳ trạng thái bên trong nào để theo dõi môi trường. 2.2.2. Môi trường xác định và không xác định Nếu ta có thể xác định trạng thái kế tiếp của môi trường khi biết được trạng thái hiện hành và những hành động agent chọn, thì ta gọi đó là môi trường xác định. Về nguyên tắc thì agent không phải lo gì về những thay đổi của môi trường tiếp cận được và xác định. Tuy nhiên, nếu môi trường không thể truy cập thì nó có thể là không xác định. Và đối với những môi trường phức tạp thì rất khó để theo dõi tất cả các khía cạnh không xác định. Như vậy, tùy theo góc nhìn của agent mà đánh giá môi trường là xác định hay không xác định. 2.2.3. Môi trường episodic và nonepisodic Trong môi trường episodic, người ta chia kinh nghiệm của agent thành các “episodic”. Mỗi episodic bao gồm nhận thức và hành động của agent. Hiệu quả của hành động mà agent thực hiện chỉ phụ thuộc vào episodic của nó, vì các episodic sau không phụ thuộc vào các hành động xuất hiện ở các episodic trước. Nghiên cứu planning để giải bài toán xác định lộ trình 39 2.2.4. Môi trường tĩnh và động Nếu môi trường có khả năng thay đổi trong khi agent đang tính toán, nó được gọi là môi trường động, ngược lại là môi trường tĩnh. Môi trường tĩnh là môi trường dễ dàng cho agent, bởi vì nó không cần phải lưu giữ những quan sát môi trường trong khi quyết định một hành động, cũng không lo thời gian trôi qua làm thay đổi trạng thái môi trường. Nếu môi trường không thay đổi theo thời gian, nhưng kết quả thực thi lại thay đổi thì ta gọi đó là môi trường bán tĩnh. 2.2.5. Môi trường rời rạc và liên tục Nếu có sự phân biệt rõ ràng những tri thức và hành động được định nghĩa trước thì ta gọi môi trường là rời rạc. Ví dụ, trò chơi cờ là rời rạc – nó có sự di chuyển cố định trong mỗi lần đi. Lái taxi và các phương tiện khác là liên tục - tốc độ và vị trí của taxi quét qua một dãy các giá trị liên tục. Bảng sau đây nêu lên các thuộc tính của các môi trường quen thuộc. Các câu trả lời có thể thay đổi phụ thuộc vào cách ta nhận thức môi trường và agent. Ví dụ, bài xì phé là xác định nếu agent có thể theo dõi các thẻ bài trên bàn, ngược lại là không xác định. Nghiên cứu planning để giải bài toán xác định lộ trình 40 Môi trường Tiếp cận được Xác định Episodic Tĩnh Rời rạc Cờ có tính thời gian Cờ không tính thời gian Bài xì phé Lái taxi Hệ thống chẩn đoán y khoa Hệ thống phân tích ảnh Bộ điều khiển nhà máy lọc Dạy Tiếng Anh giao tiếp Yes Yes No No No Yes No No Yes Yes No No No Yes No No No No No No No Yes No No Semi Yes Yes No No Semi No No Yes Yes Yes No No No No Yes Nghiên cứu planning để giải bài toán xác định lộ trình 41 CHƯƠNG 3: CÁC LÝ THUYẾT LIÊN QUAN ĐẾN LẬP KẾ HOẠCH 1. Giải toán bằng phương pháp tìm kiếm 2. Giới thiệu ngôn ngữ mô tả bài toán Nghiên cứu planning để giải bài toán xác định lộ trình 42 CHƯƠNG 3: CÁC LÝ THUYẾT LIÊN QUAN ĐẾN LẬP KẾ HOẠCH 1 GIẢI TOÁN BẰNG PHƯƠNG PHÁP TÌM KIẾM Như đã biết agent phản xạ đơn giản không thể dự đoán trước tình huống. Agent này chỉ thực thi một số hành động hạn chế, vì những hành động của chúng chỉ được xác định bởi tri thức hiện hành. Hơn nữa, chúng cũng không biết những hành động đó làm gì và muốn thu được kết quả gì. Agent giải quyết bài toán thuộc loại agent dựa trên mục tiêu có thể khắc phục các vấn đề của agent phản xạ đơn giản. Agent giải quyết bài toán quyết định làm gì bằng cách tìm kiếm những chuỗi hành động thu được những trạng thái mong muốn. Và ta sẽ xem cách mà agent đưa ra giải pháp tương ứng với bài toán mà nó cần giải quyết. 1.1. Agent giải quyết bài toán 1.1.1. Mô tả Bước đầu tiên trong việc giải quyết vấn đề là sự thiết lập mục tiêu, dựa trên ngữ cảnh hiện hành. Cùng với việc thiết lập mục tiêu, agent phải chú ý đến những nhân tố khác ảnh hưởng đến khả năng thu được mục tiêu. Mục tiêu là tập hợp các trạng thái môi trường, mà chỉ ở những trạng thái đó mục tiêu mới được thoả mãn. Các hành động là nguyên nhân chuyển đổi giữa các trạng thái môi trường. Như vậy, rõ ràng là agent phải tìm ra những hành động đưa nó đến trạng thái mục tiêu. Nhưng trước khi làm điều này, agent phải sắp xếp lại các hành động và Nghiên cứu planning để giải bài toán xác định lộ trình 43 các trạng thái cần xem xét, nhưng không đi vào hành động chi tiết ở mức thấp. Theo sau bước thiết lập mục tiêu là bước xây dựng bài toán, đây là quá trình quyết định các hành động và mục tiêu nào cần xem xét. 1.1.2. Ví dụ Ví dụ, agent muốn đi từ thành phố Arad đất nước Romania đến Bucharet bằng xe hơi. Vậy mục đích là đến Bucharet. Nhưng từ Arad ta chỉ có thể đến 3 thành phố là Sibiu, Timisoara và Zerind. Không có đường nào đến mục tiêu, và giả sử agent không quen thuộc các con đường ở Romaria. Do đó, agent không biết hành động nào là tốt nhất, nó không đủ tri thức để biết trạng thái kết quả của mỗi hành động. Nếu không có thêm tri thức, chọn một con đường bất kỳ để đi. Nhưng giả sử rằng agent có một bản đồ Romania, trên giấy hay trong bộ nhớ của nó. Bản đồ giúp agent biết được tình trạng có thể lâm vào nếu thực hiện hành động. Với bản đồ này, agent có thể quan sát các chuỗi trạng thái con của cuộc hành trình hoạch định qua mỗi thành phố, và tìm xem hành trình nào đến Bucharet. Với những lựa chọn chưa biết giá trị, để biết phải làm gì, agent thử nghiệm các chuỗi hành động khác nhau đưa đến các trạng thái đã biết giá trị, và sau đó lựa chọn chuỗi hành động tốt nhất, đây gọi là quá trình tìm kiếm. 1.1.3. Chương trình agent giải quyết bài toán đơn giản Thuật toán tìm kiếm lấy bài toán làm đầu vào và trả về giải pháp theo dạng chuỗi hành động. Khi một giải pháp được tìm thấy, các hành động trong đó được thực thi. Đây được gọi là quá trình thực thi. Như vậy, ta có một thiết kế đơn giản cho agent gồm 3 quá trình: thiết lập, tìm kiếm và thực thi. Thuật toán sau thể hiện agent giải quyết bài toán đơn giản. Sau Nghiên cứu planning để giải bài toán xác định lộ trình 44 khi thiết lập mục tiêu và bài toán cần giải quyết, agent gọi hàm search để giải bài toán. Khi giải pháp được thực thi, agent sẽ tìm mục tiêu mới. Hai hàm CẬP NHẬT TRẠNG THÁI và THIẾT LẬP MỤC TIÊU được mô tả sau. Việc thực thi giải pháp thì dễ dàng đối với agent giải quyết bài toán đơn giản: hàm CHỌN HÀNH ĐỘNG chỉ lấy hành động đầu tiên trong chuỗi hành động, hàm HÀNH ĐỘNG CÒN LẠI trả về các hành động còn lại 1.2. Thiết lập bài toán Trước khi đi vào chi tiết sự thiết lập bài toán ta cần quan tâm đến những tri thức về hành động và trạng thái của agent. Những tri thức này phụ thuộc vào mối liên hệ giữa agent và môi trường qua sự nhận thức và hành động của nó. function AGENT GIẢI QUYẾT BÀI TOÁN ĐƠN GIẢN (p) trả về hành động inputs: p, tri thức static: s, chuỗi hành động, khởi tạo là rỗng trạng thái, mô tả trạng thái môi trường hiện hành g, mục tiêu, khởi đầu là null bài toán, sự mô tả bài toán trạng thái – CẬP NHẬT TRẠNG THÁI(trạng thái,p) if s rỗng then g – THIẾT LẬP MỤC TIÊU(trạng thái) bài toán – THIẾT LẬP BÀI TOÁN(trạng thái,g) s – TÌM KIẾM(bài toán) hành động – CHỌN HÀNH ĐỘNG(s,trạng thái) s – HÀNH ĐỘNG CÒN LẠI(s,trạng thái) return hành động Problem-solving agent đơn giản Nghiên cứu planning để giải bài toán xác định lộ trình 45 Có 4 loại bài toán cơ bản khác nhau: bài toán trạng thái đơn, bài toán đa trạng thái, bài toán ngẫu nhiên và bài toán khảo sát. Mô tả cụ thể các loại bài toán được nói đến trong phần sau. 1.2.1. Các kiểu bài toán Xét ví dụ, agent cần làm sạch môi trường. Giả sử môi trường chỉ có 2 vị trí, mỗi vị trí có hoặc không có rác và agent có thể ở một trong hai vị trị trí. Có 8 trạng thái có thể xảy ra. Với bài toán này, agent có 3 hành động: Qua trái, Qua phải và Nhặt. Giải sử hành động Nhặt có hiệu quả 100%. Mục tiêu là làm sạch tất cả rác. Tương ứng với trạng thái {7,8} . Hình 3.1 thể hiện bài toán này. Hình 3.1. Bài toán agent làm sạch môi trường. 1.2.1.1. Bài toán trạng thái đơn Đối với bài toán này, agent ở trong môi trường xác định và có thể truy cập được. Agent biết rõ mình đang ở đâu và cần làm gì. Agent tính toán được trạng thái kết quả sau khi thực hiện chuỗi hành động. Cụ thể: Agent có bộ cảm biến và biết mình đang ở trạng thái 5 và biết rằng sau chuỗi hành động [Qua phải,Nhặt] nó sẽ thu được trạng thái mục tiêu. Nghiên cứu planning để giải bài toán xác định lộ trình 46 1.2.1.2. Bài toán đa trạng thái Agent ở trong môi trường xác định nhưng không thể tiếp cận được. Agent biết mình phải làm gì nhưng không biết mình đang ở đâu. Trong môi trường này agent phải suy luận về tập trạng thái mà nó có thể gặp phải. Trường hợp này, agent không có cơ quan cảm biến. Nó chỉ biết trạng thái ban đầu là tập hợp {1,2,3,4,5,6,7,8}. Tuy tình trạng này là khó khăn, nhưng agent vẫn làm việc tốt. Agent tính được là sau khi thực thi hành động Qua phải nó sẽ ở một trong các trạng thái {2,4,6,8}. Thực tế, agent có thể nhận thấy rằng chuỗi hành động [Qua phải,Nhặt,Qua trái,Nhặt] đảm bảo tìm thấy trạng thái mục tiêu. 1.2.1.3. Bài toán ngẫu nhiên Agent ở trong môi trường không xác định và cũng không thể truy cập được. Để giải quyết bài toán này, agent phải tính toàn bộ cây hành động, không chỉ chuỗi hành động đơn giản. Mỗi nhánh trong cây là một trường hợp ngẫu nhiên có thể phát sinh. Môi trường tự nhiên là một bài toán ngẫu nhiên vì sự dự đoán chính xác các trạng thái trong môi trường là không khả thi. Ví dụ cụ thể của bài toán này như sau: Giả sử agent tuân theo luật của Murphy là: hành động Nhặt đôi khi sẽ đặt rác lên tấm thảm nếu như tại đó không có rác. Ví dụ, nếu agent ở trạng thái 4, thì sau hành động Nhặt nó sẽ ở một trong các trạng thái {2,4}. Trong cây hành động, nếu agent đang ở một trong các vị trí {1,3}. Agent có thể đưa ra chuỗi hành động như sau [Nhặt,Qua phải,Nhặt]. Hành động Nhặt sẽ đặt agent vào một trong hai trạng thái {5,7} và hành động Qua phải sẽ đặt vào một trong hai trạng thái {6,8}. Nếu agent ở trạng thái 6 thì chuỗi hành động sẽ thành công, nếu ở trạng thái 8 thì kế hoạch thất bại. Nếu agent lựa chọn chuỗi hành động đơn giản hơn như Nghiên cứu planning để giải bài toán xác định lộ trình 47 [Nhặt], agent ở một trong hai trạng thái {5,7} thì đôi khi kế hoạch cũng thành công, nhưng không phải lúc này cũng vậy. Đối với bài toán này, không thể đưa ra chuỗi hành động cố định đảm bảo giải pháp thành công. 1.2.1.4. Bài toán khảo sát Agent không biết không gian trạng thái của bài toán, không biết thông tin kết quả của hành động. Giống như đi từ nơi này đến nơi khác mà không có bản đồ. Đây là bài toán khó nhất đối với agent thông minh. Agent phải thử nghiệm và từ từ khám phá xem hành động của nó làm gì và sắp xếp các trạng thái đang tồn tại. Agent học bản đồ môi trường và sử dụng nó để giải quyết bài toán. 1.2.2. Định nghĩa bài toán và giải pháp Bài toán là tập hợp các thông tin agent sẽ dùng để quyết định xem sẽ làm gì. Những thành phần cơ bản của bài toán gồm trạng thái và hành động: • Trạng thái ban đầu của agent. • Tập hợp các hành động sẵn có của agent. Thuật ngữ toán tử được dùng để biểu diễn sự mô tả hành động theo trạng thái tìm kiếm bằng cách thực thi các hành động trong trạng thái cụ thể. Ví dụ, cho hàm S và trạng thái cụ thể x, S(x) trả về tập các trạng thái có thể tìm thấy từ x bởi bất cứ hành động đơn giản nào. • Sự kiểm tra mục tiêu dùng để xác định xem trạng thái nào đó có phải là trạng thái mục tiêu không. Hay khi có tập các trạng thái mục tiêu rõ ràng, sự kiểm tra chỉ đơn giản xem agent có tìm ra một trong các trạng thái đó hay không. Nhưng đôi khi, mục tiêu được xác định bởi các thuộc tính trừu tượng, không phải tập các trạng thái được liệt kê rõ ràng. Nghiên cứu planning để giải bài toán xác định lộ trình 48 • Hàm chi phí đường đi là hàm gán chi phí cho một con đường. Với chi phí cho một con đường là tổng chi phí của các hành động riêng rẽ dọc theo con đường. Ký hiệu của hàm chi phí đường đi là g. Với: o Không gian trạng thái của bài toán là tập hợp tất cả các trạng thái có thể tìm thấy từ trạng thái ban đầu bởi bất kỳ chuỗi hành động nào. o Đường đi trong không gian trạng thái là bất kỳ chuỗi hành động nào dẫn từ trạng thái này sang trạng thái khác. o Chi phí đường đi chỉ ra giải pháp này phù hợp hơn giải pháp kia. Như vậy, trạng thái ban đầu, tập hợp các toán tử, sự kiểm tra mục tiêu và hàm chi phí đường đi định nghĩa bài toán. Ta có thể định nghĩa kiểu dữ liệu trình bày các bài toán như sau: Thể hiện của kiểu dữ liệu này sẽ là đầu vào cho thuật toán tìm kiếm của chúng ta. Đầu ra của thuật toán là một giải pháp, đó là đường đi từ trạng thái khởi đầu đến trạng thái thỏa mãn hàm kiểm tra mục tiêu. 1.2.3. Đo mức độ thực thi của việc giải toán 1.2.3.1. Các phương pháp đo độ thực thi Có ít nhất 3 cách để đo tính hiệu quả của việc tìm kiếm. a) Nó có tìm ra giải pháp trong tất cả các trường hợp hay không? b) Giải pháp tìm thấy có phải là giải pháp tốt không (chí phí đường đi thấp)? datatype BÀI TOÁN components: TRẠNG THÁI BAN ĐẦU, TẬP CÁC TOÁN TỬ, KIỂM TRA MỤC TIÊU, HÀM CHI PHÍ ĐƯỜNG ĐI Nghiên cứu planning để giải bài toán xác định lộ trình 49 c) Chi phí tìm kiếm liên kết với thời gian và bộ nhớ yêu cầu để tìm ra giải pháp là gì? Tổng chi phí tìm kiếm là tổng của chi phí đường đi và chi phí tìm kiếm. 1.2.3.2. Ví dụ Ví dụ, bài toán tìm kiếm lộ trình từ Arad đến Bucharet. − Chi phí đường đi có thể tương ứng với tổng số dặm của con đường. − Chi phí tìm kiếm phụ thuộc vào từng tình huống. Trong môi trường tĩnh, chi phí tìm kiếm có thể bằng 0 bởi vì độ đo thực thi phụ thuộc vào thời gian. Ví dụ đi từ Arad đến Bucharet, môi trường là bán động vì tính toán dài hơn, chi phí sẽ cao hơn. Trong trường hợp này, chi phí tìm kiếm biến đổi gần như xấp xỉ với thời gian tính toán (ít nhất là với lượng thời gian nhỏ). Để tính tổng chi phí, ta phải cộng số dặm và mili giây. Điều này không dễ vì ta không có tỉ lệ trao đổi chuẩn giữa hai đơn vị này. Agent phải biết cách quyết định, tài nguyên nào giành cho tìm kiếm và tài nguyên nào dành cho thực thi. Đối với những bài toán có không gian trạng thái rất nhỏ, ta dễ dàng tìm thấy những giải pháp với chi phí đường đi thấp nhất. Nhưng với không gian tìm kiếm lớn, bài toán phức tạp, rất khó khăn để có được chi phí tối ưu cả hai mặt – agent có thể thu được giải pháp tối ưu nhưng phải tìm kiếm trong thời gian dài, hay agent có thể tìm kiếm trong thời gian ngắn và thu được giải pháp với chi phí đường đi lớn hơn. 1.2.4. Chọn trạng thái và hành động Giả sử, xét bài toán “Lái xe từ Arad đến Bucharest sử dụng các con đường trong bản đồ hình 3.2.” Không gian trạng thái tương ứng có 20 trạng thái, một trạng thái được định nghĩa bằng một vị trí duy nhất, xác định một thành phố. Nghiên cứu planning để giải bài toán xác định lộ trình 50 Hình 3.2 Bản đồ đơn giản của Romaria Bài toán được mô tả như sau: 1. trạng thái ban đầu: “ở Arad” 2. các toán tử: Arad → Zerind Arad → Sibiu 3. sự kiểm tra mục tiêu: “Đây có phải là Bucharet không?” hay x = “at Bucharest” 4. chi phí đường đi: có thể là số dặm, cũng có thể là thời gian lưu thông. Nhưng bản đồ của chúng ta thì không xác định chúng, nên ta giả sử hàm chi phí đường đi sẽ đo số bước phải đi qua. 5. giải pháp: chuỗi toán tử đi từ trạng thái ban đầu đến trạng thái mục tiêu. Có rất nhiều giải pháp nhưng giải pháp đi qua Sibiu và Fagaras, có chi phí đường đi là 3 là giải pháp tốt nhất. Môi trường thế giới thực rất phức tạp. Đối với cách tiếp cận giải quyết bài toán không gian trạng thái phải được mô tả trừu tượng. Đây gọi Nghiên cứu planning để giải bài toán xác định lộ trình 51 là sự trừu tượng hoá. Quá trình này bỏ qua chi tiết của các trạng thái và hành động. Cụ thể: • Trạng thái trừu tượng: tập các trạng thái thực. Ví dụ: “at Arad”, “at Bucharest”. Bỏ qua các trạng thái môi trường khác như: trạm dừng kế tiếp bao xa, điều kiện đường đi, thời tiết, v.v… • Toán tử trừu trượng: mô tả các hành động thực trong môi trượng. Ví dụ: “Arad → Zerind” bỏ qua việc đi đúng luật, tiêu thụ nhiên liệu, v.v… • Giải pháp trừu tượng: tập các con đường trong thế giới thực. Việc thực thi những hành động trừu tượng trong giải pháp trừu tượng dễ hơn so với bài toán gốc. 1.3. Tìm kiếm giải pháp Việc tìm kiếm giải pháp được thực hiện bằng cách tìm qua không gian trạng thái. Ý tưởng là duy trì và mở rộng tập các chuỗi giải pháp cục bộ. Phần này trình bày cách tạo ra chuỗi giải pháp và cách lưu chúng trong những cấu trúc dữ liệu thích hợp. 1.3.1. Tạo các chuỗi hành động Bản chất của việc tìm kiếm là: chọn một trạng thái và đặt những cái khác qua một bên cho lần sau khi lựa chọn đầu tiên này không đưa đến giải pháp. Với mỗi trạng thái được chọn, ta kiểm tra xem nó có phải là trạng thái mục tiêu không. Nếu không phải, xét tiếp những trạng thái mới được tạo ra từ trạng thái hiện hành bằng cách áp dụng các toán tử. Đây gọi là quá trình mở rộng trạng thái. Các quá trình lựa chọn, kiểm tra và mở rộng tiếp tục cho đến khi giải pháp được tìm thấy hoặc cho đến khi không còn Nghiên cứu planning để giải bài toán xác định lộ trình 52 trạng thái nào để mở rộng nữa. Việc chọn trạng thái nào để mở rộng được xác định bởi giải pháp tìm kiếm. Ví dụ để giải quyết bài toán từ Arad đến Bucharest, ta bắt đầu với trạng thái khởi đầu là Arad. Kiểm tra xem nó có phải là trạng thái mục tiêu không. Rõ ràng là không phải, điều này rất quan trọng để tránh gặp phải vấn đề là “bắt đầu từ Arad, đến Arad.” Vì đây không phải là trạng thái mục tiêu nên ta, nên ta phải khảo sát các trạng thái khác. Áp dụng các operator với trạng thái ở Arad, tạo ra tập các trạng thái mới “ở Sibiu”, “ở Timisoara” và “ở Zerind”, vì có con đường trực tiếp từ Arad đến các thành phố này. Do có nhiều trạng thái để chọn, ta chọn một trạng thái và để các trạng thái khác cho lần lựa chọn sau. Giả sử chọn Zerind. Kiểm tra xem nó có phải là trạng thái mục tiêu không (trong trường hợp này là không), sau đó mở rộng nó “ở Arad” và “ở Oradea.” Bây giờ, có thể chọn một trong hai trạng thái, hoặc trở về và chọn Sibiu hay Timisoara. Quá trình này tiếp tục cho đến khi tìm thấy giải pháp, Để dễ dàng cho quá trình tìm kiếm, ta xây dựng cây tìm kiếm (search tree) trong không gian trạng thái. Nút gốc của cây tìm kiếm gọi là nút tìm kiếm (search node) ứng với trạng thái ban đầu. Các nút lá ứng với trạng thái không có kế thừa trong cây vì chúng chưa được mở rộng, hoặc đã mở rộng rồi nhưng tạo ra tập rỗng. Ở mỗi bước thuật toán tìm kiếm chọn một nút là để mở rộng. Nghiên cứu planning để giải bài toán xác định lộ trình 53 Hình 3.3 thể hiện sự mở rộng cây tìm kiếm đối với bài toán tìm đường đi từ Arad đến Bucharet. Thuật toán tìm kiếm tổng quát như sau: a) Trạng thái mở đầu Arad Arad ZerindTimisoaraSibiu b) Sau khi mở rộng Arad Arad ZerindTimisoaraSibiu OradeFagaraArad Rimnicu c) Sau khi mở rộng Sibiu Hình 3.3. Cây tìm kiếm cục bộ cho việc tìm kiếm tuyến đường từ Arad đến Bucharest function TÌM KIẾM(bài toán,chiến lược) trả về một giải pháp hay thất bại khởi tạo cây tìm kiếm sử dụng trạng thái ban đầu của bài toán loop do if không có trạng thái nào để mở rộng then return thất bại chọn một nút lá để mở rộng theo chiến lược if nút đó là trạng thái mục tiêu then return giải pháp tương ứng else mở rộng nút và thêm nút kết quả vào cây tìm kiếm end Nghiên cứu planning để giải bài toán xác định lộ trình 54 Phân biệt giữa không gian trạng thái và cây tìm kiếm. • Trong không gian trạng thái số trạng thái là hữu hạn. • Trong cây tìm kiếm số nút là vô hạn. Trong bài toán tìm đường đi, chỉ có 20 trạng thái trong không gian trạng thái, nhưng có vô số đường đi trong không gian trạng thái này. Vì vậy, có vô số nút trong cây tìm kiếm. Ví dụ Arad-Sibiu-Arad-Sibiu… Một thuật toán tìm kiếm hiệu quả sẽ tránh được sự lẩn quẩn như vậy. 1.3.2. Cấu trúc dữ liệu của cây tìm kiếm Có nhiều cách biễu diễn nút, nhưng ở đây, giả sử nút là một cấu trúc dữ liệu có 5 thành phần: • Trạng thái của nút trong không gian trạng thái; • Nút cha của nó trong cây tìm kiếm; • Toán tử được áp dụng để tạo ra nút; • Chiều sâu của nút – số nút trên đường đi từ nút gốc đến nút này; • Chi phí đường đi từ trạng thái ban đầu đến nút này. Kiểu dữ liệu nút: Nút và trạng thái • Nút là cấu trúc dữ liệu tính toán dùng để biểu diễn cây tìm kiếm trong những bài toán cụ thể, được tạo ra bởi một thuật toán cụ thể. • Trạng thái thể hiện dạng (hoặc tập các dạng) của môi trường. datatype nút components: TRẠNG THÁI, NÚT CHA, TOÁN TỬ, CHIỀU SÂU, CHI PHÍ ĐƯỜNG ĐI Nghiên cứu planning để giải bài toán xác định lộ trình 55 Vì vậy, nút có chiều sâu và có nút cha, trong khi trạng thái không có. Ta có thể có hai nút khác nhau nhưng có cùng một trạng thái, nếu trạng thái đó được tạo ra bởi hai chuỗi hành động khác nhau. Phương pháp tìm kiếm là một hàm, hàm này sẽ chọn nút kế tiếp được mở rộng trong tập các nút chờ được mở rộng. Hàm tìm kiếm phải xem qua tất cả các nút trong tập này để chọn nút thích hợp nhất. Giả sử rằng tất cả các nút được đặt trong một hàng đợi. Các thao tác trên hàng đợi như sau: • TẠO HÀNG ĐỢI(các thành phần) tạo một hàng đợi với các thành phần được cho. • RỖNG?(Hàng đợi) trả về true nếu không có thành phần nào trong hàng đợi. • LẤY PHẦN TỬ ĐẦU(Hàng đợi) trả về và xoá thành phần ở trước hàng đợi. • CHÈN(Các thành phần,Hàng đợi) chèn một tập các thành phần vào hàng đợi. Với những định nghĩa này, thuật toán tìm kiếm tổng quát được cải tiến như sau: function TÌM KIẾM(bài toán,CHÈN) trả về một giải pháp hay thất bại tập các nút – TẠO HÀNG ĐỢI(TẠO NÚT(TRẠNG THÁI BAN ĐẦU [bài toán])) loop do if tập các nút là rỗng then return thất bại nút – LẤY PHẨN TỬ ĐẦU(tập các nút) if KIỂM TRA MỤC TIÊU[bài toán] được áp dụng với TRẠNG THÁI(nút) thành công then return nút tập các nút – CHÈN(tập các nút,MỞ RỘNG(nút,TẬP TOÁN TỬ[bài toán])) end Nghiên cứu planning để giải bài toán xác định lộ trình 56 2 GIỚI THIỆU NGÔN NGỮ MÔ TẢ BÀI TOÁN Ngôn ngữ mô tả bài toán chủ yếu được dùng để trình bày tri thức. Mục tiêu của trình bày tri thức là mô tả tri thức ở dạng dễ xử lí trên máy tính, giúp agent hoạt động tốt hơn. Phần này mô tả bản chất của ngôn ngữ trình bày và bản chất của các ngôn ngữ logic cụ thể, giải thích chi tiết mối quan hệ giữa ngôn ngữ và cơ cấu suy luận đi chung với ngôn ngữ. Ngôn ngữ trình bày tri thức được định nghĩa ở hai khía cạnh: • Cú pháp ngôn ngữ mô tả hình dạng để tạo thành câu. Cú pháp thường được mô tả theo cách các câu được trình bày trên giấy, nhưng sự trình bày thật sự ở bên trong máy tính: mỗi câu được trình bày bởi một cấu hình vật lí, một mẫu vật lí điện tử trong bộ nhớ máy tính. • Ngữ nghĩa xác định những sự kiện trong môi trường mà câu đề cập đến. Không có ngữ nghĩa, mỗi câu chỉ là sự sắp xếp điện tử hay là một tập hợp các dấu hiệu trên giấy. Với ngữ nghĩa, mỗi câu là một xác nhận về môi trường. Và với ngữ nghĩa, ta nói rằng khi một hình dạng cụ thể tồn tại trong agent, thì agent sẽ tin câu tương ứng. Ví dụ, cú pháp ngôn ngữ của công thức toán nói rằng nếu x và y là các biểu thức số, thì x ≥ y là một câu về số. Ý nghĩa ngôn ngữ nói rằng x ≥ y là sai khi y là số lớn hơn x và đúng khi ngược lại. Cú pháp và ngữ nghĩa sẽ được định nghĩa chính xác hơn với ngôn ngữ logic. Từ cú pháp và ngữ nghĩa này, ta có thể kế thừa cơ cấu suy luận đối với agent sử dụng ngôn ngữ này. Ngữ nghĩa của ngôn ngữ xác định sự kiện mà câu đề cập đến. Sự phân biệt giữa sự kiện và sự trình bày của nó là rất quan trọng. Sự kiện là Nghiên cứu planning để giải bài toán xác định lộ trình 57 một phần của môi trường, trong khi sự trình bày của nó phải được mã hoá theo những cách mà nó có thể lưu trữ vật lí trong agent. Ta không thể đặt môi trường trong máy tính (cũng không thể đặt trong con người), vì vậy tất cả các cơ cấu suy luận phải thao tác trên sự trình bày sự kiện hơn là trên bản thân sự kiện. Vì câu là một dạng vật lý của các thành phần trong agent, việc suy luận là một quá trình tạo thành các dạng vật lý mới từ các dạng cũ. Suy luận hợp lý sẽ chắc rằng những dạng mới trình bày những sự kiện theo sau những sự kiện được trình bày bởi dạng cũ. Hình 3.4 thể hiện mối quan hệ giữa ngữ nghĩa và câu: 2.1. Sự trình bày, suy luận và logic 2.1.1. Sự trình bày ngôn ngữ Phần này nói về bản chất của ngôn ngữ trình bày tri thức với mục tiêu thiết kế cú pháp và ngữ nghĩa tương ứng. Bắt đầu với hai lớp ngôn ngữ quen thuộc, ngôn ngữ lập trình và ngôn ngữ tự nhiên để xem chúng trình bày những gì và vấn đề là ở đâu. Ngôn ngữ lập trình được dùng tốt trong việc mô tả thuật toán và tạo ra cấu trúc dữ liệu. Tuy nhiên, các ngôn ngữ lập trình không thể trình bày tất cả các câu trong ngôn ngữ tự nhiên. Vấn đề của ngôn ngữ lập trình Sự trình bày Môi trường Các câu N gữ nghĩa Các sự kiện Câu Sự kiện N gữ nghĩa Tạo ra Dẫn tới Hình 3.4. Ngữ nghĩa của ngôn ngữ cung cấp mối liên hệ giữa câu và sự kiện. Thuộc tính của một sự kiện theo sau một sự kiện khác được ánh xạ bởi thuộc tính của một câu được tạo ra bởi những câu khác. Suy luận logic tạo ra những câu mới kế thừa từ những câu cũ. Nghiên cứu planning để giải bài toán xác định lộ trình 58 là nó được thiết kế để mô tả hoàn chỉnh trạng thái của máy tính và cách mà các trạng thái thay đổi trong khi thực thi chương trình. Nhưng chúng ta muốn ngôn ngữ trình bày tri thức hỗ trợ trong những trường hợp mà chúng ta không có thông tin hoàn chỉnh – nghĩa là không biết chắc thông tin như thế nào nhưng chỉ biết một vài khả năng của chúng. Vì vậy ngôn ngữ lập trình không đủ khả năng mô tả. Ngôn ngữ tự nhiên mô tả cụ thể hơn. Chẳng hạn, báo cáo này được viết bằng ngôn ngự tự nhiên. Ngôn ngữ tự nhiên đáp ứng được nhu cầu truyền thông hơn là ngôn ngữ đặc tả. Vì ngữ nghĩa của câu không chỉ phụ thuộc và bản thân câu đó mà còn phụ thuộc và ngữ cảnh khi câu được nói. Nhưng khi một câu được đưa vào cơ sở tri thức nó đã được tách rời khỏi ngữ cảnh. Ngôn ngữ tự nhiên có thể bị nhập nhằng, nhưng ngôn ngữ lập trình thì không. Một ngôn ngữ trình bày tri thức tốt cần kết hợp được các ưu điểm của ngôn ngữ tự nhiên và ngôn ngữ hình thức. Nó phải là ngôn ngữ mô tả và súc tích để diễn tả mọi thứ một cách cô đọng. Nó không được nhập nhằng và phải độc lập ngữ cảnh. Để những gì nói ra hôm nay vẫn có giá trị trong tương lai. Và nó cũng hiệu quả khi một hàm suy luận tạo ra những suy luận mới từ những câu trong ngôn ngữ của chúng ta. Nhiều ngôn ngữ trình bày đã được thiết kế để thu được các nguyên tắt này. Logic trật tự đầu tiên cũng là một ngôn ngữ như vậy vì nó tạo ra hầu hết các lược đồ trình bày trong AI. ™ Ngữ nghĩa Trong logic, nghĩa của câu là những gì nó nói về môi trường, môi trường như thế này, không như thế kia. Ngữ nghĩa của câu phụ thuộc vào người viết ra nó. Để câu có nghĩa, người viết phải cung cấp lời giải thích cho nó Nghiên cứu planning để giải bài toán xác định lộ trình 59 về sự kiện tương ứng. Một câu bản thân nó không có nghĩa nếu không được hiểu bởi người khác. Hai bên truyền thông có thể quy ước với nhau về cách mã hoá và giải mã một câu. Do đó, về nguyên tắc, mỗi câu có thể được giải thích tuỳ ý. Nhưng trong thực thế, tất cả các ngôn ngữ trình bày đều sử dụng mối quan hệ có hệ thống giữa câu và sự kiện. Như vậy, ngữ nghĩa đưa ra sự giải thích cho một câu. Một câu có thể đúng hay sai. Một câu là đúng với sự giải thích đó nếu trạng thái vấn đề nó trình bày có trường hợp đó, vì sự đúng hay sai phụ thuộc vào sự giải thích của câu và trạng thái thật sự của môi trường. 2.1.2. Suy luận Thuật ngữ “suy luận” thường dùng để chỉ bất kỳ quá trình nào tìm thấy kết quả. Ở đây, ta quan tâm đến suy luận hợp lý được gọi là suy luận logic hay suy diễn. Suy luận logic là quá trình thiết lập quan hệ kế thừa giữa các câu. Có nhiều cách thiết kế các hệ thống suy luận logic bắt đầu với ý tưởng câu hiển nhiên đúng. • Câu có giá trị và câu phù hợp Một câu có giá trị còn gọi là câu hiển nhiên đúng nếu và chỉ nếu nó đúng trong mọi sự giải thích trong tất cả các trượng hợp bất chấp ý nghĩa của nó và bất chấp trạng thái vấn đề trong môi trường được mô tả. Ví dụ: “Có người trong xe hay không có người trong xe.” Đây là câu có giá trị, nó đúng trong bất kỳ trường hợp nào. Câu phù hợp nếu và chỉ nếu nó tồn tại sự giải thích được trong môi trường nào đó mà sự giải thích đó là đúng. Câu không phù hợp còn gọi là câu mâu thuẫn. Nghiên cứu planning để giải bài toán xác định lộ trình 60 Tóm lại ta có thể nói rằng logic bao gồm: 1. Hệ thống mô tả trạng thái vấn đề, gồm: a. Cú pháp ngôn ngữ, mô tả cách tạo thành câu và b. Ngữ nghĩa ngôn ngữ đưa ra những ràng buộc hệ thống về cách mà câu liên hệ đến những trạng thái của vấn đề. 2. Thuyết chứng minh – tập luật để suy diễn các phần kế thừa của tập các câu. 2.2. Logic mệnh đề 2.2.1. Cú pháp Các ký hiệu của logic mệnh đề là những hằng logic True và False, các ký hiệu mệnh đề như P và Q, các liên từ logic: ∧, ∨, ⇔, ⇒, ¬, (). Các câu được tạo thành bằng cách đặt các ký hiệu này lại với nhau theo các luật sau: • Mỗi hằng logic True và False là câu. • Ký hiệu mệnh đề P hay Q đều là câu. • Dấu ngoặc bao quanh một câu cũng tạo ra một câu, ví dụ (P ∧ Q). • Một câu có thể được tạo ra bằng cách liên kết những câu đơn giản hơn bởi các liên từ logic: ∧ : và (liên từ kết hợp) ∨ : hoặc (liên từ phân biệt) ⇒ : suy ra ⇔ : tương đương ¬ : phủ định Với độ ưu tiên từ cao đến thấp: ¬, ∧, ∨, ⇒, ⇔ Nghiên cứu planning để giải bài toán xác định lộ trình 61 Ví dụ câu: ¬P ∨ Q ∧ R ⇒ S tương đương với câu: ((¬P) ∨ (Q ∧ R)) ⇒ S 2.2.2. Ngữ nghĩa Ngữ nghĩa của logic mệnh đề được định nghĩa bằng cách xác định sự giải thích những ký hiệu mệnh đề, các hằng và ý nghĩa của các liên từ logic. Ký hiệu mệnh đề tuỳ thuộc vào người viết. Ví dụ: P có thể là sự kiện Hà Nội là thủ đô của Việt Nam, nhưng cũng có thể là Bông hoa màu xanh. Câu chỉ chứa một ký hiệu mệnh đề là câu phù hợp nhưng không có giá trị: nó chỉ đúng khi đưa ra sự kiện trong một trường hợp cụ thể. Ta sử dụng bảng sự thật để thể hiện giá trị của các mệnh đề và liên từ: P Q ¬P P ∧ Q P ∨ Q P ⇒ Q P ⇔ Q False False True False False True True False True True False True True False True False False False True False False True True False True True True True 2.3. Logic trật tự đầu tiên Logic mệnh đề là một trong những ngôn ngữ đơn giản nhất. Nhưng nó quá hạn chế, chỉ thao tác trên sự kiện. Điều này gây khó khăn trong việc trình bày cả những vấn đề đơn giản. Nghiên cứu planning để giải bài toán xác định lộ trình 62 Logic trật tự đầu tiên là ngôn ngữ mạnh hơn logic mệnh đề. Nó xem môi trường bao gồm các đối tượng và các thuộc tính phân biệt giữa các đối tượng với nhau. Giữa các đối tượng này có các quan hệ khác nhau. Một số quan hệ là chức năng, đây là những quan hệ chỉ có một giá trị đầu vào. Ví dụ về những đối tượng, những thuộc tính, những quan hệ và chức năng: • Các đối tượng: con người, nhà, số, học thuyết, TP Hồ Chí Minh, màu sắc, chiến tranh, tiền … • Các quan hệ: anh em của, lớn hơn, bên trong, thành phần của, có màu, xuất hiện sau khi, của… • Các thuộc tính: đỏ, tròn, ảo, giỏi… • Các chức năng: cha của, bạn tốt nhất, một lần nữa… Ví dụ: Một cộng hai bằng ba Các đối tượng: một, hai, ba; Quan hệ: bằng; Chức năng: cộng Đặc tính của logic trật tự đầu tiên là cho phép người dùng tự do mô tả những cái mình muốn theo cách tương ứng với môi trường. 2.3.1. Cú pháp và ngữ nghĩa Mỗi mô tả của logic mệnh đề là một câu, nó trình bày sự kiện. Logic trật tự đầu tiên có câu, ngoài ra còn có term, để trình bày đối tượng. Các ký hiệu hằng, biến và ký hiệu chức năng được dùng để xây dựng term, các lượng từ và vị từ dùng để xây dựng câu. • Các ký hiệu hằng: A, B, C, John… Nghiên cứu planning để giải bài toán xác định lộ trình 63 Đối tượng trong môi trường được chỉ đến bởi ký hiệu hằng. Mỗi hằng xác định chính xác tên đối tượng, nhưng không phải tất cả các đối tượng đều cần có tên và một đối tượng có thể có nhiều tên. • Các ký hiệu vị từ: Tròn, anh em… Mỗi mối quan hệ cụ thể được xác định bởi một vị từ. Ví dụ, ký hiệu Brother chỉ mối quan hệ anh em, quan hệ này chứa một cặp đối tượng. Trong ngữ cảnh tương ứng, quan hệ này được định nghĩa bởi một tập các đối tượng được sắp xếp cố định. Các đối tượng được viết trong dấu ngoặc. Ví dụ, có ba đối tượng John, Richard, Robin là ba anh em theo thứ tự. Quan hệ được định nghĩa như sau: {(John, Richard),(Richard, Robin)} • Các ký hiệu chức năng: Cha của, chân trái của… Không giống những ký hiệu vị từ, ký hiệu chức năng được dùng để chỉ đến những đối tượng cụ thể mà không dùng tên của chúng. Term làm một mô tả logic chỉ đến một đối tượng. Vì vậy, các ký hiệu hằng là các term. Đôi khi, term thuận tiện hơn trong việc mô tả đối tượng. Ví dụ, muốn nói đến cái áo của John, ký hiệu hằng là John’s shirt. Thay vì vậy ta có thể dùng ShirtOf(John). Một term phức tạp được tạo nên bởi một ký hiệu chức năng, theo sau bởi dãy các term trong dấu ngoặc đơn như là các tham số cho ký hiệu chức năng 2.3.2. Các ví dụ ¾ Câu đơn giản Ta có các term chỉ các đối tượng, và ký hiệu vị từ chỉ các quan hệ, ta có thể đặt chúng lại với nhau tạo thành câu đơn giản chỉ các sự kiện. Câu đơn giản được tạo nên từ một ký hiệu vị từ theo sau bởi danh sách các term trong dấu ngoặc. Ví dụ: Nghiên cứu planning để giải bài toán xác định lộ trình 64 Brother(Richard, John) Câu đơn giản có những tham số là các term phức tạp: Married(FatherOf(Richard), MotherOf(John)) ¾ Câu phức tạp Ta có thể dùng các liên từ logic để xây dựng câu phức tạp. Ví dụ: • Brother(Richard, John) ∧ Borther(John, Richard) chỉ đúng khi John là anh em của Richard và Richard là anh em của John. • Older(John, 30) ∨ Younger(John, 30) sai khi John 30 tuổi. • Older(John, 30) ⇒ ¬Younger(John, 30) : nếu John lớn hơn 30 tuổi thì anh ấy không thể nhỏ hơn 30. ¬Brother(Robin, John): đúng khi Robin không phải là anh em của John. 2.3.3. Lượng từ Logic trật tự đầu tiên chứa hai lượng từ chuẩn đó là với mọi và tồn tại. 1) Lượng từ với mọi (∀): được dùng để mô tả toàn bộ tập hợp đối tượng mà không phải liệt kê từng phần tử. Ví dụ: Câu “All cats are mamals” được mô tả như sau: ∀x Cat(x) ⇒ Mamal(x) 2) Lượng từ tồn tại (∃): dùng để chỉ một đối tượng cụ thể nhưng không cần nêu tên. Ví dụ: Lan là chị em của một sinh viên nào đó, ta nói: ∃x Sister(x, Lan) ∧ Student(x) Mối liên hệ giữa ∀ và ∃ Hai lượng từ này có mối quan hệ mật thiết vơi nhau thông qua liên từ phủ định. Cụ thể như sau: Nghiên cứu planning để giải bài toán xác định lộ trình 65 ∀x ¬P ≡ ¬∃x P ¬P ∧ ¬Q ≡ ¬(P ∨ Q) ¬∀x P ≡ ∃x ¬P ¬(P ∧ Q) ≡ ¬P ∨ ¬Q ∀x P ≡ ¬∃x ¬P P ∧ Q ≡ ¬(¬P ∨ ¬Q) ∃x P ≡ ¬∀x ¬P P ∨ Q ≡ ¬(¬P ∧ ¬Q) Các ký hiệu khác: • Ký hiệu bằng (=) Ký hiệu bằng trong câu thể hiện hai ký hiệu hằng khác nhau chỉ cùng một đối tượng. Ví dụ: Father(John) = Henry • Lượng từ tồn tại duy nhất (∃!): dùng để chỉ đây là đối tượng duy nhất thoả điều kiện này. Ví dụ: ∃! x King(x) Ký hiệu này có thể được thay thế bởi toán tử duy nhất i. Vídụ nói: Con mèo duy nhất của Henry chết. Được viết: Dead(i x CatOf(x, Henry)) tương tự với: ∃! x CatOf(x, Henry) ∧ ∀s CatOf(s, Henry) ⇒ Dead(s) 2.3.4. Những ký hiệu đặt biệt trong tập hợp, danh sách và số học Các ký hiệu sau đây sử dụng tương tự ký hiệu Prolog: ∅ = Tập rỗng {x} = Liền sau(x, Tập rỗng) {x,y} = Liền sau(x, Liền sau(y, Tập rỗng)) {x,y|s} = Liền sau(x, Liền sau(y,s)) r ∪ s = Hợp(r,s) Nghiên cứu planning để giải bài toán xác định lộ trình 66 r ∩ s = Giao(r,s) x ∈ s = Thành viên(x,s) r ⊆ s = Tập con(r,s) [] = Danh sách rỗng [x] = Liên tiếp (x, Danh sách rỗng) [x,y] = Liên tiếp(x, Liên tiếp(y, Danh sách rỗng)) [x,y|l] = Liên tiếp(x, Liên tiếp(y,l)) 2.3.5. Phép tính tình huống Phép tính tình huống là tên để chỉ một phương pháp cụ thể mô tả sự thay đổi trong logic trật tự đầu tiên. Nó quan niệm rằng, môi trường bao gồm một chuỗi ngữ cảnh, mỗi ngữ cảnh là một ảnh chụp nhanh của trạng thái môi trường. Các ngữ cảnh được tạo ra từ những ngữ cảnh trước bởi các hành động. Mỗi quan hệ hay thuộc tính có thể thay đổi theo thời gian được quản lí bởi tham số ngữ cảnh thêm vào tương ứng với vị từ. Ta quy ước tham số ngữ cảnh phải ở cuối cùng và hằng ngữ cảnh có dạng Si. Ví dụ: thay vì nói At(Agent, location). Ta nói. At(Agent, [1,1], S0) ∧ At(Agent, [1,2], S1) để mô tả agent ở hai ngữ cảnh liên tiếp. Đối với các quan hệ và thuộc tính không thay đổi theo thời gian không cần tham số ngữ cảnh. Ví dụ: cột đèn giao trong trên đường ở vị trí cố định ta chỉ cần nói: TrafficLight([2,2]). Bên cạnh đó ta có thể mô tả ngữ cảnh là kết quả của những hành động từ ngữ cảnh trước. Sử dụng hàm Result(action, situation). Ví dụ: Result(Forward, S0) = S1 Nghiên cứu planning để giải bài toán xác định lộ trình 67 Result(Turn(Right), S1) = S2 Result(Forward, S2) = S3 Nghiên cứu planning để giải bài toán xác định lộ trình 68 CHƯƠNG 4: CÁC VẤN ĐỀ TRONG LẬP KẾ HOẠCH 1. Giới thiệu agent lập kế hoạch đơn giản 2. Từ giải quyết bài toán đến lập kế hoạch 3. Lập kế hoạch trong phép tính tình huống 4. Ngôn ngữ STRIPS: Ngôn ngữ trình bày cơ bản trong lập kế hoạch 5. Giải pháp Nghiên cứu planning để giải bài toán xác định lộ trình 69 CHƯƠNG 4: CÁC VẤN ĐỀ TRONG LẬP KẾ HOẠCH 1 GIỚI THIỆU AGENT LẬP KẾ HOẠCH ĐƠN GIẢN Khi trạng thái môi trường là tiếp cận được, agent có thể sử dụng các tri thức do môi trường cung cấp để xây dựng một mô hình chính xác và hoàn chỉnh về trạng thái môi trường hiện hành. Với mục tiêu đã đưa ra, agent sẽ gọi một thuật toán lập kế hoạch thích hợp để tạo ra kế hoạch hành động. Sau đó agent thực thi các bước của kế hoạch, mỗi hành động thực hiện ở một thời điểm. Chương trình của agent lập kế hoạch đơn giản như sau: Thuật toán Một agent lập kế hoạch đơn giản. Agent trước tiên tạo ra một mục tiêu, sau đó xây dựng một kế hoạch để đạt được mục tiêu đó từ trạng thái hiện hành. Khi đã có kế hoạch, agent tiếp tục thực hiện kế hoạch cho tới khi kế hoạch hoàn tất, sau đó lại bắt đầu với mục tiêu mới. function AGENT LẬP KẾ HOẠCH ĐƠN GIẢN (tri thức) returns hành động static: KB, cơ sở tri thức(bao gồm sự mô tả hành động) p, kế hoạch, khởi tạo là NoPlan t, số đếm, khởi tạo là 0, chỉ thời gian local variables: G, mục tiêu trạng thái hiện hành: mô tả trạng thái hiện hành CẬP NHẬT TRI THỨC(KB, MÔ TẢ TRI THỨC(tri thức,t)) trạng thái hiện hành – MÔ TẢ TRẠNG THÁI(KB,t) if p = NoPlan then G – LÂY MỤC TIÊU(KB, MỤC TIÊU YÊU CẦU(t)) p – BỘ LẬP KẾ HOẠCH(trạng thái hiện hành, G, KB) if p = NoPlan or p rỗng then hành động - NoOp else hành động – FIRST(p) p – REST(p) CẬP NHẬT TRI THỨC(KB, MÔ TẢ HÀNH ĐỘNG(hành động,t)) t – t +1 return hành động Nghiên cứu planning để giải bài toán xác định lộ trình 70 Thuật toán lập kế hoạch trong hàm BỘ LẬP KẾ HOẠCH sẽ được mô tả sau. Hàm MÔ TẢ TRẠNG THÁI có đầu vào là tri thức và trả về sự mô tả trạng thái ban đầu theo dạng mà bộ lập kế hoạch yêu cầu, và hàm MỤC TIÊU YÊU CẦU, hàm này được dùng để hỏi cơ sở tri thức xem mục tiêu kế tiếp là gì. Agent phải xét trường hợp mục tiêu bất khả thi, với trường hợp này agent phải bỏ qua mục tiêu này và tìm những mục tiêu khác, và trường hợp kế hoạch rỗng. Agent tương tác với môi trường rất hạn chế – agent sử dụng tri thức của mình để định nghĩa trạng thái ban đầu và mục tiêu ban đầu, sau đó agent thực hiện theo các bước trong kế hoạch đã được xây dựng. 2 TỪ GIẢI QUYẾT BÀI TOÁN ĐẾN LẬP KẾ HOẠCH Lập kế hoạch và giải quyết bài toán là những hướng tiếp cận khác nhau để giải quyết vấn đề. Cả hai khác nhau về cách biểu diễn mục tiêu, trạng thái, hành động và khác biệt trong việc trình bày và xây dựng những chuỗi hành động. Phần này, đề cập đến những vấn đề khó khăn do cách tiếp cận giải quyết bài toán dựa trên tìm kiếm và đưa những phương pháp được các hệ thống lập kế hoạch sử dụng để giải quyết những khó khăn này. Các thành phần cơ bản của bộ giải quyết bài toán dựa trên tìm kiếm: • Trình bày hành động: Các hành động được mô tả bởi những chương trình tạo ra sự mô tả trạng thái kế thừa. • Trình bày trạng thái: Trong giải quyết bài toán, sự mô tả hoàn chỉnh trạng thái ban đầu được cho sẵn và các hành động được trình bày bởi những chương trình tạo ra sự mô tả trạng thái hoàn chỉnh. Vì vậy, tất cả những sự trình bày trạng thái đều hoàn chỉnh. Sự Nghiên cứu planning để giải bài toán xác định lộ trình 71 trình bày trạng thái chỉ được dùng để phát sinh kế thừa, lượng giá hàm heuristic và kiểm tra mục tiêu. • Trình bày mục tiêu: mục tiêu của agent giải quyết bài toán có dạng của hàm kiểm tra mục tiêu và hàm heuristic. • Trình bày kế hoạch: trong giải quyết bài toán, giải pháp là một chuỗi các hành động, như “Đi từ Arad đến Sibiu đến Fagaras đến Bucharest.” Trong suốt quá trình xây dựng giải pháp, thuật toán tìm kiếm chỉ quan tâm đến các chuỗi hành động liên tục bắt đầu từ trạng thái ban đầu. Ví dụ: “Lấy một lít sữa, một nải chuối và một cái máy khoan không dây đa tốc.”. • Trạng thái ban đầu: agent ở nhà nhưng không có thứ nào trong các thứ yêu cầu • Tập các toán tử: tất cả những gì mà agent có thể làm. Chúng ta có thể bổ sung thêm một hàm heuristic để lựa chọn các trạng thái. Nghiên cứu planning để giải bài toán xác định lộ trình 72 Hình 4.1 biểu diễn một phần rất nhỏ hai bước đầu tiên trong không gian tìm kiếm của bài toán này và chỉ ra con đường để đi tới đích. Hệ số rẽ nhánh trên thực tế có thể là hàng ngàn hay hàng triệu, phụ thuộc vào cách xác định hành động và chiều dài của giải pháp có thể là hàng tá bước. Có quá nhiều hành động, quá nhiều trạng thái phải xem xét. Nhưng hàm lượng giá heuristic chỉ có thể chọn một số trạng thái để quyết định cái nào gần mục tiêu nhất; nó không thể bỏ bớt các hành động cần xem xét. Thậm chí nếu hàm lượng giá chọn: agent đi siêu thị, agent phải dự đoán những hành động tiếp theo. Agent sẽ dự đoán bằng cách xem xét các hành động – mua cam, mua cá ngừ, mua ngũ cốc, mua sữa – và hàm lượng giá sẽ sắp xếp các dự đoán này – bad, bad, bad, good. Như vậy, agent biết rằng mua sữa là công việc tốt, nhưng không biết được bước kế Bắt đầu Hoàn tất … Đến cửa hàng vật Nói chuyện với két Đến trường Đến siêu thị Đi ngủ Đọc sách Ngồi ghế v. v. … … Mua con chó Đọc sách Ăn cơm Mua sữa Mua ngũ cốc Mua cá ngừ Vào lớp Hình 4.1. Giải quyết bài toán shopping bằng cách tìm kiếm tiến qua không gian ngữ cảnh trong môi trường. Nghiên cứu planning để giải bài toán xác định lộ trình 73 tiếp sẽ phải làm gì, nên phải bắt đầu lại từ đầu quá trình dự đoán trên để quyết định bước kế tiếp. Thực chất là agent giải quyết bài toán chỉ quan tâm đến chuỗi hành động bắt đầu từ trạng thái ban đầu cùng với những khó khăn của nó. Điều này buộc agent phải quyết định cái gì cần làm trước tiên ở trạng thái ban đầu, ở đây, với sự lựa chọn hợp lí, có thể đi đến bất cứ nơi nào trong các nơi còn lại. Cho đến khi agent biết được bằng cách nào để có được các đồ dùng khác nhau( bằng cách mua, mượn, thuê, trồng, sản xuất, trộm cắp) thì nó thực sự không thể quyết định được phải đi đâu. Do đó agent cần phương pháp xây dựng tri thức của nó tinh xảo hơn, để có thể làm việc với bất kì phần nào của bài toán có thể giải được với các thông tin hiện có. Ý tưởng then chốt đầu tiên đằng sau lập kế hoạch là “cởi trói” cách biểu diễn trạng thái, mục tiêu và hành động. Các thuật toán lập kế hoạch được mô tả bằng một ngôn ngữ hình thức, thường là logic trật tự đầu tiên hay ly thuyết tập con . Trạng thái và mục tiêu được biểu diễn bằng tập các câu, còn hành động được biểu diễn bằng các mệnh đề logic điều kiện cho trước và hệ quả. Điều này cho phép bộ lập kế hoạch xác định được những liên kết trực tiếp giữa trạng thái và hành động. Ví dụ, nếu agent biết rằng mục tiêu là một phép liên kết chứa Have(Milk), mà Buy(x) thu được Have(x), thì agent biết rằng nó nên xét đến đến một kế hoạch có chứa Buy(Milk). Nó không cần quan tâm đến những hành động không phù hợp như Buy(WhippingCream) hay GoToSleep. Ý tưởng then chốt thứ hai của lập kế hoạch là bộ lập kế hoạch tự do thêm hành động vào kế hoạch ở bất kỳ chỗ nào mà nó cần, chứ không ph