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

Jaein Lim, Panagiotis Tsiotras

TL;DR

Researchers at Georgia Tech have developed Class-Ordered A (COA), a path-planning algorithm that prioritizes semantic "quality" (like safety or certainty) over raw distance. By encoding environment data into weighted colored graphs, COA* finds the shortest possible path among those that minimize exposure to high-risk or unknown areas, providing a more robust solution for robots operating in partially mapped spaces.

What Problem Does This Paper Address?

Standard pathfinding algorithms like A* are designed to find the "shortest" path based on a single cost metric, usually distance. However, in the real world—think of a search-and-rescue drone or a surgical robot—distance isn't the only thing that matters. Some areas are "known-safe" (feasible), some are "known-blocked" (infeasible), and others are "unknown."

When a standard A* agent encounters an unknown region, it typically acts "optimistically," assuming the unknown space is empty to find a shortcut. This often leads to risky plans that fail once the robot actually senses an obstacle. While researchers have tried "soft-constraints" (adding a penalty for traversing unknown areas), these are notoriously difficult to tune and can lead to inconsistent behavior where a more "knowledgeable" robot actually picks a worse path than a "clueless" one. The authors address the need for a principled, consistent way to prioritize semantic information (like "don't go into the unknown unless you have to") without sacrificing the mathematical guarantees of optimality and completeness.

Methods

The authors introduce the Weighted Colored Graph, where every vertex and edge has both a weight (distance) and a "color" (a semantic class). These classes are ranked (e.g., Feasible > Unknown > Infeasible).

The core innovation is the Class-Ordered A (COA) algorithm. Unlike standard A which uses a single value to sort its priority queue, COA uses a lexicographical (dictionary-style) ordering with four distinct keys:

  1. $k_1$ & $k_2$ (Path-Class): These 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.
  2. $k_3$ & $k_4$ (Path-Cost): These act as tie-breakers. If two paths have the same semantic quality, the algorithm then chooses the shorter one.

COA also employs lazy evaluation*. Since determining the "color" of an edge (e.g., checking for collisions in a 5D robotic arm's workspace) can be computationally expensive, the algorithm uses heuristic estimates to delay the actual calculation until it is absolutely necessary for the search to progress.

Datasets

The paper evaluates the algorithm using simulated robotic environments rather than static datasets:

  • 2D Mobile Robot: Navigating a planar grid with obstacles.
  • 3D Robotic Arm: A 3-DOF arm moving through a workspace with "unknown" regions.
  • 5D Robotic Arm: A high-dimensional configuration space test to demonstrate the algorithm's scalability and the efficiency of its lazy evaluation.

Key Insights and Ideas

  • Semantic Primacy: The "aha moment" is treating semantic class as a primary sorting criteria rather than a secondary penalty. This ensures the robot only takes a "risky" path if no "safe" path exists.
  • Information Monotonicity: One of the strongest arguments for COA* is that it is "information monotonic." This means that as a robot gains more information about its environment, the quality of its planned path is guaranteed to stay the same or improve—a property that soft-constraint methods often lack.
  • Sub-additivity of Classes: The authors define a way to "add" path classes together, allowing the algorithm to keep track of the "worst" edge encountered on a path and how many times that class appears, ensuring the "best-worst" path is always found.

Key Results

  • Optimality and Completeness: The authors mathematically prove that COA* is guaranteed to find the globally optimal path (under their new definition) and will always find a path if one exists.
  • Reduced Uncertainty: In numerical simulations across 2D, 3D, and 5D scenarios, COA consistently produced paths with a significantly lower uncertainty ratio (the proportion of the path that is in unknown territory) compared to standard A.
  • Superiority in High Dimensions: The benefits of COA became even more pronounced in the 5D robotic arm tests. While standard A frequently committed to "optimistic" shortcuts that were later revealed to be blocked, COA* stayed in known-safe regions, leading to more reliable execution.

Limitations and Future Work

  • Class Ranking: The algorithm requires a pre-defined total ordering of classes. In complex environments with many overlapping concerns (e.g., battery life vs. safety vs. speed), defining this hierarchy might be non-trivial.
  • Computational Overhead: While lazy evaluation helps, maintaining a four-key priority queue and tracking path-class sequences is more complex than standard A*.
  • Future Directions: The authors suggest applying this framework to multi-agent systems, where different robots can share "colored" information (e.g., "Agent A is highly reliable, so its 'feasible' edges are better than Agent B's"). They also aim to explore more sophisticated heuristics for high-dimensional search spaces.

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

Loading related content...

Figure