Đề cương Phát triển hệ thống hướng Agent

MENU ĐỀ CƯƠNG PT HT HƯỚNG AGENT Giới thiệu ngắn gọn về 5 xu hướng phát triển trong lịch sử tính toán nói chung dẫn đến sự ra đời của công nghệ agent. - 2 Agent là gì? Các đặc trưng cơ bản của agent. Phân biệt tính phản ứng và tính chủ động của agent. 2 Đặc tính xã hội của agent là gì. 2 So sánh agent và đối tượng, hệ đa agent với hệ chuyên gia. 3 Phân biệt hệ thống đa agent dạng Purely Reactive và Perception. 4 Phân biệt các dạng kiến trúc agent 5 Chiến lược ưu thế (dominant strategies) và cân bằng NASH trong tương tác đa agent là gì? 9 Giới thiệu ngắn gọn về các mô hình tương tác kiểu đấu giá và chiến lược ưu thế của agent trong các kiểu đấu giá đó. 10 Thương lượng tự động là gì? Giới thiệu ngắn gọn về mô hình thương lượng song phương. 11 Ngôn ngữ truyền thông đa agent là gì? Thế nào là lý thuyết lời nói – hành động (Speech-act theory). 13 Ontology là gì? Vai trò của ontology trong tương tác đa agent? 15 Các phương pháp biểu diễn ontology. 16 Phương pháp xây dựng ontology tổng quát. 16 Phân loại các mô hình tương tác đa agent. 16 Giới thiệu ngắn gọn các mô hình tương tác sử dụng agent trung gian. 17 Giới thiệu và so sánh KQML và FIPA-ACL. 19 So sánh các cách tiếp cận phát triển phần mềm hướng agent. 20 Giới thiệu ngắn gọn các bước trong MaSE. 21 Goal là gì. Phương pháp xác định và phân rã goal trong MaSE. 22 Phương pháp ánh xạ goal sang role trong MaSE. 22 Phương pháp xác định lớp agent trong MaSE. 23 BT 24 ĐỀ CƯƠNG PT HT HƯỚNG AGENT Câu 1:Giới thiệu ngắn gọn về 5 xu hướng phát triển trong lịch sử tính toán nói chung dẫn đến sự ra đời của công nghệ agent. 5 xu hướng phát triển trong lịch sử tính toán dẫn đến sự ra đời của CN agent Ubiqiulity –Đặc tính có mặt khắp nơi Interconnection – kết hợp Inteligence – Thông minh Delegation- Đại diên/thay thế Human oritentation – hướng con người Câu 2 Agent là gì?Các đặc trưng cơ bản của Agent. Phân biệt tính phản ứng và tính chủ động của agent. định nghĩa agent - agent là một hệ tính toán hoàn chỉnh hay chuơng trình đuợc đặt trong một môi truờng nhất định, có khả năng hoạt động một cách tự chủ và mềm dẻo trong môi truờng đó nhằm đạt đuợc mục đích đã thiết kế - Một agent thông minh là một hệ thống máy tính có khả năng hoạt động linh hoạt và tự chủ trong môi truờng. Linh hoat nghĩa là: Phản ứng, chủ động, mang tính xã hội. Các đặc trưng cơ bản của agent tính tự chủ khả năng phản ứng tính chủ động khả năng xã hội ngoài ra agent còn có một số đặc trưng khác như: Tính thích nghi và tự học hỏi; Bền vững trong quá trình hoạt động, Hoạt động huớng đích, Giao tiếp và cộng tác, Linh hoạt, Tính di động. Phân biệt tính phản ứng và tính chủ động của Agent Tính phản ứng: là khả năng agent có thể nhận biết đuợc môi truờng ( qua bộ phận cảm nhận nào đó) và dựa qua nhận biết đó, agent đáp ứng kịp thời những thay đổi xảy ra trog môi truờng. Tính phản ứng thể hiện rõ nhất ở các agent hoạt động trên các môi trường có tính thay đổi như Internet, môi truờng mạng phân tán, môi truờng vật lý,…Phản ứng của mỗi agent đối với 1 môi truờng bên ngoài đều huớng tới việc thực hiện mục tiêu ( đích) của agent đó. Tính chủ động: khi có sự thay đổi của môi trường, agent không chỉ phản ứng một cách đơn giản mà còn xác định một chuỗi các hành động cần thực hiện, bản thân mỗi agent sẽ chủ động trong việc khởi động và thưcj hiện chuỗi hành động này Câu 3: Đặc tính xã hội của agent là gì? Các agent không chỉ huớng tới đích riêng của mình mà còn có khả năng tuơng tác với các agent khác trong hệ thống để huớng tới đích chung của hệ thống. Các hoạt động tuơng tác này rất đa dạng bao gồm: phối hợp, thuơng lượng, cạnh tranh…. Câu 4: So sánh agent và đối tương? Agent và hệ chuyên gia So sánh agent và đối tượng - Xét theo quan điểm hệ thống, có thể xem mỗi agent cùng là một đối tượng nhưng ở mức trừu tượng cao hơn. - Sự khác biệt giữa Agent và đối tượng thể hiện: Agent Object - Agent có tính tự chủ: các agent có thể tự quyết định hành đọng của mình mà không hành động theo yêu cầu của agent khác. - Agent có tính hướng đích: mỗi agent có một đích riêng và đích của các agent trong một hệ thống có thể thống nhất hay không tương thích với nhau. Do đó agent thường phải thương lượng với nhau một quá trình tương tác. - Agent thông minh, có các hành vi linh hoạt dựa trên các đặc trưng như khả năng phản ứng, khả năng xã hội. - Agent hoạt động: mỗi agent có một hoặc nhiều luồng điều khiển (thread) riêng. - Có khả năng liên hệ với các agent khác để tìm kiếm thông tin cũng như nhờ sự hỗ trợ hay thương lượng. - Agent sử dụng ngôn ngữ thông điệp chung để trao đổi thông tin với các agent khác. - Object thường bị động hay nói cách khác object là các thành phần tĩnh và sự tương tác giữa chúng chỉ thông qua các thông điệp. Object chỉ thực sự hoạt động khi nhận được lời gọi hàm từ các đối tượng khác. - Đối tượng không có mục đích riêng, chúng cùng chia sẻ mục đích chung của cả hệ thống. - Object không có khả năng phản ứng và tính xã hội. - Trong hướng đối tượng cũng có điều khiển theo luồng (thread) nhưng không yêu cầu mỗi đối tượng là có một thread riêng mà ngược lại có nhiều đối tượng chung một thread. - Tương tác thông qua sự kích hoạt lẫn nhau không có sự lan tỏa, khi nhận được yêu cầu, chỉ thực hiện yêu cầu trong khả năng của mình. - Object tương tác với nhau qua các thông điệp và các thông điệp của object chỉ giới hạn trong những class độc lập. 2.Agent và hệ chuyên gia agent ES( hệ chuyên gia) Agent được đặt trong môi trường Agent thì hành động Agent có các đặc trưng riêng như: tự chủ, phản ứng, chủ đồng và tính xã hội - Hệ chuyên gia ( Expert system) :là một hệ thống tập trung giải quyết một vấn đè xác định dựa trên tri thức của chuyên gia về vấn đề đó hoặc đua ra lời khuyên. - ES is disembodied, rather than being situated - ES không tương tác với môi trường nào và không bắt buộc phải tương tác với các agent khác - ES không có hành vi phản ứng, chủ động, tính xã hội( hợp tác, phối hợp, cạnh tranh) Câu 5: Phân biệt hệ thống đa agent dạng Purely Reactive và Perception. 1. Purely Reactive agents: - Một số agent quyết định làm gì mà không cần quan tâm đến lịch sử. Quyết định làm gì của chúng hoàn toàn dựa vào hiện tại, không tham chiến đến trạng thái quá khứ. - Chúng ta gọi những agent này là purely reactive: Action: S à A Trong đó: - S: môi trường . S = {s1,s2,L} - A: tập hành động . A={a1,a2,L} Ví dụ: Máy điều nhiệt là một purely reactive agent. Action(e) = off nếu e = nhiệt độ ok on trường hợp còn lại action(e) = off if e = temperature ok on otherwise e: trạng thái (e E) 2. Perception: (Nhận thức) à Hành động riêng của agent: - Sự tách rời của một chức năng Agent quyết định thành các hệ thống con nhận thức (perception) và hành động (Active). - Hàm see là khả năng của agent để quan sát chính nó trong môi trường, nơi mà các hàm action mô tả quyết định của agent. See action Agent Environment - Đầu ra (output) của hàm see là một percept (kết quả tri giác) see: E à Per - Hàm see là hàm ánh xạ từ các trạng thái của môi trường tới percept và đầu ra của action lúc này là một hàm action: Per* à A cái mà ánh xạ chuỗi cảm nhận đưa ra hành động. (Per* chuyển giá trị cảm nhận vào tập hành động) Per* tập giá trị cảm nhận. - Hai trạng thái môi trường khác nhau được ánh xạ tới cùng một kết quả tri giác (percept). Câu 6: Phân biệt các dạng kiến trúc agent Trả lời: Các dạng kiến trúc Agent: Ø Kiến trúc suy diễn ( Deliberative – Logic Based Architectures): - Dựa trên Symbolic AI : Đây là kiến trúc mà quá trình ra quyết định được thực hiện nhờ suy diễn Logic. - Các phương pháp ra quyết định : Logical Reasoning, Pattern matching, Symbolic manipulation. - Miêu tả đặc trưng của thế giới: + Mục đích cần đạt tới. + Tập miêu tả hành động -> tìm một chuỗi action để đạt tới mục đích. + Sử dụng thuật toán đơn giản + Toạ kế hoạch không hiệu quả. Mô hình kiến trúc: Agent Sensors Ef fec tors World Model Planner Plan Executor * Những hạn chế của kiến thức suy diễn: - Vấn đề Transduction : tốn nhiều thời gian để chuyển đổi tất cả những thông tin cần thiết thành Symbolic Representation, đặc biệt nếu môi trường thay đổi rất nhanh. - Vấn đề Representation: Làm thế nào để World – model đuợc biểu diễn một cách tượng trưng và làm thế nào để Agent có thể suy diễn kịp thời với sự thay đổi thông tin - Cho những kết quả hữu hình: những kết quả sau cùng có thể là vô dụng. (có thể có phần kiến trúc BDI hoặc không) Kiến trúc BDI ( Belief- Desire – Intention: Suy luận thông minh) - Kiến trúc dựa trên quá trình suy luận thông minh (Practical reasoning) trong đó quá trình ra quyết định được tiến hành từng bước, các hành động được thực hiện xuất phát từ yêu cầu của hàm mục tiêu đề ra. - Beliefs : biểu diễn tập các thông tin về Agent biết về môi trường hiện tại của nó ( và có thế một vài trạng thái trong). - Desires: cái xác định động cơ của nó – ví dụ cái nó đang khám phá. -Intentions: biểu diễn những quyết định phải hành động như thế nào để hoàn toàn đạt tới desires của nó. - Mô hình kiến trúc (BDI) + Beliefs = “hiểu biết của Agent” + Desires = “những mục đích của Agent” +Intentions=“những mục đích cần hoàn thành”(tập con của Desires). * Extended : goals, plans. Agent Interaction Plan, schedule, execute BDI reasoner Knowledge Base Action Perception ØKiến trúc phản xạ ( Reactive) - Là kiến trúc mà quá trình ra quyết định được cài đặt một cách trực tiếp, tức là sẽ có một ánh xạ trực tiếp từ tình huống tới hành động. - Sự suy diễn phức tạp có thể dẫn đến không lời giải hay đáp ứng về mặt thời gian. - Cho phép (brooks): + Những kiến trúc thông minh được tạo ra không cần Symbolic (AI) Representation. + Behavior thông minh có thể được tạo ra không cần Explicit abstract symbolic reasioning (AI). + Tính thông minh là thuộc tính nổi bật trong hệ thống phức tạp. + Behavior thông minh là kết quả việc tương tác với môi trường. - Sơ đồ kiến trúc: Agent Sensors Ef f ec t ors Stimulus-response behaviours ..... ...... State 1 State 2 State n Action n Action 2 Action 1 - Đặc thù của Agent phản xạ: Tính phản xạ là một mô hình phản xạ cơ sở của hành động (behavior based model of activity) mô hình thao tác tượng trưng được sử dụng trong sơ đồ. - Ưu điểm: đơn giản, kinh tế, kiểm soát được khả năng tính toán, khả năng chịu lỗi cao. - Nhược điểm: + Nếu Agent không sử dụng mô hình giống như mô hình của môi trương trong đó nó hoạt động thì chúng phải có đầy đủ những thông tin cần thiết bên trong để có thể thực hiện các Action thích hợp. + Hầu hết các Agent đều ra quyết định dựa trên các thông tin mang tính cục bộ của riêng mình. + Các agent đều không có khả năng học từ những kinh nghiệm đã gặp phải cũng như nâng cao khả năng của hệ thống kể cả đã hoạt động trong một thời gian dài. Ø Kiến trúc lai – Hybrid : - Kết hợp tính phản xạ và tính suy diễn. - Subsystem tạo ra những kế hoạch và quyết định sử dụng Symbolic reasoning và phản ứng lại sự kiện nhanh chóng mà không cần những reasoning phức tạp. - Mô hình kiến trúc: (Trang bên) Mô hình kiến trúc Hybrid: Agent Coservation modifications Senso r s Ef fec tors Deliberative component World Model Planner Plan Executor Reactive component ..... ...... State 1 State 2 State n Action n Action 2 Action 1 - Mô hình kiến trúc xây dựng theo kiến trúc lớp : Ngang và dọc + Ưu nhược điểm phân lớp chiều ngang : - Đơn giản. Nếu một Agent có n cách cư xử khác nhau thì sẽ cài đặt mô hình này. - Tuy nhiên luôn có sự tranh giành trong việc ra quyết định, để bảo đảm sự tươg thích ta thường đưa vào một hàm điều khiển trung tâm để quyết định xem lớp nào đang điều khiển hoạt động của Agent. - Có sự tương tác giữa các Action khi thực hiện. - Đây là một vấn đề khó và khi hoạt động có thể gây hiện tượng thắt cổ chai trong quá trình ra quyết định. + Ưu nhược điểm của phân lớp dọc: Sự phức tạp trong tương tác giữa các lớp đã đượ giảm. Luồng điều khiển phải đi qua toàn bộ các lớp vì thế nếu 1 lớp nào đó hoạt động không ổn định sẽ ảnh hưởng đến toàn bộ hệ thống. Câu 7: Chiến lược ưu thế (dominant strategies) và cân bằng NASH trong tương tác đa agent là gì? 1. Chiến lược ưu thế (dominant strategies) - Cho rằng mỗi agent có thể có 2 hành động C (“cooperate”) và D (“defect”) - Đưa ra một chiến lược cụ thể nào đó (cả C và D) của agent I, sẽ có một số các outcome có thể. - Nói S1 chiếm ưu thế hơn S2 nếu mỗi “outcome” có thể có bởi i khi thực hiện S1 đều ưu thế hơn mỗi “outcome” có thể có bở i khi thực hiện bởi S2. - Một rational agent sẽ không đóng vai trò một chiến lược ưu thế (tức là sẽ không là một ưu thế tối ưu - hoạt động tốt nhất tại thời điểm hiện tại). - Vì thế, trong khi quyết định làm gì, chúng ta cần loại bỏ các chiến lược chiếm ưu thế. - Không may rằng, không phải lúc nào cũng có duy nhất một chiến lược chiếm ưu thế. 2. Cân bằng NASH: - Nói rằng, hai chiến lược S1 và S2 có cần bằng Nash nếu giả thiết rằng: agent i thực hiện S1, agent j không thể thực hiện S2 tốt hơn và giả thiết rằng agent j thực hiện S2, agent i không thể thực hiện S1 tốt hơn. Note: Không agent nào có động cơ (hành động) đi ra khỏi cân bằng Nash: Lưu ý: - Không phải mọi tương tác đều có cân bằng Nash - Một vài tương tác có thể có nhiều hơn một cân bằng Nash. Ví dụ 1: Trong một trò chơi gồm 2 đối thủ cùng chọn “một số bất kì từ 0 à 10. Người nào chọn số lớn hơn sẽ thua và phải trả tiền cho người kia”. Trò chơi này chỉ có một cân bằng duy nhất: cả 2 cùng chọn số 0. Bất kỳ sự lựa chọn nào khác (mà không cần biết sự lựa chọn của đối thủ kia) cũng có thể làm đối thủ thua cuộc. Khi thay đổi luật chơi, mỗi đối thủ sẽ được hưởng số tiền bằng một con số mà cả hai cùng chọn, nếu chọn trùng nhau thì không ai có tiền, ta sẽ có 11 cân bằng Nash. Ví dụ 2: Với vấn đề “Thế trói buộc tiến thoái lưỡng nan của người tù nhân” Song đề này minh họa sự mâu thuẫn giữa hành vi cá nhân, có năng lực suy đoán và lợi ích của việc hợp tác. Vấn đề mấu chốt là mỗi khi đối thủ đều cố gắng tối đa hóa lợi ích của mình mà không quan tâm đến lợi ích của những người khác, tức là đối thủ có tính ích kỷ. Song đề tù nhân có một cân bằng Nash khi cả hai đối thủ đều không tôn trọng giao ước. Tuy nhiên cả 2 đều sai rõ ràng không bằng cả hai cùng hợp tác. Chiến lược hợp tác không bền và một đối thủ có thể làm tốt hơn bằng cách không tôn trọng giao ước trong khi đối thủ của anh ta vẫn hợp tác. Câu 8: Giới thiệu ngắn gọn về các mô hình tương tác kiểu đấu giá và chiến lược ưu thế của agent trong các kiểu đấu giá đó. - Một cuộc đấu giá diễn ra giữa một agent được xem (đóng vai trò) là người bán đấu giá và một sự tụ họp của các agent được biết đến như những người trả giá (trong cuộc đấu giá). - Với những người bán đấu giá thì mục đích của cuộc đấu giá là để (phân phát) háng hóa (sản phẩm) cho một trong số những người trả giá. - Trong hầu hết việc đấu giá, người bán đấu giá thường mong muốn một gía cao nhất (tối đa hóa lợi ích cho mình); những người trả giá lại mong muốn giá trị thấp nhất. à Các tham số của một cuộc đấu giá: 1. Hàng hóa có thể có: - Giá trị riêng - Giá trị chung - Giá trị tương quan 2. Quyết định của người thắng cuộc (trong cuộc đấu giá) có thể: - Giá thứ nhất - Giá thứ hai 3. Trả giá (Đấu giá) có thể: - Open - cry - Đấu giá kín (sealed bid) 4. Sự đấu giá (Sự trả giá) có thể: - One shot - Tăng dần - Giảm dần àCó 4 hình thức đấu giá: - English auctions (Đấu giá kiểu Anh) - Dutch auctions (Đấu giá Hà Lan) - First-Price Sealed Bid (Đấu giá kín nhưng chỉ mua với giá đầu tiên) - Vickrey auctions (Đấu giá Vickrey) * English Auctions (First-Price Open-Cry) - Mỗi người đấu giá tự do để nâng mức giá lên. Khi không có người trả giá cao hơn nữa thì cuộc đấu giá kết thúc và người đấu giá (trả giá) cao nhất sẽ dành được vật đấu giá. - Chiến lược ưu thế cho agent là luôn trả giá nhỏ hơn giá cao nhất ở hiện tại và dừng lại khi đạt được giá thị riêng. * Dutch Auctions (Đấu giá Hà Lan) - Dutch auctions là một ví dụ của các cuộc đấu giá mở giảm dần (open-cry descending auctions) + Người bán đấu giá bắt đầu đưa ra hàng hóa (sản phẩm) ở mức giá ảo cao + Người bán đấu giá giảm dần mức giá được đưa ra tới khi một số agent trả giá bằng giá được đưa ra hiện tại. + Sau đó hàng hóa (sản phẩm) được phân phát cho agent mà (agent) đưa ra giá hợp lý. Chiến lược cho agent: Đấu giá Hà Lan có chiến lược bằng đấu giá kín nhưng chỉ mua với giá đầu tiên. * First-Price Swaled-Bid Auctions (Trả giá kín nhưng chỉ mua với giá thứ nhất) - Là đấu giả kiểu one-shot + Chỉ có một vòng duy nhất. + Người đấu giá chấp nhận đấu giá kín hàng hóa (sản phẩm) + Hàng hóa được phân phát cho agent mà trả giá cao nhất + Người thắng cuộc phải trả giá cao nhất - Trong cuộc đấu giá này thì không có một sự trả giá nào có một chiến lược ưu thế à Chiến lược tốt nhất là: Trả giá thấp hơn giá trị thực. * Vickrey Auctions - Đấu giá là: Giá thứ hai Trả giá kín nhưng chỉ Đấu giá kín mua với giá thứ hai. - Hàng hóa được cấp cho agent trả giá cao nhất: ở mức giá của lần đấu giá cao nhất thứ hai. - Chiến lược chiếm ưu thế cho agent trong đấu giá Vickrey là: trả giá bằng với giá thực của bạn. Câu 9: Thương lượng tự động là gì? Giới thiệu ngắn gọn về mô hình thương lượng song phương. Thương lượng tự động là gì? Thương lượng là một tiến trình đựơc tạo ra bởi hai hay nhiều bên tham gia, mỗi bên tham gia tiến hành đề nghị các yêu cầu và trả lời các yêu cầu cho đối tác nhằm đi đến một thoả thuận chung thoả mãn tất cả các bên . Thương lượng tự động là một quá trình thương lượng, trong đó, người mua và người bán được thay thế bằng các agent. Việc tìm kiếm, mua bán và thoả thuận giữa người mua và người bán được thực hiện tự động bởi các agent. Mô hình thương lượng song phương Thương lượng song phương là dạng thương lượng chỉ có một bên mua và một bên bán tham gia vào quá trình giao dịch. Thương lượng có thể liên quan đến nhiều thuộc tính của hàng hóa như giá bán, chất lượng… Trong thương lượng song phương người ta chia ra 3 cách tiếp cận: Cách tiếp cận dựa trên lý thuyết trò chơi Cách tiêp cận dựa trên Heuristic Cách tiếp cận dựa trên lập luận Mô hình thương lượng song phương àChiến lược thương lượng cho agent bán Trong mô hình thương lượng song phương, agent bán có nhiệm vụ quản lý việc giao dich đồng thời với nhiều khách hàng của mình. Một agent bán được trang bi một tập các tri thức sau: + Tập O=(O1, O2,..., Om} các đơn vị hàng hóa có thể cung cấp, mỗi đơn vị hàng hóa Oi được mô tả thông qua n thuộc tính {o’1,o’2,...o’n} và có một giá trị lợi ích gi nếu bán được đơn vị hàng hóa đó +Một tập R={r1,r2,...,rm} các ràng buộc đối với người mua của các đơn vị hàng hóa. Tập này có miền giá trị kiểu boolean +Một tập C={c1,c2,..cn} các hình thức khuyến mại cho các đơn vị hàng hóa, tập này cũng có giá trị kiểu boolean +Một tập B={B1,B2,..Bk) các khách hang đang thương lượng với agent bán Khi đó, hoạt động thương lượng của agent bán như sau: Quá trình trên có thể diễn ra nhiều lần với một or nhiều agent mua khác nhau àChiến lược thương lượng cho agent mua: Trong mô hình thương lượng song phuong, mỗi agent mua đại diện cho một khách hàng,sẽ thương lượng với một đối tác duy nhất và do đó mỗi agent mua được trag bị các tri thức sau: +Tập A={A1,A2,..,An} các thuộc tính hàng hóa.Mỗi thuộc tính Ai có độ ưu tiên ui tương ứng +Mỗi thuộc tính Ai có một giá trị gọi là ngưỡng nhượng bộ của thuộc tính + Một giá trị ngưỡng chấp nhận đặc trưng cho khả năng chấp nhận của người dùng +Một tập D các cặp thuộc tính và các giá trị của các thuộc tính đã gửi đi cho bên agent bán Quá trình thương lượng của agent mua diễn ra như sau: Câu 10: Ngôn ngữ truyền thông đa agent là gì? Thế nào là lý thuyết lời nói – hành động (Speech-act theory). Ngôn ngữ truyền thông đa agent Các agent trao đổi với nhau thông qua các thông điệp. Khác với các hệ hướng đối tượng trong hệ đa agent không chỉ biểu diễn các lời gọi hàm đơn giản mà còn phải biểu diễn thông tin và tri thức cần trao đổi giữa các