熊 晶 段晓坤

（常州信息职业技术学院，常州 213164）

产品装配路径规划是产品装配工艺设计的重要内容之一。尤其是复杂产品，它的零部件数量多，结构复杂，内部空间紧凑。在狭窄空间内为待装配的零部件计算出一条从装配起点到装配终点的无碰撞路径，是虚拟装配设计的难点之一。

基于几何图的路径规划算法，如栅格法[1]，在路径搜索之前，先对整个求解空间进行单元分割，并用分割单元对障碍空间和自由空间进行描述，再利用基于图的搜索算法，如A*算法[2-3]，在所构建的环境图中搜索有效路径，有利于获得优化路径解。但是，这种方式用于狭窄三维空间内的路径求解时，分割单元的尺寸将直接决定狭窄空间内有效节点的数量、求解成功率与效率。分割单元尺寸过大时，有效节点过少，求解困难；分割尺寸过小时，则存在组合爆炸的情况。

快速扩展随机树（Rapid-exploring Random Tree，RRT）[4-5]是一种随机采样的路径规划算法，特点在于利用随机性来处理C空间而无需对求解空间进行精确计算，因而广泛应用于高维空间下的路径规划问题。但是，由于狭窄空间内产品装配时受到的空间约束较大，使用RRT算法进行装配路径规划时，随机采样点搜索到狭窄空间的概率低，路径树扩展的成功率和效率都有待提高。

针对以上问题，本文结合栅格法与RRT算法的优点改进RRT算法，以待扩展树节点为中心，离散化局部空间，提出两种运动策略及对应的评价指标，引导局部路径的扩展。……