컨테이너 터미널과 같이 다수의 AGV(Automated Guided Vehicle)를 한정된 공간에서 동시에 운용하는 환경에서는 AGV의 작업생산성에 악영향을 주는 충돌, 데드락(deadlock), 라이브락(liveiock)이 발생할 확률이 높다. 또한, AGV의 가/감속 운동은 AGV의 주행시간을 예측하기 어렵게 만들기 때문에 AGV 라우팅을 더욱 어렵게 만드는 요인이다. 본 논문에서는 AGV 사이의 충돌, 데드락, 라이브락을 방지하기 위해 점유영역 예약테이블(Occupancy Area Reservation table; OAR table)을 이용하는 방법과 최적주행경로를 선택하기 위해 가감속 운동을 고려하여 AGV의 주행시간을 추정하는 방법을 제안한다. 시간중심 시뮬레이 션(time-driven simulation)을 통해 제안방안을 실험 한 결과 제안방안의 효과를 확인하였다.
컨테이너 터미널과 같이 다수의 AGV(Automated Guided Vehicle)를 한정된 공간에서 동시에 운용하는 환경에서는 AGV의 작업생산성에 악영향을 주는 충돌, 데드락(deadlock), 라이브락(liveiock)이 발생할 확률이 높다. 또한, AGV의 가/감속 운동은 AGV의 주행시간을 예측하기 어렵게 만들기 때문에 AGV 라우팅을 더욱 어렵게 만드는 요인이다. 본 논문에서는 AGV 사이의 충돌, 데드락, 라이브락을 방지하기 위해 점유영역 예약테이블(Occupancy Area Reservation table; OAR table)을 이용하는 방법과 최적주행경로를 선택하기 위해 가감속 운동을 고려하여 AGV의 주행시간을 추정하는 방법을 제안한다. 시간중심 시뮬레이 션(time-driven simulation)을 통해 제안방안을 실험 한 결과 제안방안의 효과를 확인하였다.
In the environment where multiple AGVs(Automated Guided Vehicles) operate concurrently in limited space, collisions, deadlocks, and livelocks which have negative effect on the productivity of AGVs occure more frequently. The accelerated motion of an AGV is also one of the factors that make the AGV r...
In the environment where multiple AGVs(Automated Guided Vehicles) operate concurrently in limited space, collisions, deadlocks, and livelocks which have negative effect on the productivity of AGVs occure more frequently. The accelerated motion of an AGV is also one of the factors that make the AGV routing more difficult because the accelerated motion makes it difficult to estimate the vehicle's exact travel time. In this study, we propose methods of avoiding collisions, deadlocks, and livelocks using OAR(Occupancy Area Reservation) table, and selecting best route by estimating the travel time of an AGV in accelerated motion. A set of time-driven simulation works validated the effectiveness of the proposed methods.
In the environment where multiple AGVs(Automated Guided Vehicles) operate concurrently in limited space, collisions, deadlocks, and livelocks which have negative effect on the productivity of AGVs occure more frequently. The accelerated motion of an AGV is also one of the factors that make the AGV routing more difficult because the accelerated motion makes it difficult to estimate the vehicle's exact travel time. In this study, we propose methods of avoiding collisions, deadlocks, and livelocks using OAR(Occupancy Area Reservation) table, and selecting best route by estimating the travel time of an AGV in accelerated motion. A set of time-driven simulation works validated the effectiveness of the proposed methods.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이와 같이 AGV는 주행 중에 다른 AGV에 의해 주행에 간섭을 받으며 그로 인하여 AGV의 주행에 지연이 발생한다. 따라서 AGV의 주행 시간을 보다 정확하게 추정하려면 이러한 간섭으로 인한 지연을 고려해야 하며 본 논문에서는 다음과 같은 방안을 제안한다.
데드락이나 충돌은 AGV의 교통흐름을 마비시키고 차체나 컨테이너에 손상을 가할 수있으므로 반드시 방지해야 한다. 또, 목적지까지 D 최소비용으로 컨테이너를 운반할 수 있으면 AGV의 작업효율을 향상시킬 수 있으므로 AGV 주행 경로 설정에 대한 연구는 주로 충돌, 데드락 방지 및 최소비용 경로 선택을 목적으로 한다.
본 논문에서 제안한 주행 시간 추정 알고리즘이 AGV의 주행 시간을 얼마나 정확하게 주정할 수 있는지 검증하기 위해 실제 주행시간과의 오차를 측정하였다. AGV 사이의 간섭을 고려하는 것이 주행 시간을 추정하는데 미치는 영향을 확인하기 위해 간섭을 고려하지 않고 AGV의 가감속 모델만 이용하여 주행 시간을 추정한 경우와 정확성을 비교하였다.
본 논문에서는 AGV 시스템의 작업효율을 개선하기 위하여 데드락이 발생하지 않도록 AGV의 주행 경로를 설정하는 방안과 AGV의 가감속 및 다른 AGV의 주행에 의한 간섭을 고려하여 적은 계산 비용으로 AGV의 주행 시간을 추정하는 방안을 제안하였다. 제안방안을 시뮬레이션 실험으로 검증한 결과 AGV의 작업당 평균 주행 시간이 AGV 사이의 간섭을 고려하지 않는 경우에 비해 감소함을 확인하였다.
본 논문에서는 강 등(2005)이 제안한 AGV의 이동경로를 따라 주행공간을 점유영역으로 분할하는 방안을 바탕으로 점유영역 예약테이블(Occupancy Area Reservation table; OAR table)을 이용하여 AGV 사이의 충돌, 데드락, 라이브락을 방지하는 방안을 제안한다. 또한 목적지까지의 최단시간 주행 경로를 선택하기 위해 가감속 운동 및 다른 AGV와의 간섭을 고려하여 AGV의 주행 시간을 추정하는 방법을 제안한다.
가설 설정
본 논문에서는 AGV가 등가속도 운동을 한다고 가정한다. 가속도의 법칙을 이용하여 초기속도 vo, 도달속도 V, 가속도 a 로 등가속운동하는 AGV가 길이 d인 주행경로를 주행하는데 걸리는 시간을 구하는 식을 유도한 결과는 다음과 같다.
4는 AGV 주행 경로를 할당할 때, 현재 주행 중인 AGV와 데드락 또는 라이브락을 일으키지 않도록 OAR 테이블을 작성하는 알고리즘이다. 설명의 편의를 위해 AGV는 1단위 시간에 하나의 점유영역만큼 전진하며 AGV의 길이는 두 개의 점유영역의 길이와 같다고 가정한다. OARG)는 AGV가 점유영역의 i를 점유하는 기간을 나타낸다.
크기의 터미널을 가정하였으며 터미널에는 3대의 안벽크레인과 7개의 장치장 블록이 있다. 안벽크레인과 장치장 크레인은 시간당 컨테이너 50개를 처리할 수 있다고 가정하였다. Table 1은 살험에 사용한 AGV의 사양이다.
한다. 첫째, 하나의 점유영역을 여러 대의 AGV가 동시에 예약할 수 없다. 둘째, AGV는 이미 여러 개의 점유영역을 예약한 상태에서 다음 점유영역 예약을 시도한다.
1과 같이 선석 하나 .크기의 터미널을 가정하였으며 터미널에는 3대의 안벽크레인과 7개의 장치장 블록이 있다. 안벽크레인과 장치장 크레인은 시간당 컨테이너 50개를 처리할 수 있다고 가정하였다.
제안 방법
주행시간과의 오차를 측정하였다. AGV 사이의 간섭을 고려하는 것이 주행 시간을 추정하는데 미치는 영향을 확인하기 위해 간섭을 고려하지 않고 AGV의 가감속 모델만 이용하여 주행 시간을 추정한 경우와 정확성을 비교하였다. Table 2는 20000회의 주행경로를 대상으로 오차를 측정한 결과를 나타낸다.
방안을 제안한다. 또한 목적지까지의 최단시간 주행 경로를 선택하기 위해 가감속 운동 및 다른 AGV와의 간섭을 고려하여 AGV의 주행 시간을 추정하는 방법을 제안한다. 제안방안은 충돌, 데드락, 라이브락이 발생하지 않음을 보장하며 적은 계산비용으로 AGV의 주행 시간 추정이.
AGV의 수를 6대에서 24대까지 3대씩 변화시켜가며 각각 실험하였다. 매 실험마다 AGV는 24시간 동안 양하 작업을 수행하였으며 5회씩 반복하여 결과를 평균하였다.
본 논문에서는 점유영역 예약 테이블 (OAR table; Occupation Area Reservation table)을 이용하여 데드락과 라이브락을 해결한다. OAR 테이블은 주행 경로 상의 각 점유영역을 AGV가 예약한 시점부터 AGV가 점 유영 역을 완전히 이탈할 때까지의 점유 기간을 기록한 테이블이다.
세 가지 주행 경로 설정 방안에 대해 각각 시뮬레이션을 수행하고 결과를 비교하였다. 최단 예측 시간 방안은 제안방안을 이용하여 AGV사이의 간섭을 고려하여 주행 시간을 추정하고 추정치가 가장 작은 이동 경로를 선택한다.
셋째, 어떤 AGV가 먼저 예약한 점유영역을 다른 AGV가 강제로 예약을 풀어 자신이 예약할 수 없다. 제안 알고리즘은 OAR 테이블을 작성할 때 뒤에 출발한 AGV가 먼저 점유영역을 예약할 수 있더라도 앞서 출발한 AGV가 이후에 그 점유영역을 예약하려 한다면 뒤에 출발한 AGV가 예약을 포기하고 그 이전 점유영역에서 대기하도록 점유 기간을 조정한다. 따라서 데드락이 발생하기 위한 세 번째 필요조건을 만족하지 않으므로 제안방안을 이용하여 설정한 주행 경로는 데드락이 발생하지 않는다.
또한 목적지까지의 최단시간 주행 경로를 선택하기 위해 가감속 운동 및 다른 AGV와의 간섭을 고려하여 AGV의 주행 시간을 추정하는 방법을 제안한다. 제안방안은 충돌, 데드락, 라이브락이 발생하지 않음을 보장하며 적은 계산비용으로 AGV의 주행 시간 추정이. 가능하기 때문에 실시간 적용에 적합하다.
가능하기 때문에 실시간 적용에 적합하다. 제안방안을 시뮬레이션 실험으로 검증함으로써 AGV의 작업 당 주행 시간이 감소함을 검증하고자 한다.
주행 시간 추정 알고리즘을 AGV의 주행 경로 설정에 적용하였을 때의 주행 시간 감소 효과를 확인하기 위해 시뮬레이션 실험을 수행하였다. AGV의 수를 6대에서 24대까지 3대씩 변화시켜가며 각각 실험하였다.
대상 데이터
수행하였다. AGV의 수를 6대에서 24대까지 3대씩 변화시켜가며 각각 실험하였다. 매 실험마다 AGV는 24시간 동안 양하 작업을 수행하였으며 5회씩 반복하여 결과를 평균하였다.
성능/효과
본 알고리즘에서 Ts(0, T0의 값은 AGV에 주행경로를 설정할 때 모의 주행 시뮬레이션을 통해 주행 경로상의 각 점유영역을 예약하기 시작하는 시간과 완전히 이탈하는 시간을 OAR테이블에 기록하므로 교차점 i를 포함하는 후점유영역을 찾은 후 OAR 테이블을 검색하여 얻을 수 있다.
둘째, AGV는 이미 여러 개의 점유영역을 예약한 상태에서 다음 점유영역 예약을 시도한다. 셋째, 어떤 AGV가 먼저 예약한 점유영역을 다른 AGV가 강제로 예약을 풀어 자신이 예약할 수 없다. 제안 알고리즘은 OAR 테이블을 작성할 때 뒤에 출발한 AGV가 먼저 점유영역을 예약할 수 있더라도 앞서 출발한 AGV가 이후에 그 점유영역을 예약하려 한다면 뒤에 출발한 AGV가 예약을 포기하고 그 이전 점유영역에서 대기하도록 점유 기간을 조정한다.
9는 AGV가 안벽에서 장치장 블록으로 주행할 때의 평균 주행거리와 주행 시간이다. 장치장에서 안벽으로 주행할 때와는 달리 최단 예측 시간 방안과 최단거리방안이 거의 동일한 주행시간을 보였다. 안벽에서 장치장 블록으로 주행하는 경우 안벽크레인의 작업 사이클 타임 때문에 한 번에 주행할 수 있는 AGV는 안벽크레인의 수와 같은 3대이다.
제안방안을 시뮬레이션 실험으로 검증한 결과 AGV의 작업당 평균 주행 시간이 AGV 사이의 간섭을 고려하지 않는 경우에 비해 감소함을 확인하였다.
후속연구
Reveliotis(2000)는 존 제어방식을 바탕으로 하나의 존을 지날 때마다 주행 경로의 안전성과 작업성과를 고려하여 다음에 지나갈 존을 결정함으로써 이러한 불확실성에 적절히 대응하는 주행경로 설정 방안을 제안하였다. 제안방안 역시 불확실한 환경에 적용하기 위해서는 예측하지 못한 상황변화를 감지하고 새로운 상황에 맞추어 주행 계획을 수정하거나 새로 수립하는 방안에 대한 연구가 필요하다.
향후, 제안한 주행 시간 추정 알고리즘을 주행경로 선택뿐만 아니라 AGV의 컨테이너 운반계획을 수립할 때, 운반계획대로 작업을 진행하였을 때 전체 작업 완료에 걸리는 시간을 추정하는 데 적용하는 방안에 대한 연구가 필요하다.
참고문헌 (9)
강재호, 최이, 강병호, 류광렬, 김갑환(2005), '자동화 컨테이너 터미널에서의 AGV 충돌 방지 및 교착 해결 방안', 한국지능정보시스템학회지 11권 5호, pp.25-43
이용환, 박은경, 박태진, 류광렬, 김갑환 (2003), '그리드 단위의 제어에 기반한 자동화 컨테이너 터미널의 AGV운영 방안', 한국항해항만학회지 27권 2호, pp.223-231
Evers, J. J. M and Koppers, S. A. J. (1996), Automated guided vehicle traffic control at a container terminal, Transportation Research- A 30, pp. 2134
Kim, C. W. and Tanchoco, J. M. A (1991), 'Conflict-free shortest-time bidirectional AGV routing', International Journal of Production Research, 29(12), pp. 2377-2391
Kim, K. H., Jean, S. M. and Ryu, K. R. (2004), 'A deadlock detection method for automated guided vehicles in port container terminals', Proceedings of the 33rd international conference on computers and industrial engineering
Rajeeva, L. M., Wee, H. G., Ng, W. C., and Teo, C. P., (2003), 'Cyclic deadlock prediction and avoidance for zone-controlled AGV system', International Journal of Production Economics 83, pp. 309-324
Reveliotis, S. A. (2000), 'Conflict resolution in AGV Systems', IEEE Transactions, Vol. 32, pp. 647-659
Yeh, M. S. and Yeh, W. C. (1998), 'Deadlock Prediction and Avoidance for Zone-control AGVs', International Journal of Production Research, Vol. 36, No. 10, pp. 2879-2889
※ AI-Helper는 부적절한 답변을 할 수 있습니다.