Bài giảng Hệ đa Agent-Cộng đồng Agent (MAS-Multi Agent System)

Nội dung text: Bài giảng Hệ đa Agent-Cộng đồng Agent (MAS-Multi Agent System)

1. I.Khái niệm - MAS Multi-Agent System(MAS) 1.Mục đích Hệ đa Agent-Cộng đồng Agent „ Có khả năng giải quyết các vấn đề lớn, ngoài khả năng của agent đơn lẻ (ví dụ do hạn chế tài nguyên). „ Cho phép tương tác giữa các hệ có sẵn, ví dụ hệ chuyên •Khái niệm Mas gia, hệ trợ giúp quyết định, các giao thức truyền thông sẵn có.v.v. •Hoạt động các Agent „ Tăng tính mở rộng (scalability) – mô hình tổ chức của •Coordination các agent có thể thay đổi mềm dẻo theo sự biến động •Cooperation của môi trường. „ Cho phép giải quyết các bài toán có tính phân tán, bài •Negotiation toán: thông tin và tri thức có nguồn gốc phân tán •Learning 2 Multi-agent systems (MAS) Môi trường đa agent „ Một hệ thống đa Agent được sử dụng để mô tả các 1. Cơ sở hạ tầng cho việc truyền thông cùng với Agent có khả năng tương tác với nhau (trợ giúp hoặc các giao thức tương tác giữa các agent trong đối kháng). môi trường. „ Các tương tác trợ giúp được hiểu là sự hợp tác(co- 2. Là môi trường mở và không bị tập trung hoá. operation), cộng tác(colaboration) 3. Có các agent có thể hoạt động một cách tự „ tương tác cạnh tranh - competitive settings thường chủ, phân tán và tương tác được với các agent dùng để mô tả trong các hệ thống xảy ra các tương tác khác. đối kháng giữa các Agent trong MAS) . 3 4 4.Formal Definitions and Properties Agent in a MAS (cont.) „ Định nghĩa: một agent Ag trong MAS là một Agent „ Dat: bao gồm. được mô tả „ Data Own: tập hợp các vùng dữ liệu riêng của „ - Ag(Sit,Act,Dat) với các cấu trúc mở rộng sau đây. Agent Ag „ - Act = ActOwn * ActCo „ DatKS: tập các dữ liệu đáng tin cậy về các Agent „ - ActOwn: các hành động của riêng Agent. khác.( Sure Knowledge) „ - ActCo: hành động dùng liên lạc và hợp tác. „ DatKA: tập các giả thiết về Agents khác „ -Một phần tử s Sit có một môi trường Env(s) và một (Assumtion Knowledge) vừa thêm các khái niệm phần cộng tác – parner part Part(s). mới và các khái niệm cũ vẫn còn hợp lệ. 5 6 1
2. Multi-Agent System II. Các mô hình MAS „ Object Manager Group (OMG) „ Một hệ thống đa Agent Mult (is a 5- Tuple) „ www.omg.org „ Mult = (Sit, Ag, Mact, α, MultL) „ Sankar Virdbagriswaran, Damian Osisek, Pat O’Connor, „ Sit: là tập các trạn thái. Standardizing Agent Technology, ACM StandardView Vol.3, „ Ag: tập các Agent ( trong một MAS) No.3, September 1995 „ Foundation for Physical Agents (FIPA) „ Mact: tập các hoạt động cơ bản có thể được thực hiện trong Mult. „ www.fipa.org „ www.fipa.org/specs/fipa00001/fipa00001.html „ α: Mact → Ag gán mỗi hành động của Mact cho Agent thực hiện nó. „ Knowledge-able Agent-oriented System (KAoS) „ „ MultL: là ngôn ngữ hành động của Agent. „ General Magic group „ seems to be out of date 7 8 OMG’s - Model FIPA’s – Mô hình „ Dựa trên tập các Agents và các thành phần tạo „ Kết hợp các Agent và các nhom trung gian voi sự hợp tác sử dụng các mẫu và chiến lược chung nên hệ Agent gồm: „ - Agent được đặc tả bởi: khả năng, kiểu tương tác và „ Agent Platform (AP) tính lưu động. „ Directory Facilitator (DF) „ Các trung gian hỗ trợ: „ Agent Management System (AMS) „ Các hoạt động đồng thời của các Agent. „ Agent Communication Channel (ACC) „ Bảo mật „ Agent Communication Language (ACL) „ Agent di động „ . 9 10 Mô hình KAoS Mô hình General Magic „ Mô tả theo kiến trúc mở và phân tán của „ Là mô hình ứng dụng Agent thương mại trong Agent phần mềm. thương mại điện tử. „ Mô hình Định nghĩa đa dạng cách thực hiện „ Xem xét MAS ở góc độ Chợ điện tử. (electronic Agent marketplace) „ Chợ điện tử được mô hình hoá thành một mạng các „ Sử dụng kiểu đàm thoại để hình thành liên lạc máy tính có hỗ trợ một tập các địa điểm có các dịch giữa các Agent. vụ phục vụ cho Agent di động. „ Các Agent di động : có thể di chuyển, gặp gỡ các Agent khác, tạo kết nối với các địa điểm đó. Và chúng có quyền riêng. 11 12 2
3. Các hoạt động cơ bản của hệ đa tác tử III. COOPERATION-Hợp tác „ Các hoạ động cơ bản: •Mục đích kết hợp của con người „ Điều phối Phối hợp, COORDINATION, „ Hợp tác, COOPERATION, •Các agent làm việc cùng nhau để đạt được kết quả tổng „ Đàm phán NEGOTIATION hợp. Để có thể kết hợp được thì các Agent phải được tổ „ Lập kế hoạch -PLANNING chức, xắp xếp organized. „ Các hoạ động cơ bản đó là biểu hiện của việc nhóm, kết nối các hoạt động của Agent. Tạo cơ chế cho hoạt động Definition: Organization „ Lập kế hoạch: là các hoạt động và mong muốn riêng của Agent, An organization consists of nhưng trong một nhóm chung kế hoạch thường thường có liên quan tới các agent và các agent phải đóng góp và chia sẻ để cùng •a group Ags of agents, đạt được mục tiêu chung. •a communication structure Com, and •an order/report structure Rep. Multi-Agent Systems 13 Cooperative Problem Solving Cooperation Concepts Định nghĩa: Cooperative Problem Solving „ Tổ chức sử dụng một hay vài khái niệm Các bước sau cần phải được thực hiện trong mỗi tổ cooperation để giải bài toán kết hợp chức để giải bài toán kết hợp „ Ví dụ:Kết hợp bằng sử dụng ( lựa chọn) các a). Định nghĩa, tạo và phân phối nhiệm vụ thông tin có sẵn: b). Thực hiện công việc bằng các Agent đã được phân „ Đàm phán ( negotiation) công. „ Quan hệ chủ/tớ ( Master/Slave relationship) c) Tổng hợp các kết quả nhận được từ a) đến c), được lặp đi lặp lại cho đến khi giải quyết thành công bài „ Biểu quyết ( Voting) toán. „ Đấu giá ( auctions) 15 16 Example: The TECHS approach for cooperative search (bài tập| 1. Advantages of Cooperation „ Denzinger and Fuchs (1999) „ Hoàn thành công việc nhanh hơn thông qua „ Cài đặt: Bài toán tìm kiếm sử dụng Agent với chia sẻ khả năng các phương thức khác nhau. Các Agent sẽ hợp „ Bằng việc chia sẻ tài nguyên sẽ thực hiện tác để giải bài toán nhanh chóng hơn được các công việc mà nếu không phối hợp „ Các tiếp cận chung: Các agent sẽ trao đôỉ dữ thì không thể làm được liệu định kỳ được đưa đến bằng cách gửi và „ Tạo khả năng bổ sung cho nhau nhận các chung nhan „ Tránh được các tác động bất lợi 17 18 3
4. 2. Modes of Cooperation 3. Degrees of Cooperation „ Tình cờ - accidental: Một bên không có chủ „ Fully cooperative (benevolent) Hợp tác hoàn ý, một bên thì có chủ ý giúp đỡ toàn ( rộng rãi): các agent luôn cố gắng giúp đỡ các Agent khác cần sự giúp đỡ. „ Hợp tác qua lại - mutual cooperation: hai hay nhiều Agent có ý định hợp tác „ Đối kháng (antagonistic): Agent không hợp tác với Agent khác và có thể thậm chí ngăn cản mục đích của nhau. „ Partly cooperative Hợp tác một phần: các agent thỉnh thoảng sẽ giúp đỡ các Agent khác Multi-Agent Systems 19 20 COORDINATION trên Agents III. Coordination - Điều phối trong MAS ƒ Coordination là một hành vi của hệ thống đa agent biểu hiện cho một số hoạt động trong môi trường •Điều phối Coordination: là một cơ chế nhằm đảm dùng chung. bảo các hoạt động của agent tuân theo một mối quan ƒ Mức độ phối hợp được thể hiện trong phạm vi hoạt hệ mong muốn nào đó ( tuần tự, bổ xung cho nhau động của các agent trong đótránh thực hiện các hoạt ) động không cần thiết: •Điều khiển-Control: là mở rộng của điền phối mà ở • tranh giành tài nguyên của hệ thống đó các agent nhận thông tin phải thi hành • tránh livelock • deadlock • đảm bảo khả năng an toàn cho hệ thống Multi-Agent Systems 22 3. Cơ chế tiến trình điều phối 2.Mục đích Processes Mechanism „ Phụ thuộc vào các hoạt động của Agent. „ Mutual Adjustment (điều chỉnh qua lại) „ Quản lý các ràng buộc toàn cục „ Direct Supervision - Giám sát trưc tiếp „ : ví dụ : thời gian, tiền bạc, tài nguyên tính toán. „ Standardization -Chuẩn hoá „ Khi không có cá nhân nào có đủ khả năng và tiềm lực để giải quyết toàn bộ vấn đề một „ mediated coordination - phối hợp gián tiếp mình. „ reactive coordination - phối hợp phản xạ 23 24 4
5. Direct supervision Mutual adjustment Giám sát trực tiếp (điều chỉnh qua lại) • Các agent chia sẻ tài nguyên và thông tin để đạt „ Một Agent có một mức độ điều khiển hơn các được kết quả chung, điều chỉnh lại các hành vi Agent khác và có thể điều khiển thông tin, tài của chúng theo các hành vi của các Agen khác. nguyên và các hành vi. • Không có Agent nào có quyền điều khiển ưu tiên „ Thường xuyên được thiết lập thông qua điều và quyết định được kết hợp. chỉnh qua lại( ví dụ: sau khi chấp nhận thuê hoặc ký hợp đồng) •Sự phối hợp một nhóm ngang hàng ( markets thường là điều chỉnh qua lại.) Multi-Agent Systems 25 26 Điều phối gián tiếp Điều phốitheo chuẩn Mediated coordination „ Các thủ tục tiêu chuẩn được thiết lập cho agent Nhà trung gian-mediator như một người xúc tuân theo. tiến-facilitator ( tìm và định hướng thông tin)* „ Trong điều chỉnh qua lại, được thực hiện bởi Một người môi giới là trung gian và cố vấn các agent phía nhận. trong việc đàm phán trên các loại tài nguyên). „ Trong giám sát trực tiếp , được thiết lập thông qua ( yêu cầu) đề nghị bắt buộc Nhà Trung gian tạo điều kiện hoặc người môi giới điều chỉnh qua lại giữa các Agents và cũng có thể sử dụng giám sát trực tiếp. Multi-Agent Systems 27 Multi-Agent Systems 28 Điều phối dựa vào hành vi phản xạ Coordinated Systems Mechanisms Coordination by reactive behaviour Cơ chế hệ thống điều phối „ Các Agent phản xạ lại các tác nhân kích thích „ Hoạt động điều chỉnh qua lại thông qua tương tác (“situation”) bằng các hành vi cụ thể (“Action”) peer to peer, „ giám sát trực tiếp sử dụng cách tiếp cận “Chủ -Tớ “ „ Với sự lựa chọn thích hợp hoặc trích rút ra, các „ Một Mediator facilitates hoặc người môi giới điều hành vi trên sẽ được nhóm và phân bổ cho việc chỉnh qua lại giữa các Agent thực thi một số mức độ điều phối giám sát „ Điều phối phản xạ phụ thuộc vào sự kết hợp thích „ hành vi phối hợp này khi xuất hiện sẽ đóng góp hợp của các kiểu mẫu hành vi kích thích.( stimuli – cho mục tiêu của từng cá nhân hay mục đích behaviour pattern) chung của cả hệ thống „ Các nhóm phối hợp và cấu trúc có tổ chức 29 Multi-Agent Systems 30 5
6. Mức độ điều khiển trong Cơ chế Phân nhóm phối hợp –I „ nhóm lớn có thể được phân chia thành các nhóm con nếu như hầu „ Điều khiển tập trung : hết các thông tin trao đổi đều có thể xuất hiện trong các nhóm nhỏ „ Các thủ tục gọi, chủ/ tớ(tập trung, little adaption) này. „ Đồng bộ và liên lạc rõ ràng: „ Sự phối hợp hiệu quả các nhóm con yêu cầu mỗi nhóm phải có „ Semafor, monitor(ở mức hệ điều hành), bán tập coordinator / supervisor/ mediator, những người sẽ làm việc với trung (các agent/ tiến trình tranh chấp tài nguyên). nhau trong một hay nhiều nhóm phối hợp. „ Chia sẻ các dũ liệu trừu tượng ( Shared – Data „ Mỗi nhóm hợp tác cũng như nhóm con ở cấp độ thấp hơn có thể Abstraction) hợp tác ngay trong bản thân nó bởi mutual adjustment, or direct „ Các ngôn ngữ thông dụng, các ngôn ngữ lập trình supervision, mediation, or reactive behaviour. hiện tại „ Nếu chỉ sử dụng cơ chế giám sát trực tiếp thì kết quả thu được là cây phân cấp của các nhóm Multi-Agent Systems 31 32 Mức độ điều khiển trong phối hợp –II 5.Mô hình Coordination „ Functionally Accurate Cooperative Approach: „ Coordination: Các agent suy luận về các hành vi của „ Điều khiển không đồng bộ , adaptive thay đổi trong ngữ chúng và đoán trước các hành vi của các Agent khác nhằm nghĩa và những thứ không chắc chắn ( các thông tin mập đảm bảo cho các hoạt động chung trong số các hoạt động của mờ) chúng diễn ra tốt đẹp „ Điều khiển suy luận: „ Coordination = „ Agent sử dụng cơ sở tri thức của nó và các Agent khác để „ Coordination = xây dựng / sửa chữa bộ “khung” phối hợp „ Commitments Sự uỷ thác+ „ Tương tác suy luận: „ Conventions + Sự thoả thuận + „ Các agent suy luận trong suốt thời gian tương tác ( vd: „ Social Conventions + thoả thuận cộng đồng+ giải thuật di truyền ),không chia sẻ ngữ nghĩa và hoàn „ Local Reasoning :Suy luận cục bộ toàn Adaptive. 33 34 Commitment Joint Goals Uỷ nhiệm Kết hợp mục đích „ Convention(thoả hiệp) „ Kết hợp mục đích dựa cơ sở của việc kết hợp hành động „ Bằng cách quan sát sự uỷ nhiệm khi thay đổi hoàn „ Kết hợp hành động: cảnh. „ Một dạng phức tạp của việc hợp tác trong một nhóm „ Kiểu uỷ nhiệm: agents quyết định theo đuôi mục tiêu chung trên cơ sở một kiểu phối hợp nào đó. „ Quan hệ Goal- subgoal: „ Đặc tính của kết hợp hành động: • Hierarchical, AND/OR goals „ Chịu trách nhiệm qua lại Vd: theo luật „ Quan hệ Goal-Dependency : „ Kết hợp uỷ nhiệm\ Lôi kéo theo cùng hướng • Phụ thuộc mạnh/ yếu „ Hỗ trợ lẫn nhau \ ví dụ Bảo vệ Ủng hộ lẫn nhau • Uni/Bi-directional 35 36 6
7. Social Convention Types 5.3 Conventions/ Các loại thoả hiệp „ Commitment có thể thay đổi theo thời gian: do sự thay đổi „ Quan hệ Goal-Subgoal: môi trường. „ Cần thoả hiệp để mô tả khi commitment thay đổi: „ tin rằng mỗi agent sẽ thực hiện tốt mục đích ( nhỏ) của „ When to keep commitment (giữ lại) chúng „ When to revise commitment (sửa chữa) „ Quan hệ Goal-Dependency: „ When to remove commitment (loại bỏ) Ví dụ về thoả hiệp: „ quan sát sự thay đổi của commitment để quyết định hành „ Ví dụ Lý do của việc định lại commitment: động „ commitment đã hoàn thành „ không thực hiện được „ Kết hợp Action Convention, Kết hợp Commitments „ mục đích không còn tồn tại and Kết hợp Goals: „ Các hành động: „ R1: „ cho các cá nhân có thể giả thiết về hoạt động riêng của các • If Commitment đã hoàn thành OR • Commitment không thực hiện được OR Agent khác • Động cơ Commitment không còn • Huỷ Commitment 37 38 6.Common Coordination Techniques 7.Ingredients in Good Kỹ thuật điều phối Coordination „ Một kết cấu có tổ chức: ( long-term) (Organizational „ Phải có các cấu trúc làm agent có thể tương Structures ): Một kiểu quan hệ về thông tin và điều tác theo các cách có thể đoán trước khiển giữa các cá nhân „ -Phải mềm dẻo, cho phép nhìn từng phần và „ Meta-Level Information Exchange – medium term :Các Agent thông tin cho nhau về độ ưu tiên và tiêu mờ ( cho mỗi Agent) điểm hiện tại của chúng. „ - Agent phải có sự hiểu biết và khả năng suy „ Đặt kế hoạch hệ đa agent: (sort term) : Chỉ ra một kế luận để sử dụng các cấu trúc và sự mềm dẻo hoạch trong đó các hoạt động và tương tác trong đó. tương lai nhằm đạt được mục tiêu cụ thể. 39 40 7