我们提出了一种新的算法A * + BFHS，用于解决单位成本运算符的问题，其中A *和IDA *由于内存限制和/或存在同一对节点之间的许多不同路径而失败。a * + bfhs基于*和广度的启发式搜索（bfhs）。a * + bfhs与算法中的优点相结合，即*的节点订购，bfhs的内存节省以及算法重复检测。在简单的问题上，a * + bfhs与a相同。在艰难问题上，它比*慢，但节省了大量的内存。与BFIDA *相比，A * + BFHS在各种规划域上减少了几次搜索时间和/或内存要求。

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

决策树学习是机器学习中广泛使用的方法，在需要简洁明了的模型的应用中受到青睐。传统上，启发式方法用于快速生产具有相当高准确性的模型。然而，一个普遍的批评是，从精度和大小方面，所产生的树可能不一定是数据的最佳表示。近年来，这激发了最佳分类树算法的发展，这些算法与执行一系列本地最佳决策的启发式方法相比，在全球范围内优化决策树。我们遵循这一工作线，并提供了一种基于动态编程和搜索的最佳分类树的新颖算法。我们的算法支持对树的深度和节点数量的约束。我们方法的成功归因于一系列专门技术，这些技术利用了分类树独有的属性。传统上，最佳分类树的算法受到了高运行时的困扰和有限的可伸缩性，但我们在一项详细的实验研究中表明，我们的方法仅使用最先进的时间所需的时间，并且可以处理数十个数据集的数据集在数千个实例中，提供了几个数量级的改进，并特别有助于实现最佳决策树的实现。

传统上，启发式搜索一直依赖于手工制作或编程派生的启发式方法。神经网络（NNS）是更新的强大工具，可用于从州学习复杂的映射到成本到启发式方法。但是，他们缓慢的单个推理时间是一个很大的开销，可以在优化的启发式搜索实现中大大减少计划时间。最近的一些作品描述了利用NN的批处理计算的方法，以减少计划中的开销，同时保持（子）最优性的界限。但是，所有这些方法在建立批处理的同时以“阻止”方式使用了NN启发式方法，并且忽略了通常可以使用的快速计算可接受的启发式方法（例如现有的经典启发式启发术）。我们介绍了一种非阻滞批次A*（NBBA*），这是一种有界的次优方法，它懒洋洋地分批计算NN启发式方法，同时允许通过非NN启发式启发术告知扩展。我们展示了与当前的阻止替代方案相比，这种微妙但重要的变化如何导致扩展大幅减少，并看到该性能与计算出的NN和快速非NN启发式的批处理差异有关。

复杂的推理问题包含确定良好行动计划所需的计算成本各不相同的状态。利用此属性，我们提出了自适应亚go搜索（ADASUBS），这是一种适应性地调整计划范围的搜索方法。为此，ADASUBS在不同距离上产生了不同的子目标。采用验证机制来迅速滤除无法到达的子目标，从而使人专注于可行的进一步子目标。通过这种方式，ADASUBS受益于计划的效率更长的子目标，以及对较短的计划的良好控制。我们表明，ADASUB在三个复杂的推理任务上大大超过了层次规划算法：Sokoban，The Rubik的Cube和不平等现象证明了基准INT，为INT设定了新的最先进。

快速扩大的神经网络模型在单个设备上运行越来越具有挑战性。因此，在多个设备上的模型并行性对于确保训练大型模型的效率至关重要。最近的建议在长时间处理时间或性能差。因此，我们提出了Celeritas，这是一个快速的框架，用于优化大型型号的设备放置。Celeritas在标准评估中采用简单但有效的模型并行化策略，并通过一系列调度算法生成位置策略。我们进行实验以在许多大型模型上部署和评估Celeritas。结果表明，与大多数高级方法相比，Celeritas不仅将放置策略生成时间减少26.4 \％，而且还将模型运行时间提高了34.2 \％。

通过深度神经网络实现的A*算法的启发式函数的优化通常是通过最大程度地减少正方形根损失的目标成本估计值来完成的。本文认为，这不一定会导致对A*算法的更快搜索，因为其执行依赖于相对值而不是绝对值。作为缓解措施，我们提出了L*损失，该损失是A*搜索中过度扩展状态的数量上限。当用于优化最先进的深度神经网络的L*损失，用于在索科班等迷宫领域的自动化计划和带有传送的迷宫，可显着改善解决问题的比例，基础计划的质量，并降低扩大状态的数量达到约50％

本文收集了提交给核心挑战2022的求解器和ISR实例的所有描述。

