Multi-robot patrolling is a key feature for various applications related to surveillance and security, and it has been studied from several different perspectives, ranging from techniques that devise optimal off-line strategies to implemented systems. However, still few approaches consider on-line decision techniques that can cope with uncertainty and non-determinism in robot behaviors. In this articleweaddresson-linecoordination,bycastingthemultirobot patrolling problem as a task assignment problem and proposing two solution techniques: DTA-Greedy, which is a baseline greedy approach, and DTAP, which is based on sequentialsingle-itemauctions.Weevaluatetheperformance of our system in a realistic simulation environment (built with ROS and stage) as well as on real robotic platforms. In particular, in the simulated environment we compare our task assignment approaches with previous off-line and on-line methods. Our results confirm that on-line coordination approaches improve the performance of the multi-robot patrollingsysteminrealenvironments,andthatcoordination approaches that employ more informed coordination protocols(e.g.,DTAP)achievebetterperformanceswithrespectto state-of-the-art online approaches (e.g., SEBS) in scenarios where interferences among robots are likely to occur. Moreover,thedeploymentonrealplatforms(threeTurtlebotsinan office environment) shows that our on-line approaches can successfullycoordinatetherobotsachievinggoodpatrolling behaviors when facing typical uncertainty and noise (e.g., localization and navigation errors) associated to real platforms.

• Distributed on-line dynamic task assignment for multi-robot patrolling