E. Plaku, L. E. Kavraki, and M. Y. Vardi, “Impact of Workspace Decompositions on Discrete Search Leading Continuous Exploration (DSLX) Motion Planning,” in IEEE International Conference on Robotics and Automation, Pasadena, CA, 2008, pp. 3751–3756.
We have recently proposed DSLX, a motion planner that significantly reduces the computational time for solving challenging kinodynamic problems by interleaving continuous state-space exploration with discrete search on a workspace decomposition. An important but inadequately understood aspect of DSLX is the role of the workspace decomposition on the computational efficiency of the planner. Understanding this role is important for successful applications of DSLX to increasingly complex robotic systems. This work shows that the granularity of the workspace decomposition directly impacts computational efficiency: DSLX is faster when the decomposition is neither too fine- nor too coarse-grained. Finding the right level of granularity can require extensive fine-tuning. This work demonstrates that significant computational efficiency can instead be obtained with no fine-tuning by using conforming Delaunay triangulations, which in the context of DSLX provide a natural workspace decomposition that allows an efficient interplay between continuous state-space exploration and discrete search. The results of this work are based on extensive experiments on DSLX using grid, trapezoidal, and triangular decompositions of various granularities to solve challenging first and second-order kinodynamic motion-planning problems.
Publisher: http://dx.doi.org/10.1109/ROBOT.2008.4543786