State-Space Reduction for Flexible and Approximate Computation

状态空间缩减以实现灵活且近似的计算

• 批准号: 9619554
• 负责人: Weixiong Zhang
• 金额: $ 22.8万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-06-01 至 2000-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9619554&HistoricalAwards=false
• 关键词: State; Space; Reduction; Flexible; Approximate

Flexible and approximate computation considers how to allocate limited computation resources and trade solution quality for reduced computational cost in order to optimize overall performance of an autonomous system or agent. The goal of this research is to develop general, effective, and efficient methods for flexible and approximate computation. The approach, based on heuristic state-space search, consists of a set of reductions that help to restrict search effort to the most promising areas of a problem space. Specifically, a state-space reduction is a process of reducing a state space that is difficult to search into a less complex state space that is easier to explore and more likely to contain high-quality solutions. After reduction, the optimal goal in the reduced state space is found and used as an approximate solution to the original problem. Better solutions can be found incrementally, with refined reduction processes. One important issue in flexible computation is to find performance profiles of a computation which measure system performance in terms of required computation resources. This research also considers how to construct closed-form performance profiles by analyzing the expected complexity of state-space search algorithms. The results of this research will provide effective methods for real-time scheduling and on-line searching, and provide intrinsic insight into the computational behavior of state-space search methods.

灵活和近似计算考虑如何分配有限的计算资源，并以降低的解质量为代价， 计算成本，以便 优化 自治系统或代理的整体性能。 本研究的目标是开发通用的，有效的，高效的灵活和近似计算的方法。 该方法，基于启发式状态空间搜索，由一组减少，有助于限制搜索工作的问题空间的最有前途的领域。 具体地，状态空间缩减是将难以搜索的状态空间缩减为更容易探索并且更可能包含高质量解的较不复杂的状态空间的过程。 约简后，在约简的状态空间中找到最优目标，并将其用作 原问题的近似解。 可以逐步找到更好的解决方案，并改进减少过程。 灵活计算中的一个重要问题是找到计算的性能配置文件，该性能配置文件根据所需的计算资源来测量系统性能。 本研究亦考虑如何借由分析状态空间搜寻演算法的预期复杂度，建构出封闭式的效能剖面。 本研究的结果将提供有效的方法，实时调度和在线搜索，并提供内在的洞察状态空间搜索方法的计算行为。