성안당 더테이블 2018.03.21

홈 > 지식커뮤니티 > 지식채널

ATM아이엔씨 2018.01.05


이달의 매거진
잡지이미지
잡지이미지
잡지이미지
잡지이미지
잡지이미지
잡지이미지
  • 구독신청
  • 광고안내

지맨스 기사본문

중대형 물류센터 적용 가능한 물류운송로봇 스케줄링 기술 개발 (2)

입력 : 2018.03.17 01:05

글자크게보기 글자작게 댓글달기 좋아요 즐겨찾기

페이스북 트위터 카카오스토리 블로그

[첨단 헬로티]

 

중대형 물류기업용 저가형 관제기술 확보 등 다양한 효과 기대


국내의 물류기술을 살펴보면 지게차, 컨테이너, 파렛트 등 일반 물류기기장비의 경우는 기술개발 수준과 국산화율은 높으나 자동인식, 자동피킹, 자동소팅 등 자동화기술과 AGV, 무인지게차 등 무인고도장비기술 등은 2년 정도 뒤진 것으로 나타났다. 이러한 상황에서 국내 기술개발 필요성에 따라 본지는 ‘중대형 물류센터 적용이 가능한 물류운송로봇 스케줄링 기술 개발’ 사례를 2회에 걸쳐 싣는다. 


라. 물류운송로봇 스케쥴링 알고리즘

물류운송로봇의 스케쥴링 문제는 사용자가 주문한 물품 목록을 최소의 비용으로 수집할 수 있도록 로봇의 작업순서를 결정하는 문제다. 이것은 물품 목록 정보와 물류 창고의 물품 보관 상태로부터 최적의 작업순서를 제시하는 것이며, 이는 처리시간이 최소가 되도록 작업순서를 결정하는 문제와 같다고 볼 수 있다.


Order picking 시스템에서 AGV 관제의 가장 중요한 부문 중 하나는 물품 목록을 대기 중인 AGV인 한정된 자원에 할당하는 것이 된다. 이러한 관점에서 고려해야할 것은 다음과 같은 것들이 있다. 먼저 창고 내의 물품 보관소에서 피킹 룸으로 물품을 이동시키기 위해 유휴한 AGV를 선택하여 작업을 할당한다. 다음으로 서비스 요구는 이용 가능한 AGV의 집합 중에 선택될 것이고, 대기상태의 AGV는 창고의 작업 위치들 중에 한곳에서 물품을 배달하게 된다.


(1) ‌Queueing 모델 기반 다중 로봇의 작업부하 분석 및 분배 알고리즘 개발

물품 보관창고 및 피킹 룸은 AGV가 물류의 이적재를 수행하는 곳으로 AGV 시스템으로 물류 전송요구가 전달되면 최적의 AGV를 선택하고 물류전송이 요청된 장소로 AGV를 차7로 이동시키게 된다. 이동된 AGV는 물품 보관창고에 있는 물품을 적재하여 피킹 룸에 이재함함으로써 물류전송요구의 수행을 완료하게 된다.


시뮬레이션에서사용한 작업장소는 적재장소(load station), 이재장소(unload station), 대기장소(wait station), 충전장소(charge station)으로 구분하였고 각각 다음 표와 같은 특성을 가지고 있다[1].


▲ 표3. 시뮬레이션에서사용한 작업장소


명령어 처리자는 명령어를 수신하는 큐를 가지고 있으며, 시뮬레이션 과정에서는 서버로부터 명령을 전달받지 않기 때문에 사용자가 만든 jobs.txt 파일로부터 명령을 가져와서 작업부하 분석 및 분배 알고리즘으로 단위 작업을 처리하도록 지시한다.


▲ 그림14


jobs.txt 파일에 기록된 작업의 형태는 다음과 같다.

• Jobs.txt : time, things1, things2, things3, …

• 작업장소 : ‌load station, unload station, wait station, charge station

• 로봇상태 : ‌moving, waiting, loading, unloading, returning, charging


큐에서 작업을 꺼내 로봇에 job을 할당하는 프로세서는 다음과 같다.


▲ 그림15


