Shortest path based path planning algorithm for nonholonomic mobile robots

A path planning algorithm for a mobile robot subject to nonholonomic constraints is presented. The algorithm employs a global-local strategy, and solves the problem in the 2D workspace of the robot, without generating the complex configuration space. Firstly, a visibility graph is constructed for finding a collision-free shortest path for a point. Secondly, the path for a point is evaluated to find whether it can be used as a reference to build up a feasible path for the mobile robot. If not, this path is discarded and the next shortest path is selected and evaluated until a right reference path is found. Thirdly, robot configurations are placed along the selected path in the way that the robot can move from one configuration to the next avoiding obstacles. Lemmas are introduced to ensure that the robot travels using direct, indirect or reversal manoeuvres. The algorithm is computationally efficient and runs in time O(nk+n log n) for k obstacles and n vertices. The path found is near optimal in terms of distance travelled. The algorithm is tested in computer simulations and test results are presented to demonstrate its versatility in complex environments.