Planning

The simplest kind of planning for Lemmings is to give a sequence of objectives, each of which is to be achieved reactively on the basis of the scene visible at the time of completion of the previous objective. Let's see how this works out for Game7 of Lemmings Jr.. We give one such plan but note where there may be some problems with a purely reactive system for achieving the successive objectives.

In Game7 there are two lemming sources that open approximately simultaneously, both above a platform. In the middle of the platform there is a pond that drowns lemmings that fall in. It might be surmounted by a long bridge, but none of the solutions I have attempted involve doing this. As in all Lemmings games, the lemmings walk to the right when they drop out of the source. The lemmings must be got down from the platform and then marched to the left over or through various obstacles. Here's the plan.

1. Start first left lemming (lemming from left lemming source) digging just after it has moved away from under source.
2. Start first right lemming digging just after it has moved away.
3. Start any lemming that over-runs the hole being dug to digging its own hole. There won't be more than two.
4. If a left lemming bounces left (happens rarely) make it a floater.
5. Increase rate of lemmings coming from source to maximum.
6. Make left digger a basher before it breaks through ceiling.
7. Make first right digger a miner as soon as its hole is deep enough so that lemmings won't climb out of it.
8. When left basher stops at iron wall, make it a digger.
9. When left digger digs far enough to clear iron wall, make it a miner.
10. Comment: These steps will get the lemmings safely down. There are now two cases according to whether a jumper is between the two mounds on the lower level or not.

    If yes, go to step 12

11. Make first lemming to approach the right tower from right into a climber.
12.   Make sure the lemming going to the left between the two towers is a climber going left.
13. When the climber has passed the left tower, make it a builder at a place where it will build over the lemming trap in one round of building. The right place is determined by experience. If the most obvious place is chosen, the monster reaches out of the trap. If experience is to be used, then there must be a memory of places from play to play of the game. Otherwise, the place must somehow be designated by the planner to the reactive player. When I am playing the game, I remember landmarks like bushes, but it would be easy to devise a co-ordinate system and give the x-co-ordinate. This might be considered contrary to the idea making the program solve the problem that humans solve, using very limited capabilities of numerical estimation.
14. When the builder has passed the lemming trap and become a walker again, make it a builder again when it has reached the point where a two section bridge will reach the slope leading to the goal with the lemming continuing to the goal. Again experience is involved to learn the right place. Again measurement might replace experience, since a Lemmings bridge rises on pixel for every two pixel it goes horizontally.
15. When the builder has reached the end of the first stage of bridge building, make it a builder again. (A two stage bridge is needed and suffices.)
16. When the builder has reached the slope, designate a lemming on the right as a basher, just as it reaches the right tower going left.
17. When the basher has broken through and become a walker, designate it a basher again when it reaches the left tower.
18. This is all that needs to be done. All the lemmings are saved.

We believe that each of the steps mentioned above can be acomplished by reactive programming except that step 12 involves remembering whether it is necessary to designate the lemming between the towers a climber. If it was the jumper, then it is necessary, but if it just climbed it is unnecessary. The conditional element could be avoided in this case, because it does no harm to designate a lemming a climber that is already a climber. However, it is probably a good idea to allow reactive programs some reference to memory.

In this example, it seems that all the reactive execution is done subordinate to single steps generated by the plan. It is not clear whether this is always possible in Lemmings. Moreover, it makes the plan rather rigid. There is no provision for going back to the planning level if the reactive level encounters an unexpected difficulty.

Consider the communication between the logical planner and the reactive executor of steps. The following considerations apply.

1. Approximately as proposed in [McCarthy, 1959], when the planner infers a sentence of the form

   
    
   as a side-effect, the reactive achiever is called with p as argument. When the goal is achieved, the observation program takes another look at the scene and modifies the logical database accordingly. Inference then resumes.

2. Any information needed to achieve a goal that cannot be obtained by the achiever directly from the scene must be provided to the goal-achiever in advance.
3. This scheme provides for no other communication between the logic part of the system and the reactive part and is therefore less sophisticated than many existing systems that plan and execute. At least conceptually, however, it seems appropriate to begin with this primitive interaction and then study what more this particular fruit fly may require.