Domain mapping as an expeditionary strategy for fast path planning

In this paper, a new approach to path planning in static configuration space is presented. This also includes the problem of finding a path in the presence of obstacles. The method proceeds in two phases: a domain mapping phase and a query phase. In the domain mapping, the region is mapped onto a chosen convex region. For implementation in 2-D domain, the mapping has been shown onto convex hulls for the sake of better quality of mapping. However, for 3-D cases, for simplicity, the target convex region has been taken as a sphere. An obstacle in the non-convex region is shrunk to a point. Thus, there are two regions, one is the given region and the other is the corresponding mapped region. In the query phase, given any two points in the original region, corresponding positions of the two points in the mapped region are found out from the mapping already established. In the mapped (convex) region, these two points are connected by a straight line. Now, inverting the entire path back to the original region, we can get the actual path. The path obtained by this method is optimal and is away from the boundary of the region. An algorithm for the above mentioned problem has been implemented and tested on various 2-D and 3-D non-convex regions. Results exhibit a strong potential of the method for path planning. (C) 2003 Elsevier Ltd. All rights reserved.