(2) ‌다중 로봇간 경로 간섭 최소화 및 교차로/병목 지점에서 우선순위 방식 충돌 회피 알고리즘 개발

현재 운행중인 다른 AGV의 전체 이동 경로를 고려하여 최단경로를 탐색하더라도 각 AGV의 경로상에서 정확한 위치 및 돌발적인 상황을 모두 고려할 수 없기 때문에 AGV의 운행중인 경로상에서 간섭 및 데드락이 발생할 수 있게 된다. 만일 이러한 요소를 모두 고려하여 AGV의 경로를 탐색하게 된다면, 대량의 AGV가 운행되는 환경에서는 고려해야 할 요소가 증가할 뿐만 아니라 계산 과정도 기하급수적으로 증가하게 된다[3].


다음 그림에서는 충돌회피 알고리즘이 적용되지 않은 상황에서의 시뮬레이션 모습을 보여주고 있다. 두 개의 경로가 만나는 구간에서 동시에 진입한 두 AGV가 더 이상 전진하지 못하고 멈춰선 모습을 볼 수 있다.


▲ 그림16


▲ 그림17


복도와 같이 좁고 긴 구간을 설계할 때 실제 AGV가 차지하는 부피에 의해 왕복 운행이 불가해 질 수 있다. 우선적으로 경로 간섭을 최소화 하기 위해서는 AGV의 이동 경로를 양방향이 아닌 단방향으로 할 필요가 있으며, 복도와 같은 구간에서는 왕복 경로보타는 트랙을 도는 형태로 경로를 설계할 필요가 있다. 하지만 이러한 방식의 설계가 불가능할 때는 부득이 왕복 경로의 간섭을 최소화 하는 방법이 필요하다.


이를 해결하는 방법으로는 미리 복도에 진입한 AGV가 있을 때는 반대편에서 진입하는 AGV에 대해 진입을 차단하는 방법이 필요하다. 이를 위한 복도 구간의 로컬 신호체계가 필요하게 된다.


다음 그림에서와 같이 2대의 로봇이 동시 진입 가능한 Case 1, 2, 3의 신호 체계가 도입된 환경을 고려해 보자. 신호 체계의 도입 대상은 정합지점, 교차로, 왕복 1차로의 양 끝 지점이 된다.


신호 표시:

- Red: 다른 경로에서 로봇이 진입한 상태

- Green: 진입 차선에 로봇이 없는 경우

- Red/Green: 진입 차선 모두에 로봇이 대기중인 경우


(가) 복도 진입 대기구간의 신호체계

점유 경로를 먼저 진입한 AGV에게 경로 점유권을 주고 맞은 편의 진입 시간이 늦은 AGV에게는 대기하도록 한다. 먼저 진입한 AGV가 경로를 벗어날 때까지 대기하도록 하는 것이다. AGV가 진입 후 경로를 탈출하기까지 시간이 걸리기 때문에 진입 방향이 동일한 AGV는 진입이 허용되도록 하여야 한다. 하지만 이렇게 되면 AGV의 흐름이 단방향으로만 진행되며, 반대방향의 AGV는 무한정으로 기다려야만 할 경우가 생긴다. 이러한 경우를 방지하기 위해서는 일정한 시간동안만 한쪽 방향의 AGV가 진입하도록 해야 하며, 할당한 시간이 끝난 후에는 반대편 방향의 AGV가 진입될 수 있도록 해야한다.


또한, 교차로에서는 한 개 이상의 방향에서 진입한 AGV들에 의해 데드락 상태가 발생할 수 있다. 그렇기 때문에 AGV의 데드락 상태를 방지하기 위한 알고리즘은 필수적이며, 데드락 해소를 위한 신호체계가 설계되어야 한다.


(나) 교차로 진입 대기구간의 신호체계

교차로에서의 데드락 해결 방안은 복도 진입과 달리 교차로의 점유 시간이 짧은 것이 특징이다. 따라서 교차로의 점유권은 항상 먼저 진입한 AGV에게 할당되며, 이후 진입한 AGV에게는 대기하거나 회피하도록 한다.


