anatrudel@watdragon.waterloo.edu (Andre Trudel) (03/04/89)
In the non-monotonic literature there are standard examples. For example, the `birds fly problem'. Are there any standard examples in the temporal representation and reasoning literature? The `Yale shooting problem' is the only one i know of for temporal reasoning. Or, does anybody have interesting and/or challenging examples for a temporal logic? The reason for the request is that i'm writing up my thesis and need some examples. Thanks Andre
geddis@polya.Stanford.EDU (Donald F. Geddis) (03/04/89)
In article <11999@watdragon.waterloo.edu> anatrudel@watdragon.waterloo.edu (Andre Trudel) writes: >In the non-monotonic literature there are standard examples. For example, >the `birds fly problem'. > >Are there any standard examples in the temporal representation and reasoning >literature? The `Yale shooting problem' is the only one i know of for >temporal reasoning. The Yale Shooting Problem, while certainly involving time, is really also under the category of the nonmonotonic literature. Related examples have to do with breaking various proposed solutions to the original YSP. Original Yale Shooting Problem: (1) By default, fluents (predicates about the world) don't change. (This is often called the Frame Axiom.) (2) If you shoot someone with a loaded gun, they are no longer alive. Consider the sequence, from a state where the gun is loaded, "wait, then shoot". Start state (A): (Gun loaded, "Fred" alive). State (B) = after wait, and State (C) = after shoot. What happens after the two actions? Is Fred alive? We all say no. The simpleminded nonmonotonic reasoners come up with two possibilities, of equal weight. Either: (1) going from B to C, the shoot action succeed, but the frame axiom failed, so Fred is not alive anymore; or (2) going from A to B the gun mysteriously unloaded itself (the frame axiom failed), but then the shoot from B to C has no effect, because the gun is unloaded, and Fred is alive in C. Note that in either case exactly one default rule was overridden, and it was the same rule in both cases (although at different times). There are many proposed solutions, each (so far) with their own custom-made problems that "break" them (cause them to give answers that go against common sense). It doesn't really make much sense to give a list of these, since the object isn't to succeed on the problems already invented, but to make sure that people can't invent new ones which damage your solution too. Just as an example, one proposed solution was to choose, in the case of a tie, the extension (answer) where the breaking of the default came latest in time. This correctly solves the original YSP. A custom made problem for it is the stolen car problem. State 0: You have a car. You perform 10 wait actions. You notice, in State 10, that your car has been stolen. Question: when was it stolen? The frame axiom (which keeps the car in the same place, by default), must break exactly once, during the time when the car is stolen. This solution yields the answer that the car was stolen during the last time period, from states 9 to 10. Most humans say that they don't know, that each of the transitions have equal probability. There are more examples. Check literature on Reasoning About Action, and specifically on rebuttals to proposed solutions of the YSP. -- Don Geddis -- Geddis@Polya.Stanford.Edu "We don't need no education. We don't need no thought control." - Pink Floyd