基于LTL-PRM算法的分支管路自动布局方法

doi:10.3901/JME.2018.15.160

机械工程学报 ›› 2018, Vol. 54 ›› Issue (15): 160-170.doi: 10.3901/JME.2018.15.160

扫码分享

基于LTL-PRM算法的分支管路自动布局方法

马江涛, 刘检华, 徐联杰, 吴宏超, 徐金宝

北京理工大学机械与车辆学院北京 100081

收稿日期:2017-08-11 修回日期:2017-12-08 出版日期:2018-08-05 发布日期:2018-08-05
通讯作者: 刘检华(通信作者),男,1977年出生,教授,博士研究生导师。主要研究方向为数字化装配技术。E-mail:jeffliu@bit.edu.cn
作者简介:马江涛,男,1993年出生,博士研究生。主要研究方向为线缆与管路的装配规划与仿真技术。E-mail:bitmjt@bit.edu.cn;徐联杰,男,1990年出生,硕士研究生。主要研究方向为管路自动布局技术。E-mail:xulianjie1234@163.com;吴宏超,男,1991年出生,硕士研究生。主要研究方向为管路自动布局与优化技术;徐金宝,男,1991年出生,硕士研究生。主要研究方向为分支线缆自动布局技术。
基金资助:
国防基础科研资助项目（JCKY2016204A502，JCKY2017204B502）。

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

MA Jiangtao, LIU Jianhua, XU Lianjie, WU Hongchao, XU Jinbao

School of Mechanical Engineering, Beijing Institute of Technology, Beijing 100081

Received:2017-08-11 Revised:2017-12-08 Online:2018-08-05 Published:2018-08-05

摘要/Abstract

摘要： 针对非正交分支管路的自动布局问题，提出一种基于局部二次学习概率路径图算法（LTL-PRM）的分支管路自动布局方法，该方法首先采用回溯算法计算出端点之间的最小斯坦纳树，并对其中的斯坦纳点位置进行优化处理，从而获得管路系统的分支点位置，在此基础上通过局部二次学习构建路径图，并利用DIJKSTRA算法搜索出各分支管路的最短路径，最后对搜索出的路径进行优化，从而获得分支管路的最终布局结果。基于此方法，开发了管路自动布局设计软件系统并进行了实例分析，验证了该方法的可行性。

关键词: DIJKSTRA算法, LTL-PRM算法, 分支管路, 自动布局, 最小斯坦纳树

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

中图分类号:

TP391

马江涛, 刘检华, 徐联杰, 吴宏超, 徐金宝. 基于LTL-PRM算法的分支管路自动布局方法[J]. 机械工程学报, 2018, 54(15): 160-170.

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.

参考文献

[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.

基于LTL-PRM算法的分支管路自动布局方法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	张禹, 范志刚, 于润泽, 石可, 鹿浩, 张明, 巩亚东. 基于Steiner最小树和改进多目标萤火虫算法的航空发动机分支管路自动布局[J]. 机械工程学报, 2024, 60(12): 365-372.
[2]	崔钰萍, 郑国磊. 电缆布局设计技术研究进展综述[J]. 机械工程学报, 2023, 59(2): 268-280.
[3]	柳强, 毛莉. 基于MOPSO的航空发动机分支管路多目标布局优化[J]. 机械工程学报, 2018, 54(19): 197-203.
[4]	赵柏萱, 刘检华, 宁汝新, 龚晶. 一种基于工程规则的管路自动布局与综合优化技术[J]. 机械工程学报, 2015, 51(21): 121-131.
[5]	楼洪梁;杨将新;林亚福;胡建坤;吴昭同;盛伯浩. 基于图论的可重构制造系统重构策略[J]. , 2006, 42(3): 22-29.