This dissertation establishes an efficient minimum-time task planning algorithm to serve clients with robots and cooperators. For each task to serve a client, we require a preparatory moving action by a robot, followed by a simultaneous cooperative action by the same robot and a cooperator. As the number of clients is increased, a considerable number of nodes can be generated in the tree graph (NP-hard), similar to the multiple traveling salesman problem (mTSP). This dissertation is composed of three parts: 1) Extended representation of Task and Actions (ERTA), 2) Offline cooperative task planning, and 3) Online cooperative task planning. An offline cooperative task planning is divided to two problems. At first, we establish an efficient Minimum-time Cooperative Task Planning (MCTP) adopting a branch-and-bound which finds the minimum-time task schedule for a fixed number of robots (and cooperators). We also establish Cost-effective Cooperative Task Planning (CCTP), which finds the number of robots and the task schedule with the best Cost Performance Ratio (CPR). An online cooperative task planning is divided to two problems. First, we establish Emergency Cooperative Task Planning (ECTP) dealing with high-priority emergency tasks requiring interruption of the existing task schedule. We also establish Remaining Cooperative Task planning (RCTP) adopting a branch-and-bound, which can re-plan the existing task schedule for remnant normal tasks after Emergency Task schedule.
First, we propose Extended Representation of Tasks and Actions (ERTA) to formulate the task planning for serving robots and cooperators. Several robots cannot work with one cooperator at the same time. Hence the task planner always consider cooperator-conflict to find minimum-time task schedule. Our ERTA deals with concurrently executing tasks without cooperator-conflict.
Next, an offline cooperative task planning is divided to MCTP algorithm and CCTP algorithm. Our MCTP algorithm adopts branch-and-bound to find the minimum-time task schedule with a fixed number of robots. However, the conventional branch-and-bound can consume intractable amounts of storage and computing time because our task planning problem is NP-hard. For an efficient branch-and-bound, we propose initial tree using a Good Task Plan Candidates (GTPCs), and complementary heuristics considering robots and cooperators. They can reduce the tree size by intractable amounts. Our CCTP algorithm finds the most cost-effective task schedule with the minimum-CPR, and the most cost-effective number of robots. However, it is inefficient to iterate the task planning for the full search-range for finding the cost-effective task schedule. We propose an efficient procedure which reduces the search range via a relational analysis between the number of robots and the CPR. We use backward search for the reduced search range, and use the previous planning result to reduce the number of nodes.
Last, an online cooperative task planning deals with high priority emergency tasks requiring interruption of the existing task schedule. Our ECTP algorithm can quickly find emergency task schedule within 1 ms since we remove unnecessary search ranges by using Parallel Emergency Tasks (PET), Serial Emergency Tasks (SET), and Three Serial Emergency Tasks (TSET) algorithms. We also proposed the efficient RCTP algorithm based on branch-and-bound algorithm, which can quickly determine a schedule composed of the next R remaining task every serve duration.
본 논문은 로봇 (robot)과 협력자 (cooperator)이 여러 개의 협력 작업 (cooperative task)들을 최소 시간에 완료시키는 스케줄을 구하기 위한 최소 시간 작업 계획 (minimum-time task planning) 알고리즘을 다룬다. 협력 작업은 로봇과 협력자가 협업하여 클라이언트 (client)들에게 서비스를 제공하는 작업이다. 각 협력 작업은 각 로봇이 클라이언트에게 이동하는 이동 행동 (move-action)과 해당 클라이언트에 도착한 직후 로봇과 협력자가 협업하여 클라이언트에게 서비스를 제공하는 서브 행동 (serve-action)으로 구성되어 있다. 이러한 작업 계획은 클라이언트 수가 증가하면 증가할수록, 탐색량은 mTSP와 VRP 문제와 유사하게 NP-hard로 증가하게 된다. 본 논문은 오프라인 작업 계획 (offline task planning)과 온라인 작업 계획 (online task planning)으로 구성되어 있다. 오프라인 작업 계획은 최소 시간 협력 작업 계획 (MCTP, Minimum-time Cooperative Task Planning)과 가격 효율적인 협력 작업 계획 (CCTP, Cost-effective Cooperative Task Planning)으로 나뉘고, 온라인 작업 계획은 긴급 협력 작업 계획 (ECTP, Emergency Cooperative Task Planning)과 후속 협력 작업 계획 (RCTP, Remaining Cooperative Task Planning)으로 나뉜다.
우선, 로봇과 협력자의 협업 작업을 표현하기 위하여 ERTA (Extended Representation of Tasks and Actions)을 제안하였다. 이때, 작업 계획을 위해서, 협력자 충돌 (cooperator conflict)를 반드시 고려해야 한다. 협력자 충돌은 여러 대의 로봇들은 하나의 협력자를 동시에 점유할 수 없다는 것을 의미한다. ERTA는 이러한 협력자 충돌이 없는 동시 수행 작업들을 표현하기 위한 방법이다.
오프라인 작업 계획은 MCTP와 CCTP 알고리즘으로 나뉜다. 제안하는 MCTP 알고리즘은 주어진 로봇 수에 대하여, 최소 수행 시간을 가지는 스케줄을 브랜치 앤 바운드 (branch and bound)를 이용하여 찾는다. 그러나 기존의 브랜치 앤 바운드는 매우 큰 저장 공간과 계산시간을 요구하기 때문에, 지금의 작업 계획 문제에 적용하기 쉽지 않다. 그래서 효율적인 브랜치 앤 바운드를 위하여, GTPCs (Good Task Plan Candidates)를 이용한 초기 트리 (initial tree)와 로봇과 협력자를 고려한 상호 보완 휴리스틱 (complementary heuristics)을 제안한다. 제안된 방법에 의해서 트리 탐색량을 매우 크게 개선할 수 있다. CCTP 알고리즘은 가성비 (cost performance ratio)가 가장 좋은 가격 효율적인 작업 스케줄과 그 때의 로봇의 수를 구한다. 그러나 가격 효율적인 작업 스케줄을 구하기 위하여 모든 탐색 범위에 대해 작업 계획 알고리즘을 반복하는 것은 비효율적이다. 그래서 우리는 로봇의 수와 가성비 사이의 상관관계를 분석하여 탐색 범위를 크게 줄이고, 트리 노드수를 감소시킬 수 있는 방법을 제안한다.
다음으로 온라인 작업 계획은 오프라인 작업 계획에서 계산한 작업 스케쥴이 수행 중간에, 갑자기 높은 우선 순위의 긴급 작업이 요청된 경우를 다룬다. 온라인 작업 계획은 ECTP와 RCTP 알고리즘으로 나뉜다. 제안하는 ECTP 알고리즘은 PET (Parallel Emergency Tasks), SET (Serial Emergency Tasks), TSET (Three Serial Emergency Tasks)를 적용하여, 1 ms이내의 빠른 계산시간 동안 긴급 작업 스케쥴을 찾는다. RCTP 알고리즘은 긴급 작업 스케줄 이후에 남은 후속 작업들을 재계획하는 알고리즘이다. 많은 양의 작업들을 온라인으로 계획해야 하기 때문에, 한번에 계획을 하면 온라인으로 계산할 수 없다. 그러므로 매 계산 마감시간마다 로봇의 수만큼의 소량의 작업들을 브랜치 앤 바운드를 이용하여 결정하는 방법을 적용하였으며, 이로 인하여 적은 탐색 저장 공간으로 후속 작업 스케쥴을 매우 빠르게 찾을 수 있다.
