next up previous contents
Next: Stages in Path Planning Up: Reasoning About Path-Planning with Previous: The Path-Planning Problem

EPB/PDO Implementation5.4

The most basic level at which an object boundary is represented is an unordered set of boundary elements listed as a ``property''5.5 of the object. Objects have no other properties for the purpose of this system, but in a more extensive reasoning system, the object may provide an interface between a higher level of reasoning and the path planning mechanism.

The set of boundary elements includes both segments and junctions, and these are distinguished by a type property, which identifies them as one of the two types. The ordering of elements around the boundary is established using ``neighbourhood'' properties on each boundary element. The left property points to the boundary element on the left (anticlockwise) of this one, and the right property points to that on the right. The left and right pointers can be used to treat the boundary as a doubly linked circular list.5.6

The left and right neighbourhood properties are not actually simple pointers, but lists, where the list is ordered by detail resolution; the first element of the list is the coarsest level of boundary detail, and the last is the finest level of detail. The neighbourhood description is therefore used to implement the web of boundary relationships at multiple levels of detail that was proposed in chapter 4.

Boundary elements of both the segment and junction type have a shape property. The shape of a segment may be either line, curve, or wiggle. Curve and wiggle shape properties also include angle and bulge (for a curve), or wiggliness and bulge. The shape property of a junction lists its angle and flex, which may be either convex or concave.5.7

Proximity of two boundary elements (or contact between them, since contact is a special case of proximity) is represented as a property of each element. This is in contrast to the ASSF implementation, where relationships are described globally, and the relationships associated with any particular element must be found using a global search.

A proximity (or contact) relationship between two elements is represented by an independent pair of pointers to the two elements. Each element has a property which lists all such proximity pairs that refer to it. There are in fact two of these lists: the internal proximity property refers to proximities between this element and other elements on the boundary of the same object. Internal proximities are invariant for rigid objects. The external proximity property refers to proximities between this element and elements on different objects. These proximities can change when objects move.

All segments also have a size property. This points to a global ``equidistance'' list - part of the partial distance ordering - which lists all distances in the scene that are the same size. The equidistance list specified by a segment's equidistant property will have at least one entry - the segment itself.

The partial distance ordering, which relates the magnitude of all segment sizes and proximities in the scene, is composed of a number of equidistance lists. Each list specifies a set of equal distances - segments whose size is equal to this distance, and proximities between elements which are separated by this distance. The partial ordering is established with two properties of each equidistance list - the larger and smaller properties. Each of these is a pointer to another equidistance list. One special equidistance list is the contact list. It has no smaller property, and its value is the list of all boundary element proximities where the elements are in contact. In a consistent distance ordering there will also be at least one equidistance list which has no larger property.

There are five types of atom which may be pointed to by an entry on an equidistance list. Segment size is one of these, internal, external or overlap proximity pairs are another three, and the last is the synthetic distance, which is the result of some geometric construction carried out during problem solving (this is discussed further in section 5.2.5).

A portion of a scene representation, including the relationship between objects, segments, junctions, proximity, and the partial distance ordering, is illustrated in figure 5.12. This figure (which is a portion of a simple scene in which a tripod is to move through a doorway) shows the representation of an object boundary using left and right neighbourhood pointers between segments and junctions. It also shows the arrangement of proximity pairs relating boundary elements on different objects, and the comparison of segment size to proximity in the partial distance ordering. It does not include object shape descriptions (multiple levels of boundary detail, or the shape of individual boundary elements).

Figure 5.12: Implementation of the EPB/PDO Representation

next up previous contents
Next: Stages in Path Planning Up: Reasoning About Path-Planning with Previous: The Path-Planning Problem
Alan Blackwell