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

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

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

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

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

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

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

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

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

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.

多机器人系统通过整体对应物提供增强的能力，但它们以增加的协调复杂化。为了减少复杂性并使文献中的多机器人运动规划（MRMP）方法采用牺牲最优性或动态可行性的解耦方法采用解耦方法。在本文中，我们提出了一种凸起方法，即“抛物线弛豫”，为所有机器人的耦合关节空间中MRMP产生最佳和动态可行的轨迹。我们利用建议的放松来解决问题复杂性，并在极端集群环境中规划超过一百个机器人的计算途径。我们采取了一种多级优化方法，包括i）数学地配制MRMP作为非凸优化，II）将问题提升到更高的尺寸空间，III）通过所提出的计算有效的抛物线松弛和IV凸出问题。使用迭代搜索惩罚，以确保对原始问题的可行性和近最佳解决方案的可行性和恢复。我们的数值实验表明，所提出的方法能够在比最先进的成功率上具有更高成功率的挑战运动规划问题的最佳和动态可行的轨迹，但在高度密集的环境中，在一百个机器人中仍然在计算上仍然在计算上。 。

在本文中，我们通过概率保证解决了基于采样的运动计划和测量不确定性的问题。我们概括了基于基于树的基于树木的运动计划算法，以确定性系统并提出信念-USHAMCAL {a} $，该框架将任何基于动力学的树的计划者扩展到线性（或可线化）系统的信念空间。我们为信仰空间介绍了适当的抽样技术和距离指标，以保留基础规划师的概率完整性和渐近最佳性能。我们证明了我们在模拟方面对自动化和非全面系统有效和渐近地找到安全低成本路径的疗效。

本文着重于影响弹性的移动机器人的碰撞运动计划和控制的新兴范式转移，并开发了一个统一的层次结构框架，用于在未知和部分观察的杂物空间中导航。在较低级别上，我们开发了一种变形恢复控制和轨迹重新启动策略，该策略处理可能在本地运行时发生的碰撞。低级系统会积极检测碰撞（通过内部内置的移动机器人上的嵌入式霍尔效应传感器），使机器人能够从其内部恢复，并在本地调整后影响后的轨迹。然后，在高层，我们提出了一种基于搜索的计划算法，以确定如何最好地利用潜在的碰撞来改善某些指标，例如控制能量和计算时间。我们的方法建立在A*带有跳跃点的基础上。我们生成了一种新颖的启发式功能，并进行了碰撞检查和调整技术，从而使A*算法通过利用和利用可能的碰撞来更快地收敛到达目标。通过将全局A*算法和局部变形恢复和重新融合策略以及该框架的各个组件相结合而生成的整体分层框架在模拟和实验中都经过了广泛的测试。一项消融研究借鉴了与基于搜索的最先进的避免碰撞计划者（用于整体框架）的链接，以及基于搜索的避免碰撞和基于采样的碰撞 - 碰撞 - 全球规划师（对于更高的较高的碰撞 - 等级）。结果证明了我们的方法在未知环境中具有碰撞的运动计划和控制的功效，在2D中运行的一类撞击弹性机器人具有孤立的障碍物。

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

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

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.

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.

在这项工作中，我们提出了一个基于工作空间的计划框架，尽管它使用冗余工作空间密钥点代表机器人状态，但可以利用可解释的几何信息，从而为复杂的机器人提供高质量的无碰撞路径。使用工作空间几何形状，我们首先找到每个钥匙点的无碰撞线性路径，以便在每个段的端点上，在密钥点之间满足距离约束。使用这些零件线性路径作为初始条件，我们可以执行优化步骤，以快速找到满足各种约束并将所有段组合在一起以获得有效路径的路径。我们表明，这些调整后的路径不太可能造成碰撞，并且建议的方法很快，可以产生良好的效果。

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

Robotic planning in real-world scenarios typically requires joint optimization of logic and continuous variables. A core challenge to combine the strengths of logic planners and continuous solvers is the design of an efficient interface that informs the logical search about continuous infeasibilities. In this paper we present a novel iterative algorithm that connects logic planning with nonlinear optimization through a bidirectional interface, achieved by the detection of minimal subsets of nonlinear constraints that are infeasible. The algorithm continuously builds a database of graphs that represent (in)feasible subsets of continuous variables and constraints, and encodes this knowledge in the logical description. As a foundation for this algorithm, we introduce Planning with Nonlinear Transition Constraints (PNTC), a novel planning formulation that clarifies the exact assumptions our algorithm requires and can be applied to model Task and Motion Planning (TAMP) efficiently. Our experimental results show that our framework significantly outperforms alternative optimization-based approaches for TAMP.