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

本文介绍了相关的弧定向问题（CAOP），其中的任务是找到机器人团队的路线，以最大程度地收集与环境中功能相关的奖励的收集。这些功能可以是一维或环境中的点，并且可以具有空间相关性，即访问环境中的功能可能会提供与相关功能相关的奖励的一部分。机器人在环境环境时会产生成本，并且路线的总成本受到资源限制（例如电池寿命或操作时间）的限制。由于环境通常很大，我们允许多个仓库在机器人必须启动和结束路线的地方。 CAOP概括了相关的定向问题（COP），其中奖励仅与点特征相关联以及ARC定向启动问题（AOP），其中奖励与无空间相关。我们制定了一个混合整数二次程序（MIQP），该程序正式化了问题并提供最佳的解决方案。但是，这个问题是NP-HARD，因此我们开发了一种有效的贪婪的建设性算法。我们用两种不同的应用说明了问题：甲烷气体泄漏检测和道路网络覆盖范围的信息路径计划。

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

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

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

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%.

线覆盖范围的问题是找到有效的路由，以通过一个或多个资源约束的机器人覆盖线性特征。线性具有模型环境，例如道路网络，电力线以及石油和天然气管道。我们为机器人定义了两种旅行模式：维修和陷入困境。机器人服务功能如果它执行特定于任务的操作，例如拍摄图像，则它可以遍历该功能；否则，它是无人机的。穿越环境会产生成本（例如旅行时间）和对资源的需求（例如电池寿命）。维修和无人机的成本和需求功能可能具有不同的成本和需求功能，我们进一步允许它们取决于方向。我们将环境建模为图形，并提供整数线性程序。由于问题是NP-HARD，因此我们开发了一种快速有效的启发式算法，即合并 - 默认混合物（MEM）。该算法的建设性属性使得为大图求解了多depot版本。我们进一步扩展了MEM算法，以处理转弯成本和非语言限制。我们在50个道路网络的数据集上对算法进行基准测试，并在道路网络上使用空中机器人进行了实验中的算法。

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

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

线覆盖范围是为环境中的一组一维功能提供服务的任务。这对于检查线性基础设施（例如道路网络，电力线以及石油和天然气管道）很重要。本文通过在图上将其建模为优化问题，解决了空中和地面机器人的单个机器人线覆盖率问题。该问题属于广泛的ARC路由问题，与不对称的农村邮政问题（RPP）密切相关。本文提供了一个整数线性编程公式，并提供了正确的证明。使用最低成本流问题，我们开发近似算法，并保证解决方案质量。这些保证还改善了不对称RPP的现有结果。主要算法将问题分为三种情况，以所需图的结构，即需要维修的特征诱导的图。我们在世界上50个人口最多的城市的道路网络上评估了我们的算法。该算法以改进的启发式增强，在3s内运行，并生成最佳最佳10％以内的解决方案。我们在UNC Charlotte校园路网络上通过商业无人机在实验中展示了我们的算法。

在本文中，我们考虑了在具有多个自动机器人的系统中分配人类操作员协助的问题。每个机器人都需要完成独立任务，每个任务定义为一系列任务。在执行任务时，机器人可以自主操作，也可以由人类操作员远程执行，以更快地完成任务。我们表明，创建详细时间表的问题使系统的制造量最小化是NP-HARD。我们将问题提出为混合整数线性程序，可用于最佳地解决小到中等大小的问题实例。我们还开发了一种随时随地的算法，该算法利用问题结构来提供对操作员调度问题的快速和高质量解决方案，即使对于更大的问题实例也是如此。我们的关键见解是在贪婪创建的时间表中识别阻止任务，并迭代地删除这些块以提高解决方案的质量。通过数值模拟，我们证明了所提出的算法的好处是一种高于其他贪婪方法的有效且可扩展的方法。

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

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

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

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