상기와 같이 복도나 교차로에서의 경로 간섭이나 데드락을 예방하는 방안은 모든 AGV가 따르는 신호 체계의 도입과 노드에 먼저 진입하는 AGV에게 점유권을 할당함으로서 데드락 상태를 해결가능하다.


(3) ‌호출 예상위치 및 물류 부하를 고려한 실시간 스케줄링 알고리즘개발

AGV의 스케줄링 방법으로 주로 사용되는 방식들을 다음과 같은 것들이 있다[2].


* STT/D(Shortest Travel Time/Distance) rule: AGV가 하역한 후, 현재 위치에서 가장 가까운 거리에 있는 작업장을 선택하여 우선적으로 서비스를 진행하는 방법이다. 가장 기본적인 스케쥴링 방법으로 일반적으로 사용되는 방식이다.


* MEVTT(Minimum Empty Vehicle Travel Time) rule: AGV가 빈 상태로 이동하는 것을 최소화하는 것이 목적이다. AGV가 현재 위치한 작업장과 외부로부터 자재들이 시스템으로 유입되는 장소에 우선적으로 서비스를 하며, 이에 해당 사항이 없으면 현 위치에서 수요가 발생한 작업장까지의 거리를 해당 작업장을 서비스하는 경우 연속적으로 서비스할 수 있는 총 횟수로 나누어 환산된 거리가 가장 작은 작업장을 우선적으로 서비스 한다.


* MVED(Minimum Vehicle’s Empty Distance): AGV가 빈 상태로 이동하는 거리가 짧을수록 시스템의 효율이 높아지므로 이러한 거리를 줄일 수 있는 방법이다.


1. 현위치에서 이송할 짐이 있는가를 검사한다. 만일 이송할 짐이 있다면 우선적으로 이짐을 이송하게 된다. 그리고 이송할 짐이 없다면 최단 무효 이동 거리를 선택하여 우선순위를 다시 결정한다.


2. 현 위치에서 이송할 짐이 없다면, AGV가 위치한 작업장을 기준으로 일정 거리 안에 있는 작업장에서 이송할 짐이 있는지 검사한다. 여기서 만일 이송할 짐이 존재한다면 각각의 운반물들을 등록한다.


3. 등록된 운반물들 중에서 상태로 이동하는 무효 이동 거리가 얼마나 되는가를 계산한 후 이중 무효 이동 거리가 가장 짧은 대안을 AGV의 경로로 선택한다. 그리고 AGV는 이 경로를 따라 이동하면서 선적, 하역을 한다.


상기 절차에서 시스템은 시간의 변화에 따라 동적으로 변화하기 때문에 이에 적절히 대응하기 위해 차량의 하역이 이뤄질 때마다 상기 규칙이 적용되어야 하며, AGV는 상기와 같은 세 가지 단계를 통해 선정된 경로를 따라 이동하면서 이동 경로를 지속적으로 수정해야 한다.


본 연구에서의 AGV의 목적은 이동량을 줄여 물류 시간을 단축하여 생산량을 높이는 것이다. 이를 위하여 다음의 조건에 따라 AGV를 운영하도록 한다. 먼저 실시간 스케쥴링 알고리즘으로 Job x에 기술된 운반해야할 물건 정보를 가져온다. 그리고 각 물건을 최단 시간으로 가져오기 위한 VisitingSet을 만들게 된다. (상기 그림 참조) 


▲ 그림18



상기 그림에서와 같이 AGV에 Job이 할당되었을 때 s위치에서 e위치로 이동하기까지 최적의 순서를 실시간으로 찾아야 하는데, 이는 여행하는 세일즈맨 문제와 유사하다. 이 문제를 풀기 위하여 다음과 같은 절차를 고려한다.



(4) ‌입체적 물류 이동을 고려한 최적 웨이포인트 생성 알고리즘 개발

물류 시스템의 규모가 커질 경우, 운송 경로 및 방법의 다양성과 AGV의 위치를 미리 계획할 수 없기 때문에, AGV의 이동 경로를 미리 정의할 수 없게 된다. 이러한 이유로 AGV에 요청되는 작업에 따라 실시간으로 최적의 경로가 생성되어야 한다.


