Path Classes and Their Symbolic Representations

Let us introduce an abstract concept of path classes as one of the path-planning issues.

[1] Geometrical Paths

We presented the Circle Medley motion on the Circle-Tracking Atomic Motion page:

Circle Medley creates a series of motions,
in which Math Mind tracks n circles
making round trips.

The center position and the radius of each circle create Circle-Tracking Atomic Motions;
these are geometrically created motions.

If we geometrically represent these path data, for instance, using a dense sequence of points (x, y), saving the data requires a large amount of storage. On the other hand, while driving, we do not focus on such detailed geometrical information as the point (x, y) and other details. Furthermore, this geometrical-representation method has only a little insight regarding human drivers’ path understanding and planning at an abstract level. This page discusses higher-level path-representation concepts, symbolic representation of path, and others:

[2] Symbolic Representation of Paths

Consider a street map in a town. As shown in the diagram below, there are two paths P and Q from a home to a garage:

  • Path P is the one that takes 12th Street first and 7th Avenue second.
  • Path Q is the one that takes 8th Avenue first and 13th Street second.

There is an abstract method to represent paths P and Q. Let us look at a street block bounded by 7th and 8th Avenues and 12th and13th Streets in the diagram; name it Z. Then,

  • Path P negotiates with Z counterclockwise. We name this path Z+.
  • Path Q negotiates with Z clockwise. We name this path Z-.

This representation possesses a couple of advantages. One, it captures meaningful insight into how the paths negotiate with block Z. Two, this representation consumes only a little amount of data, i.e., only two characters for each. This method is applied to more general situations, as shown below. First, we generate a path N:

For this Slalom motion, a user inputs
using the buttons: A±, B±, C±, D±, and E±
in the right part of the screen.

We call this geometrical path N.

Next, we generate a path M:

For this Slalom motion, a user inputs
using the buttons.

We call this geometrical path M.

Notice that these two paths M and N share the start and goal points. We cannot continuously distort path M to path N without crossing any obstacles, A, B, C, D, E without moving both endpoints.

[3] Homotopy and Path Classes

In this slalom world, given two endpoints Start and Goal, we define a relation homotopic and a concept path class as follows:

(a) Homotopic Relation
If we can continuously distort a path P to a path Q without crossing any obstacles A, B, C, D, E, with both endpoints unmoved, P and Q are said to be homotopic. This homotopic relation of the two paths is an equivalence relation. We can intuitively tell that M and N defined above are not homotopic.

(b) Path Class
We know that an equivalence relation defines an equivalence class given a representative. Therefore, the homotopic relation defines a path class given a representative path.

  • We call the path class defined by path N “A+B-C+D-E-.” This class consists of infinitely many paths that are “similar” to N, including N itself.
  • We call the path class defined by path M “A+B-C+D-E+.” This class consists of infinitely many paths that are “similar” to M, including M itself.

This path-class concept stands for our intuitive understanding about “similarity” of paths; we say two specific geometric paths are similar if we can distort one path to the other, and detailed variations of paths do not matter, but whether we can distort one path to the other does.

The symbol A+ means that this path negotiates object “A” counterclockwise and A- clockwise. The symbolic path representation, A+B-C+D-E-, requires only ten characters. Sharing the meanings of these symbols between cars and humans will significantly reduce communication costs. The use of symbols is the fundamental feature of Artificial Intelligence, and driverless cars eventually have to master how to use symbols.

[4] Path Classes in a Block World

We apply the above symbolic path-representation method to a block world.

In a “block world” shown in this video,
we can represent path classes using
the symbolic method as discussed in [3].

In this example, a user clicks buttons
to define a path class: