Nicola Basilico

ICRA Conference 2024 Conference Paper

Combining Coordination and Independent Coverage in MultiRobot Graph Patrolling

• Carlos Diaz Alvarenga
• Nicola Basilico
• Stefano Carpin

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.

IROS Conference 2024 Conference Paper

Frontier-Based Exploration for Multi-Robot Rendezvous in Communication-Restricted Unknown Environments

• Mauro Tellaroli
• Matteo Luperto
• Michele Antonazzi
• Nicola Basilico

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.

ICRA Conference 2024 Conference Paper

Learning Generalizable Patrolling Strategies through Domain Randomization of Attacker Behaviors

• Carlos Diaz Alvarenga
• Nicola Basilico
• Stefano Carpin

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.

IROS Conference 2024 Conference Paper

R2SNet: Scalable Domain Adaptation for Object Detection in Cloud-Based Robotic Ecosystems via Proposal Refinement

• Michele Antonazzi
• Matteo Luperto
• N. Alberto Borghese
• Nicola Basilico

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.

AAMAS Conference 2023 Conference Paper

Multi-Agent Pickup and Delivery with Task Probability Distribution

• Andrea Di Pietro
• Nicola Basilico
• Francesco Amigoni

Multi-Agent Pickup and Delivery (MAPD) consists in completing a set of tasks by having agents move to the pickup location and then to the delivery location of each task. In MAPD, new tasks are dynamically added to the system throughout its lifetime and existing algorithms usually assume either complete ignorance or full knowledge about the position and the time at which future tasks will appear until they are actually added to the system. This paper introduces a novel MAPD problem in which a spatial and temporal probability distribution of future tasks is known and defines algorithms that take advantage of this knowledge to reduce the average time required to execute tasks. In particular, we build on an existing MAPD algorithm, Token Passing (TP), proposing different ways to exploit a given task probability distribution. Experiments show that these methods can have a positive impact on the time required to complete the tasks.

ICRA Conference 2020 Conference Paper

Multirobot Patrolling Against Adaptive Opponents with Limited Information

• Carlos Diaz Alvarenga
• Nicola Basilico
• Stefano Carpin

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.

AAMAS Conference 2019 Conference Paper

Delayed and Time-Variant Patrolling Strategies against Attackers with Local Observation Capabilities

• Carlos Diaz Alvarenga
• Nicola Basilico
• Stefano Carpin

Surveillance of graph-represented environments is an application of autonomous patrolling robots that received remarkable attention during the last years. In this problem setting, computing a patrolling strategy is a central task to guarantee an effective protection level. Literature provides a vast set of methods where the patrolling strategies explicitly consider the presence of a rational adversary and fully informed attacker, which is characterized by worst-case (for the patroller) observation capabilities. In this work, we consider an attacker that does not have any prior knowledge on the environment and the patrolling strategy. Instead, we assume that the attacker can only access local observations on the vertex potentially under attack. We study the definition of patrolling strategies under the assumption that the attacker, when planning an attack on a particular location, tries to forecast the arrivals of the patroller on that particular location. We model our patrolling strategies with Markov chains where we seek the generation of arrivals that are difficult to forecast. To this end we introduce time-variance in the transition matrix used to determine the patrollers movements on the graph-represented environment.

IROS Conference 2019 Conference Paper

Evaluating the Acceptability of Assistive Robots for Early Detection of Mild Cognitive Impairment

• Matteo Luperto
• Marta Romeo
• Francesca Lunardini
• Nicola Basilico
• Carlo Abbate
• Ray Jones
• Angelo Cangelosi
• Simona Ferrante

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.

IROS Conference 2019 Conference Paper

Time-Varying Graph Patrolling Against Attackers with Locally Limited and Imperfect Observation Models

• Carlos Diaz Alvarenga
• Nicola Basilico
• Stefano Carpin

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.

AAMAS Conference 2018 Conference Paper

A Journey Among Pairs of Vertices: Computing Robots' Paths for Performing Joint Measurements

• Alessandro Riva
• Jacopo Banfi
• Carlo Fanton
• Nicola Basilico
• Francesco Amigoni

