RETE Implementations towards Graph Heuristic Search

Pattern matching is repeated many times during any search algorithm. In heuristic search, to expand a node all production rules should be tested against that node to find appropriate ones. RETE algorithm was proposed by Charles Forgy to efficiently solve pattern matching problems in production systems. In this project, I implemented a few versions of RETE algorithm and use it to select the appropriate rules before expanding each node. RETE algorithm was tested using IDA*. My results showed that Basic RETE algorithm could not decrease the required time for IDA*. However, customized and enhanced versions of RETE could enhance IDA* performance.

The contributions in this project are the following:

  1. Develop the “Basic RETE” algorithm: RETE has the reputation in the literature for its extreme difficulty in implementation. In this project, I implemented it as a generic purpose matching algorithm.
  2. Customize Basic RETE to work with IDA* algorithm using rPSVN rules: rPSVN simplify the matching problem in IDA*. The nature of heuristic search problem itself simplify RETE requirements. For example, no need to add any new rule on the fly. After developing the generic purpose RETE (Basic RETE), I customized it to work with heuristic search and rPSVN rules (Customized RETE).
  3. Enhanced RETE: It turns out that “Customized RETE” did not show any enhancement on IDA* speed comparing to one of naive matching algorithms. I proposed a new version of RETE (Enhanced RETE). This version speed up IDA* by about $87\%$ with 8 puzzle problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s