高级搜索

    拓扑信息引导的多连通分量分层路径规划算法

    Hierarchical Path Planning for Multi-Component Graphics Guided by Topological Information

    • 摘要: 在机器人绘图、增材制造和数控加工等领域,高效绘制具有多个分离连通分量的复杂图形是提升加工效率与质量的关键.现有路径规划方法在处理含嵌套结构的多连通分量图形时,通常难以显式建模拓扑层级关系,难以在全局约束下最小化提笔移动距离.为此,提出一种分层拓扑优化算法,该算法基于图形组件间的拓扑包含关系构建层级结构,并融合全局优化与局部贪心策略确定连接顺序.通过在自定义、QuickDraw和KanjiVG这3类数据集上,将该算法与简单拼接、深度优先贪心及旅行商问题优化3种基准策略进行对比,测试结果表明,该算法在保证路径完整性和平均提笔次数基本持平的情况下,分层拓扑优化算法在平均提笔移动距离比例上表现最优,尤其在处理复杂嵌套与分离结构图形时优势显著.与纯粹基于距离优化的策略相比,该算法不仅降低了平均提笔移动距离比例,在执行时间上也未显著增加,虽计算开销略有增加,但时间复杂度未出现量级跃升,展现出良好的扩展性.在糖画机器人系统的应用实验中,该算法能精准处理复杂图形,降低提笔移动距离,具有显著工程实用性与应用价值.

       

      Abstract: This study addressed the problem of reducing non-productive pen-up motion when drawing graphics that contain multiple disconnected and nested components.A hierarchical topological optimization algorithm was developed to model component-wise containment relations and to improve the planning of inter-component transitions.The graphic was first decomposed into connected components,and an internal coverage path was generated for each component.Topological containment was then identified through component boundary analysis.A hierarchical planning strategy was established:global traveling-sequence optimization was applied to top-level components using a nearest-neighbor and 2-opt solver,and nested components were processed through a deterministic greedy rule based on local distance.The algorithm integrated internal paths with optimized inter-component connections to form a complete drawing path.The algorithm was evaluated on three datasets—custom graphics,Google QuickDraw sketches,and KanjiVG characters.The results showed that it achieved 100% path completeness and produced the lowest pen-up movement distance ratio among the compared strategies,including simple concatenation,depth-first-search greedy planning,and traveling-salesman-based optimization.Execution time increased only slightly and exhibited no growth in computational order.Experiments on a sugar-painting robot demonstrated that the algorithm reduced non-productive motion and improved drawing efficiency.These results indicate that the method is effective for complex graphics used in robotic drawing,additive manufacturing,and CNC machining.

       

    /

    返回文章
    返回