基于空间−区间双分治的机械臂路径规划

Research on Robotic Manipulator Path Planning Based on Dual Space−Interval Divide-and-Conquer

  • 摘要: 针对机械臂路径规划中基于采样的传统算法因随机采样而引发冗余搜索、路径剪枝中碰撞检测计算量大等问题,提出空间−区间双分治算法框架,缩短路径构建生成时间并降低路径剪枝计算开销,提高作业效率. 首先,在空间分治层融合八叉树拓扑结构与双向搜索机制提出双向拓展八叉树(Octree-Connect)算法,建立基于八叉树子节点拓展方向的结构化导向采样策略以约束高概率可行区域,较传统方法减少44.3%采样点并降低67.1%初始规划耗时,且在极端采样次数限制下仍能保持高规划成功率,展现了优异的鲁棒性. 其次,在区间分治层基于对分查找的递归分治机制提出对分剪枝(Binary Pruning)算法,融入贪心思路优先检测始末节点与中间节点的可连接性,将O(N)级全局优化转化为O(log N)级局部收敛,提升24.8%计算效率并保证路径质量. 最后,通过机械臂运动仿真及减速器人机协作装配多场景验证,表明Octree-Connect + Binary Pruning算法组合使逆运动学求解耗时稳定缩减0.1~10秒、规划成功率提升至少16.3%,验证了该算法组合的有效性和先进性.

     

    Abstract: To address the problems of redundant search caused by random sampling and high computational cost of collision detection during path pruning in traditional sampling-based robotic manipulator path planning algorithms, a dual space–interval divide-and-conquer algorithmic framework was proposed to shorten path construction time and reduce pruning computation overhead, thereby improving operational efficiency. First, at the spatial divide-and-conquer level, an Octree-Connect algorithm was proposed by integrating an octree topological structure with a bidirectional search mechanism. A structured guided sampling strategy based on the expansion directions of octree child nodes was established to constrain high-probability feasible regions. Compared with traditional methods, the proposed approach reduced the number of sampled points by 44.3% and decreased initial planning time by 67.1%. Moreover, it maintained a high planning success rate even under extremely limited sampling budgets, demonstrating strong robustness. Second, at the interval divide-and-conquer level, a Binary Pruning algorithm was developed based on a recursive divide-and-conquer mechanism derived from binary search. By incorporating a greedy strategy that prioritizes connectivity checks between the start and goal nodes and intermediate nodes, the algorithm transformed global optimization with O(N) complexity into local convergence with O(log N) complexity, improving computational efficiency by 24.8% while ensuring path quality. Finally, through robotic manipulator motion simulations and multi-scenario validations in human-robot collaborative reducer assembly, the combined Octree-Connect + Binary Pruning approach was shown to stably reduce inverse kinematics solving time by 0.1~10 seconds and increase the planning success rate by at least 16.3%, thereby verifying the effectiveness and advanced nature of the proposed algorithmic combination.

     

/

返回文章
返回