一种考虑复杂约束的线缆束路径规划方法

doi:10.19665/j.issn1001-2400.2021.03.024

摘要/Abstract

摘要：

针对现有的路径规划方法无法用于考虑复杂工程规则约束的多电飞机机载设备线缆束路径规划的问题,基于拟物拟人算法和改进A*算法,研究并提出一种考虑复杂约束的线缆束路径规划方法。首先,提出了综合考虑路径长度成本、弯线槽材料成本、弯线槽工艺成本和弯线槽重量成本的布线总成本的计算方法,并改进了传统A*算法中的估价函数;然后,基于拟物拟人算法计算出线缆束的等效半径,提出考虑工程规则约束的搜索空间自动处理算法和拐角节点合理性判定算法,进而提出了使用改进A*算法进行线缆束路径规划的流程。通过某机载设备线缆束敷设的实例验证表明,使用提出的改进A*算法得到的线缆束布线路径,不仅能满足复杂的约束条件,且布线总成本比现有算法减小了5.1%。

关键词: 线缆, 拟物拟人算法, 改进A*算法, 布线, 规划

Abstract:

Aiming at the problem that the existing path planning method cannot be used in the path planning of multiple electric aircraft airborne equipment cable harness which considers complex engineering rules constraints,a route planning method considering complex constraints is studied and proposed based on the Quasi-Physical and Quasi-Human algorithm and improved A* algorithm.First,the calculation method for the total wiring cost considering the path length cost and the material cost,process cost and weight cost of the bending groove is proposed,with the evaluation function of the traditional A* algorithm improved.Then,the equivalent radius of the cable harness is calculated based on the Quasi-Physical and Quasi-Human algorithm,and the search space automatic processing algorithm and the corner node reasonableness judgment algorithm considering the constraints of engineering rules are proposed.Finally,an example of cable harness laying in an airborne equipment shows that the routing path obtained by using the improved A* algorithm can not only meet the complex constraints,but also reduce the total wiring cost by 5.1% compared with the existing algorithm.

Key words: cable, Quasi-Physical and Quasi-Human algorithm, improved A* algorithm, wiring, planning

中图分类号:

TP391.9

杨旭,周德俭,宋微,陈小勇. 一种考虑复杂约束的线缆束路径规划方法[J]. 西安电子科技大学学报, 2021, 48(3): 197-204.

YANG Xu,ZHOU Dejian,SONG Wei,CHEN Xiaoyong. Path planning method for cable harness considering complex constraints[J]. Journal of Xidian University, 2021, 48(3): 197-204.

图/表 11

图1

图3

图2

图4

图5

表1

表2

图6

图7

参考文献 18

[1]	李春泉, 徐楚, 张明, 等. 轮廓扩展方法下的电气线缆布线技术研究[J]. 机械设计与制造, 2015,(4):266-269.
	LI Chunquan, XU Chu, ZHANG Ming, et al. Routing Technology of Electric Cables Using the Method of Contour Extension[J]. Machinery Design & Manufacture, 2015,(4):266-269.
[2]	姜康, 马世纪. 基于改进A*算法的线缆路径规划方法[J]. 中国机械工程, 2019,30(6):699-708.
	JIANG Kang, MA Shiji. A Cable Path Planning Method Based on Improved A* Algorithm[J]. China Mechanical Engineering, 2019,30(6):699-708.
[3]	陈晋吉. 飞机电磁兼容预测仿真研究[D]. 西安:西安电子科技大学, 2013.
[4]	杨福荣, 李鹏, 许万业, 等. 线缆-机箱电磁兼容分析的PEEC-MoM混合方法[J]. 西安电子科技大学学报, 2016,43(6):147-157.
	YANG Furong, LI Peng, XU Wanye, et al. PEEC-MoM Hybrid Method for Electromagnetic Compatibility Analysis of the Cable-enclosure System[J]. Journal of Xidian University, 2016,43(6):147-157.
[5]	吴宏超, 刘检华, 唐承统, 等. 基于改进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.
[6]	顾青, 豆风铅, 马飞. 基于改进A*算法的电动车能耗最优路径规划[J]. 农业机械学报, 2015,46(12):321-327.
	GU Qing, DOU Fengqian, MA Fei. Energy Optimal Path Planning of Electric Vehicle Based on Improved A* Algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2015,46(12):321-327.
