[Next] [Up] [Previous]
Next: Tracing the Route Up: Appendix: Programming Route Finding Previous: Appendix: Programming Route Finding

Carrying Out the Search

  The main search procedure is quite short. Here it is:

define search(startstat,deststat)->destfound

   vars nextevent, line;

   start(startstat);

   repeat

      next() -> nextevent;

      insertnext(nextevent);

   quitif (nextevent matches [arrived [?line ^^deststat]

                                        at = mins from =]);

      addfuture(nextevent);

   endrepeat;

   [[^line ^^deststat] at ^time mins]->destfound;

enddefine;

The procedure is called with two arguments, specifying the start station and the destination station. It returns a list with the name of the destination station, its line, and the time taken:

search([victoria],[marble arch])=>
** [[CENTRAL marble arch] at 11 mins]

At any stage of the search, the database, as well as holding the connections between stations, contains two kinds of statements about the current state of the travellers:

The procedure first calls start, which simply records pending events indicating arrival at the starting station, on every line passing through it. These events are given the time 0 minutes. The start procedure is quite simple and will not be discussed further. The program then repeatedly calls next, insertnext, and addfuture, generating the next arrival, recording it, and then adding the new future events that follow from it.

The procedure next determines which stations the group of simulated volunteers visit at each stage. Whenever a group arrives at a station or transfers to a new line, the procedure insertnext adds an entry to the database, giving the line name, the station name, and the time from the start (it also contains their last port of call to help in tracing back over the route when the simulation is complete) -- for example,

[arrived [JUBILEE Green Park] at 5 mins
from [VICTORIA Green Park]]

If the arrival station matches the destination, then quitif breaks the repeat loop.

The program then calls the procedure addfuture to add entries for each of the events that will occur as a direct result of the current arrival; these will contain much the same information, but referring to an event in the program's `future' -- for example,

[will arrive [JUBILEE Bond Street]
at 7 mins from [JUBILEE Green Park]]

The meaning should be clear. The 7 minutes refers to the time from leaving the start and the line/station combinations are as in the map representation. The group is currently at Green Park. This last piece of information is inserted only so that if some of this group win the race to the destination, it will be easy to follow their route back.

Although in principle the statements about pending events are unnecessary, using them simplifies the program enormously. As you will see, they make it much simpler to keep the simulation running in the correct time sequence. In fact, most search programs use an agenda of this sort to decide what question to ask next.

The program decides when the voyagers have reached some point in the network by looking through the database at all the pending events, and choosing the one that has the earliest time associated with it. If there are several contenders, then one is chosen arbitrarily.

The way the program determines what new future events to note in the database, following an arrival at a particular station on a particular line, is slightly more complex: it must examine the Underground map in order to find out the stations on the same line adjacent to the current station, and the lines that pass through the current station. If we use our previous assumptions about timings, future arrivals at the stations on the same line can be noted for 2 minutes after the current time and future arrivals on any other lines through the current station can be noted for 3 minutes after the current time.

foreach

Before we plunge into the program, we need one new tool. This is a POP-11 construction that allows us to test all the statements in the database that match a particular pattern. Its form is

foreach <pattern> do ***-start-it-tag-***<actions> ***-stop-it-tag-*** endforeach;

The word foreach indicates the start of a loop in the program; the actions in the loop are carried out once for each item in the database that matches a pattern. Here <pattern> can be replaced with any pattern that could go on the right-hand side of matches (see chapter 2). The <actions> can be replaced with any POP-11 instructions. For each item in the database that matches the pattern, the instructions will be carried out, with any variables that were used in the pattern set according to the database item. The way foreach is used below should make this clear.

Choosing the Next Event

Let us look now at the procedure next. This searches the pending events in the database to find the one with the smallest time (the one which will occur next).

We use foreach in a procedure, called next, which returns the actual event that corresponds to the earliest pending event. Here it is:

define next()->event;

    vars leasttime, place, time, lastplace, event;

    100000 -> leasttime;

    foreach [will arrive ?place at ?time mins from

             ?lastplace] do

        if time < leasttime then

            [arrived ^place at ^time mins from ^lastplace]

              -> event;

            time -> leasttime;

        endif;

    endforeach;

enddefine;

This may look rather complex, but here is how it works (you may need to revise the use of ? and ^ in patterns and lists). The if ...endif section is carried out once for each item in the database that matches a pattern starting with the words `will arrive'. Thus, only pending events will match it (refer back to section 4.5 to see how it works). The variables place, time, and lastplace are set up by foreach to have the values corresponding to each pending event in turn: thus at some stage they might well have the following values:

 
place     		 [VICTORIA pimlico]

time 2

lastplace [VICTORIA victoria]

The variable leasttime records the time of the earliest event so far detected, and is set to a very large number to begin with simply to ensure that some event is returned. Each time through the foreach loop, if the pending event that has been matched is earlier than the earliest pending event so far (i.e., time < leasttime), then leasttime is updated. The variable event is updated also, to hold a list that records the earliest event so far found, and when all the pending events have been tested, this is what is returned by the procedure.

After this procedure has been run, the program will need to record this event as having happened, and remove the pending event from the database. This is done simply using add and remove; we shall skip over the procedure that does this and go straight to the other main part of the simulation, which records future events.

Recording Future Events

The procedure that does this is called addfuture. We will not give it in full, as one section will suffice to show its operation. The procedure has a variable place whose value is a list giving the name of the current line and the current station (i.e., the place just reached) and a variable time, the time of arrival at this point. Let us suppose that at some stage they have the values

 
place   		   [VICTORIA green park]

time 2

The job of the procedure is to insert into the database statements like

[will arrive [VICTORIA oxford circus] at 4 mins from

                                [VICTORIA green park]]

and

[will arrive [PICCADILLY green park] at 5 mins from

                                [VICTORIA green park]]

The procedure uses foreach to scan the map of the Underground, together with another variable, newplace. Here is a simplified version of the foreach loop:

foreach [^place connects ?newplace] do

    add([will arrive ^newplace at ^(time+2) mins from ^place]);

endforeach;

For each statement in the database showing a connection from [VICTORIA green park] to another station on the same line, this part of the program adds a statement noting the arrival there in 2 minutes' time.

The version of the repeat loop shown in appendix B at the end of the book is a little more complex, in that it calls a procedure addonefuture which only adds a notification if there is not already one present in the database.

The addfuture procedure needs three more repeat loops, similar to the one we have shown: one with ^place and ?newplace reversed in the pattern (because the links can be recorded in the database either way around), and 2 to search the database for other lines passing through the current station.

Speeding Up the Search

The program we have described so far will work correctly, but will be rather slow and use more computer memory than it needs to. The reason is that the simulated volunteers will frequently revisit each place. For instance, half of the group that reaches [VICTORIA pimlico] will turn round and return to [VICTORIA victoria], whence they came. From there, some will return to [VICTORIA pimlico], and so on. There will be an enormous amount of unnecessary activity (though it will not affect the final result).

Small modifications lead to a far more efficient search. First, when a pending event is to be inserted into the database, a check is made to see whether any group has already reached the place in question. If so, the pending event is forgotten rather than recorded. Second, when an actual event is noted, all the pending events that refer to the same place are removed. These two measures mean that no duplication of activity occurs. It is like having radio links between the groups of volunteers, so that those who are wasting their time can be told to give up.


[Next] [Up] [Previous]
Next: Tracing the Route Up: Appendix: Programming Route Finding Previous: Appendix: Programming Route Finding

Cogsweb Project: luisgh@cogs.susx.ac.uk