ken@aiai.ed.ac.uk (Ken Johnson) (05/07/90)
This is a quick response to the follow-ups. Firstly, thanks for
writing. Remember that the object of the exercise is to give students
some experience of the use of depth-first, breadth-first and best-first
search on a real data base, rather than to enable passengers to find
their way across the London Underground! I think it fulfuls its purpose
fairly well. Best first search finds plausible routes. Depth first
search is useless. Breadth first is often all right, but occasionally
falls over.
The data representation is inadequate for representing the whole of the
Underground network. The Northern Line is particularly complicated,
being of the general form
-------------- Edgware
|
------------------------ |
| | | Mill Hill East
| | | |
| | | |
Morden ------------ Kennington ------------ Camden --------------- High
Town Barnet
I have circumvented this problem by omitting parts of the lines that do
this kind of thing. If I didn't, then the model as written would give
misleading answers, e.g. although both Edgware and High Barnet are on
the Northern Line you cannot travel from one to the other on one train
without changing.
The solution is probably to represent the actual routes operating through
given stations by integers, e.g.
1 4
-------------- Edgware
1 2 3 |
------------------------ |
| | | Mill Hill East
| | | | 2 5
| | | |
Morden ------------ Kennington ------------ Camden --------------- High
1 2 3 4 5 6 3 6 Barnet
4 5 6
so you would then have a mapping e.g.
name_of(1,northern).
and a representation of stations e.g.
station(high_barnet,22,28,[3,6]).
Now, once you have loaded the data base you can generate (once for all)
a table of the form
serves(3,high_barnet).
You don't have to prepare this manually. Why work hard twice? You could
even generate it as needed using assert's, so that you do strictly no
more work than necessary and no work twice.
A further problem. This route
Go from pimlico to victoria on the victoria line
Go from victoria to south kensington on the district line
and this one
Go from pimlico to victoria on the victoria line
Go from victoria to south kensington on the circle line
appear to the search program to be distinguishable; in fact, you want
them to be coalesced into
Go from pimlico to victoria on the victoria line
Go from victoria to south kensington on the circle line or the
district line
I haven't found a most convincing solution for this, although I have
found a couple which have rival merits. On the whole I think a sort of
postprocessor which merges equivalent solutions comes out most
attractive. It would have to know that e.g. Victoria to South
Kensington on the District is equivalent to the same journey on the
Circle (it uses the same track) whereas that from Euston to Finsbury
Park on the Victoria Line is faster than the same journey on the
Piccadilly Line. Similarly the journey from Baker St to Wembley Park is
faster on the Metropolitan Line than on the Jubilee Line. It is quite a
complicated problem of data representation to make the search efficient
and mimic the route selection of a human operator.
A further problem is that some stations close at some times of day,
making certain routes unavailable. (e.g. the Waterloo-Bank and
Moorgate-Finsbury Park links are operated by BR and are therefore closed
when you actually want to use them.) This has to go in as well if you
want to use the model for its ostensible purpose!
-- Ken
--
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
ps. This is all true, except the bits I made up