Mobile Robot Path Planning Algorithm by Equivalent Conduction Heat Flow Topology Optimization

[ Information ]

Structural and Multidisciplinary Optimization, vol. 45, no. 5, pp. 703-715, 2012.

[ Authors ]

Jae Chun Ryu, Frank C. Park, and Yoon Young Kim

[ Abstract ]

This paper addresses the path planning problem for a point robot moving in a planar environment filled with obstacles. Our approach is based on the principles of thermal conduction and structural topology optimization and rests on the observation that, by identifying the starting and ending configurations of a point robot as the heat source and sink of a conducting plate, respectively, the path planning problem can be formulated as a topology optimization problem that minimizes thermal compliance. Obstacles are modeled as regions of zero thermal conductivity; in fact, regions can be assigned varying levels of non-uniform conductivity depending on the application. We describe the details of our path planning algorithm, including the use of artificial mass constraints (particularly limits on the plate mass) to ensure convergence, and the choice of penalty exponents. The feasibility and practicality of our approach is validated through numerical experiments performed with several benchmarks, with intriguing possibilities for extension to more complex environments and real terrains. The benchmark problems of this paper mainly consist of obstacle-free path planning problems in two-dimensional space with maze-typed, symmetric, and spiral-type obstacles. We also address planning problems involving user-specified checkpoints, and also finding shortest paths on real three-dimensional terrain. To the authors’ knowledge, the path planning going through a stopover is considered for the first time.