TEACH SEM2A3SEARCHING                             Aaron Sloman, Oct 1995


SEARCHING

Assuming that you have successfully revised the basics of Pop-11 and are
now fluent at list processing, the next task is to implement a general
purpose searching program.

For revision on searching strategies see TEACH * TOWER, which you should
have worked on in your first year Pop-11 course. It is concerned with
the problem of finding a combination of blocks from a collection of
different sizes, in order to form a tower of exactly a specified height.
E.g. given a set of blocks of the following heights

                      [ 3 8 6 11 2 9 23 44 ]

can you choose a subset whose combined height is exactly 38 ?

This is a special case of the general problem of combinatorial search: a
number of items is available from which a succession of choices must be
made to find a solution to a problem. The items may be concrete, e.g.
blocks, or abstract, e.g. numbers, words, actions, plans, designs,
programs, etc.

TEACH * TOWER introduced programs for solving the special case using
random search, depth first search, breadth first search, and other
strategies guided by heuristics to reduce the search space.

TEACH * ROUTE describes the problem of searching for a route in a
network of links in the London Underground system.

You should also have met the problem of searching for a suitable parse
in your course on natural language processing.

Since the need for searching occurs in very many different contents many
people have been tempted to create general purpose searching systems.
TEACH * SEARCHING introduces a way of doing that.

It shows how to define a general procedure which takes an initial
problem state and a goal recognizer as input, along with a collection of
problem specific procedures, and then tries to find a solution to the
problem of finding a state which satisfies the goal recognizer.


The procedures it needs are

1. The goal recognizer, which checks whether the current state matches
the goal specification:

    define is_goal_state(state, current_goal) -> boole;

2. A procedure which can be given a state in the search space and
returns a list of "child" states, derivable from that state by applying
whatever operators are available in the problem domain.

    define nextstates(state) -> newstates;

3. A procedure for checking whether two states are equivalent, used to
prevent the program searching round in circles.

    define same_state(state1, state2) -> boole;

The "master" problem solving procedure is then invoked thus, with five
arguments, the initial state, the goal specification, and the above
three procedures:

    solve_problem
        (initial, current_goal, isgoal, nextstates, samestate) -> result;

You can try designing such a procedure yourself, and then after
implementing it compare it with the design in TEACH * SEARCHING.

If you find that too difficult work through TEACH * SEARCHING, which
shows you how to build up such general problem solver step by step.

As you work through the teach file, try to do the various steps yourself
before reading ahead, since otherwise you will really not learn from the
exercise.

Put your work for this course in a directory called sem2a3 just below
your top level directory. Your top level directory and the subdirector
for the course must be kept readable. You can achieve this with the
unix commands:

    mkdir ~/sem2a3

    chmod 755 ~ ~/sem2a3

Put your work on this exercise in a file called 'searching.p', in your
sem2a3 directory, so that I can easily find it.

Let me know if you would like to have printed copies of TEACH SEARCHING
made available.

--- $poplocal/local/teach/sem2a3searching
--- The University of Birmingham 1995.  --------------------------------