최단 경로를 찾기 위해서 그래프 탐색 기법인 A* 알고리즘을 사용한다. A*는 검색 공간의 특정 노드에 이웃한 노드들을 조사해 나가면서 시작 노드로부터 목표 노드로 이르는 가장 싼 비용의 경로를 찾는 알고리즘이다[4,5]. A* 알고리즘의 노드 목록으로는 ‘Open list’와 ‘Closed list’가 있다. Open list는 조사하지 않은 노드들이 담겨있으며, Closed list는 이미 조사한 노드들이 담겨져 있다. 초기 노드목록에는 탐색된 곳이 없으므로 Closed list는 비어있고 Open list는 처음 위치, 즉 시작 노드만 갖고 있다. 이후 탐색 과정에서 Open list에 있는 가장 낮은 비용의 노드를 가져와 다음 노드로 지정하고, 해당 노드는 Open list에서 Closed list로 이동된다. 


상기 노드가 목표 노드가 아니면 인접한 노드들을 정렬해서 아직 탐색되지 않은 곳이라면 Open list에 넣고, 이미 Open list에 있는 것일 때는 그 노드를 통하는 새로운 경로가 이전보다 비용이 싸면 그 노드의 정보를 업데이트한다. 상기 동작을 목표 노드에 도달할 때까지 반복적으로 수행하게 된다. A*에서 사용되는 비용 계산 수식은 다음과 같다.



여기서 f(n)은 전체 비용의 평가함수이고, g(n)은 시작 노드에서 n노드까지의 누적된 비용, h(n)은 n노드에서 목표 노드까지의 휴리스틱 값으로 현재 노드에서 목표 노드까지의 추정 비용을 나타내며, 일반적으로 목표 노드까지의 일직선 거리 값이 사용된다.


A* 알고리즘은 다음 그림과 같이 동작한다. (Pseudocode 참조)[6]


▲ 그림19. A* 알고리즘의 수도코드


AGV가 최단 경로를 따라 운행할 때의 소비시간은 다음과 같이 예측한다.


1. 출발과 도착지점에서의 가속도와 감속도를 고려

2. ‌곡률에 따라 구심가속도를 계산하고, 설정한 구심가속도보다 큰 구심가속도가 발생하지 않도록 곡선 이동 구간의 진입 속도를 고려

3. ‌각 노드별 거리와 속도를 고려하여 소비시간을 고려


실제로 상기와 같은 특징을 사용하여 AGV의 경로별 소비 시간을 예측하는데 가속도와 감속도, 구심가속도, 최고속도와 같은 AGV 파라미터들이 영향을 준다.


마. 물류처리 시뮬레이션 소프트웨어 개발

시뮬레이션 프로그램은 Visual Studio 2008 통합 개발환경에서 C++언어를 사용하여 작성되었으며, 개발 환경은 Pentium Quad CPU 1.8GHz, 4Gbyte RAM이며 운영체제는 Microsoft 사의 Windows7 이다. 프로그램은 크게 3개로 구성되며 시뮬레이션 데이터 취득 S/W, 맵 편집 S/W, 시뮬레이션 S/W로 나뉜다.


시뮬레이션 소프트웨어는 100대 이상의 다중로봇 시뮬레이션 가능하고 알고리즘의 최적경로 및 운송 시간, 물류 운송 효율 평가 레포트 출력 기능을 가진다. 다음 그림은 실제로 100대의 AGV를 시뮬레이션 하는 시뮬레이션 소프트웨어의 캡쳐 화면이다.


▲ 그림20


시뮬레이션을 수행하기 위해서는 다음의 가정을 따라야 한다:


1. ‌job의 선점은 허락되지 않는다. 그러므로, 앞서 시작된 작업은 다음 작업이 시작되기 전에 완료되어야 한다.

2. ‌각 job의 경로는 AGV가 출발하기 전에 미리 결정되어있다고 가정한다.

3. AGV는 job이 할당된 즉시 사용가능해야 한다.

4. ‌AGV 및 작업 공간에서 임의로 발생하는 장애는 고려하지 않는다.

5. ‌job은 특정한 평균을 가지는 지수분포의 형태로 임의로 발생한다고 가정한다.


