Kĩ thuật lập trình - Agent architectures

1Agent Architectures Kiến trúc Agent và Hệ Agent (C)Copyright Software Engineering Department Lê Tấn Hùng CNTT – ĐHBK Hà nội 2 Nội dung 1. Agent architecture (internal) là gì? 2. Abstract Agent-Architecture 3. Deliberative Architectures (Kiến trúc suy diễn) 4. Reactive Architectures (Kiến trúc phản xạ) 5. Hybrid Architectures (Kiến trúc lai) • Kiến trúc Phân lớp (Layer) 6. Kiến trúc BDI (Belief- Desire- Intention) 7. Kiến trúc mở (OAA) 3 I. Kiến trúc Agent 1.Lý do Kiến trúc Agent? „ Thay thế cho việc chuyển từ ý tưởng, chỉ dẫn thành thực thi chúng „ E.g. after or in the late steps of Gaia „ Làm thế nào để xây dựng những hệ thống máy tính thoả mãn những yêu cầu đặc biệt bằng agent theoritists „ Những kiến trúc phần mềm như thế nào là phù hợp? 4 2. Định nghĩa kiến trúc Agent - I Pattie Maes Một phương pháp học đặc biệt để xây dựng agents. Nó chỉ rõ làm thế nào agent có thể được tách ra thành cấu trúc của 1 tập các modules thành phần và làm thế nào những modules đó có thể tương tác với nhau. Toàn bộ tập modules và sư tương tác giữa chúng cho ta câu trả lời làm thế nào mà những dữ liệu cảm biến and trạng thái hiện tại của agent xác định actions và những trạng thái trong tiếp theo của agent. Một kiến trúc bao gồm các kỹ thuật và thuật toán hỗ trợ cho phương pháp này. 5 Definitions of Agent Architecture - II Kaelbling Một tập hợp đặc biệt các software (or hardware) modules, được thiết kế đặc trưng bởi những hộp với những mũi tên để chỉ ra dữ liệu và dòng điều khiển giữa các modules Một cách nhìn trừu tượng hơn với kiến trúc agent là một phương pháp chung để thiết kế được những modules riêng biệt cho những nhiệm vụ cụ thể 6 Kiến trúc Agent? „ Mô tả các trạng thái trong của agent „ Cấu trúc dữ liệu của nó „ Thao tác có thể thực hiện trên các cấu trúc „ Luồng điều khiển giữa các cấu trúc dữ liệu. „Kiến trúc agent khác nhau trên nhiều khía cạnh khác nhau về cấu trúc dữ liệu và thuật toán được biểu diễn bên trong agent 27 3. Abstract Agent Arch. a.Standard Agent S = { s1, s2, ... } Tập trạng thái môi trường có thể có A = { a1, a2, ... } Tập hành vi của Agent Agent: ÅÆ Function Action: S* Æ A Agent tập ánh xạ các trạng thái của môi trường vào các hành động của agent Kiểu agent này gọi là standard agent.(agent chuẩn) • Một agent chuẩn quyết định hành động để thực thi phụ thuộc vào history của nó, i.e., its experiences to date. AGENT ENVIRONMENT Action Input Sensor Output 8 (Non-)Deterministic Behavior Hành vi của Môi trường mô hình hóa : env: S x A Æ ρ(S) P means the powerset or set of all subsets „ non-determistic if ρ(S) = {sx, sy} Không xác định trạng thái kế tiếp của Agent „ deterministic if ρ(S) = {sx} Î Trạng thái kế tiếp xác định và là duy nhất Interested in agents whose interactions with environment doesn’t end (e.g. infinite) 9 Mô hình trong abstract agent – Sub system „ Lý thuyết tổng quan về Agent là rất hữu ích, nhưng nó không giúp ta xây dựng agent một cách hiệu quả,vì không chỉ ra việc làm thế nào để thiết kế ra những action của agent „ Chúng ta cải tiến lại abstract model, bằng cách chia nhỏ nó thành những hệ thống nhỏ hơn (sub-systems) (like top-down refinement in software engineering). „ Việc cải tiến thành những sub-systems liên quan tới việc lựa chọn dữ liệu và các cấu trúc điều khiển, những thứ hợp thành agent. 10 Kiến trúc trong (Sub-system) „ The sub-system view of an agent: một kiến trúc agent là mô tả thành phần bên trong của Agent: „ cấu trúc dữ liệu của nó, „ những hành động sẽ thao tác trên cấu trúc dữ liệu đó „ dòng điểu khiểu dữ liệu giữa các dữ liệu đó. „ Thường chia chức năng quyết định (desicion) thành hai sub-systems: „ nhận thức (perception) „ hành động (action) 11 Perception và Action Nhận thức và hành động „ Hàm see sẽ quan sát môi trường trong khi đó hàm action biểu diễn hệ thống ra quyết định của agent. ENVIRONMENT seesee actionaction AGENT •Hàm see() Có thể được cài đặt dưới dạng phần cứng/mềm Đầu ra của hàm see() là một tập các tri thức (percept) thu nhận 12 See() và Action() „ Với P là tập nhận thức đầu vào „ See: S -> P „ Action: P* -> A „ Giả sử môi trường có hai trạng thái:s1 và s2; s2≠ s1 „ nhưng see(s1) = see(s1) „ có nghĩa là hai trạng thái môi trường khác nhau nhưng đều được cảm nhận giống nhau (nhìn thấy giống nhau) „ => thông tin thu nhận được là giống nhau 313 Vi dụ „ Cho 2 trạng thái của môi trường, s1 and s2, có thể phân biệt được các agent nếu chúng map to the same percept. „ Ví dụ 1 bộ ổn nhiệt có thể phân biệt được các trạng thái của môi trường: „ x = tooCold „ y = WomanIsDanger „ •:Có nghĩa là trạng thái môi trường cho bởi tập: „ S = {{x,y},{x,!y},{!x,y},{!x,!y}} 14 „ Bây giờ, để hoạt động một cách hiệu quả, bộ cảm nhiệt không quan tâm liệu y = true không? – điều này không ảnh hưởng tới action của nó. „ Vì vậy hàm nhận thức see sẽ là: 15 c.History „ Chúng ta có thể thay thế sự tương tác của agent với môi trường là history, „ Ví dụ:.một chuỗi các cặp: state-action „ với s0 là trạng thái đầu tiên của môi trường „ ai hành động của agent khi nó ở trạng thái si. 16 History of Agent „ với mọi chuỗi h có thể là history của một agent đều bắt đầu từ trạng thái đầu tiên s0: „ Với i ∈ N, ai = action((s0,s1,s2,, si)) „ (tất cả mọi hành động đều phải qua một chuỗi trạng thái) „ i ∈ N such that i> 0, si ∈ env(si-1,ai-1) „ (mỗi trạng thái mới của agent phải thuộc một tập các trạng thái có thể có của môi trường từ trạng thái trước đó và một action cụ thể) „ N là tập số tự nhiên (0,1,2,) 17 Characteristic behaviour „ action:S* ->A , trong một môi trường, „ env:S x A ->P(S), là tập tất cả histories có thể có của agent. Chúng ta sẽ biểu thị tập histories của agent bằng hist(agent,env). „ • Hai agents, agent1 and agent2, được gọi là tương tác tương đương nhau đối với một môi trường, env, iff hist(agent1 ,env) ≡ hist(agent2,env) „ • nếu chúng tương tác tương đương nhau đối với mọi môi trường chúng được gọi đơn giản là behaviourally equivalent. 18 b.State based Agent „ Các agent thường có dữ liệu bên trong „ Dữ liệu: thông tin về trạng thái của môi trường „ Thông tin về quá khứ của Agent seesee nextnext state actionaction AGENT ENVIRONMENT thường sử dụng một chuỗi nhận thức, một agent có trạng thái trong nơi nơi ghi những thông tin về trạng thái môi trường và quá khứ của chính nó 419 Trạng thái trong Internal State „ Gọi I là tập tất cả các trạng thái trong có thể có của agent. „ see : S -> P „ action : I -> A „ Hàm thực hiện quá trình lựa chọn hành động bây giờ được định nghĩa như một ánh xạ từ các trạng thái trong của agent đến tập các hành động có thể được thực hiện: 20 Next() : I x P -> I „ Hàm next(): hàm ánh xạ từ một trạng thái trong I và tri thức thu nhận được P vào một trạng thái trong khác I’ (tức là khi nhận được tri thức mới, trạng thái trong của agent đã thay đổi) „ Vòng lặp: while(true) { p = see(s); i = next(i,p); perform(action(i)); } 21 Behavior – Abstract Agent Arch. 1. Khởi tạo với trạng thái s0 2. Quan sát môi trường với trang thái s, tạo lập và thu nhận tri thức bằng see(s) 3. Trạng thái trong của agent được thay dổi và cập nhật thông qua hàm next(i0,see(s)) 4. Các hành động tiếp theo mà agent thực hiện sẽ được lựa chọn nhờ hàm, action(next(i0,see(s))) 5. Hành động thực hiện sẽ đưa đến 1 chu trình mới (thu nhận tri thức), goto 2 22 State-based vs standard agents „ State-based agents không hiệu quả hơn agent chuẩn (standard agents), đã định nghĩa phần trước „ • Thực tế chúng đồng nhất in their expressive power „ • Tất cả state-based agent có thể được biến đổi thành 1 agent chuẩn có behaviourally equivalent. 23 II.Phân loại kiến trúc Agent „ Deliberative (Kiến trúc suy diễn) Logic-Based Architectures Belief-desire-intension BDI(Suy luận thông minh) „ Reactive (Kiến trúc phản xạ) „ Hybrid (Kiến trúc lai) „ Layered architectures (Kiến trúc lớp) 24 1. Kiến trúc suy diễn „Dựa trên symbolic AI „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 525 Kiến trúc suy diễn Symbolic description of World „ Mục đích cần đạt tới „ Tập miêu tả hành động Î Tìm một chuỗi actions để đạt tới mục đích. „ Sử dụng thuật toán đơn giản „ Tạo kế hoạch không hiểu quả 26 Kiến trúc suy diễn 27 Kiến trúc (BDI) Belief-Desire-Intention „ 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 mà 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ó (committed desires) 28 BDI Architecture [Brenner et al, simplified; origin Rao and Georgeff] 5 • 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 interaction knowledge base BDI reasoner plan, schedule, execute actions perception AGENT 29 Các thành phần của agent BDI w Tập các niềm tin hiện tại (belief): biểu diễn tập các thông tin mà agent biết được về môi trường hiện tại của nó. w Hàm thu nhận tri thức từ môi trường (belief revision function) thu nhận thông tin mới, cùng với niềm tin đã có tạo ra những hiểu biết mới về môi trường w Hàm sinh các lựa chọn (option generation function): đưa ra các lựa chọn có thể có đối với agent (desire) dựa trên hiểu biết đang có về môi trường và mong muốn của nó. 30 w Các tuỳ chọn hiện tại (set of current options) biểu diễn tập các hành động mà agent có thể thực hiện. w Hàm lọc (filter function): biểu diễn cho quá trình cân nhắc của agent để chọn ra mong muốn dựa trên những điều kiện đang có, đang biết. w Tập các mong muốn (intention): biểu diễn mong muốn hiện tại của agent. w Hàm chọn hành động để thực hiện (action selection function): xác định hành động sẽ được thực hiện. 631 Những hạn chế của kiến trúc suy diễn „ Performance problems „ 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 đượ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 ích. „ Những kết quả sau cùng có thể là vô dụng „ Does not scale to real-world scenarios 32 2. Kiến trúc phản xạ „ 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 „ No central symbolic representation of world „ Không suy luận phức tạp „ 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 33 Kiến trúc phản xạ Brooks: „ Những kiến trúc thông minh có thể đượ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 reasoning (AI) mechanisms „ Tính thông minh là thuộc tình nổi bật trong hệ thống phức tạp Î Effect of combined components > effect of each component times number of components „ ”Real” intelligence is situated in the real world, not in disembodied systems such as theorem provers or expert systems „ Behavior thông minh là kết quả của việc tương tác với môi trường 34 Sơ đồ kiến trúc 35 Đặc thù của agent phản xạ „ Tính phản xạ là một behavior based model of activity ÍÎ symbol manipulation model used in planning Các thành phần của Perception: 1. Ngữ nghĩa học của đầu vào agent 2. Tập kiến thức cơ sở. 3. A specification of state transitions „ Actions được tạo ra bởi ngữ nghĩa của đầu ra agent (reaction) „ Tất cả symbolic manipulation được thực hiện trong thời gian dịch 36 Ví dụ „ Bộ tản nhiệt đơn giản là agent phản xạ: „ S = {tooCold, okay} „ A = {heatingOn, heatingOff } „ action(okay) = heatingOff „ action(tooCold) = heatingOn 737 Ví dụ agent phản xạ Robot’s objective: khám phá các hành tinh (ví dụ. Mars), and more concretely, sưu tầm những mẫu vật của 1 loại đá đặc biệt 1. Nếu nhận ra vật cản thì đổi hướng 2. Nếu đang cầm mẫu vật và ở tại căn cứ thì sẽ nhả vật mẫu 3. Nếu đang cầm mẫu vật và chưa ở tại căn cứ thì đi về phía căn cứ 4. Nếu phát hiện ra mẫu vật thì cầm nó lên 5. If true then move randomly 38 Ư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 39 Các vấn đề của agent phản xạ – một lượng lớn thông tin cố định cần cho agent – việc học? – có đặc thù là thủ công (handcraffed) – Sự phát triển mất rất nhiều thời gian – không thể xây dựng một hệ thống lớn? – chỉ được sử dụng cho những mục đích ban đầu? 40 Nhược điểm w 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. w 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. 41 3.Kiến trúc lai - Hybrid • Kết hợp tính phản xạ và tính suy diễn •deliberative component: Subsystems tạo ra những kế hoạnh và quyết định sử dụng symbolic reasoning •reactive component: Subsystems phản ứng lại sự kiện nhanh chóng mà không cần những reasoning phức tạp •Thành phần phản xạ có quyền ưu tiên hơn thành phần không phản xạ 42 Mô hình Hybrid 843 Kiến trúc lớp ‰Phân lớp theo chiều ngang ‰Phân lớp theo chiều dọc ‰1 chiều ‰2 chiều 44 3.1Phân lớp theo chiều ngang (horizontal layering) „ trong kiến trúc này tất cả các thành phần trên các lớp đều tiếp xúc trực tiếp tới đầu vào và đầu ra „ mỗi thành phần trên một lớp có thể coi là một agent. 45 Ưu nhược điểm „ Đơn giản. Nếu ta cần 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ự trành giành trong việc ra quyết định, để đảm bảo sự tương thính ta thường đưa vào một hàm điều khiển trung tâm (mediator) để quyết định xem lớp nào đang điều khiển hoạt động của agent. „ Giả sử trong mô hình của ta có n lớp và mỗi lớp có thể thực hiện m action khác nhau vậy có nghĩa là có thể có đến mn khả năng tương tác lẫn nhau, „ theo quan điểm thiết kế thì đây là một vấn đề khó và khi hoạt động có thể gây ra hiện tượng thắt cổ chai (bottleneck) trong quá trình ra quyết định 46 3.2 Phân lớp theo chiều dọc (vertical layering) „ Kiến trúc chỉ có hai thành phần tiếp xúc với đầu vào và đầu ra, ta có thể coi như là một agent „ Đơn giản hơn rất nhiều so với phân lớp theo chiều ngang. „ Phân làm 2 loại: „ Một chiều: Luồng điều khiển lần lượt đi qua từng lớp cho tới khi tới lớp cuối cùng sẽ tạo ra hành động cần thực hiện. „ Hai chiều: Thông tin được đi theo một chiều (lên) và điều khiển được đi theo chiều khác (xuống). 47 Ưu /nhược điểm „ Sự phức tạp trong tương tác giữa các lớp đã được giảm „ Luồng điều khiển phải đi qua toàn bộ các lớp vì thế nếu một lớp nào đó hoạt động không ổn định sẽ ảnh hưởng đến toàn bộ hệ thống 48 Phân lớp „ Lớp phản xạ thực thi như là một tập quy tắc hành động tuỳ thuộc vào trạng thái, a la subsumption architecture. „ Lớp planning tạo ra những kế hoạch và lựa chọn actions để thực thi nhằm đặt tới mục đích của agent „ Lớp modelling chứa những mẫu nhận biết về các agent khác trong môi trường. „ Giữa ba lớp này có sự liên lạc với nhau và được gói trọn vào một framework điều khiển, cái sử dụng những quy luật điều khiển. 949 Kiến trúc lớp Control unit & knowledge base • Các lớp: - Thấp: phản xạ, cao: suy luận, cao nhất: đa agent communication cooperative planning layer sensors actuators local planning layer behaviour-based layer social model mental model world model knowledge base control unit A G EN T 50 III. Chọn một kiến trúc Agent “Agent của tôi lưu trữ thông tin về môi trường. Dựa trên những hiểu biết đó nó tạo ra reasoning và planning.” “Agent của tôi quan sát môi trường. Nó nhận ra những thay đổi của môi trường, cái mà sẽ bắt đầu các hành vi của nó.” Agent suy diễn Agent lai agent phản xạ both 51 Exercise! Thảo luận trong vài phút Kiến trúc bên trong nào là tôt nhất cho Peer-to-peer project? Deliberative ... Or ... Reactive? 52 Exercise! Thảo luận trong vài phút: Kiến trúc bên trong nào là tôt nhất cho Weather project? Deliberative ... Or ... Reactive?