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