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

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

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

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

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

机器人通常需要解决路径规划问题，而环境的基本和离散方面则可以观察到。这引入了多模式，机器人必须能够观察并推断其环境状态。为了解决这个问题，我们介绍了计划在信仰空间中的路径树的路径优化（PTO）算法。路径树是一种类似树状的运动，具有分支点，机器人会收到可导致信仰状态更新的观察结果。机器人取决于收到的观察结果。该算法有三个主要步骤。首先，在状态空间上生长了快速探索的随机图（RRG）。其次，通过查询观察模型，将RRG扩展到信仰空间图。在第三步中，在信仰空间图上执行动态编程以提取路径树。最终的路径树结合了探索与剥削，即它平衡了获得有关环境的知识的需求，并需要达到目标。我们在导航和移动操作任务上演示了算法功能，并在最佳和运行时使用任务和运动计划方法（TAMP）表现出比基线的优势。

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

A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two Rapidly-exploring Random Trees (RRTs) rooted at the start and the goal configurations. The trees each explore space around them and also advance towards each other through the use of a simple greedy heuristic. Although originally designed to plan motions for a human arm (modeled as a 7-DOF kinematic chain) for the automatic graphic animation of collision-free grasping and manipulation tasks, the algorithm has been successfully applied to a variety of path planning problems. Computed examples include generating collision-free motions for rigid objects in 2D and 3D, and collision-free manipulation motions for a 6-DOF PUMA arm in a 3D workspace. Some basic theoretical analysis is also presented.

混乱环境中的机器人操纵通常需要多个对象的复杂和顺序重排，以实现目标对象的所需重新配置。由于在这种情况下涉及复杂的身体互动，基于重新安排的操作仍然仅限于一小部分任务，并且尤其容易受到物理不确定性和感知噪声的影响。本文提出了一个计划框架，该框架利用了基于抽样的计划方法的效率，并通过动态控制计划范围来关闭操作循环。我们的方法交织了计划和执行，以逐步实现操纵目标，同时纠正过程中的任何错误或路径偏差。同时，我们的框架允许在不需要明确的目标配置的情况下定义操纵目标，从而使机器人能够灵活地与所有对象进行交互以促进对目标的操纵。通过在模拟和真实机器人中进行广泛的实验，我们在混乱的环境中评估了三个操纵任务的框架：抓握，重新安置和分类。与两种基线方法相比，我们表明我们的框架可以显着提高计划效率，对身体不确定性的鲁棒性以及在有限时间预算下的任务成功率。

多机器人运动计划（MRMP）是在运动动力学约束下针对在环境中作用的多个机器人的非缩进轨迹的基本问题。由于其复杂性，现有算法要么利用简化的假设或不完整。这项工作引入了基于动力学冲突的搜索（K-CB），这是一种分散的（分离）MRMP算法，是一般，可扩展性和概率完成的。该算法从成功的解决方案到MRMP的离散类似物（被称为多试路径查找（MAPF））具有灵感。具体来说，我们将基于冲突的搜索（CBS）（一种流行的分散MAPF算法）调整为MRMP设置。这种适应的新颖性是我们直接在连续领域工作，而无需离散化。特别是，动力动力学的约束在本地进行治疗。 K-CBS计划使用低级规划师分别为每个机器人计划，并通过定义单个机器人的约束来解决机器人之间的冲突树以解决机器人之间的碰撞。低水平的计划者可以是用于运动动力学机器人的任何基于采样的树搜索算法，从而将单个机器人的现有计划者提升为多机器人设置。我们表明，K-CBS继承了低级计划者的（概率）完整性。我们说明了在几个案例研究和基准测试中K-CB的一般性和性能。

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

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

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

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

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

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

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.

Rearrangement puzzles are variations of rearrangement problems in which the elements of a problem are potentially logically linked together. To efficiently solve such puzzles, we develop a motion planning approach based on a new state space that is logically factored, integrating the capabilities of the robot through factors of simultaneously manipulatable joints of an object. Based on this factored state space, we propose less-actions RRT (LA-RRT), a planner which optimizes for a low number of actions to solve a puzzle. At the core of our approach lies a new path defragmentation method, which rearranges and optimizes consecutive edges to minimize action cost. We solve six rearrangement scenarios with a Fetch robot, involving planar table puzzles and an escape room scenario. LA-RRT significantly outperforms the next best asymptotically-optimal planner by 4.01 to 6.58 times improvement in final action cost.

多步兵的操纵任务（例如打开推动的儿童瓶）需要机器人来做出各种计划选择，这些选择受到在任务期间施加力量的要求所影响的各种计划。机器人必须推荐与动作顺序相关的离散和连续选择，例如是否拾取对象以及每个动作的参数，例如如何掌握对象。为了实现计划和执行有力的操纵，我们通过限制了扭矩和摩擦限制，通过拟议的有力的运动链约束来增强现有的任务和运动计划者。在三个领域，打开一个防儿童瓶，扭动螺母并切割蔬菜，我们演示了系统如何从组合组合组合中进行选择。我们还展示了如何使用成本敏感的计划来查找强大的策略和参数物理参数的不确定性。

本文使用基于采样的方法RRT*研究，以在复杂的环境中重新配置一组连接的瓷砖，在这些环境中可能存在多个障碍。由于目标应用程序是自动构建离散的自动构建，因此使用移动机器人进行了蜂窝结构，因此有一些限制可以确定可以拾取哪些图块以及在重新配置期间可以将其放下的块。我们将我们的方法与两种算法作为全球和本地计划者进行了比较，并表明我们能够在具有不同程度的障碍空间的环境中使用合理数量的样本找到更有效的构建序列。