基于改进A*算法的线缆路径规划方法

摘要/Abstract

摘要： 针对复杂布线空间环境下虚拟线缆的路径规划问题，改进了传统A*算法的估价函数，引入附加值因子来选择合适的路径节点，使用刚性因子评估连续弯折时的线缆路径，将线缆的位置纳入算法来调整线缆路径到最优。二维网格地图中的路径规划和三维模型中的布线结果均表明，改进A*算法能产生合理的布线路径。

关键词: 线缆路径规划, 附加值因子, 刚性因子, A*算法

Abstract: Aiming at the path planning problems of virtual cable routing in complex wiring space environments, the evaluation function of traditional A* algorithm was improved herein, and an additional value factor was introduced to select the appropriate path nodes. Moreover, rigid factor which was used to evaluate the cable paths in continuous bending was applied, and location factor of cable routing was incorporated into the algorithm to adjust the positions of optimal cable paths. Path planning in 2D grid map and wiring results in 3D model show that the improved A* algorithm may generate a reasonable routing paths.

Key words: cable path planning, added value factor, rigidity factor, A* algorithm

中图分类号:

TP391.9

姜康;马世纪. 基于改进A*算法的线缆路径规划方法[J]. 中国机械工程.

JIANG Kang;MA Shiji. A Cable Path Planning Method Based on Improved A* Algorithm[J]. China Mechanical Engineering.

参考文献

