提出新方法在任意图上学习可执行的动态运输策略。
Generalized Schrödinger Bridge on Graphs
- 基于似然优化学习轨迹级控制策略，避免全局求解
- 能准确适应复杂图结构，同时优化中间状态成本
- 适合需要成本感知动态运输的场景，如物流、调度
图上的运输是多个领域中的基本挑战，决策必须遵守拓扑与操作约束。现有图运输方法缺乏可执行性，依赖苛刻假设，难以泛化至稀疏拓扑，且随图规模和时间跨度增长而效率下降。为此，我们提出广义薛定谔桥图模型（GSBoG），一种新型可扩展的数据驱动框架，用于在任意图上学习可执行的连续时间马尔可夫链（CTMC）控制策略，支持状态成本增强的动力学。GSBoG通过似然优化，在满足端点分布的同时，优化状态相关运行成本下的中间行为，学习轨迹级策略，避免密集全局求解，提升可扩展性。在真实世界复杂图拓扑上的大量实验表明，GSBoG能可靠学习到符合拓扑结构、精确且优化应用特定中间状态成本的策略，展现出广泛适用性，为通用图上的成本感知动力运输开辟新路径。
原文摘要 · Abstract (English)
Transportation on graphs is a fundamental challenge across many domains, where decisions must respect topological and operational constraints. Despite the need for actionable policies, existing graph-transport methods lack this expressivity. They rely on restrictive assumptions, fail to generalize across sparse topologies, and scale poorly with graph size and time horizon. To address these issues, we introduce Generalized Schrödinger Bridge on Graphs (GSBoG), a novel scalable data-driven framework for learning executable controlled continuous-time Markov chain (CTMC) policies on arbitrary graphs under state cost augmented dynamics. Notably, GSBoG learns trajectory-level policies, avoiding dense global solvers and thereby enhancing scalability. This is achieved via a likelihood optimization approach, satisfying the endpoint marginals, while simultaneously optimizing intermediate behavior under state-dependent running costs. Extensive experimentation on challenging real-world graph topologies shows that GSBoG reliably learns accurate, topology-respecting policies while optimizing application-specific intermediate state costs, highlighting its broad applicability and paving new avenues for cost-aware dynamical transport on general graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。