In any qualitative envisionment, a possible change in state of the system being modelled must be reflected in the representation, so that future state changes can be determined. The complete dynamic state of the sliding object system can be described as the set of all contacts in the scene. As mentioned above (and presented in more detail in the implementation section), contact is described relative to each feature, as a list of things that are in contact with that feature.
The global contact state for the whole scene is the set of all such contact lists. Each contact is mentioned twice in this set, once in the list of each feature that participates in the contact. Updating the contact set to reflect a change of state involves adding new contacts to the set, and removing all reference to contacts that have been separated.
Adding new contacts includes the addition of new contact lists to the set if a feature has no previous contacts, and determining whether the contact should be at the clockwise or anticlockwise end of the contact list if the feature does have previous contacts. Where a contact is removed, it must be removed from the contact lists of each feature to maintain consistency in the contact set. All of these functions, although they are necessary to maintain consistency in the contact set, are analagous to principles that humans automatically apply when reasoning about relative motion of moving and stationary objects.
A higher level of reasoning in the program makes use of this contact set information to search for possible new contact configurations. The search tree is presently only a binary tree, because at any point the moving object may only move clockwise or anticlockwise. If the program dealt with obstacles which had gaps between them, this search tree might expand, because of the multiple possibilities in moving between objects.
The search level of the sliding system collates a ``history'' of possible contact sets. It also determines from the contact history when it has exhausted the possible contact configurations (this occurs when a system state is exactly repeated, and the program has searched from that state in both clockwise and anticlockwise directions).
The solution required to the original sliding problem is an envisionment of all contact sets that can occur as the moving object slides. This contact history can therefore directly provide the final solution.
As pointed out in chapter 3, planning tasks differ from other qualitative reasoning domains, in that the ``envisionment'' is actually the effect of actions planned by the reasoning program, whereas ``function from structure'' problems usually determine the behaviour of a system that changes state by itself. The envisionment described here can therefore be considered by a planning program to be a history of the states that would have occurred if a robot had actually carried out previous planning stages. The formal relationship between history and envisionment in qualitative physics reasoning is discussed in some detail by Forbus [For87]. The attitude I have taken in this implementation is however quite informal.