L’analyse comparative des algorithmes révèle que les approches inspirées des comportements naturels, comme celles des insectes, transforment notre compréhension de l’exploration des environnements inconnus. Découvrez comment l’algorithme SMRSA surpasse ses prédécesseurs, offrant des solutions prometteuses pour l’intelligence artificielle distribuée.
Chapitre 2 : Couverture et exploration des environnements inconnus
Introduction
Les algorithmes de couverture
Les algorithmes de couverture pour un seul robot
- Algorithmes de couverture multi-robots
- Les champs de potentiels artificiels
- Comparaison des résultats des algorithmes de couverture mono- robot et multi-robots :
- L’exploration d’un environnement inconnu
- Définition
- Les algorithmes d’exploration
- Problème d’exploration III.Conclusion
Introduction
Les robots mobiles jouent un rôle important dans de nombreux domaines, parmi lesquels la police militaire et applications (par exemple, le déminage, les véhicules de patrouille armés, la surveillance, la bombe désarmement), l’industrie (par exemple, transport et de manutention des matériaux), l’espace (par exemple, le plan-exploration monétaire, et l’acquisition des matières sur des planètes lointaines).
Ils sont utilisés pour les risques des vies humaines et pour l’efficacité assurée pour les machine , la capacité de travail pour des longtemps , et la décharge des travaux fastidieux .
La planification de chemin est une tache fondamentale dans toutes les opérations de la robotique mobile. Le problème de base pour la planification de chemin d’un robot est de déterminer quel chemin doit être pris par le robot d’un point de départ pour qu’il parvienne à une destination comme dans un environnement connus à l’avance.
Une extension de problème planification de chemin est celle de la recherche d’une cible dont sa position est inconnus à l’avance par le robot, ce problème est considéré comme un problème de couverture partielle d’une région ou un problème d’exploration de région. [sarid. 11]
Le problème général de couvrir une superficie de systèmes robotiques simples ou multiples est un problème fondamental en robotique. Elle a des applications dans divers domaines, de missions humanitaires telles que la recherche et le sauvetage et le déminage, aux applications agricoles telles que le semis ou la récolte, à, récemment, d’entretien ménager.
Le problème a été largement étudié dans les deux domaines seul robot et des systèmes multi-robots.
Plusieurs approches ont été proposées dans la littérature pour répondre au problème de couverture, on trouvera souvent des travaux utilisant un robot seul et d’autres utilisant plusieurs robots.
L’exploration d’un environnement par une ou des entités (soit des humains, des véhicules, des robots, ou des agents logiciels) est un sujet ayant capté l’intérêt de nombreux chercheurs, particulièrement dans les domaines des mathématiques et de l’informatique, depuis plusieurs décennies. [Bautin et al, 11]
Dans cette partie du chapitre, on va faire un survol sur les plus importants et populaire des algorithmes de couverture qui se trouvent dans la littérature, (le mot agent ou robot sont utilisés interchangeable-ment dans le reste de cette partie).plus une vue générale sur l’exploration des environnements inconnus.
- Les algorithmes de couverture :
La couverture de l’environnement, une tâche connexe à la patrouille, La couverture consiste simplement à explorer l’ensemble de l’environnement, c’est-à-dire à visiter au moins une fois chaque nœud de l’environnement.
L’efficacité d’un algorithme en couverture est simplement mesurée par la durée d’une couverture complète de l’environnement. Cette durée est souvent désignée sous le terme de blanket time.
Une couverture optimale consiste, dans un cadre mono-agent, à suivre un chemin hamiltonien. Dans un contexte multi agent, cela revient à diviser l’environnement en un ensemble de chemins hamiltoniens (un par agent) ne s’intersectant pas (c’est-à-dire que chaque agent visitera un nœud inexploré à chaque itération). [Arnaud ,11]
Notons cependant que l’obtention d’une couverture optimale ne garantit pas une patrouille optimale. Si l’on est tenté de considérer intuitivement la patrouille comme une couverture répétée de l’environnement, un simple exemple prouve le contraire.
(Figure 2.1. (a)) présente une couverture optimale sur un environnement grille. En suivant cette stratégie, une fois que l’agent a effectué la couverture de l’environnement, celui-ci se retrouve dans une situation où sa prochaine décision sera nécessairement sous optimale puisque la cellule de plus grande oisiveté correspondra au point de départ de l’agent (ici en haut à gauche).
Une patrouille optimale correspondra cependant à la répétition d’une couverture optimale si ses points de départ et d’arrivée sont adjacents (Figure 2.1. (b)). [Arnaud ,11]
(a) une couverture optimale (b) une patrouille optimale
Figure 2.1: Une couverture optimale ne signifie pas nécessairement une patrouille optimale
Questions Fréquemment Posées
Quels sont les algorithmes de couverture pour les robots autonomes?
Plusieurs approches ont été proposées dans la littérature pour répondre au problème de couverture, on trouvera souvent des travaux utilisant un robot seul et d’autres utilisant plusieurs robots.
Comment l’efficacité d’un algorithme de couverture est-elle mesurée?
L’efficacité d’un algorithme en couverture est simplement mesurée par la durée d’une couverture complète de l’environnement, souvent désignée sous le terme de blanket time.
Quelle est la différence entre la couverture optimale et la patrouille optimale?
Notons cependant que l’obtention d’une couverture optimale ne garantit pas une patrouille optimale, car un simple exemple prouve le contraire.