State-Space Reduction for Flexible and Approximate Computation

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

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.