增量图诸如D * Lite重用之前的算法，并且可能部分搜索，以加快后续路径规划任务。在本文中，我们有兴趣开发增量图搜索算法，以便寻找问题，同时优化旅行风险，到达时间等的多个目标。这是具有挑战性的，因为在多目标设置中，“帕累托 - 最优” “解决方案可以对图表的大小呈指数级增长。本文提出了一种新的多目标增量搜索算法，称为基于多目标路径的D * Lite（MOPBD *），它利用基于路径的扩展策略来修剪主导的解决方案。此外，我们介绍了MOPBD *的两个变体，以进一步提高搜索效率，并近似帕累托最优的前沿。我们在数值上评估了MOPBD *及其在各种地图中的变体的性能，其中包括两个和三个目标。结果表明，我们的方法比从头开始搜索的方法更有效，并且比多目标路径规划的现有增量方法快速升至幅度速度快。

The Multi-Objective Shortest Path Problem, typically posed on a graph, determines a set of paths from a start vertex to a destination vertex while optimizing multiple objectives. In general, there does not exist a single solution path that can simultaneously optimize all the objectives and the problem thus seeks to find a set of so-called Pareto-optimal solutions. To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees. However, these MOA* algorithms often suffer from high memory usage, especially when the branching factor (i.e., the number of neighbors of any vertex) of the graph is large. This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime. In this paper, we first extend the notion of "partial expansion" (PE) from single-objective to multi-objective and then fuse this new PE technique with EMOA*, a recent runtime efficient MOA* algorithm. Furthermore, the resulting algorithm PE-EMOA* can balance between runtime and memory efficiency by tuning a user-defined hyper-parameter.

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

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

Heuristic search algorithms, e.g. A*, are the commonly used tools for pathfinding on grids, i.e. graphs of regular structure that are widely employed to represent environments in robotics, video games etc. Instance-independent heuristics for grid graphs, e.g. Manhattan distance, do not take the obstacles into account and, thus, the search led by such heuristics performs poorly in the obstacle-rich environments. To this end, we suggest learning the instance-dependent heuristic proxies that are supposed to notably increase the efficiency of the search. The first heuristic proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one (computed offline at the training phase). Unlike learning the absolute values of the cost-to-go heuristic function, which was known before, when learning the correction factor the knowledge of the instance-independent heuristic is utilized. The second heuristic proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path. This heuristic can be utilized in the Focal Search framework as the secondary heuristic, allowing us to preserve the guarantees on the bounded sub-optimality of the solution. We learn both suggested heuristics in a supervised fashion with the state-of-the-art neural networks containing attention blocks (transformers). We conduct a thorough empirical evaluation on a comprehensive dataset of planning tasks, showing that the suggested techniques i) reduce the computational effort of the A* up to a factor of $4$x while producing the solutions, which costs exceed the costs of the optimal solutions by less than $0.3$% on average; ii) outperform the competitors, which include the conventional techniques from the heuristic search, i.e. weighted A*, as well as the state-of-the-art learnable planners.

基于冲突的搜索（CBS）是一种广泛使用的算法，用于最佳地求解多代理探路（MAPF）问题。 CBS的核心思想是运行层次搜索，当在高级别的解决方案树上探索候选者的树时，在低级别上进行了针对特定代理的个人计划（受某些约束）进行。为了使运行时间的权衡取得最佳性，设计了有限的子最佳CB的不同变体，这改变了CBS的高级和低级搜索程序。此外，CBS的任何时间变体都存在将焦点搜索（FS）应用于CBS的高级搜索 - 任何时间BCB。然而，当我们简单地重新启动cbs的cbs与较低的亚XB绑定时，没有对这种算法的性能的全面分析。这项工作旨在填补这一空白。此外，我们介绍并评估了另一个在CBS上使用FS的CBS的随时随地。从经验上讲，我们证明其行为主要与任何时间BCB所证明的行为不同。最后，我们比较这两种算法从头开始，并表明在两个级别的CBS上使用焦点搜索在广泛的设置中可能是有益的。

符合使用机器学习的不断增长的趋势，帮助解决组合优化问题，一个有希望的想法是通过使用学习的策略来改善混合整数编程（MIP）分支和绑定树内的节点选择。以前使用模仿学习的工作指示通过学习自适应节点搜索顺序来获取节点选择策略的可行性。相比之下，我们的模仿学习策略仅专注于学习节点的孩子中的哪一个选择。我们介绍了一个脱机方法，用于在两个设置中学习这样的策略：一个通过致力于修剪节点的启发式;一个是从叶子精确和背溯以保证找到最佳整数解决方案的备用。前一个设置对应于困扰期间的儿童选择器，而后者则类似于潜水启发式。我们在热情和确切的设置中将策略应用于流行的开源求解器SCIP。五个MIP数据集的经验结果表明，我们的节点选择策略比文献中最先进的先例更快地导致解决方案。虽然我们在精确解决方案的时间内没有击败高度优化的SCIP状态基准节点选择器，但如果预测模型的准确性足够，我们的启发式政策比所有基线都具有始终如一的最佳最优性差距。此外，结果还表明，当应用时间限制时，我们的启发式方法发现比测试大多数问题中所有基线的更好的解决方案。我们通过表明学习的政策模仿了SCIP基线来解释结果，但没有后者早期的暴跌中止。我们的建议是，尽管对文献的清晰改进，但这种MIP儿童选择器在更广泛的方法中更好地使用MIP分支和束缚树决策。

