The path-planning problem for autonomous mobile robots has been addressed by classical search techniques such as A* or, more recently, Theta*. However, research usually focuses on reducing the length of the path or the processing time. Applying these advances to autonomous robots may result in the obtained “short” routes being less suitable for the robot locomotion subsystem. That is, in some types of exploration robots, the heading changes can be very costly (i.e. consume a lot of battery) and therefore may be beneficial to slightly increase the length of the path and decrease the number of turns (and thus reduce the battery consumption). In this paper we present a path-planning algorithm called S-Theta* that
the turns of the path. This algorithm significantly reduces the heading changes, in both, indoors and outdoors problems as results show, making the algorithm especially suitable for robots whose ability to turn is limited or the associated cost is high.