Publications

Detailed Information

물류센터 내에서의 다수 로봇 경로 최적화 : Multi-Agent Route Optimization for Robotic Mobile Fulfillment Systems

DC Field Value Language
dc.contributor.advisor이경식-
dc.contributor.author오세영-
dc.date.accessioned2020-05-07T03:35:49Z-
dc.date.available2020-05-07T03:35:49Z-
dc.date.issued2020-
dc.identifier.other000000160369-
dc.identifier.urihttp://dcollection.snu.ac.kr/common/orgView/000000160369ko_KR
dc.description학위논문(석사)--서울대학교 대학원 :공과대학 산업공학과,2020. 2. 이경식.-
dc.description.abstract본 논문은 물류센터 내 물류시스템 중 하나인 RMFS의 운영환경을 염두에 두고 충돌 없이 다수의 에이전트가 출발지에서 목적지까지 이동할 수 있는 이동계획을 찾는 문제를 다룬다. RMFS에서 사용되는 로봇은 물리적 크기를 가질 뿐만 아니라, 이동계획이 주어졌을 때 해당 계획을 부정확하게 수행할 수도 있다는 점에서 해당 특성들을 단순화하는 가정을 적용한 기존의 다수 에이전트 경로찾기문제(Multi-Agent Path Finding Problem)을 해결하기 위한 기법들의 직접적인 적용이 힘들다. 본 논문에서는 로봇의 물리적 크기와 로봇이 이동계획을 부정확하게 수행할 불확실성을 고려하여 꼭짓점에서 시간 간격을 둔 다수 에이전트 경로찾기문제를 제안하고, 이에 대한 정수최적화 모형을 제시한다. 제시된 정수최적화 모형은 결정변수와 제약식의 개수가 많기 때문에, 이를 해결하기 위하여 라그랑지안 완화기법에 기반을 둔 휴리스틱 알고리즘과, 충돌기반탐색(Conflict Based Search)의 변형, 그리고 라그랑지안 완화절차를 이용한 충돌 기반 분지한계 알고리즘을 제안한다. 실험을 통해 제안된 알고리즘이 에이전트의 수가 많거나, 부과한 시간 간격이 클 때도 제한된 시간 안에 좋은 품질의 가능해를 찾는데 효과적임을 확인하였다.-
dc.description.abstractThe 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.-
dc.description.tableofcontents제 1장 서론 1
1.1 문제 배경 1
1.2 선행 연구 3
1.2.1 다수 에이전트 경로찾기문제 3
1.2.2 다수 로봇 경로 계획 4
1.3 연구 동기 및 공헌 5
1.4 논문 구성 7
제 2장 문제 정의 및 수리 모형 8
2.1 문제 정의 8
2.2 수리 모형 10
2.2.1 시간확장그래프 10
2.2.2 시간확장그래프에서의 최단경로문제 모형 11
2.2.3 MAPFPTS의 수리모형 14
2.2.4 경로 변수를 이용한 수리모형. 16
2.3 단일 로봇의 경우 19
제 3장 최적 해법 및 휴리스틱 21
3.1 라그랑지안 완화절차 21
3.1.1 라그랑지안 완화기법. 21
3.1.2 서브그래디언트 알고리즘 25
3.1.3 수리모형 (P)의 유효한 부등식 26
3.1.4 라그랑지안 완화 기반 휴리스틱 27
3.1.5 라그랑지안 완화절차 29
3.2 충돌기반탐색 31
3.3 충돌 기반 분지한계법 34
제 4장 실험 결과 38
4.1 실험 인스턴스 39
4.2 성능 비교 41
4.2.1 휴리스틱별 라그랑지안 완화절차의 성능 비교 41
4.2.2 에이전트의 수에 따른 알고리즘별 성능 비교 43
4.2.3 시간 간격에 따른 알고리즘들의 성능 비교 45
4.2.4 그래프의 크기에 따른 알고리즘들의 성능 비교 47
제 5장 결론 49
참고문헌 51
-
dc.language.isokor-
dc.publisher서울대학교 대학원-
dc.subject.ddc670.42-
dc.title물류센터 내에서의 다수 로봇 경로 최적화-
dc.title.alternativeMulti-Agent Route Optimization for Robotic Mobile Fulfillment Systems-
dc.typeThesis-
dc.typeDissertation-
dc.contributor.AlternativeAuthorOh, Seyoung-
dc.contributor.department공과대학 산업공학과-
dc.description.degreeMaster-
dc.date.awarded2020-02-
dc.identifier.uciI804:11032-000000160369-
dc.identifier.holdings000000000042▲000000000044▲000000160369▲-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share