通过将基于图的多智能体路径规划与网络流问题相连接，本文研究表明前者可以归纳为后者，进而实现了组合网络流算法及一般线性规划技术应用于基于图的多智能体路径规划问题。此外，在研究中我们还证明了当目标具有排列不变性的情况下，问题仅有一个可行解路径集，该集合具有不超过 $n+V-1$ 的最大完成时间，并提供了一个完整的算法以在 $O (nVE)$ 时间内找到这样的解决方案。最后，我们研究了可行解的时间和距离优化，表明它们具有成对帕累托优化结构，并提供了优化这两个实际目标的有效算法。

Apr, 2012

我们考虑投射在图上的匿名多智能体路径规划（AMAPF）问题，给定了一组目标顶点，每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题，通过将其转化为特殊类型的图搜索问题，即在输入图引导下寻找最大流问题来求解。然后，我们提出了一种利用批量搜索状态的特定搜索算法，将搜索空间压缩、存储和扩展为单一状态，从而显著降低了运行时间和内存占用。实验证明，该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例，并表现出卓越的性能优势。

Dec, 2023

本论文提出了一种新的内点法来处理最大流问题，该算法通过将其应用于线性规划制定最大流、最小费用流和有损广义最小费用流的问题，并借鉴 Daitch 和 Spielman 的方法分析，最终在 O (m√nlogO (1)(U/ε)) 的时间内解决这些问题，同时在使用 Spielman 和 Peng 的 Laplacian 系统求解器进行并行化后，达到了 O (√nlogO (1)(U/ε)) 和 O (m√nlogO (1)(U/ε)) 的时间。

Dec, 2013

本文研究了 BIN PACKING 的两个泛化问题，即在路径上的不可分割问题（UFP）和存储分配问题（SAP），证明了这两个问题不支持渐近多项式时间逼近方案（APTAS），但在某些特定的解法情况下能够得出逼近比。同时提出了一种逼近算法，可在合理的时间内求解这些问题。

Feb, 2022

本文提出了对抗性 SSP 模型，包含时间上对成本的不良变化和未知转移，其开发了第一个对抗性 SSP 算法，并证明了高概率的回报上限。

Jun, 2020

本文介绍了一个基于约束的随机规划问题，其中利用整数线性规划方法确保了确定性决策，同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程，并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。

Feb, 2023

本研究证明了置信传播算法在容量约束最小费用网络流问题上的全多项式运行时间，还证明了算法的随机逼近方案，这提供了理论依据支持置信传播算法成为解决一类重要的优化问题的有吸引力的方法。

Apr, 2010

本论文提出了两种新的算法，用于计算带有实数边权（可能为负数）的有向图的全源最短路径。这两种算法运行时间复杂度为 O (n^2w_d)，可用于空间和时间推理，比 Floyd-Warshall 算法和 Johnson 算法更快，并且具有规划和调度社区的相关性。

Jan, 2014

研究了已知地形中团队智能体的 TAPF（组合目标分配和路径查找）问题，提出了 CBM（基于冲突的最小成本流）算法，结合匿名和非匿名多智能体路径查找算法的思想，可用于处理各种规模的 TAPF 实例，并可适用于模拟仓库系统。

Dec, 2016

本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。

Nov, 2014