2020/12/23 by Jaein Lim, Panagiotis Tsiotras, Lim, Jaein +1 · 1 citation
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #Robotic Path Planning Algorithms #Robotics (cs.RO) #Systems and Control (eess.SY) #Vehicle Routing Optimization Methods #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2012.13057
openalex publication_date 2020/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Both geometric and semantic information of the search space is imperative for\na good plan. We encode those properties in a weighted colored graph (geometric\ninformation in terms of edge weight and semantic information in terms of edge\nand vertex color), and propose a generalized A* to find the shortest path among\nthe set of paths with minimal inclusion of low-ranked color edges. We prove the\ncompleteness and optimality of this Class-Ordered A* (COA*) algorithm with\nrespect to the hereto defined notion of optimality. The utility of COA* is\nnumerically validated in a ternary graph with feasible, infeasible, and unknown\nvertices and edges for the cases of a 2D mobile robot, a 3D robotic arm, and a\n5D robotic arm with limited sensing capabilities. We compare the results of\nCOA* to that of the regular A* algorithm, the latter of which finds the\nshortest path regardless of uncertainty, and we show that the COA* dominates\nthe A* solution in terms of finding less uncertain paths.\n