最佳路径规划是在优化目标的起始和目标之间找到有效状态的问题。知情路径规划算法顺序他们的搜索与特定于问题的知识表达为启发式，并且可以比未表现算法更有效的数量级。启发式最有效的是，当他们准确且计算地廉价才能评估，但这些通常是矛盾的特征。这使得适当的启发式难以满足许多问题。本文提出了两个几乎肯定的渐近最优采样的路径规划算法，以解决这一挑战，自适应地通知的树木（AIT *）和精力知的树木（EIT *）。这些算法使用非对称双向搜索，其中两个搜索彼此连续通知。这允许AIT *和EIT *通过同时计算和利用越来越准确，特定于问题的启发式来改善规划性能。 AIT *和EIT *相对于其他基于样品的算法的好处是在优化路径长度和障碍物间隙的十二个问题上进行了十二个问题。实验表明，AIT *和EIT *优于优化障碍物清除的问题的其他算法，其中先验成本启发式往往是无效的，并且仍然对最小化路径长度的问题表现良好，这种启发式通常是有效的。

多样性规划算法在单个搜索空间中找到各种不同的起点和目标之间的路径。它们旨在通过在计划查询中重复使用信息来有效地做到这一点。可以在搜索之前或期间计算此信息，并且通常包括有效路径的知识。使用已知的有效途径来解决单个计划查询要比找到全新的解决方案所花费的时间更少。这允许多算法（例如PRM*）在许多问题上胜过诸如RRT*之类的单个算法，但它们的相对性能取决于重复使用的信息。尽管如此，很少有多Qualery计划者明确地寻求最大程度地提高路径重复使用，因此，许多计划者并没有始终如一地超越单寻球替代方案。本文介绍了努力的通知路线图（EIRM*），这是一种几乎渐近的最佳多样性计划算法，明确优先考虑重复使用计算工作。 Eirm*使用非对称双向搜索来识别可能有助于解决单个计划查询的现有路径，然后使用此信息来订购其搜索并减少计算工作。这使其可以在经过测试的抽象和机器人多样性计划问题上的最新计划算法找到最高级别的初始解决方案。

双向运动规划与其单向对应物相比，平均地减少计划时间。在单次查询可行的运动规划中，使用双向搜索来查找连续运动计划需要前向和反向搜索树之间的边缘连接。这样的树木连接需要解决两点边值问题问题（BVP）。然而，两点BVP解决方案可能是困难的或不可能计算许多系统。我们提出了一种新的双向搜索策略，不需要解决两点BVP。反向树的成本信息而不是直接连接前向和反向树木，而是用作前向搜索的指导启发式。这使得前向搜索能够快速收敛到可行的解决方案而不解决两点BVP。我们提出了两个新的算法（GBRRT和GABRRT），使用此策略并使用多种动态系统和现实世界硬件实验运行多个软件模拟，以表明我们的算法表现出对现有最先进的方法进行的或更好在快速找到初始可行的解决方案时。

RRT*是一种有效的基于采样的运动计划算法。但是，在不利用可访问环境信息的优势的情况下，基于抽样的算法通常会导致抽样失败，产生无用的节点和/或失败探索狭窄的段落。对于本文，为了更好地利用环境信息并进一步提高搜索效率，我们提出了一种新颖的方法来改善RRT*通过1）量化邻居重新布线的障碍物配置的当地知识，以定向可见性，2）收集环境信息在搜索过程中，以及3）在第一个解决方案找到后，更改采样策略偏向近乎浮游节点。局部定向可见性（RRT* -LDV）提出的算法RRT*更好地利用了本地已知信息，并创新了加权采样策略。加速的RRT* -LDV在收敛率和找到狭窄段落的成功率上优于RRT*。还试验了高度自由度的场景。