시뮬레이션 수행도를 평가하기 위해서는 AGV에 할당되는 job의 발생 빈도, AGV의 유휴 시간, AGV의 운행 시간과 같은 정보들이 DB로부터 수집된다. 시뮬레이션 결과로서 job당 평균 흐름시간(Flow time), 평균 적재이동에서 빈 이동의 비율, 작업시간과 대기시간의 비율 등과 같은 성능척도가 표시된다.


▲ 그림21


바. 물류환경 스캐닝 로봇 제작

물류환경을 스캐닝 하기 위한 로봇은 상용 모바일 로봇 베이스를 구매하여 맵 획득에 필요한 각종 센서를 장착하여 구성하였다. 대표적인 센서로는 Fiber Optic gyro인 DSP-3000 센서와 레이저 스캐너인 SICK-LMS123 센서다. 이 두 센서는 로봇이 지나가는 주변의 맵을 정밀하게 획득하기 위한 필수불가결한 센서다. 로봇의 구성은 다음 그림과 같다.


로봇은 스택구조로 제일 하단에 모바일 베이스가 위치하며 중앙에 센서 및 전장이 배치된다. 제일 상판에는 노트북으로 로봇의 모든 센서를 통합하도록 하였으며, 실제 운행시에는 자율주행을 하지 않고 사람이 조이스틱으로 로봇을 따라가며 직접 조작하여 운행하도록 하였다.


아래 그림은 로봇의 상판 제작에 사용된 기구 도면이다. 상용 모바일 베이스를 사용하여 확장하는 형태로 설계하였다. 레이저 스캐너와 키넥트 센서는 전방을 바라보도록 배치하였고 카메라는 천정의 랜드마크를 바라볼 수 있도록 위를 바라보도록 배치하였다.


▲ 그림22


물류환경 스캐닝 로봇의 반복 위치 정밀도는 0.1%(100m 주행시 5.8cm) 로 우수한 편이며, 실제 실험으로 측정한 데이터는 다음과 같다.


▲ 그림23


▲ 그림24


▲ 표2. 시뮬레이션에 사용된 AGV 시스템의 사양


사. 맵 빌딩 소프트웨어 개발

맵 빌딩 소프트웨어는 맵 스캐닝 로봇이 물류환경을 스캐닝 한 데이터로부터 맵을 생성하는 소프트웨어다. 맵을 빌딩할 때, 먼저 로봇이 저장한 데이터를 불러와 화면에 표시한다. 


사용자는 화면에 표시된 벽 정보를 보고 벽의 모양과 AGV가 주행할 경로를 편집하게 된다. 벽은 AGV가 주행하면서 레이저 스캐너가 측정한 데이터와 매칭하여 AGV의 위치를 보정하는데 사용됨으로 되도록 정확하게 편집되어야 한다. 그리고 로봇의 주행 경로 또한, AGV가 주행하는 길이 되기 때문에, 장애물을 피해 그려야 한다. 다음은 맵을 생성하는 과정으로 크게 4단계로 구분된다.


(1) ‌사용자가 조이스틱으로 맵빌딩 로봇을 조종하여 맵 데이터를 획득

(2) ‌ICP(Iterate Closest Point) 알고리즘으로 틀어진 맵을 보정


▲ 그림25


(3) ‌벽 정보를 따라 외벽을 편집 (Laser Scanner의 위치인식에 사용)


▲ 그림26


(4) 벽 안에서 정류장과 경로를 편집


▲ 그림27


아. 물류운송로봇 구동부 모터 드라이버 개발


▲ 그림28


모터 드라이버는 6-step 운전 및 구형파 운전이 가능한 BLDC 모터를 기본적으로 구동하게 된다. 근래에 BLDC 모터는 DC모터의 수명 및 분진 문제를 해결하는 것으로 알려져 점차 산업용으로 응용 범위가 넓어지고 있다. 상기와 같은 이유로 AGV에도 채용이 확대되고 있는 추세로, 다수의 관련 업체에서 FOC(Field Oriented Control) 운전이 가능한 BLDC/PMSM 겸용 모터 드라이버 개발을 의뢰하고 있다.


