Đọc truyện dap an

♥ Truyen2U.Pro - Tên miền mới của Truyen2U.Net

dap an

Trước Sau

Màu nền

Font chữ

Font size

Chiều cao dòng

Câu 1: (Mrs. Lình)

Anh (chị) hiểu trí tuệ nhân tạo là gì?

- Theo M.Minsky "trí tuệ nhân tạo mô phỏng bằng máy tính về hành vi thông minh của con người". Tuy nhiên định nghĩa này mới cho thấy một mặt của trí tuệ nhân tạo.

- Để định nghĩa rõ thêm về trí tuệ nhân tạo người ta đưa trên hai quan điểm đã được chấp nhận khi nhìn nhận về vai trò phuc vụ của máy tính cho ngành trí tuệ nhân tạo.

1. Quan điểm của người nghiên cứu những cơ chế của trí tuệ nhân tạo cho rằng máy tính như phương tiện mô phỏng để thử một mô hình hay thử một định ly.

2. Quan điểm khác cho rằng máy tính có nhiểu khả năng chủ động. Do vậy cần cố gắng để sản xuất máy tính có khả năng thông minh con người, như các khả năng thu nhận tri thức, nhận dạng, suy luận hoặc ra quyết định.

Khi làm việc với trí tuệ nhân tạo, quan điểm thứ hai có khuynh hướng mô phỏng máy tính như thiết bị có hành động thông minh. Tuy vậy trong các ứng dụng cụ thể cũng chỉ dưng ở mức như quan điểm thứ nhất đã khẳng định.

Các định nghĩa về trí tuệ nhân tạo trong các tài liệu suất bản gần đây cho thấy nó thuộc hai hướng chính là: (i) xử ly các suy nghĩ và suy ly, (ii) liên quan đến hành vi. Theo mỗi hướng , người ta chia ra cách xác định theo hành động mang tính người hay theo những khái niệm mang tính tư tưởng của trí tuệ tức ‎y chí con người.

Các hệ thống suy nghĩ giống con người

- Theo tài liệu của Haugeland vào năm 1985 "kích thích cố gắng mới làm các máy tính suy nghĩ.. các máy có bộ óc theo y nghĩa đầy đủ.."

- Theo tài liệu của Bellman năm 1978 "tự động của các hoạt động liên quan đến suy nghĩ mang tính người, các hoạt động như ra quyết định, giải bài toán, học... Các hệ thống suy nghĩ theo y chí

- Theo tài liệu của Charmak và McDermott năm 1985 "nghiên cứu các phương tiện thần kinh thông qua việc thực hiện các mô hình tính toán"

- Theo tài liệu của winson vào năm 1992 "nghiên cứu để có thể nhận biết, tính toán, suy ly và hành động"

Các hệ thống hành động như con người

- Theo tài liệu của Kurzweil năm 1990 "Nghệ thuật sinh ra các máy thực hiện các chức năng đòi hỏi trí tuệ khi con người vận hành"

- Theo tài liệu của Rich và Kaight năm 1991 "nghiên cứu cách thức làm máy tính thực hiện công việc mà khi đó con người thực hiện tốt hơn" Các hệ thống hành động theo y chí

- Theo tài liệu của Schalkoff năm 1990 "lĩnh vực nghiên cứu để tìm ra cách giải thích và bắt chiếc hành vi thông minh bằng các quá trình tính toán"

- Theo tài liệu của Luger và Stubblefield năm 1993 "một ngành khoa học máy tính liên quan đến tự động hóa hành vi thông minh"

Câu 2: (Mrs. Lình)

Anh (chị) hãy mô tả kiến trúc tác nhân thông minh qua tương tác với môi trường, cho ví dụ minh họa họat động của agent dựa trên chuỗi nhận thức và hàm tác động.

- Tác nhân (agent) là cái hành động. Tác nhân máy tính khác với chương trình thông thường ở các thuộc tính như hoạt đông nhờ điều khiển tự động; nhận thức được môi trường quan nó ; bền vững theo thời gian dài; thích nghi với các thay đổi và có khả năng đưa ra mục đích mới. Tác nhân hợp lý là hành động để đạt được đầu ra tốt nhất hoặc có kỳ vọng tốt nhất khi không chắc chắn.

Với cách tiếp cận "các luật tư duy" trong AI chú trọng tới các suy luận đúng. Tuy vậy suy luận đúng có thể không phải là đòi hỏi bắt buôc của tính hợp lý. Nhiều khi không chứng minh được nhưng ta vẫn thực hiện: giật tay nhanh khi chạm vật nóng thay cho đưa từ từ sau khi xem xé thận trọng. Vì vây ta chú trọng tới hành động hợp lý.

Trong giáo trình này ta xem thông minh theo cách nhìn hành xử hợp lý, một tác nhân thông minh lý tưởng sẽ hành động tốt nhất với mỗi hoàn cảnh. Nghiên cứu AI như là thiết kế agent hợp lý. Các ưu điểm của cách tiếp cận hành đợng hợp lý::

• Tổng quát hơn cách tiếp cận "các luật tư duy" vì mục dích tư duy là đạt được hành động.

• Dễ phát triển một cách khoa học hơn cách bắt chướccon người.

- Tác nhân thông minh và môi trường.

Như đã nói ở trên, một hệ có thể hành xử hợp lý được coi là thông minh.

Một agent có thể xem là nhận thức môi trường (environment)của nó qua bộ cảm nhận (sensor) và tác động vào môi trường qua bộ tác động (actuator)

Con người có mắt, tai, mũi... là bộ cảm nhận. sensor và tay, chân... là bộ tác động; Rôbot dùng camera...Soft agent dùng nội dung file, dư thiết bị, modun nhận input... làm bộ cảm nhận màn hình file in và các gói tin ra là bộ tác động.

, Kiến trúc agent được minh họa trong hình 2.1.

Ta dùng thuật ngữ nhận thức (percept) để chỉ tín hiệu tri giác nhận được của agent. Mỗi chuỗi nhận thức của agent có tính lịch sử và ở mỗi thời điểm agent chọn tác động phụ thuộc vào chuỗi nhận nhức có được tới lúc đó. Dựa trên chuỗi nhận thức , agent chọn ứng xử được mô tả như là hàm agent (agent function) và có thể biểu diễn bởi bảng. Bảng là đặc trưng ngoài của hàm agent còn bên trong là một chương trình, cần phân biệt hàm agent(mô tả toàn học) và chương trính cài đặt.

- Ví dụ thế giới ( world )máy hút bụi: hình 2.2

Máy có hai vị trí trong các hình vuông A, B . Máy nhận thức bân hay sạch và có thể chuyển động sang phải hay trài và hút bụi hay không làm gì cả

Một hàm agent đơn giản được mô tả trong hình 2.3.

Vấn đề chọn hàm agent hợp lý , chương trình thích hợp mô tả trong hình dưới.

Câu 3. (Em Như làm giúp ^_^)

Anh (chị) hiểu thế nào là một agent hợp lý?

Định nghĩa agent hợp lý:

Đối với mỗi chuỗi nhận thức có thể, một agent hợp lý sẽ chọn tác động hướng tới cực đại độ đo thực hiện dựa vào biểu hiện của chuỗi nhận thức và các tri thức đã có.

Xét agent hút bụi và giả sử:

- Độ đo thực hiện: thưởng mỗi điểm cho mỗi ô sạch ở mỗi bước và có 100 bước.

- Phân phối bụi và vị trí ban đầu chưa biết.

- Chỉ có tác động sang phải, trái, hút và không làm gì

- Agent nhận thức đúng vị trí của nó và biết có bụi hay không.

Câu 4. (Em Như làm giúp ^_^)

Anh (chị) hiểu thế nào một agent có tính quán thông và tự trị?

Tính quán thông, học và tự trị

- Một agent quán thông là một agent biết được các kết cục về tác động của nó và cho được các tác động phù hợp. Tuy nhiên thì thực tế không có. Ví dụ người qua đường:

Do đó cần cực đại độ đo kỳ vọng chứ không phải là cực đại thực.

- Thường không đòi hỏi agent quan thông và tính hợp lý chỉ phụ thuộc vào nhận thức tới lúc đó và agent có thể không quyết định thông minh.

- Một agent hợp lý cần có tính khám phá và thu thập thông tin (học)

- Một agent dựa vào tri thức được người thiết kế cài đặt hơn nhận thức mới được coi là thiếu tính tự trị.

Câu 5: (Miss. Mai)

Anh (chị) cho biết taị sao cần đặc tả PEAS khi thiết kế agent? Các tính chất nào của agent cần quan tâm khi đặc tả PEAS?

* Khi thiết kế agent cần đặc tả PEAS vì khi xây dựng và phát triển bất kì phần mềm nào thì cũng cần xây dựng các đặc tả của nó để kiểm tra tính đúng đắn của chương trình. Và đặc tả Peas là 1 đặc tả khi thiết kế agent

* Các tính chất cần thiết của Agents khi thiết kế đặc tả là: Performance, Environment, Actuators, Sensors (PEAS)

- Performance: là một chức năng đảm bảo các biện pháp chất lượng của các hành động của các Agent đã đặc tả. Như: - An toàn, nhanh, Tối đa hóa lợi nhuận vv

- Environment: Môi trường mà Agent hoạt động.

- Actuators: là các thiết lập của thiết bị mà các Agent có thể sử dụng để thực hiện hành động. Đối với một máy tính, nó có thể được một máy in hoặc màn hình. Đối với một robot cơ khí, nó có thể là một động cơ.

- Sensors( Cảm biến) cho phép các Agent để thu thập các dãy thao tác sẽ được sử dụng, về hành động tiếp theo.

Câu 6: (Miss. Mai)

Anh (chị) hãy mô tả cấu trúc của một agent phản xạ đơn giản và đặc tả chương trình của nó.

- Agent phản xạ đơn giản: là các Agent cảm nhận được khả năng hiện thời chứ không quan tâm đến chuối cảm nhận trước đó. Giống như cái bộ chế hòa khí, hay cái bộ điều nhiệt đơn giản ấy: Khi nào nóng thì nó tự khắc cho hạ nhiệt, khi nào phù hợp nó lai tắt đi. Ví dụ như:

- Cấu trúc:

- Các đặc tả đầy đủ agent phản xạ đơn

Câu 7: (Mr. Mậu)

Anh (chị) hãy mô tả cấu trúc của một agent phản xạ dựa trên mô hình.và đặc tả chương trình của nó.

Mô tả một Agent phản xạ dựa trên mô hình.

Khi quan sát từng phần thì hiện thực cần kết hợp thông tin nhận thức hiện thời với quá khứ, mỗi agent có thể có một trạng thái trong và cập nhật tri thức.

Cập nhật trạng thái trong có thể từ hai loại tri thức.Thứ nhất có thể cần thông tin độc lập với agent. Thứ hai là thông tin về ảnh hưởng của tác động của agent tới môi trường.

Mô tả kiến trúc của agent dựa trên mô hình (hình 1) và chương trình tương ứng với nó. Khi xử lý thông tin ta cần cân nhắc có cài đặt trong mạch logic hay cần đến lý thuyết khoa học đầy đủ mà nó gọi là mô hình về thế giới thực. Agent sử dụng mô hinh gọi là agent dựa trên mô hình

Hình 1. Agent phản xạ dựa trên mô hình

Hình trên (hình 1) mô tả:

- Có một số quy tắc "tập luật" (quy tắc cơ bản) trong form của "điều kiện hành động"

- Có một thành phần để giải nén đặc tính

- Không có quyền truy cập để hoàn thành trạng thái của thế giới

- Chỉ có thể làm những công việc nếu quyết định đúng dựa trên nền tảng của "percept" hiện tại.

Chương trình tương ứng:

function SIMPLE-REFLEX-AGENT (percept) return action

static rule, a set of condition-action rules

state= INTERPRET-INPUT (percept)

rule= RULE-MACHE (state, rules)

action= RULE-ACTION [rule].action

return action

Câu 8: (Mr. Mậu)

Anh (chị) hãy mô tả cấu trúc và hoạt động của một agent dựa trên đích

Agent dựa trên đích.

Tri thức về trạng thái hiện thời chưa chắc đủ để quyết định hành vi. Ví dụ tại ngã tư, quyết định của Taxi tùy thuộc vào định đi đâu. Nói cách khác ngoài trạng thái hiện thời, cần có thêm thông tin đích.mô tả tình trạng mong muốn. Agent kết hợp thông tin này với thông tin về kết quả của tác động có thể. Tìm kiếm và lập kế hoạch là lĩnh vực dành cho tìm chuỗi hành động để đạt được đích của agent.

Mô tả cấu trúc dựa trên đích thông qua hình 2

Hình 2. Agent dựa trên đích

Hình 2 mô tả:

- Có thông tin về mục tiêu của họ "reflective agent" có thể sử dụng cho một mục tiêu cố định.

- Để thực hiện các agent, một thuật toán (algorithm - alg) tìm kiếm hoặc thuật toán lập kế hoạch là cần thiết

- Không thể có các quy tắc "condition - action"

- Nó có hiệu lực hơn "Reflective Agents"

Câu 9.

Anh (chị) hãy mô tả cấu trúc và hoạt động của một agent dựa trên lợi ích

Thuật ngữ để chỉ trạng thái được ưu tiên hơn trạng thái khác là nói nó có lợi ích cao hơn đối với agent. Hàm lợi ích ánh xạ một trạng thái vào một số thực dể mô tả mức độ phù hợp với thỏa mãn.

Câu 10.

Anh (chị) hãy mô tả cấu trúc và hoạt động của một agent học.

Agent học.

Cho đến nay ta đã mô tả các chương trìnhagent khác nhau để chọn hành động mà chưa giải thích làm thế nào để có các chương trình đó.Turing có đề xuất một phương pháp nhanh là xây dựng các máy học và dạy chúng..

Một agent học có thể chia làm 4 thành phần (hình 2.15)

Quan trọng nất là thành phần học chịu trách nhiệm cải tiến và thành phần thực hiện chịu trách nhiệm chọn tác động ngoài. Thành phần thực hiện có thể xem là agent đã xét trước,nó lấy nhận thưc và quyết định hành động. Thành phần học dùng thông tin liên hệ ngược từ bộ bình luận để xác định xem cần cải tiến thế nào để bộ thực hiện hanhd động tốt hơn về sau.Thiết kế thành phần học phụ thuộc nhiềuvào thiết kế thành phần thực hiện.Cơ cấu học có thể xây dựng để cải tiến mội thành phần của agent.

Thành phần tạo sinh bài toán, nó chịu trách nhiệm gợi ý các tác động và dẫn tới các thực nghiệm nhiều thông tin và mới .

Ví dụ lái taxi.

Câu 11: (Mr. Nam)

Anh (chị) hãy phân biệt agent dựa trên tri thức và agent giải bài toán tổng quát, cho ví dụ minh họa.

Trả lời:

- Tri thức của agent giải bài toán tổng quát quá chi tiết và không mềm dẻo.

