Bài giảng 9: Làm việc cùng nhau

Tiết thứ: 34 – 36 Tuần thứ: 12

• 
  Tổng quan về làm việc cùng nhau
  
• 
  Giải quyết vấn đề phân tán hợp tác (CDPS)
  
• 
  Chia sẻ nhiệm vụ và kết quả
  
• 
  Chia sẻ kết quả
  
• 
  Kết hợp chia sẻ nhiệm vụ và kết quả
  
• 
  Xử lý sự không nhất quán
  
• 
  Phối hợp
  
• 
  Lập kế hoạch đa tác tử và đồng bộ hóa
  

I. Tổng quan về làm việc cùng nhau

- Tại sao các tác tử làm việc nhau và chúng làm việc cùng nhau thế nào?

- Cần phân biệt giữa:

+ các tác tử rộng lượng

+ các tác tử tư lợi

- Tác tử rộng lượng

+ Nếu chúng ta sở hữu cả hệ thống, chúng ta có thể thiết kế các tác tử giúp đỡ lân nhau bất kỳ khi nào có yêu cầu

+ Trong trường hợp này, chúng ta có thể coi các tác tử là rộng lượng: lợi ích lớn nhất của ta là lợi ích lớn nhất của chúng

+ Giải quyết vấn đề trong các hệ thống rộng lượng và giải quyết vấn đề phân tán hợp trác (cooperative distributed problem solving – CDPS)

+ Sự rộng lượng đơn giản hóa rất lớn nhiệm vụ thiết kế hệ thống

- Các tác tử tư lợi

+ Nếu tác tử đại diện cho các cá nhân và tổ chức, (trường hợp tổng quát hơn), thì chúng ta không thể đưa ra giả thiết về sự rộng lượng

+ Các tác tử sẽ được cho là hành động tiếp tục vì lợi ích riêng, có thể các tác tử khác phải trả giá

+ Tiềm năng xảy ra xung đột

+ Có thể làm phức tạp đáng kế nhiệm vụ thiết kế

- Chia sẻ nhiệm vụ và chia sẻ kết quả

+ Hai chế độ chính trong giải quyết vấn đề hợp tác là:

* chia sẻ nhiệm vụ: các thành phần của một nhiệm vụ là phân tán tới các tác tử thành phần.

* chia sẻ kết quả: thông tin (các kết quả thành phần,…) là phân tán.

- Mạng liên hệ: Một giao thức chia sẽ nhiệm vụ được biết đến để phân bổ nhiệm vụ là mạng liên hệ:

+ Nhận dạng

+ Công bố

+ Trả giá

+ Trao thưởng

+ Xúc tiến

- Nhận dạng: Trong giai đoạn này một tác tử nhận dạng nó có vấn đề muốn trợ giúp. Tác tử có mục tiêu và hoặc

+ nhận ra nó không thể tự đạt được mục tiêu - không có khả năng

+ nhận ra nó sẽ không thích đạt được mục tiêu một mình (thông thường bởi vì chất lượng của lời giải, thời hạn,…)

- Công bố:

+ Trong giai đoạn này, tác tử có nhiệm vụ gửi công bố về nhiệm vụ, bao gồm đặc tả nhiệm vụ sẽ đạt được.

+ Đặc tả phải được mã hóa: mô tả chính tác vụ (có thể thực hiện được)

+ các ràng buộc (ví dụ thời hạn, chất lượng)

