A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs

Jaein Lim, Panagiotis Tsiotras

Abstract

Both geometric and semantic information of the search space are imperative for a good plan. We encode those properties in a weighted colored graph (geometric information in terms of edge weight and semantic information in terms of edge and vertex color) and propose a generalized A to find the shortest path among the set of paths with minimal inclusion of low-ranked color edges. We prove the completeness and optimality of this Class-Ordered A (COA) algorithm with respect to the hereto defined notion of optimality. The utility of COA is numerically validated in a ternary graph with feasible, infeasible, and unknown vertices and edges for the cases of a 2D mobile robot, a 3D robotic arm, and a 5D robotic arm with limited sensing capabilities. We compare the results of COA to that of the regular A algorithm, the latter of which finds a shortest path regardless of the semantic information, and we show that the COA dominates the A solution in terms of finding less uncertain paths.

Introduction

In autonomous navigation and robotic manipulation, a "good" path is rarely defined by distance alone. Semantic attributes—such as the probability of an area being blocked, the safety of a maneuver, or the reliability of sensor data—are often as important as geometric length. Traditional pathfinding algorithms like A* are designed to minimize a scalar cost, typically distance. When semantic information is available, researchers often resort to "soft constraints," where semantic risks are converted into additive penalties. However, this approach is fraught with issues: finding the "right" penalty value is difficult, and it can lead to "information non-monotonicity," where a robot with more information might choose an objectively worse path than one with less.

This paper introduces the Class-Ordered A (COA) algorithm, which treats semantic information as a primary sorting criterion. By leveraging a lexicographical ordering of path classes and costs, COA* guarantees the discovery of the shortest path among those that minimize exposure to undesirable semantic regions.

Methodology: Class-Ordered A (COA)

The foundation of our approach is the Weighted Colored Graph. In this representation, each vertex and edge possesses both a weight (geometric distance) and a "color" (semantic class). These classes are ranked in a total ordering, such as Feasible > Unknown > Infeasible.

The core innovation of COA lies in its priority queue management. Instead of a single scalar value, COA uses a four-tuple for lexicographical comparison:

  • Path-Class ($k_1, k_2$): These primary keys prioritize paths based on their semantic makeup. A path that avoids "Unknown" edges entirely will always be ranked higher than one that uses them, regardless of length.
  • Path-Cost ($k_3, k_4$): These act as tie-breakers. If two paths have the same semantic quality, the algorithm then chooses the shorter one.
The COA* algorithm navigating a 2D environment.

This ordering ensures that the algorithm first seeks paths that avoid low-ranked classes entirely. Furthermore, COA incorporates lazy evaluation* to handle computationally expensive color checks (e.g., collision detection in high-dimensional spaces) by deferring these calculations until necessary for search progression.

Experimental Validation

We validated COA* in three distinct scenarios: a 2D mobile robot, a 3D robotic arm, and a 5D robotic arm. In each case, the environment contained "unknown" regions that could potentially contain obstacles.

The results demonstrate that COA consistently outperforms standard A in terms of path reliability. While A frequently chooses "optimistic" shortcuts through unknown space that are later revealed to be blocked, COA prefers longer, known-safe routes. Quantitatively, COA showed a significantly lower uncertainty ratio—the proportion of the path length spent in unknown territory. Furthermore, COA exhibits information monotonicity: as the robot gains more information, the planned path is guaranteed to be at least as good as the previous one, a property not guaranteed by penalty-based methods.

Conclusion

The Class-Ordered A algorithm provides a robust framework for semantic path planning. By mathematically formalizing the priority of semantic classes over geometric distance, COA offers guarantees of completeness and optimality that are essential for safety-critical robotic applications. Future research will extend this framework to multi-agent coordination and dynamic environments.

Summary updated

Abstract

Both geometric and semantic information of the search space are imperative for a good plan. We encode those properties in a weighted colored graph (geometric information in terms of edge weight and semantic information in terms of edge and vertex color) and propose a generalized A<sup>&#x2217;</sup> to find the shortest path among the set of paths with minimal inclusion of low-ranked color edges. We prove the completeness and optimality of this Class-Ordered A<sup>&#x2217;</sup> (COA<sup>&#x2217;</sup> ) algorithm with respect to the hereto defined notion of optimality. The utility of COA<sup>&#x2217;</sup> is numerically validated in a ternary graph with feasible, infeasible, and unknown vertices and edges for the cases of a 2D mobile robot, a 3D robotic arm, and a 5D robotic arm with limited sensing capabilities. We compare the results of COA<sup>&#x2217;</sup> to that of the regular A<sup>&#x2217;</sup> algorithm, the latter of which finds a shortest path regardless of the semantic information, and we show that the COA<sup>&#x2217;</sup> dominates the A<sup>&#x2217;</sup> solution in terms of finding less uncertain paths.
BibTeX
@inproceedings{lim2021generalized,
  author = {Jaein Lim and Panagiotis Tsiotras},
  title = {{A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2021},
  doi = {10.1109/icra48506.2021.9561135},
}
Figure