# Computational Intelligence

### A Logical Approach

# Online Code

This file contains code from Poole, Mackworth and Goebel, Computational Intelligence: A Logical Approach. All code is copyright © Poole, Mackworth and Goebel, and Oxford University Press, 1997. All Rights reserved. This code comes with absolutely no warranty.

All of this code runs in standard Prolog, such as Sicstus Prolog, which is available on UBC machines as "sicstus" or SWI prolog, that is available for free for Unix and Windows systems.

Either save the code to a file and consult it into Prolog, or cut and paste it into a Prolog window after using '[user].'. See Section B.2 in Appendix B.

You can get the whole code distribution as code.tar.gz (a gzipped tar file).

## Chapter 2

- west.pl axiomatization of office layout from Figure 2.3
- times.pl axiomatization of otdering of times from Figure 2.28

## Chapter 3

- elect.pl electrical wiring example from Section 3.2
- course.pl course example from Section 3.3.1
- lists.pl list procedures from Section 3.4
- univ.pl university requirements example of Section 3.5
- univ2.pl university requirements example, different axiomatization
- nl_cfg.pl natural language parser using context free grammar from Fig 3.5
- trans.pl grammar for outputting canned English from Figure 3.7
- trans2.pl DCG version of trans.pl
- nl_numbera.pl natural language parser with number agreement of Figure 3.8
- nl_interface.pl natural language interface of Figure 3.9

The following code is not described in the text, but are exercises:

- bin_arith.pl binary arithmetic from Exercise 3-9
- exp_parser.pl left associative parser for arithmetic expressions
- sorting.pl sorting algorithms (mergesort and quicksort)

## Chapter 4

- The following are based on the generic graph searcher:
  - search.pl The generic graph searcher from Section 4.3. This traces the frontier as the search proceeds.
  - hsearch.pl a graph searcher for heuristic search. This maintains more information per node than the generic graph searchers.
  - idsearch.pl iterative deepening search, based on the generic search algorithm.
  - idsearch2.pl iterative deepening search, based on Prolog doing the searching.
  - idastar.pl iterative deepening A* search, based on the generic search algorithm.
  - idastar2.pl iterative deepening A* search, based on Prolog doing the searching.
  The following domains can be used:
  - graph.pl The delivery domain graph from Section 4.3 of the book.
  - graph2.pl A version of graph.pl, but with cycles.
- The following are constraint satisfaction engines:
  - csp.pl constraint satisfaction using arc consistency.
  - csp_gt.pl constraint satisfaction using systematic generate and test.
  - rand_csp.pl constraint satisfaction by generating random instances and testing them.
  - gsat.pl an implementation of GSAT. This also assumes you load standard.pl and random.pl.
  These can be used on the following test examples:
  - csp_t1.pl simple test code for any of the constraint satisfaction code.
  - csp_t2.pl scheduling example for any of the constraint satisfaction code.
  - csp_t3.pl crossword example for any of the constraint satisfaction code.
- The following use useful pieces of code:
  - random.pl code for generating random numbers and random lists.
  - standard.pl standard definitions from appendix B.
  - pq.pl efficient implementation of priority queues.

## Chapter 5

- semnet.pl Structured semantic network implementation from Figure 5.6 and Example 5.13.

## Chapter 6

- bprove.pl depth-bounded meta-interpreter (Figure 6.6).
- dprove.pl delaying meta-interpreter (Figure 6.7).
  Test code: electrical domain with assumables.
- ask.pl Ask-the-user meta-interpreter (Figure 6.8).
  Test code: electrical domain with askables.
- ask_why.pl Ask-the-user meta-interpreter that allows for why questions.
- trace.pl a meta-interpreter that lets you traverse a proof tree, and use how questions.
  Test code: electrical domain.
  Test code: electrical domain with bugs; you can use the how questions to debug it.
  Test code: sorting algorithms.
  Test code: buggy sorting algorithms; you can use the how questions to debug it.
- trace2.pl like trace.pl, but is more sophisticated (more difficult to follow how it works, but more user friendly to use). If you want to actually use one of these, use trace2.pl. If you want to understand what is going on, try to understand trace.pl first.

## Chapter 7

- ineq.pl meta-interpreter to correctly handle inequality.
  Test code: small example.
- confl.pl meta-interpreter to find conflicts.
  confl_id.pl iterative-deepening meta-interpreter to find conflicts.
  Test code: small example.
  Test code: electical domain.
- thpr.pl Meta-interpreter for general clauses (Figure 7.7).
  Test code: small example (Example 7.29).
  Test code: slightly larger example (Example 7.32).

