Abstract:

Path planning for a point-mass robot moving in a cluttered two-dimensional environment is a well studied but non- trivial problem. In this paper we propose a novel computationally efficient and resolution-complete path generation method based on electrostatics. The proposed scheme comprises two stages. First, an auxiliary electrostatic problem is formulated where the boundary conditions of the Laplace equation are specified based on the map of the original path planning problem and is solved to obtain a map-specific electrostatic potential. Since its calculation only involves map, the electrostatic potential can be viewed as a roadmap and used for both single- and multi-query path planning problems. Second, feasible paths are constructed by following any equipotential curve whose potential value is different from those of obstacles and boundaries. The electrostatic potential differs from the celebrated repulsive/attractive force- based potential field by its non-vanishing gradient, subject to the resolution of the boundaries conditions for the Laplace equation. Consequently, the resolution-completeness of the pro- posed method is established. The computational efficiency of the proposed method arises from a novel electrostatic solver based on complex analysis, and on an original collision-checking algorithm inspired by the Residue theorem. Extensive numerical examples are provided to demonstrate the effectiveness and limitations of the proposed method. We believe this work provides an unconventional strategy for quantitatively encoding global map information and can play a role complementary to prevailing path planning methods.