A Novel Integrated Path Planning Algorithm for Warehouse AGVs

WEN Tao; YANG Daichuan; LIU Weifeng; WEN Chenglin; CAI Baigen

doi:10.1049/cje.2021.02.002

Volume 30 Issue 2

Apr. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(2): 331-338

WEN Tao, YANG Daichuan, LIU Weifeng, et al., “A Novel Integrated Path Planning Algorithm for Warehouse AGVs,” Chinese Journal of Electronics, vol. 30, no. 2, pp. 331-338, 2021, doi: 10.1049/cje.2021.02.002

Citation:

WEN Tao, YANG Daichuan, LIU Weifeng, et al., “A Novel Integrated Path Planning Algorithm for Warehouse AGVs,” Chinese Journal of Electronics, vol. 30, no. 2, pp. 331-338, 2021, doi: 10.1049/cje.2021.02.002

Citation:

PDF( 1637 KB)

A Novel Integrated Path Planning Algorithm for Warehouse AGVs

doi: 10.1049/cje.2021.02.002

1.
School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China
2.
School of Automation, Hangzhou Dianzi University, Hangzhou 310018, China

Funds:

the National Key Research and Development Program 2020YFB1313301

the National Natural Science Foundation of China 61806064

the National Natural Science Foundation of China 61751304

the National Natural Science Foundation of China 61933013

More Information

Corresponding author: WEN Tao (corresponding author) received the B.Eng degree in computer science from Hangzhou Dianzi University, Hangzhou, China, MSc. degree from the University of Bristol, Bristol, UK, and Ph.D degree from the University of Birmingham, Birmingham, UK, in 2011, 2013 and 2018, respectively. Now, he works at Beijing Jiaotong University. His research interests include the radio-based train control systems optimization, path planning, digital filter design and its application in transportation systems
Received Date: 2019-12-13
Accepted Date: 2020-07-09
Publish Date: 2021-03-01

Abstract

Abstract

We propose an integrated path planning method for multiple automated guided vehicles performing logistics delivery within a real-world warehouse environment considering obstacles. By applying it on each vehicle, this proposed method enables the vehicle the vehicles have the capabilities for autonomous path planning. The path planning consists of three parts, K-means algorithm based task points clustering, genetic algorithm based task points ordering, and the probabilistic road map based best path search. Vehicle conflict resolution is depending on implementing the probabilistic road map construction considering the realistic map with obstacles. The simulations result validate that the clustering and ordering are necessary for the path planning, both the path planning time and the Automated guided vehicles (AGVs) running time can be dramatically reduced.
- AGVs,
- Logistics distribution,
- Probabilistic road map,
- Path planning

FullText(HTML)

References(40)

References

