在未知奖励与成本的图中，用贝叶斯方法平衡探索与利用，优化路径决策。
Bayesian Graph Traversal
- 基于高斯过程建模未知节点奖励与边成本，动态更新信念。
- 证明问题为NP难，提出可兼顾探索与利用的启发式策略。
- 适用于无人机公共安全巡检等需权衡信息收集与行动效率场景。
本研究探讨不确定图上基于贝叶斯决策分析的遍历方法。旅行者在图中移动，首次访问节点可获得奖励，每次穿越边需支付代价。旅行者知晓图的邻接矩阵和起始位置，但未知各节点奖励与边代价。他采用贝叶斯框架，以高斯过程先验表示对这些值的信念，并致力于最大化其期望效用。从决策分析视角出发，我们为这一耦合信息收集与路径规划的问题设计了序贯决策策略。证明该问题是NP难的，并推导出最优行走路径的性质，这些性质可转化为平衡探索与利用的启发式规则。通过聚焦无人飞行系统在公共安全中的应用案例，在大量Erdos-Renyi随机图设置下实证评估了策略性能。
原文摘要 · Abstract (English)
This research considers Bayesian decision-analytic approaches toward the traversal of an uncertain graph. Namely, a traveler progresses over a graph in which rewards are gained upon a node's first visit and costs are incurred for every edge traversal. The traveler knows the graph's adjacency matrix and his starting position but does not know the rewards and costs. The traveler is a Bayesian who encodes his beliefs about these values using a Gaussian process prior and who seeks to maximize his expected utility over these beliefs. Adopting a decision-analytic perspective, we develop sequential decision-making solution strategies for this coupled information-collection and network-routing problem. We show that the problem is NP-Hard and derive properties of the optimal walk. These properties provide heuristics for the traveler's problem that balance exploration and exploitation. We provide a practical case study focused on the use of unmanned aerial systems for public safety and empirically study policy performance in myriad Erdos-Renyi settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。