[7]	邹善席, 王品, 韩旭. 基于PRM改进的路径规划算法[J]. 组合机床与自动化加工技术, 2019,(1):6-8.
	ZOU Shanxi, WANG Pin, HAN Xu. Improved Path Planning Algorithm Based on PRM[J]. Modular Machine Tool& Automatic Manufacturing Technique, 2019,(1):6-8.
[8]	马江涛, 刘检华, 徐联杰, 等. 基于LTL-PRM算法的分支管路自动布局方法[J]. 机械工程学报, 2018,54(15):160-170.
	MA Jiangtao, LIU Jianhua, XU Lianjie, et al. Method of Automatic Branch-pipe Routing Based LTL-PRM Algorithm[J]. Journal of Mechanical Engineering, 2018,54(15):160-170.
[9]	陈波芝, 陆亮, 雷新宇, 等. 基于改进快速扩展随机树算法的双机械臂协同避障规划方法[J]. 中国机械工程, 2018,29(10):1220-1226.
	CHEN Bozhi, LU Liang, LEI Xinyu, et al. Simultaneous Obstacle-avoidance Motion Planning Approach for Dual Arm Robots Based on Improved RRT Algorithm[J]. China Mechanical Engineering, 2018,29(10):1220-1226.
[10]	CHEN Y, HE Z, LI S L. Horizon-based Lazy Optimal RRT for Fast,Efficient Replanning in Dynamic Environment[J]. Autonomous Robots, 2019,43(8):2271-2292. doi: 10.1007/s10514-019-09879-8
[11]	侯仰强, 王天琪, 岳建锋, 等. 基于多目标遗传算法的双机器人协调焊接路径规划[J]. 中国机械工程, 2018,29(16):1984-1989.
	HOU Yangqiang, WANG Tianqi, YUE Jianfeng, et al. Path Planning for Dual-robot Coordinate Welding Based on Multi-objective Genetic Algorithm[J]. China Mechanical Engineering, 2018,29(16):1984-1989.
[12]	杨亚君, 陈章. 分块制造下硬件木马攻击方法及安全性分析[J]. 西安电子科技大学学报, 2019,46(4):167-175.
	YANG Yajun, CHEN Zhang. Hardware Trojan Attack Methods and Security Analysis under Split Manufacturing[J]. Journal of Xidian University, 2019,46(4):167-175.
[13]	KALA R, SHUKLA A, TIWARI R. Fusion of Probabilistic A* Algorithm and Fuzzy Inference System for Robotic Path Planning[J]. Artificial Intelligence Review, 2010,33(4):307-327. doi: 10.1007/s10462-010-9157-y
[14]	CHEN B Y, LAM W H K, SUMALEE A, et al. Reliable Shortest Path Finding in Stochastic Networks with Spatial Correlated Link Travel Times[J]. International Journal of Geographical Information Science, 2012,26(2):365-386. doi: 10.1080/13658816.2011.598133
[15]	RAHAMAN M S, MEI Y, HAMILTON M, et al. CAPRA:a Contour-based Accessible Path Routing Algorithm[J]. Information Sciences, 2017,385/386:157-173. doi: 10.1016/j.ins.2016.12.041
[16]	HERMANSSON T, BOHLIN R, CARLSON J S, et al. Automatic Routing of Flexible 1D Components with Functional and Manufacturing Constraints[J]. Computer-Aided Design, 2016,79:27-35. doi: 10.1016/j.cad.2016.05.018
[17]	HUANG W Q, XU R C. Two Personification Strategies for Solving Circles Packing Problem[J]. Science in China,Series E:Technological Sciences, 1999,42(6):595-602. doi: 10.1007/BF02916995
[18]	韩明晶. 基于A*算法的电子制造装备布线研究[D]. 武汉:华中科技大学, 2009.

线缆类型	半径R_i/mm	根数	λ_i
1	1.5	1	8
2	1.2	1	8
3	0.9	2	8
4	0.6	3	20
5	0.3	10	20

算法编号	策略	搜索空间自动处理	拐角节点合理性判定	估价函数	90°拐角个数	135°拐角个数	路径长度 /mm	总耗费
1	A*	否	否	g(n)+h(n)	0	8
2	A*	是	否	g(n)+h(n)	0	9
3	A*	是	是	g(n)+h(n)	3	3	723.61	1 930.10
4	改进A*	是	是	g*(n)+h(n)+ s(n)	4	2	735.57	1 832.38