Reasoning in Time and Space

ABSTRACT

This paper describes a new approach to representing and reason­ ing with temporal and spaUal information. A wide variety of temporal and spatial specifications can be converted into linear inequalities relatii1g the endpoints of events or bourul:1ry surfaces of objects respecUvely. Linear programming is /,lwn nsed to rep­ resent these constraints and perform dcducUons. The temporal information is modularized into semantically relal.ed clusters of events each with its own tahleau and related to each other by a reference frame transformation. A similar grouping can be done for objects making the system computationally efficient. For temporal reasoning, the system is formally adequate except for linguistic fuzziness. For geometric reasoning, polyhedra can be represented by allowing parametrization. The uniformity of the time and space representaUon makes this approach particularly attractive.

INTRODUCTION

Most work in artificial intelligence which deals with real world problems would require some reasoning with time and space. This paper describes an approach to representing temporal and spatial informatioi1 using linear constraints. Deductions can then be performed by using linear p;ogramrning,

The importance of a temporal understanding in the areas of problem solving and natural language understanding has been recognized earlier[l, 7] . Most problem solving systems have modelled time using a state-space npproaeh. In this approach the world is described as a sequence of snapshots each with a set of facts holding at the time instant. Because of the inadequacy of this approach, attempts have been made to inc.orporate time ex­ plicitly in planning [4,8,'7]. In partieular Vere's DEVISER [7] is a general purpose planner which gener?.tes parallel plans to achieve goals with imposed time constraints in the presence of scheduled external even.ts. The temporal representation and reasoning is ad hoc and tied to the needs of the planner.

A more general purpose approach is that taken in the sys­ tems [1,3,5] that build time specialists. Such a subsystem main­ tains temporal relations and provides the rest of the system with tools to store, retrieve, delete nnd rea~on with the tem­ poral information. There are two wajor requirements for a time specialist: First, it must be formally adequate, and second it must be computationally effective. The first condition is met if the formal system is coherent and consistent, and contains oufficient mechanisms to be able to represent all temporal specifications and perform all the deductions we want. The second requirement

This work was supported under ARPA contract N00039-82-C0250 and NASA grant NAG 5-2fll.

REASONING IN TIME AND SPACE

Jitendra Malik and Thomas 0. Binford

Computer Science Department Stanford University, Stanford, California 94305

is essential in order to have the program produce answers with a reasonable amount of effort. This paper describes another at­ tempt in this direction.

Geometric reasoning research has been carried out mainly in the context of Robotics and Vision. We wish to deduce spatial relationships of objeets in three dimenbions given some knowledge of their positions, orientations and shapes. In manipulation tasks it is often necessary to plan paths past obstacles. Tn vision tasks[2], one needs to identify quasi-invariant characterisations of observables that the object will generate.

II TEMPORAL REASONING

General Framework.

Temporal information is information about events from the viewpoint of an observer with an internal clock ie a mechanism for judging before and after with an internal metric. Semantically related clusters of events are grouped into one time frame with its own clock. In each time frame, temporal reasoning be­ comes a linear programming problem which is solved by the simplex method. Linear coordinate transforms relate different time frames.

Temporal specifications.

In order for the system to be formally adequate it should be possible to represent all reasonable temporal information. This information is organised as a set of temporal specifications. A temporal specification[5]is a statement that partially specifies in some manner, the time of one or more events. Examples arc:

1. The gas leak started immediately after takeoff.
2. John saw Mary a while ago.
3. My fever lasted 3 days.
4. ( 4) A few days back, I was in Las Vegas.
5. Hiroshima was bombed on August 6, 1945.
6. I will finish my PhD in two to three years.
7. Jack had an accident a month after getting to Boston.
8. The symptoms start appearing within 10- 20 minutes of the snakebite.

It may be observed that except, for (2) and possibly (4) all the specifications are linear relations betw'cen the endpoints of events and can be handled by our system. Phrases like 'a while' and 'a few' cannot be handled by a time specialist in isolation unless it is done by ad hoc rules of the type used by Kahn and Gorry[5]. We decided not to use such an approach as we believe that a satisfactory solution to this problem can come only in the context of a well-developed nat.ural language underst:mding ability.

Temporal information can be given both as relations between endpoints and between intervals. A fact like The bank opens at 9:00 am is a statement about the startpoint of the event bank­ is-open. A fact like The Cuban missile crisis took place during Kennedy's term is a statement about intervals. The two approaches are equivalent in terms of representational power. For the convenience of the user, both forms of specification are allowed. The internal representation is in terms of endpoints as that is more natural for our representational scheme.Relations involving endpoints are inequalities which are converted to equa­ tions by introducing slack variables. Relations involving intervals are converted to relations involving endpoints as shown in the following table:

Representation and Reasoning.

As may have been observed, all the temporal specifications can be converted Lo linear relations between the endpoints of the events. This means that we can use linear programming to represent and reason with temporal information. A time specialist based on linear programming is guaranteed to be for­ mally adequate- unlike the ad hoc methods. It provides a uniform representation for storing the wide variety of temporal information. The linear programming is done using the simplex algorithm in the version formulated by Tucker. In this approach the rows of the tableau have a direct physical meaning-- they cor­ respond to the endpoints of Lhe events. The system was written in MACLISP in the A CRONYM environment so that it could be used easily as a module for future image understanding work.

As the tableau represents all the information in the temporal specifications, the system is complete --all deductions that can be made from the constraints can be made from the tableau. The general approach is to formulate an expression which is maxi­ mized or minimized, while still satisfying the constraints in the tableau. The implemented features include

1. Satisfiability-As the linear constraints associated with each temporal specification are entered into the tableau, the ex­ istence of a feasibl e solution is checked. The system refuses to · accept a .constraint that is inconsistent with the previous set.
2. Bounds-One can determine the upper and lower bounds for ;,my variable, which corresponds to an endpoint of an event, or·a linear expression in these variables. For example, this permits us to find upper and lower bounds on the duration of an event.
3. Possibility and Necessity-If a predicate's being true would not be inconsistent with the constraints in the tableau, the preuicate is said to be possible. If a predicate's being false would be inconsistent with the constraints of the tableau, the predicate is s:1id to b·~ necessary. The temporal predicate is con-

verted into an arithmetic expression in the endpoint variables. By determining the upper and/or lower bounds of this characteristic expression the query can be answered. For example, the charac­ teristic expression for the temporal predicate (Before A B) is endA - start8 . If this expression is possibly non-positive, ie its lower bound is ::; 0, then the predicate is possibly true. If this expression is necessarily non-positive, then A is necessarily before B. These deductions would be useful to a planner using this time specialist. If event A is necessarily after B, then that ordering can be done right away. Possibility considerations can help prevent unnecessary backtracking.

Comparison with other systems.

The idea of using linear constraints to provide a uniform representation of temporal information is a major change from the philosophy of earlier systems. Kahn and Gorry[5] use several different ways of organizing the events- with a date-line, using before/after chains, and using special reference events each with a separate procedure for making deductions. Allcn[l] uses a network of constraints to maintain all possible relationships about how the intervals in it arc related. However, in his system no metric information is represented and thus fails to be formally adequate by our criteria.

To people conditioned to react with horror to uniform, for­ mally adequate schemes, our representation would immediately raise the specter of inefficiency. Indeed, this would be so if all the temporal facts about the domain were to be represented in the same linear programming tableau. Recall, however that we can organize the information in semantically related clusters­ each with only a small number of constraints .. The system still remains complete bceause we can do a reference frame transfor­ mation to relate events in difTerent clusters. This idea buys us the same advantage as the reference interval concept[l,5] in a more systematic way. The analogy with the way we organize and reason with spatial information suggests the naturalness of this approach.

lli SPATIAL REASONING

One dimension.

There is a direct isomorphism between temporal reasoning and spatial reasoning in on!' dirncnsion.'Object A is to the left of object B' corresponds to 'Event A is before event B'. The everyday terms left of/right of, front of/behind, below/ above arc counterparts of before/after by considering respectively the x- axis, y- axis, z- axis instead of the time--axis. The notion of different coordinate frames is equally applicable. As in the case of temporal reasoning, we are not considering the linguistic difficulties involved in understanding words like 'near' and 'fear'.

If information about each dimension can be represented independently--which is the counterpart of the assumption that [ 3 ] the temporal reasoning can be factored out- we have the power t,o represent and reason with 3- D parallelopipeds with each dimen­ sion parallel to one of the. axes. Objects which can be expressed as combinations of such primitive objects can also be represented. [ 4 ] Three separate linear programming tableaus will be maintained for the three dimensions with no sharing of variables. Questions like Is A inside B? can be answered by finding the conjunction of three query answers.

Three dimensions-Linear Constraints.

We can extend our representational power by allowing parametrisation with parameters shared between dimensions or equivalently having just one tableau to represent the constraints for all the three dimensions. Any convex polyhedral region in space can thus be represented. Standard deductions can be carried out using linear programming techniques.

Comparison with other Approaches.

Unlike the temporal domain, there are several schemes in use with greater representational power /ease of use. Generalized cones have been found more useful for modelling objects as com­ pared to polyhedra. To increase the power of the constraints approach, non- linear constraints have to be allowed as in AcRO­ NYM[2].The uniformness of the space and time approach is one of the major attractions of our approach. We have used this ap­ proach to study reasoning in the pool table world. Reasoning can be carried out equivalently in the time or spatial domain. Unfortunately, we are unable to give a detailed account here due to lack of space.

IV GENERAL REMARKS_

Much knowledge representation work has been characterised by a confusion between representation and implementation. The representational issue is the question 'What must be repre­ sented?'. The answer is in terms of a mathematical 'structure--in our case a set of linear constraints partitioned in a particular way. The implementation stage is where we deal with specific al­ gorithms and data structures-- in our case the simplex method and its tableau. Marr had considerably emphasized the significance of this distinction. As knowledge representational techniques be­ come more precise and specific, eg in Vision and Robotics re­ search, this point will become even more important.