Efficient task allocation for multi-vehicle autonomous search in dynamic environment

Abstract

In this dissertation, an efficient task allocation algorithm for autonomous search using multiple unmanned systems in dynamic environments is proposed. In order to efficiently perform given tasks in a time-varying dynamic environment, a task allocation algorithm with high computational efficiency is required. To achieve such goals, a constraint-programming based task allocation algorithm composed of two steps, namely bundle construction and path stretching step, is proposed. A novel solution approach that uses constraints as a new decision variable is proposed, and techniques to achieve fast convergence such as initial constraints set, searching strategy, and node flipping are also introduced. In addition, in order to increase the completion ratio of tasks in practical missions, they are required that a fleet size optimization, which determines the optimal number of vehicles for performing the tasks, and robust task allocation considering the position error of nodes. For this, a fleet size optimization method using a notion of virtual tasks, and a quantification method of robustness and multi-objective objective function for robust task allocation are proposed. Further, a mission plan for using multiple unmanned vehicles is presented, and the validity and usefulness of the proposed algorithm are verified through numerical simulations.