물류센터 내에서의 다수 로봇 경로 최적화

Abstract

본 논문은 물류센터 내 물류시스템 중 하나인 RMFS의 운영환경을 염두에 두고 충돌 없이 다수의 에이전트가 출발지에서 목적지까지 이동할 수 있는 이동계획을 찾는 문제를 다룬다. RMFS에서 사용되는 로봇은 물리적 크기를 가질 뿐만 아니라, 이동계획이 주어졌을 때 해당 계획을 부정확하게 수행할 수도 있다는 점에서 해당 특성들을 단순화하는 가정을 적용한 기존의 다수 에이전트 경로찾기문제(Multi-Agent Path Finding Problem)을 해결하기 위한 기법들의 직접적인 적용이 힘들다. 본 논문에서는 로봇의 물리적 크기와 로봇이 이동계획을 부정확하게 수행할 불확실성을 고려하여 꼭짓점에서 시간 간격을 둔 다수 에이전트 경로찾기문제를 제안하고, 이에 대한 정수최적화 모형을 제시한다. 제시된 정수최적화 모형은 결정변수와 제약식의 개수가 많기 때문에, 이를 해결하기 위하여 라그랑지안 완화기법에 기반을 둔 휴리스틱 알고리즘과, 충돌기반탐색(Conflict Based Search)의 변형, 그리고 라그랑지안 완화절차를 이용한 충돌 기반 분지한계 알고리즘을 제안한다. 실험을 통해 제안된 알고리즘이 에이전트의 수가 많거나, 부과한 시간 간격이 클 때도 제한된 시간 안에 좋은 품질의 가능해를 찾는데 효과적임을 확인하였다.

The Robotic Mobile Fulfillment System (RMFS) is a robotized material handling system where multiple robots transport movable shelves to and from stocking points and workstations in a warehouse. In this paper, we deal with the problem of finding collision-free routes for multiple robots to move from their starting points to destinations in a RMFS, which is defined as a generalization of the multi-agent path finding problem (MAPFP). In RMFSs, collisions among moving robots may occur due to the physical volume of robots and the inexact execution of planned routes by robots in terms of the planned timing of passing through points on the routes, which makes it difficult to directly apply the existing algorithms for MAPFP that assume the exact execution of planned routes by agents with no physical volume. Therefore, we defined the problem as a multi-agent path finding problem with the prespecified time spacing at points to address the possible sources of collisions among robots, and propose an integer optimization model for the problem. Since the proposed integer optimization model has a large number of decision variables and constraints, we propose heuristic and exact algorithms based on the Lagrangian relaxation technique and the conflict based search. Experimental results show that the proposed algorithms are effective in finding good quality solutions within a limited time even when the number of robots or the time spacing are large.