- Các agent dựa trên tri thức có lợi thế là từ tri thức dưới dạng rất tổng quát nó có thể kết hợp và tái kết hợp thông tin cho nhiều mục đích khác nhau nhờ quá trình lập luận.

Tri thức và lập luận cũng đóng vai trò quan trọng khi làm việc với môi tường được quan sát từng phần. Một agent có thể kết hợp tri thức tổng quát với nhận thức hiện thời để suy ra cảnh quan ẩn và trạng thái hiện thời trước khi chọn tác động. Lập luận cũng cho phép hiểu ngôn ngữ tự nhiên và xử lý thông tin mờ

Vd: bài toán "Thế giới quái thú".

Một hang gồm các phòng nối với nhau bới các đường đi. Một quái thú ăn thịt ẩn đâu đó trong phòng. Agent có thể bắn quái thú nhưng chỉ có một mũi tên. Một số phòng có các hố không đáy bẫy người lạ rơi vào (trừ quái thú). Trong đó có chứa một đống vàng mà agent có thể tìm thấy..

PEAS được mô tả như sau:

+ Độ đo thực hiện: +1000 nếu lấy được vàng; -1000 nếu rơi vào hố hoặc bị ăn thịt; -1 cho mỗi hành động thực hiện và -10 nếu dùng đến tên.

+Môi trường: 4x4 phòng, Agent khởi đầu ở ô [1,1], vị trí của vàng và thú cho ngẫu nhiên. với xác suất đều ở các hình vuông khác. Mỗi hình vuông khác với ô khởi đầu có hố với xác suất 0,2.

+ Bộ tác động: agent có thể đi thẳng (nếu không có tường chắn) hoặc quay sang phải, trái 90 độ. Nó bị ăn thịt nếu đi vào chỗ có quái thú. Nhặt; bắn về phía trước. Mũi tên bay đến khi gặp thú (giết ) hoặc tường.

+ Bộ cảm nhận. Agent có 5 sensor cho biết thông tin:

- Nếu có quái thú ở ô kề thì nhận được mùi tanh.

- Nếu ô liền kề có hố thì có gió lạnh

- Ở ô có vàng thì thấy lấp lánh

- Khi đi tới tường thì có va chạm

- Khi Thú bị giết thì nó phát tiếng rống và nhận ra được ở mọi nơi.

Nhận thức là một bộ năm, ví dụ: (tanh, gió lạnh, không, không, không)

Hình 72 cho mọt khởi tạo KB về môi trường

