다중 무인운반차량 시스템에서의 동적 라우팅과 스케줄링

무인 운반차량 시스템(AGV System)의 이용도가 날로 증가함에 따라 시스템의 최적화 및 운영방법에 관한 많은 연구가 진행되고 있다. 이에 본 연구에서는 AGV System에서 사용하는 Routing 및 Scheduling 정책들을 연구하고 이를 개선할 수 있는 새로운 방안을 모색한 후, 컴퓨터 모델링 기법을 이용한 보다 객관적인 시뮬레이션을 수행하여 최적의 AGV System과 그에 적합한 운영 정책을 제시하는데 그 목적이 있다. 따라서 본 논문은 크게 AGV Routing과 Scheduling에 관한 연구로 나누어진다.
AGV Routing은 AGV의 이동경로를 설정하는 것으로서 충돌 방지(Collision Avoidance)와 최단경로 탐색(Minimal Cost Path Find)이라는 두개의 주요 알고리즘으로 이루어진다.
AGV Scheduling은 장비의 공정시간과 AGV의 Loading/Unloading, Charging 시간으로 인해 불규칙한 Event가 일어났을 경우 AGV 각각의 Jop을 알맞게 선정해주는 정책을 말하며 일반적으로 AGV Selection Rule, Charging Rule이 여기에 속한다.
본 연구에서는 이러한 알고리즘들이 반영된 AGV System을 컴퓨터 모델로 구축하고, 기존 시스템에서 사용되고 있는 여러 운영정책들의 문제점들을 분석하였으며, Multiple AGV System을 최적화 시키는 운영정책이 보다 객관적으로 제시되었다.


I. Introduction

1. Description of MAGVS
AGV System이란, 무인 운반 차량 시스템 또는 자동 반송 차량 시스템이라 하며, 이는 차량의 운전자 없이 어떤 짐을 임의의 목적지까지 정해진 경로를 따라 자동으로 반송해 주는 시스템을 말한다.
AGV System에 관련된 연구분야는 크게 시스템의 설계, 운영, 구현의 세가지로 구분할 수 있다.
시스템의 설계에는 필요차량의 대수 결정, 경로(Guide Path)의 종류 및 설계, AGV의 종류 등이 있고, 시스템의 운영에는 발주법(Scheme of AGV Routing), 충돌방지(Collision Avoidance) 등이 있다.
AGV System의 종류는 Guide Path의 구조와 AGV 대수에 의해서 구분된다. 크게 Single Loop - Single AGV와 Multiple Loop - Multiple AGV로 나뉘어 진다. 본 논문에서는 최근 기업에서 그 사용이 증가하고 있는 Multiple Loop - Multiple AGV System에 관하여 논하고자 한다.

2. Motivation of This Research
1970년대 이후 생산성의 증대를 위한 많은 연구와 기술 개발이 이루어지고 있다. 그 중 유연 생산 시스템(FMS : Flexible Manufacturing System)과 유연 조립 시스템(FAS : Flexible Assembly System)이 대표적이다.
이들 시스템은 환경의 변화에 유연한 생산 체계를 갖춰서 이에 쉽게 대처하자는 것인데 , 여기에 필수적인 것이 물류의 자동화이다. 하지만 이제까지는 물류비용이 생산의 상당 부분을 차지함에도 불구하고, 생산품의 질과는 별로 상관이 없기 때문에 그 동안 많이 고려되지 않았다. 그러나 효율적인 생산을 요구하는 시대적 흐름에 의해 물류 시스템은 빠른 속도로 발전되어 가고 있다. 1970년대 후반부터는 AGV System이 자동화된 물류 시스템의 중요한 역할을 담당하고 있으며, 그 사용도 확대되어 가고 있다. 특히 시스템의 특성상 복잡하고 규모가 큰 반도체 FAB 라인에서는 AGV System의 의존도가 점점 높아지고 있다. 이제 AGV는 자동화된 물류 시스템이나 유연 생산 시스템에서 없어서는 안 될 하나의 중요한 요소로 자리잡고 있다.
이에 본 논문에서는 Multiple AGV System을 대상으로 기존의 문제점들을 분석하기 위하여 객관적인 컴퓨터 모델을 구축하였으며, 시스템을 최적화 시키는 운영정책을 연구 개발하였다.

II. Modeling Descriptions

1. Layout of MAGVS
1) Guide Path : AGV가 실제로 이동할 수 있는 안내선이다. 케이블이나 광 센서로 구축되어 있다.

