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.
