面向线束预装配的多约束线束布局方法研究

doi:10.11996/JG.j.2095-302X.2024010139

图学学报 ›› 2024, Vol. 45 ›› Issue (1): 139-147.DOI: 10.11996/JG.j.2095-302X.2024010139

• 计算机图形学与虚拟现实 • 上一篇下一篇

面向线束预装配的多约束线束布局方法研究

罗月童(), 彭俊, 高景一, 罗睿明, 陈绩, 周波()

合肥工业大学计算机与信息学院，安徽合肥 230601

收稿日期:2023-06-21 接受日期:2023-10-26 出版日期:2024-02-29 发布日期:2024-02-29
通讯作者: 周波(1981-)，男，副教授，博士。主要研究方向计算机辅助设计、地理信息系统。E-mail：zhoubo810707@hfut.edu.cn
作者简介:
罗月童(1978-)，男，教授，博士。主要研究方向为数据可视化、计算机辅助设计、计算机图形学。E-mail：ytluo@hfut.edu.cn
基金资助:
国家自然科学基金项目(61877016);国家自然科学基金项目(61602146)

Research on multi-constrained harness layout algorithm for harness pre-assembly

LUO Yuetong(), PENG Jun, GAO Jingyi, LUO Ruiming, CHEN Ji, ZHOU Bo()

School of Computer and Information, Hefei University of Technology, Hefei Anhui 230601, China

Received:2023-06-21 Accepted:2023-10-26 Online:2024-02-29 Published:2024-02-29
Contact: ZHOU Bo (1981-), associated professor, Ph.D. His main research interests cover computer-aided design, and geographic information system. E-mail：zhoubo810707@hfut.edu.cn
About author:
LUO Yuetong (1978-), professor, Ph.D. His main research interests cover data visualization, computer-aided design, and computer graphics. E-mail：ytluo@hfut.edu.cn
Supported by:
National Natural Science Foundation of China(61877016);National Natural Science Foundation of China(61602146)

摘要/Abstract

摘要：

线束由一组线束段按树状结构连接而成，是飞机汽车等产品中连接各电气设备的接线部件。为提高安装效率，复杂线束需要在线束工装板图上进行预安装，即根据角度、距离、交叉、边界等工艺约束在工装板上摆放线束，是一个多约束下的线束布局问题。通过借鉴图布局算法，将线束布局转换为优化问题，并采用随机梯度下降法SGD每次随机挑选一对线束段进行优化，逐步迭代收敛。因为线束段是长度不变的刚体，所以移动一根线束段时会带动相连的其他线束段，进而导致SGD迭代过程出现震荡，难以收敛。通过提出双向传递的线束段移动算法，在保证线束段能移动到目标位置的同时尽量少相连线束段的变动。使用合成线束案例和某真实飞机线束案例进行有效性验证，结果表明各工艺约束能均能得到满足，符合线束预装配的生产要求。

合肥工业大学罗月童教授及其学生彭俊等针对复杂线束的预装配中的布局问题，在参考图布局算法的基础上提出了基于随机梯度下降的多约束布局优化算法。针对线束段之间刚性连接所带来的优化震荡问题，提出了双向传动的线束段移动算法，减少线束段之间因刚性连接而带来的相互影响，从而减少化过程中的震荡。相关算法被应用于机舱线束布局等生成场景，能够满足生产需求。

关键词: 线束布局, 图布局, 随机梯度下降, 多约束, 预装配

Abstract:

The harness is composed of a group of harness segments connected in a tree structure. It is a wiring component connecting electrical equipment in aircraft, automobile, and other products. To improve assembly efficiency, complex wiring harnesses need to be pre-assembled on an assembly board. This involves placing the wiring harnesses on the assembly board in a way that meets process constraints such as angle, distance, intersection, and boundary. This presents a multi-constrained harness layout problem. The paper drew upon a graph layout method, transformed the wiring harness layout into an optimization problem, and employed SGD to optimize a randomly selected pair of harness segments each time, gradually iterating and converging. Due to harness segments being rigid bodies with constant length, moving one segment could affect other segments, leading to oscillations in the SGD iteration process and making convergence difficult. Therefore, a bidirectional transmission segment movement algorithm was proposed to minimize the impact on other segments while ensuring that the segment moved to the target position. Both synthetic cases and a real case of an aircraft wiring harness were used for effectiveness verification, and the results showed that various process constraints could be met, and production requirements for wire harness pre-assembly could be satisfied.

