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

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

区域覆盖范围问题是使用安装在机器人（例如无人驾驶汽车（UAV）（UAV）和无人接地车辆（UGV）等机器人上的传感器有效维修给定的二维表面的任务。我们提出了一种新颖的配方，用于生成多个容量受限机器人的覆盖路线，可以根据电池寿命或飞行时间指定容量。遍历环境对具有容量限制的机器人资源产生了需求。我们方法的主要方面是将区域覆盖问题转换为线覆盖范围问题（即线性特征的覆盖范围），然后生成途径，以最大程度地减少旅行的总成本，同时尊重容量约束。我们定义了两种旅行模式：（1）维修和（2）无人机，这与机器人是否执行特定于任务的操作相对应。我们的配方允许对两种模式的单独和不对称的旅行成本和需求。此外，从细胞分解计算出来的细胞，旨在最小化转弯的数量，不需要单调多边形。我们为细胞分解和生成服务轨道开发了新的程序，这些过程可以处理有或没有孔的非符号酮多边形。我们在具有25个室内环境的地面机器人数据集和一个具有300个室外环境的空中机器人数据集上建立了算法的功效。该算法生成的解决方案的成本比最新方法平均低10％。我们还证明了我们在无人机实验中的算法。

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

我们研究了合作航空航天车辆路线应用程序的资源分配问题，其中多个无人驾驶汽车（UAV）电池容量有限和多个无人接地车辆（UGV），这也可以充当移动充电站，需要共同实现诸如持续监视一组要点之类的任务。由于无人机的电池能力有限，他们有时必须偏离任务才能与UGV进行集合并得到充电。每个UGV一次可以一次提供有限数量的无人机。与确定性多机器人计划的先前工作相反，我们考虑了无人机能源消耗的随机性所带来的挑战。我们有兴趣找到无人机的最佳充电时间表，从而最大程度地减少了旅行成本，并且在计划范围内没有任何无人机在计划范围内取消收费的可能性大于用户定义的公差。我们将此问题（{风险意识召集集合问题（RRRP））}作为整数线性程序（ILP），其中匹配的约束捕获资源可用性约束，而背包约束捕获了成功概率约束。我们提出了一种求解RRRP的双晶格近似算法。在一个持续监测任务的背景下，我们证明了我们的制定和算法的有效性。

Coverage path planning is a major application for mobile robots, which requires robots to move along a planned path to cover the entire map. For large-scale tasks, coverage path planning benefits greatly from multiple robots. In this paper, we describe Turn-minimizing Multirobot Spanning Tree Coverage Star(TMSTC*), an improved multirobot coverage path planning (mCPP) algorithm based on the MSTC*. Our algorithm partitions the map into minimum bricks as tree's branches and thereby transforms the problem into finding the maximum independent set of bipartite graph. We then connect bricks with greedy strategy to form a tree, aiming to reduce the number of turns of corresponding circumnavigating coverage path. Our experimental results show that our approach enables multiple robots to make fewer turns and thus complete terrain coverage tasks faster than other popular algorithms.

我们介绍了多模式的汽车和乘车共享问题（MMCRP），其中使用一台汽车来涵盖一组乘车请求，同时将发现的请求分配给其他运输方式（MOT）。汽车的路线由一次或多个旅行组成。每次旅行都必须具有特定但不明的驱动程序，以仓库开始，然后以（可能不同的）仓库结束。即使两个骑行没有相同的起源和/或目的地，也允许在用户之间共享骑行。用户始终可以根据各个首选项列表使用其他运输方式。该问题可以作为车辆调度问题提出。为了解决该问题，构建了一个辅助图，在该图中，每次旅行在仓库中的启动和结尾，并覆盖可能的乘车共享，以时空图中的形式建模为弧。我们提出了一种基于列生成的两层分解算法，其中主问题可确保最多只能涵盖每个请求，并且定价问题通过在时间 - 时间中解决一种最短路径问题来生成新的有希望的路线空间网络。报告了基于现实实例的计算实验。基准实例基于奥地利维也纳的人口，空间和经济数据。我们通过在合理时间内基于列生成的方法来解决大型实例，并进一步研究了各种精确和启发式定价方案。

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.

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

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

This paper presents trajectory planning for three-dimensional autonomous multi-UAV volume coverage and visual inspection based on the Heat Equation Driven Area Coverage (HEDAC) algorithm. The method designs a potential field to achieve the target density and generate trajectories using potential gradients to direct UAVs to regions of a higher potential. Collisions are prevented by implementing a distance field and correcting the agent's directional vector if the distance threshold is reached. The method is successfully tested for volume coverage and visual inspection of complex structures such as wind turbines and a bridge. For visual inspection, the algorithm is supplemented with camera direction control. A field containing the nearest distance from any point in the domain to the structure is designed and this field's gradient provides the camera orientation throughout the trajectory. The bridge inspection test case is compared with a state-of-the-art method where the HEDAC algorithm allowed more surface area to be inspected under the same conditions. The limitations of the HEDAC method are analyzed, focusing on computational efficiency and adequacy of spatial coverage to approximate the surface coverage. The proposed methodology offers flexibility in various setup parameters and is applicable to real-world inspection tasks.

This paper presents a new method for integrated time-optimal routing and trajectory optimization of multirotor unmanned aerial vehicles (UAVs). Our approach extends the well-known Traveling Salesman Problem by accounting for the limited maneuverability of the UAVs due to their kinematic properties. To this end, we allow each waypoint to be traversed with a discretized velocity as well as a discretized flight direction and compute time-optimal trajectories to determine the travel time costs for each edge. We refer to this novel optimization problem as the Trajectory-based Traveling Salesman Problem (TBTSP). The results show that compared to a state-of-the-art approach for Traveling Salesman Problems with kinematic restrictions of UAVs, we can decrease mission duration by up to 15\%.

