Bài giảng Tác tử: Công nghệ phần mềm dựa tác tử, Hệ đa Agent và Cộng đồng Agent

I.Khái niệm - MAS 1.Mục đích

(cid:132) Có khả năng giải quyết các vấn đề lớn, ngoài khả năng

Multi-Agent System(MAS) Hệ đa Agent-Cộng đồng Agent

của agent đơn lẻ (ví dụ do hạn chế tài nguyên).

(cid:132) 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.

(cid:132) 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.

(cid:132) 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

•Khái niệm Mas •Hoạt động các Agent •Coordination •Cooperation •Negotiation •Learning

Multi-agent systems (MAS)

Môi trường đa agent

(cid:132) 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).

(cid:132) 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)

(cid:132) tương tác cạnh tranh - competitive settings thường

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.

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) .

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.

Agent in a MAS (cont.)

4.Formal Definitions and Properties

(cid:132) Định nghĩa: một agent Ag trong MAS là một Agent

được mô tả

(cid:132)

(cid:132) Dat: bao gồm. (cid:132) Data Own: tập hợp các vùng dữ liệu riêng của

- Ag(Sit,Act,Dat) với các cấu trúc mở rộng sau

Agent Ag

đây.

(cid:132) - Act = ActOwn * ActCo

(cid:132)

khác.( Sure Knowledge)

(cid:132) DatKS: tập các dữ liệu đáng tin cậy về các Agent

(cid:132) DatKA: tập các giả thiết về Agents khác

- 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. (cid:132) (cid:132) - 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).