[1]王发麟, 廖文和, 郭宇,等. 线缆虚拟装配关键技术研究现状及其发展[J]. 中国机械工程, 2016, 27(6):839-851.
WANG Falin, LIAO Wenhe, GUO Yu, et al. Research Status and Its Perspective of Key Techniques for Cable Harness Virtual Assembly[J]. China Mechanical Engineering, 2016, 27(6): 839-851.
[2]原彬, 熊伟, 王祖温. 电缆虚拟装配的关键技术及其发展[J]. 机械科学与技术, 2010, 29(5):695-700.
YUAN Bin, XIONG Wei, WANG Zuwen. A Review of the Key Techniques of Virtual Assembly for Cable Harness[J]. Mechanical Science and Technology for Aerospace Engineering, 2010, 29(5):695-700.
[3]PARK H, CUTKOSKY M R, CONRU A B, et al. An Agent-based Approach to Concurrent Cable Harness Design[J]. Artificial Intelligence for Engineering Design Analysis & Manufacturing, 1994, 8(1):45-61.
[4]CONRU A B. A Genetic Approach to the Cable Harness Routing Problem[C] // IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence. Orlando: IEEE, 1994:200-205.
[5]付宜利, 封海波, 孙建勋,等. 机电产品管路自动敷设的粒子群算法[J]. 机械工程学报, 2007, 43(11):194-199.
FU Yili, FENG Haibo, SUN Jianxun, et al. Automatic Pipe-routing Particle Swarm Optimization Algorithm in Electromechamical Products[J]. Journal of Mechanical Engineering, 2007, 43(11):194-199.
[6]权建洲, 韩明晶, 李智. 基于改进A*算法的电子制造装备布线方法研究[J]. 中国科技论文, 2009, 4(8): 555-559.
QUAN Jianzhou, HAN Mingjing, LI Zhi. Study on the Wiring of Electronic Manufacturing Equipments Based on a Modified A* Algorithm[J]. Science Paper Online, 2009, 4(8):555-559.
[7]DAI Z, GUAN Y, GUAN R. Dynamic Adjustment A* Routing Algorithm[C]// 2010 Asia-Pacific Conf. on Innovative Computing & Communication. Macao: IEEE, 2010:316-318.
[8]李纯军, 尹周平, 熊涛,等. 基于A*算法的机电产品管线自动敷设方法研究[J]. 科学技术与工程, 2011, 11(7): 1474-1479.
LI Chunjun, YIN Zhouping, XIONG Tao, et al. Study on the Auto-routing Method of Electromechanical Products Based on A* Algorithm[J]. Science Technology and Engineering, 2011, 11(7):1474-1479.
[9]姜康, 胡龙. 复杂环境下的装配路径求解与优化[J]. 中国机械工程, 2015, 26(5):632-636.
JIANG Kang, HU Long. Assembly Path Panning and Optimization under Complex Environments[J]. China Mechanical Engineering, 2015, 26(5): 632-636.
[10]展慧娴, 卓勇, 吴轩,等. 基于A*算法MID三维布线的研究与实现[J]. 厦门大学学报(自然科学版), 2015, 54(6): 888-892.
ZHAN Huixian, ZHUO Yong, WU Xuan, et al. The Realization of 3D Routing Based on A* Algorithm in MID Design[J]. Journal of Xiamen University(Natural Science), 2015, 54(6):888-892.
[11]李国闻, 张丹, 杜海遥,等. 基于遗传算法的机电产品布线结构优化设计方法[J]. 中国科技论文, 2015(16): 1944-1948.
LI Guowen, ZHANG Dan, DU Haiyao, et al. Configuration Optimization for Electromechanical Products Cable Harness Design Based on Genetic Algorithm[J]. China Science Paper, 2015(16):1944-1948.
[12]刘云翔, 杜杰, 张晴. 基于路径优化的A*算法与Dijkstra算法的性能比较[J]. 现代电子技术, 2017, 40(13): 181-183.
LIU Yunxiang, DU Jie, ZHANG Qing. Performance Comparison of A* Algorithm and Dijkstra Algorithm Based on Path Optimization[J]. Modern Electronic Technology, 2017, 40(13):181-183.
[13]陈彬, 李靖靖, 宋磊,等. 基于可视图和A*算法的连续模型路径搜索[J]. 交通信息与安全, 2012, 30(3):39-42.
CHEN Bin, LI Jingjing, SONG Lei, et al. Path Searching For Continuous Model Based on Visibility Graph and A* Algorithm[J]. Journal of Transport Information and Safety, 2012, 30(3):39-42.
[14]王红卫, 马勇, 谢勇,等. 基于平滑A*算法的移动机器人路径规划[J]. 同济大学学报(自然科学版), 2010, 38(11):1647-1650.
WANG Hongwei, MA Yong, XIE Yong, et al. Mobile Robot Optimal Path Planning Based on Smoothing A* Algorithm[J]. Journal of Tongji University(Natural Science), 2010, 38(11): 1647-1650.
[15]孙炜, 吕云峰, 唐宏伟,等. 基于一种改进A*算法的移动机器人路径规划[J]. 湖南大学学报(自科科学版), 2017, 44(4):94-101.
SUN Wei, LYU Yunfeng, TANG Hongwei, et al. Mobile Robot Path Planning Based on an Improved A* Algorithm[J]. Journal of Hunan University (Natural Science), 2017, 44(4): 94-101.
[16]陈刚, 付少锋, 周利华. A*算法在游戏地图寻径中的几种改进策略研究[J]. 科学技术与工程, 2007, 7(15): 3731-3736.
CHEN Gang, FU Shaofeng, ZHOU Lihua. Research on Improving A* Algorithm in Game Map Path Finding[J]. Science Technology and Engineering, 2007, 7(15): 3731-3736.
[17]刘潇, 刘检华, 刘佳顺,等. 基于改进随机路径图的分支线缆自动布局技术[J]. 计算机集成制造系统, 2014, 20(12): 2952-2961.
LIU Xiao, LIU Jianhua, LIU Jiashun, et al.Multi-branch Cable Automatic Routing Based on Improved PRM[J]. Computer Integrated Manufacturing Systems, 2014, 20(12): 2952-2961.
[18]樊江, 马枚, 杨晓光. 航空发动机外部管路自动敷设研究[J]. 机械设计, 2003, 20(7):21-23.
FAN Jiang, MA Mei, YANG Xiaoguang. Research on Automatic Laying out for External Pipeline of Aeroengine[J]. Machine Design, 2003, 20(7):21-23.
[19]吴宏超, 刘检华, 唐承统,等. 基于改进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.
[20]魏发远, 陈新发, 王峰军. 电缆虚拟布线及其逆运动学仿真[J]. 计算机辅助设计与图形学学报, 2006, 18(10): 1623-1627.
WEI Fayuan, CHEN Xinfa,WANG Fengjun. Virtual Wiring and Simulation of Cable Layout with Inverse Kinematics[J]. Journal of Computer-Aided Design & Computer Graphics,2006,18(10):1623-1627.
[21]刘检华, 万毕乐, 孙刚,等. 线缆虚拟布线与敷设过程仿真技术[J]. 计算机集成制造系统, 2012, 18(4):787-795.
LIU Jianhua, WAN Bile, SUN Gang, et al. Cable Harness Virtual Wiring and Assembly Process Simulation Technology[J]. Computer Integrated Manufacturing Systems, 2012, 18(4):787-795.
[22]郑超, 曹伦, 周晓东,等. 基于Creo/Cabling的电力电子设备三维布线应用[J]. 机械设计与制造工程, 2015(6): 27-31.
ZHENG Chao, CAO Lun, ZHOU Xiaodong, et al. Application of 3D Routing Based on Creo/Cabling in Power Electronic Equipment[J]. Machine Design and Manufacturing Engineering, 2015(6):27-31.