2017 · 19 citations · 0 references
ComputingAutonomous SystemsComputer ScienceMotion PlanningPath PlanningRoboticsHeuristic SearchNavigation PlanningObstacle AvoidanceRobot Motion PlanningRobot NavigationAdmissible HeuristicsEmpirical EvaluationGridsHeuristic Search In RoboticsRobotic Path PlanningTrajectory Planning
Grid pathfinding, an old AI problem, is central for the development of navigation systems for autonomous agents. A surprising fact about the vast literature on this problem is that very limited neighborhoods have been studied. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2 k -neighborhoods. First, we provide a simple recursive definition of the 2 k -neighborhood in terms of the 2 k –1 -neighborhood. Second, we derive distance functions, for any k >1, which allow us to propose admissible heurisitics which are perfect for obstacle-free grids. Third, we describe a canonical ordering which allows us to implement a version of A* whose performance scales well when increasing k . Our empirical evaluation shows that the heuristics we propose are superior to the Euclidean distance (ED) when regular A* is used. For grids beyond 64 the overhead of computing the heuristic yields decreased time performance compared to the ED. We found also that a configuration of our A*-based implementation, without canonical orders, is competitive with the any-angle path planner Theta$^*$ both in terms of solution quality and runtime.