Multi-Agent Distributed Graph Traversal

Abstract

The industry of the civil Unmanned Aerial Vehicles (UAVs) has been growing rapidly in past few years. In many scenarios, accomplishing a task using a single UAV is either not cost-effective due to the size of the project or not even feasible due to the existence of unforeseen environment conditions and constraints (e.g., weather conditions and/or physical obstacles). This limitation motivates the need to move to solutions that incorporate a network of autonomous UAVs that carry out a joint and coordinated mission. This thesis introduces a multi-agent system and related algorithms that solve the graph traversal problem in a distributed and decentralized manner while optimizing a set of costs. The environment is modelled as a graph where every node is the point for the agents to accomplish some task or to distinguish the point as an obstacle where traveling is not possible. The online distributed algorithms are implemented on a network of UAVs and we report the results of rigorous simulations and real experiments with a network of UAVs. The results clearly validate our claim that a network UAVs can be effectively employed to accomplish a given task.