Kĩ thuật lập trình - Bài 4: Multi - Agent behaviour hành vi của hệ đa agent)

1Bài 4: Multi-Agent behaviour Hành vi của hệ đa Agent) „Negotiation(Đàm phán) „Learning(Học tập) Negotiation /Đàm phán 1. Định nghĩa: Là một quá trình tăng cường tính thống nhất(giảm mâu thuẫn không chác chắn) dựa trên những quan điểm, kế hoạch chung thông qua việc trao đổi có hệ thống những tri thức liên quan(Durfee, 1989) Negotiation: Agent liên lạc với những agent khác và xác định nhu cầu về tài nguyên và dịch vụ (thường dưới những điều kiện đặc biệt); agent khác xác định cái gì có thể được cung cấp dưới những điều kiện nào; 23 August 2008 Multi-Agent Systems 3 2. Loại hình đàm phán • Bargaining: Mặc cả, thương lượng ( hứa hẹn hay trao đổi) • Bidding: đặt giá (đưa ra một dịch vụ, hay hàng hoá với mức giá cụ thể) • Contracting: ký kết (cam kết một dịch vụ, hay hàng hoá với mức giá cụ thể) hay chỉ 1 phần of the negotiation process./ký kết • Ưu tiên đàm phán: Một agent cần xác định nguồn tài nguyên, dịch vụ cần thiết (nhưng không cung cấp được )và sau đó nó cần nhận diện agent mà nó tin tưởng có thể (believes potentially could.) 23 August 2008 Multi-Agent Systems 4 3. Giao thức Đàm phán Negotiation protocols • Negotiation protocols: thủ tục có cấu trúc cho 1 hay nhiều bước của tiến trình đàm phán •Khởi tạo agent/s chấp nhận những điều kiện; •supplying agent/s cam kết cung cấp tài nguyên hoặc dịch vụ • đàm phán single-stage , Khởi tạo agent tạo các yêu cầu và đưa ra câu trả lời chấp nhận hay từ chối điều đó. • đàm phán multi-stage, Các agents lặp lại nhiều hơn một stage of offer/counter-offer. 4. Nguyên lý đàm phán wĐàm phán dựa trên 3 yếu tố wLanguage: Ngôn ngữ sử dụng bởi các agent tham gia thương lượng. wDecision: Phương thức, chiến lước mà các agent sử dụng để thương lượng ra quyết định. w Process: Tiến trình thực hiện đàm phán để ra quyết định của mỗi agent. 5.Tính chất của đàm phán w Efficiency: Các agent trong quá trình ra thương lượng ra quyết định không nên tốn quá nhiều thời gian. w Stability: Không nên thay đổi chiến lược đã định trước. w Simplicity: Cơ chế thương lượng không nên dùng các tính toán phức tạp. w Distribution: Không nên bắt một agent tính toán tập trung. w Symmetry (sự cân đối): không nên thiên vị một agent nào nếu không có một lý do hợp lý. 26. Ngôn ngữ Communication Understanding 1. Protocol (Giao thức) „ Nên sử dụng ngôn ngữ như thế nào? Ví dụ: „ Giao thức ngoại giao „ Giao thức truyền Hypertext „ TCP/IP 2. Ngữ nghĩa „ Ngữ nghĩa của ngôn ngữ phải chính xác „ Không nhập nhằng Language NEGOTIATION Sema ntics Protocols Object St ructure Primitives Initia tiato rs Reactors 3. Object Structure How the language is constructed, grammar, syntax etc. 4. Primitives Atoms of the language Based on speech-act theory Primitives Initiators: „ Propose,mục đích „ Arrange,tổ chức công việc „ Request (of resources)yêu cầu „ Inform cung cấp thông tin „ Query (for info) truy vấn „ Command mệnh lệnh „ Inspect kiểm tra REACTIVE BEHAVIOR •Answer •Refine •Modify •Change •Bid •Send •Value •Reply •Refuse •Explain •Initiators •REACTIVE BEHAVIOR •Completers Completers „ End conversation „ Confirm xác nhận „ Promise hứa hẹn „ Commit uỷ nhiệm „ Accept chấp nhận „ Reject từ chối „ Grant chuyển nhượng „ Agree đồng ý Language De cis ion Co m pl et er s Reactors Initiato rs Primitives Offers/tasks Plans Context Object Structure Action Sequences Protocols Modal Logic Effe ct Pre-conditions Semantic s Mat chi ng Preferences Strategies NEGOTIATION Gr am m ar Utility Ga me Th eo ry Decision M atrixes Op tim iza tio n Pr ob lem Non-Conflicting Plans Ma x. G ain Min. Risk Fair Solution (50-50) 7. DECISION Quyết định „ Cái gì nên được quyết định được làm hay không được làm trong một tình huống đàm phán. „ Utility „ Giá trị của mỗi thành phần khi tham gia „ ”What’s in it for me” .. So to say. „ Expressed as a mathematical function based on own agend and expectations about others. „ Matching – Phù hợp „ Matching of plans from various agents „ Non-Conflicting Plans • Try to benefit from the non-conflicting plans of players „ Preferences – Ưu tiên „ What is the users preference, interest in the outcome of the negotiation? „ Strategies – Chiến lược „ Which strategy or road-map for actions should be selected to obtain a high utility and fulfill preferences? 7.1. Utility – Trị giá „ Game Theory „ Basis in economics. „ Formal description of greediness of players „ Decision Matrix „ Lookup for values of next action „ Optimization Problem „ The essential problem is to maximize utility of the system or oneself. 37.2 Preferences „ Maximize Gain „ I want to maximise my personal gain (e.g. Money or points..) or the systems gain „ Fair Solution „ I want everybody to be treated fair and have a fair outcome „ -- no hard feelings.. „ Minimize Risk „ I’ll avoid risk and will try Strategies „ Concede Unilaterally(đơn phương thừa nhận) „ Get to a common agreement „ It may no benefit all, but its quick? „ Competetive ( Cạnh tranh) „ Sports-tradition „ Cooperative ( Hợp tác) „ We will try to get a best result „ Inaction( cù nhầy) „ Don’t do anything Language De cis ion Co m pl et er s Reactors Initiato rs Primitives Offers/tasks Plans Context Object Structure Action Sequences Protocols Modal Logic Effe ct Pre-conditions Semantic s Mat chi ng Preferences Strategies NEGOTIATION Gr am m ar Utility Ga me Th eo ry Decision M atrixes Op tim iza tio n Pr ob lem Non-Conflicting Plans Ma x. G ain Min. Risk Fair Solution (50-50) Co nc ed e Un ila te ra lly Comp etetive CooperativeInaction Process Language De cis ion Co m pl et er s Reactors Initiato rs Primitives Offers/tasks Plans Context Object Structure Action Sequences Protocols Modal Logic Effe ct Pre-conditions Semanti cs Co nfli ct Res olu tion Cyc le Negotiation Cycle Procedure Mat chi ng Preferences Strategies NEGOTIATION Gr am m ar Utility Ga me Th eo ry Decision M atrixes Op tim iza tio n Pr ob lem Non-Conflicting Plans Ma x. G ain Min. Risk Fair Solution (50-50) Co nc ed e Un ila te ra lly Comp etetive CooperativeInaction Br ea kin g B ehavior Total Work (TW) Li ve ne ss /F ai rn es s 9. PROCESS „ Procedure Thủ tục „High-level/ society view on the negotiation process) „ Behavior Hành vi „Behavior modelling ( mô hình hóa hành vi) 9.1 Procedure „ Negotiation Cycle „ Propose solutions to a certain conflict „ Criticial analysis of other solutions „ Update of solution space and preference list „ Conflict Resolution Cycle(Runs in parallel with negotiation cycle) „ Determine conflicts „ Select high-pri conflicts „ Plan conflict resolution 49.2 Behavior modelling „ Total Work (TW) The total work done in negotiation is less than or equal to the total work in a 1. Coordinated system 2. centralized on-line system – new tasks, sequentially 3. Centralized off-line system – all tasks known a priori ƒ Liveness/Fairness „ Investigate how fair a negotiation system is Over to you.. „What would be likely preferences for people participating in auctions? „What would be likely strategy for auctioneers? „ Is the auction negotiation system fair? V. Learning in MAS 1. What is learning? An AI definition: P. Langley: Elements of Machine Learning, Morgan Kaufmann, 1996: Learning is the improvement of performance in some environment through acquisition of knowledge resulting from experience in that environment. Jörg Denzinger definition „Learning encompasses all self modifications of a (combined) system that allow an improved future system behavior. Mục đích của việc học in MAS? „ Learning to achieve: „ Cooperation „ Organization „ Better competition „ Learning of and about agents: „ Để cải tiến hiệu năng „ Để đoán nhận được phản ứng của các Agent khác „ Learning and Cooperation „ Truyền thông là công cụ cho phép học „ Học cũng là công cụ giúp hạn chế hoặc tránh phải liên lạc với agent khác „ Để tạo ra một môi trương tốt hơn cho các Agent 2.Formal „ Với một agent chúng ta có thể có fag(s) tại thời điểm t1 ≠ fAg(s) tại thời điểm t2 „ For a not-learning agent Ag, its learning variant AgL and a sequence of situations s1,,si,..., we have there is an i such that „ Ag(sj) = AgL(sj) for j < i and „ Ag(si) ⎯ ≠ AgL(si) „ Suy đoán một agent học đang làm những gì là điều rất khó. 53.Mô hình basic learning model Langley (1996) Agents and the basic learning model 4. Các phương pháp học với Agent „ Distributed credit assignment: „ Reinforcement Learning „ Evolutionary approaches „ Genetic Algorithms / Genetic Programming „ Look at MAS as an evolving population: „ Swarm systems, Ant systems, etc. „ Classification methods „ Learning by heart and abstraction „ Layered learning „ ...(Mỗi giải thuật 1 bài tập) 4.1 Evolutionary learning of cooperative behavior: OLEMAS „ Denzinger and Fuchs (1996) „ OLEMAS: OffLine Evolution of Multi-Agent Systems „ Basic Problems tackled: „ How can we specify tasks on a high and abstract level and let the concrete problem solution be done by learning by the MAS? „ How can we use combined training of agents to have them show cooperative behavior without needing much communication but relying on instinctive reactive behavior? 4.2 Reinforcement learning for forming coalitions: „ the DFG algorithm Weiß (1995) „ DFG: Dissolution and Formation of Groups „ Basic Problems tackled: „ How can several agents learn what actions they can perform in parallel? „ How can several agents learn what sets of actions have to be executed sequentially? 4.1.1 Thuật toán di truyền „ Khái niệm: Sử dụng mô hình tiến hoá sinh học để cải tiến giải pháp giải quyết vấn đề. „ 1. Tạo ra một tập hợp các giải pháp (Không nhất thiết là rất tốt) giải quyết vấn đề(initial population) „ 2. Lặp lại cho đến khi điều kiện cuối cùng fulfilled: „ Generate out of actual population new solutions (using genetic operators), such that better solutions in the population are used with higher probability (quality fitness) „ Generate the next population out of the old and the new individuals 6VI. Những ứng dụng của MAS „ Internet/ Thương mại điện tử „ Giám sát các đối tượng / Distributed Sensing „ Các nhóm Robot làm việc với nhau „ Sản xuất „ Giao thông (mỗi lĩnh vực 1 bài tập) 1.MAS trong vận tải: MARS „ Kuhn et al. (1993); Fischer et al. (1994) „ MARS: Modeling Autonomous coopeRating Shipping companies „ Scenario: „ Một công ty vận tải sử dụng nguồn phương tiện vận tải(xe tải) có sẵn của công ty mình, trong thị trường cạnh tranh cần phải làm thế nào để chi phí vận chuyển càng rẻ càng tốt „ Công ty đó có thể chuyển đổi thứ tự các công việc nhằm tối ưu hoá nguồn xe tải của họ. 2. MAS cho việc quản lý không gian thông tin cá nhân: ILTIS() „ Lorenz (2001) „ ILTIS: Information Location and Tracking by Integrating Services „ Scenario: „ Một người có thể tự tạo cho họ một không gian thông tin cá nhân trên Internet với account của người đó. „ Các bản sao trang web cục bộ „ Những tru vấn có quy tắc tới các máy tìm kiếm 23 August 2008 Multi-Agent Systems 34 4 . Contract Net Protocol Giao thức ký kết „ Một agent có vai trò như nhà quản lý có nhiệm vụ phân tích nhiệm vụ cần giải quyết (bản hợp đồng) thành những phần nhỏ(subcontracts), và chúng sẽ được giải quyết bởi những agent ký kết tiềm năng. „ Với mỗi bản hợp đồng con, nhà quản lý sẽ gửi thông báo nhiệm vụ cần thực hiện lên mạng agents. „ Các Agents sẽ nhận thông báo và kiểm tra có phù hợp khả năng của mình không. „ Các Agents với nguồn tài nguyên, chuyên môn, kho thông tin riêng trả lời sự đặt giá tới nhà quản lý. „ Nhà quản lý đánh giá sự đặt giá này, và chuyển nhiệm vụ tới Agent thích hợp nhất, gọi là nhà đấu thầu „ Tóm lại, nhà quản lý và nhà đấu thầu trao đổi thông tin trong suốt quá trình đến hoàn thành nhiệm vụ” (Moulin and Chaib- Draa) 23 August 2008 Multi-Agent Systems 35 • Trong Contract Net, một người đấu thầu gửi các báo cáo về tình trạng, sau đó là báo cáo tổng kết (task completion) tới nhà quản lý. • Nhà quản lý có quyền dừng cuộc đấu thầu ngay lập tức. Agents Idle có thể truyền đi mệnh lệnh mang tính hiệu lực này. • Basic contract net mô hình không quan tâm đến tương tác qua lại (e.g. two agents each need all of an available resource; everal agents all need a resource or another agent’s help at or about the same time) 23 August 2008 Multi-Agent Systems 36 Possible approaches to interacting tasks 1.Agents negotiate directly on resolving problem. 2.A mediator coordinates the interaction to reduce or eliminate the conflict, or negotiates with agents on resolving it. „ Các Agent không chỉ lập kế hoạch làm thế nào để gải quyết nhiệm vụ, mục tiêu mà còn liên lạc với agent khác và đàm phán giải quyết mâu thuẫn, nhằm thay đổi kế hoạch cho thích hợp hơn.