In many unmanned aerial vehicle (UAV) applications for surveillance and data collection, it is not possible to reach all requested locations due to the given maximum flight time. Hence, the requested locations must be prioritized and the problem of selecting the most important locations is modeled as an Orienteering Problem (OP). To fully exploit the kinematic properties of the UAV in such scenarios, we combine the OP with the generation of time-optimal trajectories with bounds on velocity and acceleration. We define the resulting problem as the Kinematic Orienteering Problem (KOP) and propose an exact mixed-integer formulation together with a Large Neighborhood Search (LNS) as a heuristic solution method. We demonstrate the effectiveness of our approach based on Orienteering instances from the literature and benchmark against optimal solutions of the Dubins Orienteering Problem (DOP) as the state-of-the-art. Additionally, we show by simulation \color{black} that the resulting solutions can be tracked precisely by a modern MPC-based flight controller. Since we demonstrate that the state-of-the-art in generating time-optimal trajectories in multiple dimensions is not generally correct, we further present an improved analytical method for time-optimal trajectory generation.

我们介绍了一种考虑复杂的环境条件，在极地地区介绍了一种在极地地区长距离海上路线计划的方法。该方法允许构建优化的路线，描述了该过程的三个主要阶段：使用不均匀网格对环境条件进行离散建模，网格最佳路径的构建以及路径平滑。为了说明不同的车辆性能，我们构建了一系列数据驱动的功能，这些功能可以应用于环境网格，以确定给定容器和网格单元的速度限制和燃料要求，以图形和地理空间表示这些数量。在描述我们的结果时，我们展示了一个示例用途，用于Polar Research船RRS David Attenborough爵士（SDA）的路线规划，核算冰的性能特征，并验证韦德尔海地区的时空路线构建，南极洲。我们通过证明路线的变化取决于季节性海冰可变性，所使用的路线规划目标函数的差异以及其他环境条件（如电流）的存在来证明这种路线构建方法的多功能性。为了证明我们的方法的普遍性，我们在北极海洋和波罗的海中介绍了例子。本手稿中概述的技术是通用的，因此可以应用于具有不同特征的血管。我们的方法不仅可以拥有一个船只计划程序，而且我们概述了该工作流程如何适用于更广泛的社区，例如商业和乘客运输。

在过去的十年中，自动驾驶航空运输车辆引起了重大兴趣。这是通过空中操纵器和新颖的握手的技术进步来实现这一目标的。此外，改进的控制方案和车辆动力学能够更好地对有效载荷进行建模和改进的感知算法，以检测无人机（UAV）环境中的关键特征。在这项调查中，对自动空中递送车辆的技术进步和开放研究问题进行了系统的审查。首先，详细讨论了各种类型的操纵器和握手，以及动态建模和控制方法。然后，讨论了降落在静态和动态平台上的。随后，诸如天气状况，州估计和避免碰撞之类的风险以确保安全过境。最后，调查了交付的UAV路由，该路由将主题分为两个领域：无人机操作和无人机合作操作。

在过去的几十年中，经典的车辆路由问题（VRP），即为车辆分配一组订单并规划他们的路线已经被密集研究。仅作为车辆的订单分配和他们的路线已经是一个NP完整的问题，因此在实践中的应用通常无法考虑在现实世界应用中应用的约束和限制，所谓的富VRP所谓的富VRP（RVRP）并且仅限于单一方面。在这项工作中，我们融入了主要的相关真实限制和要求。我们提出了一种两级策略和时间线窗口和暂停时间的时间线算法，并将遗传算法（GA）和蚁群优化（ACO）单独应用于问题以找到最佳解决方案。我们对四种不同问题实例的评估，针对四个最先进的算法表明，我们的方法在合理的时间内处理所有给定的约束。

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

解决逆运动学问题是针对清晰机器人的运动计划，控制和校准的基本挑战。这些机器人的运动学模型通常通过关节角度进行参数化，从而在机器人构型和最终效果姿势之间产生复杂的映射。或者，可以使用机器人附加点之间的不变距离来表示运动学模型和任务约束。在本文中，我们将基于距离的逆运动学的等效性和大量铰接式机器人和任务约束的距离几何问题进行形式化。与以前的方法不同，我们使用距离几何形状和低级别矩阵完成之间的连接来通过局部优化完成部分欧几里得距离矩阵来找到逆运动学解决方案。此外，我们用固定级革兰氏矩阵的Riemannian歧管来参数欧几里得距离矩阵的空间，从而使我们能够利用各种成熟的Riemannian优化方法。最后，我们表明，绑定的平滑性可用于生成知情的初始化，而无需大量的计算开销，从而改善收敛性。我们证明，我们的逆运动求解器比传统技术获得更高的成功率，并且在涉及许多工作区约束的问题上大大优于它们。

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

无人驾驶飞机（UAV）是飞机，其飞行可以完全自主，而无需任何人为干预。自然灾害管理是可以使用无人机的最有用和最有前途的领域之一。在本文中，我们专注于紧急情况，并提出使用无人机机队，以帮助营救团队个性化受影响区域内需要帮助的人。我们将这种情况建模为原始图理论问题，称为多部门多行车路由问题，总完成时间最小化（MDMT-VRP-TCT）；我们经历了一些与之相似的文献研究中已经研究的问题，并突出了差异，提出了作为MILP作为MILP的数学表述，设计了一种数学框架来快速解决大型实例，并在实验中测试其性能。除了提出的应用程序之外，我们的解决方案在任何情况下都必须解决多部多行车路由问题的任何情况。