Negotiation /Đàm phán<br />
<br />
Bài 4: Multi-Agent behaviour<br />
Hành vi của hệ đa Agent)<br />
<br />
1. Định nghĩa:<br />
Là một quá trình tăng cường tính thống nhất(giảm mâu<br />
thuẫn không chác chắn) dựa trên những quan điểm, kế<br />
hoạch chung thông qua việc trao đổi có hệ thống những<br />
tri thức liên quan(Durfee, 1989)<br />
<br />
Negotiation(Đàm phán)<br />
Learning(Học tập)<br />
<br />
Negotiation: Agent liên lạc với những agent khác và<br />
xác định nhu cầu về tài nguyên và dịch vụ (thường dưới<br />
những điều kiện đặc biệt); agent khác xác định cái gì có<br />
thể được cung cấp dưới những điều kiện nào;<br />
<br />
3. Giao thức Đàm phán<br />
Negotiation protocols<br />
<br />
2. Loại hình đàm phán<br />
<br />
• Negotiation protocols: thủ tục có cấu trúc cho 1 hay<br />
nhiều bước của tiến trình đàm phán<br />
<br />
• Bargaining: Mặc cả, thương lượng ( hứa hẹn hay trao đổi)<br />
• Bidding: đặt giá (đưa ra một dịch vụ, hay hàng hoá với mức<br />
giá cụ thể)<br />
<br />
•Khởi tạo agent/s chấp nhận những điều kiện;<br />
•supplying agent/s cam kết cung cấp tài nguyên hoặc dịch vụ<br />
<br />
• Contracting: ký kết (cam kết một dịch vụ, hay hàng hoá với<br />
mức giá cụ thể) hay chỉ 1 phần of the negotiation process./ký<br />
kết<br />
<br />
• đàm phán single-stage , Khởi tạo agent tạo các yêu<br />
cầu và đưa ra câu trả lời chấp nhận hay từ chối điều<br />
đó.<br />
<br />
• Ưu tiên đàm phán: Một agent cần xác định nguồn tài nguyên,<br />
dịch vụ cần thiết (nhưng không cung cấp được )và sau đó nó<br />
cần nhận diện agent mà nó tin tưởng có thể (believes<br />
potentially could.)<br />
<br />
23 August 2008<br />
<br />
Multi-Agent Systems<br />
<br />
• đàm phán multi-stage, Các agents lặp lại nhiều hơn<br />
một stage of offer/counter-offer.<br />
3<br />
<br />
23 August 2008<br />
<br />
Multi-Agent Systems<br />
<br />
4<br />
<br />
4. Nguyên lý đàm phán<br />
<br />
5.Tính chất của đàm phán<br />
<br />
Đàm phán dựa trên 3 yếu tố<br />
Language: Ngôn ngữ sử dụng bởi các agent<br />
tham gia thương lượng.<br />
Decision: Phương thức, chiến lước mà các<br />
agent sử dụng để thương lượng ra quyết định.<br />
Process: Tiến trình thực hiện đàm phán để ra<br />
quyết định của mỗi agent.<br />
<br />
Efficiency: Các agent trong quá trình ra thương lượng<br />
ra quyết định không nên tốn quá nhiều thời gian.<br />
Stability: Không nên thay đổi chiến lược đã định trước.<br />
Simplicity: Cơ chế thương lượng không nên dùng các<br />
tính toán phức tạp.<br />
Distribution: Không nên bắt một agent tính toán tập<br />
trung.<br />
Symmetry (sự cân đối): không nên thiên vị một agent<br />
nào nếu không có một lý do hợp lý.<br />
<br />
1<br />
<br />
1. Protocol (Giao thức)<br />
Nên sử dụng ngôn ngữ như<br />
thế nào?<br />
<br />
Ví dụ:<br />
<br />
Prim<br />
itive<br />
s<br />
<br />
•REACTIVE BEHAVIOR<br />
•Completers<br />
<br />
rs<br />
tiato<br />
Initia<br />
<br />
Reacto<br />
rs<br />
<br />
NEGOTIATION<br />
<br />
Giao thức ngoại giao<br />
Giao thức truyền Hypertext<br />
3. Object Structure<br />
TCP/IP<br />
How the language is constructed,<br />
2. Ngữ nghĩa<br />
grammar, syntax etc.<br />
Ngữ nghĩa của ngôn ngữ phải<br />
4. Primitives<br />
chính xác<br />
Atoms of the language<br />
Không nhập nhằng<br />
Based on speech-act theory<br />
<br />
Initiators:<br />
<br />
REACTIVE BEHAVIOR<br />
<br />
Propose,mục đích<br />
Arrange,tổ chức công<br />
việc<br />
Request (of resources)yêu<br />
cầu<br />
Inform cung cấp thông tin<br />
Query (for info) truy vấn<br />
Command mệnh lệnh<br />
Inspect kiểm tra<br />
<br />
Completers<br />
<br />
Action Sequences<br />
<br />
Pre<br />
-c<br />
<br />
ond<br />
ition<br />
s<br />
<br />
•Send<br />
<br />
•Refine<br />
<br />
•Value<br />
<br />
•Modify<br />
<br />
•Reply<br />
<br />
•Change<br />
<br />
•Refuse<br />
<br />
•Bid<br />
<br />
•Explain<br />
<br />
Of<br />
fer<br />
<br />
toc<br />
ols<br />
<br />
Object Structure<br />
<br />
ics<br />
Semant<br />
<br />
t<br />
<br />
gic<br />
<br />
Prim<br />
itiv<br />
e<br />
<br />
s<br />
<br />
Plans<br />
Co<br />
nte<br />
xt<br />
<br />
er<br />
s<br />
<br />
Re<br />
ac<br />
to<br />
<br />
ors<br />
<br />
rs<br />
<br />
Co<br />
m<br />
<br />
pl<br />
et<br />
O<br />
pt<br />
Pr imiz<br />
ob a<br />
le tio<br />
m n<br />
<br />
ion<br />
cis<br />
De ixes<br />
tr<br />
Ma<br />
<br />
Ga<br />
<br />
m<br />
<br />
eT<br />
<br />
he<br />
<br />
or<br />
<br />
NEGOTIATION<br />
<br />
y<br />
<br />
Util<br />
ity<br />
<br />
ci<br />
De<br />
<br />
on<br />
si<br />
<br />
s<br />
nce<br />
fere<br />
Pre<br />
<br />
ing<br />
tc h<br />
Ma<br />
<br />
Ma<br />
<br />
x.<br />
<br />
Ga<br />
<br />
in<br />
<br />
Str<br />
<br />
ate<br />
<br />
gie<br />
s<br />
<br />
k<br />
. Ris<br />
Min<br />
o<br />
luti<br />
So 50)<br />
ir<br />
Fa (50<br />
<br />
g<br />
tin<br />
flic<br />
on<br />
n-C lans<br />
P<br />
No<br />
<br />
Confirm xác nhận<br />
Promise hứa hẹn<br />
Commit uỷ nhiệm<br />
Accept chấp nhận<br />
Reject từ chối<br />
Grant chuyển nhượng<br />
Agree đồng ý<br />
<br />
s/t<br />
as<br />
ks<br />
<br />
Initiat<br />
<br />
uage<br />
<br />
Mo<br />
dal<br />
Lo<br />
<br />
La ng<br />
<br />
ec<br />
Eff<br />
<br />
End conversation<br />
<br />
Pro<br />
<br />
•Answer<br />
<br />
am<br />
ma<br />
r<br />
<br />
cs<br />
anti<br />
Sem<br />
<br />
•Initiators<br />
<br />
Primitives<br />
<br />
e<br />
Structur<br />
Object<br />
<br />
uage<br />
Lang<br />
<br />
Communication<br />
Understanding<br />
<br />
Proto<br />
cols<br />
<br />
Gr<br />
<br />
6. Ngôn ngữ<br />
<br />
n<br />
<br />
7.<br />
<br />
DECISION Quyết định<br />
<br />
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<br />
đàm phán.<br />
Utility<br />
Giá trị của mỗi thành phần khi tham gia<br />
”What’s in it for me” .. So to say.<br />
Expressed as a mathematical function based on own agend and expectations about others.<br />
Matching – Phù hợp<br />
Matching of plans from various agents<br />
Non-Conflicting Plans<br />
• Try to benefit from the non-conflicting plans of players<br />
Preferences – Ưu tiên<br />
What is the users preference, interest in the outcome of the negotiation?<br />
Strategies – Chiến lược<br />
Which strategy or road-map for actions should be selected to obtain a high utility and fulfill<br />
preferences?<br />
<br />
7.1. Utility – Trị giá<br />
Game Theory<br />
Basis in economics.<br />
Formal description of greediness of players<br />
Decision Matrix<br />
Lookup for values of next action<br />
Optimization Problem<br />
The essential problem is to maximize utility of the system<br />
or oneself.<br />
<br />
2<br />
<br />
7.2 Preferences<br />
<br />
Strategies<br />
<br />
Maximize Gain<br />
<br />
Concede Unilaterally(đơn phương thừa nhận)<br />
Get to a common agreement<br />
It may no benefit all, but its quick?<br />
Competetive ( Cạnh tranh)<br />
Sports-tradition<br />
Cooperative ( Hợp tác)<br />
We will try to get a best result<br />
Inaction( cù nhầy)<br />
Don’t do anything<br />
<br />
I want to maximise my personal gain (e.g. Money<br />
or points..) or the systems gain<br />
<br />
Fair Solution<br />
I want everybody to be treated fair and have a fair<br />
outcome<br />
-- no hard feelings..<br />
<br />
Minimize Risk<br />
I’ll avoid risk and will try<br />
<br />
Of<br />
<br />
ma<br />
r<br />
<br />
t<br />
<br />
am<br />
<br />
i ve<br />
<br />
s<br />
<br />
Initia<br />
<br />
s<br />
<br />
t or<br />
<br />
tors<br />
<br />
s<br />
<br />
pl<br />
<br />
et<br />
<br />
ac<br />
<br />
Co<br />
m<br />
<br />
a te<br />
<br />
s<br />
<br />
g ie<br />
<br />
s<br />
<br />
in<br />
<br />
. Ris<br />
<br />
k<br />
<br />
Proc edure<br />
<br />
ive<br />
p etet<br />
Co m<br />
Coo<br />
pera<br />
tive<br />
<br />
ac<br />
In<br />
<br />
tio<br />
n<br />
<br />
M<br />
<br />
a<br />
.G<br />
ax<br />
<br />
M in<br />
<br />
ion<br />
lut<br />
So 50)<br />
ir<br />
Fa (50<br />
<br />
Procedure Thủ tục<br />
High-level/ society view on the negotiation<br />
process)<br />
Behavior Hành vi<br />
Behavior modelling ( mô hình hóa hành vi)<br />
<br />
S tr<br />
<br />
n ce<br />
<br />
n<br />
<br />
9. PROCESS<br />
<br />
on<br />
<br />
fere<br />
<br />
e<br />
<br />
si<br />
<br />
Tota<br />
<br />
ess<br />
<br />
ing<br />
<br />
ci<br />
<br />
l Wo<br />
<br />
rk (T<br />
<br />
W)<br />
<br />
irn<br />
<br />
tc h<br />
<br />
De<br />
<br />
ict<br />
nfl o n<br />
C o ol uti<br />
s<br />
le<br />
R e C yc<br />
<br />
ss/F<br />
a<br />
<br />
lity<br />
<br />
Process<br />
<br />
Liv<br />
ene<br />
<br />
rall<br />
Un<br />
il<br />
<br />
Ma<br />
<br />
NEGOTIATION<br />
<br />
y<br />
<br />
ate<br />
rall<br />
y<br />
<br />
Co<br />
m<br />
<br />
O<br />
pt<br />
Pr i m i<br />
ob z a<br />
le tio<br />
m n<br />
<br />
U ti<br />
<br />
or<br />
<br />
Co<br />
n<br />
<br />
er<br />
s<br />
<br />
Plans<br />
Co<br />
nte<br />
x<br />
<br />
r<br />
avio<br />
<br />
ate<br />
<br />
he<br />
<br />
P re<br />
<br />
k<br />
. Ris<br />
Min<br />
<br />
ks<br />
<br />
Re<br />
<br />
eU<br />
nil<br />
<br />
eT<br />
<br />
tive<br />
pete<br />
Com<br />
<br />
Coo<br />
pera<br />
tiv<br />
<br />
m it<br />
<br />
ce<br />
d<br />
<br />
m<br />
<br />
g<br />
tin<br />
flic<br />
on<br />
n-C lans<br />
P<br />
<br />
in<br />
<br />
gie<br />
s<br />
<br />
Ga<br />
<br />
No<br />
<br />
Ga<br />
<br />
ate<br />
<br />
n<br />
tio<br />
ac<br />
In<br />
<br />
x.<br />
<br />
Str<br />
<br />
o<br />
luti<br />
So 50)<br />
ir<br />
Fa (50<br />
<br />
g<br />
tin<br />
flic<br />
on<br />
n-C lans<br />
P<br />
No<br />
<br />
Ma<br />
<br />
on<br />
y<br />
<br />
si<br />
<br />
s<br />
nce<br />
fere<br />
Pre<br />
<br />
ing<br />
tc h<br />
Ma<br />
<br />
ci<br />
De<br />
<br />
ic<br />
<br />
as<br />
<br />
tion<br />
otia<br />
Neg ycle<br />
C<br />
<br />
Util<br />
ity<br />
<br />
P ri<br />
<br />
rs<br />
<br />
pl<br />
et<br />
<br />
Re<br />
ac<br />
to<br />
<br />
NEGOTIATION<br />
<br />
y<br />
<br />
Lo g<br />
<br />
ors<br />
<br />
de<br />
<br />
or<br />
<br />
dal<br />
<br />
er<br />
<br />
Initiat<br />
<br />
Co<br />
nc<br />
e<br />
<br />
he<br />
<br />
Mo<br />
<br />
s /t<br />
<br />
Beh<br />
<br />
O<br />
pt<br />
Pr imiz<br />
ob a<br />
le tio<br />
m n<br />
<br />
eT<br />
<br />
t<br />
<br />
ing<br />
<br />
s<br />
<br />
ion<br />
cis<br />
De ixes<br />
tr<br />
Ma<br />
<br />
ion<br />
cis<br />
De ixes<br />
tr<br />
Ma<br />
<br />
m<br />
Ga<br />
<br />
ec<br />
<br />
ak<br />
<br />
Prim<br />
itiv<br />
e<br />
<br />
Ef f<br />
<br />
ns<br />
<br />
fe r<br />
<br />
Objec t Structure<br />
<br />
tics<br />
S eman<br />
<br />
Br<br />
e<br />
<br />
gic<br />
<br />
uage<br />
<br />
Mo<br />
dal<br />
Lo<br />
<br />
Plans<br />
Co<br />
nte<br />
xt<br />
<br />
ditio<br />
<br />
ols<br />
<br />
ua g e<br />
<br />
t<br />
<br />
La ng<br />
<br />
ec<br />
Eff<br />
<br />
Object Structure<br />
<br />
ics<br />
Semant<br />
<br />
am<br />
ma<br />
r<br />
<br />
ond<br />
ition<br />
s<br />
<br />
toc<br />
ols<br />
<br />
s/t<br />
as<br />
ks<br />
<br />
-con<br />
<br />
toc<br />
<br />
La n g<br />
<br />
Pre<br />
-c<br />
<br />
Pro<br />
<br />
Pre<br />
<br />
Gr<br />
<br />
Action Sequences<br />
<br />
Of<br />
fer<br />
<br />
P ro<br />
<br />
Gr<br />
<br />
s<br />
Action Sequence<br />
<br />
9.1 Procedure<br />
Negotiation Cycle<br />
Propose solutions to a certain conflict<br />
Criticial analysis of other solutions<br />
Update of solution space and preference list<br />
Conflict Resolution Cycle(Runs in parallel with<br />
<br />
negotiation cycle)<br />
<br />
Determine conflicts<br />
Select high-pri conflicts<br />
Plan conflict resolution<br />
<br />
3<br />
<br />
9.2 Behavior modelling<br />
<br />
1.<br />
2.<br />
3.<br />
<br />
Total Work (TW) The total work done in negotiation<br />
is less than or equal to the total work in a<br />
Coordinated system<br />
centralized on-line system – new tasks, sequentially<br />
Centralized off-line system – all tasks known a priori<br />
Liveness/Fairness<br />
Investigate how fair a negotiation system is<br />
<br />
V. Learning in MAS<br />
1. What is learning?<br />
An AI definition:<br />
P. Langley: Elements of Machine Learning, Morgan<br />
Kaufmann, 1996:<br />
Learning is the improvement of performance in some<br />
environment through acquisition of knowledge<br />
resulting from experience in that environment.<br />
<br />
Over to you..<br />
What would be likely preferences for<br />
people participating in auctions?<br />
What would be likely strategy for<br />
auctioneers?<br />
<br />
Is the auction negotiation system<br />
fair?<br />
<br />
Jörg Denzinger definition<br />
Learning encompasses all self<br />
modifications of a (combined)<br />
system that allow an improved future<br />
system behavior.<br />
<br />
Mục đích của việc học in MAS?<br />
<br />
2.Formal<br />
<br />
Learning to achieve:<br />
Cooperation<br />
Organization<br />
Better competition<br />
Learning of and about agents:<br />
Để cải tiến hiệu năng<br />
Để đoán nhận được phản ứng của các Agent khác<br />
Learning and Cooperation<br />
Truyền thông là công cụ cho phép học<br />
Học cũng là công cụ giúp hạn chế hoặc tránh phải liên<br />
lạc với agent khác<br />
Để tạo ra một môi trương tốt hơn cho các Agent<br />
<br />
Với một agent chúng ta có thể có fag(s) tại thời<br />
điểm t1 ≠ fAg(s) tại thời điểm t2<br />
For a not-learning agent Ag, its learning variant<br />
AgL and a sequence of situations s1,…,si,..., we<br />
have there is an i such that<br />
Ag(sj) = AgL(sj) for j < i and<br />
Ag(si) ⎯ ≠ AgL(si)<br />
Suy đoán một agent học đang làm những gì là<br />
điều rất khó.<br />
<br />
4<br />
<br />
3.Mô hình<br />
basic learning model Langley (1996)<br />
<br />
Agents and the basic learning<br />
model<br />
<br />
4. Các phương pháp học với Agent<br />
<br />
4.1 Evolutionary learning of<br />
cooperative behavior: OLEMAS<br />
<br />
Distributed credit assignment:<br />
Reinforcement Learning<br />
Evolutionary approaches<br />
Genetic Algorithms / Genetic Programming<br />
Look at MAS as an evolving population:<br />
Swarm systems, Ant systems, etc.<br />
Classification methods<br />
Learning by heart and abstraction<br />
Layered learning<br />
...(Mỗi giải thuật 1 bài tập)<br />
<br />
4.2 Reinforcement learning for<br />
forming coalitions:<br />
the DFG algorithm Weiß (1995)<br />
DFG: Dissolution and Formation of Groups<br />
Basic Problems tackled:<br />
How can several agents learn what actions<br />
they can perform in parallel?<br />
How can several agents learn what sets of<br />
actions have to be executed sequentially?<br />
<br />
Denzinger and Fuchs (1996)<br />
OLEMAS: OffLine Evolution of Multi-Agent<br />
Systems<br />
Basic Problems tackled:<br />
How can we specify tasks on a high and abstract<br />
level and let the concrete problem solution be<br />
done by learning by the MAS?<br />
How can we use combined training of agents to<br />
have them show cooperative behavior without<br />
needing much communication but relying on<br />
instinctive reactive behavior?<br />
<br />
4.1.1 Thuật toán di truyền<br />
Khái niệm: Sử dụng mô hình tiến hoá sinh học để cải<br />
tiến giải pháp giải quyết vấn đề.<br />
1. Tạo ra một tập hợp các giải pháp (Không nhất thiết là<br />
rất tốt) giải quyết vấn đề(initial population)<br />
2. Lặp lại cho đến khi điều kiện cuối cùng fulfilled:<br />
Generate out of actual population new solutions (using<br />
genetic operators), such that better solutions in the<br />
population are used with higher probability (quality<br />
fitness)<br />
Generate the next population out of the old and the new<br />
individuals<br />
<br />
5<br />
<br />
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
