A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs
A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs
复制标题
一种在加权彩色图中寻找全局最优路径的广义 A* 算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
P. Tsiotras
中科院分区：
文献类型：
--
作者：
J. Lim;P. Tsiotras
搜索空间的几何和语义信息对于一个好的计划来说是必不可少的。我们将这些属性编码在加权彩色图中（边权重方面的几何信息以及边和顶点颜色方面的语义信息），并提出一个广义 A* 来找到路径集中包含最少低排名颜色边的最短路径。我们证明了该类排序 A* (COA*) 算法相对于迄今为止定义的最优性概念的完整性和最优性。对于 2D 移动机器人、3D 机械臂和传感能力有限的 5D 机械臂的情况，COA* 的实用性在具有可行、不可行和未知顶点和边的三元图中进行了数值验证。我们将 COA* 的结果与常规 A* 算法的结果进行比较，后者无论语义信息如何都会找到最短路径，并且我们表明 COA* 在寻找不确定性较小的路径方面优于 A* 解决方案。
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.