A Multi-Purpose Off-Line Path Planner Based on an A* Search Algorithm

摘要

Abstract Efficient navigation of an autonomous mobile robot through a well-defined environment requires the ability of the robot to plan paths. An efficient and reliable planar off-line path planner has been developed that is based on the A* search method. Using this method, two types of planning are accomplished. The first uses a map of all known obstacles to determine the shortest-distance path from a start to goal configuration. The second determines the shortest path along a network of predefined roads. For the most complicated environment of obstacles and roads, a near-optimal piecewise-linear path is found within a few seconds. The planner can generate paths for robots capable of rotation about a point as well as car-like robots that have a minimum turning radius. For car-like robots, the planner can generate forward and reverse paths. This software is currently implemented on a computer controlled Kawasaki Mule 500 all-terrain vehicle and a computer controlled John Deere 690 excavator.