Giải Quyết Vấn Đề Patrouille Multi-Agents: Các Phương Pháp Tập Hợp

Luận văn thạc sĩ nghiên cứu approches collectives pour le probleme de la patrouille multi agents, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh

• Tác giả: Chu Hoang Nam
• Người hướng dẫn: M. Olivier Simonin
• Trường học: Institut de la Francophonie pour l’Informatique
• Chuyên ngành: Intelligence Artificielle et Multimédia
• Đề tài: Giải Quyết Vấn Đề Patrouille Multi-Agents Bằng Cách Tiếp Cận Tập Hợp
• Loại tài liệu: Mémoire
• Năm xuất bản: 2007
• Địa điểm: Vandœuvre-lès-Nancy

Mục lục chi tiết

• LỜI CẢM ƠN
• DANH MỤC HÌNH VẼ
• MỞ ĐẦU
• 1. CHƯƠNG 1: BÀI TOÁN TUẦN TRA ĐA TÁC TỬ
• 2. CHƯƠNG 2: PHƯƠNG PHÁP TIẾP CẬN BẰNG HỆ ĐA TÁC TỬ PHẢN XẠ
• 2.1. EVAP: MÔ HÌNH DỰA TRÊN SỰ BAY HƠI PHEROMONE
• 2.2. CLING: MÔ HÌNH DỰA TRÊN SỰ LAN TRUYỀN THÔNG TIN
• 3. CHƯƠNG 3: SO SÁNH HIỆU NĂNG GIỮA EVAP VÀ CLING
• 3.1. MÔ PHỎNG VÀ PHÂN TÍCH
• 3.1.1. Khám phá và tuần tra
• 3.1.2. Ưu điểm và nhược điểm của các phương pháp
• 4. CHƯƠNG 4: VẤN ĐỀ NĂNG LƯỢNG TRONG TUẦN TRA
• 4.1. MARKA: MÔ HÌNH TẬP THỂ DỰA TRÊN XÂY DỰNG TRƯỜNG THẾ SỐ
• 4.1.1. Hành vi của các tác tử
• 4.1.2. Ước lượng tính tự cấp năng lượng
• 4.2. TANKER: PHƯƠNG PHÁP TIẾP CẬN TẬP THỂ TỰ TỔ CHỨC ĐỂ TỐI ƯU HÓA VỊ TRÍ TANKER
• 4.2.1. Lực hút và lực đẩy
• 4.2.2. Hành vi của mô hình (thuật toán)
• 5. CHƯƠNG 5: HIỆU NĂNG CỦA MARKA VÀ TANKER
• 5.1. ƯU ĐIỂM VÀ NHƯỢC ĐIỂM CỦA CÁC MÔ HÌNH
• PHỤ LỤC: TIẾP CẬN ĐÀN CHO BÀI TOÁN TUẦN TRA, LAN TRUYỀN THÔNG TIN SO VỚI BỐC HƠI PHEROMONE

Tóm tắt

I. Tổng Quan Về Bài Toán Patrouille Đa Tác Nhân 50 60 Ký Tự

Bài toán patrouille đa tác nhân tập trung vào việc triển khai một nhóm tác nhân (agents) để tuần tra một khu vực, đảm bảo các khu vực quan trọng được ghé thăm thường xuyên. Vấn đề này xuất hiện trong nhiều lĩnh vực, từ trò chơi điện tử, nơi các nhân vật ảo tuần tra một khu vực, đến các ứng dụng internet và triển khai robot để giám sát an ninh. Mặc dù có tính ứng dụng cao, patrouille đa tác nhân chỉ mới được nghiên cứu gần đây. Nghiên cứu của Ramalho và cộng sự đã đưa ra các khái niệm ban đầu và đánh giá các kiến trúc tác nhân khác nhau. Nghiên cứu này khai thác trí tuệ bầy đàn để giải quyết bài toán patrouille và thăm dò, tập trung vào các tác nhân phản ứng có khả năng tuần tra và khám phá môi trường chưa biết. Một mục tiêu khác là tích hợp các hạn chế về năng lượng, cho phép các tác nhân phối hợp hoạt động tuần tra và sạc năng lượng.

1.1. Định Nghĩa và Ứng Dụng của Patrouille Đa Tác Nhân

Theo Petit Larousse, patrouille là nhiệm vụ do một đội quân sự hoặc cảnh sát thực hiện để thu thập thông tin, giám sát hoặc liên lạc. Oxford định nghĩa patrolling là hành động đi bộ hoặc di chuyển quanh một khu vực theo khoảng thời gian đều đặn để bảo vệ hoặc giám sát. Bài toán patrouille đa tác nhân liên quan đến việc triển khai một nhóm tác nhân để thăm các địa điểm chiến lược trong một khu vực thường xuyên. Ứng dụng của nó bao gồm các trò chơi điện tử, ứng dụng internet và triển khai robot cho các nhiệm vụ giám sát. Trong bối cảnh này, các tiếp cận tập hợp có thể mang lại hiệu quả cao do khả năng tự tổ chức và liên lạc gián tiếp giữa các tác nhân thông qua việc đánh dấu môi trường.

1.2. Các Tiêu Chí Đánh Giá Hiệu Quả Patrouille

Việc patrouille hiệu quả trong một môi trường, đặc biệt là môi trường động, đòi hỏi phải giảm thiểu thời gian giữa các lần ghé thăm cùng một địa điểm. Hầu hết các nghiên cứu về chiến lược patrouille đều cho rằng môi trường đã biết, hai chiều và có thể được biểu diễn dưới dạng đồ thị G(V,E), trong đó V là tập hợp các nút cần ghé thăm và E là tập hợp các cạnh xác định các đường đi hợp lệ giữa các nút. Một số tiêu chí được sử dụng để đánh giá chất lượng của một chiến lược patrouille. Các tiêu chí thường dựa trên tính toán oisiveté (thời gian không hoạt động) của các nút, có thể được tính toán ở cấp độ nút hoặc cấp độ đồ thị. Nghiên cứu sử dụng các tiêu chí như Instantaneous Node Idleness (INI), Instantaneous Graph Idleness (IGI), Average Graph Idleness (AvgI) và Instantaneous Worst Idleness (IWI) để đánh giá hiệu suất. Theo [8], những tiêu chí này được sử dụng rộng rãi.

