CIF: Small: String Submodularity and Near-Optimal Adaptive Control and Sensing

CIF：小：字符串子模块性和近乎最优的自适应控制和传感

• 批准号: 1422658
• 负责人: Ali Pezeshki
• 金额: $ 50万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422658&HistoricalAwards=false
• 关键词: CIF; Small; String; Submodularity; Near

In a great number of problems in engineering and applied science, we are faced with optimally choosing a sequence of actions over a finite horizon to maximize an objective function. The problem arises in sequential decision making in engineering, economics, management science, and medicine. However, in such problems, optimal strategies are hard to compute in general. On the other hand, greedy strategies, though suboptimal in general, are easy to compute because they only involve finding an action at each stage to maximize the step-wise gain in the objective function. This research provides a systematic method to bound the suboptimality of greedy strategies relative to optimal strategies. This research has broad impact both in application areas and educationally.New results extend the notion of submodular functions over sets to submodular functions over strings. These results establish that, under string submodularity, the greedy strategies achieve a performance that is no worse than a factor of (approximately) 63% of optimal strategies in sequential decision problems. Under additional curvature conditions, this bound becomes even sharper. This research involves a number of issues related to this new string-submodularity framework as follows: 1) Identifying canonical problems in sensing and control that can be treated systematically using the string-submodularity framework; 2) Bounding the performance of approximate dynamic programming (ADP) by reducing a given ADP method into a greedy strategy associated with an induced submodular string function; 3) Going beyond submodularity by investigating relaxed definitions of submodularity and curvature in order to greatly expand the scope of the applicability of the theory.

在工程和应用科学方面的许多问题中，我们面临最佳选择，而不是有限的视野来最大化目标函数。问题是在工程，经济学，管理科学和医学中的顺序决策中引起的。但是，在此类问题中，总体上很难计算最佳策略。另一方面，贪婪的策略虽然通常是最佳的，但很容易计算，因为它们仅涉及在每个阶段找到一个动作，以最大程度地提高目标函数的逐步增长。这项研究提供了一种系统的方法，可以将贪婪策略相对于最佳策略的次序限制。这项研究在应用领域和教育方面都有广泛的影响。新的结果将表函数的概念扩展到集合上的集合概念到字符串的下函数。这些结果表明，在字符串的义务下，贪婪的策略达到的绩效并不比（约为）在顺序决策问题中的最佳策略的63％差。在额外的曲率条件下，这种界限变得更加尖锐。这项研究涉及与此新的弦乐模块化框架相关的许多问题，如下所示：1）在感应和控制中识别可以使用字符串 - 解换框架进行系统处理的经典问题； 2）通过将给定的ADP方法简化为与诱导的下弦函数相关的贪婪策略来界定近似动态编程（ADP）的性能； 3）通过调查了子二次性和曲率的轻松定义，以大大扩大理论的适用性范围，超越了义务。