基于最佳抽样的运动计划和轨迹优化是两个竞争框架，以生成最佳运动计划。这两个框架都有互补的属性：基于抽样的计划者通常会趋于趋势，但提供最佳保证。但是，轨迹优化器通常很快就可以收敛，但在非凸问题中不提供全局最佳保证，例如场景有障碍。为了达到两全其美，我们介绍了一个新的计划者Bitkomo，该计划者将渐近最佳的批处理知识树（BIT*）计划者与K-order Markov优化（KOMO）轨迹优化框架集成在一起。我们的计划者随时随地，并保持BIT*提供的相同的渐近优化性保证，同时还利用KOMO轨迹优化器的快速收敛性。我们在实验中评估了我们的计划者在涉及高维配置空间的操作场景方面，最多有两个7-DOF操纵器，障碍物和狭窄的通道。即使Komo失败，Bitkomo的表现也比Komo更好，并且在收敛到最佳解决方案方面，它的表现优于Bit*。

工业机器人操纵器（例如柯机）的应用可能需要在具有静态和非静态障碍物组合的环境中有效的在线运动计划。当可用的计算时间受到限制或无法完全产生解决方案时，现有的通用计划方法通常会产生较差的质量解决方案。我们提出了一个新的运动计划框架，旨在在用户定义的任务空间中运行，而不是机器人的工作空间，该框架有意将工作空间一般性交易，以计划和执行时间效率。我们的框架自动构建在线查询的轨迹库，类似于利用离线计算的以前方法。重要的是，我们的方法还提供了轨迹长度上有限的次级优势保证。关键的想法是建立称为$ \ epsilon $ -Gromov-Hausdorff近似值的近似异构体，以便在任务空间附近的点也很接近配置空间。这些边界关系进一步意味着可以平稳地串联轨迹，这使我们的框架能够解决批次查询方案，目的是找到最小长度的轨迹顺序，这些轨迹访问一组无序的目标。我们通过几种运动型配置评估了模拟框架，包括安装在移动基础上的操纵器。结果表明，我们的方法可实现可行的实时应用，并为扩展其功能提供了有趣的机会。

本文通过结合可允许的知情采样和本地抽样（即，对当前解决方案的邻域进行采样）来改善基于RRT*的基于采样的路径计划者的性能。一种自适应策略来说明成本进展，可调节勘探（可接受的知情抽样）和剥削（本地抽样）之间的权衡。该论文证明所得算法在渐近上是最佳的。此外，在模拟和制造案例研究中，其收敛率优于最先进的路径计划者，例如知情RRT*。还发布了开源ROS兼容的实现。

\ textit {约束路径发现}的经典问题是一个经过充分研究但充满挑战的主题，在各个领域，例如沟通和运输等各个领域的应用。权重限制了最短路径问题（WCSPP），作为仅具有一个侧面约束的约束路径查找的基本形式，旨在计划成本最佳路径，其权重/资源使用受到限制。鉴于问题的双标准性质（即处理路径的成本和权重），解决WCSPP的方法具有一些带有双目标搜索的共同属性。本文在约束路径查找和双目标搜索中利用了最新的基于A*的最新技术，并为WCSPP提供了两种精确的解决方案方法，两者都可以在非常大的图表上解决硬性问题实例。我们从经验上评估了算法在新的大型和现实的问题实例上的性能，并在时空指标中显示出它们比最新算法的优势。本文还调查了优先级队列在被a*的约束搜索中的重要性。我们通过对逼真的和随机图进行了广泛的实验来展示，基于桶的队列没有打破打盘的方式可以有效地改善详尽的双标准搜索的算法性能。

