Genetic Informed Trees (GIT*): Path Planning via Reinforced Genetic Programming Heuristics
作者: Liding Zhang, Kuanqi Cai, Zhenshan Bing, Chaoqun Wang, Alois Knoll
分类: cs.RO
发布日期: 2025-08-28
期刊: Biomimetic Intelligence and Robotics 2025
DOI: 10.1016/j.birob.2025.100237
💡 一句话要点
提出GIT*算法，利用强化遗传规划优化启发式函数，提升高维空间路径规划效率。
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 路径规划 启发式函数 遗传规划 强化学习 机器人导航
📋 核心要点
- 现有路径规划方法在复杂环境中，由于忽略环境信息和简化启发式函数结构，导致搜索效率和解的质量受限。
- GIT*算法通过整合环境数据（如斥力和顶点重要性）优化启发式函数，并利用强化遗传规划（RGP）自动进化启发式函数。
- 实验结果表明，GIT*在高维空间（R^4到R^16）的路径规划问题中，优于现有的单查询、基于采样的规划器，并在真实机器人操作任务中验证。
📝 摘要（中文）
最优路径规划旨在寻找起始状态和目标状态之间可行的状态序列，并优化目标函数。该过程依赖于启发式函数来指导搜索方向。然而，现有方法通常忽略可用的环境数据，并由于信息关系的复杂性而简化函数结构。本研究提出了遗传信息树（GIT），它通过整合更广泛的环境数据（如来自障碍物的斥力和顶点的动态重要性）来改进努力信息树（EIT），从而优化启发式函数以获得更好的指导。此外，我们集成了强化遗传规划（RGP），它将遗传规划与奖励系统反馈相结合，以突变GIT的基因型生成启发式函数。RGP利用多种数据类型，从而在设定的时间内提高计算效率和解决方案质量。对比分析表明，在R^4到R^16的问题中，GIT超越了现有的单查询、基于采样的规划器，并在真实的移动操作任务中进行了测试。
🔬 方法详解
问题定义：论文旨在解决高维空间中路径规划问题，现有方法的痛点在于启发式函数设计不足，无法充分利用环境信息，导致搜索效率低下，解的质量不高。传统方法要么忽略环境数据，要么过度简化启发式函数结构，难以适应复杂环境。
核心思路：论文的核心思路是利用遗传规划自动搜索和优化启发式函数。通过整合更丰富的环境信息（如障碍物斥力、顶点动态重要性）到启发式函数中，并结合强化学习的奖励机制，引导遗传规划朝着更有效的方向进化，从而提升路径规划的效率和质量。
技术框架：GIT算法基于EIT算法框架，主要包含以下几个模块：1) 环境信息提取模块：提取障碍物斥力、顶点动态重要性等环境信息。2) 启发式函数生成模块：利用遗传规划生成候选的启发式函数。3) 路径搜索模块：使用EIT*算法进行路径搜索，并评估启发式函数的性能。4) 强化遗传规划模块：根据路径搜索结果，利用奖励机制对启发式函数进行选择、交叉和变异，迭代优化启发式函数。
关键创新：最重要的技术创新点是强化遗传规划（RGP）在启发式函数优化中的应用。RGP将遗传规划与强化学习相结合，通过奖励机制引导遗传规划朝着更有效的方向进化。与传统的遗传规划相比，RGP能够更有效地利用环境信息，生成更优的启发式函数。与手动设计的启发式函数相比，RGP能够自动适应不同的环境，具有更强的泛化能力。
关键设计：RGP的关键设计包括：1) 基因型编码：使用树结构表示启发式函数，树的节点可以是环境信息、算术运算符等。2) 适应度函数：使用路径长度、搜索时间等指标评估启发式函数的性能，并将其作为奖励信号。3) 遗传算子：使用选择、交叉和变异等遗传算子对基因型进行操作，生成新的启发式函数。4) 奖励机制：根据路径搜索结果，对启发式函数进行奖励或惩罚，引导遗传规划朝着更有效的方向进化。
🖼️ 关键图片
📊 实验亮点
实验结果表明，GIT算法在高维空间（R^4到R^16）的路径规划问题中，优于现有的单查询、基于采样的规划器。具体来说，GIT在搜索时间和路径长度方面均有显著提升。此外，GIT*还在真实的移动操作任务中进行了测试，验证了其在实际应用中的有效性。实验视频可在https://youtu.be/URjXbc_BiYg 观看。
🎯 应用场景
该研究成果可应用于机器人导航、游戏AI、自动驾驶等领域。通过自动优化启发式函数，可以提升机器人在复杂环境中的路径规划能力，使其能够更快速、更安全地到达目标位置。此外，该方法还可以应用于其他优化问题，例如资源分配、任务调度等。
📄 摘要（原文）
Optimal path planning involves finding a feasible state sequence between a start and a goal that optimizes an objective. This process relies on heuristic functions to guide the search direction. While a robust function can improve search efficiency and solution quality, current methods often overlook available environmental data and simplify the function structure due to the complexity of information relationships. This study introduces Genetic Informed Trees (GIT), which improves upon Effort Informed Trees (EIT) by integrating a wider array of environmental data, such as repulsive forces from obstacles and the dynamic importance of vertices, to refine heuristic functions for better guidance. Furthermore, we integrated reinforced genetic programming (RGP), which combines genetic programming with reward system feedback to mutate genotype-generative heuristic functions for GIT. RGP leverages a multitude of data types, thereby improving computational efficiency and solution quality within a set timeframe. Comparative analyses demonstrate that GIT surpasses existing single-query, sampling-based planners in problems ranging from R^4 to R^16 and was tested on a real-world mobile manipulation task. A video showcasing our experimental results is available at https://youtu.be/URjXbc_BiYg