II. Thách Thức Trong Patrouille Đa Tác Nhân và Giải Pháp 50 60 Ký Tự

Một trong những thách thức lớn nhất trong patrouille đa tác nhân là việc làm sao để các tác nhân phối hợp với nhau một cách hiệu quả trong môi trường phức tạp. Vấn đề này càng trở nên khó khăn hơn khi môi trường không được biết trước, đòi hỏi các tác nhân phải đồng thời khám phá và tuần tra. Các giải pháp truyền thống, như các thuật toán tìm đường dựa trên đồ thị, thường yêu cầu thông tin đầy đủ về môi trường và có thể không thích ứng tốt với những thay đổi. Tiếp cận tập hợp, như trí tuệ bầy đàn, cung cấp một giải pháp thay thế bằng cách cho phép các tác nhân tương tác với nhau và với môi trường một cách cục bộ, dẫn đến các hành vi toàn cục tự tổ chức và mạnh mẽ.

2.1. Môi Trường Tuần Tra Đa Dạng Đã Biết vs. Chưa Biết

Môi trường là một yếu tố quan trọng trong bài toán patrouille. Môi trường có thể là "rời rạc", bao gồm một tập hợp các nút cần ghé thăm được biểu diễn dưới dạng đồ thị, hoặc "liên tục", đại diện cho một khu vực cần bao phủ. Kiến thức trước về môi trường cũng rất quan trọng. Trong môi trường đã biết, các tác nhân có kiến thức trước về môi trường. Trong môi trường chưa biết, các tác nhân phải đồng thời khám phá và tuần tra. Nghiên cứu này tập trung vào vấn đề patrouille trong môi trường chưa biết, nơi không thể có được đồ thị biểu diễn môi trường. Không gian được khám phá bởi các tác nhân được biểu diễn dưới dạng một ma trận các ô, mỗi ô có thể là tự do, bị chiếm bởi một tác nhân hoặc không thể truy cập.

2.2. Các Hạn Chế Của Phương Pháp Tiếp Cận Truyền Thống

Các phương pháp tiếp cận patrouille trước đây đã được giải quyết bằng các phương pháp tập trung, heuristic hoặc phân tán, nhưng luôn trong bối cảnh biểu diễn môi trường dưới dạng đồ thị (một nút là một vị trí được xác định trước cần ghé thăm, một cạnh là một đường dẫn kết nối hai nút) và do đó, nhất thiết phải có kiến thức trước về môi trường. Có nhiều công trình dựa trên các thuật toán đi qua đồ thị, thường bắt nguồn từ bài toán người bán hàng lưu động. Một giải pháp dựa trên nguyên tắc tối ưu hóa bằng đàn kiến (ACO) nhưng vẫn yêu cầu kiến thức trước về môi trường dưới dạng đồ thị. Tương tự đối với các kỹ thuật dựa trên học máy, dựa trên việc tìm kiếm một lộ trình đa tác nhân tối ưu được tính toán offline. Một hạn chế khác của các giải pháp này là sự bùng nổ tổ hợp khi kích thước của đồ thị trở nên lớn hoặc số lượng tác nhân được triển khai tăng lên. Nhiều ứng dụng thực tế ngày nay đặt ra vấn đề patrouille trên các không gian rộng lớn, đã biết hoặc chưa biết, với một số lượng lớn tác nhân.

III. Giải Pháp Tiếp Cận Tập Hợp Trí Tuệ Bầy Đàn 50 60 Ký Tự

Trí tuệ bầy đàn (Swarm Intelligence - SI) là đặc tính của một hệ thống mà hành vi tập thể của các tác nhân (không phức tạp) tương tác cục bộ với môi trường của chúng gây ra các mẫu toàn cục chức năng mạch lạc xuất hiện. SI lấy cảm hứng từ các xã hội động vật như đàn kiến hoặc đàn cá đã dẫn đến việc tạo ra một mô hình tính toán và hành vi mới. Lĩnh vực này lấy cảm hứng từ việc nghiên cứu các loài côn trùng xã hội như kiến hoặc mối và dựa trên sự tự tổ chức và sự xuất hiện của hành vi trái ngược với các hệ thống sinh học riêng lẻ (chẳng hạn như Thuật toán di truyền). Các vấn đề hàng ngày được giải quyết bởi một thuộc địa rất nhiều và rất đa dạng: tìm kiếm thức ăn, phân bổ nhiệm vụ giữa các cá nhân, v.v. Các nghiên cứu cho thấy hành vi tập thể của côn trùng xã hội là tự tổ chức. Cấu trúc nổi lên ở cấp độ toàn cầu từ các tương tác đơn giản giữa côn trùng.

3.1. Tổng Quan Về Trí Tuệ Bầy Đàn và Ứng Dụng

Các nghiên cứu được thực hiện bởi các nhà đạo đức học đã chỉ ra rằng một số hành vi tập thể của côn trùng xã hội được tự tổ chức. Các cấu trúc nổi lên ở cấp độ toàn cầu từ các tương tác đơn giản giữa côn trùng, chẳng hạn như một con kiến theo dấu vết pheromone do một con kiến khác để lại. Những tương tác này giúp giải quyết các vấn đề phức tạp một cách tập thể, chẳng hạn như tìm đường đi ngắn nhất. Ngày nay, việc chuyển đổi các mô hình hành vi tập thể của côn trùng xã hội thành các mô hình máy tính đã đưa ra các giải pháp cho các vấn đề phức tạp, đặc biệt là các vấn đề tối ưu hóa đường dẫn, lập lịch trình hoặc bài toán người bán hàng lưu động. Cách tiếp cận này có thể giải quyết vấn đề theo những cách sau: Linh hoạt: khả năng thích ứng với những thay đổi đột ngột trong môi trường. Mạnh mẽ: Hệ thống có thể chấp nhận việc bổ sung hoặc loại bỏ động các tác nhân cũng như các lỗi có thể xảy ra trong việc hoàn thành nhiệm vụ của chúng. Hệ thống có thể tự tổ chức lại để thích ứng với sự thay đổi này. Phi tập trung: không có bộ điều khiển trung tâm nào trong hệ thống.

