© 2025 The Authors. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by- nc-nd/4.0/ ).

Graph-patrolling problems in the adversarial domain typically embed models and assumptions about how hostile events, from which an environment must be protected, are generated at a specific time and location. Relying upon such attacker models prevents algorithms from synthesizing strategies that can generalize in different settings, providing good performance under different and uncertain scenarios. In this paper, we propose a first method to deal with adversarial patrolling using a data driven approach. We cast the problem in an RL setting where the reward function is based on the ability to neutralize attacks that can follow an unknown strategy and that, hence, can be viewed as a black box component. We apply a policy gradient framework for optimizing action probabilities under such a reward model showing how effective patrolling strategies can be obtained from repeated attack-defense interactions between a patrolling agent and an attacker. Our results show that the data driven patroller can effectively provide protection against multiple, diverse attacker behaviors.

Graph patrolling algorithms provide effective strategies for coordinating mobile robots in the context of autonomously surveilling valuable assets. Optimizing patrolling strategies often aims to minimize the time between subsequent visits to a vertex, a measure known in the literature as idleness. In the domain of multi-robot patrolling, two approaches have received the most attention so far. The first involves coordinating all robots to follow a shared patrolling strategy covering the entire graph, while the second approach partitions the environment into disjoint areas that are then assigned to individual robots. Starting from these existing solutions, this paper introduces a new method that bridges these two complementary approaches. Our technique splits the vertices of the graph into a partition that includes a shared portion of the environment patrolled collectively by all robots, along with disjoint areas allocated exclusively to individual robots. This problem is formulated in terms of minimizing the maximum weighted idleness of the graph and is shown to be NP-hard. We then describe an exact solution for the problem and propose various heuristics to efficiently compute solutions for large problem instances. We evaluate and compare the proposed techniques in simulation and demonstrate that, in most cases, our methods produce better patrolling strategies when compared to classic solutions. Moreover, for small problem instances where the exact solution can be found, we show that our proposed heuristic has a competitive performance ratio.

We introduce a novel approach for scalable domain adaptation in cloud robotics scenarios where robots rely on third–party AI inference services powered by large pre– trained deep neural networks. Our method is based on a downstream proposal–refinement stage running locally on the robots, exploiting a new lightweight DNN architecture, R2SNet. This architecture aims to mitigate performance degradation from domain shifts by adapting the object detection process to the target environment, focusing on relabeling, rescoring, and suppression of bounding–box proposals. Our method allows for local execution on robots, addressing the scalability challenges of domain adaptation without incurring significant computational costs. Real–world results on mobile service robots performing door detection show the effectiveness of the proposed method in achieving scalable domain adaptation.

Multi-robot rendezvous and exploration are fundamental challenges in the domain of mobile robotic systems. This paper addresses multi-robot rendezvous within an initially unknown environment where communication is only possible after the rendezvous. Traditionally, exploration has been focused on rapidly mapping the environment, often leading to suboptimal rendezvous performance in later stages. We adapt a standard frontier-based exploration technique to integrate exploration and rendezvous into a unified strategy, with a mechanism that allows robots to re-visit previously explored regions thus enhancing rendezvous opportunities. We validate our approach in 3D realistic simulations using ROS, showcasing its effectiveness in achieving faster rendezvous times compared to exploration strategies.

We study a patrolling problem where multiple agents are tasked with protecting an environment where one or more adversaries are trying to compromise targets of varying value. The objective of the patrollers is to move between targets to quickly spot when an attack is taking place and then diffuse it. Differently from most related literature, we do not assume that attackers have full knowledge of the strategies followed by the patrollers, but rather build a model at run time through repeated observations of how often they visit certain targets. We study three different solutions to this problem. The first two partition the environment using either a fast heuristic or an exact method that is significantly more time consuming. The third method, instead does not partition the environment, but rather lets every patroller roam over the entire environment. After having identified strengths and weaknesses of each method, we contrast their performances against attackers using different algorithms to decide whether to attack or not.

