Print Email Facebook Twitter The PageRank algorithm as a method to optimize swarm behavior through local analysis Title The PageRank algorithm as a method to optimize swarm behavior through local analysis Author Coppola, M. (TU Delft Control & Simulation) Guo, J. (TU Delft Space Systems Egineering) Gill, E.K.A. (TU Delft Space Engineering) de Croon, G.C.H.E. (TU Delft Control & Simulation) Department Space Engineering Date 2019 Abstract This work proposes PageRank as a tool to evaluate and optimize the global performance of a swarm based on the analysis of the local behavior of a single robot. PageRank is a graph centrality measure that assesses the importance of nodes based on how likely they are to be reached when traversing a graph. We relate this, using a microscopic model, to a random robot in a swarm that transitions through local states by executing local actions. The PageRank centrality then becomes a measure of how likely it is, given a local policy, for a robot in the swarm to visit each local state. This is used to optimize a stochastic policy such that the robot is most likely to reach the local states that are “desirable,” based on the swarm’s global goal. The optimization is performed by an evolutionary algorithm, whereby the fitness function maximizes the PageRank score of these local states. The calculation of the PageRank score only scales with the size of the local state space and demands much less computation than swarm simulations would. The approach is applied to a consensus task, a pattern formation task, and an aggregation task. For each task, when all robots in the swarm execute the evolved policy, the swarm significantly outperforms a swarm that uses the baseline policy. When compared to globally optimized policies, the final performance achieved by the swarm is also shown to be comparable. As this new approach is based on a local model, it natively produces controllers that are flexible and robust to global parameters such as the number of robots in the swarm, the environment, and the initial conditions. Furthermore, as the wall-clock time to evaluate the fitness function does not scale with the size of the swarm, it is possible to optimize for larger swarms at no additional computational expense. Subject AggregationCentralityConsensusEvolutionary algorithmLocalMicroscopicMicro–macro linkPageRankPattern formationSwarm roboticsMicro-macro link To reference this document use: http://resolver.tudelft.nl/uuid:6468bc8e-a5e9-4fdd-acad-7f1420d3bb0c DOI https://doi.org/10.1007/s11721-019-00172-z ISSN 1935-3812 Source Swarm Intelligence, 13 (3-4), 277-319 Part of collection Institutional Repository Document type journal article Rights © 2019 M. Coppola, J. Guo, E.K.A. Gill, G.C.H.E. de Croon Files PDF Coppola2019_Article_ThePa ... ethodT.pdf 3.7 MB Close viewer /islandora/object/uuid:6468bc8e-a5e9-4fdd-acad-7f1420d3bb0c/datastream/OBJ/view