Education

  • Ph.D. 2014-now

    Ph.D. Student in Computer Science and Engineering

    Politecnico di Milano, Italy

  • ASP Diploma 2015

    Alta Scuola Politecnica Diploma

    Politecnico di Milano and Politecnico di Torino, Italy

  • M.Sc.2015

    Master of Science in Computer Science and Engineering

    Politecnico di Torino, Italy

    Mark: 110/110 with honors

  • M.Sc.2014

    Master of Science in Computer Science and Engineering

    Politecnico di Milano, Italy

    Mark: 110/110 with honors

  • B.Sc.2012

    Bachelor of Science in Computer Science and Engineering

    Politecnico di Milano, Italy

    Mark: 110/110

Visiting Periods

  • 2016
    University of Southern California
    image
    From June to September, I have been at USC, developing research with the Teamcore, under the supervision of Prof. Milind Tambe.

Awards and Grants

  • 2015
    Leonardo Lesmo Award
    image
    2015 AIxIA (Italian Association for the Artificial Intelligence) award for the best Italian MSc thesis on Artificial Intelligence
    2014
    National Doctoral Scholarship
    image
    Three-years doctoral scholarship sponsored by the Ministry of Education, Universities and Research.

Research Group

Francesco Trovò

Postdoc

Webpage

Stefano Paladino

Ph.D. Student

Webpage

Nicola Gatti

Associate Professor

Webpage

Marcello Restelli

Assistant Professor

Webpage

Nicola Basilico

Assistant Professor

Webpage

Filter by type:

Sort by year:

2017-Computing the Team–maxmin equilibrium in Single–Team Single–Adversary Team Games

Nicola Basilico, Andrea Celli, Giuseppe De Nittis and Nicola Gatti
JournalIntelligenza Artificiale

Abstract

A team game is a non–cooperative normal–form game in which some teams of players play against others. Team members share a common goal but, due to some constraints, they cannot act jointly. A real–world example is the protection of environments or complex infrastructures by different security agencies: they all protect the area with valuable targets but they have to act individually since they cannot share their defending strategies (of course, they are aware of the presence of the other agents). Here, we focus on zero–sum team games with n players, where a team of n-1 players plays against one single adversary. In these games, the most appropriate solution concept is the Team–maxmin equilibrium, i.e., the Nash equilibrium that ensures the team the highest payoff. We investigate the Team–maxmin equilibrium, characterizing the utility of the team and showing that it can be irrational. The problem of computing such equilibrium is NP–hard and cannot be approximated within a factor of n . The exact solution can only be found by global optimization. We propose two approximation algorithms: the former is a modified version of an already existing algorithm, the latter is a novel anytime algorithm. We computationally investigate such algorithms, providing bounds on the utility for the team. We experimentally evaluate the algorithms analyzing their performance w.r.t. a global optimization approach and evaluate the loss due to the impossibility of correlating.

Adversarial Patrolling with Spatially Uncertain Alarm Signals

Nicola Basilico, Giuseppe De Nittis and Nicola Gatti
JournalArtificial Intelligence (AIJ)

Abstract

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.

Coordinating Multiple Defensive Resources in Patrolling Games with Alarm Systems

Nicola Basilico, Andrea Celli, Giuseppe De Nittis and Nicola Gatti
Conference The Sixteenth International Conference on Antonomous Agents and Multiagent Sytems (AAMAS-2017)

Abstract

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.

Team–maxmin Equilibrium: Efficiency Bounds and Algorithms

Nicola Basilico, Andrea Celli, Giuseppe De Nittis and Nicola Gatti
Conference The Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

Abstract

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 (unless degeneracy) 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.

A Security Game Combining Patrolling and Alarm–Triggered Responses under Spatial and Detection Uncertainties

Nicola Basilico, Giuseppe De Nittis and Nicola Gatti
Conference The Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)

Abstract

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.

A Security Game Model for Environment Protection in the Presence of an Alarm System

Nicola Basilico, Giuseppe De Nittis and Nicola Gatti
Conference 2015 Conference on Decision and Game Theory for Security (GameSec 2015)

Abstract

We propose, to the best of our knowledge, the first Security Game where a Defender is supported by a spatially uncertain alarm system which non–deterministically generates signals once a target is under attack. Spatial uncertainty is common when securing large environments, e.g., for wildlife protection. We show that finding the equilibrium for this game is FNP–hard even in the zero–sum case and we provide both an exact algorithm and a heuristic algorithm to deal with it. 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.

Current Teaching

    • 2014 2017

    Sistemi Informatici

    Teaching Assistant

Music

To improvise, you must know which armony you're in.

- Paco De Lucia -

I started playing classical guitar 12 years ago. I started from the basic exercises and scales going up to the main guitarists of the XIX century, to finally approach guitar virtuoso like Tàrrega and Paganini.

During these years, I have practiced a lot, studying and exploring also other genres. Next to my older guitar, now you can find an acoustic guitar and a ukulele.

Scout

Leave this world a little better than you found it.

- Robert Baden-Powell -

I have been a scout for 14 years, following the whole path and becoming a chief with the role of Capo Unità nel Branco.

As a child, I have learnt how to play with the others, respecting them and the rules of the games. As a boy, I have learnt how to collaborate with other people in order to light a fire, build a table and put up a tent, sharing with them practical skills, but also how to lighten up nights around the fire camp. As a young man I have learnt the importance of sharing my knowledge, fears and thoughts with the others, making them trustful and trusting them.

Reading

The reading of all good books is like a conversation with the finest minds of past centuries.

- René Descartes -

I love reading fictions, but also literary novels and scientific books about nuclear physics.

I enjoy reading articles about our history, philosophy of mind and the evolution of the human thought, since I believe that you need to know from where you come to know where to go.