Search and State Space : Causal Networks

The diagram below is an example of a causal network from a real-world manufacturing business model. Causal networks (and Bayesian or belief networks which are similar) are Directed Acyclic Graphs (DAG’s) made up of nodes, each representing a concept and arcs (or edges) which represent an influence. For example productivity affects assembly cost, sales price and assembly design. The degree to which one concept affects another can be represented as a weight on the arc (these are listed below the diagram for clarity). Such networks can be used to aid decision making and provide Deep Knowledge for Rule Based Systems applications.

Weights and connections represented as prolog relationships:

connected(productivity,assembly_design,30).

connected(productivity,assembly_cost,25).

connected(productivity,sales_price,15).

connected(economy_conditions,assembly_cost,15).

connected(economy_conditions,market_demand,15).

connected(assembly_cost,sales_price,55).

connected(assembly_cost,competitiveness,15).

connected(market_demand,market_share,10).

connected(assembly_design,market_demand,30).

connected(assembly_design,competitiveness,35).

connected(assembly_quality,sales_price,30).

connected(assembly_quality,assembly_cost,60).

connected(competitiveness,market_share,50).

connected(sales_price,competitiveness,30).

connected(sales_price,market_demand,25).

connected(sales_price,market_share,30).

connected(sales_price,assembly_design,45).

connected(quality_control,competitiveness,25).

connected(quality_control,assembly_design,25).

connected(quality_control,market_demand,30).

connected(competitors_advert,market_share,10).

Specification

1) Describe, in detail the Best First Search technique and why it may be applicable for this problem. Describing any general issues (e.g. local maxima, plateaus etc) associated with Best First Search technique and how you might overcome them for an arbitrary problem.

2) Produce a search function (either Breadth First or Best First) that will search between any two concept nodes to see if one affects the other (see indicative marks below). If coding a Heuristic Search you should search in order of descending weight value.

Do not forget that you can debug and test the constituent prolog rules separately.

Comment your code extensively and ensure you use indicative naming for rule and variable names. If you use any books or websites for help, ensure you include a list of references.

3) Amend your code to calculate the actual influence of one concept over another, where we will calculate this as:

Sum of influence weights on path between concepts

Length of path between concepts

There are lots of useful hints in the lab notes and in Prolog books like Bratko (many copies in the library).

I want:

1)  The Prolog code

2)  Evidence of the outputs for each of your test cases (try different combinations of concepts), i.e. cut and paste the results to a text document.