• RRT
• submodularity
• optimization
• path planning
• greedy algorithm
• distributed algorithm
• coordinated search
• task allocation

The core work of this thesis tackles the case-study problem of coordinating the motion of a multi-agent, multi-target system subject to bounding constraints.
The need for efficient detection and tracking of stationary or moving objects, such as lost people, over a wide, open area motivates the use of swarms of Unmanned Autonomous Vehicles (UAVs).
Typically these agents have bounded resources to comply with, such as fuel limitation, allotted mission time and the like. Thus a careful evaluation is required prior to the actual path generation: an optimal task allocation between agents and targets has to be executed to not potentially waste any resource at disposal.
Given that optimal results usually aren’t obtained in real scenarios due to the high computational burden (centralized approach) or the nature of the problem itself (NP-Hard), the key is distributing the computational load among all agents through a decentralized approach, while compromising on performances.
Leveraging the submodularity property of a special class of functions, the study produced a novel solution for Decentralised Task Allocation, which allows to achieve a reduced computational burden and still guarantee a sub-optimal level of performances.
A novel algorithm has been implemented to generate the path for each agent (RSIG, Rapidly-exploring Submodular Information Gathering), which is a custom version of the RRT* path planner based on criteria of information retrieval.