Multi-Stage Multi-AGV Path Planning with Walk under Shelves for Robotic Mobile Fulfillment Systems

doi:10.16182/j.issn1004731x.joss.21-1060

Abstract

Abstract:

Aiming at the problem of increasing travel time due to turning and obstacle avoidance in robotic mobile fulfillment systems(RMFS) with large-scale multi-AGV path planning, a path planning model with the shortest task completion time is established. A path planning model considering no-load AGV that can pass through the shelf is proposed, and the model is solved by an improving A* algorithm. The AGV operation stage is divided, an turning penalty value is introduced into the A* algorithm to reduce the turning times, and the obstacle avoidance priority with the obstacle avoidance waiting time is set. The simulation results show that the new path planning method considering turning and obstacle avoidance can reduce task completion time and travel path length, and improve order picking efficiency of the warehouse of a distribution center.

Key words: RMFS (robotic mobile fulfillment systems), multi-AGVs path planning, walk under shelves, turning time, obstacle avoidance strategy, A* algorithm

CLC Number:

TP391.9

Teng Li, Peipei Ding, Jinfang Liu. Multi-Stage Multi-AGV Path Planning with Walk under Shelves for Robotic Mobile Fulfillment Systems[J]. Journal of System Simulation, 2022, 34(7): 1512-1523.

Figures/Tables 20

Fig. 1

Fig. 2

Fig. 3

Table 1

Symbol explanation in model

符号	含义	符号	含义
$T p$	AGV完成任务的时间	$d$	AGV一次加减速行走距离
$i$	第 $i$ 个任务， $i ∈ 1, M$	$q Z i j$	第 $j$ 个AGV完成第 $i$ 个任务转弯总次数
$j$	第 $j$ 个AGV， $j ∈ 1, N$	$q K i j$	第 $j$ 个AGV完成第 $i$ 个任务避障等待总次数
$r j$	第 $j$ 个AGV完成任务的数量	$S$	值为1时表示前往拣选台阶段，值为2时表示放回货架阶段
$v$	AGV匀速运行速度	$u$	系统中第 $u$ 条路段， $u ∈ [1, G i j]$
$t J$	拣选人员拣货时间	$(y l, x l)$	编号为 $l$ 的栅格位置位置，栅格总数为 $L$
$t l$	AGV举起货架花费的时间	$H K a b i j$	第 $j$ 个AGV执行第 $i$ 个任务时，空载阶段行走的路段
$t d$	AGV放下货架花费的时间	$H Z a b i j$	第 $j$ 个AGV执行第 $i$ 个任务时，重载阶段行走的路段
$T s t k i j$	第 $j$ 个AGV执行第 $i$ 个任务过程中第 $k$ 次避障等待开始时间点	$U 1$	除拣选台外，相邻栅格中心构成的路段集合
$T e n k i j$	第 $j$ 个AGV执行第 $i$ 个任务过程中第 $k$ 次避障等待结束时间点	$U 2$	除拣选台和货架外，相邻栅格中心构成的路段集合
$t w k i j$	第 $j$ 个AGV执行第 $i$ 个任务过程中第 $k$ 次避障等待时间	$G i j$	第 $j$ 个AGV执行第 $i$ 个任务时行走路段总数
$t p 1$	AGV加减速消耗时间	$r ⇀ a b i j$	第 $j$ 个AGV执行第 $i$ 个任务时，行走的路段 $H a b$ 构成的向量
$t p$	AGV转弯过程消耗时间	$R a b i j$	决策变量，表示是否经过路段 $H a b$ ，1表示经过，0表示不经过
$h$	路段长度	$H a b$	编号分别为a,b的栅格中心构成的路段，且栅格a,b相邻

Table 1

Fig. 4

Fig. 5

Fig. 6

Table 2

Table 3

Fig. 7

Fig. 8

Table 4

Table 5

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Table 6

Fig. 14

References 17

1	ENRIGHT J, WURMAN P. Optimization and Coordinated Autonomy in Mobile Fulfillment Systems[C]// Automated Action Planning for Autonomous Mobile Robots. the 2011 AAAI Workshop, San Francisco, California, USA, August 7, 2011. AAAIPress, 2011: 33-38.
2	徐翔斌, 马中强. 基于移动机器人的拣货系统研究进展[J]. 自动化学报, 2022, 48(1): 1-20.
	Xu Xiangbin, Ma Zhongqiang. Robotic Mobile Fulfillment Systems: State-of-the-art and Prospects[J]. Acta Automatica Sinica. 2022, 48(1): 1-20.
3	Da Costa Barros Ítalo Renan, Do Nascimento Tiago Pereira. Robotic Mobile Fulfillment Systems: A Survey on Recent Developments and Research Opportunities[J]. Robotics and Autonomous Systems (S0921-8890), 2021,137: 1-5.
4	Vivaldini K, Rocha L, Martarelli N, et al. Integrated Tasks Assignment and Routing for the Estimation of the Optimal Number of AGVS[J]. International Journal of Advanced Manufacturing Technology (S0268-3768), 2016, 82(4): 719-736.
5	Ma H, H-nig W, Cohen L, et al. Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems[J]. IEEE Intelligent Systems (S1541-1672), 2017, 32(6): 6-12.
6	Kamoshida R, Kazama Y. Acquisition of Automated Guided Vehicle Route Planning Policy Using Deep Reinforcement Learning[C]// 6th IEEE International Conference on Advanced Logistics and Transport. Washington, D C, USA: IEEE, 2017: 1-6
7	邓向阳, 张立民, 方伟, 等. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
	Deng Xiangyang, Zhang Limin, Fang Wei, et al. Robot:Path Planning Based on Bidirectional Aggregation Ant Colony Optimization[J]. Journal of System Simulation,2022, 34(5): 1101-1108.
