Extended triangulation algorithm for robot path planning with obstacle avoidance

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


Presented is a strategy for planning a smooth collision-free trajectory by a modified triangulation algorithm, for a three-wheel omni-directional mobile robot, which is equipped with an on-board ultrasonic sensor system. The robot environment consist of polygonal obstacles. Planning such a trajectory consists of three principal serial operations. First, the free space of the mobile robot is triangulated into a number of triangular partitions. This operation is identical to the decomposition process of the triangulation path planning algorithm. Second, instead of a geometrical line-line path planned on the incenter-node triangulation graph, the searching is done on a topological graph which explicitly represents the connectivity of the triangular partitions, resulting in a solution channel. This solution channel is a subset of the system's free space. Third, a collision free trajectory of the mobile robot is planned inside the solution channel taking into account the mechanical features of the mobile robot, such as the velocity and acceleration profiles of motors, and dimensions of the mobile robot. There are two principal advantages of the revised algorithm over its earlier version. Since the proposed solution channel accommodates a number of paths, mainly due to its collision tolerances, the revised triangulation algorithm allows the mobile robot to deal with unexpected events or objects while the mobile robot is executing a globally designated trajectory. In addition, while moving along the proposed trajectory the mobile robot is able to utilize its on board ultrasonic sensors to monitor the cumulative errors in the motion trajectory.

Original languageBritish English
Title of host publicationDynamic Systems, Simulation, and Control
EditorsA. Faghri, M.A. Yaghoubi
Number of pages8
StatePublished - 1994
EventProceedings of the 2nd Biennial European Joint Conference on Engineering Systems Design and Analysis. Part 1 (of 8) - London, Engl
Duration: 4 Jul 19947 Jul 1994

Publication series

NameAmerican Society of Mechanical Engineers, Petroleum Division (Publication) PD


ConferenceProceedings of the 2nd Biennial European Joint Conference on Engineering Systems Design and Analysis. Part 1 (of 8)
CityLondon, Engl


Dive into the research topics of 'Extended triangulation algorithm for robot path planning with obstacle avoidance'. Together they form a unique fingerprint.

Cite this