复杂的多目标任务需要在多个相互连接的级别（例如联盟形成，调度和运动计划）上协调异质机器人。动态变化（例如传感器和执行器故障，通信损失和意外延迟）加剧了这一挑战。我们将动态迭代任务分配图搜索（D-ITAGS）介绍到\ textit {同时}地址在涉及异构团队的动态设置中，地址为联盟组建，调度和运动计划。 D-Itag通过两个关键特征实现弹性：i）交错执行，ii）有针对性的维修。 \ textIt {交错执行}可以在每一层进行有效搜索解决方案，同时避免与其他层不兼容。 \ textIt {目标修复}识别并修复了现有解决方案的一部分，该解决方案在保存其余部分的同时受到给定破坏的影响。除了算法贡献外，我们还提供理论上的见解，以了解这些设置中时间和资源最优性之间固有的权衡，并在计划次级临时性上得出有意义的界限。我们的实验表明，在动态设置中，i）d-itag的速度明显比从头开始的重新计算要快得多，而溶液质量几乎没有损失，ii）理论次优界在实践中始终保持。

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

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

我们为多机器人任务计划和分配问题提出了一种新的公式，该公式结合了（a）任务之间的优先关系； （b）任务的协调，允许多个机器人提高效率； （c）通过形成机器人联盟的任务合作，而单独的机器人不能执行。在我们的公式中，任务图指定任务和任务之间的关系。我们在任务图的节点和边缘上定义了一组奖励函数。这些功能对机器人联盟规模对任务绩效的影响进行建模，并结合一个任务的性能对依赖任务的影响。最佳解决此问题是NP-HARD。但是，使用任务图公式使我们能够利用最小成本的网络流量方法有效地获得近似解决方案。此外，我们还探索了一种混合整数编程方法，该方法为问题的小实例提供了最佳的解决方案，但计算上很昂贵。我们还开发了一种贪婪的启发式算法作为基准。我们的建模和解决方案方法导致任务计划，即使在与许多代理商的大型任务中，也利用任务优先关系的关系以及机器人的协调和合作来实现高级任务绩效。

This paper presents a learning framework to estimate an agent capability and task requirement model for multi-agent task allocation. With a set of team configurations and the corresponding task performances as the training data, linear task constraints can be learned to be embedded in many existing optimization-based task allocation frameworks. Comprehensive computational evaluations are conducted to test the scalability and prediction accuracy of the learning framework with a limited number of team configurations and performance pairs. A ROS and Gazebo-based simulation environment is developed to validate the proposed requirements learning and task allocation framework in practical multi-agent exploration and manipulation tasks. Results show that the learning process for scenarios with 40 tasks and 6 types of agents uses around 12 seconds, ending up with prediction errors in the range of 0.5-2%.

使用团队或机器人联盟的任务分配是机器人技术，计算机科学，运营研究和人工智能中最重要的问题之一。在最近的工作中，研究集中在处理复杂的目标和可行性限制之间，这是多机器人任务分配问题的其他变化。在这些方向上有许多重要的研究进展的例子。我们提出了任务分配问题的一般表述，该问题概括了几个经过充分研究的版本。我们的表述包括机器人，任务和其操作周围环境的状态。我们描述问题如何根据可行性约束，目标函数和动态变化信息的水平而变化。此外，我们讨论了有关该问题的现有解决方案方法，包括基于优化的方法和基于市场的方法。

在异构机器人网络上进行计算负载共享是一个有希望的方法，可以将机器人能力和效率作为极端环境中的团队提高。然而，在这种环境中，通信链路可以是间歇性的，并且与云或因特网的连接可能是不存在的。在本文中，我们介绍了用于多机器人系统的通信感知，计算任务调度问题，并提出了整数线性程序（ILP），该程序（ILP）优化了异构机器人网络中的计算任务分配，占网络机器人的计算能力对于可用（和可能的时变）通信链接。我们考虑调度由依赖关系图建模的一组相互依赖的必需任务和可选任务。我们为共享世界，分布式系统提供了一项备份的调度架构。我们验证了ILP制定和不同计算平台中的分布式实现，并在模拟场景中，偏向于月球或行星探索方案。我们的研究结果表明，与没有计算负载共享的类似系统相比，所提出的实施方式可以优化提高时间表以允许三倍增加所执行的奖励任务的数量（例如，科学测量）。

