Distributed algorithms for autonomous target search problems

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.