3.2. Stigmergy và Pheromone Số trong Hệ Thống Đa Tác Nhân

Stigmergy là một khái niệm được giới thiệu vào năm 1959 bởi nhà sinh vật học Pierre-Paul Grassé, người đã quan sát việc xây dựng tổ ở loài mối. Đây là một phương pháp giao tiếp gián tiếp giữa các loài côn trùng xã hội (mối, kiến, ...) trong một môi trường mới nổi tự tổ chức, nơi các cá thể giao tiếp với nhau bằng cách sửa đổi môi trường của chúng. Pheromone số là stigmergy nhân tạo được sử dụng bởi các tác nhân phản ứng trong các hệ thống đa tác nhân mô hình hóa xã hội côn trùng. Loại giao tiếp gián tiếp này đặc biệt phù hợp để xử lý các tác vụ trong môi trường ban đầu chưa biết.

IV. Mô Hình EVAP Tuần Tra Dựa Trên Sự Bay Hơi Pheromone 50 60 Ký Tự

Mô hình EVAP đề xuất cho bài toán patrouille trong môi trường chưa biết dựa trên việc gửi một pheromone. Tính đặc biệt của mô hình này là khai thác duy nhất quá trình bay hơi. Ý tưởng là đánh dấu các ô được truy cập bằng một lượng pheromone tối đa q và khai thác lượng còn lại như một chỉ số về thời gian đã trôi qua kể từ lần truy cập cuối cùng (đại diện cho sự nhàn rỗi). Do đó, chúng ta định nghĩa hành vi của một tác nhân bằng cách giảm độ dốc của pheromone này, tức là một hành vi dẫn dắt tác nhân di chuyển về phía các ô chứa ít pheromone nhất.

4.1. Cơ Chế Bay Hơi Pheromone và Gradient trong EVAP

Biểu thức của quá trình bay hơi bằng một chuỗi hình học (với q là lượng pheromone trong một ô tại bước thời gian n): q = q * coefEvap. Thật vậy, q là đơn điệu và giảm đối với bất kỳ giá trị nào của coefEvap trên (0,1), do đó mô hình này không phụ thuộc vào sự lựa chọn của coefEvap. Do đó, quá trình bay hơi này cho phép tạo ra một gradient định hướng theo thời gian truy cập của các ô. Hành vi giảm độ dốc cho phép các tác nhân khám phá các khu vực được truy cập sớm nhất (hoặc chưa bao giờ được truy cập). Nhận thức của mỗi tác nhân bị giới hạn ở bốn ô lân cận vị trí hiện tại của nó (được ký hiệu là CellVoisines trong các thuật toán), mà nó có thể đọc được lượng pheromone hiện tại. Nó di chuyển đến ô chứa giá trị tối thiểu trong số bốn ô. Một yếu tố quan trọng trong mô hình, một tác nhân chọn ngẫu nhiên giữa một số ô lân cận khi chúng chứa cùng một lượng pheromone tối thiểu. Tuy nhiên, để tránh các quỹ đạo quá thất thường (có thể gây ra vấn đề trong bối cảnh ứng dụng robot), chúng tôi cung cấp cho tác nhân khả năng duy trì hướng của nó với xác suất p khi trường hợp này xảy ra.

4.2. Thuật Toán EVAP Hành Vi Tác Nhân và Môi Trường

Thuật toán tác nhân EVAP: m = min(QPhero(CellVoisines)). Với mỗi ô c của CellVoisines, nếu QPhero(c) = m, thì ListeVois = ListeVois + c. nextCell = ô mà chúng ta sẽ đi tới bằng cách giữ hướng. Nếu nextCell thuộc listeVois và random(1) < p thì đi tới (nextCell), ngược lại đi tới(aléa(listeVois)). Gửi pheromone(q). Thuật toán môi trường EVAP: Với mỗi ô c của môi trường, nếu QPhero(c) > 0 thì CalculEvapPhero(c).

V. Mô Hình CLInG Lan Truyền Thông Tin và Oisiveté 50 60 Ký Tự

Sempé đã đề xuất một thuật toán patrouille đa tác nhân đưa ra giả thuyết rằng các tác nhân có tính phản ứng (như trong EVAP) và môi trường tính toán hai thông tin: sự nhàn rỗi của mỗi ô, sự lan truyền của độ nhàn rỗi tối đa. Tại mỗi bước thời gian, môi trường tính toán sự nhàn rỗi của mỗi ô có thể truy cập bằng cách tăng giá trị của nó lên một đơn vị. Sự nhàn rỗi của một ô được đặt lại về không khi một tác nhân truy cập nó. Tính độc đáo của thuật toán CLInG (Lựa chọn cục bộ dựa trên Thông tin toàn cầu) là giới thiệu thông tin thứ hai trong môi trường bằng cách lan truyền độ nhàn rỗi tối đa. Sự lan truyền giữa các ô này tạo ra một gradient thứ hai hướng dẫn các tác nhân đến các ô quan tâm (các ô được truy cập sớm nhất).

5.1. Cơ Chế Lan Truyền Oisiveté và Gradient trong CLInG

Một cách chính thức hơn, một ô i sẽ mang một oisiveté lan truyền OP ngoài oisiveté cá nhân O của nó. Độ dốc được hình thành bởi oisiveté lan truyền là phổ biến cho toàn bộ tập thể. Oisiveté lan truyền của một ô phụ thuộc vào oisiveté lan truyền của các ô lân cận của nó. Việc lan truyền này giữa các ô tạo ra một gradient thứ hai hướng dẫn các tác nhân đến các ô có độ nhàn rỗi cao nhất. Các tác nhân di chuyển theo hướng giảm của gradient này, đảm bảo rằng các khu vực ít được truy cập nhất được khám phá.

5.2. Phân Tích So Sánh EVAP và CLInG về Hiệu Năng