BLDC 제어기를 설계할 때는 모터 및 제어기 단가를 낮추기 위해 홀센서만으로 정밀한 속도 예측이 가능한 속도 추정 기능이 포함되어야 하고 홀센서 신호의 위상각 보정 방법도 포함되어야 한다. 


본 과제에서 개발된 물류운송로봇 구동부 모터 드라이버는 BLDC/PMSM 겸용 모터 드라이버로 구동 전압이 10~50V이며 최대 전류는 30A로 500Kg 이상의 부하를 운반할 수 있는 수준의 제어기다.


▲ 그림29. 모터 드라이버


▲ 그림30. 모터 드라이버가 적용된 AGV 바퀴


차. 물류운송 모션 컨트롤러 개발

모션 컨트롤러는 AGV에 장착되는 각종 디지털 접점, 스위치, 센서 등의 입력을 받아들이고 릴레이, 경광등, 브레이크 등을 동작시키기 위해 여러 IO를 가지도록 요구된다. 또한 두 개의 AGV 구동 모터를 포함하여 여분의 축을 가지는 3축 동기 구동이 가능한 모션 컨트롤러를 요구하고 있다. 모션 컨트롤러는 3축 동기 구동이 가능하며, 디지털 출력으로 28접점, 디지털 입력으로 16접점을 연결할 수 있다. 또한 상위 PC나 PLC와 통신하기 위하여 RS-232, RS-485 통신을 지원한다.


▲ 그림31. 모션 컨트롤러


▲ 그림32. 모션 컨트롤러가 적용된 AGV


본 과제를 통해 제작된 모션 컨트롤러는 다음과 같으며, 실제로 제작된 모션 컨트롤러는 S사의 실외용 AGV에 적용되어 테스트 되었다.


제 3 절 기대효과 및 사업화 계획


1. 기대효과

본 과제를 통해 물류현장에서 필요로 하는 물류운송로봇 관련 요구사항을 파악하고 기 개발한 자율주행기술의 성능향상을 통하여 기존 기술의 완성도를 향상시키고 다중로봇의 관제 핵심기술을 확보함으로 중소형 물류운송 시스템 구축에 활용이 예상된다.


또한, 대형 병원, 실버타운, 공항, 전시장 등에서 청소, 경비, 순찰 등의 임무를 수행하는 타 용도의 로봇 개발에도 적용함으로써 기술적인 파급 효과가 클 것으로 판단된다. 


본 과제를 통해 중대형 물류기업용 저가형 관제기술을 확보함으로써, 생산에 필요한 투자비를 절감하고 생산성을 향상시켜 기업의 이익 증대에 기여할 수 있을 것이다. 


국내외 대형 물류 공정의 수작업 공정 개선으로 생산성향상을 통한 국제경쟁력 향상에 기여하고, 핵심 알고리즘의 국산화와 시장 요구를 반영한 기술개발로 수출 및 수입 대체효과도 기대해 볼 수 있다. 


2. 사업화 계획

초저가 제조용 구동 센싱모듈 및 로봇 시스템 기술개발(총 정부출연금 60억원 이내)이라는 과제명으로 산업통상자원부 산업핵심기술개발사업 신규과제 RFP 작업을 하고 있다. 


자율주행 로봇 및 맵빌딩 로봇을 기반으로 하는 시범보급사업을 추진하고, DC/BLDC/PMSM 모터 드라이버 및 모션 컨트롤러를 기반으로 하는 사업을 추진하고 있다. 


한국생산기술연구원 양광웅, 이설희 연구원

이 기사는 의 요약글입니다. <기사 상세내용보기>를 클릭하시면 전체 기사를 보실 수 있습니다.

기사 상세내용보기

마이크로칩 2018.09
디지키 08.09
이전글
2D 또는 3D 카메라? 3D 카메라 기술이 적합한 애플리케이션은?
다음글
음료 살균처리 용기를 위한 레이저 마킹기
교육원 법정의무교육
다이어리 홍보
댓글쓰기

0/500

등록
전체 댓글수 0

최신순 | 인기순

    댓글이 없습니다.