A Local Search Approach for Batch Repair With Configuration Neighbor and Sub-Degree in Circuit System

Abstract

The goal of automated troubleshooting is to diagnose and fix a system by repairing its abnormal behaviors, and this process has wide application. Heuristic search is an efficient way to solve troubleshooting problems, such as the batch repair problem (BRP), and heuristic search aims to minimize the costs of repairing a circuit system. The local search method is an efficient search approach and has very good performance in many areas. The key to this method is the modeling of “neighbor” and the search strategy. This paper proposes a local search approach for batch repair with configuration neighbors and sub-degree (CNASD). First, we define configuration neighbors in the BRP. Second, we propose three strategies to guide the search process, namely, best diagnosis with the highest probability component (BDHC), configuration neighbor with aspiration (CNA) and minimal sub-degree. Experimentally, compared with state-of-the-art batch repair algorithms that use heuristic search, our algorithm performs better in terms of the average / maximum repair cost and average / maximum runtime (decreased by up to one order of magnitude) on ISCAS'85 and ITC'99 systems, which are the standard combinational circuit systems.

Keywords

• Local search
• model-based diagnosis
• batch repair
• configuration neighbor
• sub-degree