... problem.^1.1

The relationships between these research topics is illustrated in the diagrams of appendix B.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... operators.^2.1

Further discussion of RAPT can be found in the following references: The RAPT representation of object relationships is described in [AP75], the relational language which is used to implement the system is described in [Pop79], the interpreter is described in [PAB80], and a comparison of RAPT with programming in VAL and with a computer aided drafting system, is given in [APK82]. An extension to RAPT which deals with representation of tolerance information, and propagation of positional uncertainty through an assembly is described by Fleming [Fle85b].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...[dK79]^3.1

The reference listed in my bibliography is a version of this paper in a 1979 collection. The paper was initially published as MIT AI Lab Technical Report TR-352 in 1975. De Kleer also published related papers in 1977 [dK77]

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... circuits^3.2

Initially described in ``Causal and Teleological Reasoning in Circuit Recognition'', MIT AI Lab Technical Report TR-529 1979, but more fully developed in [dK84]

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... systems.^3.3

Hayes' awareness of the problems of real world reasoning may also have been strengthened by his early work in robotics.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... motion^3.4

[Hay83] p.10

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... entities.^3.5

Hayes also uses the term ``quantity space'', but by it he means any space in which reasoning takes place without knowledge concerning the properties of the space. This difference in terminology can be a source of confusion when investigating the relationship between qualitative physics and naive physics.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... instance.^3.6

Franz Reuleaux ``The Kinematics of Machinery: Outline of a Theory of Machines'' Reprinted by Dover Publications in 1963

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... size.^4.1

Absolute size information may become important when the robot is physically operating on workpieces, if positioning and motion of robot arms are specified as absolute coordinates within the workspace, but it is not always necessary during task planning stages.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... end.^4.2

These three types of boundary segment were selected primarily because they were convenient in motion planning problems, but an advantage in this selection is that it is possible to extract this information directly from a visual image, as shown by Mackerras [Mac87b]. His system produces an ``RSK'' segmentation graph, containing ``regions'', ``segments'' and ``knots'', which is similar to my extended polygon representation. Brady's Smoothed Local Symmetries vision system [BA84b] also produces shape description output in this form.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... boundary.^4.3

See Appendix A for a LISP code example of the way that multiple levels of detail are represented on an object boundary.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... points.^4.4

The minimum number of absolute points would be the three points that distinguish between concave and convex, and between acute and obtuse. This could provide a relatively easy transition from the current system to the angle ordering, by simply replacing the current set of distinguished angles with absolute points in the partial ordering.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... them).^5.1

See [LP83] for a typical geometric algorithm which finds solutions to the mover's problem.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^5.2

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^5.3

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^5.4

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...

Appendix A contains a complete LISP description of a scene using EPB/PDO. The reader may wish to refer to this appendix for examples and further detail than is given in this discussion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ``property''^5.5

Where the ASSF implementation made extensive use of the LISP ``defstruct'', the EPB/PDO system was implemented using ``properties''. A LISP atom can have any number of properties, and new properties be defined dynamically (defstructs must be explicitly defined by the programmer). Use of properties is more portable between different LISPs, and the ability to define them dynamically seems to be more consistent with the general style of LISP programming.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... list.^5.6

Although a logical circular list is formed by these pointers, no list exists in the LISP sense - it cannot be operated on by the LISP list operations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... concave.^5.7

LISP implementation note - shape properties are implemented using assoc lists with the keys angle, bulge, wiggliness, and flex.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... size.^5.8

Note that this technique is only applicable to translation - further facilities must be provided to analyse simultaneous translation and rotation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... side''^5.9

These ``rules'' are actually assoc lists which are interpreted to relate all possible combinations of angles to directions

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.