Triangulation-based path planning for a mobile robot

L. D. Seneviratne, W. S. Ko, S. W.E. Earles

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


A triangulation-based path planning algorithm for a mobile robot is presented. A circular robot operating in a planar polygonal environment cluttered with polygonal obstacles is considered. The free space of the robot consists of a polygonal region with polygonal holes. A method called bridge building is presented for triangulating a simple polygon with polygonal holes. The free working space of the robot is thus triangulated, resulting in an exact cell decomposition. This enables a triangulation graph to be constructed, representing the topological connectivity of the free space, from which safe paths from the start to the goal can be found. The paths are contained within free channels bounded by the obstacles and the environmental boundaries. An important feature of the process is that many segments of a selected path are parallel to the environmental boundaries. This would enable relatively simple sensing devices, such as ultrasonic sensors, to be used for correcting navigation errors. The algorithm is computationally efficient, being of O(n2) complexity. :.

Original languageBritish English
Pages (from-to)365-371
Number of pages7
JournalProceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science
Issue number5
StatePublished - 1997


  • Collision avoidance
  • Exact cell decomposition
  • Path planning
  • Robot navigation
  • Triangulation


Dive into the research topics of 'Triangulation-based path planning for a mobile robot'. Together they form a unique fingerprint.

Cite this