## Chapter 8

- The following use the situation calculus:
  - bprove.pl a depth bounded meta-interpreter suitable for planning using the situation calculus representation.
  - delrob_sitc.pl is the delivery robot world in the Situation Calculus.
- The following use the STRIPS representation:
  - strips_strips.pl a STRIPS planner that uses the STRIPS representation (Figure 8.2).
  - regr_strips_sim.pl a simple regression planner that uses the STRIPS representation.
  - regr_strips.pl a regression planner that uses the STRIPS representation. Like `regr_strips_sim.pl`, with loop detection and uses heuristic information about the satisfiability of conjunctions of goals.
  - pop.pl a partial-order planner that uses the STRIPS representation.
  - pop_sics.pl a partial-order planner that uses the STRIPS representation. This assumes that `dif` exists that delays inequalities when they cannot be immediately resolved. It is more efficient than `pop.pl`, but not so portable.
  delrob_strips.pl the delivery robot world in the STRIPS representation.

## Chapter 9

Code:

- iass.pl An iterative-deepening abduction interpreter that finds minimal explanations.

Examples:

- iass_t1.pl Simple meaningless example.
- iass_t2.pl Example 9.4.
- iass_t3.pl Example 9.5.
- iass_t4.pl Example 9.6.
- iass_t5.pl Example 9.9.

## Chapter 10

Code:

- bnet.pl A belief network interpreter. (from Appendix C).
- relevant.pl code to prune irrelevant variables. This can make the above belief network interpreter much more efficient. Note that this redefines the `relevant` predicate.

Example Networks:

- Leaving network
- Aching limbs network
- Leaving influence diagram (for a single strategy).

## Chapter 11

- The following implement decision tree learning:
  - dtlearn1.pl binary attributes, myopic max information split, no noise.
  - dtlearn2.pl binary attributes, myopic max info split, noise allowed.
  - dtlearn3.pl binary attributes, full search for smallest tree, no noise.
  - dtlearn4.pl binary attributes, GINI index, no noise.
  These run on the following data:
  - dtlearn_t1.pl classification data from Figure 11.2.
  - dtlearn_t2.pl classification data from Figure 11.2, with Boolean attributes.
  - dtlearn_t3.pl small Boolean example
- The following implement neural-network learning:
  - nnlearn.pl backpropagation learner.
  - nnlearn2.pl same as nnlearn.pl, but it prints out a detailed trace.
  These run on the following data:
  - nnl_t1.pl classification data from Figure 11.2 (two hidden units)
  - nnl_t2.pl classification data from Figure 11.2 (no hidden units)
  - nnl_t3.pl small Boolean example (same data as dtlearn_t3.pl)
- ebl.pl Explanation-Based Learning Meta-Interpreter.
  Test Code: Course database from book.
  Test Code: Example from Mitchell's book.
  ebl2.pl Explanation-Based Learning Meta-Interpreter. This version collects a conjunction as the body of the learned list.

## Chapter 12

- sim.pl Robot simulator.
- sim_t.pl and axiomatization of a car-like robot with one whisker, and its environment for use with the above simulator.
- sim2.pl Robot simulator that takes advantage of delaying.

## Appendix B

- code.pl Code from Appendix B.

## Appendix C

The following code sometimes assumes we use the standard built-in for this book. There are all described in Appendix B.

- fwd.pl A forward chaining definite clause interpreter, with test program.
- fwdnf.pl A forward chaining definite clause interpreter with negation as failure. Also test program.
- fwdab.pl A forward chaining abductive Horn clause interpreter, with test program.
- how.pl A meta interpreter to traverse proof trees. It allows you to ask how a goal is proved. Also base-level program of the electical domain.
- iprove.pl Iterative deepening definite clause interpreter. Also test program.
- ask.pl Ask-the-user interpreter. Also test program.
- prall.pl A meta-interpreter that allows control over search strategy. Also test program.
- csp.pl A constraint satisfaction program using arc consistency and domain splitting. Also problem domains: Simple Example, Scheduling Problem, Crossword Problem.
- nnlearn.pl Neural-network style learning for parametrized logic programs. Also test data.
- pop.pl A partial order planner using STRIPS representation. Also axiomatization of robot domain.
- bnet.pl A Bayesian network interpreter. Also Leaving network, Aching limbs network, Leaving influence diagram (for a single strategy). [This is the same code referred to in Chapter 10 above].
- sim.pl Robot simulator. Also axiomatization of a car-like robot with one whisker, and its environment.