An Experimental Analysis of a Robust Pheromone-based Algorithm for the Patrolling Problem
An Experimental Analysis of a Robust Pheromone-based Algorithm for the Patrolling Problem
复制标题
基于鲁棒信息素的巡逻问题算法的实验分析
DOI：
10.1007/978-3-319-27000-5_1
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Shigeo DOI
中科院分区：
文献类型：
--
作者：
河野健一;森沢知之;森山善文;矢部広樹;吉次豊見;田中 謙;Shigeo DOI
Recently, the necessity to resolve the patrolling problem has become pressing. This problem is modeled using an undirected graph structure in which one or more agents patrol the graph and regularly visit each node with the shortest time interval possible. Some central controlled algorithms have been proposed to solve this problem. However, the reliability of these algorithms, which depends on the central controller and communication between the controller and each agent, is considered insufficient. Thus, algorithms with a central controller are not applicable to critical environments. As an alternative approach, some autonomous and distributed algorithms have been proposed to achieve higher reliability and robustness. In a previous paper, we proposed an autonomous and distributed algorithm, called pheromone- and inverse-degree-based Probabilistic Vertex-Ant-Walk (pidPVAW). pidPVAW uses a pheromone model corresponding to fixed points for agent communication and cooperative patrolling as an extension of pheromone-based PVAW (pPVAW). In this paper, we introduce a new parameterkto control the effect of the degree of the neighbor nodes on the agent decision to move. When, pidPVAW behaves like pPVAW; therefore, pidPVAW includes pPVAW. The parameterkcontrols how easily nodes with lower connectivity can be visited. We ran some computer simulations for the parameterkon square grid graphs and scale-free graphs, and showed its effect on the system.
