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