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

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

The Multi-Objective Shortest Path Problem, typically posed on a graph, determines a set of paths from a start vertex to a destination vertex while optimizing multiple objectives. In general, there does not exist a single solution path that can simultaneously optimize all the objectives and the problem thus seeks to find a set of so-called Pareto-optimal solutions. To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees. However, these MOA* algorithms often suffer from high memory usage, especially when the branching factor (i.e., the number of neighbors of any vertex) of the graph is large. This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime. In this paper, we first extend the notion of "partial expansion" (PE) from single-objective to multi-objective and then fuse this new PE technique with EMOA*, a recent runtime efficient MOA* algorithm. Furthermore, the resulting algorithm PE-EMOA* can balance between runtime and memory efficiency by tuning a user-defined hyper-parameter.

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

在不同情况下，机器人有可能执行搜索各种应用程序。我们的工作是由人道主义助理和灾难救济（HADR）激发的，在存在冲突的标准，目标和信息的情况下，找到生命的迹象通常至关重要。我们认为，厄运搜索可以提供一个框架来利用可用信息，并为HADR等应用程序探索新信息，尤其是在时间本质上。千古搜索算法规划轨迹，使得在一个地区所花费的时间与该地区的信息量成正比，并且能够自然平衡剥削（近视搜索高信息搜索区域）和探索（访问搜索空间的所有位置以获取新的信息）。现有的Ergodic搜索算法以及其他基于信息的方法通常仅使用单个信息图考虑搜索。但是，在许多情况下，使用多个编码不同类型相关信息的多个信息图很常见。当前的厄运搜索方法没有同时的能力，也不具有平衡信息优先级的方法。这使我们提出了一个多目标的千古搜索（MOES）问题，旨在找到所谓的帕累托最佳解决方案，目的是为人类的决策者提供各种解决方案，这些解决方案在相互矛盾的标准之间进行贸易。为了有效地解决MOE，我们开发了一个称为顺序局部Ergodic搜索（SLE）的框架，该框架将MOES问题转换为“重量空间覆盖率”问题。它利用了厄隆搜索方法的最新进展以及局部优化的想法，以有效地近似帕累托最佳前沿。我们的数值结果表明，SLE的运行速度明显快于基线方法。

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

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

本文提出了一种有效的算法来解决$ k $最短的非副总体路径计划（$ k $ -snpp）问题。通过加速对2D环境的同拷贝增强空间的效率低下的探索，我们的基本思想是尽早确定非最佳路径拓扑，并终止沿它们的路径。这是一种非平凡的做法，因为当局部最短路径尚未完全构造时，必须在路径计划过程的中间状态下完成。换句话说，要比较的路径尚未在目标位置上进行划分，这使得同义理论，对具有相同端点的路径之间的空间关系建模，而不是适用。本文是开发基于系统的基于距离的拓扑简化机制来解决$ k $ -SNPP任务的第一份工作，其核心贡献是在构造它们之前主张基于距离的本地最短路径的基于距离的顺序。如果可以预测该订单，则证明具有超过$ K $的那些路径拓扑被证明没有所需的$ K $路径，因此可以在路径计划过程中安全丢弃。为此，提出了一棵层次拓扑树作为该机制的实现，其节点被证明可以在非副主导方向和边缘（无碰撞路径段）中扩展，在局部最短。有了有效的标准，可以观察到将部分构造的本地最短路径之间的顺序关系赋予树，将不会扩展以非 - $ k $最佳拓扑扩展的树节点。结果，解决$ K $ -SNPP问题的计算时间减少了两个数量级。

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

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

多路径定向问题询问机器人团队的路径最大化收集的总奖励，同时满足路径长度上的预算约束。这个问题模拟了许多多机器人路由任务，例如探索未知的环境和环境监控信息。在本文中，我们专注于如何使机器人团队在对抗环境中运行时对故障的强大。我们介绍了强大的多路径定向事问题（RMOP），在那里我们寻求最糟糕的案例保证，反对能够在大多数$ \ Alpha $机器人处攻击的对手。我们考虑两个问题的两个版本：RMOP离线和RMOP在线。在离线版本中，当机器人执行其计划时，没有通信或重新扫描，我们的主要贡献是一种具有界限近似保证的一般近似方案，其取决于$ \ alpha $和单个机器人导向的近似因子。特别是，我们表明该算法在成本函数是模块化时产生（i）恒因子近似; （ii）在成本函数是子模具时，$ \ log $因子近似; （iii）当成本函数是子模块时的恒因子近似，但是允许机器人通过有界金额超过其路径预算。在在线版本中，RMOP被建模为双人顺序游戏，并基于蒙特卡罗树搜索（MCT），以后退地平线方式自适应解决。除了理论分析之外，我们还对海洋监测和隧道信息收集应用进行仿真研究，以证明我们的方法的功效。

