Increasing allocated tasks with a time minimization algorithm for a search and rescue scenario

Abstract

Rescue missions require both speed to meet strict time constraints and maximum use of resources. This study presents a Task Swap Allocation (TSA) algorithm that increases vehicle allocation with respect to the state-of-the-art consensus-based bundle algorithm and one of its extensions, while meeting time constraints. The novel idea is to enable an online reconfiguration of task allocation among distributed and networked vehicles. The proposed strategy reallocates tasks among vehicles to create feasible spaces for unallocated tasks, thereby optimizing the total number of allocated tasks. The algorithm is shown to be efficient with respect to previous methods because changes are made to a task list only once a suitable space in a schedule has been identified. Furthermore, the proposed TSA can be employed as an extension for other distributed task allocation algorithms with similar constraints to improve performance by escaping local optima and by reacting to dynamic environments.