The problem of performing joint measurements recurs in many robotic applications, like constructing communication maps from signal strength samples gathered on the field. In spite of this, a theory supporting efficient algorithms has not been yet developed and ad hoc methods are usually employed. In this paper, we consider an environment represented by a metric graph and prove that the problem of jointly performing measurements from given vertices is NP-hard when either the total traveled distance or the task completion time have to be minimized. Given the difficulty of finding optimal paths in an efficient way, we propose a greedy randomized approach able to cope with both the optimization objectives. In settings for which joint measurements must be taken for all pairs of vertices, we prove that a deterministic greedy algorithm achieves an O(m logn) approximation factor for the traveled distance objective, where m is the number of robots and n the number of vertices, and an O(m2 logn) approximation factor for the completion time. Experiments in simulation show that our algorithms perform well in practice, also when compared to an ad hoc method taken from the literature.

IJCAI Conference 2018 Conference Paper

Digitalized Cognitive Assessment mediated by a Virtual Caregiver

• Matteo Luperto
• Marta Romeo
• Francesca Lunardini
• Nicola Basilico
• Ray Jones
• Angelo Cangelosi
• Simona Ferrante
• N. Alberto Borghese

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.

IROS Conference 2018 Conference Paper

Optimal Redeployment of Multirobot Teams for Communication Maintenance

• Jacopo Banfi
• Nicola Basilico
• Stefano Carpin

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.

AAMAS Conference 2018 Conference Paper

Seeking Prevention of Cognitive Decline in Elders via Activity Suggestion by A Virtual Caregiver

• Alessandro Vuono
• Matteo Luperto
• Jacopo Banfi
• Nicola Basilico
• Nunzio A. Borghese
• Michael Sioutis
• Jennifer Renoux
• Amy Loufti

Addressing the lack of social, cognitive, and physical stimuli among elders is a key factor to contrast Mild Cognitive Impairment (MCI) that can arise during the third age. Against such background, agentbased technology has been applied to different application domains related to the assistance of elders. In this demo, we introduce an application of this kind: an activity center featuring social, cognitive, and physical activities targeted for elders. This activity center interacts with an autonomous agent, called Virtual Caregiver, residing in the cloud and generating interventions based on users’ data. We show how the user experience can be enriched with an adaptive configuration encouraging socialization and cognitive training.

AIJ Journal 2017 Journal Article

Adversarial patrolling with spatially uncertain alarm signals

• Nicola Basilico
• Giuseppe De Nittis
• Nicola Gatti

When securing complex infrastructures or large environments, constant surveillance of every area is not affordable. To cope with this issue, a common countermeasure is the usage of cheap but wide-ranged sensors, able to detect suspicious events that occur in large areas, supporting patrollers to improve the effectiveness of their strategies. However, such sensors are commonly affected by uncertainty. In the present paper, we focus on spatially uncertain alarm signals. That is, the alarm system is able to detect an attack but it is uncertain on the exact position where the attack is taking place. This is common when the area to be secured is wide, such as in border patrolling and fair site surveillance. We propose, to the best of our knowledge, the first Patrolling Security Game where a Defender is supported by a spatially uncertain alarm system, which non-deterministically generates signals once a target is under attack. We show that finding the optimal strategy is FNP -hard even in tree graphs and APX -hard in arbitrary graphs. We provide two (exponential time) exact algorithms and two (polynomial time) approximation algorithms. Finally, we show that, without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non-negligible missed detection rates, which, unfortunately, affect every commercial alarm system. We evaluate our methods in simulation, assessing both quantitative and qualitative aspects.

AAMAS Conference 2017 Conference Paper

Coordinating Multiple Defensive Resources in Patrolling Games with Alarm Systems

• Nicola Basilico
• Andrea Celli
• Giuseppe De Nittis
• Nicola Gatti

