Kĩ thuật lập trình - Multi - Agent system (mas)

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