The use of autonomous robots for surveillance is one of the most interesting applications of graph-patrolling algorithms. In recent years, considerable effort has been devoted to tackling the problem of efficiently computing effective patrolling strategies. One of the mainstream approaches is adversarial patrolling, where a model of a strategic attacker is explicitly taken into account. A common assumption made by these techniques is to consider a worst-case attacker, characterized by ubiquitous and perfect observation capabilities. Motivated by the domain of robotic applications, we instead consider a more realistic and limited attacker model capable of gathering noisy observations in a locally limited range of the environment. We assume that the modeled attacker follows a behavior induced by its observations. Thus, we devise a randomized patrolling strategy based on Markov chains that makes observations reveal very little information, while still maintaining a reasonable level of protection in the environment. Our experimental results obtained in simulation confirm time-variance as a practical approach for our objective.

The employment of Social Assistive Robots (SARs) for monitoring elderly users represents a valuable gateway for at-home assistance. Their deployment in the house of the users can provide effective opportunities for early detection of Mild Cognitive Impairment (MCI), a condition of increasing impact in our aging society, by means of digitalized cognitive tests. In this work, we present a system where a specific set of cognitive tests is selected, digitalized, and integrated with a robotic assistant, whose task is the guidance and supervision of the users during the completion of such tests. The system is then evaluated by means of an experimental study involving potential future users, in order to assess its acceptability and identify key directions for technical improvements.

The ageing of the population deeply impacts on the social costs relative to health care. The use of modern technologies is one of the most promising approaches, under current study, to reduce such impact. In this demonstration, we propose a framework that can be employed for at-home assessment of Mild Cognitive Impairment (MCI). It is composed by a set of digitalized cognitive tests, developed from their paper-and-pencil counterparts, and by a Virtual Caregiver, which oversees the test execution and provides instructions.

In this paper, we consider the problem of maintaining and restoring connectivity among a set of agents (humans or robots) by incrementally redeploying a team of mobile robots acting as communication relays. This problem is relevant in numerous scenarios where humans and robots are jointly deployed for tasks like urban search and rescue, surveillance, and the like. In this case, as the humans move in the environment, connectivity may be broken, and consequently, robots need to reposition themselves to restore it. We study the computational complexity of the problem, also in terms of approximation hardness, and present an Integer Linear Programming formulation to compute optimal solutions. We then analyze the performance of the proposed resolution approach against a heuristic algorithm taken from the literature, and we demonstrate how our method favorably compares in terms of solution quality and scalability.

In several multirobot applications in which communication is limited, the mission could require the robots to iteratively take coordinated joint decisions on how to spread out in the environment and on how to reconnect with each other to share data and compute plans. Exploration and surveillance are examples of these applications. In this paper, we consider the problem of computing robots' paths on a graph-represented environment for restoring connections at minimum traveling cost. We call it the multirobot reconnection problem, we show its NP-hardness and hardness of approximation on some important classes of graphs, and we provide optimal and heuristic algorithms to solve it in practical settings. The techniques we propose are then exploited to derive a new efficient planning algorithm for a relevant connectivity-constrained multirobot planning problem addressed in the literature, the multirobot informative path planning with periodic connectivity problem.

The Team-maxmin equilibrium prescribes the optimal strategies for a team of rational players sharing the same goal and without the capability of correlating their strategies in strategic games against an adversary. This solution concept can capture situations in which an agent controls multiple resources - corresponding to the team members - that cannot communicate. It is known that such equilibrium always exists and it is unique (except degenerate cases) and these properties make it a credible solution concept to be used in real-world applications, especially in security scenarios. Nevertheless, to the best of our knowledge, the Team-maxmin equilibrium is almost completely unexplored in the literature. In this paper, we investigate bounds of (in)efficiency of the Team-maxmin equilibrium w.r.t. the Nash equilibria and w.r.t. the Maxmin equilibrium when the team members can play correlated strategies. Furthermore, we study a number of algorithms to find and/or approximate an equilibrium, discussing their theoretical guarantees and evaluating their performance by using a standard testbed of game instances.

