A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs
Published:
Recommended citation: Lim, J., and Tsiotras, P., "A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs," 2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 7503-7509, doi: 10.1109/ICRA48506.2021.9561135.
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.