文章快速检索 高级检索

1. 南开大学 机器人与信息自动化研究所, 天津 300071;
2. 美国纽约州立大学布法罗分校

Intelligent scheduling and path planning of warehouse mobile robots
SHEN Bowen1,2 , YU Ningbo1 , LIU Jingtai1
1. Institute of Robotics and Automatic Information Systems, Nankai University, Tianjin 300071 ;
2. Department of Computer Science and Engineering, University at Buffalo
Abstract: The rapid increase of E-commerce brings new challenges for warehouse logistics. The shipments are characterized as big variety, small volume, large number of small batches and short cycle, and thus are difficult to handle. Emerging logistic technology based on mobile robots is the promising solution. In this work, firstly a warehouse model with flexible re-configurability was set up and a set of rules to govern warehouse logistics and robot movement were defined. After that, the logistic task was decomposed and a robot scheduling method taking into account the Manhattan path cost and the waiting time cost was proposed. Next, the A* algorithm was adapted for robot path planning under the special constraint rules. Finally, timing information was included for consideration and a time-space map was established to carry out three-dimensional path planning. The intelligent scheduling and path planning methods were validated by simulation experiments. The path planning methods and number of robots were compared in relation to total time cost, total mileage and number of conflicts.
Key words: warehouse logistics     mobile robots     intelligent scheduling     path planning     A* algorithm

1 仓储空间结构和物流任务分析

 图 1 仓储空间全局平面示意图 Fig. 1 Warehouse floor plan overview

 图 2 任务形式 Fig. 2 Task form

 图 3 一个任务的流程图 Fig. 3 Task flow chart
2 机器人的智能调度和路径规划 2.1 机器人的智能调度算法

 ${g_n} = w \times {t_{{n_1}}} + {t_{{n_2}}}$ (1)

 ${g_n} = {\rm{abs}}\left( {{\rm{cur}}.x - n.x} \right) + {\rm{abs}}\left( {{\rm{cur}}.y - n.y} \right)$ (2)

2.2 特殊规则约束下基于A*算法的路径规划

A*算法的基本流程是从起始点开始，根据估计代价选择性地扩展节点，直到将目标点扩展进来。关键是选择合适的评价函数：

 $f\left( n \right) = g\left( n \right) + h\left( n \right)$ (3)

 图 4 A*算法路径规划的节点拓展 Fig. 4 Node expansion of A* path planning

 图 5 从货架和道路扩展到道路 Fig. 5 Expansion from shelf or road to road

 图 6 扩展目标点 Fig. 6 Expand destination

 图 7 估价函数h(n) Fig. 7 Cost function h(n)
2.3 加入时序A*算法的路径规划

2.4 碰撞预防

3 仿真实验

3.1 任务生成和实验设定

1) 采用随机算法产生任务。货架与机器人的初始位置也随机产生。任务调用的货架编号和入货口/出货口符合随机高斯分布。

2) 任务数量设为1 000,随机产生10组任务。移动机器人的数量分别设定为10、20、30、40和50共5种情况。每种情况下，利用智能调度算法和2种路径规划算法完成给定的10组任务。总共进行了100次实验。

3.2 实验结果

 p 运行总里程 耗费时间 抢路冲突 机器人数量 ＜10-4 ＜10-4 ＜10-4 路径规划算法 0.969 0 0.919 9 0.000 3

 图 8 完成设定任务运行总里程随机器人数量的增加而减少 Fig. 8 The total pathway decreases as robot number increases

 图 9 完成设定任务耗费时间随机器人数量的增加而降低 Fig. 9 Running time decreases as robot number increases
 图 10 运行中发生的抢路冲突随机器人数量的增加而增加 Fig. 10 Conflicts increases as robot number increases

4 结束语

 [1] 邹爽心. 仓储机器人的应用现状与发展战略探讨[J]. 物流工程与管理,2013, 35 (6) : 171 –172. ZOU Shuangxin. The present and future of warehouse robot[J]. Logistics Engineering and Management,2013, 35 (6) : 171 –172. [2] 曹宝文. 自动化仓库中多AGV系统路径规划研究[D]. 天津: 南开大学, 2012: 21-23. CAO Baowen. Path planning of multi-AGV system in automatic warehouse[D]. Tianjin: Nankai University, 2012: 21-23. [3] 张建英, 赵志萍, 刘暾. 基于人工势场法的机器人路径规划[J]. 哈尔滨工业大学学报,2006, 38 (8) : 1306 –1309. ZHANG Jianying, ZHAO Zhiping, LIU Tun. A path planning method for mobile robot based on artificial potential field[J]. Journal of Harbin Institute of Technology,2006, 38 (8) : 1306 –1309. [4] 于振中, 闫继宏, 赵杰, 等. 改进人工势场法的移动机器人路径规划[J]. 哈尔滨工业大学学报,2011, 43 (1) : 50 –55. YU Zhenzhong, YAN Jihong, ZHAO Jie, et al. Mobile robot path planning based on improved artificial potential field method[J]. Journal of Harbin Institute of Technology,2011, 43 (1) : 50 –55. [5] 黄磊. 基于神经网络的移动机器人路径规划研究[D]. 武汉: 武汉理工大学, 2008: 17-27. HUANG Lei. Research on path planning of mobile robots based on neural networks[D]. Wuhan: Wuhan University of Technology, 2008: 17-27. [6] 陈华志, 谢存禧, 曾德怀. 基于神经网络的移动机器人路径规划算法的仿真[J]. 华南理工大学学报:自然科学版,2003, 31 (6) : 56 –59. CHEN Huazhi, XIE Cunxi, ZENG Dehuai. Simulation of path planning algorithm of mobile robots based on neural networks[J]. Journal of South China University of Technology: Natural Science,2003, 31 (6) : 56 –59. [7] 苏治宝, 陆际联. 用模糊逻辑法对移动机器人进行路径规划的研究[J]. 北京理工大学学报,2003, 23 (3) : 290 –293. SU Zhibao, LU Jilian. A study on the path planning of mobile robot with the fuzzy logic method[J]. Transactions of Beijing Institute of Technology,2003, 23 (3) : 290 –293. [8] 卓睿, 陈宗海, 陈春林. 基于强化学习和模糊逻辑的移动机器人导航[J]. 计算机仿真,2005, 22 (8) : 157 –162. ZHUO Rui, CHEN Zonghai, CHEN Chunlin. Navigation for mobile robots using reinforcement learning and fuzzy logic[J]. Computer Simulation,2005, 22 (8) : 157 –162. [9] HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics,1968, 4 (2) : 100 –107. [10] 王勇. 智能仓库系统多移动机器人路劲规划研究[D]. 哈尔滨: 哈尔滨工业大学, 2010: 19-30. WANG Yong. Research about path planning of multiple mobile robots in intelligent warehouse system[D]. Harbin: Harbin Institute of Technology, 2010: 19-30.
DOI: 10.3969/j.issn.1673-4785.201312048

0

#### 文章信息

SHEN Bowen, YU Ningbo, LIU Jingtai

Intelligent scheduling and path planning of warehouse mobile robots

CAAI Transactions on Intelligent Systems, 2014, 9(6): 659-664
http://dx.doi.org/10.3969/j.issn.1673-4785.201312048