Triangulation-based path planning for a mobile robot

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(n²) complexity.

Keywords

path planning collision avoidance robot navigation triangulation exact cell decomposition

Get full access to this article

View all access options for this article.

References

Schwartz

J. T.

Sharir

On the ‘piano movers’ problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Commun. Pure and Appl. Mathematics, 1983, XXXVI, 345–398.

Chen

C.-X.

Trivedi

M. M.

Bidlack

C. R.

Simulation and animation of sensor-driven robots. IEEE Trans. Robotics and Automn, October 1994, 10(5), 684–704.

Bhanu

Faugeras

Sridhar

Thorpe

C. E.

Introduction to the special section on perception-based real-world navigation. IEEE Trans. Robotics and Automn, December 1994, 10(6), 725–727.

Slack

M. G.

Navigation templates: Mediating qualitative guidance and quantitative control in mobile robots. IEEE Trans. Systems, Man, and Cybernetics, March-April 1993, 23(2), 452–466.

Spence

Hutchinson

An integrated architecture for robot motion planning and control in the presence of obstacles with unknown trajectories. IEEE Trans. Systems, Man, and Cybernetics, January 1995, 25(1), 100–110.

Hwang

Y. K.

Ahuja

A potential field approach to path planning. IEEE Trans. Robotics and Automn, February 1992, 8(1), 23–32.

Lengyle

Reichert

Donald

B. R.

Greenberg

D. P.

Real-time robot motion planning using rasterizing computer graphics hardware. Computer Graphics, August 1990, 24(4), 327–335.

Lozano-Perez

Wesley

M. A.

An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, October 1979, 22(10), 560–570.

Lozano-Perez

Spatial planning: A configuration space approach. IEEE Trans. Computers, February 1983, C-32(2), 108–120.

10.

Brooks

R. A.

Lozano-Perez

A subdivision algorithm in configuration space for findpath with rotation. IEEE Trans. Systems, Man, and Cybernetics, March-April 1985, SMC-15(2), 224–233.

11.

Bonner

Kelley

R. B.

A novel representation for planning 3-D collision-free paths. IEEE Trans. Systems, Man, and Cybernetics, November-December 1990, 20(6), 1337–1351.

12.

Brooks

R. A.

Solving the find-path problem by good representation of free space. IEEE Trans. Systems, Man, and Cybernetics, March-April 1983, SMC-13(3), 190–197.

13.

Nilsson

N. J.

Principles of Artificial Intelligence, 1982 (Springer-Verlag, New York).

14.

Liu

Choo

S.-H.

Lok

S.-L.

Leong

S.-M.

Lee

S.-C.

Poon

F.-P.

Tan

H.-H.

Finding the shortest route using cases, knowledge, and Dijkstra's algorithm. IEEE Expert, October 1994, 7–11.

15.

Liu

Y.-H.

Arimoto

Computation of the tangent graph of polygonal obstacles by moving-line processing. IEEE Trans. Robotics and Automn, December 1994, 10(6), 823–830.

16.

Takahashi

Schilling

R. J.

Motion planning in a plane using generalised Voronoi diagrams. IEEE Trans. Robotics and Automn, April 1989, 5(2), 143–150.

17.

Wilfong

G. T.

Motion planning for an autonomous vehicle. In Proceedings of the IEEE International Conference on Robotics and Automation,) 1988, pp. 529–533.

18.

Vasseur

H. A.

F. G.

Taylor

J. R.

Navigation of a car-like mobile robot using a decomposition of the environment in convex cells. Proceedings of the 1991 IEEE International Conference on Robotics and Automation, pp. 1496–1502.

19.

Chazelle

Incerpi

Triangulation and shape-complexity. ACM Trans. Graphics, April 1984, 3(2), 135–152.

20.

Woo

T. C.

Shin

S. Y.

A linear time algorithm for triangulating a point-visible polygon. ACM Trans. Graphics, January 1985, 4(1), 60–70.

21.

Fournier

Montuno

D. Y.

Triangulating simple polygons and equivalent problems. ACM Trans. Graphics, April 1984, 3(2), 153–174.

22.

Garey

M. R.

Johnson

D. S.

Preparata

F. P.

Tarjan

R. E.

Triangulating a simple polygon. Inf. Processing Lett., June 1978, 7(4), 175–179.

23.

Tarjan

R. E.

Van Wyk

C. J.

An O(nloglogn)-time algorithm for triangulating a simple polygon. SIAM J. Computing, February 1988, 17(1), 143–178.

24.

Ekoule

A. B.

Peyrin

F. C.

Odet

C. L.

A triangulation algorithm from arbitrary shaped multiple planar contours. ACM Trans. Graphics, April 1991, 10(2), 182–199.

25.

Wilson

R. J.

Introduction to Graph Theory, 1979 (Longman, London).

26.

W. S.

A navigation strategy for mobile robots in a manufacturing environment. PhD thesis, University of London, 1996.

27.

Mortenson

M. E.

Computer Graphics: An Introduction to the Mathematics and Geometry, 1989 (Heinemann Newnes).