2) Control Point : AGV가 멈출 수 있는 곳, Node라고 해도 무방하다. AGV는 Control Point에서 Loading /Unloading과 Parking 등 작업을 수행할 수 있다.
3) Parking Point : 더 이상의 할당된 작업이 없는 AGV가 대기하는 장소
4) Recharging Point : AGV가 충전하는 장소. 시스템에 있는 AGV 대수와 일치
5) MIC : Moving in Complete. Load가 AGV로 실어지는 마지막 Conveyor.
6) Block : AGV의 출입을 제한하는 구역. 흔히 충돌 및 혼잡 방지를 위해 사용된다.
7) Stack Area : AGV System으로 들어가는 Load들이 대기하는 일종의 Queue.
8) Machine : AGV System 내에 있는 장비.

2. Specification of MAGVS
1) AGV Specification
AGV의 기본적인 Spec.은 아래 <표 1> 과 같다. AGV에는 Spin 방식과 Crab 방식이 있다.
Spin 방식은 분기점에서 90도 회전을 해야 하므로 속도가 느린 반면, Crab 방식은 회전 없이 옆으로 이동 가능한 방식으로써 Spin 방식에 비해 빠르다.
2) Guide Path Specification
<그림 1>에서 보듯이 Guide Path의 구조는 두 개의 Main Line이 가로로 놓여 있고 이것을 잇는 여러 개의 Path들이 놓여져 있다. 따라서 Multiple Loop인 경우에 해당되며 Path의 종류는 양방향(Bi-directional) 이다.
3) MIC & Machine
Conveyor로 구성되어 있는 MIC는 Accumulate 방식으로 Load가 들어오는 차례대로 쌓이게 되며 MIC의 Load Capacity는 4개이다.
시스템에 있는 장비는 AGV와의 Interface를 위하여 I/O Port를 가지고 있다. AGV위에 있는 로봇 팔은 I/O Port의 문이 열리면 장비로 건네주게 된다.

3. Functional Architecture
전체 시스템을 운영하는 주요 모듈들은 크게 3부분으로 나누어지는데, 이는 <그림 2> 와 같다.

1) Layout Management Module
a) Encoding Control Point Function
Guide Path 위에 있는 여러 개의 Control Point들을 약속된 Number로 Code화함으로써 스케쥴러가 사용하기 편하게 인터페이스 해주는 함수이다. Main Path 위에 있는 Control Point들은 서로 1 만큼의 차이를 가지고 있다.
MIC 앞에 있는 Control Point부터 차례로 Cpa1, Cpa2,...순으로 이름짓고, 반대편 Main Line 위에 있는 Control Point도 역시 Cpb1, Cpb2,... 순으로 이름지었다. 하지만 50 ∼ 60개 정도 되는 Control Point를 컴퓨터가 쉽게 제어하려면, 문자로 되어있는 Control Point 이름을 숫자화 하는 것이 필요하다. 즉, Cpa1 = 101, Cpa2 = 102, ..., Cpb1 = 201, Cpb2 = 202, ... 로 일대일 Mapping을 해줌으로써 효율적인 제어가 가능하게 된다. 이러한 숫자를 Coded Number라 하자.

b) Mac hine Control Point Mapping Function
AGV는 Load를 싣고 할당된 장비로 가게된다. 이때 실제로는 장비 앞에 있는 약속된 Control Point로 이동하는 것이다. 그렇다면, 여러개의 Control Point 중에서 Load/Unload Point들을 미리 기억하고, Parking Point, Recharging Point 역시 미리 기억하고 있어야 한다.

