Markov Decision Processes and Discrete Optimization

马尔可夫决策过程和离散优化

• 批准号: 0600538
• 负责人: Eugene Feinberg
• 金额: $ 30万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-01 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600538&HistoricalAwards=false
• 关键词: Markov; Decision; Processes; Discrete; Optimization

This grant provides funding for the investigation of the links between two important classes of optimization problems: stochastic dynamic programming, also known under the name of Markov Decision Processes, and discrete optimization. In particular, this project studies applications of discrete optimization to stochastic dynamic programming, applications of stochastic dynamic programming to discrete optimization, and applications of stochastic and discrete optimization to production, service, telecommunication, and surveillance systems. The first task of this project studies classification problems for Markov Decision Processes. These problems are important for the implementation of efficient algorithms for Markov Decision Processes. The second task investigates representations of discrete optimization problems via Markov Decision Processes and develops new solution methods for certain discrete optimization problems. The third task develops efficient algorithms for several production, service, telecommunication, and homeland security problems.If successful, this research will develop new methodologies and algorithms to solve important optimization problems. It will develop classification algorithms for Markov Decision Processes that identify their specific structural properties. Such algorithms are important for efficient optimization of Markov Decision Processes, which are broadly used for various applications such as control of production and service systems, reinforcement learning in artificial intelligence, and decision making. This project will also study new approaches to important discrete optimization problems including the Hamiltonian Cycle, Traveling Salesman, and Generalized Pinwheel Problems. These approaches are based on the representations of discrete optimization problems via Markov Decision Processes and studying the properties of these representations. This project will develop new solution techniques for certain production, service, and telecommunication applications by developing efficient scheduling, admission, and resource allocation algorithms. This project will contribute to the development of human resources in science and engineering, to technological progress, and to mutually beneficial interactions between industry and academia.

该补助金为两类重要的优化问题之间的联系的调查提供资金：随机动态规划，也称为马尔可夫决策过程和离散优化。 特别是，这个项目研究离散优化的随机动态规划的应用，随机动态规划的离散优化的应用，以及随机和离散优化的生产，服务，电信和监控系统的应用。 本计画的第一个任务是研究马尔可夫决策过程的分类问题。 这些问题对于马尔可夫决策过程有效算法的实现具有重要意义。 第二个任务通过马尔可夫决策过程研究离散优化问题的表示，并为某些离散优化问题开发新的解决方法。第三个任务是为一些生产、服务、电信和国土安全问题开发有效的算法。如果成功，本研究将开发新的方法和算法来解决重要的优化问题。 它将开发马尔可夫决策过程的分类算法，以确定其特定的结构特性。这些算法对于马尔可夫决策过程的有效优化非常重要，马尔可夫决策过程广泛用于各种应用，例如生产和服务系统的控制，人工智能中的强化学习和决策。 这个项目还将研究新的方法来解决重要的离散优化问题，包括哈密尔顿循环，旅行推销员和广义风车问题。 这些方法是基于离散优化问题通过马尔可夫决策过程的表示，并研究这些表示的属性。 该项目将通过开发有效的调度、接纳和资源分配算法，为某些生产、服务和电信应用开发新的解决方案技术。该项目将有助于科学和工程领域的人力资源开发，技术进步以及工业界和学术界之间的互利互动。