The importance of communication in many multirobot information-gathering tasks requires the availability of reliable communication maps. These provide estimates of the radio signal strength and can be used to predict the presence of communication links between different locations of the environment. In the problem we consider, a team of mobile robots has to build such maps autonomously in a robot-to-robot communication setting. The solution we propose models the signal's distribution with a Gaussian Process and exploits different online sensing strategies to coordinate and guide the robots during their data acquisition. Our methods show interesting operative insights both in simulations and on real TurtleBot 2 platforms.

We study the problem of computing an equilibrium in leader-follower games with a single leader and multiple followers where, after the leader’s commitment to a mixed strategy, the followers play simultaneously in a noncooperative way, reaching a Nash equilibrium. We tackle the problem from a bilevel programming perspective. Since, given the leader’s strategy, the followers’ subgame may admit multiple Nash equilibria, we consider the cases where the followers play either the best (optimistic) or the worst (pessimistic) Nash equilibrium in terms of the leader’s utility. For the optimistic case, we propose three formulations which cast the problem into a single level mixed-integer nonconvex program. For the pessimistic case, which, as we show, may admit a supremum but not a maximum, we develop an ad hoc branch-and-bound algorithm. Computational results are reported and illustrated.

When a piece of software is loaded on an untrusted machine it can be analyzed by an attacker who could discover any secret information hidden in the code. Software protection by continuously updating the components deployed in an untrusted environment forces a malicious user to restart her or his analyses, thus reducing the time window in which the attack is feasible. In this setting, both the attacker and the defender need to know how to direct their(necessarily limited) efforts. In this paper, we analyze the problem from a game theoretical perspective in order to devise a rational strategy to decide when and which orthogonal updates have to be scheduled in order to minimize the security risks of tampering. We formalize the problem of protecting a set of software modules and we cast it as a game. Since the update strategy is observable by the attacker, we show that the Leader-Follower equilibrium is the proper solution concept for such a game and we describe the basic method to compute it.

Motivated by a number of security applications, among which border patrolling, we study, to the best of our knowledge, the first Security Game model in which patrolling strategies need to be combined with responses to signals raised by an alarm system, which is spatially uncertain (i.e., it is uncertain over the exact location the attack is ongoing) and is affected by false negatives (i.e., the missed detection rate of an attack may be positive). Ours is an infinite-horizon patrolling scenario on a graph, where a single patroller moves. We study the properties of the game model in terms of computational issues and form of the optimal strategies and we provide an approach to solve it. Finally, we provide an experimental analysis of our techniques.

In multirobot exploration under centralized control, communication plays an important role in constraining the team exploration strategy. Recurrent connectivity is a way to define communication constraints for which robots must connect to a base station only when making new observations. This paper studies effective multirobot exploration strategies under recurrent connectivity by considering a centralized and asynchronous planning framework. We formalize the problem of selecting the optimal set of locations robots should reach, provide an exact formulation to solve it, and devise an approximation algorithm to obtain efficient solutions with a bounded loss of optimality. Experiments in simulation and on real robots evaluate our approach in a number of settings.

Most of the literature on delay tolerant networks (DTNs) focuses on optimal routing policies exploiting a priori knowledge about nodes mobility traces. For the case in which no a priori knowledge is available (very common in practice), apart from basic epidemic routing, the main approaches focus on controlling two-hop routing policies. However, these latter results commonly employ fluid approximation techniques, which, in principle, do not provide any theoretical bound over the approximation ratio. In our work, we focus on the case without a priori mobility knowledge and we provide approximation algorithms with theoretical guarantees that can be applied to cases where the number of hops allowed in the routing process is arbitrary. Our approach is rather flexible allowing us to address heterogeneous mobility patterns and transmission technologies, to consider explicitly the signaling and transmission costs, and to include also nodes discarding packets after a local timeout. We then provide a comprehensive performance evaluation of our algorithms, showing that two-hop routing provides the best tradeoff between delay and energy and that, in this case, they find solutions very close to the optimal ones with a low overhead. Finally, we compare our methods against some state-of-the-art approaches by means of a DTN simulation environment in realistic settings.

