KRRF算法高效规划机器人多目标运动轨迹，兼顾路径最短与计算速度。
KRRF: Kinodynamic Rapidly-exploring Random Forest algorithm for multi-goal motion planning
- 并行生长多棵动力学树，用其他树作启发引导搜索
- 目标间路径和整体序列成本降低1.1至2倍，计算更快
- 适合复杂环境中需满足运动约束的机器人路径规划
Kinodynamic多目标运动规划问题是在未知访问顺序的情况下，为具有动力学约束的机器人在障碍物密集环境中寻找经过多个目标点的最小成本轨迹。该问题尚未被高效解决，因其结合了两个NP难问题：旅行商问题（TSP）和动力学运动规划问题。本文提出一种新型近似方法——动力学快速探索随机森林（KRRF），可生成满足机器人运动约束的无碰撞多目标轨迹。KRRF同时从各目标点向其他目标点生长动力学树，并利用其他树作为启发信息加速搜索。一旦完成目标间轨迹规划，便用其成本求解TSP以确定访问序列。最终轨迹通过基于RRT的规划器沿TSP序列中的目标间路径进行引导生成。相较于现有方法，KRRF在多数测试场景中实现更短的目标间及整体轨迹，成本降低1.1至2倍，且计算速度更快。该方法将开源发布。
原文摘要 · Abstract (English)
The problem of kinodynamic multi-goal motion planning is to find a trajectory over multiple target locations with an apriori unknown sequence of visits. The objective is to minimize the cost of the trajectory planned in a cluttered environment for a robot with a kinodynamic motion model. This problem has yet to be efficiently solved as it combines two NP-hard problems, the Traveling Salesman Problem~(TSP) and the kinodynamic motion planning problem. We propose a novel approximate method called Kinodynamic Rapidly-exploring Random Forest~(KRRF) to find a collision-free multi-goal trajectory that satisfies the motion constraints of the robot. KRRF simultaneously grows kinodynamic trees from all targets towards all other targets while using the other trees as a heuristic to boost the growth. Once the target-to-target trajectories are planned, their cost is used to solve the TSP to find the sequence of targets. The final multi-goal trajectory satisfying kinodynamic constraints is planned by guiding the RRT-based planner along the target-to-target trajectories in the TSP sequence. Compared with existing approaches, KRRF provides shorter target-to-target trajectories and final multi-goal trajectories with $1.1-2$ times lower costs while being computationally faster in most test cases. The method will be published as an open-source library.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。