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.