在本文中，我们研究了通过优化的流量路由的路径增加对运输网络的影响。特别是，我们研究了总旅行时间的行为，并考虑了自我利益的路由范式，例如用户平衡（UE）路由以及合作范式，例如经典多商品（MC）网络流量和系统最佳（因此）路由。我们提供了一个正式的框架，用于通过迭代路径添加设计运输网络，引入跨越树和跳跃路径图的概念。使用此形式化，我们证明了运输网络设计的目标函数的多个属性。由于基础路由问题是NP-HARD，因此我们研究了提供近似算法设计保证的属性。首先，尽管Braess的悖论表明，对于在自私路由（UE）下的路径添加（UE）方面，总旅行时间并不是单调的非侵扰，但我们证明，相反，单调性具有合作路由（MC等）。该结果具有重要的含义，即合作社可以充分利用冗余基础设施。其次，我们通过反例证证明，直观的语句``在传输网络中添加路径始终赋予用户更大或平等的好处，而不是将其添加到该网络的超集中'是错误的。换句话说，我们证明，对于所有研究的路由公式，相对于路径添加而言，总旅行时间不是超模型。尽管这种违反直觉结果为算法设计带来了硬度属性，但我们提供了特定的实例，而相反，超模型的属性则具有。我们关于相对于路径增加的总旅行时间的单调性和超模样的研究提供了正式的证明和场景，构成了运输网络设计师的重要见解。

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

在本文中，我们证明了一种用于优化耦合子模块的最大化问题的制定，具有可提供的次优先界限。在机器人应用中，很常见的是优化问题彼此耦合，因此不能独立解决。具体地，如果第一问题的结果影响第二问题的解决方案，我们考虑两个问题耦合的两个问题，该第二问题在更长的时间尺度上运行。例如，在环境监测的激励问题中，我们对多机器人任务分配有可能影响环境动态，从而影响未来监测的质量，在这里建模为多机器人间歇部署问题。通过该激励例证明了解决这种类型耦合问题的一般理论方法。具体地，我们提出了一种求解由Matroid约束模拟的子模具集功能建模的耦合问题的方法。提出了一种解决这类问题的贪婪算法，以及子最优的保证。最后，通过蒙特卡罗模拟示出了实用的最优比率，以证明所提出的算法可以高效率产生近最佳解决方案。

In many domains such as transportation and logistics, search and rescue, or cooperative surveillance, tasks are pending to be allocated with the consideration of possible execution uncertainties. Existing task coordination algorithms either ignore the stochastic process or suffer from the computational intensity. Taking advantage of the weakly coupled feature of the problem and the opportunity for coordination in advance, we propose a decentralized auction-based coordination strategy using a newly formulated score function which is generated by forming the problem into task-constrained Markov decision processes (MDPs). The proposed method guarantees convergence and at least 50% optimality in the premise of a submodular reward function. Furthermore, for the implementation on large-scale applications, an approximate variant of the proposed method, namely Deep Auction, is also suggested with the use of neural networks, which is evasive of the troublesome for constructing MDPs. Inspired by the well-known actor-critic architecture, two Transformers are used to map observations to action probabilities and cumulative rewards respectively. Finally, we demonstrate the performance of the two proposed approaches in the context of drone deliveries, where the stochastic planning for the drone league is cast into a stochastic price-collecting Vehicle Routing Problem (VRP) with time windows. Simulation results are compared with state-of-the-art methods in terms of solution quality, planning efficiency and scalability.

协调图是一种有前途的模型代理协作在多智能体增强学习中的合作方法。它将一个大的多代理系统分解为代表底层协调依赖性的重叠组套件。此范例中的一个危急挑战是计算基于图形的值分子的最大值动作的复杂性。它指的是分散的约束优化问题（DCOP），其恒定比率近似是NP - 硬问题。为了绕过这一基本硬度，提出了一种新的方法，命名为自组织的多项式协调图（SOP-CG），它使用结构化图表来保证具有足够功能表达的所致DCOP的最优性。我们将图形拓扑扩展为状态依赖性，将图形选择作为假想的代理商，最终从统一的Bellman Optimaly方程中获得端到端的学习范例。在实验中，我们表明我们的方法了解可解释的图形拓扑，诱导有效的协调，并提高各种合作多功能机构任务的性能。