Politecnico di Torino (logo)

Distributed algorithms for autonomous target search problems

Michele Da Re

Distributed algorithms for autonomous target search problems.

Rel. Fabio Fagnani, Sara Bernardini, Nicola Gatti. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2020

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (3MB) | Preview

Search-and-Tracking (SaT) is a problem where an autonomous vehicles such as an UAV (Unmanned Aerial Vehicle, commonly known as 'drone') has the task of tracking a target while it moves and, whenever the target is lost, perform a search phase. In this work, the problem is approached with a focus on the search phase and with the assumption that the target is moving towards its destination along the optimal ruote and without trying to evade the search. Previous work on this problem developed a Monte Carlo simulation that allows the UAV to select a number of candidate locations where to perform the search. The goal is to find a sequence of such locations that is time-feasible and that maximazes an objective function that is related to the probability of success and the expected time of target recovery. The work proposes a new method for solving this optimization problem based on a distributed algorithm, meaning that the selection of a feasible candidate solution is reframed as follows. A graph is built where the nodes are given by pairs of candidate locations and possible time instant where the search could begin. An edge connects nodes representing searches that cannot be executed both because of a time constraint. A candidate solution is then a subset of nodes such that no pair of selected nodes are connected. Moreover, the probability of success will be necessarily maximized on a selection of nodes where if a node is not selected then at least one of its neighbours is. These two constraints determine that the candidate solutions are exactly the maximal independent sets of the graph. To extract these sets, a game-theoretic approach is followed. By associating to each node two actions, "selected" and "not selected" and an utility function related to the number of neighbours in violation of those two constraints, then it is possible to study the related Noisy Best Response Dynamics and to know the stationary distribution of its Markov chain. Moreover, the most likely configurations are exactly the maximal independent sets. Therefore, the algorithm has the nodes play this game and allows to randomly sample maximal independet sets, that are feasible solutions to the original optimization problem. The algorithm is then compared to previous solvers and tested with different choices of parameters, different objective functions and different problem instances.

Relators: Fabio Fagnani, Sara Bernardini, Nicola Gatti
Academic year: 2020/21
Publication type: Electronic
Number of Pages: 47
Corso di laurea: Corso di laurea magistrale in Ingegneria Matematica
Classe di laurea: New organization > Master science > LM-44 - MATHEMATICAL MODELLING FOR ENGINEERING
Ente in cotutela: Royal Holloway - University of London (REGNO UNITO)
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/16295
Modify record (reserved for operators) Modify record (reserved for operators)