2) Job Scheduling Module
Stack Area에 쌓여 있는 Load들을 장비에 할당해 주는데는 알맞은 정책이 필요하며, 이는 전체 시스템의 Performance에 영향을 미치고 Bottleneck을 조정할 수 있다는 차원에서 매우 중요한 부분이다. Job Scheduler는 Stack Area에 있는 Load중 임박한 작업을 요하는 Load를 장비에 할당해 주어야 한다.
Job Scheduler가 갖추어야 할 두가지 요건은 공평성(Fairness)과 응답시간의 최적화(Minimize of Response Time)이다. Fairness는 Stack Area에 있는 모든 Load들이 얼마나 공평하게 Dispatch 되는가에 초점을 두고, 응답시간의 최적화는 Stack Area에서 Load들이 지연되는 시간을 얼마나 줄이는가에 초점을 둔다.
a) Scheduling Scheme Management Part
Job Scheduler가 가지게 되는 Scheme을 선정한다. 본 연구에서 실험한 정책은 First In First Out(FIFO)와 Round Robin, First Available Job, Shortest Job First, Dynamic Priority Scheduling으로 모두 5개의 Scheme이 적용되었다.
FIFO(First In First Out) : Load가 들어오는 순서대로 장비를 할당해 준다.
이 정책은 Stack Area에 먼저 들어 온 Load가 나중에 들어오는 Load에 영향을 줌으로 공평성(Fairness)이 떨어지며 응답시간(Response Tim)도 좋지 않다.
Round Robin : Scheduler는 일정시간 동안 Load에 장비를 할당해 준다. 따라서 모든 Load는 일정한 시간(Time Quantum) 동안만 공정을 하고, 다음 Load를 위해서 양보해야 한다. 따라서 이 정책은 높은 Response Time을 갖지만 공평성이 없다.
First Available Job : 장비에 할당 가능한 Load 순서대로 선택한다.
Shortest Job First : Stack Area에 있는 Load 중에서 가장 짧은 공정시간을 갖는 순서대로 선택한다. 이는 Turnaround Time을 줄일 수 있다.
Dynamic Priority Scheduling : Scheduler는 Stack Area 에 있는 Load에 Priority를 부여한다. 이때의 기준은 shortest job available 정책을 따르지만, 공정의 Deadline Time이 적용되어서 Recharging 하게 된다.

b) AGV Selection Part
Job Scheduler는 장비에 일을 할당하면서 전송할 AGV를 먼저 선택해주어야 하는데 이때 여러대의 AGV가 있는 경우 즉, MAGVS인 경우 알맞은 AGV를 선택해야 한다. 따라서 AGV Selection Rule에 여러가지 Scheme들을 적용해야 하는데, 이때 Scheduler가 고려해야 하는 점은, AGV가 현재 위치에서 Load를 싣기 위해 이동해 오는데 낭비되는 시간 (Empty Travel Overhead)을 최소화해야 하고, Load가 AGV를 요청한 시간부터 할당받은 장비로 들어가야 하는 최종시간(Deadline Requirement)을 엄수해야 한다는 점, 그리고 AGV의 Utilization을 고려해서 최종적으로 AGV를 선택해야 하는 것이다.
이러한 관점에서 본 연구에서는 AGV Selection Rule 에 반영할 Scheme으로 First Available, Nearest , Least Utilized, Advanced AGV Selection Rule을 가지고 실험하였다.
First Available AGV : 여러 개의 AGV 가운데 첫 번째로 사용 가능한 AGV를 선택한다. 이러한 정책은 AGV의 Retrieve Time이 커지는 경향이 있다.
Nearest AGV : Load의 현 위치에서 가장 가까이 있는 AGV를 선택한다. 이러한 정책은 AGV의 Retrieve Time을 줄이긴 하지만 전체 AGV의 Utilization이 줄어드는 현상이 일어난다.
Least Utilized AGV : 현재까지 Utilization이 가장 작은 AGV를 선택한다. 이는 AGV의 Retrieve Time이 커지긴 하지만 전체 AGV의 Utilization을 높이는 경향이 있다.

c) Parking Management Part
AGV의 일이 끝난 후 더 이상 수행해야할 일이 없을 때 AGV는 Parking 상태로 들어간다. 그러나 이때 Parking 하는 장소는 매우 중요하다.
정해진 Parking Point로 이동할 것인지 아니면 마지막 수행했던 장소에 그대로 Parking 할 것인지 결정해야 한다. 본 연구에서 실험한 Parking Scheme 두 가지는 Reserved Parking Point로 이동하는 것과 Last Job Point에서 Parking 하는 것이다.

d) Recharging Management Part
AGV는 자체적으로 Battery를 내장하고 있어서 일정한 수준에 이르면 재충전을 해주어야 한다. 이는 Job Scheduler에게는 상당히 중요한 과제이다. Job Scheduler는 모든 AGV의 현재 Battery Level을 일정한 시간 간격으로 체크해서 필요하면 Recharging 수행 루틴에 들어가야 한다. 이는 모든 Job들 보다 높은 Priority를 가지며 그 방식은 다음과 같다.
Time Calculation : AGV가 충전했던 시간을 기억해 두고서 일정 시간이 지나면 무조건 재충전을 하는 방식이다.
Distance Calculation : AGV가 이동할 때마다 그 이동 거리를 누적하면서 일정 거리 이상 운행하였을 때 재충전하는 방식이다.
Advanced Time Calculation : AGV가 Battery를 사용하는 경우에 따라 다르게 계산하는 방법이 있다. 즉, AGV의 Travel Time에서 사용되는 Battery의 양과 Working Time, Loading/ Unloading Time에서 사용되는 Battery의 양은 다르므로 이를 양분하여 계산하는 방법이 있다. (예, Total Time = Travel Time * 0.3 + Working Time * 0.7)