本文提出了一个基于抽样的运动计划者，该计划将RRT*（迅速探索随机树星）集成到预计运动原始图的数据库中，以减轻其计算负载，并允许在动态或部分已知的环境中进行运动计划。该数据库是通过在某些网格空间中考虑一组初始状态和最终状态对来构建的，并确定每个对与系统动力学和约束兼容的最佳轨迹，同时最小化成本。通过在网格状态空间中提取样品并在数据库中选择将其连接到现有节点的数据库中的最佳无障碍运动原始性，将节点逐渐添加到RRT*算法中可行轨迹树中的节点。如果可以通过无障碍的运动原始的原始较低的成本从新的采样状态达到一些节点，则树将重新接线。因此，运动计划的计算更密集的部分被移至数据库构建的初步离线阶段（以网格造成的某些性能退化为代价。可以对网格分辨率进行调整，以便在数据库的最优性和大小之间妥协。由于网格分辨率为零，并且采样状态的数量增长到无穷大，因此规划器被证明是渐近的最佳选择。

我们考虑针对翻译不变的动态系统的时间 - 最佳运动计划，该属性适用于许多移动机器人，例如差速器，汽车，飞机和多旋转器。我们的关键见解是，当与优化共生时，我们可以将图形搜索算法扩展到连续情况。对于图形搜索，我们引入了不连续性的A*（DB-A*），这是A*算法的概括，该算法使用了基于采样计划者的概念和数据结构。 db-a*重复使用短轨迹，所谓的运动原语作为边缘，并允许在顶点处最大的用户指定的不连续性。这些轨迹是通过轨迹优化在局部修复的，这也提供了新的改进的运动原语。我们的新型动力学运动计划者KMP-DB-A*几乎具有渐近的最佳行为，并迅速计算了近乎最佳的解决方案。对于我们的经验验证，我们提供了第一个基准，该基准测试在不同设置中的多个动态系统上比较搜索，采样和基于优化的时间 - 最佳运动计划。与基线相比，KMP-DB-A*始终求解更多的问题实例，找到较低成本的初始解决方案并更快地收敛。

在操纵器需要执行多个连续任务的环境中，对象操纵的行为将改变基础配置空间，从而影响所有后续任务。以前的免费配置现在可能被操纵的对象占据，并且以前占用的空间现在可能打开新的路径。我们提出了基于懒惰的Replanner（LTR*） - 一种新型的混合计划者，旨在继承现有的任何时间增量采样计划者的快速计划性质。同时，它允许后续任务通过懒惰的体验图来利用先前的经验。以懒惰的图结构总结了先前的经验，而Ltr*的表述是强大和有益的，无论工作空间的变化程度如何。与现有的基于路线图的规划人员相比，我们的混合方法在获得初始解决方案方面的速度更快，并且轨迹长度的成本较低。随后的任务可以利用懒惰的体验图来加快找到解决方案并利用优化图来最大程度地减少成本目标。我们提供概率完整性和几乎渐近的最佳保证的证明。在实验上，我们表明，在重复的选择任务中，LTR*在计划后续任务时的性能很高。

在本文中，提出了一种基于静态障碍的环境中实验室规模3D龙门起重机的基于抽样的轨迹计划算法，并呈现了龙门起重机系统速度和加速度的范围。重点是针对差异化系统开发快速运动计划算法，在该系统中可以存储和重复使用中间结果以进行进一步的任务，例如重新植入。所提出的方法基于知情的最佳迅速探索随机树算法（知情RRT*），该算法用于构建轨迹树，这些树在开始和/或目标状态变化时重新使用。与最先进的方法相反，拟议的运动计划算法包含了线性二次最低时间（LQTM）本地计划者。因此，在提出的算法中直接考虑了动态特性，例如时间最优性和轨迹的平滑度。此外，通过集成分支和结合方法以在轨迹树上执行修剪过程，提出的算法可以消除树中没有促成更好解决方案的点中的点。这有助于抑制记忆消耗并降低运动（RE）计划期间的计算复杂性。 3D龙门起重机的经过验证的数学模型的仿真结果显示了所提出的方法的可行性。