Key words: wiring harness layout, graph layout, stochastic gradient descent, multiple constraints, pre-assembly

中图分类号:

TP391

罗月童, 彭俊, 高景一, 罗睿明, 陈绩, 周波. 面向线束预装配的多约束线束布局方法研究[J]. 图学学报, 2024, 45(1): 139-147.

LUO Yuetong, PENG Jun, GAO Jingyi, LUO Ruiming, CHEN Ji, ZHOU Bo. Research on multi-constrained harness layout algorithm for harness pre-assembly[J]. Journal of Graphics, 2024, 45(1): 139-147.

图/表 19

图1 线束设计图和布局图示例((a)线束设计图；(b)线束设计图投影；(c)线束工装板结果示意图)

Fig. 1 Example of a harness design and layout diagram ((a) Wiring harness design drawing; (b) Harness design drawing projection; (c) Schematic diagram of the wire harness tooling board results)

图2 线束结构示意图

Fig. 2 Schematic diagram of the wiring harness structure

算法1. 线束布局算法
1. Harness_SGD_Layout(H)
	Input: 线束：H=(hs₁,hs₂,···,hs_n)
	Output: 完成布局的线束H=(hs₁,hs₂,···,hs_n)
2.	iteration←0;
3.	while 不满足结束条件
4.		η←annealing(iteration)
5.		foreach随机线束段对(hs_i,hs_j),i≠j
7.			(dx,dy)←η×CalcMovement(hs_i,hs_j);
8.			BiMove(hs_i,α,dx,dy);
9.	return

图3 角度约束示意图

Fig. 3 Schematic diagram of angle constraints

图4 距离约束计算方法示意图

Fig. 4 Schematic diagram of the distance constraint calculation method

图5 边界约束计算方法示意图

Fig. 5 Schematic diagram of the boundary constraint calculation method

图6 交叉约束计算示意图

Fig. 6 Schematic diagram of the cross-constraint calculation

图7 线束段旋转移动方式示意图

Fig. 7 Schematic diagram of how harness segments rotate and move

图8 子线束移动对比图

Fig. 8 Subharness movement comparison chart

算法2. 线束段调整的向上传递
1. UpMove(hs,α,dx,dy)
	Input: dx, dy：线束段hs终点的位移量 α：分配位移量的比例参数
	Output: 完成位置调整的线束；
2.	if (dx<1.0e-5 && dy<1.0e-5) return;
3.	if (hs是根线束段) DownMove(hs,dx,dy)；//向下传递
4.	dxP←α×dx; dyP←α×dy;//父线束终点位移量
5.	dx←(1-α)×dx; dy←(1-α)×dy;//hs终点位移量
6.	UpMonv(hs.Parent,α,dxpP,dyP);//向上传递
7.	DownMove(hs,dx,dy);//向下传递
8.	return;

图9 “向上传递”策略示例

Fig. 9 Example of a “pass up” policy

图10 孩子线束段终点位置计算方法

Fig. 10 How to calculate the end position of the child’s harness segment

算法3. 线束段移动的向下传递
1. DownMove(hs,dx,dy)
	Input: dx, dy：线束段hs终点的位移量
	Output: 完成位置调整的线束;
2.	newEPtx←hs.EPtx+dx;//hs新终点位置
3.	newEPty←hs.EPty+dy;
4.	hs.setEndPt(newEPtx,newEPty);
5.	sPtx←newEPtx//孩子线束段新起点
6.	sPty←newEPty
7.	foreach 孩子线束段chs
8.	(cdx,cdy)←MinMove(chs,sPtx,sPty)
9.	chs.setStartPt(sPtx,sPty);
10.	DownMove(chs,cdx,cdy);//递归
11.	return

图11 合成案例调整情况((a)初始布局情况；(b)设置调整结果；(c)设置调整结果)

Fig. 11 Synthesis case adjustment ((a) Initial layout situation; (b) Set 1 adjustment result; (c) Set 2 adjustment effect)

表1 超参数配置

Table 1 Hyperparameter configuration

参数	设置1	设置2
θ_H	45.0	60.0
θ_S	30.0	45.0
d_H	30.0	15.0
d_S	50.0	30.0
y_u	400.0	450.0
β	30.0	0.0

表2 实际案例基本情况

Table 2 Basic information of actual cases