3) Traffic Control Module
MAGVS에서 Traffic Control이 반드시 필요한 이유는 크게 두 가지가 있다. 하나는 Collision Avoidance이고 또 하나는 Congestion Handling이다.
a) Routing Scheme Management Part
본 연구에서 실험할 Routing Scheme 대상은 경로 예약 방법(Reserved Path Routing)과 동적 우선권 방법(Dynamic Priority Routing)이다. Reserved Path 방법은 AGV가 이동할 전체 경로를 미리 예약하고 이동하는 방법이고 Dynamic Priority 방법은 경로 예약 없이 AGV가 처한 상황에 맞는 우선권을 주는 방법이다.

b) Collision Avoidance Part
MAGVS에서 목적지까지 최단거리로만 운행하다 보면 반드시 충돌이 일어나므로 이를 방지하기 위한 정확한 제어가 필요하며, 실제로 이것은 중앙 컴퓨터에 의해 제어된다.
본 논문에서 제안하는 제어 방법은 다음과 같다. 우선 AGV가 이동하는데 있어서 기본적으로 고려해야 할 것은 첫째, 각 Control Point의 Capacity이다. Capacity가 1이라는 것은 그 Point가 Free라는 뜻이며, Capacity가 0이라는 것은 그 Point가 점유 (Occupied)되었다는 뜻이다. 두번째, 전체 Control Point가 Coded Number로 변환되어 있다는 사실이다. 이는 Controller가 정확한 제어를 가능하게 해주기 때문에 매우 중요하다.
세번째, Main Path와 Sub Path에는 Priority가 있다는 것이다. 만약 목적지가 동일 Main Path상에 있으면 그대로 직진하고, 반대로 다른 Main Path상에 목적지가 있으면, Sub Path로 먼저 이동 후 Main Path로 이동해야 한다. 절대로 Main Path로 이동 후 Sub Path로 이동해서는 안 된다. 왜냐하면, AGV의 Parking 동작시 Forward나 Backward 일 때는 문제없지만 Crab으로 이동해온 AGV는 Parking 하기 곤란하기 때문이다.
예를 들어 <그림 4>와 같은 상황에서 AGV가 어떻게 충돌을 피해 가는지 살펴보도록 하자. 우선 AGV1의 목적지는 Cpa7이며 AGV2의 목적지는 Cpa1이다.
현재 AGV1은 Cpa2에서 Cpa3으로 이동 중이며 AGV2는 Cpa4에 있으며 목적지까지 최단 거리로 가기 위해서는 Cpa3으로 이동해야 한다. 그러나 AGV1은 짐을 싣고 있으며, AGV2는 비어 있는 상태이다. 따라서 AGV1이 더 높은 Priority를 가지며 AGV2가 양보해야 한다. 그리고 AGV1은 그대로 직진할 수 있게 해야 한다.
그러면 실제 Coded Number의 계산은 어떻게 되는지 살펴보자. AGV2는 Cpa4에 있으므로 Coded Number가 104이다. 최단거리로 목적지에 가야하기 때문에 Coded Number - 1(= 103)을 해준다. 그러나 103 Control Point로 갈 수 없기 때문에, Sub-path로 Crab 한다. 즉, 현재 Coded Number 103에 101을 더해줌으로써 ( 103+101 = 204 ), AGV2는 Cpb4로 가게된다. 그리고 다시 충돌 방지 함수를 호출하게 된다. 그러나 AGV1은 약간 다르다 AGV2가 Cpa4에서 Cpb4로 이동 중에 있으면 Cpa4는 아직 Capacity가 없기 때문에 진입이 불가능하다. 그래서 직진해야 함에도 불구하고 충돌 방지 함수를 호출하게 된다. 이때 AGV1은 짐을 가지고 있고 AGV2는 비어 있으므로 충돌 방지 함수에서는 AGV1에게 더 높은 Priority를 부여하고 적당한 시간만큼 Cpa3에서 멈추게 해줌으로써 충돌 방지를 하게 되는 것이다.
AGV2는 Cpb4로 양보하지만 목적지는 Cpa1로 변하지 않으며 Main Path 보다 Sub Path가 우선되어야 한다. 그러나 AGV1에 의해서 Sub Path로의 진입이 불가능함으로 AGV2는 Cpb3으로 다시 양보하게 된다.
지금까지 설명된 예에서 두 개의 AGV가 어떻게 Control Point를 소유하게 되는지 <표 6>과 <표 7>에서 설명하도록 하겠다.

