Shortest path based path planning algorithm for nonholonomic mobile robots

Kaichun Jiang, Lakmal D. Seneviratne, S. W.E. Earles

Research output: Contribution to journalArticlepeer-review

46 Scopus citations


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.

Original languageBritish English
Pages (from-to)347-366
Number of pages20
JournalJournal of Intelligent and Robotic Systems: Theory and Applications
Issue number4
StatePublished - Apr 1999


Dive into the research topics of 'Shortest path based path planning algorithm for nonholonomic mobile robots'. Together they form a unique fingerprint.

Cite this