On Finding Globally Optimal Paths through Weighted Colored Graphs

Abstract

In this paper, we present a method for finding a globally optimal path through a colored graph. Optimal here means that, for a given path, the induced path coloring corresponds to an equivalent class. A total ordering is placed over these equivalent classes, and the edge weights are simply tie breakers within the classes. Optimality is achieved by mapping the class, or color, of each edge in combination with its weight to a real number. As a result, optimal paths can be computed using just the new weight function and standard edge relaxation methods (e.g. Dijkstra’s Algorithm). The motivation for this research is the task of planning paths for mobile autonomous robots through outdoor environments with unknown and varied terrain.