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

嘈杂的传感，不完美的控制和环境变化是许多现实世界机器人任务的定义特征。部分可观察到的马尔可夫决策过程（POMDP）提供了一个原则上的数学框架，用于建模和解决不确定性下的机器人决策和控制任务。在过去的十年中，它看到了许多成功的应用程序，涵盖了本地化和导航，搜索和跟踪，自动驾驶，多机器人系统，操纵和人类机器人交互。这项调查旨在弥合POMDP模型的开发与算法之间的差距，以及针对另一端的不同机器人决策任务的应用。它分析了这些任务的特征，并将它们与POMDP框架的数学和算法属性联系起来，以进行有效的建模和解决方案。对于从业者来说，调查提供了一些关键任务特征，以决定何时以及如何成功地将POMDP应用于机器人任务。对于POMDP算法设计师，该调查为将POMDP应用于机器人系统的独特挑战提供了新的见解，并指出了有希望的新方向进行进一步研究。

本文在具有部分未知语义的环境中解决了多机器人规划问题。假设环境具有已知的几何结构（例如，墙壁），并且由具有不确定位置和类的静态标记的地标占用。这种建模方法引发了语义SLAM算法生成的不确定语义地图。我们的目标是为配备有嘈杂感知系统的机器人设计控制策略，以便他们可以完成全局时间逻辑规范捕获的协同任务。为了指定考虑环境和感知不确定性的任务，我们采用了线性时间逻辑（LTL）的片段，称为CO-Safe LTL，定义了基于感知的原子谓性建模概率满意度要求。基于感知的LTL规划问题产生了通过新型采样的算法解决的最佳控制问题，它产生了在线更新的开环控制策略，以适应连续学习的语义地图。我们提供广泛的实验，以证明拟议的规划架构的效率。

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

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.

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

We propose a path planning methodology for a mobile robot navigating through an obstacle-filled environment to generate a reference path that is traceable with moderate sensing efforts. The desired reference path is characterized as the shortest path in an obstacle-filled Gaussian belief manifold equipped with a novel information-geometric distance function. The distance function we introduce is shown to be an asymmetric quasi-pseudometric and can be interpreted as the minimum information gain required to steer the Gaussian belief. An RRT*-based numerical solution algorithm is presented to solve the formulated shortest-path problem. To gain insight into the asymptotic optimality of the proposed algorithm, we show that the considered path length function is continuous with respect to the topology of total variation. Simulation results demonstrate that the proposed method is effective in various robot navigation scenarios to reduce sensing costs, such as the required frequency of sensor measurements and the number of sensors that must be operated simultaneously.

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

行为树（BT）是一种在自主代理中（例如机器人或计算机游戏中的虚拟实体）之间在不同任务之间进行切换的方法。 BT是创建模块化和反应性的复杂系统的一种非常有效的方法。这些属性在许多应用中至关重要，这导致BT从计算机游戏编程到AI和机器人技术的许多分支。在本书中，我们将首先对BTS进行介绍，然后我们描述BTS与早期切换结构的关系，并且在许多情况下如何概括。然后，这些想法被用作一套高效且易于使用的设计原理的基础。安全性，鲁棒性和效率等属性对于自主系统很重要，我们描述了一套使用BTS的状态空间描述正式分析这些系统的工具。借助新的分析工具，我们可以对BTS如何推广早期方法的形式形式化。我们还显示了BTS在自动化计划和机器学习中的使用。最后，我们描述了一组扩展的工具，以捕获随机BT的行为，其中动作的结果由概率描述。这些工具可以计算成功概率和完成时间。

