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

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:143

Thêm vào BST

Báo xấu

169
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầ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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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 1
Nghiên cứu planning để giải bài toán xác định lộ trình 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. 2
Nghiên cứu planning để giải bài toán xác định lộ trình 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 3
Nghiên cứu planning để giải bài toán xác định lộ trình NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... 4
Nghiên cứu planning để giải bài toán xác định lộ trình NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... 5
Nghiên cứu planning để giải bài toán xác định lộ trình 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 6
Nghiên cứu planning để giải bài toán xác định lộ trình 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 7
Nghiên cứu planning để giải bài toán xác định lộ trình 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 8
Nghiên cứu planning để giải bài toán xác định lộ trình 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 9
Nghiên cứu planning để giải bài toán xác định lộ trình 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 10
Nghiên cứu planning để giải bài toán xác định lộ trình 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 11
Nghiên cứu planning để giải bài toán xác định lộ trình 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. 12
Nghiên cứu planning để giải bài toán xác định lộ trình 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ế 13
Nghiên cứu planning để giải bài toán xác định lộ trình 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. 14
Nghiên cứu planning để giải bài toán xác định lộ trình CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN 1. Các thuật ngữ c hung 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ế 15
Nghiên cứu planning để giải bài toán xác định lộ trình 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 16
Nghiên cứu planning để giải bài toán xác định lộ trình 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ụ t h ể . 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 … 17
Nghiên cứu planning để giải bài toán xác định lộ trình 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ơ q uan 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 18
Nghiên cứu planning để giải bài toán xác định lộ trình 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 19