Giải quyết vấn đề phân tán

Giải quyết vấn đề phân tán nghiên cứu cách một vấn đề có thể được giải quyết bởi nhiều tác nhân, mỗi tác nhân nắm giữ một phần thông tin hoặc trách nhiệm, những tác nhân này giao tiếp và kết hợp các kết quả cục bộ của họ thành một giải pháp toàn cục.

Definition

Giải quyết vấn đề phân tán là việc giải quyết vấn đề một cách hợp tác bởi một nhóm các tác nhân, mỗi tác nhân có kiến thức cục bộ hoặc các vấn đề con, phối hợp thông qua giao tiếp để tạo ra một giải pháp tổng thể mạch lạc.

Scope

Chủ đề này bao gồm việc giải quyết vấn đề hợp tác giữa các tác nhân không chia sẻ bộ điều khiển trung tâm: chia sẻ nhiệm vụ và kết quả, thỏa mãn và tối ưu hóa ràng buộc phân tán (DCSP/DCOP) với các thuật toán như quay lui không đồng bộ, và sự phối hợp các giải pháp cục bộ dưới các ràng buộc về giao tiếp và quyền riêng tư. Nó đề cập đến cách phân tách, tính toán cục bộ và truyền thông điệp tạo ra các giải pháp nhất quán toàn cục. Tương tác cạnh tranh thuần túy và thiết kế khuyến khích được đề cập trong lý thuyết trò chơi và thiết kế cơ chế.

Core questions

• Một vấn đề được phân tách và phân phối giữa các tác nhân có góc nhìn cục bộ như thế nào?
• Các tác nhân chia sẻ nhiệm vụ và kết quả trung gian như thế nào để xây dựng một giải pháp toàn cục?
• Một vấn đề ràng buộc được giải quyết như thế nào khi các biến và ràng buộc được phân tán giữa các tác nhân?
• Chi phí giao tiếp và quyền tự chủ cục bộ được cân bằng như thế nào so với chất lượng giải pháp?

Key concepts

• phân tách vấn đề
• chia sẻ nhiệm vụ và chia sẻ kết quả
• thỏa mãn ràng buộc phân tán (DCSP)
• tối ưu hóa ràng buộc phân tán (DCOP)
• quay lui không đồng bộ
• truyền thông điệp
• quyền tự chủ cục bộ và quyền riêng tư
• tính nhất quán toàn cục

Key theories

Thỏa mãn và tối ưu hóa ràng buộc phân tán

Thỏa mãn ràng buộc phân tán (DCSP) và tối ưu hóa (DCOP) khái quát hóa các vấn đề ràng buộc sang các thiết lập trong đó các biến và ràng buộc được nắm giữ bởi các tác nhân khác nhau, được giải quyết bằng các thuật toán trong đó các tác nhân trao đổi không đồng bộ các gán giá trị và thông tin xung đột.

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

Giải quyết vấn đề phân tán hợp tác tiến hành bằng cách phân tách và phân phối các nhiệm vụ và bằng cách trao đổi các kết quả cục bộ mà các tác nhân tích hợp, cho phép một nhóm giải quyết các vấn đề mà không một tác nhân nào có thể giải quyết một mình.

Tìm kiếm phân tán không đồng bộ

Các thuật toán như quay lui không đồng bộ cho phép các tác nhân tìm kiếm một gán toàn cục nhất quán mà không cần kiểm soát trung tâm, sử dụng truyền thông điệp ưu tiên để giải quyết xung đột trong khi vẫn duy trì quyền tự chủ cục bộ.

Clinical relevance

Giải quyết vấn đề phân tán áp dụng cho giám sát và theo dõi đa cảm biến, lập lịch phân tán và phối hợp cuộc họp, quản lý lưới điện và giao thông, và bất kỳ thiết lập nào mà dữ liệu hoặc trách nhiệm được phân tán tự nhiên giữa các tác nhân phải cùng nhau tìm ra một giải pháp nhất quán trong khi hạn chế giao tiếp.

History

Giải quyết vấn đề phân tán hợp tác là một chủ đề nền tảng của AI phân tán, được minh họa bằng công trình nghiên cứu về mạng cảm biến phân tán và hệ thống bảng đen vào những năm 1980. Yokoo và các đồng nghiệp đã chính thức hóa việc thỏa mãn ràng buộc phân tán vào những năm 1990, và tối ưu hóa ràng buộc phân tán sau đó trở thành một khuôn khổ chính cho việc ra quyết định đa tác nhân hợp tác.

Key figures

• Edmund H. Durfee
• Victor R. Lesser
• Makoto Yokoo
• Daniel D. Corkill

Seminal works

• yokoo1998
• durfee1989

Frequently asked questions

Giải quyết vấn đề phân tán khác với tính toán song song như thế nào?

Tính toán song song thường chia một vấn đề giữa các bộ xử lý dưới sự kiểm soát trung tâm để tăng tốc độ. Giải quyết vấn đề phân tán giả định các tác nhân tự chủ với kiến thức cục bộ của riêng họ và có thể có các ràng buộc về quyền riêng tư hoặc giao tiếp, vì vậy thách thức là phối hợp và đạt được một giải pháp mạch lạc, chứ không chỉ là tốc độ.

Vấn đề tối ưu hóa ràng buộc phân tán là gì?

Đó là một vấn đề ràng buộc trong đó các biến và ràng buộc thuộc sở hữu của các tác nhân khác nhau, và các tác nhân phải hợp tác gán giá trị để tối ưu hóa một mục tiêu toàn cục (chẳng hạn như giảm thiểu tổng chi phí) trong khi chỉ giao tiếp cục bộ. Nó mô hình hóa nhiều nhiệm vụ phối hợp hợp tác giữa các tác nhân.