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

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