If the validity
of these nodes was not already checked during construction
of the Cntl-Rdmp, they will be checked now before adding
them to the approximate roadmap.
In node connection, we connect nodes corresponding to
adjacent edges in the Cntl-Rdmp. For each such connec-
tion, the two nodes are connected via a simple arc and a line
segment if needed. For example (see Figure 2), consider
´
µ
´
µ
two nodes Ö½ ½ and Ö¾ ¾ , and let their common end-
´
Ü Ý . Also,
point in the Cntl-Rdmp be Ö¿ , where Ö
Ö½ Ö¿ and
Ö¾ Ö¿ . Denote the an-
let
gle between the two edges as «. Then the curvature for the
ÓØ´ ¾µ Ñ Ò´ µ
«
arc is
, and the length of path is
½
·
£ « . The edge is added to roadmap, with-
out collision checking, if its curvature is smaller than some
threshold Ñ Ü . This coarse curvature test filters useless
nodes and edges from the roadmap.

The positional co-
ordinates of the nodes are the midpoints on the edges of
the Cntl-Rdmp, and their orientations are directed along the
edges, so as to align them with the roadway.

We next construct an approximate roadmap from the
Cntl-Rdmp. Intuitively, we will use the Cntl-Rdmp to help
us compose (rather than randomly generate) nodes in the
¼¾ µ
car-like robot’s ʾ ¢
C-space.