Bài giảng Tác tử - Bài 4: Hành vi của hệ đa Agent

Nội dung text: Bài giảng Tác tử - Bài 4: Hành vi của hệ đa Agent

1. Bài 4: Multi-Agent behaviour Negotiation /Đàm phỏn Hành vi của hệ đa Agent) 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ế „Negotiation(Đàm phỏn) 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à „Learning(Học tập) 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; 3. Giao thức Đàm phỏn 2. Loại hỡnh đàm phỏn Negotiation protocols • Bargaining: Mặc cả, thương lượng ( hứa hẹn hay trao đổi) • Negotiation protocols: thủ tục cú cấu trỳc cho 1 hay • Bidding: đặt giỏ (đưa ra một dịch vụ, hay hàng hoỏ với mức nhiều bước của tiến trỡnh đàm phỏn giỏ cụ thể) •Khởitạo agent/s chấp nhận những điều kiện; • Contracting: ký kết(cam kết một dịch vụ, hay hàng hoỏ với •supplying agent/s cam kết cung cấp tài nguyờn hoặc dịch vụ mức giỏ cụ thể) hay chỉ 1 phần of the negotiation process./ký • đàm phỏn single-stage , Khởi tạo agent tạo cỏc yờu kết cầu và đưa ra cõu trả lời chấp nhận hay từ chối điều • Ư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 • đàm phỏn multi-stage, Cỏc agents lặp lại nhiều hơn potentially could.) một stage of offer/counter-offer. 23 August 2008 Multi-Agent Systems 3 23 August 2008 Multi-Agent Systems 4 4. Nguyờn lý đàm phỏn 5.Tớnh chất của đàm phỏn w Đàm phỏn dựa trờn 3 yếu tố 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 Language: Ngụn ngữ sử dụng bởi cỏc agent w Stability: Khụng nờn thay đổi chiến lược đó định trước. tham gia thương lượng. 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 Decision: Phương thức, chiến lước mà cỏc w Distribution: Khụng nờn bắt một agent tớnh toỏn tập agent sử dụng để thương lượng ra quyết định. trung. w Process: Tiến trỡnh thực hiện đàm phỏn để ra w Symmetry (sự cõn đối): khụng nờn thiờn vị mộtagent nào nếu khụng cú một lý do hợp lý. quyết định của mỗi agent. 1
2. •Initiators 6. Ngụn ngữ P Primitives roto ure •REACTIVE BEHAVIOR cols Struct Communication Object s •Completers ntic Understanding ema L Prim S a itiv n es rs iato g iat Init u a R eacto 1. Protocol (Giao thức) g rs Initiators: REACTIVE BEHAVIOR e „ Nờn sử dụng ngụn ngữ như „ Propose,mục đớch thế nào? •Answer „ Arrange,tổ chức cụng •Send Vớ dụ: NEGOTIATION việc •Refine „ Giao thức ngoại giao •Value „ Request (of resources)yờu „ Giao thức truyền Hypertext 3. Object Structure cầu •Modify •Reply „ TCP/IP How the language is constructed, „ Inform cung cấp thụng tin 2. Ngữ nghĩa grammar, syntax etc. •Change „ Query (for info) truy vấn •Refuse „ Ngữ nghĩa của ngụn ngữ phải 4. Primitives chớnh xỏc Atoms of the language „ Command mệnh lệnh •Bid •Explain „ Khụng nhập nhằng Based on speech-act theory „ Inspect kiểm tra O ff er es s/ Action Sequenc P ta Completers ro sk to s lans col P P s Object Structure re- C con s r on ditio antic a tex ns Sem m t L Pr m a im a i r t n ti ec Mo ve G ff d g s E al L og u rs ic itiato „ End conversation a In g R e e ac to s r r s te le p m o „ D Confirm xỏc nhận M e C a c t i y r s r i i o x o he NEGOTIATION e n T s e „ Promise hứa hẹn m a G on n U i „ Commit uỷ nhiệm o ti is ti li a ty c iz m e le D tim b p ro „ Accept chấp nhận O P ing S h P tr tc r at a e eg M f ie „ Reject từ chối e s r e N n o c n e - „ Grant chuyển nhượng C s P o l n k a f is n l R i n. s c Mi t in i a F n G a „ Agree đồng ý g . ir x a ( S M 5 o 0 - lu 5 0 ti ) o n 7. DECISION Quyết định 7.1. Utility – Trị giỏ „ 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 „ Game Theory đàm phỏn. „ „ Utility Basis in economics. „ Giỏ trị của mỗi thành phần khi tham gia „ Formal description of greediness of players „ ”What’s in it for me” So to say. „ Expressed as a mathematical function based on own agend and expectations about others. „ Decision Matrix „ Matching – Phự hợp „ Matching of plans from various agents „ Lookup for values of next action „ Non-Conflicting Plans • Try to benefit from the non-conflicting plans of players „ Optimization Problem „ Preferences – Ưu tiờn „ „ What is the users preference, interest in the outcome of the negotiation? The essential problem is to maximize utility of the system „ Strategies – Chiến lược or oneself. „ Which strategy or road-map for actions should be selected to obtain a high utility and fulfill preferences? 2
3. 7.2 Preferences Strategies „ Maximize Gain „ Concede Unilaterally(đơn phương thừa nhận) „ I want to maximise my personal gain (e.g. Money „ Get to a common agreement or points ) or the systems gain „ It may no benefit all, but its quick? „ Fair Solution „ Competetive ( Cạnh tranh) „ Sports-tradition „ I want everybody to be treated fair and have a fair outcome „ Cooperative ( Hợp tỏc) „ no hard feelings „ We will try to get a best result „ Inaction( cự nhầy) „ Minimize Risk „ Don’t do anything „ I’ll avoid risk and will try O ffe rs n Sequences /t Actio Pro as to ks lans col P P s Object Structure O re- C ffe con r on rs di tics a te equences /t tio man xt Action S Pr as ns Se m ot k L oco s Plans Pr m ls a i a P Object Structure m r re C t n it -co r on c Mo iv G ndi tics a te fe e tio man xt f d g s ns Se m E al L L P m og u tors a ri a ic tia m r a Ini n it ct iv G e Mo e g ff d g s E al L Re o u rs e gic tiato ac a Ini t s o g r rs R e e e t ac e to l s r r s p te m le D o p Mat eci C m t D o y c r s r li M e C o f ixe io e EGOTIATION n a c h N n io t i y n o t r s r T u i i o s e C l x o he NEGOTIATION o e n T m s e s e a e l m G R c a Pro y G n cess Procedure C n io N io n U n U o t s e o t s i i i g ti ili i t li a ty c a ty c B z m z m e C o i e e i l le y t im D y m e t b l i b D ly i p o l t l c a r a p o h O P r r a l t e O P r e i g t e a o a in P S l g t h t i n a v n c r i S l t r at n h P i a e e U t i c r n M gi t re a o f e e a te U e s d g r e M f i e r e c e e n s d N n o r e ive c o c C tet e pe n n e om - C N n o C s tive T o o c C te ot P Co pe al l n k op n e om W a f is er C o n l R at - rk i n. I ive C s ( s c Mi n s TW t in a P o ) i a F c g C s n a l n oo G ti a sk n p e g . ir o f i i er x n l . R k at n a ( S n i in I ive r M 5 o s c M a n i 0 t in e a a - lu i F r 5 n a a c F 0 ti G B ti / ) o g . ir o s n x a ( S n s M 5 o e 0 n - lu 5 e 0 ti v ) o i n L 9. PROCESS 9.1 Procedure „ Procedure Thủ tục „ Negotiation Cycle „ Propose solutions to a certain conflict „ High-level/ society view on the negotiation „ Criticial analysis of other solutions process) „ Update of solution space and preference list „ Behavior Hành vi „ Conflict Resolution Cycle(Runs in parallel with negotiation cycle) „ Behavior modelling ( mụ hỡnh húa hành vi) „ Determine conflicts „ Select high-pri conflicts „ Plan conflict resolution 3
4. 9.2 Behavior modelling Over to you „ Total Work (TW) The total work done in negotiation „ What would be likely preferences for is less than or equal to the total work in a people participating in auctions? 1. Coordinated system „ 2. centralized on-line system – new tasks, sequentially What would be likely strategy for 3. Centralized off-line system – all tasks known a priori auctioneers? ƒ Liveness/Fairness „ Is the auction negotiation system „ Investigate how fair a negotiation system is fair? V. Learning in MAS Jửrg Denzinger definition „ Learning encompasses all self 1. What is learning? modifications of a (combined) An AI definition: system that allow an improved future P. Langley: Elements of Machine Learning, Morgan system behavior. Kaufmann, 1996: Learning is the improvement of performance in some environment through acquisition of knowledge resulting from experience in that environment. Mục đớch của việc học in MAS? 2.Formal „ Learning to achieve: „ Với một agent chỳng ta cú thể cú fag(s) tại thời „ Cooperation điểmt1 ≠ fAg(s) tại thời điểmt2 „ Organization „ For a not-learning agent Ag, its learning variant „ Better competition AgL and a sequence of situations s1, ,si, , we have there is an i such that „ Learning of and about agents: „ „ Để cải tiến hiệu năng Ag(sj) = AgL(sj) for j < i and „ Để đoỏn nhận được phản ứng của cỏc Agent khỏc „ Ag(si) ⎯ ≠ AgL(si) „ Learning and Cooperation „ Truyền thụng là cụng cụ cho phộp học „ Suy đoỏn một agent học đang làm những gỡ là „ Học cũng là cụng cụ giỳp hạn chế hoặc trỏnh phải liờn điều rất khú. lạc với agent khỏc „ Để tạo ra một mụi trương tốt hơn cho cỏc Agent 4
5. 3.Mụ hỡnh Agents and the basic learning basic learning model Langley (1996) model 4.1 Evolutionary learning of 4. Cỏc phương phỏp học với Agent cooperative behavior: OLEMAS „ Distributed credit assignment: „ Denzinger and Fuchs (1996) „ Reinforcement Learning „ OLEMAS: OffLine Evolution of Multi-Agent „ Evolutionary approaches Systems „ Genetic Algorithms / Genetic Programming „ Basic Problems tackled: „ Look at MAS as an evolving population: „ How can we specify tasks on a high and abstract level and let the concrete problem solution be „ Swarm systems, Ant systems, etc. done by learning by the MAS? „ Classification methods „ How can we use combined training of agents to „ Learning by heart and abstraction have them show cooperative behavior without „ Layered learning needing much communication but relying on „ (Mỗi giải thuật1bài tập) instinctive reactive behavior? 4.2 Reinforcement learning for forming coalitions: 4.1.1 Thuật toỏn di truyền „ the DFG algorithm Weiò (1995) „ 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 đề. „ DFG: Dissolution and Formation of Groups „ 1. Tạo ra một tập hợp cỏc giải phỏp (Khụng nhất thiết là „ Basic Problems tackled: 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: „ How can several agents learn what actions „ Generate out of actual population new solutions (using they can perform in parallel? genetic operators), such that better solutions in the „ How can several agents learn what sets of population are used with higher probability (quality actions have to be executed sequentially? fitness) „ Generate the next population out of the old and the new individuals 5
6. VI. Những ứng dụng củaMAS 1.MAS trong vận tải: MARS „ Internet/ Thương mại điện tử „ Kuhn et al. (1993); Fischer et al. (1994) „ MARS: Modeling Autonomous coopeRating Shipping „ Giỏm sỏt cỏc đối tượng / Distributed Sensing companies „ Cỏc nhúm Robot làm việc với nhau „ Scenario: „ Sản xuất „ 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 „ Giao thụng cạnh tranh cần phải làm thế nào để chi phớ vận chuyển (mỗi lĩnh vực 1 bài tập) 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 4 . Contract Net Protocol gian thụng tin cỏ nhõn: ILTIS() Giao thức ký kết „ Lorenz (2001) „ 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 „ ILTIS: Information Location and Tracking by nhỏ(subcontracts), và chỳng sẽ được giải quyết bởi những Integrating Services agent ký kết tiềm năng. „ Scenario: „ Vớimỗ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. „ Một người cú thể tự tạo cho họ một khụng gian „ Cỏc Agents sẽ nhận thụng bỏo và kiểm tra cú phự hợp khả thụng tin cỏ nhõn trờn Internet với account của năng của mỡnh khụng. người đú. „ Cỏc Agents với nguồn tài nguyờn, chuyờn mụn, kho thụng tin „ Cỏc bản sao trang web cục bộ riờng trả lời sự đặt giỏ tới nhà quản lý. „ Những tru vấn cú quy tắc tới cỏc mỏy tỡm kiếm „ 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 34 Possible approaches to interacting tasks • 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 1.Agents negotiate directly on resolving lý. problem. • Nhà quản lý cú quyền dừng cuộc đấu thầu ngay lập tức. Agents 2.A mediator coordinates the interaction to reduce Idle cú thể truyền đi mệnh lệnh mang tớnh hiệu lực này. or eliminate the conflict, or negotiates with agents on resolving it. • 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 „ Cỏc Agent khụng chỉ lập kế hoạch làm thế nào để agents all need a resource or another agent’s help at or about the gải quyết nhiệm vụ,mục tiờu mà cũn liờn lạc với same time) agent khỏc và đàm phỏn giải quyết mõu thuẫn, nhằmthay đổi kế hoạch cho thớch hợp hơn. 23 August 2008 Multi-Agent Systems 35 23 August 2008 Multi-Agent Systems 36 6