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

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 19

References 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

算法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

算法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

算法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;

算法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;

算法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