可以部署一组合作的空中机器人，以有效地巡逻地形，每个机器人都会在指定区域飞行，并定期与邻居共享信息，以保护或监督它。为了确保鲁棒性，以前对这些同步系统的作品提出了将机器人发送到相邻区域的情况，以防它检测到故障。为了处理不可预测性并提高确定性巡逻计划的效率，本文提出了随机策略，以涵盖在代理之间分配的领域。首先，在本文中针对两个指标进行了对随机过程的理论研究：\ emph {闲置时间}，这是两个连续观察到地形的任何点和\ emph {隔离时间}之间的预期时间，预期的时间}，预期的时间机器人没有与任何其他机器人通信的时间。之后，将随机策略与添加另一个指标的确定性策略进行了比较：\ emph {广播时间}，从机器人发出消息的那一刻，直到团队的所有其他机器人收到消息。模拟表明，理论结果与模拟和随机策略的表现非常吻合，其行为与文献中提出的确定性协议获得的行为相比。

许多复杂网络的结构包括其拓扑顶部的边缘方向性和权重。可以无缝考虑这些属性组合的网络分析是可取的。在本文中，我们研究了两个重要的这样的网络分析技术，即中心和聚类。采用信息流基于集群的模型，该模型本身就是在计算中心的信息定理措施时构建。我们的主要捐款包括马尔可夫熵中心的广义模型，灵活地调整节点度，边缘权重和方向的重要性，具有闭合形式的渐近分析。它导致一种新颖的两级图形聚类算法。中心分析有助于推理我们对给定图形的方法的适用性，并确定探索当地社区结构的“查询”节点，从而导致群集聚类机制。熵中心计算由我们的聚类算法摊销，使其计算得高效：与使用马尔可夫熵中心为聚类的先前方法相比，我们的实验表明了多个速度的速度。我们的聚类算法自然地继承了适应边缘方向性的灵活性，以及​​边缘权重和节点度之间的不同解释和相互作用。总的来说，本文不仅具有显着的理论和概念贡献，还转化为实际相关性的文物，产生新的，有效和可扩展的中心计算和图形聚类算法，其有效通过广泛的基准测试进行了验证。

共识算法通过使多个机器人能够收敛到仅使用本地通信的全局变量的一致估计来构成许多分布式算法的基础。但是，标准共识协议可以轻松地由非合作团队成员误入歧途。因此，对于设计弹性分布式算法是必要的，对共识的弹性形式的研究是必要的。 W-MSR共识是一种这样的有弹性共识算法，它允许仅具有通信图的本地知识，而没有用于共享数据的先验模型。但是，给定通信图满足严格的图形连接要求的验证使W-MSR在实践中难以使用。在本文中，我们显示了机器人文献中常用的通信图结构，即基于Voronoi Tessellation构建的通信图，自动产生足够连接的图以拒绝单个非合作团队成员。此外，我们展示了如何增强该图，以拒绝两个非合作团队成员，并为修改进一步的弹性提供路线图。这项贡献将允许在已经依赖基于Voronoi的通信（例如分布式覆盖范围和探索算法）的算法中轻松应用弹性共识。

当考虑$ N $标记的机器人的运动计划时，我们需要通过一系列平行，连续的，无碰撞的机器人运动来重新布置给定的启动配置为所需的目标配置。目的是在最短的时间内达到新配置；一个重要的约束是始终保持群体连接。以前已经考虑过这种类型的问题，最近值得注意的结果可实现不一定连接的重新配置：如果将起始配置映射到目标配置，则需要最大的曼哈顿距离$ D $，则总体时间表的总持续时间可以是限制为$ \ Mathcal {O}（d）$，这是最佳选择的恒定因素。但是，只有在允许断开连接的重新配置或用于缩放的配置（通过将给定对象的所有维度通过相同的乘法因子增加到相同的乘法因子增加）时，才能实现恒定拉伸。我们通过（1）建立$ \ omega（\ sqrt {n}）$的下限来解决这些主要的开放问题可以实现重新配置。此外，我们表明（3）决定是否可以实现2个制造物，而可以检查多项式时间是否可以实现1个制造pan。

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

