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

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ể.

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.