8	王梓强, 胡晓光, 李晓筱, 等. 移动机器人全局路径规划算法综述[J]. 计算机科学[J]. 2021, 48(10): 19-29.
	Wang Ziqiang, Hu Xiaoguang, Li Xiaoxiao, et al. Overview of Global Path Planning Algorithms for Mobile Robots[J]. Computer Science, 2021, 48(10): 19-29.
9	Lee C K M, Lin Bingbing, Ng K K H, et al. Smart Robotic Mobile Fulfillment System with Dynamic Conflict-free Strategies Considering Cyber-physical Integration[J]. Advanced Engineering Informatics (S1474-0346), 2019, 42(13): 1-12.
10	Guo Lixiao, Yang Qiang, Yan Wenjun. Intelligent Path Planning for Automated Guided Vehicles System Based on Topological Map[C]// 2012 IEEE Conference on Control Systems &Industrial Informatics. Washington, D C, USA: IEEE, 2012: 69-74.
11	李荣华. 面向智能仓储的多机器人任务分配与路径规划研究[D]. 哈尔滨: 哈尔滨工业大学, 2017.
	LI Ronghua. Research on Task Assignment and Path Planning for Multi-robots for Intelligent Warehouse[D]. Harbin: Harbin Institute of Technology, 2017.
12	Merschformann M, Lamballais T, Koster M D, et al. Decision Rules for Robotic Mobile Fulfillment Systems[J]. Operations Research Perspectives (S2214-7160),2019, 6: 1-15.
13	张丹露, 孙小勇, 傅顺, 等. 智能仓库中的多机器人协同路径规划方法[J].计算机集成制造系统, 2018, 24(2): 410-418.
	Zhang Danlu, Sun Xiaoyong, Fu Shun, et al. Cooperative Path Planning in Multi-robots for Intelligent Warehouse[J]. Computer Integrated Manufacturing Systems, 2018, 24(2): 410-418.
14	Roy D, NIGAM S, DE KOSTER R, et al. Robot-storage Zone Assignment Strategies in Mobile Fulfillment Systems[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2019, 122: 119-142.
15	张新艳, 邹亚圣. 基于改进A*算法的自动导引车无碰撞路径规划[J]. 系统工程理论与实践, 2021, 41(1): 240-246.
	Zhang Xinyan, Zou Yasheng. Collision-free Path Planning for Automated Guided Vehicles Based on Improved A* Algorithm[J]. Systems Engineering-Theory & Practice, 2021, 41(1): 240-246.
16	Dou Jiajia, Chen C hunlin, Yang Pei. Genetic Scheduling and Reinforcement Learning in Multirobot Systems for Intelligent Warehouses[M/OL]// Mathematical Problems in Engineering, 2015: 1-10 [2021-8-10]..
17	Yuan Ruiping, Dong Tingting, Li Juntao. Research on the Collision-free Path Planning of Multi-AGVs System Based on Improved A*algorithm[J]. American Journal of Operations Research (S2160-8849), 2016, 6(6): 442-449.

AGV路径规划	栅格号	位置
1	1 084	(22，34)
2	2 413	(49，13)
3	1 845	(37，45)
4	788	(16，38)
5	2 129	(43，29)

任务编号	栅格序号	位置	任务编号	栅格序号	位置
1	866	(18，16)	16	121	(3，21)
2	1 315	(27，15)	17	72	(2，22)
3	383	(8，33)	18	1 877	(38，27)
4	447	(9，47)	19	1 312	(27，12)
5	1 860	(38， 10)	20	425	(9，25)
6	821	(17，21)	21	137	(3，37)
7	746	(15，46)	22	1 858	(38，8)
8	2 366	(48，16)	23	285	(6，35)
9	1 179	(24，29)	24	1 618	(33，18)
10	1 634	(33，34)	25	1 270	(26，20)
11	696	(14，46)	26	1 885	(38，35)
12	1 789	(36，39)	27	656	(14，6)
13	2 306	(47，6)	28	1 497	(30，47)
14	2 338	(47，38)	29	883	(33，18)
15	1 487	(30，37)	30	268	(6，18)

序号	转弯次数/次	避障时间/s	任务分配结果	目标拣选台
1	26	52	1,7,13,18,22,25	1,1,2,2,2,1
2	26	62	2,8,12,17,23,29	2,2,2,1,1,1
3	27	56	4,10,15,19,24,26	1,2,2,2,2,2
4	30	96	1,9,14,20,27,30	1,1,2,1,1,1
5	29	58	5,6,11,16,21,28	2,1,1,1,1,2

避障及转弯处理			优化结果		时间统计
避障处理	转弯处理	可否穿行货架	任务完成时间	AGV行走总时间	转弯时间	避障时间	转弯避障总时间
任务序号优先级	无	否	782	3 591	322	444	766
任务序号优先级	无	是	722	3 284	246	313	559
任务序号优先级	有	否	707	3 360	312	269	581
任务序号优先级	有	是	684	3 203	262	241	503
避障时间优先级	有	否	701	3 349	310	249	559
避障时间优先级	有	是	662	3 211	276	234	510

AGV号	栅格序号	位置	AGV号	栅格序号	位置
1	2474	(59.24)	6	2477	(59.27)
2	2475	(59.25)	7	2471	(59.21)
3	2473	(59.23)	8	2478	(59.28)
4	2476	(59.26)	9	2470	(59.20)
5	2472	(59.22)	10	2479	(59.29)