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

Abstract

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
Volume211
Issue number5
DOIs
StatePublished - 1997

Keywords

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

Fingerprint

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

Cite this