马尔可夫链是一类概率模型，在定量科学中已广泛应用。这部分是由于它们的多功能性，但是可以通过分析探测的便利性使其更加复杂。本教程为马尔可夫连锁店提供了深入的介绍，并探索了它们与图形和随机步行的联系。我们利用从线性代数和图形论的工具来描述不同类型的马尔可夫链的过渡矩阵，特别着眼于探索与这些矩阵相对应的特征值和特征向量的属性。提出的结果与机器学习和数据挖掘中的许多方法有关，我们在各个阶段描述了这些方法。本文并没有本身就成为一项新颖的学术研究，而是提出了一些已知结果的集合以及一些新概念。此外，该教程的重点是向读者提供直觉，而不是正式的理解，并且仅假定对线性代数和概率理论的概念的基本曝光。因此，来自各种学科的学生和研究人员可以访问它。

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.

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

随机漫游是许多机器学习算法中使用的基本原语，其中包括聚类和半监督学习中的几种应用。尽管他们的相关性，但最近推出了第一个计算随机散步的有效并行算法（Lacki等人）。不幸的是，他们的方法具有基本缺点：它们的算法是非本地的，因为它严重依赖于计算随机从输入图中的所有节点中散布，即使在许多实际应用中只对计算随机只能从一个小子集中散步感兴趣图中的节点。在本文中，我们介绍了一种新的算法，通过同时建立随机和本地的随机行走来克服这种限制。我们表明我们的技术既存储器也又高效，特别是产生有效的并行本地聚类算法。最后，我们将我们的理论分析补充了实验结果，表明我们的算法比以前的方法更可扩展。

我们提出了一个新的图形神经网络，我们称为AgentNet，该网络专为图形级任务而设计。 AgentNet的灵感来自子宫性算法，具有独立于图形大小的计算复杂性。代理Net的体系结构从根本上与已知图神经网络的体系结构不同。在AgentNet中，一些受过训练的\ textit {神经代理}智能地行走图，然后共同决定输出。我们提供了对AgentNet的广泛理论分析：我们表明，代理可以学会系统地探索其邻居，并且AgentNet可以区分某些甚至3-WL无法区分的结构。此外，AgentNet能够将任何两个图形分开，这些图在子图方面完全不同。我们通过在难以辨认的图和现实图形分类任务上进行合成实验来确认这些理论结果。在这两种情况下，我们不仅与标准GNN相比，而且与计算更昂贵的GNN扩展相比。

我们提出协调指导矢量字段，以与机器人团队同时完成两个任务：首先，多个机器人的指导和导航到可能嵌入2D或3D中的可能不同的路径或表面；其次，他们的运动协调在跟踪他们的规定路径或表面时。运动配位是由路径或表面上的机器人之间所需的参数位移定义的。通过控制对应于指导矢量场之间的路径或表面参数的虚拟坐标来实现这种所需的位移。由动力学系统理论和Lyapunov理论支撑的严格数学保证，用于从所有初始位置上有效的分布式运动协调和机器人在路径或表面上导航。作为实用机器人应用的一个例子，我们从所提出的具有驱动饱和度的Dubins-car样模型的指导向量场中得出了一种对照算法。我们提出的算法分布并可扩展到任意数量的机器人。此外，广泛的说明性模拟和固定翼飞机户外实验验证了我们算法的有效性和鲁棒性。

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

近年来，研究人员委托机器人和无人驾驶汽车（UAV）团队委托进行准确的在线野火覆盖范围和跟踪。迄今为止，大多数先前的工作都集中在此类多机器人系统的协调和控制上，但尚未赋予这些无人机团队对火的轨道（即位置和传播动态）进行推理的能力，以提供性能保证时间范围。在空中野火监测的问题上，我们提出了一个预测框架，该框架使多UAV团队的合作能够与概率性能保证一起进行协作现场覆盖和火灾跟踪。我们的方法使无人机能够推断出潜在的火灾传播动态，以在安全至关重要的条件下进行时间扩展的协调。我们得出了一组新颖的，分析的时间和跟踪纠纷界限，以使无人机团队根据特定于案例的估计状态分发有限的资源并覆盖整个火灾区域，并提供概率性能保证。我们的结果不仅限于空中野火监测案例研究，而且通常适用于搜索和救援，目标跟踪和边境巡逻等问题。我们在模拟中评估了我们的方法，并在物理多机器人测试台上提供了建议的框架，以说明真实的机器人动态和限制。我们的定量评估验证了我们的方法的性能，分别比基于最新的模型和强化学习基准分别累积了7.5倍和9.0倍的跟踪误差。