路径计划是设计机器人行为的关键算法方法。基于抽样的方法，例如快速探索随机树（RRT）或概率路线图，是针对路径计划问题的突出算法解决方案。尽管其指数收敛速率，RRT只能找到次优路径。另一方面，$ \ textrm {rrt}^*$是RRT广泛​​使用的扩展名，保证了寻找最佳路径的概率完整性，但在复杂环境中缓慢收敛而在实践中遭受痛苦。此外，现实世界中的机器人环境通常是可观察到的，或者描述的动力学不好，施放了$ \ textrm {rrt}^*$在复杂任务中的应用。本文研究了用于机器人路径计划的流行蒙特卡洛树搜索（MCTS）算法的新型算法公式。值得注意的是，我们通过分析和证明其指数的收敛速率（MCPP）在完全可观察到的马尔可夫决策过程（MDP）的一部分中，并证明其指数收敛速率，而另一部分则是其概率的完整性假设有限的距离可观察性（证明草图），在部分可观察的MDP（POMDP）中找到可行的路径。我们的算法贡献使我们能够采用最近提出的MCT的变体，并具有不同的勘探策略来进行机器人路径计划。我们在模拟的2D和3D环境中进行了7度自由度（DOF）操纵器以及现实世界机器人路径计划任务中的实验评估，证明了MCPP在POMDP任务中的优势。

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

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

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

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

本文解决了不确定和动态环境中的新语义多机器人计划问题。特别是，环境被不合作，移动，不确定的标记目标占据。这些目标受随机动力学的控制，而它们的当前和未来位置及其语义标签尚不确定。我们的目标是控制移动传感机器人，以便他们可以完成根据这些目标的当前/未来位置和标签定义的协作语义任务。我们使用线性时间逻辑（LTL）表达这些任务。我们提出了一种基于抽样的方法，该方法探讨了机器人运动空间，任务规范空间以及标记目标的未来配置，以设计最佳路径。这些路径在线修订以适应不确定的感知反馈。据我们所知，这是解决不确定和动态语义环境中语义任务计划问题的第一项工作。我们提供了广泛的实验，以证明该方法的效率

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

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

Representing and reasoning about uncertainty is crucial for autonomous agents acting in partially observable environments with noisy sensors. Partially observable Markov decision processes (POMDPs) serve as a general framework for representing problems in which uncertainty is an important factor. Online sample-based POMDP methods have emerged as efficient approaches to solving large POMDPs and have been shown to extend to continuous domains. However, these solutions struggle to find long-horizon plans in problems with significant uncertainty. Exploration heuristics can help guide planning, but many real-world settings contain significant task-irrelevant uncertainty that might distract from the task objective. In this paper, we propose STRUG, an online POMDP solver capable of handling domains that require long-horizon planning with significant task-relevant and task-irrelevant uncertainty. We demonstrate our solution on several temporally extended versions of toy POMDP problems as well as robotic manipulation of articulated objects using a neural perception frontend to construct a distribution of possible models. Our results show that STRUG outperforms the current sample-based online POMDP solvers on several tasks.

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

有效计划的能力对于生物体和人造系统都是至关重要的。在认知神经科学和人工智能（AI）中广泛研究了基于模型的计划和假期，但是从不同的角度来看，以及难以调和的考虑（生物现实主义与可伸缩性）的不同意见（生物现实主义与可伸缩性）。在这里，我们介绍了一种新颖的方法来计划大型POMDP（Active Tree search（ACT）），该方法结合了神经科学中领先的计划理论的规范性特征和生物学现实主义（主动推论）和树木搜索方法的可扩展性AI。这种统一对两种方法都是有益的。一方面，使用树搜索可以使生物学接地的第一原理，主动推断的方法可应用于大规模问题。另一方面，主动推理为探索 - 开发困境提供了一种原则性的解决方案，该解决方案通常在树搜索方法中以启发性解决。我们的模拟表明，ACT成功地浏览了对基于抽样的方法，需要自适应探索的问题以及大型POMDP问题“ RockSample”的二进制树，其中ACT近似于最新的POMDP解决方案。此外，我们说明了如何使用ACT来模拟人类和其他解决大型计划问题的人类和其他动物的神经生理反应（例如，在海马和前额叶皮层）。这些数值分析表明，主动树搜索是神经科学和AI计划理论的原则性实现，既具有生物现实主义和可扩展性。