我们提出了一种分层骨骼引导的运动计划算法来指导移动机器人。良好的骨骼绘制了C空间子空间的连接性，该子空间包含显着的自由度，并能够引导计划者快速找到所需的解决方案。但是，有时骨骼并不能密切代表自由的C空间，这通常会误导当前的骨架引导的计划者。分层骨骼指导的计划策略逐渐放松其对工作区骨骼的依赖，因为C空间被采样，从而逐渐返回了一条次优路径，该路径在标准骨架引导的算法中无法保证。与标准骨骼指导计划者和其他懒惰计划策略的实验比较显示了路线图施工时间的显着改善，同时保持混乱环境中多电量问题的路径质量。

基于采样的运动计划者，例如RRT*和BIT*，当应用于运动动力运动计划时，依靠转向功能来生成连接采样状态的时间优势解决方案。实施精确的转向功能需要针对时间最佳控制问题的分析解决方案，或者非线性编程（NLP）求解器以鉴于系统的动力学方程式解决边界值问题。不幸的是，对于许多实际域而言，分析解决方案不可用，而NLP求解器在计算上非常昂贵，因此快速且最佳的动力动力运动计划仍然是一个开放的问题。我们通过引入状态监督转向功能（S3F）来提供解决此问题的解决方案，这是一种学习时间优势转向功能的新方法。 S3F能够比其NLP对应物更快地为转向函数的数量级产生近乎最佳的解决方案。在三个具有挑战性的机器人域进行的实验表明，使用S3F的RRT*在解决方案成本和运行时都显着优于最先进的计划方法。我们进一步提供了RRT*修改以使用S3F的概率完整性的证明。

基于采样的路径规划算法通常实现均匀的采样方法来搜索状态空间。然而，统一的采样可能导致许多情况下不必要的探索，例如具有几个死角的环境。我们以前的工作建议使用有希望的区域来指导采样过程来解决问题。然而，预测的有希望区域通常是断开连接，这意味着它们无法连接到开始和目标状态，导致缺乏概率完整性。这项工作侧重于提高预测有前途地区的连通性。我们所提出的方法在x和y方向上回归边缘的连接概率。此外，它可以计算丢失中有希望的边缘的重量，以引导神经网络更加关注有前景区域的连通性。我们进行一系列仿真实验，结果表明，有前途地区的连接性显着提高。此外，我们分析了连接基于采样的路径规划算法的影响，并得出结论，连接在维护算法性能方面发挥着重要作用。

增量图诸如D * Lite重用之前的算法，并且可能部分搜索，以加快后续路径规划任务。在本文中，我们有兴趣开发增量图搜索算法，以便寻找问题，同时优化旅行风险，到达时间等的多个目标。这是具有挑战性的，因为在多目标设置中，“帕累托 - 最优” “解决方案可以对图表的大小呈指数级增长。本文提出了一种新的多目标增量搜索算法，称为基于多目标路径的D * Lite（MOPBD *），它利用基于路径的扩展策略来修剪主导的解决方案。此外，我们介绍了MOPBD *的两个变体，以进一步提高搜索效率，并近似帕累托最优的前沿。我们在数值上评估了MOPBD *及其在各种地图中的变体的性能，其中包括两个和三个目标。结果表明，我们的方法比从头开始搜索的方法更有效，并且比多目标路径规划的现有增量方法快速升至幅度速度快。

