Optimal Node Visitation in Stochastic Digraphs
Optimal Node Visitation in Stochastic Digraphs
复制标题
随机有向图中的最优节点访问
DOI：
--
复制
发表时间：
2008
影响因子：
6.8
通讯作者：
S. Reveliotis
中科院分区：
文献类型：
--
作者：
T. Bountourelis;S. Reveliotis
本文解决的最优节点访问（ONV）问题涉及随机图中节点子集指定次数的访问，同时最小化对该图中另一个节点的预期访问。所提出的结果首先将 ONV 问题表述为随机最短路径问题，随后他们开发了一种计算上易于处理且渐近最优的次优策略。特别是，随着基本访问需求统一缩放到无穷大，该策略的预期性能与最优策略的预期性能的比率收敛于 1。此外，结果表明，在一些更强的假设下，随着访问要求缩放到无穷大，该策略的性能与最优策略的性能的差异仍然统一受常数限制。最后，结果表明，对于某些问题结构，所考虑的策略承认其性能的封闭形式表征，从而使其能够优化参数化并有效集成到效率更高的自适应控制方案中。
The optimal node visitation (ONV) problem addressed in this paper concerns the visitation of a subset of nodes in a stochastic graph a specified number of times, while minimizing the expected visits to another node in this graph. The presented results first provide a formulation of the ONV problem as a stochastic shortest path problem, and subsequently they develop a suboptimal policy that is computationally tractable and asymptotically optimal. In particular, it is established that the ratio of the expected performance of this policy to the expected performance of an optimal policy converges to one, as the underlying visitation requirements are scaled uniformly to infinity. Furthermore, it is shown that under some stronger assumptions, the divergence of the performance of this policy from the performance of the optimal policy remains uniformly bounded by a constant, as the visitation requirements are scaled to infinity. Finally, it is shown that, for certain problem structures, the considered policy admits a closed-form characterization of its performance, which subsequently enables its optimized parameterization and its efficient integration into adaptive control schemes of even higher efficiency.