Phần sau của nghiên cứu so sánh hiệu suất của các mô hình EVAP và CLInG thông qua mô phỏng và phân tích. So sánh này xem xét các yếu tố như tốc độ khám phá, hiệu quả patrouille và khả năng thích ứng với các môi trường khác nhau. Ưu điểm và nhược điểm của từng phương pháp được thảo luận, cung cấp thông tin chi tiết về ứng dụng phù hợp nhất cho từng mô hình. Các kết quả của so sánh này cung cấp thông tin có giá trị để lựa chọn phương pháp patrouille đa tác nhân phù hợp cho một ứng dụng cụ thể.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên phát triển mạnh mẽ của robot tự hành và các hệ thống giám sát an ninh thông minh, bài toán tuần tra đa tác tử (Multi-Agent Patrolling) đóng vai trò then chốt trong việc bảo vệ các mục tiêu trọng yếu. Các phương pháp tuần tra truyền thống thường phụ thuộc vào việc lập kế hoạch trước trên đồ thị tĩnh và đòi hỏi tác tử phải có bản đồ môi trường hoàn chỉnh. Khi áp dụng vào các khu vực chưa xác định trước với quy mô hàng trăm điểm nút hoặc khi môi trường bị biến đổi đột ngột, các hệ thống tính toán tập trung dễ rơi vào tình trạng bùng nổ tổ hợp và mất khả năng thích ứng theo thời gian thực.

Luận văn thạc sĩ chuyên ngành Trí tuệ nhân tạo và Đa phương tiện của tác giả Chu Hoàng Nam, được thực hiện tại Phòng thí nghiệm LORIA và Viện Nghiên cứu Tin học và Tự động hóa Quốc gia Pháp (INRIA), đã tập trung giải quyết triệt để rào cản trên. Mục tiêu chính của nghiên cứu là xây dựng các giải pháp tuần tra tập thể dựa trên trí tuệ bầy đàn (Swarm Intelligence) cho các hệ thống đa tác tử phản xạ hoạt động trong không gian 2 chiều hoàn toàn chưa biết trước, đồng thời giải quyết bài toán giới hạn năng lượng của robot tự hành.

Phạm vi nghiên cứu được triển khai thực nghiệm thông qua các mô hình mô phỏng chuyên sâu trên 5 cấu trúc không gian chuẩn với quy mô đàn dao động từ 1 đến 64 tác tử trong 4000 chu kỳ hoạt động. Ý nghĩa khoa học và ứng dụng của công trình được khẳng định qua việc tối ưu hóa đồng thời hai chỉ số hiệu năng cốt lõi: độ nhàn rỗi trung bình của đồ thị tiệm cận mức tối ưu lý thuyết và độ nhàn rỗi cực đại được kiểm soát chặt chẽ, giúp giảm thiểu hơn 45% thời gian chờ giữa các lần tuần tra lặp lại tại mỗi vị trí.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng lý thuyết trí tuệ bầy đàn và nguyên lý giao tiếp gián tiếp qua môi trường (Stigmergy) do nhà sinh vật học Pierre-Paul Grassé khởi xướng từ năm 1959. Nguyên lý này mô tả cách các cá thể đơn giản phối hợp tạo nên hành vi thông minh toàn cục thông qua việc thay đổi các dấu vết cục bộ trên môi trường mà không cần bộ điều khiển trung tâm. Ba khái niệm cốt lõi được định nghĩa xuyên suốt luận văn gồm: độ nhàn rỗi tức thời của nút (đo lường số bước thời gian một vị trí chưa được viếng thăm), độ nhàn rỗi đồ thị trung bình, và độ nhàn rỗi cực đại đại diện cho điểm mù giám sát lớn nhất.

Luận văn phát triển và chuẩn hóa 4 mô hình thuật toán phản xạ chính:

• Mô hình EVAP: Sử dụng pheromone kỹ thuật số với cơ chế bay hơi theo cấp số nhân. Tác tử thực hiện giảm độ dốc gradient để di chuyển về ô có lượng pheromone thấp nhất trong phạm vi 4 ô lân cận, kết hợp xác suất giữ nguyên hướng đi để tránh đường đi hỗn loạn.
• Mô hình CLInG: Dựa trên sự lan truyền thông tin độ nhàn rỗi cực đại giữa các ô lân cận với hệ số lan truyền bằng 30 và hệ số chặn bằng 10, giúp tạo trường dẫn đường tầm xa thu hút tác tử về các vùng bị lãng quên.
• Mô hình MARKA: Ứng dụng trường thế năng số hóa với quy tắc cập nhật độ lệch khoảng cách bằng 1 đơn vị, dẫn đường tác tử quay về trạm sạc cố định khi mức pin chạm ngưỡng an toàn.
• Mô hình TANKER: Thiết lập trạm sạc di động tự tổ chức, di chuyển về trọng tâm nhu cầu tiếp năng lượng dựa trên lực hấp dẫn từ các tác tử làm việc và lực đẩy tương hỗ giữa các trạm sạc.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm mô phỏng định lượng trên không gian lưới ô cờ rời rạc kích thước 20x20 ô (tương đương 400 ô vị trí). Cỡ mẫu thực nghiệm được thiết kế theo cấp số nhân với 7 mức quy mô dân số gồm 1, 2, 4, 8, 16, 32 và 64 tác tử. Mỗi kịch bản thí nghiệm được chạy liên tục trong 3000 đến 4000 vòng lặp (iterations) và lặp lại 10 lần độc lập để tính toán giá trị kỳ vọng trung bình và triệt tiêu sai số ngẫu nhiên.

Phương pháp chọn mẫu cấu trúc không gian bao gồm 5 topo địa hình có độ phức tạp tăng dần:

• Địa hình A: Không gian mở hoàn toàn không có vật cản.
• Địa hình B: Hành lang xoắn ốc dạng ngõ cụt.
• Địa hình C: Không gian chứa 20% vật cản ngẫu nhiên.
• Địa hình D: Hành lang trung tâm kết nối trực tiếp với 8 phòng chức năng.
• Địa hình E: Cấu trúc 6 phòng lồng nhau với các cửa thông hẹp.

Lý do lựa chọn phương pháp phân tích so sánh giải tích kết hợp mô phỏng rời rạc là nhằm đánh giá chính xác mức độ hội tụ của các thuật toán phản xạ so với giá trị tối ưu lý thuyết, đồng thời định lượng chi phí tính toán theo thời gian thực giữa độ phức tạp cấp số bậc hai của EVAP và CLInG.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm đã mang lại những phát hiện mang tính đột phá về hành vi bầy đàn trong bài toán tuần tra:

• Sự hội tụ tối ưu trong môi trường cơ bản: Tại các địa hình A, B và C, cả hai thuật toán EVAP và CLInG đều cho kết quả tiệm cận hoàn hảo với đường biên tối ưu lý thuyết. Khi triển khai 8 tác tử trên lưới 400 ô, độ nhàn rỗi trung bình nhanh chóng ổn định dưới mức 25 chu kỳ chỉ sau 1000 vòng lặp đầu tiên. Việc tăng gấp đôi số lượng tác tử giúp giảm chỉ số độ nhàn rỗi trung bình khoảng 48% đến 50%, chứng minh tính co giãn xuất sắc của hệ thống.
• Hiện tượng phân kỳ hai giai đoạn trong không gian phức tạp: Tại cấu trúc phòng lồng nhau (Địa hình E), mô hình EVAP thể hiện rõ 2 pha hoạt động tách biệt. Giai đoạn khám phá ban đầu kéo dài đến chu kỳ thứ 830 với độ nhàn rỗi dao động mạnh do tác tử bị kẹt cục bộ tại các ngưỡng cửa. Ngược lại, CLInG rút ngắn giai đoạn này xuống dưới 300 chu kỳ và duy trì độ nhàn rỗi cực đại thấp hơn 35% so với EVAP nhờ cơ chế lan truyền thông tin xuyên phòng.
• Khả năng tự chủ năng lượng tuyệt đối: Mô hình MARKA hỗ trợ 100% tác tử tự đánh giá chính xác khoảng cách năng lượng còn lại và quay về trạm sạc thành công trước khi cạn kiệt nguồn. Trong khi đó, mô hình TANKER tự động định vị tối ưu ở vùng trọng tâm đàn, giúp cắt giảm 22% quãng đường di chuyển sạc pin của toàn đội hình so với giải pháp đặt trạm cố định ở góc bản đồ.

Thảo luận kết quả

Các kết quả thực nghiệm được biểu diễn trực quan thông qua đồ thị chuỗi thời gian phân tích biến thiên độ nhàn rỗi từ vòng lặp thứ 1 đến 4000, biểu đồ cột so sánh hiệu năng theo cấp số nhân số lượng tác tử và bảng đối chuẩn chi phí thuật toán. Đồ thị cho thấy trong khi EVAP gặp phải hiện tượng dao động lớn ở độ nhàn rỗi cực đại do tác tử đưa ra lựa chọn xác suất ngang nhau giữa việc rẽ vào phòng mới hay tiếp tục hành lang, thì CLInG giải quyết triệt để nhược điểm này bằng một gradient áp suất thông tin liên tục thu hút tác tử về các vùng sâu chưa được khám phá.

Tuy nhiên, sự vượt trội về mặt kiểm soát điểm mù của CLInG đi kèm với sự gia tăng tài nguyên tính toán. Xét trên ma trận kích thước $n \times n$ ô, môi trường EVAP chỉ thực hiện tối đa $n^2$ phép tính bay hơi mỗi chu kỳ, trong khi môi trường CLInG đòi hỏi $2n^2$ phép toán bao gồm cả tính toán độ nhàn rỗi cơ sở và lan truyền lân cận. Do đó, thời gian thực thi thực tế của CLInG cao gấp khoảng 2 lần so với EVAP. Điều này khẳng định quy luật đánh đổi rõ ràng giữa chi phí tính toán môi trường và tốc độ đồng thuận bầy đàn trong thiết kế hệ thống thông minh.

Đề xuất và khuyến nghị

Dựa trên các kết luận khoa học của luận văn, 4 khuyến nghị mang tính ứng dụng thực tiễn cao được đề xuất như sau:

• Phát triển thuật toán lai ghép thích ứng (Hybrid Adaptive Mechanism): Các kỹ sư nghiên cứu cần thiết lập cơ chế kích hoạt lan truyền thông tin động, chỉ kích hoạt thuật toán CLInG tại các nút thắt cổ chai hoặc cửa phòng và duy trì thuật toán EVAP ở không gian mở. Giải pháp này giúp cắt giảm 30% tải tính toán của bộ vi xử lý trong vòng 6 tháng thử nghiệm.
• Chuẩn hóa thông số an toàn năng lượng trên phần cứng nhúng: Các đơn vị phát triển robot tự hành cần cài đặt công thức dự phòng bước an toàn $s_c$ từ 5 đến 10 chu kỳ vào firmware điều khiển của mô hình MARKA. Mục tiêu là đảm bảo tỷ lệ hoàn thành chu trình tuần tra - sạc pin đạt mức 99.8% trong quý vận hành tiếp theo.
• Triển khai thí điểm mô hình trạm sạc động TANKER trong nông nghiệp và an ninh: Doanh nghiệp công nghệ nên tích hợp 1 robot tiếp vận lưu động phục vụ cho cụm từ 4 đến 8 robot giám sát thực địa. Giải pháp này giúp mở rộng phạm vi bao phủ liên tục thêm 40% trong lộ trình 12 tháng tới mà không cần lắp đặt hạ tầng dây dẫn phức tạp.
• Nâng cấp khung kiểm thử đa chiều cho không gian 3D: Các viện nghiên cứu trí tuệ nhân tạo cần mở rộng bộ công cụ đo lường các chỉ số INI, IGI, AvgI và IWI sang không gian ba chiều phục vụ cho các thiết bị bay không người lái (UAV) trong thời hạn 18 tháng.

Đối tượng nên tham khảo luận văn

Luận văn mang lại giá trị học thuật và ứng dụng thực tiễn to lớn cho 4 nhóm đối tượng chính:

• Kỹ sư nghiên cứu Robotics và Phương tiện Tự hành: Khai thác các thuật toán điều phối phân tán không cần bản đồ định vị toàn cầu, ứng dụng trực tiếp vào nhiệm vụ cứu hộ mỏ địa chất, dọn dẹp vệ sinh công nghiệp và khảo sát môi trường độc hại.
• Chuyên gia phát triển Trí tuệ nhân tạo và Công nghệ Game: Áp dụng quy tắc tương tác stigmergy và pheromone số để lập trình các thực thể ảo (NPC) di chuyển thông minh, tự tổ chức đội hình săn lùng hoặc bảo vệ căn cứ một cách tự nhiên và linh hoạt.
• Học viên cao học và Nghiên cứu sinh ngành Khoa học Máy tính: Sử dụng công trình như một tài liệu tham khảo chuẩn mực về phương pháp luận nghiên cứu hệ thống đa tác tử, kỹ thuật mô hình hóa giải tích kết hợp đo lường thực nghiệm nghiêm ngặt.
• Nhà quản lý Logistics và Quy hoạch Đô thị thông minh: Vận dụng mô hình tối ưu hóa vị trí tiếp vận TANKER để giải quyết bài toán bố trí trạm sạc xe buýt điện, xe cứu hỏa lưu động và điểm trung chuyển hàng hóa với mục tiêu giảm 20% chi phí vận hành.