在本文中，我们推导了机器人来测量相对方向或到达角度（AOA）的新能力，以在非视线和未映射的环境中运行的其他机器人，而无需外部基础架构。我们通过捕获WiFi信号在从发送到接收机器人时遍历的所有路径来这样做，这是我们术语AOA简档。当机器人在3D空间中移动时，关键直觉是“在空中模拟空气中的天线阵列”，一种类似于合成孔径雷达（SAR）的方法。主要贡献包括i）一个框架，以适应任意3D轨迹的框架，以及所有机器人的持续移动性，而计算AOA配置文件和II）随附的分析，其提供了作为机器人轨迹的函数的AOA估计方差的较低限制基于Cramer Rao绑定的几何。这是一个关键的区别与先前的SAR的工作，限制机器人移动到规定的运动模式，不概括到3D空间，和/或在数据采集时段期间需要将机器人发送到静态。我们的方法导致更准确的AOA配置文件，从而更好地估计，并正式地将该观察表征为轨迹的信息性;我们推导出封闭形式的可计算量。所有理论发展都是通过广泛的模拟和硬件实验证实的。我们还表明，我们的配方可以与现成的轨迹估计传感器一起使用。最后，我们展示了我们系统对多机器人动态集合任务的表现。

随着大型网络在重要领域的相关领域的相关性，例如对疾病传播的联系网络的研究，或社交网络对地缘政治的影响，已经有必要研究可扩展到非常大的网络的机器学习工具，通常包含数百万节点。一种主要类别可扩展算法称为网络表示学习或网络嵌入。这些算法尝试通过首次运行多个随机散步，然后使用观察到的随机步行段中的每对节点的共同数量来学习网络功能（例如〜节点）的表示，以获得一些节点的低维表示欧几里德空间。本文的目的是严格地了解两个主要算法，深途化和Node2VEC的性能，以恢复与地面真理社区的规范网络模型的社区。根据图的稀疏性，我们发现所需的随机步道段的长度，使得相应的观察到的共生窗口能够对底层社区分配的几乎精确恢复。我们证明，考虑到一些固定的共同发生窗口，使用随机散步的Node2Vec与低横向概率的随机散步可以相比，与使用简单随机散步的深度扫视相比，稀疏网络可以成功。此外，如果稀疏参数低，我们提供了证据表明这些算法几乎完全恢复可能不会成功。该分析需要开发用于对具有底层低级结构的随机网络计数的通用工具，这与独立兴趣。

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

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

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲，我们的结果表明，随机块模型没有稳健性。我们的工作受到最近的银行，Mohanty和Raghavendra（SODA 2021）的工作，为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观：种植的分区可能远非最佳意义，即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知，我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化（与平方和不同的不同），这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术，其提高了任意强大的弱恢复算法的成功（输入的随机性）从恒定（或缓慢消失）概率以指数高概率。

重新配置图中的两个最短路径意味着通过一次改变一个顶点来修改一个最短的路径，使得所有中间路径也是最短路径。这个问题有几个自然应用，即：（a）改造道路网络，（b）在同步多处理设置中重新排出数据包，（c）运输集装箱存货问题，以及（d）列车编组问题。在作为图形问题的建模时，（a）是最常规的情况而（b），（c）和（d）是对不同图形类的限制。我们表明（a）是棘手的，即使对于问题的轻松变体也是如此。对于（b），（c）和（d），我们提出了有效的算法来解决各自的问题。我们还将问题概括为当最多$ k $（对于固定整数$ k \ geq k \ ge $ k \ geq 2 $）一次连续的顶点一次可以一次更改。