实例	线束段总数	违规线束段数	典型违规约束	初始正确率/%	最终正确率/%
(1)	99	53	距离约束交叉约束	46.46	100
(2)	80	59	边界约束距离约束	26.25	100
(3)	45	10	交叉约束	77.77	100

图12 实际案例(1)的初始布局及最终布局((a)初始状态；(b)调整结果)

Fig. 12 The initial layout and final layout of the actual case (1) ((a) Initial state; (b) Adjustment results)

图13 实际案例(2)的初始布局及最终布局((a)初始状态；(b)调整结果)

Fig. 13 The initial layout and final layout of the actual case (2) ((a) Initial state; (b) Adjustment results)

图14 实际案例(3)的初始布局及最终布局((a)初始状态；(b)调整结果)

Fig. 14 The initial layout and final layout of the actual case (3) ((a) Initial state; (b) Adjustment results)

参考文献 12

[1]	徐本柱, 程光春, 李忠泽, 等. 基于力导向算法的线束连接图自动布局研究[J]. 工程图学学报, 2010, 31(6): 171-177.
	XU B Z, CHENG G C, LI Z Z, et al. Research on automatic layout of wire-harness connection graph based on force-directed algorithm[J]. Journal of Engineering Graphics, 2010, 31(6): 171-177 (in Chinese).
[2]	程光春. 汽车线束图纸的自动布局研究[D]. 合肥: 合肥工业大学, 2009.
	CHENG G C. Research on automatic layout of automobile wire harness drawings[D]. Hefei: Hefei University of Technology, 2009 (in Chinese).
[3]	WAGNER D, KAUFMANN M. Drawing Graphs: Methods and Models[M]. Heidelberg: Springer-Verlag: Springer, 2001: 1-22
[4]	KAMADA T, KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters, 1989, 31(1): 7-15. DOI URL
[5]	GANSNER E R, KOREN Y, NORTH S. Graph drawing by stress majorization[C]// International Symposium on Graph Drawing. Berlin, Heidelberg: Springer, 2005: 239-250.
[6]	GANSNER E R, HU Y F, NORTH S. A maxent-stress model for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(6): 927-940. DOI URL
[7]	KHOURY M, HU Y F, KRISHNAN S, et al. Drawing large graphs by low-rank stress majorization[J]. Computer Graphics Forum, 2012, 31(3pt1): 975-984. DOI URL
[8]	ORTMANN M, KLIMENTA M, BRANDES U. A sparse stress model[C]// International Symposium on Graph Drawing and Network Visualization. Cham: Springer, 2016: 18-32.
[9]	ZHENG J X, PAWAR S, GOODMAN D F M. Graph drawing by stochastic gradient descent[J]. IEEE Transactions on Visualization and Computer Graphics, 2019, 25(9): 2738-2748. DOI URL
[10]	AHMED R, DE LUCA F, DEVKOTA S, et al. Multicriteria scalable graph drawing via stochastic gradient descent, $(SGD)^{2}$(SGD)₂[J]. IEEE Transactions on Visualization and Computer Graphics, 2022, 28(6): 2388-2399.
[11]	XUE M L, WANG Z, ZHONG F H, et al. Taurus: towards a unified force representation and universal solver for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2023, 29(1): 886-895.
[12]	LONG T F, JIAO W L, HE G J, et al. Block adjustment with relaxed constraints from reference images of coarse resolution[J]. IEEE Transactions on Geoscience and Remote Sensing, 2020, 58(11): 7815-7828. DOI URL

面向线束预装配的多约束线束布局方法研究

Research on multi-constrained harness layout algorithm for harness pre-assembly

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 19

参考文献 12

相关文章 4

编辑推荐

Metrics

本文评价

[1]	张野，王松，吴亚东 . FMR：基于 FR 的快速多层次算法[J]. 图学学报, 2019, 40(1): 78-86.
[2]	陈炳坤，周虹 . 基于多层图布局算法的不确定性网络可视化方法[J]. 图学学报, 2018, 39(6): 1130-1138.
[3]	李博，吉晓民，陈登凯，余隋怀. 多约束下的载人潜器舱内计算机辅助工效设计系统研究[J]. 图学学报, 2014, 35(4): 553-562.
[4]	杨铮园，申立勇. 燃气燃爆实验数据的多约束B 样条曲线拟合[J]. 图学学报, 2014, 35(4): 595-602.