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

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

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.

我们从理论和算法的观点正式化和研究多目标任务分配和路径发现（MG-TAPF）问题。MG-TAPF问题是要计算到代理的任务分配，每个任务都由一系列目标位置组成，并为代理的无碰撞路径组成，这些代理商访问其分配任务的所有目标位置。从理论上讲，我们证明MG-TAPF问题是最佳解决的NP问题。我们提出算法，这些算法基于用于多代理路径的算法技术，发现问题并最佳地解决MG-TAPF问题。我们通过实验将这些算法在各种不同的基准域上进行比较。

多试路径查找（MAPF）是人工智能中的一个活跃领域，它具有许多真实的应用程序，例如仓库管理，交通控制，机器人技术等。最近，M*及其变体大大提高了解决该问题的能力MAPF问题。尽管在这些方法中使用的优异扩展显着降低了关节搜索空间的维度并降低了分支因子，但它们并不能充分利用每个代理的最佳路径的可能性非唯一性。结果，碰撞集的更新可能会带来大量冗余计算。在本文中，旁路的想法被引入细分扩展中，以减少冗余计算。具体而言，我们提出了BPM*算法，该算法是M*中旁路的细分扩展的实现。在实验中，我们表明BPM*在解决几个MAPF基准问题方面胜过最先进的问题。

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

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

在多代理路径查找（MAPF）问题中，一组在图表上移动的代理必须达到其自身各自的目的地，而无需间间冲突。在实用的MAPF应用中，如自动仓库导航，偶尔有数百个或更多代理商，MAPF必须在终身基础上迭代地解决。这种情景排除了离线计算密集型最佳方法的简单调整;因此，可扩展的子最优算法用于此类设置。理想的可扩展算法适用于可预测计算时间的迭代方案和输出合理的解决方案。对于上述目的，在本研究中，提出了一种具有回溯（PIBT）的优先级继承的新型算法以迭代地解决MAPF。 PIBT依赖于适应性优先级方案，专注于多个代理的相邻运动;因此它可以应用于若干域。我们证明，无论其数量如何，当环境是图形时，所有代理都保证在有限的时间内达到目的地，使得所有相邻节点属于一个简单的周期（例如，双绞线）。实验结果涵盖了各种场景，包括真正的机器人演示，揭示了所提出的方法的好处。即使用数百种代理商，PIBT也会立即产生可接受的解决方案，可以解决其他事实上MAPF方法的大型情况。此外，PIBT在运行时和解决方案质量的自动化仓库中的传送包中的迭代方案上占据了现有方法。

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

Multi-agent path finding (MAPF) is a task of finding non-conflicting paths connecting agents' specified initial and goal positions in a shared environment. We focus on compilation-based solvers in which the MAPF problem is expressed in a different well established formalism such as mixed-integer linear programming (MILP), Boolean satisfiability (SAT), or constraint programming (CP). As the target solvers for these formalisms act as black-boxes it is challenging to integrate MAPF specific heuristics in the MAPF compilation-based solvers. We show in this work how the build a MAPF encoding for the target SAT solver in which domain specific heuristic knowledge is reflected. The heuristic knowledge is transferred to the SAT solver by selecting candidate paths for each agent and by constructing the encoding only for these candidate paths instead of constructing the encoding for all possible paths for an agent. The conducted experiments show that heuristically guided compilation outperforms the vanilla variants of the SAT-based MAPF solver.

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

在这项工作中，我们考虑了多代理拾取和交付（MAPD）问题，在该问题中，代理商不断参与新任务，并需要计划无碰撞的路径以执行它们。要执行任务，代理需要访问由接送位置和交货位置组成的两对目标位置。我们提出了两种算法的变体，该变体使用Anytime Algorithm大型邻域搜索（LNS）为每个代理分配一系列任务，并使用多代理路径查找（MAPF）基于算法优先级搜索（PBS）计划路径。 LNS-PBS已完善，用于良好的MAPD实例，MAPD实例的现实子类，并且比现有完整的MAPD算法中央更有效。 LNS-WPBS没有提供完整的保证，但在经验上比LNS-PBS更高效和稳定。它扩展到大型仓库中数千名代理商和数千个任务，并且在经验上比现有的可伸缩MAPD算法HBH+MLA*更有效。 LNS-PBS和LNS-WPB也适用于MAPD的更一般变体，即多目标MAPD（MG-MAPD）问题，其中任务可以具有不同数量的目标位置。

基于冲突的搜索（CBS）是一种流行的多试路径查找（MAPF）求解器，该求解器采用低级单位代理计划者和高级约束树来解决冲突。绝大多数现代MAPF求解器都专注于通过各种策略减少这棵树的大小来改善CB，几乎没有修改低级计划者的方法。现有CBS方法中的所有低级计划者都使用未加权的启发式启发式方法，次优的CBS方法还使用冲突启发式启发式启发式来帮助高级搜索。与普遍的信念相反，我们表明，通过以特定方式加权冲突，可以更有效地使用启发式成本的启发式。我们介绍了这样做的两个变体，并证明这种变化在某些情况下可以导致2-100倍的加速。此外，据我们所知，我们展示了优先规划和有限的次优的CB的第一个理论关系，并证明我们的方法是它们的自然概括。

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

本文为多代理系统开发了一个随机编程框架，在该系统中，任务分解，分配和调度问题同时被优化。该框架可以应用于具有分布式子任务的异质移动机器人团队。例子包括大流行机器人服务协调，探索和救援以及具有异质车辆的交付系统。由于其固有的灵活性和鲁棒性，多代理系统被应用于越来越多的现实问题，涉及异质任务和不确定信息。大多数以前的作品都采用一种将任务分解为角色的独特方法，以后可以将任务分配给代理。对于角色可以变化并且存在多个分解结构的复杂任务，此假设无效。同时，尚不清楚如何在多代理系统设置下系统地量化和优化任务要求和代理能力中的不确定性。提出了复杂任务的表示形式：代理功能表示为随机分布的向量，任务要求通过可推广的二进制函数验证。在目标函数中选择有风险的条件值（CVAR）作为制定强大计划的度量。描述了一种有效的算法来解决该模型，并在两个不同的实践案例中评估了整个框架：在大流行期间的捕获量和机器人服务协调（例如，Covid-19）。结果表明，该框架是可扩展的，可扩展到示例案例的140个代理和40个任务，并提供了低成本计划，以确保成功的概率很高。

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

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

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.

审查多个机器人的无碰撞路径的目的对于现实世界多机器人系统很重要，并且已被研究为在图形上的优化问题，称为多代理路径查找（MAPF）。这篇评论调查了不同类别的经典和最先进的MAPF算法，并进行了不同的研究尝试，以应对将MAPF技术推广到现实世界情景的挑战。最新的发现解决MAPF问题是在计算上具有挑战性的。最近的进步导致了MAPF算法，该算法可以在运行时计算数百个机器人和数千个导航任务的无碰撞路径。 MAPF的许多变体已被正式化，以使MAPF技术适应不同的现实需求，例如机器人运动学的考虑，实时系统的在线优化以及任务分配和路径计划的集成。用于MAPF问题的摘要算法技术已经解决了多个多机器人应用程序的重要方面，包括自动仓库履行和分类，自动化火车调度以及非独立机器人和四轮驱动器的导航。这展示了它们在大型多机器人系统的现实应用中的潜力。

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