Abstract
Search is one of the central problem-solving paradigms in Artificial Intelligence. Unfortunately, search can be quite expensive. Problem-solvers frequently use rejection heuristics to lower the cost of their searches. Unfortunately, these rejection heuristics can also prevent a problem-solver from solving a problem. I describe a new learning algorithm, SHAPeS, that enables the learner to modify both rejection heuristics implemented explicitly as search control rules and those implemented implicitly by either being embedded within the program code or by being incorporated into the search space generators. The SHAPeS learning algorithm only requires a solution to be supplied rather than needing that solution's problem-solving trace. This frees the system from having to find the solution itself. The SHAPeS algorithm is generally applicable to search-based problem-solvers. I discuss both the conditions for the algorithm's correctness and its computational complexity. I implemented a restricted version of SHAPeS, called Bacall, and in this thesis report on the results of experiments conducted to assess the utility of the Bacall learned modifications. The experiments show that not only can Bacall learned modifications extend a problem-solver coverage but can also enable it to run faster. The experiments also compare the utility of the Bacall learned modifications with the utility of current approaches to modifying rejection heuristics. The experiments show that Bacall learned modifications can improve the problem-solver's performance more than comparable modifications learned by the alternative approaches. Lastly, I identify three types of search control knowledge interactions that complicate the analysis of rejection heuristics' effects upon a problem-solver's coverage. These interactions cause modifications to a problem-solver's search control knowledge to have counter-intuitive effects upon the problem-solver's coverage. For example, removing rejection rules or specializing their preconditions can cause the problem-solver to become unable solve some problems. I also identify conditions that are sufficient to eliminate these types of interactions and that simplify the analysis of the effect of modifying a problem-solver's search control logic upon its coverage.