Despite recent progress on trajectory planning of multiple robots and path planning of a single tethered robot, planning of multiple tethered robots to reach their individual targets without entanglements remains a challenging problem. In this paper, we present a complete approach to address this problem. Firstly, we propose a multi-robot tether-aware representation of homotopy, using which we can efficiently evaluate the feasibility and safety of a potential path in terms of (1) the cable length required to reach a target following the path, and (2) the risk of entanglements with the cables of other robots. Then, the proposed representation is applied in a decentralized and online planning framework that includes a graph-based kinodynamic trajectory finder and an optimization-based trajectory refinement, to generate entanglement-free, collision-free and dynamically feasible trajectories. The efficiency of the proposed homotopy representation is compared against existing single and multiple tethered robot planning approaches. Simulations with up to 8 UAVs show the effectiveness of the approach in entanglement prevention and its real-time capabilities. Flight experiments using 3 tethered UAVs verify the practicality of the presented approach.

在许多环境监测方案中，采样机器人需要同时探索环境和利用有限时间利用感兴趣的特征。我们介绍了一个名为Pareto Monte Carlo树搜索的多目标信息规划方法，该方法允许机器人处理潜在的竞争目标，例如勘探与剥削。该方法基于环境状态的知识（估计）为机器人产生了优化的决策解决方案，从而更好地适应环境动态。我们在关键树节点选择步骤提供算法分析，并显示选择子最优节点的次数是对数界限的，并且搜索结果以多项式率收敛到最佳选择。

对于一个合作探索未知环境的多机器人团队，至关重要的是，收集的信息可以在机器人之间有效共享，以支持勘探和导航任务。无线通道的实际限制（例如有限的带宽和位率）敦促机器人仔细选择要传输的信息。在本文中，我们考虑了使用3D场景图对环境信息进行建模的情况，这是一个层次模型，描述了环境的几何和语义方面。然后，我们利用图理论工具，即图形跨度，以设计有效压缩3D场景图的启发式策略，以在带宽约束下启用通信。我们的压缩策略以导航为导向，因为它们旨在在感兴趣的位置之间近乎保留最短的路径，同时满足用户指定的通信预算约束。通过广泛的数值分析和现实模拟器中的合成实验证明了所提出的算法的有效性。

在以并发方式解决团队范围的任务时，多机构系统可能非常有效。但是，如果没有正确的同步，则很难保证合并行为的正确性，例如遵循子任务的特定顺序或同时进行协作。这项工作解决了在复杂的全球任务下，将最低时间的任务计划问题称为线性时间逻辑（LTL）公式。这些任务包括独立本地动作和直接子团队合作的时间和空间要求。提出的解决方案是一种随时随地的算法，结合了对任务分解的基础任务自动机的部分顺序分析，以及用于任务分配的分支和绑定（BNB）搜索方法。提供最小的完成时间的合理性，完整性和最佳性分析。还表明，在搜索范围内持续在时间预算之内，可以迅速达成可行且近乎最佳的解决方案。此外，为了处理在线执行期间任务持续时间和代理失败的波动，提出了适应算法来同步执行状态并动态地重新分配未完成的子任务以保持正确性和最佳性。两种算法通过数值模拟和硬件实验在大规模系统上进行了严格的验证，该算法对几个强基地进行了验证。

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

基于冲突的搜索（CBS）是一种广泛使用的算法，用于最佳地求解多代理探路（MAPF）问题。 CBS的核心思想是运行层次搜索，当在高级别的解决方案树上探索候选者的树时，在低级别上进行了针对特定代理的个人计划（受某些约束）进行。为了使运行时间的权衡取得最佳性，设计了有限的子最佳CB的不同变体，这改变了CBS的高级和低级搜索程序。此外，CBS的任何时间变体都存在将焦点搜索（FS）应用于CBS的高级搜索 - 任何时间BCB。然而，当我们简单地重新启动cbs的cbs与较低的亚XB绑定时，没有对这种算法的性能的全面分析。这项工作旨在填补这一空白。此外，我们介绍并评估了另一个在CBS上使用FS的CBS的随时随地。从经验上讲，我们证明其行为主要与任何时间BCB所证明的行为不同。最后，我们比较这两种算法从头开始，并表明在两个级别的CBS上使用焦点搜索在广泛的设置中可能是有益的。

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

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

这篇简短的评论旨在使读者熟悉与计划，调度和学习有关的最新作品。首先，我们研究最先进的计划算法。我们简要介绍神经网络。然后，我们更详细地探索图形神经网络，这是一种适合处理图形结构输入的神经网络的最新变体。我们简要描述了强化学习算法和迄今为止设计的一些方法的概念。接下来，我们研究了一些成功的方法，结合了用于路径规划的神经网络。最后，我们专注于不确定性的时间计划问题。