KB khởi tạo chứa các luật về môi trường đã nêu trên, đặc biệt cho biết ô [[1,1] an toàn và agent đang ở đó.

Ta khảo sát sự phát triển nhận thức và hành động.

Nhân thức đầu tiên là (không, không, không, không, không). Từ đó agent kết luận cách ô liền kề an toàn (hình 7.3.a) do không có mùi tanh và gió lạnh tại ô đang đứng.

Một Agent cẩn thận chỉ tới các ô OK.

Giả sử nó tới ô [2,1 (hình 7.3 b) và nhận thức (không, gió lạnh, không, không, không) và biết có gió lạnh (B) vậy nên các ô liền kề có thể có hố (P), một Agent cẩn thận sẽ quay lại và tới [1,2].

Nhận thức mới là (tanh, không, không, không, không) (hình 7.4.a)

Mùi tanh cho biết có thú ở gần nhưng không phải [1,1] và [2,1] vầ Agent suy ra thú ở [1,3]; vì không có gió lạnh nên biết [2,2] không có hố và như vậy hố ở [3,1]. Kết luận này khó vì phải kết hợp tri thức ở các thời điểm khác nhau tại các vị trí khác nhau. Bây giờ agent có thể tới ô [2,2], nếu agent tới ô [2,3] và thấy lấp lánh, nhặt vàng rồi kết thúc 2

Câu 12: (Mr. Nam)

Anh (chị) hãy trình bày về chương trình agent dựa trên tri thức và cho ví dụ minh họa hoạt động của agent nhờ dùng chương trình

Trả lời:

Thành phần trung tâm của agent dựa trên tri thức (Knowledge-based) là cơ sở tri thức (knowledge base hay KB). Một cơ sở tri thức là một tập câu (sentence). Câu ở đây là thuật ngữ kỹ thuật, nó có liên quan nhưng không đồng nhất với câu trong ngôn ngữ tự nhiên. Mỗi câu được biểu diễn trong một ngôn ngữ biểu diễn tri thức (Knowledge representation language) tương ứng để biểu thị một khẳng định về thế giới. Để làm việc được, cần có phương tiện để đạt thêm tri thức mới và tri vấn tri thức đã có. Khả năng này ta gọi là khả năng biểu đạt (tell) và yêu cầu (ask), nó được thực hiện bởi cơ chế suy luận (inference) hay lập luận (resonning) của ngôn ngữ biểu diễn tri thức tương ứng để tạo ra câu mới từ các câu cũ.

Chi tiết của ngôn ngữ biểu diễn ẩn trong cài đặt tương tác giữa bộ cảm nhận và bộ tác động

Chương trình agent dựa trên tri thức được phác họa trong hình 7.1, giống với agent, nó lấy input là nhận thức và trả về một tác động. Agent thường xuyên có KB, có thể ban đầu được khởi tạo bởi tri thức nào đó. Tại mỗi thời điểm, agent làm 2 việc:

1- biểu đạt cho KB những cái nhận thức được;

2- hỏi KB hành động nào sẽ được thực hiện. (tell thứ hai là để nói cho KB hành động giả thuyết nào đang được thực hiện.

Make-Percept-sentence lấy một nhận thức và một thời điểm và trả ra một câu khẳng định rằng agent đã nhận biết nhận thức ở thời điểm đã cho. Make-Action-query lấy một thời điểm làm input và trả về yêu cầu cho biết hành động nào cần thực hiện tại thời điểm đó. Cơ cấu suy luận ẩn trong các hàm Tell và Ask.

Chương trình tri thức này khác với chương trình tính toán khác ở chỗ nó tuân theo mô tả ở mức tri thức trong đó ta chỉ cần cho agent biết cái gì là đích mà nó cần chỉnh sửa hành vi. Khác với tri thức mức cài đặt (yếu tố địa lý, điểm ảnh)

Câu 13: (Ms. Nguyệt)

Anh (chị) hiểu kỹ nghệ bản thể học là gì? Khó khắn chính trong đó là gì?

a.Kỹ nghệ bản thể học cho phép tổ chức và gắn kết các miền tri thức cụ thể với nhau

b. Khó khăn chính trong vấn đề này là

Khó khăn chính là hầu hết các tổng quát hóa đều có ngoại lệ.

Câu 14: (Ms. Nguyệt)

Trình bày về quan hệ giữa các lớp và các đối tượng trong bản thể học và cách dùng vị từ cấp một khi mô tả chúng.

a. Quan hệ giữa các lớp và các đối tượng trong bản thể học

 Trong thế giới thực thì ta làm việc với các đối thượng cụ thể , trong nhiều lập luận thường làm việc với các lớp. Chẳng hạn người mua hàng có thể mua một quả bóng rổ chứ không bắt buộc là một loại bóng rổ cụ thể nào đó.

 Khi suy luận đoán các đối tượng trong nhận thức nhận được thông tin

đặc tính đối tượng được lấy từ thông tin lớp của nó.

Ví dụ nếu nó màu xanh, da có sọc, kích thước lớn và hình quả trứng thì

suy luận nó là quả dưa hấu và có thể dùng làm salad.

b. cách dùng vị từ cấp một khi mô tả chúng

Có hai cách biểu diễn lớp trong FOL: Vị từ và đối tượng.

 Có thể dùng vị từ Basketball(b) hoặc cụ thể hóa (reify) nó như là đối

tượng Basketballs

 Quan hệ thành viên:

Câu 15: (Miss. Như)

Trình bày về các cách mô tả hợp thành vật lý. Giải thích ngữ nghĩa của các mô tả:

part of(Apple1,Apple)

BunchOf({Apple1; Apple2; Apple3})

Trả lời:

Hợp thành vật lý (physical composition)

Một đối tượng có thể là một phần của đối tượng khác. Quan hệ part of để chỉ một cái là một phần của cái khác. Các đối tượng nhóm theo quan hệ phân cấp này gợi nhớ phân cấp tập con.

Lớp các đối tượng hợp thành (composite objects) thường được đặc trưng bởi cấu trúc giữa các phần.

Ví dụ: Động vật hai chân có hai chân gắn vào thân:

Ta có thể định nghĩa quan hệ Partpartition tương tự quan hệ Partition. Một đối tượng hợp thành từ các phần trong Partpartition của nó và có thể lấy một số đặc tính từ các phần này. Ví dụ như khối lượng của vật là tổng của khối lượng thành phần (khác với lớp là lớp tự nó không có khối lượng).

part of(Apple1,Apple)

Ngữ nghĩa trên diễn tả rằng đối tượng Apple 1 là một phần của đối tượng Apple. Đối tượng Apple chỉ về một loại trái cây ăn được là Táo nói chung. Đối tượng Apple1 là một quả táo cụ thể, và chắc chắn là Apple1 có các đặc tính của một loài Táo như ăn được, có hình thù ra sao, mùi thơm như thế nào.

Bó (Bunch)

Một cách khác để định nghĩa đối tượng hợp thành qua các phần nhờ khái niệm mới là Bó (bunch)

Nếu muốn nói các quả táo (3 quả) trong túi nặng 1kg thì với khái niệm đã biết (tập hợp) ta không có trọng lượng. Ta dùng khái niệm cụm, giả sử các quả táo là Apple1, Apple 2, Apple3 thì:

BunchOf({Apple1; Apple2; Apple3})

Là đối tượng hợp thành có 3 quả táo như là các thành phần.

Khi đó BunchOf({x})=x

BunchOf({Apple}) là lớp hoặc tập mọi quả táo.

Các phép đo (measurement)

Mỗi đối tượng thường có đặc trưng số (chiều cao, cân nặng, giá). Giá trị của nó ta gọi là độ đo. Tùy theo đơn vị đo mà đối tượng có độ đo khác nhau.

Ví dụ: đoạn L1 có độ dài 4 cm, ta viết: Length(L1)=4cm.

Ta cho phương trình chuyển đổi đơn vị, giả sử sang inches:

Centimeters(2.54xd)=Inches(d).

Đo chất:

Ví dụ mức khó (của bài tập); mức hay (của bài hát). Có thể dùng quan hệ thứ tự để mô tả, chẳng hạn bài tập của Norvig khó hơn bài tập của Russel và bài tập dễ hơn thì có điểm thấp hơn được mô tả như sau:

Các quan hệ đơn điệu trong độ đo thuộc về vật lý lượng, nó nghiên cứu cách lập luận về các hệ vật lý mà không phải gắn liền với các phương trình và mô phỏng số.

Giải thích ngữ nghĩa:

part of(Apple1,Apple)

BunchOf({Apple1; Apple2; Apple3})

Là đối tượng hợp thành có 3 quả táo như là các thành phần.

Câu 16: (Miss. Như)

Trình bày về mô tả vật chất và đối tượng trong bản thể học (ontology)?

Vật chất (subsstances) và đối tượng

Đối tượng vật chất có thể phân thành đối tượng thành phần (primitive) và đối tượng hợp thành.

Các đối tượng như quả cam, oto ta dễ làm việc với số lượng lớn cá thể (induviduation).

Với các chất liệu (stuff) thì phức tạp hơn. Ta phân biệt chất liệu và vật.

Ví dụ đối tượng bơ ta phân biệt cách nói một oto với bơ (Tiếng Anh). Trong lớp bơ ta có đối tượng là cụ bơ Butter 1; Butter 2; Butter 3...

Chú ý: một phần của đối tượng cũng là đối tượng:

Và mô tả các loại đặc biệt của lớp này: UnsaltedButters (Bơ nhạt). Mặt khác lớp PoundOfButters bao gồm các cục bơ nặng 1 pound và lớp này không phải chất liệu.

Phân biệt các đặc tính thuộc bản chất (intrinsic) và ngoại diên (extrinsic). Các chất liệu được đặc tả bởi đặc tính bản chất.

Câu 17.

Giới thiệu khái niệm tình trạng và các mô tả

Khái niệm tình trạng:

(Giả thiết môi trường chỉ có 1 agent)

- Các tình trạng là các hạng thức logic bao gồm tình trạng khởi phát (S0) và các tình trạng tạo nên khi ứng dụng một tác động. Ký hiệu Result(a,s) là kết quả của tác đông a trong trạng thái s

- Ảnh hưởng (Fluents) là các hàm và vị từ biến đổi từ một trạng thái vào trạng thái tiếp theo, chẳng hạn vị trí của agent hoặc sự sống của quái thú. Quy ước tình trạng luôn là kết cục cuối cùng của một ảnh hưởng:

Ví dụ: -Holding(G1,S0), Age(wumpus, S0)

- Một agent tính toán tình trạng cần có khả năng diễn dịch kết quả của chuỗi tác động đã cho. Với thuật toán đã xây dựng, agent cần tìm được dãy tình trạng (hay tác động) đạt được kết quả mong muốn.

Mô tả:

Mô tả tác động trong phép tính tình trạng:

- Trong phép tính tình trạng, mỗi tác động thường được mô tả bởi 2 tiên đề: tiên đề khả năng và tiên đề hiệu quả. Chúng có dạng sau:

Possibility AXIOM: Preconditions => Poss(a,s)

Effect AXIOM: Poss (a,s)=> Changes that result from taking action.

(Poss(a,s): có thể thực hiện tác động a khi ở tình trạng s)

Câu 18.

Giới thiệu khái niệm kế hoạch trong phép tính tình trạng.

Câu 19: (Mr. Quyền)

Trình bày về cách mô tả tác động trong phép tính tình trạng.

Trong phép tính tình trạng, mỗi tác động thường được mô tả bởi hai tiên đề: tiên đề khả năng và tiên đề hiệu quả (effect). Chúng có dạng sau:

(Pos(a,s) nghĩa là có thể thực hiện tác động a khi ở tình trạng s.)

Ví dụ Cho thế giới quái thú, quy ước: o đối tượng, s tình trạng, a là tác động, g là vàng và x,y là vị trí. Bỏ qua ký hiệu lượng từ, trong thế giới các tiên đề có thể là agent đi tới ô kề nhặt vàng và bỏ vàng (khi cầm vàng).

Tiên đề tác động chỉ ra ảnh hưởng nếu thực hiện tác động có thể:

Tuy vậy ta chưa khảng định được kế hoạch sẽ đạt mục tiêu. Rước hết Go([1,1]),[1,2]) có thể thực hiện ở tình trạng S0 và hiệu quả là agent tới ô [1,2]:

Tuy vậy ta không biết rằng vàng có ở [1,2] hay không? Tiên đề hiệu quả cho biết thay đổi nhưng không nói rõ cái gì không đổi.

Biểu diễn những yếu tố không đổi thuộc bài toán khung (frame problem). Trong thế giới thực, mỗi tác động chỉ gây nên ảnh hưởng tới phần nhỏ còn đa số không đổi.

Một cách tiếp cận là viết rõ cái gì không đổi. Chẳng hạn chuyển động của agent giữ nguyên các đối tượng trừ khi chúng bị cầm:

Nếu có F vị từ ảnh hưởng và A tác động thì ta cần O(AF) tiên đề khung. Nếu mỗi tác động có E hiệu quả (E nhỏ hơn F) thì những cái cần biễu diễn có cỡ nhỏ hơn O(AE). Đây là bài toán khung biễu diễn (representational frame problem). Nó liên quan chặt chẽ với bài toán khung suy luận (Inferential frame problem)

Câu 20: (Mr. Quyền)

Trình bày cú pháp và ngữ nghĩa của tiên đề trạng thái kế tiếp.

Ta thay đổi một chút cách nhìn để viết tiên đề, thay vì viết các hiệu quả tác động thì ta xét các vị từ ảnh hưởng theo thời gian. Các tiên đề dạng trạng thái kế tiếp (succesor-state axioms) có dạng sau:

Chẳng hạn tiên đề trạng thái kế tiếp đối với vị trí agent ở y sau khi thực hiện một tác động là:

Tiên đề cầm vàng:

Số lượng loại tiên đề này là O(AE) literal vì mỗi trong E kết quả của mỗi trong E tác động chỉ dẫn ra đúng một lần. Các literal rải ra trên F tiên đề khác nhau về trung bình có khoảng AE/F. Có thể thấy các tiên đề này có At ảnh hưởng đối với agent nhưng không phải với vàng. Ta vẫn chưa chứng minh được kế hoạch 3 bước có vàng ở [1,1]. Ta hiểu một hệ quả ẩn là agent cầm vàng thì khi chuyển dịch vàng cũng chuyển dịch theo.

Làm việc với hệ quả ẩn gọi là bài toán phân nhánh.

Ta cần thêm tiên đề:

Câu 21:

Hai cách xử lý bài toán khung suy diễn

(Two way solving the inferential frame problem)

(Nguyễn Sơn dịch từ cuốn AI_A modern aproach + slide của thày, các vấn đề cốt lõi cần đưa ra khi trả lời vấn đáp được tô đậm màu đỏ)

Tiên đề trạng thái kế tiếp giải quyết bài toán khung biểu diễn (representational frame problem), nhưng không phải là bài toán khung suy diễn (inferential frame problem). Hãy xem xét một kế hoạch p t-bước mà St = Result(p, S0). Để quyết định ảnh hưởng nào đúng trong St, chúng ta cần phải xem xét từng tiên đề khung F trên mỗi bước thời gian t. Bởi vì các tiên đề có kích thước trung bình AE/F, điều này cho chúng ta O(AEt) công việc suy diễn. Hầu hết các công việc liên quan đến việc sao chép những ảnh hưởng không thay đổi từ một trạng thái tới trạng thái kế tiếp.

Để giải quyết bài toán khung suy luận, chúng ta có hai lựa chọn.

• Thứ nhất, chúng ta có thể loại bỏ tính toán tình trạng và phát minh ra một hình thức mới để viết các tiên đề. T đã được thực hiện với hình thức như tính toán thuần thục.

• Thứ hai, chúng ta có thể làm thay đổi cơ chế suy luận để xử lý các tiên đề khung hiệu quả hơn.

Một gợi ý rằng điều này nên có thể tiếp cận đơn giản là O(AEt); lý do tại sao nó phải phụ thuộc vào số lượng các hành động, A, khi chúng ta biết chính xác một hành động được thực hiện ở mỗi bước thời gian? Để xem làm thế nào để cải thiện vấn đề, trước tiên chúng ta quan sát định dạng của các tiên đề khung:

Đó là, mỗi tiên đề đề cập đến một vài hành động có thể làm cho ảnh hưởng chính xác và một số hành động có thể làm cho nó sai. Chúng ta có thể chính thức hóa điều này bằng cách giới thiệu bổ đề PosEffect(a, Fi), có nghĩa là hành động một nguyên nhân Fi trở thành sự thật, và NegEffect(a, Fi) có nghĩa là một nguyên nhân Fi trở nên sai. Sau đó chúng ta có thể viết lại các lược đồ tiền đề nói trên như là:

Cho dù điều này có thể được thực hiện tự động phụ thuộc vào định dạng chính xác của các tiên đề khung. Để thực hiện một thủ tục suy luận hiệu quả bằng cách sử dụng các tiên đề như thế, chúng ta cần làm 3 việc:

1. Đánh chỉ số các PosEffect và các bổ đề NegEffect bởi đối số đầu tiên của chúng để khi chúng ta được cho một hành động xảy ra tại thời gian t, chúng ta có thể tìm thấy ảnh hưởng của nó trong thời gian O(1).

2. Đánh chỉ số các tiên đề để mỗi khi bạn biết rằng Fi là một kết quả của một hành động, bạn có thể tìm thấy những tiên đề cho Fi trong khoảng thời gian O(1). Sau đó, bạn thậm chí không cần xem xét các tiên đề cho ảnh hưởng mà không phải là một kết quả của hành động.

3. Biểu diễn mỗi trạng thái như là một trạng thái trước đó cộng với một giá trị delta. Như vậy, nếu không có gì thay đổi từ một bước tới bước kế tiếp, chúng ta không cần phải làm gì. Trong tiếp cận cũ, chúng ta sẽ cần phải thực hiện O(F) việc để tạo một sự khẳng định cho từng Fi(Result(a, s)) từ những khẳng định Fi(s) trước.

Như vậy ở mỗi bước thời gian, chúng ta quan sát hành động hiện thời, lấy kết quả của nó, và cập nhật các thiết lập của các ảnh hưởng đúng (true fluents). Mỗi bước thời gian sẽ có trung bình E các cập nhật này, đối với một tổng O(Et). Điều này tạo thành một giải pháp cho bài toán khung suy diễn.

Câu 22:

Giới thiệu bài toán lập kế hoạch và các cách tiếp cận giải quyết

(Nguyễn Sơn dịch từ cuốn AI_A modern Aproach và kết hợp với slide của thày, các vấn đề cốt lõi cần đưa ra khi thi vấn đáp được tô màu đỏ)

1. Giới thiệu bài toán lập kế hoạch

Việc xây dựng một dãy các thao tác thực hiện các hành động để đạt được một mục tiêu được gọi là kế hoạch. Chúng ta đã thấy hai ví dụ về tác tử lập kế hoạch: tác tử giải quyết vấn đề dựa trên tìm kiếm và tác tử lập kế hoạch logic.

Cần phát triển một ngôn ngữ ràng buộc cho việc biểu diễn các bài toán lập kế hoạch, bao gồm các hành động và các trạng thái. Ngôn ngữ này có liên quan gần gũi với đề xuất về cách thức mà các thuật toán tìm kiếm tiến và tìm kiếm lùi có thể tận dụng lợi thế của biểu diễn này, chủ yếu thông qua các heuristic chính xác mà có thể được dẫn xuất tự động từ cấu trúc của biểu diễn.

Để đưa đến các tiếp cận giải bài toán lập kế hoạch, chúng ta chỉ quan tâm tới các môi trường được quan sát đầy đủ, xác định, hữu hạn, tĩnh (thay đổi chỉ xảy ra khi các tác tử đưa ra hành động), và rời rạc (về mặt thời gian, hành động, các đối tượng, và các hiệu ứng). Chúng được gọi là các môi trường lập kế hoạch truyền thống. Ngoài ra, lập kế hoạch không truyền thống chỉ dành riêng cho các môi trường có thể quan sát được theo từng bộ phận hoặc ngẫu nhiên, liên quan đến tập khác nhau của các thuật toán và thiết kế tác tử.

2. Các cách tiếp cận giải quyết bài toán lập kế hoạch

Các agent giải bài toán (Problem solving agent) có thể tìm lời giải tốt hơn theo các tiếp cận sau:

a. Để tránh duyệt các tác động không phù hợp, một agent nhạy cảm có thể mô tả mục đích hiện tại và tạo sinh tác động trực tiếp.

Ví dụ. Sách đựơc mã 10 chữ số ISBN và cần mua cuốn ISBN 0137903952, agent có thể mô tả mục đích là: Have(ISBN 0137903952) Và tạo tác động trực tiếp By((ISBN 0137903952)

b. Các hàm heuristics có thể xác định nhờ các heuristic độc lập miền khi mục đích có thể mô tả như là hội của các mục đích "con" (Subgoal).

c. Phân rã bài toán. Chia bài toán lớn thành bài toán con (ví dụ tìm chu trình haminton với cụm).

Để minh họa cho các tiếp cận trên, chúng ta hãy quan tâm đến những điều có thể xảy ra như mô tả dưới đây khi một tác tử giải quyết vấn đề thông thường sử dụng các thuật toán tìm kiếm theo chiều sâu chuẩn như thuật toán A*, vân vân, giải quyết các bài toán rộng lớn của thế giới thực. Điều này sẽ giúp chúng ta thiết kế các tác tử lập kế hoạch tốt hơn.

Cách tiếp cận a

Khó khăn rõ ràng nhất là việc tác tử giải quyết vấn đề có thể bị tràn ngập bởi những tác động không phù hợp. Xem xét các tác vụ mua một bản sao của cuốn sách "AI- A modern approach" từ một nhà sách trực tuyến. Giả sử có một hành động mua cho mỗi mã ISBN 10 chữ số, sẽ dẫn đến tổng cộng 10 tỷ hành động. Các thuật toán tìm kiếm đã có thể kiểm tra trạng thái kết quả của tất cả 10 tỷ hành động để tìm ra một trong số đó thỏa mãn các mục tiêu là để sở hữu một bản sao có mã số ISBN bằng 0137903952. Một tác tử kế hoạch hợp lý sẽ phải xuất phát từ một mô tả mục tiêu rõ ràng như có (ISBN0137903952) và tạo ra hành động Buy (ISBN 0137903952) một cách trực tiếp. Để làm điều này, tác tử đơn giản chỉ cần các tri thức thông thường như Buy(x) và Have(x). Đưa ra tri thức này và mục tiêu, người lập kế hoạch có thể xác định duy nhất hành động Buy (ISBN0137903952) là hành động đúng.

Cách tiếp cận b

Khó khăn tiếp theo là tìm một hàm heuristic tốt. Giả sử mục tiêu của tác tử là mua 4 cuốn sách trực tuyến khác nhau. Sau đó sẽ có 1040 kế hoạch chỉ cho bốn bước này, đây là hậu quả của việc tìm kiếm mà không có một ước tính heuristic chính xác cho chi phí của một trạng thái là số cuốn sách còn lại phải mua (tức là, sau khi mua một cuốn sách, thì phải loại bỏ bớt số lượng trạng thái trước khi lập kế hoạch mua cuốn sách tiếp theo); tiếc là, cái nhìn sâu sắc về điều này là không rõ ràng cho một tác tử giải quyết vấn đề, bởi vì nó thấy mục tiêu kiểm tra chỉ như là một hộp đen trả về đúng hoặc sai cho mỗi trạng thái. Vì vậy, tác tử giải quyết vấn đề thiếu tự chủ; nó đòi hỏi phải có một con người hỗ trợ để cung cấp cho nó một hàm heuristic cho từng vấn đề mới. Mặt khác, nếu một tác tử lập kế hoạch đã truy cập vào một biểu diễn rõ ràng của mục tiêu như là một liên kết của các mục tiêu phụ, sau đó nó có thể sử dụng một heuristic độc lập miền duy nhất: số liên kết không thỏa mãn. Đối với vấn đề mua sách, mục tiêu sẽ là Have(A) ^ Have(B) ^ Have(C) ^ Have(D), và một trạng thái có chứa Have(A) ^ Have(C) sẽ có chi phí 2. Như vậy, tác tử tự động chọn heuristic đúng cho vấn đề này, và cho các vấn đề khác. Chúng ta sẽ xem sau này trong chương nói về cách làm thế nào để xây dựng các heuristics tinh vi hơn cho phép kiểm tra các hành động có sẵn cũng như cấu trúc của mục tiêu.

Cách tiếp cận c

Cuối cùng, người giải quyết vấn đề có thể là không hiệu quả vì nó không thể tận dụng lợi thế của việc phân rã một vấn đề. Hãy xem xét những vấn đề của việc cung cấp một bộ các gói lữ hành qua đêm tới các điểm du lịch tương ứng, nằm rải rác trên khắp nước Úc. Sẽ là khôn ngoan khi tìm ra sân bay gần nhất cho mỗi điểm đến và phân chia các vấn đề tổng thể vào một số bài toán con, mỗi bài toán cho từng sân bay. Trong bộ gói đã được định tuyến qua một sân bay nào đó, cho dù việc phân rã sâu hơn có thể phụ thuộc vào các thành phố đích. Ảnh hưởng tương tự cũng đúng cho các nhà hoạch định: trong trường hợp xấu nhất, có thể mất 0 (n!) thời gian để tìm phương án tốt nhất để cung cấp các gói n, nhưng chỉ có O((n/k)!*k thời gian nếu vấn đề có thể được phân hủy thành k phần bằng nhau.

Việc thiết kế nhiều hệ thống lập kế hoạch--- đặc biệt là các nhà hoạch định thứ tự bộ phận dựa trên giả định rằng hầu hết các vấn đề thực tế là "gần phân rã". Tức là, nhà hoạch định có thể làm việc trên các mục tiêu phụ một cách độc lập, nhưng có thể cần phải làm thêm một số công việc để kết hợp các kế hoạch phụ lại. Đối với một số vấn đề, giả thiết này bị hư vì làm việc trên một mục tiêu phụ thì gần như là "undo" lại các mục tiêu phụ khác. Các tương tác giữa các mục tiêu phụ này là những gì làm cho các "vấn đề nan giải" (như các câu đố-8) trở nên nan giải hơn.

Thảo luận vừa rồi đề xuất rằng việc biểu diễn lại của các bài toán lập kế hoạch--- các trạng thái, hành động và mục tiêu--- cần phải làm cho các thuật toán lập kế hoạch có thể tận dụng được lợi thế về mặt cấu trúc logic của vấn đề. Chìa khóa ở đây là tìm ra một ngôn ngữ đủ ý nghĩa biểu cảm để mô tả một dải rộng của các vấn đề, nhưng lại có giới hạn vừa đủ để cho phép các thuật toán hoạt động hiệu quả trên nó. Một trong các ngôn ngữ tái biểu diễn của các nhà hoạch định cổ điển là ngôn ngữ STRIPS (được trình bày ở các câu hỏi 23 và 24).

Câu 23.

Giới thiệu cách biễu diễn trạng thái và đích bởi STRIPS

Biểu diễn trạng thái:

Các thành phần lập kế hoạch phân rã thế giới thành các điều kiện logic và biểu diễn một trạng thái như là hội của các literal dương

VD:

Các literal bậc 1 mô tả trạng thái phải cụ thể và không chứa hàm.

Biểu diễn đích:

Trạng thái đích được biểu diễn dưới dạng hội của các literal dương cụ thể.

Một trạng thái mệnh đề s thỏa mãn đích g nếu nó chứa mọi phần tử trong g.

Câu 24.

Giới thiệu cách biễu diễn tác động bởi STRIPS.

Cú pháp:

Một tác động được đặc tả bởi tiền điều kiện trước khi thực hiện và hiệu quả khi thực hiện tác động. Chẳng hạn, một tác động bay của máy bay từ vị trí này sang vị trí khác là:

Người ta dùng lược đồ tác động (action schema) để biểu diễn chính xác một số tác động từ biến p, from, to tới các hằng khác.

Tổng quát, một lược đồ tác động gồm ba phần:

• Một tên tác động và danh sách tham số để định danh tác động.

Ví dụ: Fly(p,from,to)

• Tiền điều kiện (precondition) là hội các literal dương không có hàm nói rõ những gì phải có trong trạng thái trước khi tác động. Các biến trong tiền điều kiện phải xuất hiện trong danh sách tham số của tác động.

• Hiệu quả (effect) là hội của các literal không có hàm mô tả trạng thái thay đổi ra sao khi tác động được thực hiện.

Một literal dương P trong hiệu quả được khẳng định là đúng trong trạng thái có được từ tác động còn literal ¬P được khẳng định là sai.

Các biến trong hiệu quả cũng phải xuất hiện trong danh sách tham số của tác động.

Để dễ đọc, một số hệ lập kế hoạch chia hiệu quả thành danh sách thêm (add list) cho các literal dương và danh sách loại (delete list) cho các literal âm.

Ngữ nghĩa.

Có thể trực tiếp là mô tả tác động ảnh hưởng tới trạng thái ra sao.( một trong đó là đặc tả một bản dịch trực tiếp thành các tiên đề trạng thái kế tiếp., ngữ nghĩa của nó thừa hưởng từ logic bậc một).

+Ta nói rằng một tác động là ứng dụng được trong các trạng thái thỏa mãn tiền điều kiện.

+Đối với lược đồ tác động bậc một, việc thiết lập tính ứng dụng được bao hàm việc thay thế θ cho các biến trong tiền điều kiện.

Câu 25: (Mr. Thái)

Giới thiệu các cách lập kế hoạch nhờ tìm kiếm trong không gian trạng thái.

Tìm kiếm tiến trong không gian trạng thái:

Lập kế hoạch nhờ tìm kiếm tiến tương tự với cách giải bài toán tổng quát (chương 3 của Russel): Ta khởi đầu từ trạng thái ban đầu của bài toán, khảo sát các dãy tác động cho tới khi tìm được một trạng thái đích.

Mô tả hình thức:

• Trạng thái ban đầu của tìm kiếm là trạng thái ban đầu của bài toán lập kế hoạch. Mỗi trạng thái là tập các literal cụ thể dương (trang thái không xuất hiện là sai)

• Với mỗi trạng thái, tác động ứng dụng được là những tác động mà tiền điều kiện của nó được thỏa mãn. Trạng thái kế tiếp sinh ra từ một tác động nhờ thêm vào các literal hiệu quả dương (trong trường hợp này ta phải hợp nhất tiền điều kiện với hiệu quả) và loại bỏ các literal hiệu quả âm. Cần nhớ rằng các hàm kế tiếp làm việc với mọi bài toán lập kế hoạch.

• Kiểm tra đích: Kiểm tra trạng thái có thỏa mãn đích của bài toán lập kế hoach không.

Chi phí bước của mỗi tác động thường là 1 (mặc dù có thể có chi phi khác nhưng ít gặp trong STRIPS)

Chú ý:

+ Do không có hàm nên không gian trạng thái là hữu hạn.

+Với các thuật toán tìm kiếm đầy đủ thì luôn tìm được lời giải.

Tuy vậy cách tiếp cận này thường không hiệu quả do không gian trạng thái quá lớn và khó tìm định hướng heuristic.

Ví dụ (bài toán vận tải)

Có 50 máy bay có thể bay tới 9 sân bay khác, có 200 kiện có thể chất vào hoặc lấy ra ở các máy bay tại sân bay của nó. Về trung bình có thể có 1000 tác động có thể và cây tìm kiếm theo độ sâu gồm 100041đỉnh

Tìm kiếm lùi trong không gian trạng thái

Khó cài đặt khi trạng thái đích được mô tả bởi tập ràng buộc mà không phải là danh sách hiện.

Không phải khi nào cũng có thể mô tả các tiền trạng (predecessors) cho các trạng thái đích (Ở biểu diễn STRIPS các khó khăn này được khắc phục).

Ưu điểm : của phương pháp quay lui là cho phép ta chỉ xét các tác động phù hợp (relevance). Tác động phù hợp với đích hội, là tác động thoả mãn một literral trong hội của đích.

Ví dụ: dích trong bài toán vận tải với 10 sân bay là 20 kiện hàng ở B. Chính xác hơn là At(C1, B) ^ At(C2, B) ^....^ At(C20, B)

Ta xets At(C1, B) Chỉ có một hành động có hiệu quả này : Unload (C1, p, B) trong đó p chưa đặc tả

Chú ý:

Nhiều hành động không phù hợp cũng dẫn tới trạng thái đích.

Ví dụ: có thể bay với máy bay rỗng từ JFK tới SFO; hành động này đạt được trạng thái đích từ các trạng thái trước trong đó máy bay ở tại JFK và các thành phần hội thỏa mãn. Một thuật toán tìm kiếm lùi cho phép tác động không phù hợp vẫn đầy đủ nhưng kém hiệu quả hơn.

Hạn chế các tác động phù hợp thì các nhánh tìm kiếm của quay lui ít hơn tìm kiếm tiến nhiều.

( bài toán vận tải có 1000 tác động trong tìm kiếm tiến thì tìm kiếm lùi chỉ cần 20 tác động từ đích)

Câu 26: (Mr. Thái)

So sánh các cách lập nhờ tìm kiếm tiến và lùi trong không gian trạng thái.

So sách hai phương pháp.

Hai phương pháp đều là tìm kiếm trong không gian trạng thái.

Đều gặp trở ngại, là khi không gian trạng thái lớn thì không hiệu quả.

Tuy nhiên với tìm kiếm tiến, ta phải đi hết các trường hợp cụ thể để tìm trạng thái đích. Còn trạng thái đích có thể chỉ lựa chọn một số các trạng thái thích hợp.

Về mặt hoạt động: Khác nhau rõ ràng giữa hai phương pháp. Tìm kiếm tiến, tiếp cận từ trạng thái ban đầu đi đến trạng thái đích. Tìm kiếm lùi, theo hướng ngược lại.

Về mặt cài đặt: Tìm kiếm tiến cài đặt dễ dàng, bởi trạng thái ban đầu được xác định trước. Tìm kiếm lùi khó cài khi trạng thái đích được mô tả bởi tập ràng buộc mà không phải là danh sách hiện. Không phải lúc nào cg có thể mô tả các tiền trạng thái cho các trạng thái đích.

Câu 27: (Miss. Thịnh)

Giới thiệu các heuristic mà anh (chị ) biết có thể dùng khi lập kế hoạch nhờ tìm kiếm trong không gian trạng thái

Thuần túy tìm kiếm tiến hoặc lùi mà không có heuristic đều kém khiệu quả .

Heuristic có thể là ước lượng số tác động cần thiêt.

Hai cách tiếp cận có thể sử dụng.

• Dùng bài toán lỏng (relax Problem) dễ giải để có heuristic chấp nhận được.

• Chia để trị nhờ giả thiết mục đích con độc lập (Subgoal Independence assumption ). Phân biệt lạc quan và bi quan .

Câu 28: (Miss. Thịnh)

Mô tả POP cho bài toán lập kế hoạch mệnh đề

Viêc xác định bao gồm trạng thái ban đầu, các tác động và kiểm tra đích.

• Kế hoạch khởi tạo chứa Start và Finish với ràng buộc thứ tự Start

• Hàm kế tiếp (successor function) lấy một điều kiện mở ở một tác động p và tạo ra một kế hoạch kế tiếp cho mỗi cách chọn tác động A thích hợp để đạt được p.

Tính thích hợp được thực hiện như sau:

1. Causal link và ràng buộc thứ tự A

2. Ta cần giải quyết các mâu thuẫn giữa causal link của tác động A (nếu là mới) với các causal link hiện hữu và các causal link với A. Một mâu thuẫn dạng với C được giải quyết nhờ cho C xảy ra ở thời điểm ngoài khoảng bảo vệ hay thêm ràng buộc thứ tự B

Câu 29: (Ms. Trà)

giải thích thuật toán POP bằng ví dụ:

Ví dụ .Ta xét bài toán thay lốp xe mô tả trong hình 11.7

Việc tìm kiếm lời giải bắt đầu bởi kế hoạch khởi tạo chứa một tác động Start với hiệu ứng At(Spare, Trunk) Λ At(Flat, Axle) và tác động Finish với tiền điều kiện At(Spare, Axle). Để tạo hậu duệ (kế hoạch kế tiếp) ta chọn một điều kiện mở và chọn trong số các tác động có thể để đạt được tiền điều kiện này (lúc này ta chưa quan tâm đến heuristic). Chuỗi sự kiện tiếp theo như sau:

1. Chọn chỉ điều kiện mở At(Spare, Axle) của Finish. Và chọn tác động ứng dụng được PutOn(Spare, Axle)

2. Chọn tiền điều kiện At(Spare, Ground) của PutOn(Spare, Axle) và chọn remove(Spare, Trunk) để đạt được nó. Kế hoạch đạt được trong hình 11.8

3. Lấy tiền điều kiện ¬At(Flat, Axle) của PutOn(Spare, Axle). Nếu chọn LeaveOvernight mà không chọn Remove(Flat, Axle) cũng có hiệu quả ¬At(Flat, Axle) nhưng nó cũng có hiệu quả ¬At(Spare, Ground) mâu thuẫn với causal link: Remove(Spare, Trunk) PutOn(Spare,Axle). Để giải quyết mâu thuẫn, để LeaveOvernight trước remove(Spare, Trunk). Kế hoạch đạt được trong hình 11.9

4. Chỉ còn một tiền điều kiện mở là At(Spare, Trunk) của tác động Remove(Spare,Trunk). Chỉ có tác động Start đạt được điều này, nhưng causal link từ Start đến Remove(Spare, Trunk)mâu thuẫn với hiệu quả ¬At(Spare, Trunk) của LeaveOvernight. Lần này không có cách nào giải quyết mâu thuẫn với LeaveOvernight: không thể đặt trước Start hoặc sau Remove(Spare, Trunk). Như vậy phải quay lại trạng thái trong hình 11.8. (Có thể chứng minh rằng tác động LeaveOvernight không có ích gì cho bài toán???).

5. Trở lại xét tiền điều kiện ¬At(Flat, Axle) của PutOn(Spare, Axle) và chọn Remove(Flat, Axle).

6. Lại chọn At(Spare, Trunk) của Remove(Flat,Axle) và chọn Start để đạt được nó, lần này không mâu thuẫn.

7. Chọn tiền điều kiện At(Flat, Axle) của Remove(Flat, Axle) và chọn Start để đạt được nó. Ta được kế hoạch đầy đủ như hình 11.10.

Câu 30: (Ms. Trà)

Giải thích các khái niệm điều kiện mở và causal link? Cho biết các heuristic có thể dùng khi lập kế hoạch thứ tự bộ phận.

Trả lời:

Cho biết các heuristic có thể dùng khi lập kế hoạch thứ tự bộ phận.

- POP không biễu diễn trạng thái một cách trực tiếp nên khó ước lượng được bao lâu nữa thì tới đích .

- Vì vậy hiểu biết về tìm heuristics còn ít so với lập kế hoạch sắp thẳng.

- Heuristic dễ thấy nhất là đếm số điều kiện mở. Có thể cải tiến nhờ trừ số điều kiện mở cho các literal khớp trong trạng thái khởi đầu.

- Giống trường hợp sắp thẳng, sẽ đánh giá quá cao chi phí khi có tác động đạt được mục đích bội và đánh giá thấp khi có tương tác âm giữa các bước kế hoạch.

- Hàm heuristics dùng để chọn kế hoach thác triển .

- Thuật toán tạo sinh kế hoạch kế tiếp nhờ chọn điều kiện mở đơn giản nhất để làm việc.

Heuristic biến buộc chặt nhất có thể dùng cho việc lập kế hoạchch và tỏ ra dùng khá tốt.

Ý tưởng là chọn điều kiện mở có ít cách thỏa mãn nhất.

Có hai trường hợp của heuristic này

- Điều kiện mở không thể đạt được bởi bất cứ tác động nào (tìm cái không thể)

- Điều kiện mở chỉ đạt được bằng một tác động

- (tránh tính toán số cách thỏa mãn điều kiện vì chi phí lớn)

Câu 33: (Mr. Tuyên)

Trình bày thuật toán GRAPLAN

Thuật toán GRAPHPLAN (hình 11.13) chỉ ra cách trích một kế hoạch từ đồ thị lập kế hoạch gồm 2 bước chính, luân phiên trong một vòng lặp.

1- Kiểm tra liệu các literal đích có ở mức hiện thời không và có liên kết mutex giữa cặp nào không. Nếu tốt thì lời giải có thể tồn tại ở đồ thị đang có và thuật toán sẽ thử trích lời giải đó.

2-Ngược lại, nó mở rộng đồ thị nhờ thêm vào các tác động đối với mức hiện thời và các literal trạng thái của mức sau. Quá trình tiếp tục cho tới khi tìm được một lời giải hoặc biết được lời giải không tồn tại.

Xét thuật toán cho bài toán thay lốp xe (đồ thị đầy đủ trong hình 11.14).

Dòng đầu (cột 1) của thuật toán khởi tạo đồ thị lập kế hoạch ở mức 1 (S0) bao gồm 5 literal ở trạng thái ban đầu. Literal đích At(Spare, Axle) không có trong S0 nên không cần gọi EXTRACT_SOLUTION vì ta chắc chưa có lời giải.

EXPAND-GRAPH thêm 3 tác động mà tiền điều kiện của nó có ở mức S0 (tức là mọi tác động, trừ PutOn(Spare, Axle) và các tác động giữ nguyên các literal ở mức S0.

Hiệu quả của tác động được thêm ở mức S1.

EXPAND-GRAPH xét các quan hệ mutex và thêm chúng vào đồ thị

At(Spare, Axle) không có trong S1 nên ta không gọi EXTRCT-SOLUTION.

Tiếp tục gọi EXPAND-GRAPH cho đồ thị lập kế hoạch trong hình 11.14.

Một số ví dụ về các mutex và nguyên nhân của chúng

- Các hiệu quả không phù hợp: Remove(Spare, Trunk) là mutex với LeaveOvernight bởi vì nó có hiệu quả At(Spare, Ground) và cái còn lại phủ định nó

- Can thiệp nhau: Remove(Flat, Axle) là mutex với LeaveOvernight vì một có tiền điều kiện At (Flat, Axle) và cái kia có hệ quả phủ định nó.

- Cần cạnh tranh: PutOn(Spare, Axle) là mutex với Remove(Flat, Axle) vì một tác động có At(Flat, Axle) là tiền điều kiện và cái kia phủ định nó.

- Hỗ trợ không tương thích: At(Spare, Axle) là mutex với At(Flat, Axle) trong S2 vì chỉ có một cách đạt được At(Spare, Axle) là bởi PutOn(Spare, Axle) nhưng nó là mutex với tác động giữ nguyên là cách duy nhất để có At(Flat, Axle). Như vậy các quan hệ mutex khám phá ngay các mâu thuẫn khi đặt hai đối tượng trong cùng một chỗ tại cùng một lúc.

Trở lại đầu vòng lặp, mọi literal đích đã có trong S2 và không có mutex giữa chúng.

Lời giải có thể có và EXTRACT-SOLUTION sẽ thử tìm nó.

EXTRACT-SOLUTION giải một bài toán CSP mà các biến của nó là các tác động ở mỗi mức và giá trị cho mỗi biến ở trong hoặc ngoài kế hoạch.

Ta có thể dùng thuật toán CSP chuẩn để giải nó hoặc xác định Extract-Solution như một bài toán tìm kiếm trong đó mỗi trạng thái trong tìm kiếm chứa một con trỏ tới một mức trong đồ thị kế hoạch và một tập đích không thoả mãn.

Bài toán tìm kiếm này như sau:

- Trạng thái đầu là mức cuối cùng Sn của đồ thị lập kế hoạch với tập đích của bài toán.

- Các tác động có ở trong trạng thái ở mức Si là để chọn tập con các tác động không mâu thuẫn trong Ai-1 mà hiệu quả của nó chứa đích trong trạng thái. Trạng thái dẫn đến có mức Si-1 và có tập đích của nó là tiền điều kiện cho các tác động được chọn. Do việc không mâu thuẫn nên tập tác động như vậy không có cặp nào có quan hệ mutex và cũng không có tiền điều kiện nào là mutex.

- Đích là đạt tới một trạng thái ở mức So ssao cho mọi literal đích đều thoả mãn

- Chi phí cho mỗi tác động là 1.

Với bài toán cụ thể này ta bắt đầu từ S2 với đích At (Spare, Axle).

Chỉ có một tác động để chọn đạt được mục đích là PutOn(Spare, Axle).

Tác động dẫn tới một trạng thái tìm kiếm ở S1 với đích At(Spare, Ground) và ¬At(Flat, Axle).

Literal đầu chỉ có thể đạt được nhờ Remove(Spare, Trunk) còn cái sau là Remove(Flat, Axle) hoặc LeaveOvernight.

Vì LeaveOvernight là mutex với Remove(Spare, Trunk) nên chỉ có lời giải được chọn: Remove(Spare, Trunk) và Remove(Flat, Axle).

Bây giờ dẫn tới một trạng thái tìm kiếm ở trạng thái So với đích At(Spare, Trunk) và At (Flat, Axle). Cả hai đã có trong trạng thái này. Ta có lời giải: các tác động Remove(Spare, Trunk) và Remove(Flat, Axle) ở mức A0 tiếp theo PutOn(Spare, Axle) trong A1 .

Độ phức tạp

Việc xây dựng đồ thị lập kế hoạch có thời gian đa thức nhưng lập kế hoạch là PSPACE-đầy đủ nên việc trích lời giải là không quyết định được trong tình huống xấu nhất.

Vì vậy cần một số hướng dẫn heuristic để chọn các tác động trong tìm kiếm quay lui.

Môt tiếp cận tốt trong thực hành là thuật toán tham lam dựa trên chi phí mức của các literal. Với mọi tập đích, ta xử lý theo thứ tự sau:

1.Trước tiên lấy literal có chi phí mức cao nhất

2. Để đạt được literal đó, chọn tác động với tiền điều kiện dễ nhất trước, tức là chọn tác động mà tổng chi phí mức của các tiền điều kiện nhỏ nhất.

Kết thúc của GRAPHPLAN

Nếu bài toán không có lời giải, ta có thể chắc chắn rằng GRAPHPLAN sẽ dừng sau hữu hạn bước.

Kết luận dựa trên các tính chất (không chứng minh).

- Các literal tăng đơn điệu (do có tác động giữ nguyên)

- Các tác động tăng đơn điệu

- Các mutex giảm đơn điệu

Câu 35: (Ms. Vân PT)

Trình bày thuật toán SATPLAN

Thuật toán:

Function SATPLAN (problem, Tmax) returns solution or failure

Inputs: problem, a planning problem

Tmax, an upper limit for plan length

For T = 0 to Tmax do

Cnf, mapping  TRANSLATE - TO - SAT (problem, T)

Assignment  SAT - SOLVER (cnf)

if assignment is not null then

return EXTRACT - SOLUTION (assignment, mapping)

return failure

Giải thích:

1 Thuật toán sử dụng 2 tham số là: problem và Tmax, kết quả trả về là giải pháp để giải quyết problem hoặc sai

2 Đầu vào của thuật toán: problem, một vấn đề quy hoạch

o Tmax, một giới hạn trên của kế hoạch

3 Hàm TRANSLATE - TO - SAT (problem, T): tại bước T chuyển vấn đề thành một câu logic

4 SAT - SOLVER (cnf): Đưa ra hướng giải quyết cho câu lôgic

5 EXTRACT - SOLUTION (assignment, mapping): chiết xuất hướng giải quyết đúng từ mô hình thỏa mãn câu logic

Ý nghĩa thuật toán:

1 Bước 1: tại mỗi thời điểm T ta chuyển vấn đề thành một câu logic

2 Bước 2: đưa ra hướng giải quyết cho câu logic và gán nó cho biến Assignment

3 Nếu Assignment tồn tại sẽ trích một phần Assignment trong các giải pháp cho câu logic và tiếp tục lặp lại từ bước 1

4 Bước 3: Nếu Assignment không tồn tại câu logic sẽ không thoả được

Câu 36: (Ms. Vân PT)

Phát biểu bài toán lập lịch công việc, cho ví dụ mô tả bài toán

Phát biểu bài toán: Có tập công việc {J1 .......Jn}. Mỗi công việc Jk cần thực hiện m tác động a1k, ...., amk với mỗi tác động cần một khoảng thời gian và tài nguyên nhất định (aik = 0 thì không có quy tác này

Ví dụ: Bài toán JSS, có hai công việc: lắp ráp ô tô C1 và C2. Mỗi công việc gồm 3 tác động: lắp máy, lắp bánh xe và kiểm tra kết quả

Thuật toán:

Giải thích:

Chassis (C1), Chassis (C2): là ô tô 1 và ô tô 2

Engine (E1, C1, 30): Quá trình lắp máy E1 vào ô to C1 và mất 30 phút để lắp giáp

Duration(d): một hành động cần một khoảng thời gian d để thực hiện

Inspect(c): Quá trình kiểm tra ô tô c

Wheels(w,c,d): Quá trình lắp bánh xe w vào ô tô c mất khoảng thời gian là d

Thời gian chùng (Slack). Đại lượng LS - ES gọi là thời gian chùng của tác động

Giải thích thuật toán:

Hành động 1: Lắp máy vào ô tô C AddEngine (e,C)

 Những vấn đề: Máy e là của ô tô c và lắp máy e vào ô tô C mất khoảng thời gian là d, có thể máy e không phải của ô tô c

 Kết quả: lắp được máy e vào ô tô c và quá trình lắp mất khoảng thời gian d

Hành động 2: Lắp bánh xe w vào ô tô C

 Những vấn đề: Bánh w là của ô tô c và lắp bánh w vào ô tô C mất khoảng thời gian là d

 Kết quả: lắp được bánh vào ô tô c và quá trình lắp mất khoảng thời gian là d

Hành động 3: Kiểm tra ô tô c.

 Những vấn đề: Máy và bánh xe đa được lắp đúng

 Kết quả: kiểm tra xong xe C mất khoảng thời gian là 10

Máy phải lắp trước còn kiểm tra là khâu cuối cùng.

Hình sau đây chỉ ra một lời giải của bộ lập kế hoạch từng phần (POP-Partial Order Planner)

Để xây dựng lịch (không phải là kế hoạch ), ta cần xác định khi nào mỗi tác động có thể bắt đầu và kết thúc.

Ta cần chú ý tới khoảng thời gian thực hiện và thứ tự các tác động.

Hình 3

Giải thích hình 3:

• B1: Bắt đầu: mất 15' để xác định xem máy nào là của xe C1 sau đó mất 30' để lắp máy cho C1

• B2: Lúc này ta đã biết máy còn lại là của C2: vì thế tiến hành đồng thời 2 hành động là lắp máy cho C2 và lắp bánh cho C1 (lắp bánh cho C1 mất 30')

• B3: kiểm tra xe C1 (mất 10'), đồng thời lắp bánh cho C2 (mất 15')

• B4: Xe C1 đã lắp xong, kiểm tra xe 2 mất 10'

Kết quả: quá trình lắp máy và lắp bánh cho 2 ô tô là diễn ra đồng thời nên toàn bộ kế hoạch kéo dài 85'

Câu 37: (Mr. Việt)

Câu hỏi 37- 38 liên quan đến bài toán lập lịch câu 36. Cần phải hiểu bài toán trước đã.

Bài toán: "Có tập công việc {J1,J2,.....Jn}. Mỗi công việc Jk cần thực hiện m tác động a1k,a2k,...,amk (ở đây ta có thể hiểu mỗi tác động là một phần việc task) với mỗi tác động cần một khoảng thời gian tài nguyên nhất định. Hãy lập kế hoạch thực hiện tập n công việc trên".

Để lập kế hoạch dùng phương pháp đường găng(Critical Path Method), trước tiên ta phải xây dựng đồ thị kế hoạch:

Một ví dụ đơn giản trong bài giảng của thầy Huấn. Có hai công việc lắp ráp ô tô C1 và C2. Mỗi việc gồm 3 tác động: lắp máy(AddEngine), lắp bánh xe(AddWheels), kiểm tra kết quả(Inspect). Đồ thị kế hoạch như sau:

Trong đồ thị trên ta phải hiểu như sau:

Trong công việc C1:

• Lắp máy(AddEngine1) xong hoàn toàn thì mới lắp bánh xe(AddWheels1), rồi mới thực hiện kiểm tra kết quả(Inspect1).

• Những mối quan hệ trên được thể hiện bằng mũi tên trong đồ thị. Ta nói tác động AddWheels1 chịu ảnh hưởng của tác động AddEngine1 vì phải làm xong AddEngine1 mới có thể bắt đầu làm AddWheels1. Và khi bắt đầu thực hiện tác động AddWheels1 ta chỉ quan tâm đến tác động AddEngine1 đã hoàn thành chưa mà thôi, không phải quan tâm đến những tác động (phần việc) khác còn lại.

Tương tự như vậy là công việc C2

Ta có bảng mối quan hệ của các tác động(phần việc) như sau:

Tác động(phần việc)

(Activity) Phụ thuộc

(Dependent)

(Preceding Activity) Thời gian thực hiện(giờ)

(Duration)

AddEngine1 ------ 30

AddWheels1 AddEngine1 30

Inspect1 AddWheels1 10

AddEngine2 ------ 60

AddWheels2 AddEngine2 15

Inspect2 AddWheels2 10

Finish khi hoàn thành xong Inspect1 và Inspect2

Có thể mô tả lại đồ thị trên theo một các khác tương đương như sau:

Trong đồ thị này mỗi cung là một tác động(phần việc) có kèm theo trọng số thời gian thực hiện, mỗi đỉnh là trạng thái, tại đó ta đã làm xong phần việc ta có thể nghỉ ngơi một chút hoặc làm tiếp phần việc tiếp theo.

Đường găng trong đồ thị kế hoạch hình 12.2 là đường đi từ start đến finish có tổng trọng số của các đỉnh (trừ đỉnh Start và finish) là lớn nhất

Đường găng trong đồ thị kế hoạch mới là đường đi từ start đến finish có tổng trọng số của các cạnh lớn nhất

Bản chất tìm đường găng là tìm đường đi dài nhất.

Đặc điểm của đường găng:

• "Tổng trọng số của đường găng là thời gian ngắn nhất để hoàn thành các công việc". Để hoàn thành công việc với thời gian trọng số của đường găng. Thì các phần việc trên đường găng phải thực liên tục, đồng thời trên các đường khác không phải đường găng ta chỉ có thể tạm giải lao giữa các phần việc một số thời gian cho phép

• Đường găng là đường mà thời gian toàn phần dài nhất, rút ngắn hoặc kéo dài nó ảnh hưởng tới toàn bộ kế hoạch. (Ta lấy một ví dụ phức tạp hơn ví dụ trong bài ta sẽ hiểu rõ hơn đặc điểm này).

Trong bài tập ví dụ trên đường găng là đường StartAddEngine2AddWheels2 Inspect2finish. Tổng thời gian thực hiện là 60+15+10=85 (giờ). Còn đường StartAddEngine1AddWheels1Inspect1finish, có tổng thời gian thực hiện các phần việc là 30+30+10=70 (giờ). Để hoàn thành công việc với thời gian trọng số của đường găng thì ta chỉ có 85-70 =15 giờ nghi giải lao giữa các phần việc.

Chuý ý:

 Hai phương pháp biểu diễn đồ thị kế hoạch ở trên hiện nay đều đang được áp dụng để tìm các đường găng

 Tuy nhiên cách thứ hai chưa toát lên được việc lập một kế hoạch cụ thể cho thực hiện công việc. Chẳng hạn ở cách thứ nhất nhìn vào đồ thị ta thu được kết quả sau:

• Tại thời điểm t [0,0]  t=0 ta phải bắt đầu thực hiện phần việc AddEngine2

• Tại thời điểm t [60,60]  t=60 ta phải bắt đầu thực hiện phần việc AddWheels2

• ......

• Trong thời điểm t [0,15] ta phải bắt đầu thực hiện phần việc AddEngine1

• Trong thời điểm t [30,45], đồng thời lúc đó AddEngine1 đã hoàn thành, ta phải bắt đầu thực hiện phần việc AddWheels1

• .......

• Điều đáng nói nữa là: đoạn [0,15] của tác động AddEngine1 có nghĩa là thời điểm bắt đấu sớm nhất ES (Early Start) và thời điểm bắt đầu muộn nhất LS (Late Start) để thực hiện tác động AddEngine1.

• Vậy ES(AddEngine1)=0 còn LS(AddEngine1)=15

• Tương ứng sẽ có thời điểm kết thúc sớm nhất (Early Finish)và thời điểm kết thúc muộn nhất(Late Finish) của tác động AddEngine1 là EF=0+30=30, LF=15+30=45.

Ta có các công thức:

ES(AddEngine1)+Duration(AddEngine1) = ES(AddWheels1)

LS(AddEngine1)+Duration(AddEngine1) = LS(AddWheels1)

.......v.v....

Phương pháp đường găng để lập kế hoạch

 Mô tả bảng mối quan hệ của các tác động(phần việc)

 Lập độ thị kế hoạch (ta nên dùng đồ thị cách một ở trên)

 Tìm các đường găng, Thực chất là tính [ES, LS] tại mỗi đỉnh theo thuật toán như sau:

o Tính ES cả tất cả các tác động

 Khởi đầu gán ES(Start)=0.

 ES của tác động B được tính khi mọi ES của tác động trước nó đã được gán

 ES của tác động B bằng giá trị cực đại của các thời điểm kết thúc sớm nhất các tác động trước B.

 Thời điểm kết thúc sớm nhất của tác động là thời điểm bắt đầu sớm nhất cộng với thời gian thực hiện tác động.

Vậy ES(B)=Max{ES(A) + Duration(A) | A là tác động trước của B}

 Lặp lại quá trình này đến khi mọi giá trị của mọi tác động đã được gán.

o Tính LS cả tất cả các tác động

Tương tự như ES, giá trị FS được tính lui từ Finish

LS(finish)=ES(finish)

LS(B)=Min{LS(C)-Duration(B) | C là tác động sau của B }

 Từ ES, và LS của mỗi tác động ta sẽ đưa ra được một kế hoạch thực hiện công việc

Câu 38: (Mr. Việt)

minh hoạ phương pháp đường găng để lập kế hoạch:

Giả sử có hai công việc CV1 và CV2

Với CV1 gồm các tác động (phần việc): A, C,G, H, I, J, M

CV2 gồm các tác động (phần việc): B, D, E, F, K, L, N

Bảng mô tả bảng mối quan hệ của các tác động(phần việc) như sau:

Activity Preceding Activity Duration

A ------ 10

B ------ 14

C A 11

D B 5

E B 15

F B 20

G C, D 8

H C, D 12

I G 16

J H, E 10

K H, E 21

L H, E 6

M I, J 9

N L, F 12

Finish khi hoàn thành xong K, M, N

Xây dựng đồ thị kế hoạch trong phương pháp biểu diễn đồ thị.

Tìm đường găng theo thuật toán:

Cả hai đồ thị đều cho đường găng là ACGIM và ACHK

Nhưng cách thư hai có thể trích ra được một kế hoạch thực thi hệ hai công việc CV1 và CV2> còn cách thứ nhất chưa làm được như vậy.

Câu 39 - 40: (Mr. Vũ)

Mô tả bài toán lập lịch với ràng buộc tài nguyên và cách xử lý

Lập lịch với ràng buộc tài nguyên.

Bài toán lập lịch thực phức tạp vì thường có ràng buộc về tài nguyên.

Nếu khi lắp máy xe cần một cần trục máy và chỉ có 1 cần trục thì không thể lắp hai máy đồng thời.

Tài nguyên dùng lại được (reusable resource):

là tài nguyên bị chiếm giữ trong thời gian tác động nh ưng lại dùng cho tác động khác được khi tác động kết thúc.(ví dụ cần trục máy)

Chú ý: Tài nguyên dùng lại được không thể điều khiển được trong mô tả chuẩn của tiền điều kiện và hiệu quả. Vì vậy, ta thêm vào biểu diễn một trường dạng RESOURCE:

R(k) có nghĩa rằng tác động đòi hỏi k đơn vị tài nguyên R.

Tài nguyên đòi hỏi phải có sẵn và hiệu quả lâm thời (temporary) theo nghĩa rằng ngay khi tác động bắt đầu thì tài nguyên này giảm đi k đơn vị trong khoảng thời gian thực hiện tác động.

Hình 12.3 chỉ ra việc mở rộng bài toán lắp máy như thế nào với ba tài nguyên: một cần cẩu máy để lắp máy, một sân để lắp bánh và hai bộ kiểm tra.

Hình 12.4 chỉ ra một lời giải với thời gian ho àn thành nhanh nhất là 115 phút.

Lâu hơn lập lịch không ràng buộc tài nguyên (85 phút).

Kĩ thuật tích hợp (aggregation).

Nhóm các đối tượng lại theo lượng để giảm được độ phức tạp của thuật toán khi các đối tượng này không khác nhau về mục đích sử dụng. Theo đó ta viết Inspector(2) hơn là viết Inspector(1) và Inspector(2).

Ví dụ. Một lịch có 10 tác động Inspect cạnh tranh nhưng chỉ có 9 Inspector có sẵn . Với cách tích hợp lượng thì biết ngay lịch không chấp nhận được và cần tìm lịch khác trong khi biểu diễn theo các cá thể thì phair10! cách gán Inspector cho các tác động Inspect.

Bài toán lập lịch với tài ngyên hạn chế là NP khó. Nhiều cách giải đã được thử: nhánh cận, luyện kim,GA, ACO,...

Một cách heuristic đơn giản là cực tiểu thời gian chùng theo kiểu tham lam. Tại mỗi phép lặp, với các tác động chưa lập lịch với các tác động trước nó đã thực hiện, chọn tác động có thời gian chùng nhỏ nhất cho bắt đầu thực hiện rồi cập nhật ES và LS cho mỗi tác động bị ảnh hưởng. Cách này nói chung không cho lời giải tối ưu,.

Cách tiếp cận là : lập kế hoach trước, lập lịch sau.

Phần giải được chia làm hai pha.

Pha thứ nhất là lập kế hoạch, các tác động được chọn và sắp thứ tự bộ phận để đáp ứng đích.

Pha thứ hai là pha lập lịch, các thông tin lâm thời (temporal information) được xét để đảm bảo về tài nguyên và thời gian.

Câu 41: (Ms. Yến)

Cho ví dụ minh họa phân biệt bài toán lập lịch công việc có và không có ràng bupộc tài nguyên và cách sử dụng phương pháp đường găng.

1. Ví dụ 41.1: Bài toán lập lịch công việc không có ràng buộc tài nguyên

Ví dụ bài toán JSS (Job Shop Scheduling):

Có hai công việc: lắp ráp ô tô C1 và C2. Mỗi việc gồm 3 động tác: lắp máy, lắp bánh xe và kiểm tra kết quả.

2. Ví dụ 41.2: Bài toán lập lịch công việc có ràng buộc tài nguyên

Trong ví dụ 41.1, thêm điều kiện: nếu khi lắp máy xe cần một cần trục máy và chỉ có 1 cần trục thì không thể lắp hai máy đồng thời.

Bài toán trở thành Lập lịch công việc có ràng buộc tài nguyên

3. Cách sử dụng đường găng:

a. Các khái niệm cơ bản

 Khái niệm khoảng - Duratuion(d) trong hiệu quả của một tác động l à số chỉ thời gian (phút) thực hiện tác động .

Phương pháp đường găng-CPM (tới hạn - critical path method) Với thứ tự và thời gian tác động trong hình 12.2 ta có thể dùng phương pháp đường găng (CPM ) để xác định thời điểm khởi đầu và kết thúc của mỗi tác động.

 Đường đi qua một kế hoạch thứ tự bộ phận là dãy sắp thẳng các tác động bắt đầu bằng Start và kết thúc bởi Finish.

 Đường găng là đường mà thời gian toàn phần dài nhất rút ngắn hoặc kéo dài nó ảnh hưởng tới toàn bộ kế hoạch. (Trong hình vẽ đường găng được vẽ với mũi tên đậm)

Để hoàn thành kế hoạch với thời gian ngắn nhất, các tác động thuộc đ ường găng phải thực hiện ngay khi có thể mà không được trì hoãn.

Mỗi cửa sổ có cụ thể hóa thời điểm sơm nhất ES và muộn nhất FS có thể bắt đầu tác động tương ứng.

 Thời gian chùng (Slack). Đại lượng LS - ESgọi là thời gian chùng của tác động.

b. Cách sử dụng đường găng

 Khởi đầu gán ES(Start)=0.

 ES của tác động B được tính khi mọi ES của tác động trước nó đã được gán ES của tác động B bằng giá trị cực đại của các thời điểm kết thúc sớm nhất các tác động trước B.

 Thời điểm kết thúc sớm nhất của tác động là thời điểm khởi tạo sớm nhất cộng với thời gian thực hiện tác động.

 Lặp lại quá trình này đến khi mọi giá trị của mọi tác động đã được gán.

 Giá trị FS được tính lui tương tự từ Finish của tác động.

 Độ phức tạp của thuật toán đường găng là O(Nb), trong đó N là số tác động là số yếu tố nhánh cực đại tới hoặc ra khỏi tác động..

 Sử dụng phương pháp đường găng vào bài toán lập lịch

Câu 42: (Ms. Yến)

Trình bày phương pháp lập kế hoạch dựa trên mạng tác vụ phân cấp (HTN)

Lập kế hoạch nhờ mạng tác vụ phân cấp (Hierarchical Task Network Planning)

• Phương pháp lập kế hoạch dựa trên mạng tác vụ phân cấp (HTN) dùng cho các bài toán phức tạp.

• Trong lập kế hoạch HTN, kế hoạch khởi tạo mô tả về cái gì sẽ làm ở mức cao (ví dụ xây nhà).

• Các kế hoạch được làm mịn bằng cách áp dụng phân tách tác động.

• Mỗi phân tách tác động diễn dịch tác động mức cao thành tập thứ tự bộ phận các tác động ở mức thấp.

• Quá trình tiếp tục cho đến khi chỉ còn các tác động gốc trong kế hoạch.

• Các phân tách tác động thể hiện tri thức về việc cài đặt tác động.

• Ví dụ. Việc xây nhà có thể diễn dịch thành các tác động: xin giấy phép; thuê nhà thầu; thực hiệu xây dựng và thanh toán cho nhà thầu. (hình 12.5).

• Tác động gốc thường là các tác động mà agent có thể thực hiện tự động (nhưng còn tuỳ ngữ cảnh). Đối với nhà thầu chung thì tạo cảnh có thể là tác động gốc còn với nhà thầu tạo cảnh thì trồng cây A ở chỗ B mới có thể là tác động gốc.

• Trong lập kế hoạch HTN thuần tuý, các kế hoạch được tạo sinh nhờ các phân tách tác động liên tiếp.

• HTN xem việc lập kế hoạch là mô tả các tác động từng bước cụ thể hơn, không phải là quá trình xây dựng một mô tả tác động bắt đầu từ kế hoạch rỗng như trước.

Câu 43: (Mrs. Huyền)

Cho ví dụ về phương pháp phân tách tác động và biễu diễn trong mạng tác vụ phân cấp

• Phương pháp lập kế hoạch dựa trên mạng tác vụ phân cấp (HTN) dùng cho các bài toán phức tạp.

• Trong lập kế hoạch mạng tác vụ phân cấp, kế hoạch khởi tạo mô tả về cái gì sẽ làm ở mức cao (ví dụ xây nhà).

• Các kế hoạch được làm mịn bằng cách áp dụng phân tách tác động.

• Mỗi phân tách tác động diễn dịch tác động mức cao thành tập thứ tự bộ phận các tác động ở mức thấp.

• Quá trình tiếp tục cho đến khi chỉ còn các tác động gốc trong kế hoạch.

• Các phân tách tác động thể hiện tri thức về việc cài đặt tác động.

• Ví dụ. Việc xây nhà có thể diễn dịch thành các tác động: xin giấy phép; thuê nhà thầu; thực hiệu xây dựng và thanh toán cho nhà thầu. (hình 12.5).

• Trong lập kế hoạch mạng tác vụ phân cấp thuần tuý, các kế hoạch được tạo sinh nhờ các phân tách tác động liên tiếp.

• Mạng tác vụ phân cấp xem việc lập kế hoạch là mô tả các tác động từng bước cụ thể hơn, không phải là quá trình xây dựng một mô tả tác động bắt đầu từ kế hoạch rỗng như trước.

Biễu diễn phân hoạch tác động.

• Các mô tả chung về các phương pháp phân tách tác động được lưu trữ trong thư viện kế hoạch (Plan library), từ đó chúng được trích ra và khởi tạo phù hợp với đòi hỏi của kế hoạch đang được xây dựng.

• Mỗi phương pháp là một biễu diễn của dạng Decompose(a,d), tức là một tác động a được phân tách thành kế hoạch d và được biểu diễn như một kế hoạch thứ tự bộ phận được.

Ví dụ xây nhà. ( Hình 12.5)

Tác động BuildHouse phân tách thành 4 tác động mức thấp hơn. Hình 12.6 chỉ ra một số mô tả tác động cho phân tách tác động BuildHouse có thể có trong thư viện kế hoạch. (Ngoài ra, có thể có các phân tách khác trong thư viện.)

Tiền điều kiện ngoài (External Precondition)

Tác động Start của phân tách cung cấp các tiền điều kiện của các tác động trong kế hoạch mà chúng không được cung cấp bởi các tác động khác. Ta gọi chúng là các tiền điều kiện ngoài.

Trong ví dụ của ta, tiền điều kiện ngoài là Land và Money.

Hiệu quả ngoài (External Effects):là tiền điều kiện của Finish, chúng là các hiệu quả của các tác động trong kế hoạch không bị phủ định bởi các tác động khác.

Ví dụ, hiệu quả ngoài của BuildHouse là House và ¬Money.

Một số bộ lập kế hoạch mạng tác vụ phân cấp cũng phân biêt hiệu quả gốc (House) và hiệu quả thứ cấp (¬Money).

+ Chỉ các hiệu quả gốc có thể dùng để đạt được đích

+ Cả hai loại hiệu quả đều có thể tạo nên mâu thuẫn với các tác động khác, chúng giúp giảm không gian tìm kiếm.

Phân tách có thể .

Một phân tách có thể là một thực hiện đúng tác động. Một kế hoạch d thực hiện đúng tác động a nếu d là một kế hoạch thứ tự bộ phận thích hợp và đầy đủ của bài toán đạt được các hiệu quả của a với tiền điều kiện đã cho của a.

Hiển nhiên phân tách là đúng nếu nó là kết quả nhờ chạy một bộ lập kế hoạch thứ tự bộ phận hoàn chỉnh.

Một thư viện kế hoạch có thể chứa một số phân tách cho một tác động mức cao.

Ví dụ. có thể có một phân tách khác mô tả một quá trình xây nhà, trong đó agent xây nhà thủ công bằng đá, đất .

• Mỗi phân tách có thể là một kế hoạch đúng nhưng có thể có các hiệu quả và tiền điều kiện bổ sung ngoài những gì đã có trong mô tả mức cao.

Ví dụ: phân tách xây nhà ( hình 12.5 ) đòi hỏi thêm Money vào cùng với Land và có hiệu quả ¬Money. Mặt khác, lựa chọn tự xây không đòi hỏi Money nhưng đòi hỏi Rock và Turf - có thể xét trong thời lạc hậu ( Badback).

• Với một tác động mức cao có thể có một số phân tách chấp nhận được, mô tả tác động của nó có thể ẩn một số tiền điều kiện và hệ quả của riêng phân tách ấy.

• Tiền điều kiện của tác động ở mức cao có thể có giao với tiền điều kiện ngoài của phân tách (hiệu quả cũng vậy).

Nói cách khác, tiền điều kiện và hiệu quả mức cao được đảm bảo là một tập con của tiền điều kiện và hiệu quả đúng của mỗt thực hiện gốc.

Hai dạng khác của thông tin ẩn:

1. Mô tả mức cao hoàn toàn không để ý tới các hiệu quả trong của phân tách.

Ví dụ: phân tách BuildHouse có hiệu quả trong là Permit và Contract

2. Mô tả mức cao không chỉ rõ khoảng thời gian tác động trong đó tiền điều kiện và hiệu quả mức cao xảy ra.

Ví dụ: tiền điều kiện Land cần đúng chỉ tới khi GetPermit được thực hiện, House là đúng chỉ sau khi PayBuild được thực hiện.

Ẩn thông tin như vậy quan trọng là để giảm độ phức tạp trong lập kế hoạch phân cấp: ta cần khả năng lập luận về các tác động mức cao mà không quan tâm tới chi tiết của tác động.

Nhược điểm. Ví dụ, có thể tồn tại mâu thuẫn giữa các điều kiện trong của một tác động mức cao và tác động trong của phân tách khác nhưng không thể khám phá được từ mô tả mức cao.

Câu 44: (Mrs. Huyền)

Trình bày thuật toán thuật toán AND-OR-GRAPH-SEARCH trong môi trường quan sát đầy đủ

Thuật toán AND-OR-GRAPH-SEARCH.

Không gian tìm kiếm là một đồ thị AND-OR

Để lập kế hoạch, dùng đồ thị thuật toán AND-OR-SEARCH với sửa đổi

+ Kế hoạch cần lấy một tác động nào đó tại mỗi trạng thái đạt đến nhưng phải nắm được kết quả của tác động mà nó thực hiện.

+ Tại một nút OR, một tác động được chọn.

+ Ở nút AND, là một chuỗi lồng nhau của các bước if-then-else đặc tả các kế hoạch con đối với mỗi kết quả ra; kiểm tra trong các bước này là các mô tả trạng thái đầy đủ. (kế hoạch như vậy cũng có thể xem xây dựng tình huống (Case construct). Ở đây các nhánh là tác động (Hình 12.10)

Xử lý các chu trình

Một điểm then chốt trong các bài toán lập kế hoạch bất định (tức là một tác động có thể không có hiệu quả hoặc có hiệu quả không dự tính trước xảy ra) là cách xử lý các chu trình .

Nếu trạng thái hiện thời là đồng nhất với một trạng thái trên đường từ gốc thì nó trả lại với thất bại (returns with failure). Điều này không có nghĩa là không có lời giải từ trạng thái hiện thời, mà có nghĩa là nếu có một lời giải không chu trình thì nó phải đạt đến từ tổ tiên của trạng thái hiện thời nên các trạng thái mới có thể loại bỏ.

Với cách kiểm tra này, đảm bảo thuật toán kết thúc trong mỗi không gian trạng thái hữu hạn (bởi vì mỗi đường phải đạt được một đích, một kết thúc chết hoặc một trạng thái lặp).

Nhớ rằng thuật toán không kiểm tra liệu trạng thái hiện tại có là một trạng thái của đường khác từ gốc hay không.

Tìm kiếm theo biến đơn.

Kế hoạch nhận được từ tìm kiếm đồ thị AND-OR chứa các bước điều kiện mà chúng kiểm tra (mô tả trạng thái toàn bộ) để quyết định vào một nhánh.

Trong nhiều trường hợp, có thể kiểm tra không vét cạn. Chẳng hạn, lời giải trong hình 12.9 có thể viết đơn giản là:

[Left, if CleanL then [ ] else Suck].

CleanL đủ để chia các trạng thái ở nút AND thành hai tập đơn nên sau khi kiểm tra thì agent biết rõ nó đang ở trạng thái nào.

Một loạt phép kiểm định if-then-else của các biến đơn luôn đủ để chia tập trạng thái thành các tập riêng khi trạng thái được quan sát đầy đủ. Vì vậy, không mất tổng quát, ta chỉ hạn chế trong việc kiểm tra các biến đơn.

Tác động không hiệu quả.

Có một rắc rối cuối cùng thường nảy sinh trong miền bất định là tác động không hiệu quả mà phải làm lại.

Ví dụ máy hút bụi 3-Murphy (Hình 12.11), tác động đôi khi không theo lệnh:

Left có thể có hiệu quả tuyển là AtL V AtR

Bây giờ kế hoạch [Left, if CleanL then [ ] else Suck] không đảm bảo làm việc nữa.

Hình 12.11 chỉ ra không có lời giải không có khuyên, thuật toán AND-OR-GRAPH-SEARCH có thể cho kết quả thất bại. Tuy nhiên có một lời giải chu trình (Cycle solution) mà nó cứ thử Left cho đến khi nó làm việc.

Ta có thể biểu diễn lời giải này bằng cách thêm vào một nhãn để ký hiệu một phần nào đó của kế hoạch và dùng nhãn này về sau thay cho lặp lại nó trong kế hoạch. Vậy nên lời giải chu trình là:

[L1 : Left, if AtR then L1 else if CleanL then [] else Suck].

(Cú pháp tốt hơn của phần lặp trong kế hoạch này là "while AtR do Left.") .

Trường hợp xấu là các vòng lặp này có thể vô hạn. Chẳng hạn không chắc tác động Left trong 3-Murphy sẽ có lúc có kết quả. Vì vậy kế hoạch chu trình không được ưa bằng kế hoạch không chu trình nhưng chúng có thể là lời giải được xét đến

Câu 45.

Trình bày về lập kế hoạch có điều kiện trong môi trường quan sát đầy đủ nhờ minh họa bởi bài toán máy hút bụi.

Lập kế hoạch có điều kiện:

• Để xử lý tính bất định nhờ kiểm tra những gì đang xảy ra ở môi trường tại mỗi điểm định trước của kế hoạch.

• Là cách đơn giản nhất để giải thích đối với môi trường quan sát đầy đủ.

• Môi trường quan sát từng phần khó hơn

Lập kế hoạch có điều kiện trong môi trường quan sát đầy đủ:

Quan sát đầy đủ : agent luôn biết trạng thái hiện thời.

Trong môi trường bất định, agent có thể không dự báo được kết quả của tác động.

Agent sẽ xử lý tính bất định bằng cách xây dựng trong kế hoạch các bước có điều kiện trong đó nó sẽ kiểm tra trạng thái của môi trường để quyết định làm gì tiếp theo

Xét ví dụ về máy hút bụi mà không gian trạng thái trong trường hợp tất định đã biết:

• 8 trạng thái ở một trong hai ô: trái, phải ;có buị hoặc không.

• Ba tác động Left; Right và Suck.

• Một số mệnh đề để xác định trạng thái: AtL đúng nếu agent đang ở ô trái

AtR :phải,

AtL là đúng iff ¬AtR và ngược lại;

CleanL (CleanR) đúng nếu nếu ô trái (phải) là sạch.

Ta cần lập luận theo STRPSS cho phép bất định.

Hiệu quả tuyển (disjunctive effect

Để lập luận theo STRPSS với tính bất định, ta cho phép có hiệu quả tuyển:

tác động có thể có nhiều kết quả mỗi khi nó được thực hiện.

Ví dụ mô tả chuẩn của tác động sang trái:

phải sửa lại để bằng hiệu quả tuyển:

Hiệu quả có điều kiện (conditional effect),

Cho phép hiệu quả có điều kiện: hiệu quả của tác động tùy thuộc vào trạng thái hiện thời thực hiện tác động.

Hiệu quả có điều kiện được đặt ở khe Effect của tác động ; có cú pháp:

"when : ".

Ví dụ, tác động Suck có thể viết là:

Hiệu quả có điều kiện chưa đưa vào tính không xác định nhưng chúng có thể giúp để mô hình nó.

Ví dụ: ta có một máy hút bụi láu cá, đôi khi nó xả bụi ra trong ô đến khi nó di chuyển nhưng chỉ khi ô này sạch. Điều này có thể được mô hình là:

gồm cả tuyển và điều kiện.

Trong đó hiệu quả điều kiện: when CleanL: ¬CleanL có thể hơi kỳ quặc, nhớrằng lCleanL nói tình trạng trưốc khi tác động và ¬CleanL nói tình trạng sau tác động.

Để tạo ra kế hoạch có điều kiện , ta cần các bước điều kiện với cú pháp:

"if then plan.A else plan.B,"

trong đó là một hàm logic của các biến trạng thái.

Ví dụ, một bước điều kiện cho máy hút bụi có thể là:

Nhờ lồng các bước như thế, các kế hoạch trở thành các cây.

Ví dụ. Thế giới máy hút bụi.

Trạng thái ban đầu có một Robot ở ô bên phải của một thế giới sạch;

Vì môi trường quan sát đầy đủ nên agent biết mô tả toàn bộ trạng thái.

Trạng thái đích có Robot ở ô bên trái và thế giới sạch.

Tính bất định: máy hút bụi đôi khi xả bụi khi nó chuyển đến ô sạch hoặc xả rác khi nó hút ở một ô sạch. ( hình 12.9.)

Các tác động của robot được lấy ở các nút trạng thái của cây

quyết định cơ may của đầu ra được chỉ ra ở nút tròn.

Lời giải là một cây con :

(1) Có một nút đích ở mỗi lá

(2) Đặc tả một tác động tại mỗi nút trạng thái của nó

(3) Bao gồm mỗi nhánh kết quả ra cho mỗi nút cơ hội

Lời giải được chỉ ra bằng đường in đậm trong hình; tương ứng với kế hoạch:

(dùng bộ lập kế hoạch không gian-trạng thái, các kiểm tra trong các bước điều kiện là mô tả trạng thái đầy đủ)

Câu 46.

Trình bày về lập kế hoạch có điều kiện trong môi trường quan sát từng phần

Môi trường quan sát đầy đủ, nó có ưu điểm là có thể hỏi bất cứ câu hỏi nào ở mọi lúc và chắc chắn có câu trả lời.

Trong thế giới thực, thường gặp môi trường quan sát từng phần hơn.

Trong quan sát từng phần, agent chỉ biết một số thông tin về trạng thái hiện thời.

Trạng thái tin chắc

Cách đơn giản nhất để mô hình tình trạng này là nói rằng trạng thái đang xét thuộc về một tập trạng thái; tập trạng thái là một cách để mô tả trạng thái tin chắc của agent.

Giả sử agent hút bụi biết rằng nó đang ở ô bên phải và ô này sạch nhưng nó không cảm nhận được có bụi trong ô khác hay không. Thì nó biết là nó có thể ở một trong hai trạng thái: ô bên trái có thể sạch hoặc bẩn..

Trạng thái tin chắc này được đánh dấu A trong hình 12.12( phần của đồ thị AND-OR đối với máy hút bụi 2-Murphy , trong đó bụi có thể để lại phía sau khi agent rời một ô sạch).

Đồ thị AND-OR được xây dựng ra sao?

Các kết quả là các trạng thái tin chắc:

Từ trạng thái tin chắc A, các kết quả của tác động Left ( agent có thể để bẩn lại phía sau) từ hai thế giới có thể ban đầu trở thành 4 thế giới có thể được chỉ ra trong B và C.

Các thế giới tạo nên hai trạng thái tin chắc khác biệt , chúng được phân lớp bằng thông tin cảm nhận sẵn có

Các nhánh trong trạng thái tin chắc được tạo nên do tri thức về đầu ra khác nhau chứ không phải do đầu ra vật lí khác nhau:

Trong B, agent biết CleanL ; trong C nó biết ¬CleanL.

Từ C làm sạch; chuyển agent sang B.

Từ B chuyển sang phải có thể để lại bẩn phía sau hoặc không; vậy nên có bốn thế giới có thể được chia bởi tri thức của agent về việc CleanR (quay trở về A) hoặc ¬CleanR (trạng thái tin chắc D) .

Môi trường quan sát từng phần bất định được biểu diễn bằng một đồ thị AND-OR của các tập trạng thái tin chắc.

Kế hoạch có điều kiện có thể được tìm bằng đúng thuật toán AND-OR-GRAPH-SEARCH như trong trường hợp quan sát đầy đủ.

Lúc đó xem các trạng thái tin chắc của agent là luôn luôn quan sát đầy đủ- nó luôn biết cái nó biết.

Bài toán toán quan sát đầy đủ là trường hợp đặc biệt trong đó mỗi tập trạng thái tin chắc chỉ có đúng một trạng thái vật lý.

Biễu diễn trạng thái tin chắc, nhận biết và mô tả tác động .

Có ba lựa chọn cơ bản cho biểu diễn các trạng thái tin chắc.

1-Các tập mô tả trạng thái đầy đủ. Chẳng hạn, trạng thái tin chắc ban đầu cho trong hình 12.12 là:

Biễu diễn này đơn giản để làm việc nhưng phải trả giá nếu có n mệnh đề logic xác định trạng thái thì trạng thái tin chắc có thể chứa O( 2n ) mô tả trạng thái vật lý, mỗi trạng thái vật lý cókích cỡ O(n). Các trạng thái tin chắc sẽ lớn cỡ hàm mũ khi agent chỉ biết một phần của các mệnh đề.

Câu logic phản ánh đúng tập thế giới có thể trong trạng thái tin chắc.

Ví dụ, trạng thái ban đầu có thể viết là:

Trạng thái tin chắc có thể được phản ánh đúng bằng một câu logic nếu dùng tuyển của tất cả mô tả trạng thái hội.

Nhược điểm: các câu logic tổng quát có nhiều câu tương đương logic khác nhau cho cùng một trạng thái tin chắc nên việc kiểm tra các trạng thái trùng lặp trong thuật toán tìm kiếm trên đồ thị cần được chứng minh.

Vì vậy ta muốn có một biểu diễn chính tắc (canonical) cho các câu: mỗi trạng thái tin chắc tương ứng với đúng một hội của các literal được sắp thứ tự bằng tên các mệnh đề. ví dụ:

Đây là biểu diễn chuẩn với gỉa thiết thế giới mở. Không phải mọi câu logic đều viết được dưới dạng như vậy ( ví dụ ) nhưng có nhiều miền có thể được

Các mệnh đề tri thức mô tả tri thức của agent.

Đối với trạng thái ban đầu ta có:

ở đây K có nghĩa " biết rằng" và K(P) có nghĩa agent biết P là đúng.

Với các mệnh đề tri thức, ta dùng giả thiết thế giới đóng :

nếu một mệnh đề tri thức không xuất hiện trong danh sách thì giả thiết nó sai.

Ví dụ: ¬K(CleaneL) và ¬K(¬CleanL) là ẩn trong câu trên thì nó ẩn yếu tố là agent không biết giá trị đúng của cleane

Ta thườngdùng lựa chon thứ ba (mệnh đề tri thức, vì nó cho các ví dụ sinh động hơn và vì ta đã biết mô tả STRIPS cho thế giới đóng).

Xử lý nhận thức.

Có hai cách lựa chọn:

1-Ta có thể nhận biết tự động tức là ở mỗi bước thời gian, agent nhận tất cả các nhận thức sẵn có. Ví dụ: trong hình 12.12 giả thiết nhận biết tự động về vị trí và bẩn địa phương.

2- Nhận biết tích cực, có nghĩa là các nhận thức đạt được chỉ bằng thực hiện các tác động cảm nhận cụ thể (sensory actions) như là CheckDirt và CheckLocation. Ta lần lượt xử lý mỗi loại nhận biết.

Giả sử mô tả tác động sử dụng mệnh đề tri thức. Giả định agent chuyển sang trái trong thế giới 2-Murphy với nhận biết bẩn địa phương tự động: theo quy tắc agent có thể để lại bẩn phía sau ô đã làm sạch hoặc không. Về hiệu quả vật lý, điều này có thể là tuyển, nhưng như một hiệu quả tri thức, nó chỉ đơn giản là loại trừ tri thức của agent về CleanR.

Agent cũng biết CleanL là đúng hay không vì nó nhận biết bẩn địa phương. Và nó biết nó đang ở L (AtL.):

Chú ý: các tiền điều kiện và các điều kiện when là mệnh đề giải thích chứ không phải là mệnh đề tri thức

Làm thế nào để kiểm tra giá trị đúng khi ta chỉ có trạng thái tin chắc kết quả của tác động phụ thuộc vào thế giới hiện thời?

+Nếu agent biết một mệnh đề (K(AtR)) trong trạng thái tin chắc hiện thời thì nó đúng trong trạng thái vật lý hiện thời và tác động là ứng dụng được.

+Nếu agent không biết một mệnh đề, chẳng hạn điều kiện when CleanR thì thì trạng thái tin chắc phải bao gồm thế giới trong nó là đúng và thế giới trong đó CleanR là sai.

Điều này làm tác động dẫn đến trạng thái tin chắc bội. Nếu trạng thái ban đầu là: Thì thì sau khi đi sang trái, kết quả hai trạng thái tin chắc là

Trong cả hai trường hợp, giá trị đúng của CleanL đã biết nên kiểm tra CleanL có thể được dùng trong kế hoạch.

Với nhận biết tích cực.

Agent tiếp nhận nhân thức mới chỉ nhờ hỏi về chúng.

Sau khi sang trái, agent không biết ô bên trái này bẩn hay không

Để nhận ra ô này có bẩn hay không, agent phải gọi CheckDirt.

Left tiếp theo là CheckDirt trong nhận biết tích cực dẫn đến kết quả hai trạng thái tin chắc như nhận biết tự động với tác động Left đã làm.

Trong nhận biết tích cực, các tác động vật lý ánh xạ một trạng thái tin chắc vào một trạng thái tin chắc kế tiếp.

Các trạng thái tin chắc bội có thể được giới thiệu chỉ nhờ các tác động cảm nhận, chúng cung cấp tri thức chi tiết và do đó cho phép các kiểm tra có điều kiện được dùng trong kế hoạch.

Câu 47: (Ms. Hoa)

Trình bày về agent theo dõi thực hiện và tái hoạch định. Trình bày về lập kế hoạch liên tục.

* Agent theo dõi thực hiện:

Một agent theo dõi thực hiện luôn kiểm tra nhận thức của nó để biết liệu mọi cái có phù hợp với kế hoạch không.

Trong bài toán bất định không giới hạn, một số tình trạng không định trước luôn có thể xuất hiện, nên theo dõi thực hiện là cần thiết trong môi trường thực.

Hai loại giám sát thực hiện thông dụng:

+ Giám sát tác động: agent kiểm định môi trường để kiểm tra tác động tiếp theo sẽ làm việc.

+ Theo dõi kế hoạch (phức tạp nhưng hiệu quả hơn): agent kiểm tra toàn bộ phần kế hoạch còn lại.

* Agent tái hoạch định:

Một agent tái hoạch định luôn biết cần phải làm gì khi xảy ra bất thường.

Gọi một bộ lập kế hoạch để có kế hoạch mới đạt được đích. Để tránh mất nhiều thời gian lập lịch, việc tái hoạch định này thường sửa lại kế hoạch cũ, tìm cách từ trạng thái bất thường quay về kế hoạch đã có.

Agent tái hoạch định theo dõi cả phần còn lại của kế hoạch (kế hoạch phân đoạn) và kế hoạch gốc (kế hoạch toàn bộ).

* Lập kế hoạch liên tục:

Bây giờ ta xét một agent bền bỉ lập kế hoạch mà môi trường và do đó đích và các pha tác động thay đổi trong khi lập kế hoạch và điều chỉnh. Ta gọi nó là agent lập kế hoạch liên tục (CP-agent).

+ Agent này luôn ở trạng thái đang thực hiện một phần của kế hoạch lớn trong đời.

+ Các hoạt động đang thực hiện của kế hoạch là để thỏa mãn điều kiện mở hoặc giải quyết tranh chấp và đổi một kế hoạch với các thông tin mới.

+ CP-agent xây dựng kế hoạch một cách tăng cường với mỗi lần tăng cường có thời gian hạn chế

(trước đây, nó có thể nhận thức và thực hiện cho một kế hoạch đầy đủ).

Câu 48: (Ms. Hoa)

Cho biết các nguyên nhân agent phải tác động trong môi trường không chắc chắn, cho ví dụ.

* Các nguyên nhân agent phải tác động trong môi trường không chắc chắn:

Con người hầu như không hiểu biết một cách đầy dủ và chính xác về môi trường, trong nhiều trường hợp các thông tin mà chúng ta biết được hoặc không chính xác, hoặc không chắc chắn. Trong hoàn cảnh các thông tin biết được không chắc chắn, các tác tử thông minh (intelligent agents) vẫn cần phải đưa ra các quyết định, các hành động. Một vấn đề đặt ra là, trên cơ sở nào để các quyết định, các hành động mà các tác nhân đưa ra được xem là hợp lý, đúng đắn. Vì vậy, việc nghiên cứu các mô hình biểu diễn tri thức không chắc chắn và các phương thức suy luận liên quan tới tính không chắc chắn (uncertainty) đóng vai trò quan trọng trong các hệ thông minh.

+ Tính không chắc chắn có thể xuất hiện từ nhiều nguồn. Trước hết, có những quá trình mà bản chất của nó chúng ta không thể mô tả chính xác bởi các mô hình đơn định. Chẳng hạn, chúng ta xét quá trình một cầu thủ sút phạt 11m. trước khi cầu thủ đá phạt, chúng ta không thể đoán biết được quỹ đạo chuyển động của quả bóng, tốc độ chuyển động của nó, quả bóng có vào gôn, vọt xà ngang hay trúng cột bên trái,...

+ Tính không chắc chắn có thể xuất hiện do sự hiểu biết không đầy đủ của chúng ta về vấn đề đang xét. Có thể thấy rõ điều này khi các bác sĩ chẩn đoán bệnh, khi các kỹ sư phỏng đoán sự hỏng hóc của máy móc. Do sự hiểu biết không đầy đủ nguyên nhân, cơ chế gây bệnh, người thầy thuốc chỉ có thể nói, chẳng hạn với các triệu chứng và các kết quả xét nghiệm, là họ biết thì có 80% khả năng bệnh nhân bị sốt xuất huyết. Ngay cả khi chúng ta có thể mô tả chính xác, đơn định một quá trình, nhưng nếu mô tả đầy đủ và chính xác thì sẽ rất phức tạp,độ phức tạp của tính toán, lập luận sẽ rất cao. Trong các trường hợp đó, người ta có thể mô tả xấp xỉ bằng cách sử dụng tính không chắc chắn để đơn giản cho việc tính toán, suy diễn.

* Để làm sáng tỏ các nguyên nhân agent phải tác động trong môi trường không chắc chắn ở trên, chúng ta xét ví dụ sau:

Giả sử bệnh nhân hút thuốc (smoking). Đương nhiên, không phải bệnh nhân nào hút thuốc cũng ung thư (cancer). Trong y học, người ta chưa biết được chính xác những nguyên nhân nào thì một người hút thuốc sẽ bị ung thư và những nguyên nhân nào thì một người hút thuốc sẽ không ung thư. Bây giờ, giả sử rằng người ta biết được đầy đủ các điều kiện mà một bệnh nhân hút thuốc sẽ bị ung thư. Vị từ smoking(p) có nghĩa là bệnh nhân p hút thuốc; vị từ symtom(p, Sk): bệnh nhân p có triệu chứng Sk và vị từ cancer(p): bệnh nhân p bị ung thư. Sử dụng các vị từ này có:

Smoking(p) Symtom(p, S1) ... Symtom(p, Sn)  cancer(p)

Nếu như số các điều kiện Symtom(p, S k) rất lớn thì trong trường hợp này, thay vì sự mô tả chính xác bởi luật trên người ta sử dụng tính không chắc chắn để mô tả xấp xỉ mối quan hệ nhân-quả. Chẳng hạn, người ta nói: Smoking(p)  Cancer(p) với độ tin cậy là 8 %.

-------------------------------

Câu 50: (Ms. Hòa)

Ngữ nghĩa mạng Bayer

Ngữ nghĩa toàn cục (Global semantics): Ngữ nghĩa toàn cục xác định phân bố đầy đủ là tích của các phân bố địa phương có điều kiện:

Ví dụ:

Ngữ nghĩa cục bộ (Local semantics): Mỗi nút là độc lập có điều kiện với các nút con cháu của nó khi cho trước các nút cha

Ta có định lý: Ngữ nghĩa toàn cục Ngữ nghĩa cục bộ

Câu 51: (Mrs. Hạnh)

Trình bầy cách xây dựng mạng Bayes?

Trả lời:

a) Giới thiệu sơ lược về mạng Bayes:

• Định nghĩa:

Bayesian Belief Networks (BBNs) còn gọi là Bayesian Networks (BNs) hay Belief Networks (BNs) được phát triển đầu tiên vào cuối những năm 1970s ở Đại học Stanford [1]. BBNs là mô hình đồ thị (graphical model) thể hiện mối quan hệ nhân - quả (cause - effect) giữa các biến. BBNs chủ yếu dựa trên lý thuyết xác suất có điều kiện hay còn gọi là lý thuyết Bayes (Bayesian theory, hay Bayes' theory). Chính vì thế, kỹ thuật này có tên gọi là Bayesian Belief Networks (BBNs).

• Ý nghĩa:

Trong lĩnh vực xây dựng, BBNs dùng để dự báo, đánh giá rủi ro tiến độ, kinh phí, chất lượng, tai nạn lao động... Ngoài ra, BBNs còn được dùng để chuẩn đoán trong y học; trong công nghệ kỹ thuật, dự báo chất lượng của các phần mềm máy tính, rủi ro tai nạn đường sắt...

• Cơ sở lý thuyết:

Công thức Bayes

BBNs dựa trên lý thuyết xác suất có điều kiện của Thomas Bayes, ông này đã đưa ra qui luật cơ bản của xác suất, do đó gọi là công thức Bayes [4]. Công thức đơn giản nhất như sau:

Trong đó:

A và B là hai sự kiện có thể xảy ra và phụ thuộc với nhau.

P(A) là xác suất của sự kiện A;

P(B) là xác suất của sự kiện B;

P(B/A) là xác suất có điều kiện của B khi biết trước A đã xảy ra;

P(A/B) là xác suất có điều kiện của A khi biết trước B đã xảy ra.

Cấu trúc mạng BBNs

BBNs là mô hình trực tiếp mà mỗi biến được đại diện bởi một nút (node), mối quan hệ nhân quả giữa hai biến đó được biểu thị bằng mũi tên được gọi "edge". Mũi tên hướng từ nút nguyên nhân "parent node" đến nút kết quả "child node". Nút kết quả phụ thuộc có điều kiện vào nút nguyên nhân. Mỗi nút (hay là biến) có một trạng thái (state) tùy thuộc đặc trưng của biến đó.

Cấu trúc mạng Bayes tổng quát:

Bảng xác suất có điều kiện (CPT)

Mỗi nút luôn được gắn với một bảng xác suất có điều kiện (conditional probability table: CPT) dựa vào những thông tin ban đầu hay dữ liệu, kinh nghiệm trong quá khứ.

Ví dụ: theo sơ đồ 2, nút "tuyết rơi" là nút nguyên nhân ảnh hưởng đến nút kết quả "tình trạng con đường" và chúng có những trạng thái tương ứng .

Bảng xác suất có điều kiện của các biến trong sơ đồ 2 được biểu diễn như sau:

b) Các bước xây dựng mạng Bayes:

• Xác định các biến và trạng thái của chúng để đưa vào mô hình.

• Xác định mối quan hệ "nhân- quả" giữa các biến dựa vào suy luận logic, dữ liệu quá khứ...

• Lập bảng xác suất có điều kiện (CPTs) ứng với mỗi sự kết hợp của biến nguyên nhân và bảng xác suất ban đầu của chúng. CPTs có thể xác định từ kinh nghiệm của chuyên gia, hoặc từ kết quả của mô hình khác...

• Sau khi đã lập CPTs, đưa vào phần mềm để tính toán.

c) Ví dụ ứng dụng phần mềm để xây dựng mạng Bayes:

( Sử dụng phần mềm MSBNX)

Xét mô hình ở sơ đồ 1a:

Giả sử ta có các CPTs như sau:

1- CPT của nút "Cloudy":

Cloudy

True False

0.50 0.50

2- CPT của nút "Spinkler":

Parent nodes Child node

Cloudy Sprinkler

True False

True 0.10 0.90

False 0.50 0.50

3- CPT của nút "Rain":

Parent nodes Child node

Cloudy Rain

True False

True 0.80 0.20

Fasle 0.20 0.80

4- CPT của nút "Wet Grass":

Các bảng xác suất có điều kiện CPTs được đưa vào phần mềm MSBNX như sau:

Kết quả được thể hiện bằng mô hình và các xác suất tương ứng ở sơ đồ 6. Dựa vào đó, ta thấy rằng, xác suất để cho biến "WetGrass" ở trạng thái "True" là 0.6471 và ở trạng thái "Fasle" là 0.3529.

Kết quả sau khi dùng phần mềm để giải mạng Bayes ở sơ đồ 2:

Câu 52: (Ms. Vân)

Trình bày thuật toán liệt kê để suy diễn trong mạng Bayes

Câu 53: (Mrs. Quyên)

thuật toán loại trừ biến để suy diễn trong mạng Bayes

Loại trừ biến: thực hiện các phép cộng từ phải sang trái, lưu trữ các kết quả trung gian (hệ số) để tránh phải tính toán lại:

Tổng hợp ra một biến từ một thể hiện của các hệ số: chuyển bất cứ hệ số không thay đổi (hằng số) ra ngoài, gắn lên ma trận trong những điểm tối ưu của những hệ số còn lại

Giả sử f1, ..., fi không phụ thuộc vào X

Thể hiện điểm tối ưu của các hệ số f1 và f2 được tính như sau:

Ví dụ:

Dưới đây là thủ tục của thuật toán:

Bạn đang đọc truyện trên: Truyen2U.Pro

Trước Sau

#bvc