[1]	Gongde Guo, Hui Wang, David Bell, Yaxin Bi, and Kieran Greer. Knn model-based approach in classification. In Robert Meersman, Zahir Tari, and Douglas C. Schmidt, editors, On The Move to Meaningful Internet Systems 2003: CoopIS, DOA, and ODBASE, pages 986–996, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
[2]	J.R. Quinlan. Induction of decision trees. Mach. Learn., Vol. 1, No. 1, pp. 81-106, March 1986.
[3]	Peter Brucker. Scheduling algorithms. 10.1007/978-3-662-04550-3.
[4]	Taixiong Zheng and Jiongqiu Li. Multi-robot task allocation and scheduling based on fish swarm algorithm. In 2010 8th World Congress on Intelligent Control and Automation, pp. 6681-6685, July 2010.
[5]	Kap Hwan Kim and Kyung Chan Moon. Berth scheduling by simulated annealing. Transportation Research Part B, Vol. 37, No. 6, pp. 0-560. http://www.sciencedirect.com/science/article/pii/S0191261502000279
[6]	H. Zhang, H. Luo, Z. Wang, Y. Liu, and Y. Liu. Multi-robot cooperative task allocation with definite path-conflict-free handling. IEEE Access, 7: 138495–138511, 2019. doi: 10.1109/ACCESS.2019.2942966
[7]	N. Smolic-Rocak, S. Bogdan, Z. Kovacic, and T. Petrovic. Time windows based dynamic routing in multi-agv systems. IEEE Transactions on Automation Science and Engineering, Vol. 7, No. 1, pp. 151-155, Jan 2010. doi: 10.1109/TASE.2009.2016350
[8]	W. Zhang, Y. Peng, W. Wei, and L. Kou. Real-time conflict-free task assignment and path planning of multi-agv system in intelligent warehousing. In 2018 37th Chinese Control Conference (CCC), pp. 5311-5316, July 2018.
[9]	W. Seo, S. Ok, J. Ahn, S. Kang, and B. Moon. An efficient hardware architecture of the a-star algorithm for the shortest path search engine. In 2009 Fifth International Joint Conference on INC, IMS and IDC, pp. 1499-1502, Aug 2009.
[10]	L. Xin, H. Xiangyuan, Y. Ziqi, Q. Xiaoning, and D. Yingkui. The algebraic algorithm for path planning problem of agv in flexible manufacturing system. In 2018 37th Chinese Control Conference (CCC), pp. 2396-2399, July 2018.
[11]	T. Nishi and R. Maeno. Petri net decomposition approach to optimization of route planning problems for agv systems. IEEE Transactions on Automation Science and Engineering, Vol. 7, No. 3, pp. 523-537, July 2010.
[12]	Se Jin Lee, Dong Woo Cho, Wan Kyun Chung, Jong Hwan Lim, and Chul Ung Kang. Feature based map building using sparse sonar data. In 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1648-1652, Aug 2005.
[13]	W. Yuan, Z. Cao, M. Tan, and J. Liu. Topological mapping and navigation based on visual sensor network. In 2014 IEEE International Conference on Mechatronics and Automation, pp. 1686-1690, Aug 2014.
[14]	X. Wang, Y. Jin, and Zhaohong Ding. A path planning algorithm of raster maps based on artificial potential field. In 2015 Chinese Automation Congress (CAC), pp. 627-632, Nov 2015.
[15]	Daichuan Yang and Chenglin Wen. Multiple targets robot path planning based on ant colony and improved probabilistic road map. Journal of Hangzhou Dianzi University, 2017. http://en.cnki.com.cn/Article_en/CJFDTOTAL-HXDY201703013.htm
[16]	Kai-bo Xu, Hai-yan Lu, Yang Huang, and Shi-juan Hu. Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment. Chinese Journal of Electronics, Vol. 47, No. 10, pp. 2166-2176, 2019. http://en.cnki.com.cn/Article_en/CJFDTotal-DZXU201910019.htm
[17]	L.E. Kavraki, P. Svestka, J. Latombe, and M.H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, Vol. 12, No. 4, pp. 566-580, Aug 1996.
[18]	Zheng Sun, D. Hsu, Tingting Jiang, H. Kurniawati, and J. H. Reif. Narrow passage sampling for probabilistic roadmap planning. IEEE Transactions on Robotics, Vol. 21, No. 6, pp. 1105-1115, 2005. doi: 10.1109/TRO.2005.853485
[19]	Korbinian Nottensteiner, Mikel Sagardia, Andreas Stemmer, and Christoph Hermann Borst. Narrow passage sampling in the observation of robotic assembly tasks. In IEEE International Conference on Robotics and Automation, pp. 130-137, 2016.
[20]	Changan, CHANG, Jingang, and Chunyang. Path planning for mobile robot based on an improved probabilistic roadmap method. Chinese Journal of Electronics, Vol. 18, No. 3, pp. 395-399, 2009.
[21]	Mitul Saha, Jean Claude Latombe, Yu Chi Chang, and Friedrich Prinz. Finding narrow passages with probabilistic roadmaps: The small-step retraction method. Autonomous Robots, Vol. 19, No. 3, pp. 301-319, 2005. doi: 10.1007/s10514-005-4748-1
[22]	Leif Peterson. K-nearest neighbor. Scholarpedia, Vol. 4, No. 2, 2009.
[23]	J. A. Hartigan and M. A. Wong. Algorithm as 136: A k-means clustering algorithm. Journal of the Royal Statistical Society, Vol. 28, No. 1, pp. 100-108, 1979.
[24]	Partha Pratim Kundu and Sushmita Mitra. Multi-objective optimization of shared nearest neighbor similarity for feature selection. Applied Soft Computing, Vol. 37, No. C, pp. 751-762, 2015. http://www.sciencedirect.com/science/article/pii/S1568494615005505
[25]	W. Chiu, G. G. Yen, and T. Juan. Minimum manhattan distance approach to multiple criteria decision making in multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, Vol. 20, No. 6, pp. 972-985, Dec 2016.
[26]	Tangkai Zhang, Jie Luo, and Longjun Li. Path planning method based on k-means and svm combination grid partition. Microcomputer & Its Applications, 2016. http://search.cnki.net/down/default.aspx?filename=WXJY201621006&dbcode=CJFD&year=2016&dflag=pdfdown
[27]	Yong Wang, Heng Zhou, and Ying Wang. Mobile robot dynamic path planning based on improved genetic algorithm. In Green Energy and Sustainable Development Ⅰ: Proceedings of the International Conference on Green Energy and Sustainable Development, pp. 020046, 2010.
[28]	L.E. Kavraki, M.N. Kolountzakis, and J. Latombe. Analysis of probabilistic roadmaps for path planning. IEEE Transactions on Robotics and Automation, Vol. 14, No. 1, pp. 166-171, Feb 1998.
[29]	Richard E. Korf. Iterative-deepening-a: An optimal admissible tree search. In International Joint Conference on Artificial Intelligence*, pp. 1034-1036, 2010.
[30]	Sven Koenig and Maxim Likhachev. Dlite. In Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada*, pp. 476-483, 2002.
[31]	V. Lumelsky and A. Stepanov. Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Transactions on Automatic Control, Vol. 31, No. 11, pp. 1058-1063, November 1986.
[32]	Jingang Cao. Robot global path planning based on an improved ant colony algorithm. Journal of Computer Communications, Vol. 04, No. 2, pp. 11-19, 2016. doi: 10.4236/jcc.2016.42002
[33]	Jianhua Liu, Jianguo Yang, Huaping Liu, Xingjun Tian, and Meng Gao. An improved ant colony algorithm for robot path planning. Soft Computing, Vol. 1, No. 11, pp. 1-11, 2016.
[34]	Qianjie Lu, Zhiping Chen, Linjia Zhang, Haonan Wang, and Chunlu Liu. Multi-sources and multi-destinations route search in community bus service based on ant colony algorithm. Journal of Hangzhou Dianzi University, 2016. http://en.cnki.com.cn/Article_en/CJFDTOTAL-HXDY201603017.htm
[35]	T. Wen, C. Constantinou, L. Chen, Z. Li, and C. Roberts. A practical access point deployment optimization strategy in communication-based train control systems. IEEE Transactions on Intelligent Transportation Systems, Vol. 20, No. 8, pp. 3156-3167, Aug 2019.
[36]	T. Wen, Q. Ge, X. Lyu, L. Chen, C. Constantinou, C. Roberts, and. Cai. A cost-effective wireless network migration planning method supporting high-security enabled railway data communication systems. Journal of the Franklin Institute, 2019. DOI: 10.1016/j.jfranklin.2019.01.037.
[37]	T. Wen, C. Wen, C. Roberts, and B. Cai. Distributed filtering for a class of discrete-time systems over wireless sensor networks. Journal of the Franklin Institute, Vol. 35, No. 5, pp. 3038-3055, 2020. http://www.sciencedirect.com/science/article/pii/S0016003220300892
[38]	G. Xie, L. Sun, T. Wen, X. Hei, and F. Qian. Adaptive transition probability matrix-based parallel imm algorithm. IEEE Transactions on Systems, Man, and Cybernetics: Systems, pp. 1-10, 2019. http://ieeexplore.ieee.org/document/8747402
[39]	Wei-dong Chen and Qi-guang Zhu. Mobile robot path planning based on fuzzy algorithms. Chinese Journal of Electronics, Vol. 39, No. 4, pp. 971-974. http://en.cnki.com.cn/Article_en/CJFDTOTAL-DZXU201104042.htm
[40]	Chang-an Liu, Xiao-hu Yan, Chun-yang Liu, and hua Wu. Dynamic path planning for mobile robot based on improved ant colony optimization algorithm. Chinese Journal of Electronics, Vol. 39, No. 5, pp. 238-242, 2011. http://www.researchgate.net/publication/290672960_dynamic_path_planning_for_mobile_robot_based_on_improved_ant_colony_optimization_algorithm