Improving Heuristic Function of Cost-Based Abduction System Using Real-Time Heuristic Search

摘要

Cost-based abduction, which can find a best explanation for a given observation by assuming some hypothesis, is an important framework of inference because it is applied to diagnosis, design, planning, natural language understanding, and so on. However, slow reasoning speed is a crucial drawback. In order to overcome this problem, previous work achieved an efficient system, and a search control technique of A{sup}* search was introduced into cost-based abduction. However, the system has the problem that space complexity is very large because it has to store all of the many nodes. In this paper, we introduced real-time heuristic search by which the user can set up look-ahead depth and store only the best node. We also introduced a new heuristic function in order to inference successfully and speed up inconsistency processing. We examined the validity of our proposed method with a diagnostic problem of a logic circuit.