*
d ij
*
d ij
Agent j
Agent i
ĐIỀU KHIỂN HỆ ĐA TÁC TỬ
Trịnh Hoàng Minh, Nguyễn Minh Hiệu
Agent j
g ji
g ji
g ij
*
*
Trajectory
Initial formation
Desired formation
Agent i
g ij
Initial
position
Desired
position
Điều khiển hệ đa tác tử
Điều khiển hệ đa tác tử
Trịnh Hoàng Minh, Nguyễn Minh Hiệu
Ngày 30 tháng 11 năm 2022
Điều khiển hệ đa tác tử
Bản quyền
Giáo trình này được chia sẻ qua website cá nhân của TS. Trịnh Hoàng Minh (https://sites.google.com/
view/minhhoangtrinh). Việc sử dụng nội dung trong tài liệu này với mục đích tham khảo, học tập, giảng
dạy là miễn phí. Tuy nhiên, người đọc không được sao chép các nội dung của giáo trình khi chưa có đồng
ý từ các tác giả.
Ghi chú
Giáo trình này được viết bằng LATEX, dựa trên template kaobook. Template kaobook được phân phối
miễn phí qua Overleaf. Người đọc có thể sử dụng template này tại: KOMA-Script, LATEX, kaobook.
Ngày xuất bản
Phiên bản 10/2022
Lời nói đầu
Phân tích và điều khiển hệ đa tác tử là một hướng nghiên cứu đã và đang được quan tâm trên thế giới từ
khoảng đầu những năm 2000. Nội dung nghiên cứu bao gồm các hệ đa tác tử trong tự nhiên (hiện tượng
tụ bầy ở chim, cá), trong kĩ thuật (hệ các robot tự hành, mạng cảm biến, lưới điện thông minh), hay các
hiện tượng xã hội (mạng xã hội, mạng học thuật).
Mặc dù nghiên cứu về các hệ đa tác tử hiện nay đã phân chia thành nhiều hướng nghiên cứu nhỏ và
chuyên sâu, hiện nay không có nhiều những sách tham khảo, kể cả bằng tiếng Anh, bao quát các kiến
thức cơ bản về điều khiển hệ đa tác tử. Tài liệu này được biên soạn với mong muốn cung cấp một nguồn
tham khảo ngắn gọn bằng tiếng Việt cho học viên trong hai học phần Điều khiển nối mạng và Điều khiển
hệ đa tác tử tại Đại học Bách Khoa Hà Nội.
Tài liệu được chia thành ba phần chính. Phần I giới thiệu về hệ đa tác tử và cung cấp một số kiến thức cơ
bản về lý thuyết đồ thị. Phần II trình bày về hệ đồng thuận tuyến tính và một số phương pháp phân tích
và thiết kế các luật đồng thuận và đồng bộ hóa đầu ra. Phần III giới thiệu về một số ứng dụng của hệ đa
tác tử bao gồm điều khiển đội hình, giữ liên kết và tránh va chạm, định vị mạng cảm biến, và một số mô
hình động học quan điểm trong nghiên cứu mạng xã hội. Để sử dụng tài liệu, người đọc cần có kiến thức
cơ bản về Đại số tuyến tính, Giải tích, Tín hiệu hệ thống và Lý thuyết điều khiển tuyến tính. Một số kiến
thức liên quan về Đại số tuyến tính, Lý thuyết điều khiển liên quan cũng được cung cấp trong phần Phụ
lục của tài liệu.
Tài liệu tiếng Việt này sẽ không tránh được những sai sót. Tác giả hi vọng sẽ nhận được những ý kiến
góp ý về nội dung của tài liệu từ độc giả. Cuối cùng, tác giả muốn gửi lời cảm ơn tới những thầy cô,
bạn bè, và sinh viên trong và ngoài nước đã hướng dẫn, thảo luận và góp ý về các nội dung trong tài liệu này.
Trịnh Hoàng Minh, Nguyễn Minh Hiệu
Khoa tự động hóa
Trường Điện - Điện tử
Đại học Bách Khoa Hà Nội
Email:
[email protected]
Mục lục
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
Danh mục kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
I
1
Cơ sở
1
Giới
1.1
1.2
1.3
thiệu về hệ đa tác tử . . . . . .
Giới thiệu, định nghĩa, và ví dụ
Điều khiển hệ đa tác tử . . . .
Ghi chú và tài liệu tham khảo .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
3
5
2
Lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . .
2.1 Đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Đồ thị vô hướng . . . . . . . . . . . . . . . . .
2.1.2 Đồ thị hữu hướng . . . . . . . . . . . . . . . .
2.1.3 Đồ thị có trọng số . . . . . . . . . . . . . . . .
2.2 Đại số đồ thị . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Một số ma trận của đồ thị . . . . . . . . . . . .
2.2.1.1 Ma trận bậc và ma trận kề . . . . . .
2.2.1.2 Ma trận liên thuộc . . . . . . . . . . .
2.2.1.3 Ma trận Laplace của đồ thị vô hướng
2.2.2 Ma trận Laplace của đồ thị hữu hướng . . . . .
2.3 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . .
2.4 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
7
10
11
11
11
11
12
14
17
20
21
II Hệ đồng thuận
3
Thuật toán đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Hệ đồng thuận gồm các tác tử tích phân bậc nhất . . . . . . . .
3.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Trường hợp tổng quát . . . . . . . . . . . . . . . . . . . .
3.1.3 Một số trường hợp riêng . . . . . . . . . . . . . . . . . . .
3.2 Đồng thuận với các tác tử tích phân bậc hai . . . . . . . . . . .
3.3 Hệ đồng thuận tuyến tính tổng quát . . . . . . . . . . . . . . . .
3.4 Hệ đồng thuận tuyến tính không liên tục . . . . . . . . . . . . .
3.4.1 Mô hình và điều kiện đồng thuận . . . . . . . . . . . . . .
3.4.2 Liên hệ với mô hình hệ đồng thuận liên tục . . . . . . . .
3.5 Đồng bộ đầu ra hệ tuyến tính dựa trên quan sát trạng thái . . .
3.5.1 Đồng bộ hóa dựa trên bộ quan sát trạng thái Luenberger
3.5.2 Bộ quan sát kết hợp đồng bộ hóa đầu ra . . . . . . . . . .
3.6 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . . . . . . . .
3.7 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
25
25
26
28
31
36
38
38
40
43
43
47
50
51
4
Phân tích hệ đồng thuận theo phương pháp Lyapunov và quá
4.1 Hàm bất đồng thuận . . . . . . . . . . . . . . . . . . . .
4.2 Phân tích theo phương pháp Lyapunov . . . . . . . . .
4.3 Quá trình đồng thuận cạnh . . . . . . . . . . . . . . . .
4.4 Đồng bộ hóa đầu ra các hệ thụ động . . . . . . . . . . .
4.5 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . . .
4.6 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . .
trình
. . .
. . .
. . .
. . .
. . .
. . .
đồng thuận
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
cạnh
. . .
. . .
. . .
. . .
. . .
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
III Một số ứng dụng của hệ đa tác tử
5
Điều
5.1
5.2
5.3
5.4
5.5
5.6
5.7
71
khiển đội hình . . . . . . . . . . . . . . . . . . . . . .
Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . .
Điều khiển đội hình dựa trên vị trí tuyệt đối . . . . .
Điều khiển đội hình dựa trên vị trí tương đối . . . . .
5.3.1 Trường hợp tác tử là khâu tích phân bậc nhất
5.3.2 Trường hợp tác tử là khâu tích phân bậc hai .
Điều khiển đội hình dựa trên khoảng cách . . . . . . .
5.4.1 Lý thuyết cứng khoảng cách . . . . . . . . . . .
5.4.2 Luật điều khiển đội hình . . . . . . . . . . . . .
Điều khiển đội hình dựa trên vector hướng . . . . . .
5.5.1 Lý thuyết cứng hướng trên ℝ 𝑑 . . . . . . . . .
5.5.2 Điều khiển đội hình cứng hướng vi phân . . . .
Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . .
Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . .
liên kết và tránh
Giữ liên kết . .
Tránh va chạm
Bài tập . . . .
va chạm
. . . . .
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
55
55
57
61
63
66
66
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
72
72
76
77
77
79
79
80
82
88
88
90
97
98
6
Giữ
6.1
6.2
6.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
102
102
104
111
7
Định vị mạng cảm biến . . . . . . . . . . . . . . . . . . . .
7.1 Bài toán định vị mạng cảm biến . . . . . . . . . . . .
7.2 Định vị mạng dựa trên vị trí tương đối . . . . . . . .
7.2.1 Trường hợp không có nút tham chiếu . . . . . .
7.2.2 Trường hợp có nút tham chiếu trong mạng . .
7.2.3 Phương pháp dựa trên vector hướng . . . . . .
7.2.3.1 Trường hợp không có nút tham chiếu
7.2.3.2 Trường hợp có nút tham chiếu . . . .
7.2.4 Phương pháp dựa trên khoảng cách . . . . . .
7.3 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
113
113
113
113
114
115
115
116
117
118
8
Mô hình động học ý kiến . . . . . . . . . . . . . .
8.1 Mô hình French - Degroot . . . . . . . . . . .
8.2 Mô hình Friendkin - Johnsen . . . . . . . . .
8.3 Mô hình Abelson và mô hình Taylor . . . . .
8.4 Mô hình Friendkin - Johnsen đa chiều và một
8.5 Mô hình Hegselmann-Krause . . . . . . . . .
8.6 Mô hình Altafini . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
số mở rộng
. . . . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
122
122
123
125
126
132
135
9
Hệ đồng thuận trọng số ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.1 Đồ thị với trọng số ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
138
138
9.2
9.3
9.4
9.5
Thuật toán đồng thuận trọng số ma trận . .
9.2.1 Điều kiện đồng thuận . . . . . . . . .
9.2.2 Hiện tượng phân cụm . . . . . . . . .
Đồng thuận trọng số ma trận với hệ có leader
9.3.1 Trường hợp leader đứng yên . . . . . .
9.3.2 Trường hợp leader chuyển động . . . .
Đồ thị trọng số ma trận hữu hướng . . . . .
9.4.1 Đồ thị có dạng cây với một gốc ra . .
9.4.2 Đồ thị trọng số ma trận cân bằng . .
Ghi chú và tài liệu tham khảo . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Phụ lục
139
139
141
144
144
146
147
148
148
150
151
A Một số kết quả về lý thuyết ma trận . . . . . . . . . . . . . . .
A.1 Một số định nghĩa và phép toán cơ bản . . . . . . . . . .
A.2 Định thức và ma trận nghịch đảo . . . . . . . . . . . . . .
A.3 Giá trị riêng, vector riêng, định lý Cayley - Hamilton . .
A.4 Định lý Gerschgorin . . . . . . . . . . . . . . . . . . . . .
A.5 Chéo hóa ma trận và dạng Jordan . . . . . . . . . . . . .
A.6 Ma trận hàm mũ . . . . . . . . . . . . . . . . . . . . . . .
A.7 Tích Kronecker . . . . . . . . . . . . . . . . . . . . . . . .
A.8 Ma trận xác định dương và ma trận bán xác định dương .
A.9 Chuẩn của vector và ma trận . . . . . . . . . . . . . . . .
A.10 Lý thuyết Perron-Frobenius . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
152
152
153
153
154
154
155
156
156
157
157
B Lý thuyết điều khiển tuyến tính . .
B.1 Hệ tuyến tính . . . . . . . . .
B.2 Lý thuyết ổn định Lyapunov
B.3 Bổ đề Barbalat . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
158
158
159
160
C Mô phỏng MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.1 Hàm biểu diễn các đội hình 2D và 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.2 Biểu diễn sự thay đổi của đội hình theo thời gian . . . . . . . . . . . . . . . . . . . . . .
162
162
164
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
166
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Danh sách hình vẽ
2.1
2.2
2.3
2.4
2.5
Một số ví dụ về đồ thị vô hướng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ về các lát cắt cạnh của đồ thị 𝐺 gồm 5 đỉnh và 8 cạnh. . . . . . . . . . . . . . . . . .
Ví dụ về các lát cắt đỉnh của đồ thị 𝐺 gồm 5 đỉnh và 8 cạnh. . . . . . . . . . . . . . . . . .
Một số đồ thị định hướng khác nhau của đồ thị 𝐺 trên Hình 2.1(a). . . . . . . . . . . . . .
Các giá trị riêng của L nằm trong đĩa tròn 𝐵 tâm Δ + 𝑗 0, bán kính Δ = max𝑖 deg− (𝑣 𝑖 ) (vùng
màu đỏ). Các trị riêng của −L nằm trong đĩa tròn 𝐵0 đối xứng với 𝐵 qua trục ảo (vùng màu
xanh). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Minh họa Ví dụ 2.2.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7 Đồ thị vô hướng 𝐺1 và 𝐺2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.8 Đồ thị vô hướng 𝐻1 và 𝐻2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Sơ đồ khối thuật toán đồng thuận theo góc nhìn của tác tử 𝑖. . . . . . . . . . . . . . . . . .
3.2 Mô phỏng thuật toán đồng thuận với ba đồ thị khác nhau: 𝐺1 là đồ thị đều gồm 16 đỉnh, mỗi
đỉnh có 3 đỉnh kề, 𝐺2 là đồ thị chu trình gồm 20 đỉnh và 𝐺3 là đồ thị Bucky (quả bóng đá)
gồm 60 đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Mô phỏng chuyển động của các tác tử với luật đồng thuận (3.19). . . . . . . . . . . . . . . .
3.4 Mô phỏng hệ đồng thuận ở Ví dụ 3.3.1. Các biến trạng thái x𝑖 → x 𝑗 khi 𝑡 → +∞. . . . . . .
3.5 Đồ thị 𝐺1 là liên thông mạnh và có chu kỳ bằng 2; Đồ thị 𝐺2 và 𝐺3 là có gốc ra, thành phần
liên thông mạnh chứa gốc ra là không có chu kỳ, trong đó đồ thị 𝐺3 có chứa khuyên; Đồ thị
𝐺4 , 𝐺5 là liên thông mạnh và không có chu kỳ. . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Mô phỏng đối chiếu thuật toán đồng thuận liên tục và không liên tục . . . . . . . . . . . . .
3.7 Sơ đồ khối mô tả thuật toán đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 Mô phỏng hệ đồng thuận gồm 8 tác tử trong Ví dụ 3.5.1. Các biến đầu ra y𝑖 , 𝑖 = 1 , . . . , 8 , dần
đạt tới đồng thuận sau khoảng 100 giây. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Sơ đồ mô tả bộ đồng bộ hóa (3.50). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 Mô phỏng Ví dụ 3.5.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11 Đồ thị ở Bài tập 3.7.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Đồ thị 𝐺 ứng với L. (b) Đồ thị 𝐺0 ứng với L> . (c) Đồ thị 𝐺¯ ứng với L̄ = 𝚪L + L> 𝚪. .
Mô phỏng thuật toán đồng thuận với ba đồ thị hữu hướng khác nhau. . . . . . . . . . . . .
Đồ thị 𝐺 có ba chu trình, trong đó hai chu trình là độc lập. . . . . . . . . . . . . . . . . . .
Mô phỏng minh họa Ví dụ 4.3.2. Những cạnh màu đỏ tạo thành một cây bao trùm của đồ thị.
Các biến tương đối 𝜻(𝑡) → 0 khi 𝑡 → +∞. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Hệ Σ gồm 𝑛 hệ con thụ động với hàm kết nối 𝝓(·). . . . . . . . . . . . . . . . . . . . . . . .
4.6 Mô phỏng mô hình Kuramoto đơn giản cho hệ 6 tác tử ở Ví dụ 4.4.1. . . . . . . . . . . . . .
4.7 Các đồ thị trong Bài tập 4.6.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1
4.2
4.3
4.4
Hệ qui chiếu toàn cục ( 𝑔 Σ), hệ qui chiếu chung (𝑐 Σ), và các hệ qui chiếu cục bộ (𝑖 Σ và 𝑗 Σ).
Mô phỏng thuật toán điều khiển đội hình dựa trên vị trí tuyệt đối. . . . . . . . . . . . . . .
Mô phỏng thuật toán điều khiển đội hình dựa trên vị trí tương đối trong 2D và 3D. . . . .
Một số ví dụ minh họa lý thuyết cứng khoảng cách. . . . . . . . . . . . . . . . . . . . . . .
Minh họa Ví dụ 5.4.2: (a) cấu hình mong muốn, (b) & (c) & (d) & (e) bốn cấu hình khác nhau
thuộc U∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Đội hình đặt trong Ví dụ 5.4.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7 Đội hình gồm 5 tác tử: (a) và (b): p tiến tới một đến một cấu hình mong muốn; (c) và (d) p
tiến tới một cấu hình không mong muốn. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1
5.2
5.3
5.4
5.5
7
9
10
12
20
20
21
21
26
30
34
37
39
42
44
45
47
49
52
57
60
62
62
64
65
69
74
77
78
81
85
86
87
5.8 Ví dụ về tính cứng hướng vi phân: Trong ℝ2 , các đội hình (a), (b), (c) là cứng hướng vi phân,
các đội hình (d), (e), (f) là không cứng hướng vi phân. Trong ℝ3 , các đội hình (g), (h), (i), (j)
là cứng hướng vi phân, các đội hình (k), (l) là không cứng hướng vi phân. . . . . . . . . . .
5.9 Xây dựng đồ thị cứng hướng phổ quát trong ℝ3 xuất phát từ một cạnh nối hai đỉnh. . . . .
5.10 Xây dựng đồ thị cứng hướng phổ quát trong ℝ3 xuất phát từ chu trình 𝐶4 . . . . . . . . . .
5.11 Minh họa phân tích ổn định thuật toán điều khiển đội hình chỉ dựa trên vector hướng: (a) Luật
điều khiển chỉ sử dụng vector hướng; (b) Ví dụ về hai điểm cân bằng đối xứng tâm và có cùng
trọng tâm; (c) 𝜹 luôn nằm trong tập S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.12 Mô phỏng đội hình 4 tác tử dưới luật điều khiển (5.42) trong trường hợp 2D và 3D. . . . .
5.13 Các đồ thị 𝐺1 và 𝐺2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 Minh họa bài toán giữ liên kết: mỗi tác tử có một miền trao đổi thông tin mô tả bởi một hình
tròn tâm tại vị trí tác tử. Nếu hai tác tử nằm trong miền thông tin của nhau thì tồn tại một
cạnh mô tả sự tương tác giữa hai tác tử. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Hàm trọng số 𝑎 𝑖𝑗 (p) = 𝜎𝜔 (𝜖 − 𝑑 𝑖𝑗 (p(𝑡))) tương ứng với một số bộ tham số 𝜔 và 𝜖 khác nhau.
Dễ thấy 𝑎 𝑖𝑗 (p) → 0 khi 𝑑 𝑖𝑗 (k p𝑖 − p 𝑗 k) → 𝛿 = 1. . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Minh họa việc tránh va chạm của các tác tử. . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 Biểu diễn hàm 𝛽 𝑖𝑗 (k p𝑖 − p 𝑗 k) với 𝑑 = 0.75 , 1 , 1.5. . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Mô phỏng luật giữ liên kết trong Ví dụ 6.2.1. . . . . . . . . . . . . . . . . . . . . . . . . . .
6.6 Mô phỏng luật giữ liên kết trong Ví dụ 6.2.2. . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1 Mô tả mạng cảm biến với các nút tham chiếu và các nút mạng thường. Mỗi cạnh của đồ thị
thể hiện luồng thông tin (đo đạc hoặc truyền thông) giữa các nút mạng.Nhiễu 𝜺𝑖𝑗 có thể xuất
hiện trong từng cạnh của đồ thị. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Minh họa định vị mạng cảm biến gồm 10 nút với luật định vị mạng (7.9) . . . . . . . . . .
7.3 Định vị nút 4 dựa vào 3 nút mốc và 3 khoảng cách . . . . . . . . . . . . . . . . . . . . . . .
7.4 Ví dụ đồ thị cứng 3-liên thông có 2 hiên thực hóa trong 2D. Đồ thị này không thừa cứng. .
7.5 Đồ thị trong Bài tập 7.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6 Mạng cảm biến (𝐺, p) trong Bài tập 7.3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1
8.2
8.3
8.4
8.5
8.6
8.7
8.8
8.9
8.10
8.11
8.12
Mô phỏng hệ 4 tác tử với mô hình F-J trong hai trường hợp khác nhau của đồ thị tương tác.
Mô phỏng hệ 10 tác tử với mô hình Taylor
mở rộng . . . . . . . . . . . . . . . . . . . . . . .
Mô phỏng mô hình F-J với ma trận C = 0.8 0.20.3 0.7 . . . . . . . . . . . . . . . . . . .
Mô phỏng mô hình F-J với ma trận C = 0.8 −0.2 − 0.3 0.7 . . . . . . . . . . . . . . . . .
Mô hình Ye 1 khi hệ có và không có định kiến. . . . . . . . . . . . . . . . . . . . . . . . . .
Mô hình Ye 2 khi hệ có và không có định kiến. . . . . . . . . . . . . . . . . . . . . . . . . .
Tăng mức độ liên kết giữa các tác tử làm mô hình Ye 1 mất ổn định trong khi đó sẽ đẩy nhanh
quá trình đồng thuận nhưng không làm thay đổi điểm đồng thuận của mô hình Ye 2. . . . .
Đồ thị mô tả các tác tử trong ví dụ 8.4.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Đồng thuận với ma trận Laplace theo mô hình Ahn: Trái - Chủ đề 1 (𝑥 𝑖,1 , 𝑖 = 1 , . . . , 5). Giữa Chủ đề 2 (𝑥 𝑖,2 , 𝑖 = 1 , . . . , 5). Phải - Chủ đề 3 (𝑥 𝑖,3 , 𝑖 = 1 , . . . , 5). . . . . . . . . . . . . . . .
Mô phỏng mô hình Hegselmann - Krausse với 𝑑 = 0.2 , 0.4 , . . . , 1.2. . . . . . . . . . . . . .
(a) Đồ thị dấu cân bằng cấu trúc; (b) Đồ thị dấu không cân bằng cấu trúc . . . . . . . . .
Mô phỏng mô hình Altafini với các đồ thị trong Ví dụ 8.6.1. . . . . . . . . . . . . . . . . . .
9.1 Ví dụ đồ thị trọng số ma trận trong đó cạnh màu đỏ thể hiện một cạnh xác định dương và
cạnh màu xanh thể hiện một cạnh xác định dương hoặc bán xác định dương. Đồ thị với các
cạnh màu đỏ là một cây bao trùm xác định dương của 𝐺. . . . . . . . . . . . . . . . . . . .
9.2 Đồ thị minh họa hệ bốn tác tử trong Ví dụ 9.2.1. . . . . . . . . . . . . . . . . . . . . . . . .
9.3 Ví dụ 9.2.1: Thay đổi của biến trạng thái của hệ với luật đồng thuận (9.5). . . . . . . . . .
9.4 Đồ thị gồm 5 đỉnh ở Ví dụ 9.2.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5 Ví dụ 9.2.2: Thay đổi của biến trạng thái của hệ với luật đồng thuận (9.5). . . . . . . . . .
89
92
92
93
95
99
102
103
105
105
107
109
114
117
118
118
118
119
124
126
129
130
130
131
131
131
132
134
135
136
139
143
143
144
144
9.6 Ví dụ về đồ thị cây có hướng với đỉnh 1 là gốc ra. . . . . . . . . . . . . . . . . . . . . . . . .
148
C.1 Thay đổi đội hình theo thời gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
165
Danh mục kí hiệu
ℝ
ℂ
ℝ𝑑
ℝ 𝑑×𝑑
𝛼, 𝛽, 𝛾, . . .
𝑎, 𝑏, 𝑐, . . .
a, b, c, . . .
A, B, C, . . .
A, B, C, . . .
𝐴, 𝐵, 𝐶, . . .
𝚥
Re(𝑠), Im(𝑠)
A>
A−1
det(A)
trace(A)
ker(A)
span(a1 , . . . , a𝑛 )
im(A)
dim(A)
diag(a)
blkdiag(A 𝑘 )
rank(A)
kak 𝑙 , kAk 𝑙
k a k, k A k
|·|
1𝑛
0𝑛
I𝑛
⊗
𝑔Σ
𝑖Σ
a𝑖 , b𝑖 , c𝑖 , . . .
a𝑖𝑖 , b𝑖𝑖 , c𝑖𝑖 , . . .
a𝑖𝑗 , b𝑖𝑗 , c𝑖𝑗 , . . .
a𝑖𝑖𝑗 , b𝑖𝑖𝑗 , c𝑖𝑖𝑗 , . . .
a∗ , b∗ , c∗ , . . .
Tập hợp các số thực
Tập hợp các số phức
Không gian các vector 𝑑 chiều
Không gian các ma trận kích thước 𝑑 × 𝑑
Các hằng số
Các đại lượng vô hướng hoặc các hàm nhận giá trị vô hướng
Các vector
Các ma trận
Các không gian vector con hay tập con của ℝ 𝑑
Các đồ thị hoặc các tập hợp liên quan đến đồ thị
Đơn vị ảo
Phần thực, phần ảo của số phức 𝑠
Chuyển vị của ma trận A
Nghịch đảo của ma trận A
Định thức của ma trận A
Vết của ma trận A
Không gian rỗng hay hạt nhân của ma trận A
Không gian tuyến tính sinh bởi các vector a𝑖 , 𝑖 = 1, . . . , 𝑛
Không gian ảnh của ma trận A
Số chiều của không gian A
Ma trận đường chéo có các phần tử trên đường chéo là các phần tử của vector a
Ma trận đường chéo khối với các ma trận A 𝑘 trên đường chéo chính
Hạng của ma trận A
Chuẩn-𝑙 của vector a và ma trận A
Chuẩn-2 (hay chuẩn Euclid) của vector 𝑎 và ma trận A
Giá trị tuyệt đối của một đại lượng vô hướng, hoặc lực lượng của một tập hợp
Vector cột kích thước 𝑛 × 1 với toàn bộ phần tử 1s
Vector cột kích thước 𝑛 × 1 với toàn bộ các phần tử 0, hoặc ma trậ không có
kích thước 𝑛 × 𝑛
Ma trận đơn vị kích thước 𝑛 × 𝑛
Tích Kronecker
Hệ qui chiếu toàn cục
Hệ qui chiếu riêng (địa phương) của tác tử 𝑖
Các vector liên quan tới tác tử 𝑖 viết trong hệ qui chiếu toàn cục 𝑔 Σ
Các vector liên quan tới tác tử 𝑖 viết trong hệ qui chiếu riêng 𝑖 Σ
Các vector biến tương đối giữa hai tác tử 𝑖 và 𝑗 viết trong hệ qui chiếu 𝑔 Σ
Các vector biến tương đối giữa hai tác tử 𝑖 và 𝑗 viết trong hệ qui chiếu 𝑖 Σ
Các vector đặt
Phần I
Cơ sở
1
1.1 Giới thiệu, định nghĩa, và
ví dụ . . . . . . . . . . . . . .
2
1.2 Điều khiển hệ đa tác tử . .
3
1.3 Ghi chú và tài liệu tham
khảo . . . . . . . . . . . . . . .
5
1: Multi-agent systems
2: Smart-grid
Giới thiệu về hệ đa tác tử
1.1 Giới thiệu, định nghĩa, và ví dụ
Các hệ đa tác tử1 đang ngày càng hiện hữu trong đời sống hiện nay
nhờ vào những tiến bộ trong những lĩnh vực khoa học công nghệ khác
nhau. Một số ứng dụng của hệ đa tác tử có thể kể đến các đội hình
máy bay không người lái, mạng cảm biến không dây, hệ thống sản xuất
và cung cấp điện năng2 , cũng như các hệ thống điều khiển giao thông
thông minh. Một hệ đa tác tử bao gồm nhiều hệ thống nhỏ, mỗi hệ
thống nhỏ được gọi là các tác tử. Mỗi tác tử trong hệ có thể chỉ là
phần mềm máy tính hoặc là các hệ thống vật lý cụ thể. Các tác tử
trong hệ tương tác với nhau và với môi trường bên ngoài thông qua
mạng truyền thông, các cảm biến, và cơ cấu chấp hành. Hơn nữa, các
hệ đa tác tử thường được thiết kế để các tác tử hợp tác cùng nhau
nhằm thực hiện một nhiệm vụ phức tạp và thường không thực hiện
được bởi một tác tử đơn lẻ.
Tuy khái niệm về hệ đa tác tử mới được ra đời trong vài thập kỉ gần
đây, các hệ thống đa tác tử (tự nhiên và nhân tạo) đã được quan sát,
phân tích, nghiên cứu bởi nhiều ngành khoa học và kĩ thuật khác nhau
từ rất lâu.
[110]: Reynolds (1987), “Flocks, herds
and schools: A distributed behavioral
model”
[148]: Vicsek andothers (1995), “Novel
type of phase transition in a system
of self-driven particles”
[58]: Jadbabaie andothers (2003),
“Coordination of groups of mobile autonomous agents using nearest neighbor rules”
Đầu tiên có thể kể đến các hiện tượng bầy đàn trong tự nhiên ở chim sẻ,
cá, và côn trùng. Khi di cư lên đầu nguồn để sinh sản, cá hồi bơi thành
đàn lớn để tiết kiệm năng lượng cũng như tăng khả năng sống sót trước
các loài thiên địch. Một đàn châu chấu có thể di chuyển với số lượng
hàng triệu con từ vùng này sang vùng khác, tạo thành hiện tượng mưa
châu chấu có sức tàn phá lớn hơn rất nhiều so với vài trăm cá thể đơn
lẻ. Một hiện tượng thú vị khác là các con đom đóm trong một diện
tích rộng lại có thể đồng điệu chớp sáng cùng với nhau. Nghiên cứu
của các nhà sinh vật học đã chỉ ra rằng, tuy các hiện tượng này thể
hiện bên ngoài khá phức tạp, cơ chế nảy sinh chúng lại khá đơn giản,
và hầu như chỉ dựa trên tương tác giữa các cá thể lân cận trong hệ.
Một mô hình đơn giản lấy cảm hứng từ tự nhiên đã được đề xuất bởi
Reynolds [110]. Trong mô hình này, mỗi tác tử (được gọi là một boid
trong bài báo) di chuyển trong không gian ba chiều tuân theo ba qui
tắc đơn giản là chia tách, căn chỉnh, và gắn kết. Với ba luật đơn giản
trên, Reynolds đã mô phỏng lại được một loạt các hiện tượng quan
sát được trong tự nhiên. Một mô hình khác được đề xuất bởi nhóm
nghiên cứu của nhà vật lý học Vicsek [148] mô tả hệ các tác tử chuyển
động trên mặt phẳng với cùng tốc độ nhưng với hướng khác nhau. Mỗi
tác tử cập nhật hướng đi của mình dựa trên trung bình cộng về góc
hướng của tác tử đó và các tác tử lân cận và một thành phần nhiễu từ
môi trường. Phân tích và mô phỏng cho thấy, nếu như nhiễu là không
đáng kể, theo thời gian, các tác tử dần di chuyển theo cùng một hướng.
Phân tích toán học của các hiện tượng này sau đó được trình bày vào
khoảng năm 2003 dựa trên lý thuyết về các hệ đồng thuận rời rạc [58].
Hiện nay, những hiện tượng tự nhiên thường được nghiên cứu từ quan
1.2 Điều khiển hệ đa tác tử
sát thực tế, sau đó lập mô hình giản lược và phân tích ngược lại dựa
trên toán học. Tương tác lẫn nhau giữa các tác tử trong hệ thường
được mô tả dựa trên cung cụ chính là lý thuyết đồ thị đại số. Lý thuyết
điều khiển là một trong những công cụ đang được sử dụng rộng rãi
trong phân tích các hệ đa tác tử, giúp đưa ra một số kết luận về tính
hội tụ, ổn định, điều khiển được và tính quan sát được. Hơn thế, những
luật tự điều chỉnh trong tự nhiên [self-organized systems] là cảm hứng
để thiết kế lời giải cho các bài toán về hệ đa tác tử nhân tạo.
3
self-organized systems
Ví dụ về hệ đa tác tử nhân tạo có thể kể đến hệ thống sản xuất và
phân phối điện năng. Trong hệ thống này, mỗi nhà máy phát điện lớn
hay mỗi hộ gia đình có máy phát điện cỡ nhỏ (máy phát điện gió, diesel
hay pin mặt trời) đều có thể coi là một tác tử, nhưng qui mô và mức
ảnh ưởng của các tác tử trong hệ khác nhau. Lưới điện đã được xây
dựng và không ngừng mở rộng từ khi điện năng còn chưa được sử dụng
rộng rãi. Việc vận hành và xây dựng lưới điện phần lớn tự phát theo
nhu cầu. Điều này dẫn đến những vấn đề về an toàn và khả năng chống
chịu, phục hồi của hệ thống khi sự cố xảy ra. Nhiều sự kiện xảy ra trên
thế giới đã cho thấy, một sự cố xảy ra tại một nơi gây ảnh hưởng sập
lưới trên diện rộng hay thậm chí toàn bộ lưới điện. Do ảnh hưởng sâu
rộng của lưới điện với đời sống con người, nghiên cứu về hệ thống điện
từ góc độ một hệ đa tác tử là một hướng nghiên cứu đã và đang được
nhiều quan tâm [39, 56].
Một ví dụ khác là các hệ thống giao thông trên đường cao tốc, khi
các hệ thống xe tự lái đi vào hoạt động. Khi lưu thông trên đường cao
tốc, các xe tải cần lập thành một đội xe (platooning) để di chuyển với
cùng vận tốc và giữ khoảng cách giữa các xe định trước. Việc lập đội
xe ngoài đảm bảo tính an toàn và tiết kiệm nhiên liệu còn giúp tăng
lưu lượng xe và hạn chế ách tắc trên đường. Bài toán lập đội xe là một
trường hợp riêng trong bài toán lớn hơn là bài toán về điều khiển đội
hình sẽ được phân tích ở chương 5 [88]. Từ một góc độ khác, ta có thể
coi mỗi con đường cùng lưu lượng xe là một tác tử, và mạng lưới giao
thông là một hệ thống đa tác tử khổng lồ. Giả sử rằng hệ thống đèn
tín hiệu có thể điều khiển lưu lượng và sự luân chuyển xe giữa các con
đường, bài toàn điều khiển giao thông có thể qui về bài toán sản xuất
và phân phối hay rộng hơn là bài toán tối ưu phân tán [79, 62, 80].
Một hướng nghiên cứu đang được quan tâm hiện nay là về các hiện
tượng xã hội học, hay nghiên cứu về các mạng xã hội. Những mô hình
toán phân tích động học của ý kiến được đưa ta từ nửa sau của thế
kỷ 20 (mô hình French-Degroot [48, 35], Abelson [1], hay FriedkinJohnsen [49]) tương đồng với mô hình hệ đồng thuận trong điều khiển.
Mối liên hệ thú vị này, cùng với các hiện tượng xã hội khó dự đoán xảy
ra trên các mạng xã hội nảy sinh các bài toán phân tích các mạng xã
hội. Hơn thế nữa, việc phân tích và dự báo các hiện tượng lan truyền
thông tin có thể được sử dụng chống lại việc sử dụng mạng xã hội vào
các mục đích xấu, ví dụ như lan truyền tin tức giả, hay chi phối dư
luận ở các chính quyền độc tài [104, 103].
1.2 Điều khiển hệ đa tác tử
Từ góc nhìn của hệ thống điều khiển, trọng tâm nghiên cứu về hệ đa
tác tử đi về ba bài toán: (i) mô hình hóa hệ đa tác tử, (ii) phân tích
[39]: Dörfler andothers (2018), “Electrical networks and algebraic graph
theory: Models, properties, and applications”
[56]: Hoang andothers (2017), “A distributed control algorithm via saddle
point dynamics for optimal resource
allocation problem over netwoked systems”
[88]: Oh andothers (2015), “A survey
of multi-agent formation control”
[79]: Nedić andothers (2018), “Distributed optimization for control”
[62]: Kim andothers (2014), “Distributed coordination and control for
a freeway traffic network using consensus algorithms”
[80]: Nguyen andothers (2017), “Distributed learning in a multi-agent potential game”
[48]: French Jr. (1956), “A formal theory of social power”
[35]: DeGroot (1974), “Reaching a
consensus”
[1]: Abelson (1967), “Mathematical
models in social psychology”
[49]: Friedkin (1986), “A formal theory of social power”
[104]: Proskurnikov andothers (2017),
“A tutorial on modeling and analysis
of dynamic social networks: Part I”
[103]: Proskurnikov andothers (2018),
“A tutorial on modeling and analysis
of dynamic social networks: Part II”
4
1 Giới thiệu về hệ đa tác tử
tính hội tụ, ổn định và chất lượng của hệ đa tác tử, (iii) thiết kế luật
điều khiển cũng như tổng hợp các hệ đa tác tử theo những mục tiêu,
giới hạn cho trước.
Một mô hình toán học hữu ích cần phải thể hiện được động học/động
lực học của từng tác tử, sự tương tác giữa các tác tử trong hệ thống,
và sự vận động của tất cả tác tử như một hệ thống thống nhất. Tuy
nhiên, mô hình này cũng cần phải đủ đơn giản cho việc phân tích, thiết
kế luật điều khiển, và mô phỏng. Các hệ đa tác tử, từ định nghĩa, luôn
mang trong mình tính phân tán và phi tập trung. Trong nhiều trường
hợp, việc thiết kế một bộ điều khiển trung tâm để điều khiển mọi tác
tử riêng rẽ là không thực tế. Bởi vậy, nghiên cứu điều khiển hệ đa tác
tử chủ yếu quan tâm tới việc thiết kế các thuật toán, sách lược điều
khiển phi tập trung và phân tán. Tính phi tập trung/phân tán của các
sách lược điều khiển thể hiện ở các điểm sau:
Qui Mô Bài toán điều khiển hệ đa tác tử là một bài toán phức tạp,
với một hay một số yêu cầu khác nhau đối với các biến trạng
thái chung, hay còn gọi là những biến toàn cục của hệ.
Giới Hạn Thông Tin Mỗi tác tử bị giới hạn về khả năng liên lạc, đo
đạc các thông tin toàn cục của hệ. Giả sử mỗi tác tử chỉ có thông
tin về một số biến trạng thái của hệ (biến trạng thái cục bộ), và
có thể trao đổi thông tin với một số lượng nhỏ các tác tử lân cận
khác trong hệ. Những thông tin thu được từ đo đạc và trao đổi
của mỗi tác tử gọi chung là các thông tin địa phương. Hơn nữa,
phạm vi điều khiển của một tác tử cũng bị hạn chế, một tác tử
chỉ có thể tác động tới một số tác tử xung quanh mình.
Luật Điều Khiển Địa Phương Mỗi tác tử đưa ra quyết định điều khiển
dựa trên các thông tin địa phương để giải quyết một bài toán
nhỏ của mình, nhằm đạt được các yêu cầu đối với các biến trạng
thái địa phương.
Động Học/Động Lực Học Toàn Hệ Sự thay đổi/vận động chung của
hệ đa tác tử dựa trên việc các tác tử giải quyết các bài toán nhỏ
một cách độc lập (có thể tuần tự hoặc đồng thời) và thường khác
biệt và phức tạp hơn khá nhiều so với động học/động lực học
của từng tác tử đơn lẻ.
Như vậy, ta có thể nhìn nhận một thuật toán điều khiển phân tán là
một cách phân chia một bài toán lớn thành nhiều bài toán nhỏ, sao
cho các bài toán nhỏ có thể giải quyết bởi mỗi tác tử nhờ các thông
tin địa phương.
So sánh với thiết kế điều khiển tập trung, điều khiển phi tập trung/phân
tán không đòi hỏi có một bộ điều khiển trung tâm mà chỉ dựa trên
việc trao đổi, đo đạc, và tính toán tại địa phương. Điều này giúp giảm
chi phí hiện thực hóa các hệ đa tác tử. Một lợi ích khác của điều khiển
phi tập trung/phân tán là khả năng mở rộng và phát triển hệ đa tác
tử. Do các tác tử được xét tương tự nhau (có thể sai khác nhau về tỉ
lệ), các luật điều khiển phi tập trung/phân tán cho mỗi tác tử là tương
tự nhau và không phụ thuộc vào số lượng tác tử. Điều đó có nghĩa là
ta chỉ cần thiết kế một luật điều khiển phổ quát cho tác tử một lần, và
không cần thay đổi luật điều khiển này khi tăng số lượng tác tử trong
hệ sau này. Cuối cùng, do ta chia nhỏ bài toán lớn thành các bài toán
nhỏ cho các tác tử, ảnh hưởng khi một tác tử không hoàn thành nhiệm
vụ tới toàn hệ sẽ được hạn chế. Chú ý rằng một số nghiên cứu xét tới
1.3 Ghi chú và tài liệu tham khảo
5
điều khiển hệ đa tác tử có phương trình động học/động lực học cụ thể
khác nhau. Luật điều khiển và phân tích trong những trường hợp này
thường bao quát được những sai khác mô hình của từng tác tử trong
hệ.
Đi kèm với những lợi thế kể trên, các phương pháp điều khiển phi tập
trung/phân tán cũng có những hạn chế, khó khăn của mình. Đầu tiên
là khó khăn trong thiết kế luật điều khiển phi tập trung/phân tán. Giả
sử ta có một hệ thống và các yêu cầu cần đạt được. Khi có đầy đủ
thông tin về các biến trạng thái, ta có thể phân tích và thiết kế bộ điều
khiển tập trung một cách dễ dàng dựa trên các phương pháp thiết kế
điều khiển truyền thống. Tuy nhiên, khi thiết kế luật điều khiển phi
tập trung/phân tán, mỗi tác tử bị hạn chế về thông tin, do đó nhiều
khi mặc dù các tác tử hoàn thành nhiệm vụ riêng của mình, hệ đa tác
tử vẫn không đạt được toàn bộ các yêu cầu của bài toán thiết kế. Nói
cách khác, lượng thông tin giảm bớt được đánh đổi bởi chất lượng của
hệ thống và sẽ được minh họa trong bài toán điều khiển đội hình ở
chương sau. Thứ hai, mặc dù các luật điều khiển địa phương thường
đơn giản, động học chung của cả hệ đa tác tử thường phức tạp hơn rất
nhiều. Các hệ đa tác tử trong thực tế là các hệ phi tuyến và có những
yếu tố bất định trong mô hình cũng như bị ảnh hưởng từ môi trường
bên ngoài. Tuy nhiên, những mô hình xấp xỉ hóa, tuyến tính là cơ sở
cho nghiên cứu các mô hình phức tạp hơn.3 Nhìn chung, các hệ đa tác
tử đều có một cơ sở nghiên cứu chung (đại số tuyến tính, lý thuyết đồ
thị,lý thuyết điều khiển) và tùy ứng dụng cụ thể mà có một số công cụ
phân tích, thiết kế được phát triển riêng. Một vấn đề khác là an toàn
của các hệ đa tác tử khi bị tấn công hay khi có tác tử gặp sự cố. Một
tác động địa phương có thể bị nhân lên thành một thảm họa cho cả hệ
thống nếu như hệ không được thiết kế với khả năng phát hiện và cô
lập các sự cố một cách phân tán và theo thời gian thực.
3: Một phần lớn nội dung của tài liệu
này sẽ đề cập tới việc mô hình hóa,
phân tích và thiết kế các hệ đa tác tử
tuyến tính.
1.3 Ghi chú và tài liệu tham khảo
Một điểm đặc biệt của các hệ đa tác tử nhân tạo (lưới điện, hệ giao
thông, mạng xã hội,...) là chúng đã được xây dựng và phát triển trước
khi có một lý thuyết chung về hệ đa tác tử. Sự phát triển của các hệ đa
tác tử sẽ nảy sinh nhu cầu về nghiên cứu về hệ đa tác tử. Để sử dụng
tài liệu này, người đọc cần kiến thức cơ bản về đại số tuyến tính [119],
lý thuyết điều khiển [8, 84, 60], lý thuyết đồ thị [152, 19] và tối ưu
hóa [24]. Một số kiến thức liên quan về đại số tuyến tính, lý thuyết
điều khiển tuyến tính và phi tuyến được trình bày trong phần phụ lục
để tiện tham khảo.
Trong phần I, cơ sở về lý thuyết đồ thị sẽ được trình bày ở chương 2.
Tiếp theo, ở phần II, một số kết quả quan trọng trong phân tích hệ
đồng thuận sẽ được trình bày. Những kết quả về hệ đồng thuận tuyến
tính ở chương 3, mặc dù đơn giản nhưng là khởi điểm cho các nghiên
cứu về các hệ đa tác tử trong hai thập kỉ qua. Những ứng dụng của hệ
đồng thuận trong các bài toán như điều khiển đội hình, giữ liên kết,
tránh va chạm, định vị mạng cảm biến và một số mô hình động học
quan điểm trong nghiên cứu mạng xã hội sẽ được giới thiệu ở phần III,
trong các chương 5–8 nhằm cung cấp những ví dụ cụ thể về việc thiết
kế, phân tích các hệ đa tác tử hiện nay. Các ví dụ mô phỏng, tính toán
[119]: Strang (1988), Linear Algebra
and Its Applications
[8]: Antsaklis andothers (2006), Linear Systems
[84]: Ogata (2009), Modern control
engineering
[60]: Khalil (2002), Nonlinear Systems
[152]: West (1996), Introduction to
graph theory
[19]: Biggs (1993), Algebraic Graph
Theory
[24]: Boyd andothers (2004), Convex
optimization
6
1 Giới thiệu về hệ đa tác tử
viết trên MATLAB/SIMULINK được cung cấp để hỗ trợ độc giả tiếp
cận các kết quả lý thuyết trong tài liệu.
Lý thuyết đồ thị
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh
đó. Tính trừu tượng hóa cao của đồ thị cho phép mô tả nhiều bài toán
trong các lĩnh vực khác nhau. Không quá khi nhận xét rằng, gần như
mọi bài toán về hệ đa tác tử đều ít nhiều dựa trên những kết quả khác
nhau từ lý thuyết đồ thị. Ví dụ, người ta có thể dùng đồ thị để biểu
diễn ảnh hưởng xã hội giữa các thành viên trong một tổ chức, để mô
tả dòng phương tiện giữa các nút giao thông khác nhau, hay để biểu
diễn những luồng thu thập, trao đổi thông tin trong một mạng cảm
biến, . . . .
Mục tiêu của chương này là tổng kết những kết quả của lý thuyết đồ
thị thường dùng trong nghiên cứu về hệ đa tác tử. Đầu tiên, các định
nghĩa và kết quả cơ bản về đồ thị theo lý thuyết tập hợp được giới
thiệu trong mục 2.1. Tiếp theo, mục 2.2 trình bày các cấu trúc đại số
để mô tả đồ thị, ví dụ như ma trận liền kề, ma trận liên thuộc, và ma
trận Laplacian. Hai mục 2.1 và 2.2 là nền tảng để mô tả các hệ đa tác
tử và sẽ được dùng trong phân tích hệ đồng thuận ở Chương 3.
2.1 Đồ thị
2
2.1 Đồ
2.1.1 Đồ
2.1.2 Đồ
2.1.3 Đồ
thị
thị
thị
thị
........
vô hướng .
hữu hướng
có trọng số
.
.
.
.
.
.
.
.
.
.
.
.
. 7
. 7
. 10
. 11
2.2 Đại số đồ thị . . . . . . . . 11
2.2.1 Một số ma trận của đồ
thị . . . . . . . . . . . . . . . 11
2.2.2 Ma trận Laplace của đồ
thị hữu hướng . . . . . . . 17
2.3
Ghi chú và tài liệu tham
khảo . . . . . . . . . . . . . . 20
2.4
Bài tập . . . . . . . . . . . . 21
1: Bởi vậy, với đồ thị vô hướng 𝐺, ta
chỉ cần liệt kê (𝑣 𝑖 , 𝑣 𝑗 ) là đủ hiểu rằng
cả (𝑣 𝑖 , 𝑣 𝑗 ) và (𝑣 𝑗 , 𝑣 𝑖 ) đều thuộc 𝐸.
𝑣4
𝑣3
𝑣1
𝑣2
2.1.1 Đồ thị vô hướng
Một đồ thị đơn, hữu hạn, vô hướng (hay gọi ngắn gọn là một đồ thị)
𝐺 = (𝑉 , 𝐸), gồm một tập đỉnh 𝑉 = {𝑣 1 , 𝑣2 , . . . , 𝑣 𝑛 } với |𝑉 | = 𝑛 > 0
phần tử, và một tập cạnh 𝐸 = {(𝑣 𝑖 , 𝑣 𝑗 )| 𝑖, 𝑗 = 1 , . . . , 𝑛, 𝑖 ≠ 𝑗} ∈ 𝑉 × 𝑉
với |𝐸| = 𝑚 phần tử. Ta gọi 𝑣 𝑖 ∈ 𝑉 và (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸 tương ứng là môt
đỉnh và một cạnh của đồ thị 𝐺. Do đồ thị là vô hướng nên nếu có
(𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸 thì cũng có (𝑣 𝑗 , 𝑣 𝑖 ) ∈ 𝐸.1 Khi có nhiều đồ thị khác nhau, ta
kí hiệu tập đỉnh và tập cạnh tương ứng của đồ thị 𝐺 bởi 𝑉(𝐺) và 𝐸(𝐺).
Trong một số ngữ cảnh, để đơn giản, ta có thể kí hiệu đỉnh 𝑣 𝑖 bởi 𝑖,
cạnh (𝑣 𝑖 , 𝑣 𝑗 ) bởi (𝑖, 𝑗) hoặc 𝑒 𝑖𝑗 .
Mỗi đồ thị 𝐺 có một biểu diễn hình học tương ứng, gồm các vòng tròn
nhỏ biểu diễn các đỉnh 𝑣 𝑖 ∈ 𝑉, và các đoạn thẳng (hay các cung) nối
𝑣 𝑖 với 𝑣 𝑗 nếu (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸.
(a) 𝐺1
𝑣1
𝑣5
𝑣2
𝑣3
𝑣4
(b) 𝐺2
𝑣10
Ví dụ 2.1.1 Trên hình 2.1:
I Đồ thị 𝐺1 = (𝑉1 , 𝐸1 ) có tập đỉnh 𝑉1 = {𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 } và tập
cạnh 𝐸1 = {(𝑣1 , 𝑣2 ), (𝑣2 , 𝑣3 ), (𝑣3 , 𝑣4 ), (𝑣4 , 𝑣1 ), (𝑣1 , 𝑣3 )}.
𝑣50
𝑣20
I Đồ thị 𝐺2 = (𝑉2 , 𝐸2 ) có tập đỉnh 𝑉2 = {𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 , 𝑣 5 } và tập
cạnh 𝐸2 = {(𝑣1 , 𝑣2 ), (𝑣2 , 𝑣3 ), (𝑣3 , 𝑣4 ), (𝑣4 , 𝑣5 ), (𝑣5 , 𝑣1 )}.
I Đồ thị 𝐺3 = (𝑉3 , 𝐸3 ) có tập đỉnh 𝑉3 = {𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 , 𝑣 5 } và tập
cạnh 𝐸3 = {(𝑣1 , 𝑣3 ), (𝑣3 , 𝑣5 ), (𝑣5 , 𝑣2 ), (𝑣2 , 𝑣4 ), (𝑣4 , 𝑣1 )}.
Giả sử (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸(𝐺) thì ta nói 𝑣 𝑖 , 𝑣 𝑗 là hai đỉnh kề nhau (kí hiệu
𝑣 𝑖 ∼ 𝑣 𝑗 ), và đỉnh 𝑣 𝑖 gọi là liên thuộc với cạnh (𝑣 𝑖 , 𝑣 𝑗 ). Hai cạnh phân
𝑣30
𝑣40
(c) 𝐺3
Hình 2.1: Một số ví dụ về đồ thị vô
hướng.
8
2 Lý thuyết đồ thị
biệt có chung một đỉnh gọi là hai cạnh kề. Hai đồ thị là đẳng cấu nếu
tồn tại một song ánh giữa hai tập đỉnh mà bảo toàn quan hệ liền kề.
Từ nay, ta không phân biệt giữa hai đồ thị đẳng cấu . Nếu 𝐺 và 𝐻 là
hai đồ thị đẳng cấu , ta viết 𝐺 𝐻 hoặc đơn giản là 𝐺 = 𝐻.
Ví dụ 2.1.2 Xét hai đồ thị 𝐺2 và 𝐺3 trên Hình 2.1(b) và (c). Định
nghĩa ánh xạ 𝑓 : 𝑉2 → 𝑉3 như sau: 𝑓 (𝑣1 ) = 𝑣10 , 𝑓 (𝑣2 ) = 𝑣30 , 𝑓 (𝑣 3 ) = 𝑣 50 ,
𝑓 (𝑣4 ) = 𝑣20 , và 𝑓 (𝑣 5 ) = 𝑣 40 . Dễ thấy 𝑓 là một song ánh giữa 𝑉1 và 𝑉2 .
Hơn nữa, có thể kiểm tra:
I
I
I
I
I
(𝑣1 , 𝑣2 ) ∈
(𝑣2 , 𝑣3 ) ∈
(𝑣3 , 𝑣4 ) ∈
(𝑣4 , 𝑣5 ) ∈
(𝑣5 , 𝑣1 ) ∈
𝐸1
𝐸1
𝐸1
𝐸1
𝐸1
thì
thì
thì
thì
thì
( 𝑓 (𝑣1 ),
( 𝑓 (𝑣3 ),
( 𝑓 (𝑣3 ),
( 𝑓 (𝑣4 ),
( 𝑓 (𝑣5 ),
𝑓 (𝑣2 )) = (𝑣10 , 𝑣30 ) ∈
𝑓 (𝑣3 )) = (𝑣30 , 𝑣50 ) ∈
𝑓 (𝑣4 )) = (𝑣50 , 𝑣20 ) ∈
𝑓 (𝑣5 )) = (𝑣20 , 𝑣40 ) ∈
𝑓 (𝑣1 )) = (𝑣40 , 𝑣10 ) ∈
𝐸2 ,
𝐸2 ,
𝐸2 ,
𝐸2 ,
𝐸2 .
Như vậy 𝑓 bảo toàn quan hệ liền kề và ta đi đến kết luận rằng
𝐺2 𝐺3 .
Một đồ thị 𝐺0 = (𝑉 0 , 𝐸0) là một đồ thị con của 𝐺 = (𝑉 , 𝐸) nếu 𝑉 0 ⊆ 𝑉
và 𝐸0 ⊂ 𝐸. Trong trường hợp này ta viết 𝐺0 ⊆ 𝐺. Nếu 𝑉 0 ⊂ 𝑉 thì đồ
thị (𝑉 0 , 𝐸 ∩ 𝑉 0 × 𝑉 0) là một đồ thị con được dẫn xuất từ 𝑉 0, và kí hiệu
bởi 𝐺[𝑉 0]. Đồ thị 𝐻 là một đồ thị con dẫn xuất của 𝐺 nếu 𝐻 ⊂ 𝐺 và
𝐻 = 𝐺[𝑉(𝐻)].
Tập láng giềng của đỉnh 𝑣 𝑖 của đồ thị 𝐺 được định nghĩa bởi 𝑁(𝑣 𝑖 ) =
{𝑣 𝑗 | (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸}. Bậc của đỉnh 𝑣 𝑖 là số phần tử của tập láng giềng
𝑁(𝑣 𝑖 ), tức là deg(𝑣 𝑖 ) = |𝑁(𝑣 𝑖 )|. Ta cũng có thể định nghĩa bậc của một
đỉnh trong đồ thị là số cạnh liên thuộc với nó. Khi chỉ có một đồ thị
𝐺, ta có thể dùng kí hiệu rút gọn 𝑁(𝑣 𝑖 ) = 𝑁𝑖 và deg(𝑣 𝑖 ) = deg𝑖 . Khi có
nhiều đồ thị khác nhau, ta thêm kí hiệu đồ thị như một chỉ số dưới. Ví
dụ nếu 𝐻 là một đồ thị con được dẫn xuất của 𝐺 và 𝑣 ∈ 𝐻 thì
𝑁𝐻 (𝑣) = 𝑁𝐺 (𝑣) ∩ 𝑉(𝐻), và deg𝐻 (𝑣) = |𝑁𝐻 (𝑣)|.
Với tập 𝑉 0 ⊂ 𝑉, ta định nghĩa tập 𝑁(𝑉 0) = ∪{𝑁(𝑣)| 𝑣 ∈ 𝑉 0 }. Bậc tối
thiểu của các đỉnh của 𝐺 được kí hiệu bởi 𝛿(𝐺) và bậc tối đa được kí
hiệu bởi Δ(𝐺). Nếu 𝛿(𝐺) = Δ(𝐺) = 𝑘, tức là mọi đỉnh của 𝐺 đều có bậc
𝑘, thì 𝐺 gọi là một đồ thị chính quy bậc 𝑘 (hoặc đồ thị đều bậc 𝑘). Đồ
thị chính quy mạnh là đồ thị chính quy mà mọi cặp đỉnh kề nhau đều
có số láng giềng chung bằng nhau và mọi cặp đỉnh không kề đều có số
láng giềng chung bằng nhau. Đồ thị chính quy bậc 𝑘 = |𝑉 | − 1 = 𝑛 − 1
gọi là đồ thị đầy đủ bậc 𝑛, kí hiệu bởi 𝐾 𝑛 .
Nếu 𝐸0 ⊂ 𝐸(𝐺) thì 𝐺 − 𝐸0 , (𝑉 , 𝐸(𝐺) \ 𝐸0) gọi là đồ thị thu hẹp từ 𝐺 sau
khi ta xóa đi các cạnh trong 𝐸0. Tương tự, nếu 𝑉 0 ⊂ 𝑉(𝐺) thì 𝐺 − 𝑉 0 là
đồ thị thu hẹp từ 𝐺 sau khi xóa đi các đỉnh thuộc 𝑉 0, với qui ước rằng
khi một đỉnh 𝑣 ∈ 𝑉 0 bị xóa đi thì các cạnh kề với 𝑣 cũng bị xóa đi. Nói
cách khác, nếu 𝐺 = (𝑉 , 𝐸) thì 𝐺 − 𝑉 0 = (𝑉 \ 𝑉 0 , 𝐸 ∩ (𝑉 \ 𝑉 0) × (𝑉 \ 𝑉 0)).
Nếu 𝑉 0 = {𝑣}, ta thường viết 𝐺 − 𝑣 thay cho 𝐺 − {𝑣}. Tương tự, ta viết
𝐺 − 𝑒 thay cho 𝐺 − {𝑒}. Với đồ thị 𝐻 ⊂ 𝐺, ta có thể viết 𝐺 − 𝐻 thay
cho 𝐺 − 𝑉(𝐻). Nếu cạnh 𝑒 ∈ 𝑉 × 𝑉 \ 𝐸 thì đồ thị mở rộng từ 𝐺 bằng
cách thêm vào cạnh 𝑒 được kí hiệu là 𝐺 + 𝑒 = (𝑉 , 𝐸 ∪ {𝑒}). Ta cũng có
những định nghĩa tương tự cho đồ thị mở rộng nhờ thêm đỉnh.