论文标题
一种通用的A*算法，用于在加权彩色图中查找全球最佳路径
A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs
论文作者
论文摘要
搜索空间的几何信息和语义信息对于一个好的计划至关重要。我们在加权彩色图中编码这些属性（根据边缘的重量和语义信息的边缘和顶点颜色，几何信息），并提出了一个广义的a*，以在一组路径之间找到最短路径，而低排名的颜色边缘最小包含。我们证明了此类订购的A*（COA*）算法的完整性和最佳性，相对于所定义的最佳概念。 COA*的效用在三元图中进行了数值验证，该图具有可行，不可行的，不明的顶点和边缘，用于2D移动机器人，3D机器人臂以及具有有限感官功能的5D机器人臂。我们将COA*的结果与常规A*算法的结果进行了比较，后者发现最短路径无论不确定性如何，我们表明COA*在发现较少不确定的路径方面占主导地位。
Both geometric and semantic information of the search space is 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 the shortest path regardless of uncertainty, and we show that the COA* dominates the A* solution in terms of finding less uncertain paths.