(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ệ.

1

Multi-Agent System

II. Các mô hình MAS

(cid:132) Object Manager Group (OMG) (cid:132) www.omg.org (cid:132) Sankar Virdbagriswaran, Damian Osisek, Pat O’Connor,

Standardizing Agent Technology, ACM StandardView Vol.3, No.3, September 1995

hiện trong Mult.

(cid:132) Một hệ thống đa Agent Mult (is a 5- Tuple) (cid:132) Mult = (Sit, Ag, Mact, α, MultL) (cid:132) Sit: là tập các trạn thái. (cid:132) Ag: tập các Agent ( trong một MAS) (cid:132) Mact: tập các hoạt động cơ bản có thể được thực

Agent thực hiện nó.

(cid:132) α: Mact → Ag gán mỗi hành động của Mact cho

(cid:132) Foundation for Physical Agents (FIPA) (cid:132) www.fipa.org (cid:132) www.fipa.org/specs/fipa00001/fipa00001.html (cid:132) Knowledge-able Agent-oriented System (KAoS) (cid:132) http://ksi.cpsc.ucalgary.ca/KAW/KAW96/bradshaw/KAW.html (cid:132) General Magic group (cid:132) seems to be out of date...

(cid:132) MultL: là ngôn ngữ hành động của Agent.

OMG’s - Model

FIPA’s – Mô hình

(cid:132) 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

(cid:132) - Agent được đặc tả bởi: khả năng, kiểu tương tác và

tính lưu động.

(cid:132) Các trung gian hỗ trợ:

(cid:132)

nên hệ Agent gồm: (cid:132) Agent Platform (AP) (cid:132) Directory Facilitator (DF) (cid:132) Agent Management System (AMS) (cid:132) Agent Communication Channel (ACC) (cid:132) Agent Communication Language (ACL)

Các hoạt động đồng thời của các Agent. Bảo mật Agent di động

(cid:132) (cid:132) ….

(cid:132) Dựa trên tập các Agents và các thành phần tạo

Mô hình KAoS

Mô hình General Magic

(cid:132) Là mô hình ứng dụng Agent thương mại trong

thương mại điện tử.

Agent phần mềm.

(cid:132) Xem xét MAS ở góc độ Chợ điện tử. (electronic

(cid:132) Mô tả theo kiến trúc mở và phân tán của

marketplace)

Agent

(cid:132) Mô hình Định nghĩa đa dạng cách thực hiện

giữa các Agent.

(cid:132) 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.

(cid:132) 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.

(cid:132) Sử dụng kiểu đàm thoại để hình thành liên lạc

2 Các hoạt động cơ bản của hệ đa tác tử

III. COOPERATION-Hợp tác

(cid:132) Các hoạ động cơ bản:

•Mục đích kết hợp của con người

(cid:132) Điều phối Phối hợp, COORDINATION, (cid:132) Hợp tác, COOPERATION, (cid:132) Đàm phán NEGOTIATION (cid:132) Lập kế hoạch -PLANNING

(cid:132) Các hoạ động cơ bản đó là biểu hiện của việc nhóm, kết nối các

•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

(cid:132) 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.

An organization consists of •a group Ags of agents, •a communication structure Com, and •an order/report structure Rep.

Multi-Agent Systems

hoạt động của Agent. Tạo cơ chế cho hoạt động

Cooperative Problem Solving

Cooperation Concepts

Đị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.

thông tin có sẵn: (cid:132) Đàm phán ( negotiation) (cid:132) Quan hệ chủ/tớ ( Master/Slave relationship) (cid:132) Biểu quyết ( Voting) (cid:132) Đấu giá ( auctions)

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.

Example: The TECHS approach for cooperative search (bài tập|

(cid:132) 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 (cid:132) Ví dụ:Kết hợp bằng sử dụng ( lựa chọn) các

1. Advantages of Cooperation

chia sẻ khả năng

(cid:132) Hoàn thành công việc nhanh hơn thông qua

được các công việc mà nếu không phối hợp thì không thể làm được

(cid:132) Bằng việc chia sẻ tài nguyên sẽ thực hiện (cid:132) Denzinger and Fuchs (1999) (cid:132) 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

(cid:132) 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 (cid:132) Tạo khả năng bổ sung cho nhau (cid:132) Tránh được các tác động bất lợi

3 2. Modes of Cooperation

3. Degrees of Cooperation

(cid:132) Fully cooperative (benevolent) Hợp tác hoàn

ý, một bên thì có chủ ý giúp đỡ

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 đỡ.

(cid:132) Tình cờ - accidental: Một bên không có chủ

hay nhiều Agent có ý định hợp tác

(cid:132) Hợp tác qua lại - mutual cooperation: hai

(cid:132) 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

Multi-Agent Systems

(cid:132) Đố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.

COORDINATION trên Agents

III. Coordination - Điều phối trong MAS

(cid:131) 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.

(cid:131) 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:

•Đ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

3. Cơ chế tiến trình điều phối Processes Mechanism

• 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

2.Mục đích

(cid:132) Phụ thuộc vào các hoạt động của Agent. (cid:132) Quản lý các ràng buộc toàn cục

(cid:132) : ví dụ : thời gian, tiền bạc, tài nguyên tính toán. (cid:132) 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.

(cid:132) Mutual Adjustment (điều chỉnh qua lại) (cid:132) Direct Supervision - Giám sát trưc tiếp (cid:132) Standardization - Chuẩn hoá (cid:132) mediated coordination - phối hợp gián tiếp (cid:132) reactive coordination - phối hợp phản xạ

4

Direct supervision Giám sát trực tiếp

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.

(cid:132) 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.

• Sự phối hợp một nhóm ngang hàng ( markets

thường là điều chỉnh qua lại.)

Multi-Agent Systems

(cid:132) 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)

Điều phối theo chuẩn

Điều phối gián tiếp Mediated coordination

Nhà trung gian-mediator như một người xúc

tuân theo.

tiến-facilitator ( tìm và định hướng thông tin)*

(cid:132) Các thủ tục tiêu chuẩn được thiết lập cho agent

Một người môi giới là trung gian và cố vấn

các agent phía nhận.

trong việc đàm phán trên các loại tài nguyên).

(cid:132) Trong điều chỉnh qua lại, được thực hiện bởi

qua ( yêu cầu) đề nghị bắt buộc

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.

Multi-Agent Systems

(cid:132) Trong giám sát trực tiếp , được thiết lập thông

Coordinated Systems Mechanisms Cơ chế hệ thống điều phối

Điều phối dựa vào hành vi phản xạ Coordination by reactive behaviour

(cid:132) Hoạt động điều chỉnh qua lại thông qua tương tác

peer to peer,

(cid:132) giám sát trực tiếp sử dụng cách tiếp cận “Chủ - Tớ “ (cid:132) 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

(“situation”) bằng các hành vi cụ thể (“Action”) (cid:132) 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

(cid:132) Đ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)

(cid:132) Các Agent phản xạ lại các tác nhân kích thích

(cid:132) Các nhóm phối hợp và cấu trúc có tổ chức

Multi-Agent Systems

(cid:132) 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

5

Cơ chế Phân nhóm