Alarm systems represent a novel issue in Security Games, requiring new models that explicitly describe the dynamic interaction between the players. Recent works studied their employment, even considering various forms of uncertainty, and showed that disregarding them can lead to arbitrarily poor strategies. One of the key problems is computing the best strategy to respond to alarm signals for each mobile defensive resource. The current literature only solves the basic single–resource version of such problem. In this paper, we provide a solution for the multi–resource case addressing the challenge of designing algorithms to coordinate a scaling– up number of resources. First, we focus on finding the minimum number of resources assuring non–null protection to every target. Then, we deal with the computation of multi–resource strategies with different degrees of coordination among resources resorting to adversarial team game models. For each considered problem, we provide algorithms and their theoretical and empirical analysis.

IS Journal 2017 Journal Article

Multirobot Exploration of Communication-Restricted Environments: A Survey

• Francesco Amigoni
• Jacopo Banfi
• Nicola Basilico

Exploration of initially unknown environments is an online task in which autonomous mobile robots coordinate themselves to efficiently discover free spaces and obstacles. Several efforts have been devoted to study coordinated multirobot exploration assuming that communication is possible between any two locations. The problem of developing multirobot systems for effective exploration in the presence of communication constraints, despite its remarkable practical relevance, is comparably much less studied. The authors provide a taxonomy of the field of communication-restricted multirobot exploration, survey recent work in this field, and outline some promising research directions.

ICRA Conference 2017 Conference Paper

Multirobot online construction of communication maps

• Jacopo Banfi
• Alberto Quattrini Li
• Nicola Basilico
• Ioannis M. Rekleitis
• Francesco Amigoni

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.

AAAI Conference 2017 Conference Paper

Team-Maxmin Equilibrium: Efficiency Bounds and Algorithms

• Nicola Basilico
• Andrea Celli
• Giuseppe De Nittis
• Nicola Gatti

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.

AAAI Conference 2016 Conference Paper

A Security Game Combining Patrolling and Alarm-Triggered Responses Under Spatial and Detection Uncertainties

• Nicola Basilico
• Giuseppe De Nittis
• Nicola Gatti

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.

ICRA Conference 2016 Conference Paper

Asynchronous multirobot exploration under recurrent connectivity constraints

• Jacopo Banfi
• Alberto Quattrini Li
• Nicola Basilico
• Ioannis M. Rekleitis
• Francesco Amigoni

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.

AAMAS Conference 2016 Conference Paper

Methods for Finding Leader-Follower Equilibria with Multiple Followers (Extended Abstract)

• Nicola Basilico
• Stefano Coniglio
• Nicola Gatti

Leader-follower (LF) equilibria play a central role in several applications of game theory. In spite of this, the literature only presents sporadic results for the case with two or more followers. In this work, we address the problem of computing LF equilibria in this setting, assuming that the followers play a Nash Equilibrium after the leader’s commitment.

IROS Conference 2015 Conference Paper

Deploying teams of heterogeneous UAVs in cooperative two-level surveillance missions

• Nicola Basilico
• Stefano Carpin

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.

IROS Conference 2015 Conference Paper

Minimizing communication latency in multirobot situation-aware patrolling

• Jacopo Banfi
• Nicola Basilico
• Francesco Amigoni

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.

AAMAS Conference 2013 Conference Paper

Introducing Alarms in Adversarial Patrolling Games

• Enrique Munoz de Cote
• Ruben Stranders
• Nicola Basilico
• Nicola Gatti
• NICK JENNINGS

Adversarial patrolling games (APGs) can be modeled as Stackelberg games where a patroller and an intruder compete. The former moves with the aim of detecting an intrusion, while the latter tries to intrude without being detected. In this paper, we introduce alarms in APGs, namely devices that can remotely inform the patroller about the presence of the intruder at some location. We introduce a basic model, provide an extended formulation of the problem and show how it can be cast as partially observable stochastic game. We then introduce the general resolution approach.

ICRA Conference 2012 Conference Paper

A game theoretical approach to finding optimal strategies for pursuit evasion in grid environments

• Francesco Amigoni
• Nicola Basilico

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.

ICRA Conference 2012 Conference Paper

Online patrolling using hierarchical spatial representations

• Nicola Basilico
• Stefano Carpin

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.

AIJ Journal 2012 Journal Article

Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder

• Nicola Basilico
• Nicola Gatti
• Francesco Amigoni

Security games are gaining significant interest in artificial intelligence. They are characterized by two players (a defender and an attacker) and by a set of targets the defender tries to protect from the attackerʼs intrusions by committing to a strategy. To reach their goals, players use resources such as patrollers and intruders. Security games are Stackelberg games where the appropriate solution concept is the leader–follower equilibrium. Current algorithms for solving these games are applicable when the underlying game is in normal form (i. e. , each player has a single decision node). In this paper, we define and study security games with an extensive-form infinite-horizon underlying game, where decision nodes are potentially infinite. We introduce a novel scenario where the attacker can undertake actions during the execution of the defenderʼs strategy. We call this new game class patrolling security games (PSGs), since its most prominent application is patrolling environments against intruders. We show that PSGs cannot be reduced to security games studied so far and we highlight their generality in tackling adversarial patrolling on arbitrary graphs. We then design algorithms to solve large instances with single patroller and single intruder.

AAAI Conference 2012 Conference Paper

Searching for Optimal Off-Line Exploration Paths in Grid Environments for a Robot with Limited Visibility

• Alberto Quattrini Li
• Francesco Amigoni
• Nicola Basilico

AAAI Conference 2011 Conference Paper

Automated Abstractions for Patrolling Security Games

• Nicola Basilico
• Nicola Gatti

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.

ICRA Conference 2011 Conference Paper

Defining effective exploration strategies for search and rescue applications with Multi-Criteria Decision Making

• Nicola Basilico
• Francesco Amigoni

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.

AAMAS Conference 2011 Conference Paper

Exploration Strategies Based on Multi-Criteria Decision Making for Search and Rescue Autonomous Robots

• Nicola Basilico
• Francesco Amigoni

Autonomous mobile robots are considered a valuable technology for search and rescue applications, where an initially unknown environment has to be explored to locate human victims. In this scenario, robots 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 some MCDM-based exploration strategies within an existing robot controller and we experimentally evaluated their performance in a simulated environment.

AAMAS Conference 2011 Conference Paper

is a software tool for supporting the development of security applications with mobile patrolling robots. Exploiting talos 's functionalities, a user can easily compose a patrolling setting and apply recent algorithms presented in the multi-agent literature to find optimal patrolling strategies. Results can be evaluated and compared with intuitive graphical representations and an interacting game can be played by the user in a simulated patrolling scenario. TALOS: A Tool for Designing Security Applications with Mobile Patrolling Robots

• Nicola Basilico
• Nicola Gatti
• Pietro Testa

talos

AAAI Conference 2010 Conference Paper

Asynchronous Multi-Robot Patrolling against Intrusions in Arbitrary Topologies

• Nicola Basilico
• Nicola Gatti
• Federico Villa

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 currently 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.

ICRA Conference 2010 Conference Paper

Moving game theoretical patrolling strategies from theory to practice: An USARSim simulation

• Francesco Amigoni
• Nicola Basilico
• Nicola Gatti 0001
• Alessandro Saporiti
• Stefano Troiani

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.

ICRA Conference 2009 Conference Paper

Finding the optimal strategies for robotic patrolling with adversaries in topologically-represented environments

• Francesco Amigoni
• Nicola Basilico
• Nicola Gatti 0001

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.

AAMAS Conference 2009 Conference Paper

Leader-Follower Strategies for Robotic Patrolling in Environments with Arbitrary Topologies

• Nicola Basilico
• Nicola Gatti
• Francesco Amigoni

Game theoretic approaches to patrolling have become a topic of increasing interest in the very last years. They mainly refer to a patrolling mobile robot that preserves an environment from intrusions. These approaches allow for the development of patrolling strategies that consider the possible actions of the intruder in deciding where the robot should move. Usually, it is supposed that the intruder can hide and observe the actions of the patroller before intervening. This leads to the adoption of a leader-follower solution concept. In this paper, mostly theoretical in its nature, we propose an approach to determine optimal leader-follower strategies for a mobile robot patrolling an environment. Differently from previous works in literature, our approach can be applied to environments with arbitrary topologies.