路由问题是许多实际应用的一类组合问题。最近，已经提出了端到端的深度学习方法，以了解这些问题的近似解决方案启发式。相比之下，经典动态编程（DP）算法保证最佳解决方案，但与问题大小严重规模。我们提出了深入的政策动态规划（DPDP），旨在将学习神经启发式的优势与DP算法结合起来。 DPDP优先确定并限制DP状态空间，使用来自深度神经网络的策略进行培训，以预测示例解决方案的边缘。我们在旅行推销员问题（TSP）上评估我们的框架，车辆路由问题（VRP）和TSP与时间窗口（TSPTW），并表明神经政策提高了（限制性）DP算法的性能，使其对强有力的替代品具有竞争力如LKH，同时也优于求解TSP，VRP和TSPTWS的大多数其他“神经方法”，其中包含100个节点。

图中最短的路径问题是理论和应用的基石。现有的工作是边缘重量访问时间，但通常会忽略边缘重量计算时间。在本文中，我们提出了一个加权有向图的广义框架，其中每个边缘的成本可以通过多个估计器动态估计，该估计器提供不同的成本范围和运行时间。这引发了几个通用的最短路径问题，可以优化路径成本的不同方面，同时需要保证成本不确定性，从而为建模现实问题提供了更好的基础。我们提供完整的，任何时间来解决这些问题，并提供解决方案质量的保证。

Cohn and Umans proposed a framework for developing fast matrix multiplication algorithms based on the embedding computation in certain groups algebras. In subsequent work with Kleinberg and Szegedy, they connected this to the search for combinatorial objects called strong uniquely solvable puzzles (strong USPs). We begin a systematic computer-aided search for these objects. We develop and implement constraint-based algorithms build on reductions to $\mathrm{SAT}$ and $\mathrm{IP}$ to verify that puzzles are strong USPs, and to search for large strong USPs. We produce tight bounds on the maximum size of a strong USP for width $k \le 5$, construct puzzles of small width that are larger than previous work, and improve the upper bounds on strong USP size for $k \le 12$. Although our work only deals with puzzles of small-constant width, the strong USPs we find imply matrix multiplication algorithms that run in $O(n^\omega)$ time with exponent $\omega \le 2.66$. While our algorithms do not beat the fastest algorithms, our work provides evidence and, perhaps, a path to finding families of strong USPs that imply matrix multiplication algorithms that are more efficient than those currently known.

近年来，深入的强化学习（RL）在各种组合搜索领域（例如两人游戏和科学发现）中都取得了成功。但是，直接在计划域中应用深度RL仍然具有挑战性。一个主要的困难是，如果没有人工制作的启发式功能，奖励信号除非学习框架发现任何解决方案计划，否则奖励信号将保持零。随着计划的最小长度的增长，搜索空间变为\ emph {指数更大}，这是计划实例的严重限制，该实例的计划最小计划长度为数百到数千步。以前的学习框架可以增强使用深神经网络和额外生成的子观念的图形搜索在各种具有挑战性的计划域中取得了成功。但是，生成有用的子目标需要广泛的领域知识。我们提出了一种独立于域的方法，该方法可以通过图值迭代来增强图形搜索，以求解针对域特有的求解器无法实现的硬计划实例。特别是，我们的方法还没有仅从发现的计划中获得学习信号，而是从未达到目标状态的失败尝试中学习。图值迭代组件可以利用本地搜索空间的图形结构并提供更有信息的学习信号。我们还展示了如何使用课程策略来平滑学习过程并对图形值迭代量表的完整分析并实现学习。

最佳路径规划是在优化目标的起始和目标之间找到有效状态的问题。知情路径规划算法顺序他们的搜索与特定于问题的知识表达为启发式，并且可以比未表现算法更有效的数量级。启发式最有效的是，当他们准确且计算地廉价才能评估，但这些通常是矛盾的特征。这使得适当的启发式难以满足许多问题。本文提出了两个几乎肯定的渐近最优采样的路径规划算法，以解决这一挑战，自适应地通知的树木（AIT *）和精力知的树木（EIT *）。这些算法使用非对称双向搜索，其中两个搜索彼此连续通知。这允许AIT *和EIT *通过同时计算和利用越来越准确，特定于问题的启发式来改善规划性能。 AIT *和EIT *相对于其他基于样品的算法的好处是在优化路径长度和障碍物间隙的十二个问题上进行了十二个问题。实验表明，AIT *和EIT *优于优化障碍物清除的问题的其他算法，其中先验成本启发式往往是无效的，并且仍然对最小化路径长度的问题表现良好，这种启发式通常是有效的。