+ thông tin nhiệm vụ biến đổi (ví dụ “Các trả giá phải được nộp trước…”_

+ Công bố sau đó được phát đị

- Trả giá:

+ Các tác tử nhận thông báo quyết định cho chúng liệu chúng có muốn trả giá cho nhiệm vụ

+ Các yếu tố: tác tử phải quyết định liệu nó có khả năng tiến hành nhiệm vụ; tác tử phải xác đinh các ràng buộc chất lượng và thông tin giá (chi phí) nếu có

+ Nếu chung chọn trả giá, sau đó chúng phải gửi yêu cầu.

- Trao thưởng và xúc tiến

+ Tác tử gửi công bố nhiệm vụ phải chọn giữa các trả giá và quyết đinh người được giao hợp đồng

+ Kết quả của quá trình này được thông tin cho các tác tử đã đưa ra trả giá

+ Người đấu thầu thành công sau đó sẽ xúc tiến nhiệm vụ

+ Có thể liên quan đến việc tiếp tục hình thành các mối quan hệ giữa người quản lý và người đấu thầu: hợp đồng phụ

- Các vấn đề cài đặt mạng liên hệ: Làm thế nào để

+ Xác định các nhiệm vụ?

+ Xác định chất lượng dịch vụ?

+ chọn giữa các đề xuất cạnh tranh

+ phân biệt các đề xuất dựa trên nhiều tiêu chí?

- Mạng liên hệ

+ Một cách tiếp cận cho việc giải quyết vấn đề phân tán, tập trung vào việc phân bổ nhiệm vụ

+ Phân bổ nhiệm vụ được xem như một kiểu thương lượng hợp đồng

+ Giao thức xác định nội dung giao tiêp, chứ không chỉ có mẫu

+ Việc chuyển thông tin hai chiều là mở rộng tự nhiện của việc chuyển các mô hình điều khiển.

II. Giải quyết vấn đề phân tán hợp tác (CDPS)

- Không có điều khiển toàn cục không lưu dữ liệu toàn cục – không tác tử nào có đủ thông tin để giải quyết toàn bộ ván đề.

- Điều khiển và dữ liệu là phân tán

- Các đặc tính của hệ thống CDPS và các hệ quả

+ Giao tiếp chậm hơn tính toán

* mất kết nối

* giao thức hiệu quả

* các vấn đề lập module

* các vấn đề với kích thước hạt lớn

- Một nút duy nhất nào là một bế tắc tiềm năng

+ phân tán dữ liệu

+ phân tán điều khiển

+ hành vi được tổ chức kho để đảm bảo (ví không có nút nào có toàn bộ thông tin)

III. Chia sẻ nhiệm vụ và kết quả

- Bốn giai đoạn để có được lời giải, như đã trình bày ở mạng liên hệ

+ Phân rã bài toán

+ Phân bổ các bài toán con

+ Lời giải cho các bài toán cong

+ Trả lời tổng hợp

Mạng liên hệ giải quyết giai đoạn 2.

3.1 Chia sẻ nhiệm vụ trong mạng liên hệ

- Mạng liên hệ

+ Tập các nút là mạng liên hệ

+ Mỗi nút trong mạng có thể, tại các thời điểm khác nhau hoặc đới với các nhiệm vụ khác sau, là người quản lý hoặc người đấu thấu.

+ Khi một nút nhận được một nhiệm vụ hỗn hợp (hoặc vì lý do nào đó không thể giải quyết được nhiệm vụ hiện thời), nó chia thành các nhiệm vụ con (nếu có thể) và công bố chúng (hoạt động như người quản lý), và nhận được trả giá từ những người đấu thầu, và sau đó giao công việc (ví dụ bài toán: quản lý tài nguyên mạng, máy in..)

- Định giá cụ thể bài toán

+ Thông điệp công bố nhiệm vụ thúc đẩy các nhà đấu thầu tiềm năng dung các thủ tục đánh giá nhiệm vụ cụ thể của bài toán; việc nhân nhắc tiếp tục thực hiện, chứ không chỉ có lựa chọn – Có lẽ không nhiệm vụ nào hiện tại phù hợp

+ Người quản lý cân nhắc các trả giá sử dụng thủ tục lượng giá giá trả

- Các loại thông điệp

+ Công bố nhiệm vụ

+ Trả giá

+ Trao thưởng (Giao nhiệm vụ)

+ Báo cáo tạm thời (trong tiến trình)

+ Báo cáo cuối cùng (bao gồm mô tả kết quả)

+ Thông điệp kết thúc (nếu người quản lý muốn kết thúc hợp đồng)

IV. Chia sẻ kết quả

- Trong chia sẻ kết quả, việc giải quyết vấn đề tiếp tục bởi các tác tử hợp tác trao đổi thông tin khi một lời giải được phát triển. Thông thường, các kết quả này sẽ phát triển từ các lời giải của bài toán nhỏ, sau đó tiếp tục cải tiến thành các lời giải trừu tượng và rộng hơn.

Durfee (1999) đề xuất một người giải quyết vấn đề có thể cải thiện khả năng làm việc nhóm bằng chia sẻ dữ liệu theo những cách sau:

+ Độ tin cậy: các giải pháp được đưa ra độc lập có thể được kiểm tra chéo, nhấn mạnh các lỗi có thể, và tăng độ tin cậy của lời giải tổng thể.

+ Tính đầy đủ: Các tác tử có thể chia sẻ quan điểm cục bộ để đạt được qua điểm toàn cục tốt hơn

+ Tính chính xác: các tác tử có thể chia sẻ các kết quả để đảm bảo rằng độ chính xác của lời giải tổng thể tăng

+ Lịch trình: thâm chí nếu một tác tử có thể tự giải quyết một vấn đề, bằng việc chia sẻ kết quả, kết quả có thể được nhận được nhanh hơn.

V. Kết hợp chia sẻ nhiệm vụ và kết quả

- Trong công việc hợp tác hàng ngày mà chúng ta tất cả đều liên quan, chúng ta thường kết hợp chia sẻ nhiệm vụ và kết quả. Phần này sẽ trình bày tổng quan về cách điều này có thể đạt được trong hệ thống FELINE. FELINE là hệ chuyên gia hợp tác. Ý tưởng là xây dựng một hệ giải quyết vấn đề tổng thể như là tập hợp các chuyên gia công tác, mỗi người có tri thức chuyên gia riêng biệt nhưng có liên hệ. Hệ thống làm việc bởi các tác tử hợp tác để chia sẻ các tri thức và phân tán các nhiệm vụ. Mỗi tác tử trong FELINE là một hệ thống tựa luật độc lập: nó có bộ nhớ làm viêc, hay cơ sở dữ liệu, chứa các thông tin về trạng thái hiện tại của việc giải quyết vấn đề; ngoài ra, mỗi tác tử có một tập các luật, mã hóa tri thức về bài toán.

VI. Xử lý sự không nhất quán

- Một trong những vấn đề chính nảy sinh trong hoạt động hợp tác là sự không nhất quán giữa các tác tử khác nhau trong hệ thống. Các tác tử có sự không nhất quan liên quan đến cả niềm tin của chúng và các mục tiêu ý đinh của chúng.

- Sự không nhất quán về mục tiêu thường bởi vì các tác tử là độc lập và do đó không chia sẻ cùng mục tiêu.

- Sự không nhất quán về niềm tin xuất phát từ nhiều nguyên nhân:

+ không có tác tử nào có thể có được bức trang tổng thể về môi trường

+ các bộ cảm ứng của tác tử có thể bị lỗi, hoặc các nguồn tin mà tác tử truy cập có thể lỗi.

- Một số cách tiếp cận để khắc phục

+ Không cho phép nó xảy ra – hoặc ít nhất bỏ quan qua nó.

+ Giải quyết sự không nhất quán thông qua thương lượng

+ Xây dựng các hệ thống tồn tại hợp lý cùng với sự không nhất quán.

VII. Phối hợp

- Vấn đề mối hợp là việc quản lý sự phụ thuộc giữa các hoạt động của các tác tử: một mô hình phối hợp nào đó là cần thiết nếu các hoạt động mà các tác tử tham gia có thể tương tác. Hai hoạt động có thể tương tác như thế nào? Xem xét các ví dụ sau

+ Bạn và tôi cả hai đều muốn rời phòng, và vì vây chúng ta độc lập đi tới cửa phòng. Cửa phòng chỉ cho một trong 2 người qua. Tôi cho phép bạn đi trước. Trong ví dụ này, hành động của 2 người cần được điều phối bởi vì chỉ có một nguồn tài nguyên (chiếc cửa) cả hai người muốn dung, nhưng chỉ cho phép 1 người 1 lúc.

+ Tôi có ý định nộp một đề xuất xin kinh phí, nhưng để làm điều này tôi cần chữ ký của bàn. Trong trường hợp này hành động gửi đề xuất của tôi phụ thuộc hoạt động ký của bạn – Tôi không thể thực hiện hoạt động của mình đến khi hoạt động của bạn hoàn tất. Nói cách khác hoạt động của tôi phụ thuộc hoạt động của bạn.

+ Tôi có bản mềm của của một tờ giấy từ trang Web. Tôi biết rằng báo cáo này cũng sẽ là quan tâm của bạn. Biết điều này, Tôi chủ động photo 1 bản và đưa bản photo cho bạn. Trong trường hợp này, hành động của chúng tôi không cần phải phối hợp – vì báo cáo là sẵn có trên Web, bạn có thể download và in bản copy của bạn. Nhưng thông qua việc chủ động in một bản copy, tôi tiết kiệm thời gian cho bạn và do đó tăng lợi ích (utility) của bạn.

Biểu đồ hình học của Von Martial về các quan hệ phối hợp.

Von Martial (1990) đã đề xuât một biểu đồ hình học cho các mối quan hệ phối hợp. Ông đề xuất các mối quan hệ giữa các hoạt động có thể là tích cực hoặc tiêu cực.

- Các quan hệ tích cự là quan hệ giữa các kế hoạch có thể mang lại lợi ích nào đó cho một hoặc cả hai, bằng cách kết hợp chúng.

- Các cách tiệp cận chính đã được phát triển cho các hoạt động phối hợp động

+ Phối hợp thông qua lập kế hoạch toàn cục từng phần

+ Phối hợp thông qua các ý định chung

+ Phối hợp thông qua lập mô hình chung

+ Phối hợp thông qua các chuẩn và luật xã hội

IIX. Lập kế hoạch đa tác tử và đồng bộ hóa

- Một vấn đề rõ ràng trong giải các bài toán đa tác tử là lập kế hoạch các hoạt động của một nhóm tác tử. Trong chương 4, chúng ta đã thấy việc lập kế hoạch có thể được sáp nhật như một thành phần trong một tác tử lập luận thực tế như thế nào: Những mở rộng và thay đổi nào có thể cần để lập kế hoạch cho một nhóm các tác tử? Mặc dù nó tương tự với lập kế hoạch truyền thống, lập kế hoạch đa tác tử cần cân nhắc thực tế là các hoạt động của các tác tử có thể anh hưởng lẫn nhau – hành động của chúng do đó phải được phối hợp. Có hai khả năng cho lập kế hoạch đa tác tử như sau:

+ lập kế hoạch trung tâm cho các kế hoạch phân tán: một hệ thống lập kế hoạch trung tâm phát triển một kế hoạch cho một nhóm tác tử, trong đó sự phân chia và trật tự công việc được định rõ. Tác tử chủ sau đó phân bổ kế hoạch cho các tác tử khách. Những tác tử sau đó sẽ thực hiện phần kế hoạch của mình.

+ Lập kế hoach phân tán: Một nhóm tác tử hợp tác để hình thành một kế hoạch trung tâm. Thông thường, các tác tử thành phần là các chuyên gia trong các khía cạnh khác nhau của kế hoạch tổng thể, và sẽ đóng góp một phần vào kế hoạch đó. Tuy nhiên, các tác tử hình thành kế hoạch sẽ không là các tác tử thực hiện kế hoạch; vai trò của chúng chỉ đơn giản là tạo ra kế hoạch.

+ Lập kế hoạch phân tán cho các kế hoạch phân tán: một nhóm tác tử hợp tác để hình thành các kế hoạch hành động cho cá nhân, phối hợp động các hoạt động trong quá trình thực hiện. Các tác tử có thể là tư lợi, và bởi vậy, khi các vấn đề phối hợp tiềm năng hình thành, chúng có thể cần được giải quyết thông qua thương lượng.

+ Đọc trước: Chương 9, Tài liệu 1

+ Bài tập về nhà: Bài 1 - 3, Chương 9, Tài Liệu 1.