Bài giảng Hành vi của hệ đa Agent

ion
„ 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.