A Genetic Algorithm for calculating minimum distance between convex and concave bodies

摘要

Distance determination, i.e. obtaining the distance between a pair of objects, is used in di¤erent applications such as the simulation of physical systems and robot path planning. Most of the existing algorithms focus on obtaining the separation distance and are limited to deal only with convex objects. In this work, a novel method for solving the minimum separation distance between convex and/or concave objects is presented. The method is based on the global optimization technique known as Genetic Algorithms (GA). Unlike previously developed works based on the use of optimization techniques to obtain the minimum distance amongst objects, the one presented here is not limited to convex objects, i.e. it does not require the concave objects to be partitioned into convex pieces. A simple local optimization method is also presented. It is shown that this method accelerates the convergence of the global stochastic search algorithm. A few examples with simple and complex objects are presented. The results obtained using di¤erent variations of the minimum distance method are compared. Particular attention is focused on the computational expense to obtain the solution as well as the precision of the solution.