疏散计划是灾难管理的关键部分，其目标是将人员搬迁到安全和减少伤亡。每个疏散计划都有两个基本组件：路由和调度。但是，这两个组件与目标的联合优化，例如最大程度地减少平均疏散时间或疏散完成时间，这是一个计算问题上的问题。为了解决它，我们提出了MIP-LNS，这是一种可扩展的优化方法，将启发式搜索与数学优化结合在一起，并可以优化各种目标函数。我们使用来自德克萨斯州休斯敦的哈里斯县的现实世界道路网络和人口数据，并应用MIP-LNS来查找该地区的疏散路线和时间表。我们表明，在给定的时间限制内，我们提出的方法在平均疏散时间，疏散完成时间和解决方案的最佳保证方面找到了比现有方法更好的解决方案。我们在研究区域进行基于代理的疏散模拟，以证明解决方案的功效和鲁棒性。我们表明，即使撤离人员在一定程度上偏离了建议的时间表，我们的规定疏散计划仍然有效。我们还研究了疏散计划如何受到道路故障的影响。我们的结果表明，MIP-LN可以使用有关道路估计截止日期的信息，以成功，方便地撤离更多人，以提出更好的疏散计划。

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

有关行动成本的信息对于现实世界中的AI规划应用程序至关重要。最近的方法不仅依靠声明性的行动模型，还使用了在计划阶段应用的黑框外部动作成本估算器，通常是从数据中学到的。但是，这些可能在计算上很昂贵，并产生不确定的值。在本文中，我们建议对确定性计划的概括，并允许在多个估计器之间选择动作成本，以平衡计算时间与有限估计不确定性。这使问题表示能力更丰富，并且相应地更现实。重要的是，它允许计划者限制计划的准确性，从而提高可靠性，同时减少不必要的计算负担，这对于扩展到大问题至关重要。我们介绍了一种搜索算法，概括了$ a^*$，该算法解决了此类计划问题和其他算法扩展。除了理论保证外，与替代方案相比，广泛的实验还显示出大量的运行时节省节省。

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

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

尽管使用多个无人机（UAV）具有快速自主探索的巨大潜力，但它的关注程度很少。在本文中，我们提出了赛车手，这是一种使用分散无人机的舰队的快速协作探索方法。为了有效派遣无人机，使用了基于在线HGRID空间分解的成对交互。它可确保仅使用异步和有限的通信同时探索不同的区域。此外，我们优化了未知空间的覆盖路径，并通过电容的车辆路由问题（CVRP）配方平衡分区到每个UAV的工作负载。鉴于任务分配，每个无人机都会不断更新覆盖路径，并逐步提取关键信息以支持探索计划。分层规划师可以找到探索路径，完善本地观点并生成序列的最小时间轨迹，以敏捷，安全地探索未知空间。对所提出的方法进行了广泛的评估，显示出较高的勘探效率，可伸缩性和对有限交流的鲁棒性。此外，我们第一次与现实世界中的多个无人机进行了完全分散的协作探索。我们将作为开源软件包发布实施。

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.

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

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

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

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

我们为仓库环境中的移动机器人提供基于新颖的强化学习（RL）任务分配和分散的导航算法。我们的方法是针对各种机器人执行各种接送和交付任务的场景而设计的。我们考虑了联合分散任务分配和导航的问题，并提出了解决该问题的两层方法。在更高级别，我们通过根据马尔可夫决策过程制定任务并选择适当的奖励来最大程度地减少总旅行延迟（TTD）来解决任务分配。在较低级别，我们使用基于ORCA的分散导航方案，使每个机器人能够独立执行这些任务，并避免与其他机器人和动态障碍物发生碰撞。我们通过定义较高级别的奖励作为低级导航算法的反馈来结合这些下层和上层。我们在复杂的仓库布局中进行了广泛的评估，并具有大量代理商，并根据近视拾取距离距离最小化和基于遗憾的任务选择，突出了对最先进算法的好处。我们观察到任务完成时间的改善高达14％，并且在计算机器人的无碰撞轨迹方面提高了40％。

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment with obstacles is challenging and cannot be guaranteed in a finite time. We propose an algorithm in which the accuracy of the path planning is iteratively increased. The approach provides a certificate when the uncertainties on estimates of the shortest paths become small enough to guarantee the optimality of the goal assignment. To this end, we apply results from assignment sensitivity assuming upper and lower bounds on the length of the shortest paths. We then provide polynomial-time methods to find such bounds by applying sampling-based path planning. The upper bounds are given by feasible paths, the lower bounds are obtained by expanding the sample set and leveraging knowledge of the sample dispersion. We demonstrate the application of the proposed method with a multi-robot path-planning case study.