Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Toán học Giáo trình điều khiển hệ đa tác tử...

Tài liệu Giáo trình điều khiển hệ đa tác tử

.PDF
186
1
111

Mô tả:

* 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.
- Xem thêm -

Tài liệu liên quan