两种尺寸的模块化机器人的良好理论模型是边缘连接的方形模块配置，可以通过所谓的滑动移动重新配置。 Dumitrescu和Pach [图形和Combinatorics，2006]证明，始终可以将N $ Squares的一个边缘连接配置重新配置为任何其他使用$ O（n ^ 2）$滑动移动，同时保持配置连接每时每刻。对于某些配置，重新配置可能需要$ \ omega（n ^ 2）$滑动移动。然而，可能就足够较少。我们证明它是难以最小化给定对边缘连接配置的滑动移动的数量。在正面，我们呈现收集和紧凑，一个输入敏感的就地算法只需要$ O（\ bar {p} n）$ slide移动，将一个配置转换为另一个配置，其中$ \ bar {p} $两个边界框的最大周边。正方形仅在边界盒内移动，除了可以通过与边界框相邻的位置移动的时间最多的一个正方形。 $ O（\ bar {p} n）$绑定永远不会超过$ o（n ^ 2）$，并且在只需$ n $和$ \ bar {p} $ 。我们的算法建立在基本原理上，可以有效地转换模块化机器人的良好连接的组件。因此，我们迭代地提高配置内的连接，最终到达一个固体$ xy $-monotone组件。我们实施了聚集＆紧凑，并通过实验进行了比较了Moreno和Searist的原始修改，Dumitrescu和PACH算法（MSDP）的[Eurocg 2020]。我们的实验表明，在所有类型的方形配置上，聚集和紧凑始终如一地优于MSDP。

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

