Next: Summary of Path-Planning Issues Up: Reasoning About Path-Planning with Previous: Specifying Motion

Directional Reasoning

Reasoning about object motion requires the ability to represent direction. There is no explicit directional information in the original scene description, but it can be inferred from information such as the angle of curves and junctions, or from ``parallel proximity''; a segment which is in proximity to another segment, with junctions at each end which are both equidistant from that segment, is known to be parallel to it. The representation of direction requires that the reasoning system be able to relate vertex angles or parallel lines to directions of motion.

Any direction reference is specified relative to one boundary element on a one object (i.e. there is no global direction such as ``North''). Directions can be specified as forward, back, left or right relative to the named boundary element, where the named direction refers to a possible motion of the object.

For directional reasoning purposes, a full set of relationships must be established between these motion directions, and vertex angles. This is achieved using functions that apply rules such as ``The segment on the left side of an acute, convex junction faces backward and to the left with respect to the segment on the right side''5.9. Other directional relationships include the effects of reflection, and addition or subtraction of angles. These are all defined by a set of direction functions.

The directional reasoning part of the system distinguishes between directions that are precisely known, and directions that are ``vague''. Precisely known directions are based on right angles, and represent exact angular values. Forward, left, back, and right are all precise directions. Between these directions are four quadrants (corresponding to acute and obtuse angles), within which the angle value could be anywhere within the 90 degree range. The ``vague'' directions describing these quadrants are ``forward and to the left'' (fl), ``back and to the right'' (br), ``forward and to the right'' (fr), and ``back and to the left'' (bl). This organisation is obviously a result of the way the angle quantity space is structured in this implementation, but the distinct nature of precise directions applies to some values in any quantity space.

It is possible to perform some operations with vague directions - the reflection of a vague direction is known (it is another vague direction), as is the value of that direction plus or minus 90 degrees (also a vague direction). No operation performed on a vague direction can return a precise direction, however, and this limits the utility of vague directional information. In addition, an acute or obtuse angle added to another vague direction results in no certain direction at all, because the result may be in either of two quadrants, or it may be a right angle.

The reasoning system includes functions to discriminate between the vague and precise directions where necessary, so that directional information can be maintained that is as precise as possible given the input data. Most functions of the system will continue to operate with vague information for as long as possible, but will return an ``unknown direction'' token (the unknown direction is represented by the atom '? in lisp) when information becomes too imprecise. The atom '? effectively acts as a ninth qualitative direction, which is accepted as a legal input by directional reasoning functions, but usually results in the propagation of unknown directions throughout the system during geometric reasoning tasks.

The incorporation of ``vague'' and ``unknown'' directions makes the current system robust enough to accept scene data involving imprecise qualitative angle descriptions. This directional reasoning is, however, less powerful than the partial distance ordering, and in most cases it was vague angle information that resulted in the breakdown of geometric reasoning tasks, rather than lack of precision in size information.

Next: Summary of Path-Planning Issues Up: Reasoning About Path-Planning with Previous: Specifying Motion
Alan Blackwell
2000-11-17