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.
이 논문에서는 동적 환경에서 다수 무인 시스템을 이용해 자율 탐색을 수행할 때 필요한 효율적인 작업 할당 알고리즘을 제시한다. 시간에 따라 변하는 동적 환경에서 효율적으로 작업을 수행하기 위해서는 높은 계산 효율의 작업 할당 알고리즘이 요구되며, 이를 위해 번들 생성(bundle construction)과 우회 경로 개선(path stretching) 두 단계로 이루어진 제약 프로그래밍 기반의 작업 할당 알고리즘을 제시한다. 높은 계산 효율을 만족하기 위해 제약 조건을 새로운 결정변수로 하여 해를 찾는 절차에 대해 제시하고, 효과적인 수렴을 위한 초기 제약 조건, 그래프 탐색 전략 및 우회 경로 개선 방법을 개발하고 시뮬레이션을 통해 그 유용성을 보인다. 또한, 실제 임무에서 작업 완료율을 높이기 위해서는 계산 효율 뿐만이 아니라, 작업 수행을 위한 최적의 운동체 수를 결정하는 선단최적화(fleet size optimization)를 고려할 수 있으면서 노드(운동체와 작업)의 위치 오차가 있는 상황에서도 신뢰할만한 성능을 낼 수 있는 알고리즘이 요구된다. 이를 위해, 가상의 작업(virtual task)을 활용한 선단 최적화 방법을 개발하고, 강인성의 정량화 기법 및 이를 활용해 신뢰할 수 있는 해를 얻는 방법을 함께 사용하여 보다 효율적으로 높은 작업 완료율을 달성할 수 있는 작업 할당 알고리즘을 제시한다. 추가적으로, 다수 운동체를 활용하기 위한 임무 계획을 제시하고 수치 시뮬레이션을 통해 제안하는 알고리즘의 활용 방안 및 타당성과 유용성을 검증한다.