Tendon-driven robots, where one or more tendons under tension bend and manipulate a flexible backbone, can improve minimally invasive surgeries involving difficult-to-reach regions in the human body. Planning motions safely within constrained anatomical environments requires accuracy and efficiency in shape estimation and collision checking. Tendon robots that employ arbitrarily-routed tendons can achieve complex and interesting shapes, enabling them to travel to difficult-to-reach anatomical regions. Arbitrarily-routed tendon-driven robots have unintuitive nonlinear kinematics. Therefore, we envision clinicians leveraging an assistive interactive-rate motion planner to automatically generate collision-free trajectories to clinician-specified destinations during minimally-invasive surgical procedures. Standard motion-planning techniques cannot achieve interactive-rate motion planning with the current expensive tendon robot kinematic models. In this work, we present a 3-phase motion-planning system for arbitrarily-routed tendon-driven robots with a Precompute phase, a Load phase, and a Supervisory Control phase. Our system achieves an interactive rate by developing a fast kinematic model (over 1,000 times faster than current models), a fast voxel collision method (27.6 times faster than standard methods), and leveraging a precomputed roadmap of the entire robot workspace with pre-voxelized vertices and edges. In simulated experiments, we show that our motion-planning method achieves high tip-position accuracy and generates plans at 14.8 Hz on average in a segmented collapsed lung pleural space anatomical environment. Our results show that our method is 17,700 times faster than popular off-the-shelf motion planning algorithms with standard FK and collision detection approaches. Our open-source code is available online.

基于基本快速探索随机树（RRT）的路径规划者是快速且有效的，因此有利于实时机器人路径规划，但几乎 - 肯定是次优。相反，最佳RRT（RRT *）会聚到最佳解决方案，但在实践中可能是昂贵的。最近的工作致力于加快RRT *的收敛速度。最成功的策略是通知采样，路径优化和其组合。但是，知情采样及其与路径优化的组合尚未应用于基本RRT。此外，虽然可以使用多个路径优化器来加速收敛速度，但缺乏其有效性的比较。本文调查了使用知情采样和路径优化，以基于基本RRT和RRT *加速规划者，从而导致称为已知优化的通知RRT的算法系列。我们应用不同的路径优化器并比较它们的效果。目标是确定应用知情采样和路径优化是否可以帮助快速，尽管几乎肯定地，基于基本RRT的路径规划者比RRT *基于策划者实现了可比或更好的性能。分析表明，基于RRT的优化明智的RRT可以获得比计划时间有限的RRT *基数的更好的性能，并且当有更多规划时间时。

Visual Teach and Repeat 3 (VT&R3), a generalization of stereo VT&R, achieves long-term autonomous path-following using topometric mapping and localization from a single rich sensor stream. In this paper, we improve the capabilities of a LiDAR implementation of VT&R3 to reliably detect and avoid obstacles in changing environments. Our architecture simplifies the obstacle-perception problem to that of place-dependent change detection. We then extend the behaviour of generic sample-based motion planners to better suit the teach-and-repeat problem structure by introducing a new edge-cost metric paired with a curvilinear planning space. The resulting planner generates naturally smooth paths that avoid local obstacles while minimizing lateral path deviation to best exploit prior terrain knowledge. While we use the method with VT&R, it can be generalized to suit arbitrary path-following applications. Experimental results from online run-time analysis, unit testing, and qualitative experiments on a differential drive robot show the promise of the technique for reliable long-term autonomous operation in complex unstructured environments.

传统的多代理路径规划者通常在优化单个物镜的同时计算路径的集合，例如路径长度。然而，许多应用可能需要多个目标，例如在规划期间同时优化的燃料消耗和完井时间，并且这些标准可能无法容易地进行比较，有时彼此竞争。天真地应用现有的多目标搜索算法，例如多目标A *（MoA *），以多代理路径查找可能被证明是效率低，作为可能的解决方案的空间的大小，即帕累托最优集合，可以用代理的数量（搜索空间的维度）指数增长。本文介绍了一种名为基于多目标冲突的搜索（Mo-CBS）的方法，该方法通过利用基于冲突的搜索（CBS），是单目标多代理的公知算法来绕过这种所谓的维度诅咒路径发现，以及多目标优化文献的优势原则。我们还开发了MO-CBS的几种变体，以进一步提高其性能。我们证明了MO-CBS及其变体能够计算整个帕累托最优集合。数值结果表明，Mo-CBS优于MoA *以及妈妈*，最近开发的最先进的多目标多功能策划员。