Study of self-organization in pheromone-based multi-agent patrolling algorithms
Etude de l'auto-organisation dans les algorithmes de patrouille multi-agent fondés sur les phéromones digitales
Résumé
We use here reactive multi-agent systems --- a self-organized and decentralized approach --- for problem solving. We study how reactive agents, acting only according to their local perceptions, can produce robust and competitive performance. So, getting formal proofs of the system's properties is an important issue to be taken care of. In particular, we evaluate the interest of these kind of approaches for the multi-agent patrolling problem which aims for a group of agents at repeatedly visiting the vertices of a discrete environment. We tackle these problems by proposing the EVAP model. It relies on a group of agents patrolling the environment only using pheromone markings and their local perceptions. We take on this model through both theoretical and experimental studies of its behavior. In particular, we prove the self-organization of the system in stable cycles which are near optimal in terms of visit frequency. This property is particularly interesting as it guarantees the long-term performance of the patrol. We also study EVAP's robustness against the modification of the execution model.
Nous abordons, dans cette thèse, la problématique de la résolution de problèmes à l'aide des systèmes multi-agent réactifs, une approche décentralisée et auto-organisée. Nous étudions comment des agents réactifs, dont les décisions ne dépendent que de leurs perceptions locales, peuvent interagir pour produire des solutions robustes et performantes. Assurer formellement les propriétés d'un tel système devient alors un enjeu particulièrement important du domaine. Nous cherchons en particulier à évaluer l'intérêt de ce type d'approches pour pour le problème de la patrouille multi-agent qui consiste à visiter l'ensemble des noeuds d'un environnement discret le plus régulièrement possible. Nous proposons le modèle EVAP qui repose sur l'utilisation d'agents fourmi se coordonnant par marquage de l'environnement à l'aide de phéromones digitales. Nous nous intéressons à ce modèle à travers les études théorique et expérimentale de son comportement. En particulier, nous prouvons que les agents s'auto-organisent vers des attracteurs cycliques stables. Ceux-ci garantissent une fréquence de visite de l'environnement quasi optimale. Nous étudions enfin la robustesse d'EVAP aux variations des hypothèses d'exécution.
Loading...