Abstract: Aiming at the automatic routing and optimization problem of multi-branch cable in mechanical and electrical products,a multi-branch cable automatic routing method based on Steiner Minimal Tree (SMT) and improved Low Dispersion and Obstacle Based Probabilistic Roadmap (LDOB-PRM) algorithms was proposed.In this method,Steiner points with constraints were solved by SMT to determine the location of middle forked points.Based on the basic PRM algorithm,the mixed sampling strategy based on low dispersion and obstacle was adopted to construct a path map covering the surface of whole space obstacle.The shortest distance of each path was searched by A* algorithm.The path points were fitted and the multi-branch cable layout design result was obtained.A multi-branch cable automatic routing prototype system was developed and some experiments were tested to prove the feasibility of the proposed method.

Key words: multi-branch cable, automatic routing, probabilistic roadmaps algorithm, Steiner minimal tree, mechanical and electrical products

摘要： 针对机电产品中的分支线缆自动布局设计与优化难题,提出一种基于最小斯坦纳生成树和改进的随机路径图算法的分支线缆自动布局设计方法。该方法采用最小斯坦纳生成树算法求解带有约束的斯坦纳点,并将该点确定为分支线缆的分支点;以基本随机路径图算法为基础,采用低离散度和基于障碍物的混合采样策略,构建一幅覆盖全空间障碍物表面的路径图,再利用A*算法搜索各线缆段的最短路径;对求解得到的路径点进行拟合,并最终获得分支线缆布局设计结果。设计并开发了分支线缆自动布局设计软件原型系统,并进行了算例测试与实例验证,证明了所提方法的可行性。

关键词: 分支线缆, 自动布局设计, 随机路径图, 最小斯坦纳生成树, 机电产品