Abstract:
Recently, for security reasons, the need to solve the patrolling problem has become increasingly urgent. We consider a problem in which agents patrol a graph at the short...Show MoreMetadata
Abstract:
Recently, for security reasons, the need to solve the patrolling problem has become increasingly urgent. We consider a problem in which agents patrol a graph at the shortest regular intervals possible for each node. To solve the problem, we propose an autonomous distributed algorithm called pheromone-based Probabilistic Vertex-Ant-Walk (pPVAW), an improved version of Probabilistic Vertex-Ant-Walk (PVAW) that uses a pheromone model for agent communication and cooperative work. In our algorithm, an agent at a node perceives pheromones related to the difference between the current time and the time when the agent previously visited each neighbor node. The agent determines the next node to select using roulette selection that is proportional to the pheromone. Agents using pPVAW do not go back to the previously visited node. This is in contrast to PVAW, in which agents may go back to the previously visited node because agents using PVAW can randomly select a neighbor node to visit. A comparison of pPVAW with PVAW for dynamic environments indicates that the performance of pPVAW is better than that of PVAW.
Published in: 2013 IEEE Symposium on Swarm Intelligence (SIS)
Date of Conference: 16-19 April 2013
Date Added to IEEE Xplore: 30 September 2013
Electronic ISBN:978-1-4673-6004-3