Giáo trình Điều khiển hệ đa tác tử: Phần 1 - Trịnh Hoàng Minh, Nguyễn Minh Hiệu

Chia sẻ: Lăng Mộng Như | Ngày: | Loại File: PDF | Số trang:82

Thêm vào BST

Báo xấu

35
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 của giáo trình "Điều khiển hệ đa tác tử" trình bày những nội dung về: giới thiệu hệ đa tác tử; lý thuyết đồ thị; hệ đồng thuận; thuật toán đồng thuận; phân tích hệ đồng thuận theo phương pháp Lyapunov và quá trình đồng thuận cạnh;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Điều khiển hệ đa tác tử: Phần 1 - Trịnh Hoàng Minh, Nguyễn Minh Hiệu

* d ij * d ij Agent i Agent j ĐIỀU KHIỂN HỆ ĐA TÁC TỬ Trịnh Hoàng Minh, Nguyễn Minh Hiệu Agent j g ji Desired g ij * g ji * position Trajectory g ij Initial formation Desired formation Initial Agent i 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: trinhhoangminhbk@gmail.com
Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Danh mục kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x I Cơ sở 1 1 Giới thiệu về hệ đa tác tử . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 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 2 Lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Đồ thị vô hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.2 Đồ thị hữu hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.3 Đồ thị có trọng số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Đại số đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Một số ma trận của đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1.1 Ma trận bậc và ma trận kề . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1.2 Ma trận liên thuộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1.3 Ma trận Laplace của đồ thị vô hướng . . . . . . . . . . . . . . . . . . . 14 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 II Hệ đồng thuận 24 3 Thuật toán đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1 Hệ đồng thuận gồm các tác tử tích phân bậc nhất . . . . . . . . . . . . . . . . . . . . . 25 3.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1.2 Trường hợp tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.3 Một số trường hợp riêng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Đồng thuận với các tác tử tích phân bậc hai . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Hệ đồng thuận tuyến tính tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Hệ đồng thuận tuyến tính không liên tục . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.1 Mô hình và điều kiện đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.2 Liên hệ với mô hình hệ đồng thuận liên tục . . . . . . . . . . . . . . . . . . . . . 40 3.5 Đồng bộ đầu ra hệ tuyến tính dựa trên quan sát trạng thái . . . . . . . . . . . . . . . . 43 3.5.1 Đồng bộ hóa dựa trên bộ quan sát trạng thái Luenberger . . . . . . . . . . . . . 43 3.5.2 Bộ quan sát kết hợp đồng bộ hóa đầu ra . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.7 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Phân tích hệ đồng thuận theo phương pháp Lyapunov và quá trình đồng thuận cạnh . . . . . 55 4.1 Hàm bất đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 Phân tích theo phương pháp Lyapunov . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3 Quá trình đồng thuận cạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.4 Đồng bộ hóa đầu ra các hệ thụ động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.6 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 III Một số ứng dụng của hệ đa tác tử 71 5 Điều khiển đội hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.2 Điều khiển đội hình dựa trên vị trí tuyệt đối . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 Điều khiển đội hình dựa trên vị trí tương đối . . . . . . . . . . . . . . . . . . . . . . . . 77 5.3.1 Trường hợp tác tử là khâu tích phân bậc nhất . . . . . . . . . . . . . . . . . . . 77 5.3.2 Trường hợp tác tử là khâu tích phân bậc hai . . . . . . . . . . . . . . . . . . . . 79 5.4 Điều khiển đội hình dựa trên khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.4.1 Lý thuyết cứng khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.4.2 Luật điều khiển đội hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.5 Điều khiển đội hình dựa trên vector hướng . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.5.1 Lý thuyết cứng hướng trên ℝ 𝑑 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.5.2 Điều khiển đội hình cứng hướng vi phân . . . . . . . . . . . . . . . . . . . . . . . 90 5.6 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.7 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6 Giữ liên kết và tránh va chạm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.1 Giữ liên kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.2 Tránh va chạm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.3 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7 Định vị mạng cảm biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.1 Bài toán định vị mạng cảm biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.2 Định vị mạng dựa trên vị trí tương đối . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.2.1 Trường hợp không có nút tham chiếu . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.2.2 Trường hợp có nút tham chiếu trong mạng . . . . . . . . . . . . . . . . . . . . . 114 7.2.3 Phương pháp dựa trên vector hướng . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.2.3.1 Trường hợp không có nút tham chiếu . . . . . . . . . . . . . . . . . . . 115 7.2.3.2 Trường hợp có nút tham chiếu . . . . . . . . . . . . . . . . . . . . . . . 116 7.2.4 Phương pháp dựa trên khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.3 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 8 Mô hình động học ý kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 8.1 Mô hình French - Degroot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 8.2 Mô hình Friendkin - Johnsen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 8.3 Mô hình Abelson và mô hình Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 8.4 Mô hình Friendkin - Johnsen đa chiều và một số mở rộng . . . . . . . . . . . . . . . . . 126 8.5 Mô hình Hegselmann-Krause . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.6 Mô hình Altafini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 9 Hệ đồng thuận trọng số ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.1 Đồ thị với trọng số ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.2 Thuật toán đồng thuận trọng số ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . 139 9.2.1 Điều kiện đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 9.2.2 Hiện tượng phân cụm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 9.3 Đồng thuận trọng số ma trận với hệ có leader . . . . . . . . . . . . . . . . . . . . . . . . 144 9.3.1 Trường hợp leader đứng yên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 9.3.2 Trường hợp leader chuyển động . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.4 Đồ thị trọng số ma trận hữu hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 9.4.1 Đồ thị có dạng cây với một gốc ra . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4.2 Đồ thị trọng số ma trận cân bằng . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.5 Ghi chú và tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Phụ lục 151 A Một số kết quả về lý thuyết ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 A.1 Một số định nghĩa và phép toán cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 A.2 Định thức và ma trận nghịch đảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.3 Giá trị riêng, vector riêng, định lý Cayley - Hamilton . . . . . . . . . . . . . . . . . . . 153 A.4 Định lý Gerschgorin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.5 Chéo hóa ma trận và dạng Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.6 Ma trận hàm mũ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 A.7 Tích Kronecker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 A.8 Ma trận xác định dương và ma trận bán xác định dương . . . . . . . . . . . . . . . . . . 156 A.9 Chuẩn của vector và ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 A.10 Lý thuyết Perron-Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 B Lý thuyết điều khiển tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 B.1 Hệ tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 B.2 Lý thuyết ổn định Lyapunov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 B.3 Bổ đề Barbalat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 C Mô phỏng MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 C.1 Hàm biểu diễn các đội hình 2D và 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 C.2 Biểu diễn sự thay đổi của đội hình theo thời gian . . . . . . . . . . . . . . . . . . . . . . 164 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Danh sách hình vẽ 2.1 Một số ví dụ về đồ thị vô hướng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Ví dụ về các lát cắt cạnh của đồ thị 𝐺 gồm 5 đỉnh và 8 cạnh. . . . . . . . . . . . . . . . . . 9 2.3 Ví dụ về các lát cắt đỉnh của đồ thị 𝐺 gồm 5 đỉnh và 8 cạnh. . . . . . . . . . . . . . . . . . 10 2.4 Một số đồ thị định hướng khác nhau của đồ thị 𝐺 trên Hình 2.1(a). . . . . . . . . . . . . . 12 2.5 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). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Minh họa Ví dụ 2.2.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Đồ thị vô hướng 𝐺1 và 𝐺2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.8 Đồ thị vô hướng 𝐻1 và 𝐻2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 Sơ đồ khối thuật toán đồng thuận theo góc nhìn của tác tử 𝑖. . . . . . . . . . . . . . . . . . 26 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 Mô phỏng chuyển động của các tác tử với luật đồng thuận (3.19). . . . . . . . . . . . . . . . 34 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 𝑡 → +∞. . . . . . . 37 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ỳ. . . . . . . . . . . . . . . . . . . . . . . . . . 39 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 . . . . . . . . . . . . . 42 3.7 Sơ đồ khối mô tả thuật toán đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.9 Sơ đồ mô tả bộ đồng bộ hóa (3.50). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.10 Mô phỏng Ví dụ 3.5.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.11 Đồ thị ở Bài tập 3.7.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1 (a) Đồ thị 𝐺 ứng với L. (b) Đồ thị 𝐺0 ứng với L> . (c) Đồ thị 𝐺¯ ứng với L ¯ = 𝚪L + L> 𝚪. . 57 4.2 Mô phỏng thuật toán đồng thuận với ba đồ thị hữu hướng khác nhau. . . . . . . . . . . . . 60 4.3 Đồ thị 𝐺 có ba chu trình, trong đó hai chu trình là độc lập. . . . . . . . . . . . . . . . . . . 62 4.4 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 𝑡 → +∞. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.5 Hệ Σ gồm 𝑛 hệ con thụ động với hàm kết nối 𝝓(·). . . . . . . . . . . . . . . . . . . . . . . . 64 4.6 Mô phỏng mô hình Kuramoto đơn giản cho hệ 6 tác tử ở Ví dụ 4.4.1. . . . . . . . . . . . . . 65 4.7 Các đồ thị trong Bài tập 4.6.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.1 Hệ qui chiếu toàn cục ( 𝑔 Σ), hệ qui chiếu chung (𝑐 Σ), và các hệ qui chiếu cục bộ (𝑖 Σ và 𝑗 Σ). 74 5.2 Mô phỏng thuật toán điều khiển đội hình dựa trên vị trí tuyệt đối. . . . . . . . . . . . . . . 77 5.3 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. . . . . 78 5.4 Một số ví dụ minh họa lý thuyết cứng khoảng cách. . . . . . . . . . . . . . . . . . . . . . . 81 5.5 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∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.6 Đội hình đặt trong Ví dụ 5.4.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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. . . . . . . . . . . 89 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. . . . . 92 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 . . . . . . . . . . 92 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 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. . . . . 95 5.13 Các đồ thị 𝐺1 và 𝐺2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 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ử. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 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. . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.3 Minh họa việc tránh va chạm của các tác tử. . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.4 Biểu diễn hàm 𝛽 𝑖𝑗 (k p𝑖 − p 𝑗 k) với 𝑑 = 0.75 , 1 , 1.5. . . . . . . . . . . . . . . . . . . . . . . . . 105 6.5 Mô phỏng luật giữ liên kết trong Ví dụ 6.2.1. . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.6 Mô phỏng luật giữ liên kết trong Ví dụ 6.2.2. . . . . . . . . . . . . . . . . . . . . . . . . . . 109 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ị. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 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) . . . . . . . . . . 117 7.3 Định vị nút 4 dựa vào 3 nút mốc và 3 khoảng cách . . . . . . . . . . . . . . . . . . . . . . . 118 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. . 118 7.5 Đồ thị trong Bài tập 7.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 7.6 Mạng cảm biến (𝐺, p) trong Bài tập 7.3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.1 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. 124 8.2 Mô phỏng hệ 10 tác tử với mô hình Taylor mở rộng . . . . . . . . . . . . . . . . . . . . . . . 126 8.3 Mô phỏng mô hình F-J với ma trận C = 0.8 0.20.3 0.7 . . . . . . . . . . . . . . . . . . . 129 8.4 Mô phỏng mô hình F-J với ma trận C = 0.8 −0.2 − 0.3 0.7 . . . . . . . . . . . . . . . . . 130 8.5 Mô hình Ye 1 khi hệ có và không có định kiến. . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.6 Mô hình Ye 2 khi hệ có và không có định kiến. . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.7 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. . . . . 131 8.8 Đồ thị mô tả các tác tử trong ví dụ 8.4.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.9 Đồ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). . . . . . . . . . . . . . . . 132 8.10 Mô phỏng mô hình Hegselmann - Krausse với 𝑑 = 0.2 , 0.4 , . . . , 1.2. . . . . . . . . . . . . . 134 8.11 (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 . . . . . . . . . 135 8.12 Mô phỏng mô hình Altafini với các đồ thị trong Ví dụ 8.6.1. . . . . . . . . . . . . . . . . . . 136 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 𝐺. . . . . . . . . . . . . . . . . . . . 139 9.2 Đồ thị minh họa hệ bốn tác tử trong Ví dụ 9.2.1. . . . . . . . . . . . . . . . . . . . . . . . . 143 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). . . . . . . . . . 143 9.4 Đồ thị gồm 5 đỉnh ở Ví dụ 9.2.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 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). . . . . . . . . . 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 ℝ 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 a, b, c, . . . Các vector A, B, C, . . . Các ma trận A, B, C, . . . 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 Re(𝑠), Im(𝑠) Phần thực, phần ảo của số phức 𝑠 A> Chuyển vị của ma trận A A−1 Nghịch đảo của ma trận A det(A) Định thức của ma trận A trace(A) Vết của ma trận A ker(A) Không gian rỗng hay hạt nhân của ma trận A span(a1 , . . . , a𝑛 ) Không gian tuyến tính sinh bởi các vector a𝑖 , 𝑖 = 1, . . . , 𝑛 im(A) Không gian ảnh của ma trận A dim(A) Số chiều của không gian A diag(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 blkdiag(A 𝑘 ) Ma trận đường chéo khối với các ma trận A 𝑘 trên đường chéo chính rank(A) Hạng của ma trận A kak 𝑙 , kAk 𝑙 Chuẩn-𝑙 của vector a và ma trận A k a k, k A k 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 1𝑛 Vector cột kích thước 𝑛 × 1 với toàn bộ phần tử 1s 0𝑛 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 𝑛 × 𝑛 I𝑛 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ử 𝑖 a𝑖 , b𝑖 , c𝑖 , . . . Các vector liên quan tới tác tử 𝑖 viết trong hệ qui chiếu toàn cục 𝑔 Σ a𝑖𝑖 , b𝑖𝑖 , c𝑖𝑖 , . . . Các vector liên quan tới tác tử 𝑖 viết trong hệ qui chiếu riêng 𝑖 Σ a𝑖𝑗 , b𝑖𝑗 , c𝑖𝑗 , . . . Các vector biến tương đối giữa hai tác tử 𝑖 và 𝑗 viết trong hệ qui chiếu 𝑔 Σ a𝑖𝑖𝑗 , b𝑖𝑖𝑗 , c𝑖𝑖𝑗 , . . . Các vector biến tương đối giữa hai tác tử 𝑖 và 𝑗 viết trong hệ qui chiếu 𝑖 Σ a∗ , b∗ , c∗ , . . . Các vector đặt
Phần I Cơ sở
1 Giới thiệu về hệ đa tác tử 1.1 Giới thiệu, định nghĩa, và ví dụ . . . . . . . . . . . . . . 2 1.1 Giới thiệu, định nghĩa, và ví dụ 1.2 Điều khiển hệ đa tác tử . . 3 1.3 Ghi chú và tài liệu tham Các hệ đa tác tử1 đang ngày càng hiện hữu trong đời sống hiện nay khảo . . . . . . . . . . . . . . . 5 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 1: Multi-agent systems thông minh. Một hệ đa tác tử bao gồm nhiều hệ thống nhỏ, mỗi hệ 2: Smart-grid 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. Đầ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 [110]: Reynolds (1987), “Flocks, herds Reynolds [110]. Trong mô hình này, mỗi tác tử (được gọi là một boid and schools: A distributed behavioral trong bài báo) di chuyển trong không gian ba chiều tuân theo ba qui model” 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 [148]: Vicsek andothers (1995), “Novel nghiên cứu của nhà vật lý học Vicsek [148] mô tả hệ các tác tử chuyển type of phase transition in a system động trên mặt phẳng với cùng tốc độ nhưng với hướng khác nhau. Mỗi of self-driven particles” 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. [58]: Jadbabaie andothers (2003), 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 “Coordination of groups of mobile au- khoảng năm 2003 dựa trên lý thuyết về các hệ đồng thuận rời rạc [58]. tonomous agents using nearest neigh- bor rules” 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ử 3 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 self-organized systems để thiết kế lời giải cho các bài toán về hệ đa tác tử nhân tạo. 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]. [39]: D¨ orfler andothers (2018), “Elec- Một ví dụ khác là các hệ thống giao thông trên đường cao tốc, khi trical networks and algebraic graph các hệ thống xe tự lái đi vào hoạt động. Khi lưu thông trên đường cao theory: Models, properties, and ap- plications” tốc, các xe tải cần lập thành một đội xe (platooning) để di chuyển với [56]: Hoang andothers (2017), “A dis- 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 tributed control algorithm via saddle 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 point dynamics for optimal resource 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 allocation problem over netwoked sys- tems” 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ể [88]: Oh andothers (2015), “A survey coi mỗi con đường cùng lưu lượng xe là một tác tử, và mạng lưới giao of multi-agent formation control” 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]. [79]: Nedi´c andothers (2018), “Dis- Một hướng nghiên cứu đang được quan tâm hiện nay là về các hiện tributed optimization for control” 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 [62]: Kim andothers (2014), “Dis- tributed coordination and control for toán phân tích động học của ý kiến được đưa ta từ nửa sau của thế a freeway traffic network using con- kỷ 20 (mô hình French-Degroot [48, 35], Abelson [1], hay Friedkin- sensus algorithms” Johnsen [49]) tương đồng với mô hình hệ đồng thuận trong điều khiển. [80]: Nguyen andothers (2017), “Dis- 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 tributed learning in a multi-agent po- tential game” 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ã [48]: French Jr. (1956), “A formal the- 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 ory of social power” 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 [35]: DeGroot (1974), “Reaching a các mục đích xấu, ví dụ như lan truyền tin tức giả, hay chi phối dư consensus” luận ở các chính quyền độc tài [104, 103]. [1]: Abelson (1967), “Mathematical models in social psychology” [49]: Friedkin (1986), “A formal the- ory of social power” 1.2 Điều khiển hệ đa tác tử [104]: Proskurnikov andothers (2017), “A tutorial on modeling and analysis of dynamic social networks: Part I” 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 [103]: Proskurnikov andothers (2018), 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 “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ở 3: Một phần lớn nội dung của tài liệu 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 này sẽ đề cập tới việc mô hình hóa, tử đều có một cơ sở nghiên cứu chung (đại số tuyến tính, lý thuyết đồ phân tích và thiết kế các hệ đa tác 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ụ tuyến tính. 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. 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], [119]: Strang (1988), Linear Algebra lý thuyết điều khiển [8, 84, 60], lý thuyết đồ thị [152, 19] và tối ưu and Its Applications hóa [24]. Một số kiến thức liên quan về đại số tuyến tính, lý thuyết [8]: Antsaklis andothers (2006), Lin- điều khiển tuyến tính và phi tuyến được trình bày trong phần phụ lục ear Systems để tiện tham khảo. [84]: Ogata (2009), Modern control engineering Trong phần I, cơ sở về lý thuyết đồ thị sẽ được trình bày ở chương 2. [60]: Khalil (2002), Nonlinear Systems Tiếp theo, ở phần II, một số kết quả quan trọng trong phân tích hệ [152]: West (1996), Introduction to graph theory đồng thuận sẽ được trình bày. Những kết quả về hệ đồng thuận tuyến [19]: Biggs (1993), Algebraic Graph tính ở chương 3, mặc dù đơn giản nhưng là khởi điểm cho các nghiên Theory cứu về các hệ đa tác tử trong hai thập kỉ qua. Những ứng dụng của hệ [24]: Boyd andothers (2004), Convex đồng thuận trong các bài toán như điều khiển đội hình, giữ liên kết, optimization 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
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ị 2 Đồ 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 2.1 Đồ thị ........ . . . . 7 đó. Tính trừu tượng hóa cao của đồ thị cho phép mô tả nhiều bài toán 2.1.1 Đồ thị vô hướng . . . . . 7 trong các lĩnh vực khác nhau. Không quá khi nhận xét rằng, gần như 2.1.2 Đồ thị hữu hướng . . . . 10 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 2.1.3 Đồ thị có trọng số . . . . 11 nhau từ lý thuyết đồ thị. Ví dụ, người ta có thể dùng đồ thị để biểu 2.2 Đại số đồ thị . . . . . . . . 11 diễn ảnh hưởng xã hội giữa các thành viên trong một tổ chức, để mô 2.2.1 Một số ma trận của đồ tả dòng phương tiện giữa các nút giao thông khác nhau, hay để biểu thị . . . . . . . . . . . . . . . 11 2.2.2 Ma trận Laplace của đồ diễn những luồng thu thập, trao đổi thông tin trong một mạng cảm thị hữu hướng . . . . . . . 17 biến, . . . . 2.3 Ghi chú và tài liệu tham 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 đồ khảo . . . . . . . . . . . . . . 20 thị thường dùng trong nghiên cứu về hệ đa tác tử. Đầu tiên, các định 2.4 Bài tập . . . . . . . . . . . . 21 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 1: Bởi vậy, với đồ thị vô hướng 𝐺, ta trận Laplacian. Hai mục 2.1 và 2.2 là nền tảng để mô tả các hệ đa tác chỉ cần liệt kê (𝑣 𝑖 , 𝑣 𝑗 ) là đủ hiểu rằng tử và sẽ được dùng trong phân tích hệ đồng thuận ở Chương 3. cả (𝑣 𝑖 , 𝑣 𝑗 ) và (𝑣 𝑗 , 𝑣 𝑖 ) đều thuộc 𝐸. 2.1 Đồ thị 𝑣4 𝑣3 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 𝑣1 𝑣2 phần tử, và một tập cạnh 𝐸 = {(𝑣 𝑖 , 𝑣 𝑗 )| 𝑖, 𝑗 = 1 , . . . , 𝑛, 𝑖 ≠ 𝑗} ∈ 𝑉 × 𝑉 (a) 𝐺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ó 𝑣1 (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸 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à 𝐸(𝐺). 𝑣2 𝑣5 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 𝑣3 𝑣4 nhỏ biểu diễn các đỉnh 𝑣 𝑖 ∈ 𝑉, và các đoạn thẳng (hay các cung) nối (b) 𝐺2 𝑣 𝑖 với 𝑣 𝑗 nếu (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸. 𝑣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 𝑣20 𝑣50 cạnh 𝐸1 = {(𝑣1 , 𝑣2 ), (𝑣2 , 𝑣3 ), (𝑣3 , 𝑣4 ), (𝑣4 , 𝑣1 ), (𝑣1 , 𝑣3 )}. 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 𝑣30 𝑣40 cạnh 𝐸3 = {(𝑣1 , 𝑣3 ), (𝑣3 , 𝑣5 ), (𝑣5 , 𝑣2 ), (𝑣2 , 𝑣4 ), (𝑣4 , 𝑣1 )}. (c) 𝐺3 Hình 2.1: Một số ví dụ về đồ thị vô Giả sử (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸(𝐺) thì ta nói 𝑣 𝑖 , 𝑣 𝑗 là hai đỉnh kề nhau (kí hiệu hướng. 𝑣 𝑖 ∼ 𝑣 𝑗 ), và đỉnh 𝑣 𝑖 gọi là liên thuộc với cạnh (𝑣 𝑖 , 𝑣 𝑗 ). Hai cạnh phân
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 (𝑣1 , 𝑣2 ) ∈ 𝐸1 thì ( 𝑓 (𝑣1 ), 𝑓 (𝑣2 )) = (𝑣10 , 𝑣30 ) ∈ 𝐸2 , I (𝑣2 , 𝑣3 ) ∈ 𝐸1 thì ( 𝑓 (𝑣3 ), 𝑓 (𝑣3 )) = (𝑣30 , 𝑣50 ) ∈ 𝐸2 , I (𝑣3 , 𝑣4 ) ∈ 𝐸1 thì ( 𝑓 (𝑣3 ), 𝑓 (𝑣4 )) = (𝑣50 , 𝑣20 ) ∈ 𝐸2 , I (𝑣4 , 𝑣5 ) ∈ 𝐸1 thì ( 𝑓 (𝑣4 ), 𝑓 (𝑣5 )) = (𝑣20 , 𝑣40 ) ∈ 𝐸2 , I (𝑣5 , 𝑣1 ) ∈ 𝐸1 thì ( 𝑓 (𝑣5 ), 𝑓 (𝑣1 )) = (𝑣40 , 𝑣10 ) ∈ 𝐸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.