Method of Automatic Branch-pipe Routing Based LTL-PRM Algorithm

doi:10.3901/JME.2018.15.160

Abstract

Abstract: A local twice learning probabilistic roadmap method(LTL-PRM) for the problem of non-orthogonal branch pipe automatic layout is proposed. Firstly, a minimum Steiner tree between endpoints is calculated by the backtracking algorithm. After the optimization of Steiner points, the positions of branch points of the branch pipe are acquired. Then, based on the basic PRM, a roadmap is constructed by local twice learning and the DIJKSTRA algorithm is used to search out the shortest un-collision path of each branch. Finally, the layout of the branch pipe is obtained after optimizing the initial path. The method is implemented in a prototype system and demonstrated by typical cases.

Key words: auto layout, branch pipe, DIJKSTRA algorithm, LTL-PRM algorithm, minimum Steiner tree

CLC Number:

TP391

MA Jiangtao, LIU Jianhua, XU Lianjie, WU Hongchao, XU Jinbao. Method of Automatic Branch-pipe Routing Based LTL-PRM Algorithm[J]. Journal of Mechanical Engineering, 2018, 54(15): 160-170.

References

[1] NEWELL R G. An interactive approach to pipe routing in process plants[C]//IFIP Congress (2). 1971:1080-1085.
[2] KIM D G,CORNE D,ROSS P. Industrial plant pipe-route optimization with genetic algorithms[M]. Berlin Heidelberg:Springer,1996.
[3] PARK J H,STORCH R L. Pipe-routing algorithm development:Case study of a ship engine room design[J]. Expert Systems with Applications,2002,23(3):299-309.
[4] ASMARA A,NIENHUIS U. Automatic piping system in ship[C]//COMPIT-5th Int. Conf. on Computer and IT Application Mar. Ind.,2006.
[5] 邬君. 基于协同进化的船舶分支管路空间布局优化[D]. 大连:大连理工大学,2008. WU Jun. Coevolutionary optimization algorithm for ship branch pipe routing[D]. Dalian:Dalian University of Technology,2008.
[6] 邬君,林焰,纪卓尚,等. 基于协同进化的舰船分支管路系统路径优化研究[J]. 船海工程,2008,37(4):135-138. WU Jun,LIN Yan,JI Zhuoshang,et al. Optimal approach of ship branch pipe routing optimization based on co-evolutionary algorithm[J]. Ship & Ocean Engineering,2008,37(4):135-138.
[7] 封海波. 机械设备管路自动敷设设计方法的研究[D]. 哈尔滨:哈尔滨工业大学,2009. FENG Haibo. Resrarch on automatic design methods of pipeline laying in mechinery equipment[D]. Harbin:Harbin Institute of Technology,2009.
[8] LIU Q,WANG C. Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimization[J]. Enterprise Information Systems,2012,6(3):315-327.
[9] 白晓兰,王成恩,张禹,等. 三点间管路自动布局方法研究[J]. 东北大学学报,2009,30(2):283-286. BAI Xiaolan,WANG Chengen,ZHANG Yu,et al. On the automatic route layout for connection of three pipeline terminals[J]. Journal of Northeastern University,2009,30(2):283-286.
[10] 樊江,马枚,杨晓光. 航空发动机外部管路自动敷设研究[J]. 机械设计,2003,20(7):21-23. FAN Jiang,MA Mei,YANG Xiaoguang. Research on automatic laying out for external pipeline for aeroengine[J]. Journal of Machine Design,2003,20(7):21-23.
[11] KAVRAKI L E,ŠVESTKA P,LATOMBE J C,et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. Robotics and Automation,IEEE Transactions on,1996,12(4):566-580.
[12] AMATO N M,BAYAZIT O B,DALE L K, et al. OBPRM:An obstacle-based PRM for 3D workspaces[J]. In Robotics:The Algorithmic Perspective,1998:155-168.
[13] BOHLIN R,KAVRAKI L E. Path planning using lazy PRM[C]//Robotics and Automation,2000. Proceedings. ICRA'00. IEEE International Conference on. IEEE,2000,1:521-528.
[14] HSU D,JIANG T,REIF J,et al. The bridge test for sampling narrow passages with probabilistic roadmap planners[C]//Robotics and Automation,2003. Proceedings. ICRA'03. IEEE International Conference on. IEEE,2003,3:4420-4426.
[15] BOOR V,OVERMARS M H. The Gaussian sampling strategy for probabilistic roadmap planners[C]//Robotics and automation,1999. proceedings. 1999 ieee international conference on. IEEE,1999,2:1018-1023.
[16] WILMARTH S,AMATO N M,STILLER P E. MAPRM:A probabilistic roadmap planner with sampling on the medial axis of the free space[C]//Robotics and Automation,1999. Proceedings. 1999 IEEE International Conference on. IEEE,1999:1024-1031.
[17] SIMÉON T,LAUMOND J P,NISSOUX C. Visibility-based probabilistic roadmaps for motion planning[J]. Advanced Robotics,2000,14(6):477-493.
[18] 越民义. 最小网络:斯坦纳树问题[M]. 上海:上海科学技术出版社,2006. Yue Minyi. Minimal network-the problem of steiner tree[M]. Shanghai:Shanghai Scientific and Technological Publishers,2006.
[19] SMITH W D. How to find Steiner minimal trees in euclideand-space[J]. Algorithmica,1992,7(1-6):137-177.
[20] 柳金海. 管材管件应用技术手册[M]. 北京:机械工业出版社,2004. LIU Jinhai. Pipe and pipe fitting application technical manuals[M]. Beijing:China Machine Press,2004.
[21] RITTER J. An efficient bounding sphere[C]//Graphics gems. Academic Press Professional,Inc.,1990:301-303.
[22] DIJKSTRA E W. A note on two problems in connection with graphs[J]. Numerische Mathematic,1959,1(1):269-271.
[23] 刘密,刘检华,何永熹,等. 复杂结构条件下的装配路径求解与优化技术[J]. 机械工程学报,2013,50(9):97-105. LIU Mi,LIU Jianhua,HE Yongxi,et al. Research on assembly path planning and optimization of complex structures[J]. Journal of Mechanical Engineering,2013,50(9):97-105.
[24] 吴宏超,刘检华,唐承统,等. 基于改进A^*算法的管路自动布局设计与优化方法[J]. 计算机集成制造系统,2016,22(4):945-954. WU Hongchao,LIU Jianhua,TANG Chengtong,et al. Automatic pipe layout design and optimization method based on improved A^* algorithm[J]. Computer Integrated Manufacturing Systems,2016,22(4):945-954.