We consider the problem of computing patrolling strategies under communication constraints for a team of autonomous robots employed in repeated surveillance missions on a set of predefined locations. We assume the presence of a communication infrastructure providing only some regions of the environment with a communication link to a mission control center (MCC). We define the problem of computing a joint patrolling strategy that minimizes communication latencies, defined as the delays between inspecting some locations and reporting the outcome to the MCC. We provide and experimentally evaluate a MILP formulation and a heuristic method.

We consider the problem of providing surveillance to a grid area using multiple heterogeneous UAVs, named sentinels and searchers, with complementary sensing and actuation capabilities. We consider probabilistic attacks and we analyze the expected performance with respect to the team deployment. We then introduce the problem of finding minmax deployments that result in the most desirable worst case performance caused by an attack. We present an algorithm to compute deployments while trading off solution's quality and computational effort and we qualitatively and quantitatively analyze it.

Most applications of wireless sensor networks (WSNs) rely on data about the positions of sensor nodes, which are not necessarily known beforehand. Several localization approaches have been proposed but most of them omit to consider that WSNs could be deployed in adversarial settings, where hostile nodes under the control of an attacker coexist with faithful ones. Verifiable multilateration (VM) was proposed to cope with this problem by leveraging on a set of trusted landmark nodes that act as verifiers. Although VM is able to recognize reliable localization measures, it allows for regions of undecided positions that can amount to the 40 percent of the monitored area. We studied the properties of VM as a noncooperative two-player game where the first player employs a number of verifiers to do VM computations and the second player controls a malicious node. The verifiers aim at securely localizing malicious nodes, while malicious nodes strive to masquerade as unknown and to pretend false positions. Thanks to game theory, the potentialities of VM are analyzed with the aim of improving the defender's strategy. We found that the best placement for verifiers is an equilateral triangle with edge equal to the power range $(R)$, and maximum deception in the undecided region is approximately $(0.27R)$. Moreover, we characterizedâin terms of the probability of choosing an unknown node to examine furtherâthe strategies of the players.

Marching along the DARPA SyNAPSE roadmap, IBM unveils a trilogy of innovations towards the TrueNorth cognitive computing system inspired by the brain's function and efficiency. The non-von Neumann nature of the TrueNorth architecture necessitates a novel approach to efficient system design. To this end, we have developed a set of abstractions, algorithms, and applications that are natively efficient for TrueNorth. First, we developed repeatedly-used abstractions that span neural codes (such as binary, rate, population, and time-to-spike), long-range connectivity, and short-range connectivity. Second, we implemented ten algorithms that include convolution networks, spectral content estimators, liquid state machines, restricted Boltzmann machines, hidden Markov models, looming detection, temporal pattern matching, and various classifiers. Third, we demonstrate seven applications that include speaker recognition, music composer recognition, digit recognition, sequence prediction, collision avoidance, optical flow, and eye detection. Our results showcase the parallelism, versatility, rich connectivity, spatio-temporality, and multi-modality of the TrueNorth architecture as well as compositionality of the corelet programming paradigm and the flexibility of the underlying neuron model.

Robotic exploration is an on-line problem in which autonomous mobile robots incrementally discover and map the physical structure of initially unknown environments. Usually, the performance of exploration strategies used to decide where to go next is not compared against the optimal performance obtainable in the test environments, because the latter is generally unknown. In this paper, we present a method to calculate an approximation of the optimal (shortest) exploration path in an arbitrary environment. We consider a mobile robot with limited visibility, discretize a two-dimensional environment with a regular grid, and formulate a search problem for finding the optimal exploration path in the grid, which is solved using A*. Experimental results show the viability of our approach for realistically large environments and its potential for better assessing the performance of on-line exploration strategies.

Pursuit evasion problems, in which evading targets must be cleared from an environment, are encountered in surveillance and search and rescue applications. Several works have addressed variants of this problem in order to study strategies for the pursuers. As a common trait, many of these works present results in the general form: given some assumptions on the environment, on the pursuers, and on the evaders, upper and lower bounds are calculated for the time needed for (the probability of, the resources needed for, ...) clearing the environment. The question “what is the optimal strategy for a given pursuer in a given environment to clear a given evader?” is left largely open. In this paper, we propose a game theoretical framework that contributes in finding an answer to the above question in a version of the pursuit evasion problem in which the evader enters and exits a grid environment and the pursuer has to intercept it along its path. We adopt a criterion for optimality related to the probability of capture. We experimentally evaluate the proposed approach in simulated settings and we provide some hints to generalize the framework to other versions of the pursuit evasion problem.