我们研究了一个可编程物质系统的模型，该模型由位于二维正方形网格上的$ n $设备组成，该设备能够执行相互旋转的最小机械操作。目的是将初始形状A变成目标形状B。我们有兴趣表征形状类别，这些形状可以在这种情况下在始终保持全局连接性的附加约束下相互转化。这是$ [$ MICHAIL等人，JCSS'19 $] $打开的主要问题之一。请注意，被考虑的问题是关于转型的结构可行性，我们仅通过集中的建设性证明来处理。分布式解决方案留给将来的工作，并形成一个有趣的研究方向。过去的工作取得了一些特殊形状类别的进步。我们在这里考虑了正交凸形的类别，其中任何两个节点$ u，v $在网格上的水平或垂直线中，$ u $和$ v $之间没有空单元。我们开发了一个通用的集中转换，并证明，对于任何一对$ a $ a $ b $ colour colour consisterstent的正交凸形形状，它可以将$ a $ a $变成$ b $。鉴于在考虑类中存在阻塞的形状，我们使用最小的3节点种子来触发转化。我们转换的运行时间是最佳$ O（n^2）$顺序移动，其中$ n = | a | = | b | $。我们留下的是一个空旷的问题，存在着一个小种子的普遍保留连接转换。我们的信念是，本文开发的技术可能对回答这一点很有用。

我们考虑通过变质机器人系统（MRS）在有限3D立方网格中搜索，该系统由匿名模块组成。在整个模块保持连接的同时，模块可以执行滑动和旋转。随着模块的数量增加，MRS可以执行的各种动作增加。搜索问题要求MRS在给定的有限字段中找到目标。 Doi等人。 （SSS 2018）演示了用于搜索有限2D平方网格的必要和足够数量的模块。我们考虑在有限3D立方网格中搜索并调查共同知识的效果。我们考虑三种不同的设置。首先，我们表明，当所有模块配备公共指南针时，我们就需要三个模块，即，他们就标准的方向和方向达到$ x $，$ y $和$ z $ x。其次，当所有模块都达成垂直轴的方向和方向时，我们表明需要四个模块并且充分。最后，我们表明，当所有模块都没有配备普通的指南针时，需要五个模块。我们的结果表明，3D立方网格中的MRS的形状比2D方形网格中的结构更丰富。

Arbitrary pattern formation (\textsc{Apf}) is well studied problem in swarm robotics. The problem has been considered in two different settings so far; one is in plane and another is in infinite grid. This work deals the problem in infinite rectangular grid setting. The previous works in literature dealing with \textsc{Apf} problem in infinite grid had a fundamental issue. These deterministic algorithms use a lot space of the grid to solve the problem mainly because of maintaining asymmetry of the configuration or to avoid collision. These solution techniques can not be useful if there is a space constrain in the application field. In this work, we consider luminous robots (with one light that can take two colors) in order to avoid symmetry, but we carefully designed a deterministic algorithm which solves the \textsc{Apf} problem using minimal required space in the grid. The robots are autonomous, identical, anonymous and they operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The \textsc{Apf} algorithm proposed in [WALCOM'2019] by Bose et al. can be modified using luminous robots so that it uses minimal space but that algorithm is not move optimal. The algorithm proposed in this paper not only uses minimal space but also asymptotically move optimal. The algorithm proposed in this work is designed for infinite rectangular grid but it can be easily modified to work in a finite grid as well.

本文使用基于采样的方法RRT*研究，以在复杂的环境中重新配置一组连接的瓷砖，在这些环境中可能存在多个障碍。由于目标应用程序是自动构建离散的自动构建，因此使用移动机器人进行了蜂窝结构，因此有一些限制可以确定可以拾取哪些图块以及在重新配置期间可以将其放下的块。我们将我们的方法与两种算法作为全球和本地计划者进行了比较，并表明我们能够在具有不同程度的障碍空间的环境中使用合理数量的样本找到更有效的构建序列。

结构分解方法，例如普遍的高树木分解，已成功用于解决约束满意度问题（CSP）。由于可以重复使用分解以求解具有相同约束范围的CSP，因此即使计算本身很难，将资源投资于计算良好的分解是有益的。不幸的是，即使示波器仅略有变化，当前方法也需要计算全新的分解。在本文中，我们迈出了解决CSP $ P $分解的问题的第一步，以使其成为由$ P $修改产生的新CSP $ P'$的有效分解。即使从理论上讲问题很难，我们还是提出并实施了一个有效更新GHD的框架。我们算法的实验评估强烈提出了实际适用性。

分子机器人有挑战性，所以最好保持简单。我们考虑基于异步执行的简单折叠指令的抽象分子机器人模型。车削机器是一个简单的1D到2D折叠模型，也可以轻松地展开2D到3D折叠。车削机在离散平面中的一条连接的单体线开始，每个连接单体具有相关的转弯数。单体相对于其邻居转动，执行单位距离转换，其沿其拖动其它单体，并且通过集体运动，初始单体组最终折叠成编程形状。我们充分地表征了转动机器执行线路旋转的能力，并为此如此有效：计算5 \ PI / 3 $弧度的几乎全线旋转，但不可能为2 \ PI $旋转。我们表明，这种线旋转在模型中代表了一个基本原语，通过使用它们来有效地和异步地折叠任意大的Zig-Zag-reasted方块和$ Y $ -Onotone形状。

在自动机器人群的现有文献中，采用的可见性模型具有一些与实际传感设备实现不符的理想主义假设。本文在更现实的可见性模型中调查了这个问题，称为不透明的脂肪机器人，具有纤细的全向相机。机器人被建模为单位磁盘，每个磁盘都具有全向摄像头，表示为尺寸较小的磁盘。我们假设机器人具有指南针，可以在其局部坐标系统的两个轴方向和方向上达成共识。机器人配备了可见的灯光，这些灯光是通信的媒介，也可以用作记忆的形式。我们为相互可见性问题提供了分布式算法，该算法在半同步设置中被证明是正确的。我们的算法还为领导者选举提供了解决方案，我们将其用作主要算法中的子例程。尽管在完整的可见性模型中，领导者选举在两个轴心协议中是微不足道的，但在我们的案例中，这是具有挑战性的，并且具有独立的利益。

在分配的图表上，多代理探路（MAPF）的问题在于为多种代理寻找路径，避免碰撞。已知找到最小长度的解决方案是NP-固定的，并且计算时间随着试剂的数量而呈指数增长。但是，在工业应用中，重要的是要在随着代理数量多一项生长的时期找到可行的次优溶液。这种算法存在于无向和双连接的有向图。我们的主要贡献是将这些算法概括为更加牢固连接的有向图的情况。特别是，给定至少两个孔的MAPF问题，我们提出了一种算法，该算法可检查线性时间相对于节点数量的可行性，并在多项式时间内提供可行的解决方案。

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

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

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

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

$ N $ -Quens配置是$ N \ Times N $ Chessboard的$ N $相互非攻击座位的位置。Nauck在1850年介绍的$ N $ -Queens完井问题是决定是否可以将给定的部分配置完成为$ N $ -Queens配置。在本文中，我们研究了这个问题的极端方面，即：部分配置必须小心，以便完成完成？我们表明，可以完成任何最多$ N / 60 $相互非攻击Queens的展示。我们还提供了大约N / 4 $ Queens的部分配置，不能完成，并制定一些有趣的问题。我们的证据将Queens问题与二角形图中的彩虹匹配连接，并使用概率参数以及线性编程二元性。

连续约束满意度问题（CCSP）是一个约束满意度问题（CSP），其间隔域$ u \ subset \ mathbb {r} $。我们进行了一项系统的研究，以对CCSP进行分类，这些CCSP已完成现实的存在理论，即ER完整。为了定义该类别，我们首先考虑ETR问题，该问题也代表了真实的存在理论。在此问题的情况下，我们给出了$ \ compant x_1，\ ldots，x_n \ in \ mathbb {r}的某个句子：\ phi（x_1，\ ldots，x_n）$，其中$ \ phi $ is由符号$ \ {0、1， +，\ cdot，\ geq，>，\ wedge，\ vee，\ neg \} $组成的符号符号的公式正确。 。现在，ER是所有问题的家族，这些家族允许多项式时间降低到ETR。众所周知，np $ \ subseteq $ er $ \ subseteq $ pspace。我们将注意力限制在CCSP上，并具有附加限制（$ x + y = z $）和其他一些轻度的技术状况。以前，已经显示出乘法约束（$ x \ cdot y = z $），平方约束（$ x^2 = y $）或反转约束（$ x \ cdot y = 1 $）足以建立ER-完整性。如下所示，我们以最大的平等约束来扩展这一点。我们表明，CCSP（具有附加限制和其他轻度技术状况）具有任何一个表现良好的弯曲平等约束（$ f（x，y）= 0 $）的CCSP是ER的曲线限制（$ F（x，y）= 0 $）。我们将结果进一步扩展到不平等约束。我们表明，任何行为良好的凸出弯曲且行为良好的凹陷弯曲的不平等约束（$ f（x，y）\ geq 0 $ and $ g（x，x，y）\ geq 0 $）暗示着班级的ER完整性这种CCSP。

我们根据描述逻辑ALC和ALCI介绍并研究了本体论介导的查询的几个近似概念。我们的近似值有两种：我们可以（1）用一种以易访问的本体语言为例，例如ELI或某些TGD，以及（2）用可拖动类的一个替换数据库，例如其treewidth的数据库，由常数界定。我们确定所得近似值的计算复杂性和相对完整性。（几乎）所有这些都将数据复杂性从Conp-Complete降低到Ptime，在某些情况下甚至是固定参数可拖动和线性时间。虽然种类（1）的近似也降低了综合复杂性，但这种近似（2）往往并非如此。在某些情况下，联合复杂性甚至会增加。

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.

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

We consider the algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to fit a given set of data points. This problem is known as empirical risk minimization in the machine learning community. We show that the problem is $\exists\mathbb{R}$-complete. This complexity class can be defined as the set of algorithmic problems that are polynomial-time equivalent to finding real roots of a polynomial with integer coefficients. Furthermore, we show that arbitrary algebraic numbers are required as weights to be able to train some instances to optimality, even if all data points are rational. Our results hold even if the following restrictions are all added simultaneously. $\bullet$ There are exactly two output neurons. $\bullet$ There are exactly two input neurons. $\bullet$ The data has only 13 different labels. $\bullet$ The number of hidden neurons is a constant fraction of the number of data points. $\bullet$ The target training error is zero. $\bullet$ The ReLU activation function is used. This shows that even very simple networks are difficult to train. The result explains why typical methods for $\mathsf{NP}$-complete problems, like mixed-integer programming or SAT-solving, cannot train neural networks to global optimality, unless $\mathsf{NP}=\exists\mathbb{R}$. We strengthen a recent result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021].