Towards an orientation enhanced astar algorithm for robotic navigation

This paper presents an algorithm capable of generating smooth, feasible paths for an any-shape non-holonomic mobile robot, taking into account orientation restrictions, with the aim of navigating close to obstacles. Our contribution consists in an extension of the A* algorithm in a cell decomposition, where besides its position, the orientation of the platform is also considered when searching for a path. This is achieved by constructing 16 layers of orientations and only visiting neighbor layers when searching for the lowest cost. To simplify collision checking, the robot´s footprint is used to inflate obstacles, yet, to allow the robot to find paths close to obstacles, the actual footprint of the robot must used. By discretizing the orientation space into layers and computing an oriented footprint for each layer, the actual footprint of the robot is used, increasing the configuration space without becoming computationally expensive. The path planning algorithm was developed under the EU-funded project CARLoS¹ and was implemented in a stud welding robot simulated within a naval industry environment, validating our approach.