Lobaton Edgar, Zhang Jinghe, Patil Sachin, Alterovitz Ron
Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, USA
IEEE Int Conf Robot Autom. 2011:1463-1469. doi: 10.1109/ICRA.2011.5980446.
We present a new sampling-based method for planning optimal, collision-free, curvature-constrained paths for nonholonomic robots to visit multiple goals in any order. Rather than sampling configurations as in standard sampling-based planners, we construct a roadmap by sampling circles of constant curvature and then generating feasible transitions between the sampled circles. We provide a closed-form formula for connecting the sampled circles in 2D and generalize the approach to 3D workspaces. We then formulate the multi-goal planning problem as finding a minimum directed Steiner tree over the roadmap. Since optimally solving the multi-goal planning problem requires exponential time, we propose greedy heuristics to efficiently compute a path that visits multiple goals. We apply the planner in the context of medical needle steering where the needle tip must reach multiple goals in soft tissue, a common requirement for clinical procedures such as biopsies, drug delivery, and brachytherapy cancer treatment. We demonstrate that our multi-goal planner significantly decreases tissue that must be cut when compared to sequential execution of single-goal plans.
我们提出了一种新的基于采样的方法，用于为非完整机器人规划最优、无碰撞且曲率受限的路径，使其能够以任意顺序访问多个目标点。与标准基于采样的规划器对构型进行采样不同，我们通过对恒定曲率的圆进行采样来构建路线图，然后在采样的圆之间生成可行的过渡。我们给出了在二维空间中连接采样圆的闭式公式，并将该方法推广到三维工作空间。接着，我们将多目标规划问题表述为在路线图上寻找最小有向斯坦纳树。由于最优解决多目标规划问题需要指数时间，我们提出贪婪启发式算法来高效计算访问多个目标点的路径。我们将该规划器应用于医疗针引导的场景中，在这种场景下，针尖必须在软组织中到达多个目标点，这是活检、药物递送和近距离放射治疗癌症等临床手术的常见要求。我们证明，与单目标计划的顺序执行相比，我们的多目标规划器显著减少了必须切割的组织量。