Unmanned Aerial Vehicles (UAVs) can be an effective technology for security applications involving patrolling and search missions. Defining online patrolling strategies for UAVs presents challenges related both to classical patrolling, as periodic monitoring of the environment, and to search, as accurate localization and identification of the mission-related activities. In this paper, we deal with this problem considering probabilistic intrusions and a variable resolution sensing model that naturally applies to the domain of UAVs. We present three online single-robot patrolling strategies exploiting a variable resolution paradigm to represent the environment that has recently shown promising results for search problems. The approach uses a hierarchical representation based on probabilistic quadtrees that allows UAVs to tradeoff sensing accuracy with sensing area. The model is extended by adding stochastic arrivals of intruders in space and time. Obtained results validate this approach for online patrolling against approaches based on uniform grids.

Recently, there has been a significant interest in studying security games to provide tools for addressing resource allocation problems in security applications. Patrolling security games (PSGs) constitute a special class of security games wherein the resources are mobile. One of the most relevant open problems in security games is the design of scalable algorithms to tackle realistic scenarios. While the literature mainly focuses on heuristics and decomposition techniques (e.g., double oracle), in this paper we provide, to the best of our knowledge, the first study on the use of abstractions in security games (specifically for PSGs) to design scalable algorithms. We define some classes of abstractions and we provide parametric algorithms to automatically generate abstractions. We show that abstractions allow one to relax the constraint of patrolling strategies' Markovianity (customary in PSGs) and to solve large game instances. We additionally pose the problem to search for the optimal abstraction and we develop an anytime algorithm to find it.

Autonomous mobile robots are a promising technology for search and rescue scenarios, where an initially unknown environment has to be explored to locate human victims. Robots can exploit exploration strategies to autonomously move around the environment. Most of the strategies proposed in literature are based on the idea of evaluating a number of candidate locations according to ad hoc utility functions that combine different criteria. In this paper, we show some of the advantages of using a more theoretically-grounded approach, based on Multi-Criteria Decision Making (MCDM), to define exploration strategies for robots employed in search and rescue applications. We implemented our MCDM-based exploration strategies within an existing robot controller and we evaluated their performance in a simulated environment.

Use of game theoretical models to derive randomized mobile robot patrolling strategies has recently received a growing attention. We focus on the problem of patrolling environments with arbitrary topologies using multiple robots. We address two important issues cur rently open in the literature. We determine the smallest number of robots needed to patrol a given environment and we compute the optimal patrolling strategies along several coordination dimensions. Finally, we experimentally evaluate the proposed techniques.

Game theoretical approaches have been recently used to develop patrolling strategies for mobile robots. The idea is that the patroller and the intruder play a game, whose outcome depends on the combination of their actions. From the analysis of this game, an optimal strategy for the patrolling robot can be derived. Although game theoretical approaches are promising, their applicability in real settings is still an open problem. In this paper, we experimentally evaluate the practical applicability of the most general game theoretical approach for patrolling strategies, called BGA model. Experiments are conducted by using USARSim, with the goal of studying the behavior of the optimal patrolling strategy returned by the BGA model both in situations that violate its idealized assumptions and in comparison with other patrolling strategies that can be developed with much less computational effort.

Using autonomous mobile robots to patrol environments for detecting intruders is a topic of increasing relevance for its possible applications. A large part of strategies for mobile patrolling robots proposed so far adopt some kind of random movements. Although these strategies are unpredictable for an intruder, they are not always efficient in getting the patroller a large expected utility. In this paper we propose an approach that considers a model of the adversary in a game theoretic framework to find optimally-efficient patrolling strategies. We show that our approach extends those proposed in literature and we experimentally analyze some of its features.