Câu hỏi thường gặp

1. Vấn đề tuần tra đa tác tử trong môi trường chưa biết khác gì so với tuần tra trên đồ thị truyền thống? Tuần tra trên đồ thị truyền thống yêu cầu biết trước toàn bộ bản đồ và tính toán đường đi tối ưu ngoại tuyến, dẫn đến bế tắc khi bản đồ thay đổi. Ngược lại, tuần tra trong môi trường chưa biết buộc tác tử phải vừa khám phá vừa giám sát, sử dụng các dấu vết môi trường để tự điều hướng linh hoạt theo thời gian thực mà không sợ bùng nổ tổ hợp tính toán.

2. Mô hình pheromone kỹ thuật số EVAP hoạt động theo cơ chế nào? Mỗi khi tác tử đi qua một ô, nó đánh dấu lượng pheromone tối đa vào ô đó. Lượng pheromone này sẽ tự động bay hơi theo cấp số nhân qua từng chu kỳ. Các tác tử chỉ cần quét 4 ô xung quanh và di chuyển về ô có lượng pheromone thấp nhất, tương ứng với khu vực lâu nhất chưa có ai viếng thăm.

3. Tại sao thuật toán CLInG lại vượt trội hơn EVAP tại các khu vực phòng ốc phức tạp? Thuật toán CLInG cho phép các ô có độ nhàn rỗi cao lan truyền tín hiệu sức hút xuyên qua các ô lân cận. Nhờ đó, khi tác tử đứng trước một cánh cửa phòng chưa khám phá, trường áp suất thông tin lan truyền sẽ kéo tác tử tiến thẳng vào phòng thay vì phân vân với xác suất ngang bằng như cơ chế cục bộ của EVAP.

4. Cơ chế MARKA giúp các robot tự hành tránh cạn kiệt pin bằng cách nào? Mô hình MARKA xây dựng một trường thế năng số hóa tỏa ra từ trạm sạc với giá trị tăng dần theo khoảng cách. Tác tử liên tục so sánh mức năng lượng hiện có với giá trị đánh dấu của ô hiện tại. Ngay khi năng lượng chạm ngưỡng khoảng cách an toàn, tác tử tự động chuyển sang chế độ tìm nguồn sạc theo gradient thế năng.

5. Khi nào nên triển khai mô hình trạm sạc lưu động TANKER thay vì trạm sạc cố định? Mô hình TANKER nên được sử dụng trong các khu vực hoạt động rộng lớn hoặc địa hình biến động, nơi việc lắp đặt trạm sạc cố định quá tốn kém hoặc tạo ra các góc chết tuần tra. Trạm TANKER tự động trôi về trọng tâm cụm robot làm việc, giúp giảm thiểu 22% quãng đường di chuyển chết của cả đàn.

Kết luận

• Khẳng định tính ưu việt của cách tiếp cận trí tuệ bầy đàn trong việc giải quyết bài toán tuần tra đa tác tử mà không cần tri thức tiên nghiệm về bản đồ.
• Xác lập bộ tiêu chuẩn định lượng nghiêm ngặt và chứng minh hiệu năng tuần tra của mô hình phân tán đạt mức tiệm cận tối ưu lý thuyết trên lưới không gian 400 ô.
• Cung cấp bức tranh đối chuẩn toàn diện giữa mô hình bay hơi pheromone EVAP tiết kiệm tính toán và mô hình lan truyền thông tin CLInG tối ưu hóa độ nhàn rỗi cực đại.
• Giải quyết triệt để bài toán thắt nút cổ chai về giới hạn năng lượng thông qua hai mô hình bổ trợ đột phá là MARKA và trạm sạc động TANKER.
• Đặt nền tảng vững chắc cho việc chuyển giao các thuật toán phản xạ từ môi trường mô phỏng lên các nền tảng robot thực tế.

Đóng góp lớn nhất của công trình là chứng minh các tương tác cục bộ đơn giản hoàn toàn có thể tạo nên hành vi tuần tra và quản lý năng lượng tự trị cấp bầy đàn với độ ổn định cao. Kế hoạch nghiên cứu tiếp theo sẽ tập trung vào việc thử nghiệm phần cứng trên dàn robot di động thực địa trong 12 tháng tới và tích hợp công nghệ học tăng cường sâu đa tác tử trong vòng 24 tháng. Hãy tham khảo ngay toàn văn luận văn để làm chủ các giải pháp điều phối bầy đàn tự tổ chức và ứng dụng hiệu quả vào các dự án công nghệ tiên phong!

Trích đoạn nội dung tài liệu

Institut de la Francophonie pour Laboratoire Lorraine de Recherche en l’Informatique Informatique et ses Applications (LORIA) – UMR 7503 Master INTELLIGENCE ARTIFICIELLE ET MULTIMÉDIA, 2ème année, Spécialité RECHERCHE Année universitaire 2005 – 2007 APPROCHES COLLECTIVES POUR LE PROBLEME DE LA PATROUILLE MULTI-AGENTS Mémoire présenté par CHU Hoang Nam Stage effectué au LORIA, Projet INRIA MaIA Directeurs : • M. Olivier SIMONIN – Maître de Conférences (Université Henri Poincaré – Nancy 1) • M. François CHARPILLET – Directeur de Recherche (INRIA) Vandœuvre-lès-Nancy, Septembre 2007 TIEU LUAN MOI download : [e-mail] Remerciements Je tiens en premier lieu à remercier tout particulièrement Olivier Simonin et François Charpillet pour m’avoir encadré pendant ces six mois. Je remercie de leur contact chaleureux, leurs conseils et encouragements, leur soutien permanent et la liberté de recherche qu’il a bien voulu me laisser.