Mức độ điều khiển trong phối hợp –I

(cid:132) Điều khiển tập trung :

(cid:132) 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.

(cid:132) (cid:132) Đồng bộ và liên lạc rõ ràng:

(cid:132)

Các thủ tục gọi, chủ/ tớ(tập trung, little adaption)

(cid:132) 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.

(cid:132) Chia sẻ các dũ liệu trừu tượng ( Shared – Data

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).

(cid:132)

(cid:132) 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.

(cid:132) Nếu chỉ sử dụng cơ chế giám sát trực tiếp thì kết quả thu được là

Abstraction) Các ngôn ngữ thông dụng, các ngôn ngữ lập trình hiện tại

Multi-Agent Systems

cây phân cấp của các nhóm

Mức độ điều khiển trong phối hợp – II

5.Mô hình Coordination

(cid:132) 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

(cid:132) Functionally Accurate Cooperative Approach: (cid:132) Đ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ờ)

(cid:132) Coordination =

(cid:132)

(cid:132) Điều khiển suy luận: (cid:132) Agent sử dụng cơ sở tri thức của nó và các Agent khác để

(cid:132) Commitments Sự uỷ thác+ (cid:132) Conventions + Sự thoả thuận + (cid:132) Social Conventions + thoả thuận cộng đồng+ (cid:132) Local Reasoning :Suy luận cục bộ

Coordination = xây dựng / sửa chữa bộ “khung” phối hợp

(cid:132) Tương tác suy luận: (cid:132) 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.

Joint Goals Kết hợp mục đích

Commitment Uỷ nhiệm

(cid:132) Convention(thoả hiệp)

(cid:132) Kết hợp mục đích dựa cơ sở của việc kết hợp hành động (cid:132) Kết hợp hành động:

(cid:132) Bằng cách quan sát sự uỷ nhiệm khi thay đổi hoàn

(cid:132) Một dạng phức tạp của việc hợp tác trong một nhóm

cảnh.

(cid:132) Quan hệ Goal- subgoal:

(cid:132) Kiểu uỷ nhiệ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 đó. (cid:132) Đặc tính của kết hợp hành động:

(cid:132) Chịu trách nhiệm qua lại Vd: theo luật (cid:132) Kết hợp uỷ nhiệm\ Lôi kéo theo cùng hướng (cid:132) Hỗ trợ lẫn nhau \ ví dụ Bảo vệ Ủng hộ lẫn nhau

• Hierarchical, AND/OR goals (cid:132) Quan hệ Goal-Dependency :

• Phụ thuộc mạnh/ yếu • Uni/Bi-directional

6

5.3 Conventions/

Social Convention Types Các loại thoả hiệp

(cid:132) Commitment có thể thay đổi theo thời gian: do sự thay đổi

(cid:132) Quan hệ Goal-Subgoal:

(cid:132) tin rằng mỗi agent sẽ thực hiện tốt mục đích ( nhỏ) của

(cid:132) Cần thoả hiệp để mô tả khi commitment thay đổi:

môi trường.

(cid:132) Quan hệ Goal-Dependency:

(cid:132) When to keep commitment (giữ lại) (cid:132) When to revise commitment (sửa chữa) (cid:132) When to remove commitment (loại bỏ) Ví dụ về thoả hiệp:

(cid:132) quan sát sự thay đổi của commitment để quyết định hành

(cid:132) Ví dụ Lý do của việc định lại commitment:

chúng

(cid:132) Kết hợp Action Convention, Kết hợp Commitments

(cid:132) commitment đã hoàn thành (cid:132) không thực hiện được (cid:132) mục đích không còn tồn tại (cid:132) Các hành động:

(cid:132) R1:

and Kết hợp Goals: (cid:132) cho các cá nhân có thể giả thiết về hoạt động riêng của các

If Commitment đã hoàn thành OR

động

Commitment không thực hiện được OR Động cơ Commitment không còn

• • • •

Huỷ Commitment

6.Common Coordination Techniques Kỹ thuật điều phối

Agent khác

7.Ingredients in Good Coordination

tác theo các cách có thể đoán trước

(cid:132) 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

(cid:132) Phải có các cấu trúc làm agent có thể tương

mờ ( cho mỗi Agent)

(cid:132) 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.

(cid:132) - Phải mềm dẻo, cho phép nhìn từng phần và

(cid:132) Đặ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ể.

(cid:132) - 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 đó.