III. Dynamic Priority Routing
Traffic Control에서 혼잡 및 충돌 방지가 가장 중요하다. 이를 해결하기 위해서 흔히 경로 예약 방법을 사용하는데, AGV의 Performance를 고려할 때 Dynamic Priority Routing과 비교하여 살펴보도록 하자.

Dynamic Priority Routing(DPR)이란?
최단경로를 탐색하고 설정한 AGV가 목적지까지의 전체 경로를 미리 예약하지 않고, Next Control Point만을 예약하며 이동하도록 하는 것이다. 따라서 충돌이 일어나지 않을 경우는 최단경로를 따라서 이동하지만 충돌이 일어날 경우에는 그 상황에 맞게 각 AGV에게 Priority가 부여되고, 양보할 AGV는 Sub Path로 가게 된다.
이때 중요한 것은 AGV의 상황에 따라 Priority 가 주어져야 한다는 것이다. AGV의 상태(Status)는 <표 8>에서와 같이 7가지로 구분할 수 있다고 할 때 각 상황에 따라 어떻게 Priority가 결정되는지 알아보도록 하자. Priority가 어떻게 결정되는지 아래 그림을 보고 이해하도록 하자. ① Recharging하고 있거나 Recharging 하러 가는 AGV가 우선된다.
② Loaded AGV가 Empty AGV보다 우선된다.
③ 싣고 있는 Load가 공정이 완료된 상태인 AGV 보다 공정을 받으러 이동중인 Load를 싣고 있는 AGV가 우선된다.
④ Parking중인 AGV보다 작업을 할당받은 AGV가 우선된다. 따라서 이 경우 Parking중인 AGV가 Wakeup Procedure를 거쳐 다시 Active되어야 하고 곧바로 양보 수행 루틴으로 들어가야 한다. 일반적으로 여러 곳에 Parking Point가 있을 경우 비어 있는 다른 Parking Point로 이동하게 된다.

IV. Conclusions and Recommendations
지금까지 우리는 Multiple AGV System을 대상으로 여러가지 실험을 하였고, 이에 바탕을 두어 본 논문에서는 시스템을 최적화시키는 여러 운영정책들을 제안하였으며 이는 앞으로 많은 분야에서 활용되리라 본다.
실험에서 보다 정확한 결과를 얻기 위해서 전체 운영 구조를 Layout Management와 Job Scheduling과 Traffic Control Part로 구분하였고, 세부적으로 Job Scheduling에는 Dynamic Priority Scheduling과 Least Utilized AGV Selection Rule이 상대적으로 우수한 평가를 받았다.
Parking Scheme에는 Last Job Point Parking 정책이 좋은 점수를 받았고, Recharging Scheme에는 Advanced Time Calculation이 효율적인 것으로 검증되었다. 그리고 마지막으로 이 논문의 중점적인 관심이었던 Traffic Control Scheme에는 Dynamic Priority Routing Scheme이 우수한 성능평가를 받았다.
향후 본 연구에서 개선할 점은 Layout의 변화에 크게 종속되지 않고 AGV System을 시뮬레이션 할 수 있도록 시스템의 설계와 운영이 좀더 독립적인 모듈로 개발되고 세분화되어야 할 것이다.




References

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Fivest, “Introduction to Algorithms", The MIT Press, Cambridge, England, 1989.
[2] Andrew S. Tanenbaum, “Modern Operating Systems", Prentice Hall Inc., 1992.
[3] Madhav Ram Vemoory and Hsu Wen Jing, “Scheduling and Routing of AGVs", The Fifth International Conference on Control, Automation, Robotics and Vision, 1998.
[4] A. J. Bostel and V. K. Sagar, “Dynamic control systems for AGVs,” IEE Computing & Control Engineering jounal, 1996.