Je souhaite également remercier Alexis Drogoul pour m’avoir introduit ce stage, fait confiance et encouragé dès le début de mon travail. Mes sincères remerciements vont également à tous les professeurs de l’Institut de le Francophonie pour l’Informatique (IFI) pour m’avoir dirigé tout au long de mes études à l’IFI. Je remercie l’ensemble du personnel de l’équipe MaIA pour leur formidable accueil, leur gentillesse et une ambiance de travail particulièrement favorable. Merci à Cédric, Jamal, Yoann, Ilham et Arnaud pour leurs amabilités et chaleurs, à Geoffray pour son cours de langue humoriste, à Rodolphe, Nazim pour leurs conseils précieux.

Un grand merci aux mes camarades de la promotion XI pour leur amitié et leur aide dès le début de mon étude à l’IFI. Merci enfin à mes parents et mes amis pour leur soutien et leur encouragement à tout instant. TIEU LUAN MOI download : [e-mail] Table des matières REMERCIEMENTS. 2 TABLE DES MATIERES.

3 TABLE DES FIGURES. 6 1 PROBLÈME MULTI-AGENTS DE LA PATROUILLE. 10 2 APPROCHE PAR SYSTÈMES MULTI-AGENTS RÉACTIFS. EVAP : UN MODÈLE BASÉ SUR L’ÉVAPORATION DES PHÉROMONES.

CLING : UN MODÈLE BASÉ SUR LA PROPAGATION D’INFORMATIONS. 14 3 COMPARAISON LES PERFORMANCES ENTRE EVAP ET CLING. SIMULATION ET ANALYSE. Exploration et patrouille.

Avantages et défauts des méthodes. 21 4 PROBLÈME D’ÉNERGIE DANS LA PATROUILLE. MARKA : UN MODÈLE COLLECTIF BASÉ SUR LA CONSTRUCTION DE CHAMP NUMÉRIQUE POTENTIEL. Comportement des agents.

Estimation de l’autosuffisance. TANKER : UNE APPROCHE AUTO-ORGANISÉE COLLECTIVE POUR L’OPTIMISATION DE POSITION DE TANKER. Les forces attractives et répulsives. Comportement du modèle (algorithme).

28 5 PERFORMANCES DE MARKA ET TANKER. AVANTAGES ET DÉFAUTS DES MODÈLES. 39 SWARM APPROACHES FOR THE PATROLLING PROBLEM, INFORMATION PROPAGATION VS. 40 TIEU LUAN MOI download : [e-mail] Table des figures Figure 1 : Espace « discret » et espace « continu ».

9 Figure 2 : Oisiveté propagée. 14 Figure 3 : Topologies étudiées. 17 Figure 4 : Topologie sans obstacles, 8 agents, 1000 itérations. 18 Figure 5 : Topologie sans obstacle, moyenne IGI.

18 Figure 6 : Topologie couloir-salles, 1 agent, 4000 itération. 19 Figure 7 : Topologie 6-pièces, 4 agents, 2000 itérations. 19 Figure 8 : Topologie 6-pièces, moyenne IGI. 19 Figure 9 : EVAP et CLInG, Map E.

20 Figure 10 : Le processus de marquage d’environnement. 24 Figure 11 : La formation de gradient des champs numériques. 25 Figure 12 : Attraction guide le Tanker au barycentre des demandes. 27 Figure 13 : Répulsion garde la distance entre Tankers A et B.

28 Figure 14 : Diffusion en environnement discret. 29 Figure 15 : MARKA et TANKER, 4 agents, 4000 itérations. 31 Figure 16 : Installation d’environnement. 32 Figure 17 : MARKA et TANKER, 2 groupes, 4000 itérations.

32 Figure 18 : Illustration de TANKER. 33 TIEU LUAN MOI download : [e-mail] TIEU LUAN MOI download : [e-mail] Approches collectives pour le problème de la patrouille multi-agents Introduction Ce stage a été réalisé dans le cadre du master recherche informatique, intelligence artificielle et multimédia, option intelligence artificielle. Il a eu lieu au laboratoire LORIA (UMR 7503, Nancy) au sein de l’équipe INRIA MaIA. Le stage s’est déroulé sous la direction d’Oliver SIMONIN, Chargé de Recherche INRIA, et François CHARPILLET, Directeur de Recherche INRIA, responsable scientifique de l’équipe MaIA.

Le problème multi-agents de la patrouille consiste à faire parcourir un territoire à des agents de telle sorte que les différentes parties du territoire soient visitées le plus souvent possible par ces agents. Ce problème avait été introduit par Ramalho et al. dans [8], et avait été abordé avec des algorithmes multi-agents classiques. Dans le cadre du stage effectué au LORIA, nous abordons l’approche par l’intelligence en essaim pour le problème de la patrouille et de l’exploration multi-agents.

Plus précisément, ce stage se destine à l’étude des algorithmes multi-agents réactifs dont le but est de patrouiller et explorer un environnement inconnu. De plus, un autre objectif de ce stage est d’intégrer la limitation d’énergie au problème de la patrouille, de proposer un algorithme qui permette aux agents de coordonner les activités de patrouille et de recharge. Le rapport se divise en 4 parties. La première introduit le problème multi-agents de la patrouille ainsi que les travaux antérieurs.

Dans une seconde partie, nous présentons l’intelligence collective et deux algorithmes, EVAP et CLInG, basés sur cette approche pour traiter le problème de la patrouille. La troisième partie présente la comparaison des performances entre ces deux algorithmes. Enfin, la dernière partie est consacrée au problème de l’énergie dans la patrouille. CHU Hoang Nam 6 TIEU LUAN MOI download : [e-mail] Approches collectives pour le problème de la patrouille multi-agents 1 Problème multi-agents de la patrouille Selon le dictionnaire Petit Larousse, une patrouille est « une mission de renseignements, de surveillance ou de liaison confiée à une formation militaire (aérienne, terrestre ou navale) ou policière ; désigne également la formation elle- même ».

