logo SBA


Digital archive of theses discussed at the University of Pisa


Thesis etd-11212017-101641

Thesis type
Tesi di dottorato di ricerca
Thesis title
A game theoretic approach for multi-robot coordination to guarantee security in critical scenarios, from theory to real applications
Academic discipline
Course of study
tutor Prof.ssa Pallottino, Lucia
commissario Prof. Alberti, Giovanni
commissario Prof. Schenato, Luca
commissario Prof. Secchi, Cristian
  • distributed control
  • game theory
  • herding
  • multi-robot system
  • search and secure
Graduation session start date
This research presents results of the last three years collaboration between the Centro di Ricerca ''E.~Piaggio'' and the company Ingegneria dei Sistemi SpA (IDS), on the application of game theoretic algorithms.
Based on the results obtained by this research, IDS has decided to investigate the implementation of the proposed system on board of its unmanned vehicles, in order to provide a novel security system to the market.
This research proposed the application of a coordinated multi robot system to the problem of asymmetric threat, both in military and civilian scenarios.
The problem of detecting and accordingly reacting to an asymmetric threat (Asymmetric threats or techniques are a version of not ''fighting fair,'' which can include the use of surprise in all its operational and strategic dimensions and the use of weapons in ways unplanned) is a challenge both from research and technological points of view.
Even though the available surveillance sensors are sufficient to identify and classify asymmetric threats, they are able to give a quick alert only in nominal working conditions. Indeed, adverse weather conditions easily lead to degradation of sensors performance leading to a drastic reduction of the time available for a possible reaction after the detection, identification and classification procedures.
The short time--to--reaction may increase the possibility of human errors especially in stressful situations (e.g. an incorrect assessment of the necessary reaction).
This research proposes the use of multi--robot coordinated team as autonomous surveillance systems that can guarantee an adequate supervision of the area in any working conditions even though the entire area is not fully monitored at any time instant.
Indeed, the mobility abilities of autonomous vehicles can be exploited to deploy the team of robots to monitor the environment and to react to possible intruders.
In particular, this research is focussed on the problem of coordinating a team of robots based on partial knowledge of the environment due to limited sensors footprint and communication range.
The coordination of the robot must also guarantee the accomplishment of other tasks in a framework in which communication is limited due to security issues or deteriorated communication channels (e.g. underwater scenarios).
An example of antagonistic tasks is the monitoring of the area around the main ship while detecting, tracking and herding an intruder toward a safe area.
It is worth noting that the marine scenario is only a possible application of the proposed methodology that is valid whenever the goal is to detect, localize and react to any environmental changes of interest, e.g. high variation of temperature, water pollution, terrorists attacks, etc.
In this research a unified model has been proposed for the problem under study for different application scenarios such as asymmetric threats protection in marine environments and safety at border crossing points, such as airports.
The proposed unified framework is based on the Game Theory.
Indeed, it is well known that the particular class of potential games solves several cooperative control problems with a reduced amount of communication between robots.
In particular, the considered control problem is transformed into a non--cooperative game where the goal is to reach specific equilibria.
Moreover, the case of ``payoff--based'' scenarios, where robots get a reward in the reached regions based on the action performed by other robots, helps in capturing the requirements into the problem formulation.
Learning algorithms that can steer the robots toward Nash equilibria are proven to solve partially the problem.
In case of a static environment, e.g. fixed area of interest in the scenario, the coverage problem has been largely studied with a game theoretic approach.
However, such algorithms are proven to converge to a static configuration maximizing the number of interested area covered by the robot sensors' footprint but are not able to handle a dynamic intruder.
On the other hand, in case of dynamic environment, as for asymmetric threat protection, existing algorithms have been only designed to explore the entire area without selecting the sub--regions of major interest or doing it with high communication costs.
Concluding, with respect to the state of the art literature, in this research, a game theoretic approach is used to detecting, track and herd a dynamic intruder protecting pre-defined areas.
In particular, the work proposes two kind of coordination protocols which are proved to solve the asymmetric threat protection problem.
Based on the well--known payoff--based algorithms, the research presents some extension of state--of--the--art coordination protocols which are suitable for dynamic environment.
Moreover, the work presents new payoff--based algorithms to deal with the problem of multi--robot coordination in dynamic environment where the robots must accomplish antagonistic tasks simultaneously.
For those new algorithms convergence to equilibria is formally proved.
Finally, our research is interested in investigating the relationship between the team of guards and the intruder once it has been identified, i.e, the \emph{reaction phase}.
Such problem is investigated with the use of a game theoretic framework and, a novel team coordination protocols for the intruder herding problem, is proposed.
Such new algorithm solves the problem of steering a team of guards for guiding an intruder towards a restricted area of a known environment.
The proposed system, based on the virtual objectives concept, is able to limit the movement of an intruder without communication between robots of the team.
Proposed framework has been validated with a Monte Carlo simulation in order to cover a large set of different situations.
Based on Monte Carlo simulation, a novel tool, that solves the problem of determine the minimum number of robots contrasting an intruder which is moving in the area, is proposed.
Indeed, it can be used to determine the maximum volume to store autonomous vehicles on board.
Proposed algorithms have been evaluated against intruders piloted by human, in order to test the robustness of the proposed solution.
The proposed game theoretic framework has been tested in real robot experiments thanks to the use of a novel multi--robot system for managing team of robots.
Based on the promising results, the proposed model has been extended to cope the asymmetric threat protection problem when sensors are affected by uncertainty on the detection.
Video of some validation results are available online (https://youtu.be/emyf4xx-_pY, https://youtu.be/rBs23CNdh8U and https://youtu.be/ODoHY7WgQdc).