Anil B. Suryawanshi, Milind B. Joshi, Bhaskar Dasgupta and
Arpan Biswas
by Domain Mapping as an Expeditionary Strategy for Fast Path Planning
Abstract:
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-dimensional domain, the mapping has been shown onto
convex hulls for the sake of better quality of mapping. However, for
3-dimensional 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.