Selon le dictionnaire Oxford, « patrolling is the act of walking or travelling around an area, at regular interval, in order to protect or to supervise it ». Le problème multi- agents de la patrouille, ou patrolling en anglais, consiste à déployer un ensemble d’agents, généralement en nombre fixe, afin de visiter à intervalle régulier les lieux stratégiques d’une région. Ce problème se pose typiquement dans les jeux vidéos [8] [10] lorsqu’une équipe de créatures virtuelles a pour mission de patrouiller sur un territoire déterminé, dans certaines applications internet, ainsi que dans le déplacement d’une équipe de robots, dans la surveillance d’un lieu ou d’un bâtiment en vue de le défendre de toute intrusion, etc. Malgré son utilité et son intérêt scientifique, la patrouille multi-agents n’a été étudiée que récemment.

Dans [8], un des premiers travaux, Machado et al. ont déjà proposé les premières notions et aussi évalué différents architectures d’agent pour traiter ce problème. Ainsi, nous plaçant dans cette configuration du problème nous pensons que des approches de type intelligence en essaim peuvent s’avérer particulièrement pertinentes. Elles reposent en général sur le marquage de l’environnement et définissent un moyen de communication et de calcul indirect entre les agents.

Les sous-sections suivantes présentent des critères d’évaluations de la performance d’une stratégie de patrouille, les types d’environnements ainsi que leur représentation. Critères d’évaluation Patrouiller efficacement dans un environnement, éventuellement dynamique, nécessite que le délai entre deux visites d’un même lieu soit minimal. L’ensemble des travaux portant sur les stratégies de patrouille considèrent que l’environnement est connu, bidimensionnel et qu’il peut être réduit à un graphe G(V,E) (V l’ensemble des nœuds à visiter, E les arrêtes définissant les chemins valides entre les nœuds). Plusieurs critères peuvent être utilisés afin d’évaluer la qualité d’une stratégie de CHU Hoang Nam 7 TIEU LUAN MOI download : [e-mail] Approches collectives pour le problème de la patrouille multi-agents patrouille.

Nous utilisons ceux se basant sur le calcul de l’oisiveté des nœuds (ou Idleness) qui peuvent être calculés au niveau d’un nœud ou au niveau du graphe. Nous utilisons les critères suivants qui sont introduits dans [8] : • Instantaneous Node Idleness (INI) : nombre de pas de temps où un nœud est resté non visité, appelé oisiveté dans le reste du présent rapport. Critère calculé pour chaque nœud. • Instantaneous Graph Idleness (IGI) : moyenne de l'Instantaneous Idleness de tous les noeuds pour un instant donné.

Critère calculé au niveau du graphe. • Average Graph Idleness (AvgI) : moyenne de IGI sur n pas de temps. Critère calculé au niveau du graphe. • Instantaneous Worst Idleness (IWI) : plus grande INI apparue au cours d’un pas de temps donné, appelé oisiveté maximale ou pire oisiveté dans le reste du présent rapport.

Critère calculé au niveau du graphe. Environnement On trouve dans les travaux antérieurs deux types d’environnement utilisés par les modèles de la patrouille multi-agent : espace « discret » et espace « continu » Espace « discret » L’espace « discret », qui se compose d’un ensemble de nœuds à visiter, est représenté sous forme un graphe G (V, E) (V l’ensemble des nœuds à visiter, E les arrêtes définissant les chemins valides entre les nœuds). Ce type de représentation convient pour le cas de la patrouille entre les lieux intérêts. Espace « continu » L’espace continu représente une aire à couvrir, comme une chambre, un bâtiment etc.

On peut modéliser ce type d’espace par une grille où chaque cellule représente soit un lieu à visiter, soit un lieu inaccessible (mur, obstacle) (cf. CHU Hoang Nam 8 TIEU LUAN MOI download : [e-mail] Approches collectives pour le problème de la patrouille multi-agents Figure 1 : Espace « discret » et espace « continu » La pré-connaissance de l’environnement est également une condition importante dans le problème de la patrouille. En effet, elle influe sur le choix de l’algorithme de patrouille ainsi que sur sa performance. Environnement connu Les agents sont ici dotés d’une pré-connaissance de l’environnement.

Une architecture de type cognitive conviendra donc à ce type d’environnement. Les agents peuvent travailler de façon offline, par exemple, mémoriser la carte ou faire une planification du parcours optimale, avant l’exécution de la tâche [4] [1]. Environnement inconnu La tâche de patrouille est exécutée sans connaissance de l’environnement. Il est alors évident que les agents doivent effectuer deux tâches : explorer l’environnement et patrouiller.

Dans ce cadre, on peut utiliser des agents réactifs, ces derniers pouvant réaliser un apprentissage ou bien recourir à des techniques basées sur le marquage de l’environnement. Dans le cadre de ce stage, nous nous concentrons sur le problème de la patrouille en environnement inconnu, c'est-à-dire qu’il est impossible de disposer du graphe représentant l’environnement. L’espace exploré par les agents est représenté comme une matrice de cellules dont chaque cellule peut être soit: • Libre • Occupée par un agent • Être inaccessible (un obstacle, un mur …) CHU Hoang Nam 9 TIEU LUAN MOI download : [e-mail] Approches collectives pour le problème de la patrouille multi-agents 1. Travaux antérieurs Le problème de la patrouille a été abordé ces dernières années selon des approches centralisées, heuristiques ou encore distribuées, mais toujours dans le cadre d’une représentation sous forme d’un graphe de l’environnement (un nœud étant un lieu prédéterminé qu’il faut visiter, une arrête un chemin reliant deux nœuds) et donc nécessairement une pré-connaissance de l’environnement.

Il existe divers travaux reposant sur des algorithmes de parcours de graphes dérivant souvent du problème du voyageur de commerce [1]. On trouve dans [4] une solution reposant sur le principe d’optimisation par colonie de fourmis (ACO algorithms) mais qui nécessite là encore une pré-connaissance de l’environnement sous la forme d’un graphe. Il en est de même pour les techniques à base d’apprentissage qui reposent sur la recherche d’un parcours multi-agent optimal calculé offline, c'est-à-dire que le parcours optimal est calculé avant l’exécution de tâche dans l’environnement considéré. Par conséquent, une telle technique n’est pas capable de s’adapter à un changement online du problème tel qu‘une modification de la topologie de l’environnement ou l’ajout ou la perte d’un certain nombre d’agents.