# 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.

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 a higher 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 downtown. 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 the 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* in a *slalom world*:

For this *Slalom* motion, a user inputs

“A+B-C+D-E-”

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

“A+B-C+D-E+”

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; actually, we can formally prove this claim if necessary (but we do not discuss it here).

(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,

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:

A+C-B+E+F-H-G+J+K-L+