TY - JOUR
T1 - On soft predicates in subdivision motion planning
AU - Wang, Cong
AU - Chiang, Yi Jen
AU - Yap, Chee
N1 - Funding Information:
An extended abstract of this paper appeared in Proc. ACM Symposium on Computational Geometry (SoCG'13), pp. 349–358, 2013. This work is supported by NSF Grant CCF-0917093 and DOE Grant DE-SC0004874 .
Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2015/6/3
Y1 - 2015/6/3
N2 - We propose to design new algorithms for motion planning problems using the well-known Domain Subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K > 1, and takes an arbitrary input "resolution" parameter ε > 0 such that: if there is a path with clearance Kε, it will output a path with clearance ε/K; if there are no paths with clearance ε/K, it reports "NO PATH". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A∗ search and probabilistic search. Our algorithms are theoretically sound, practical, easy to implement, without implementation gaps, and have adaptive complexity. Our deterministic and probabilistic strategies avoid the Halting Problem of current probabilistically complete algorithms. We develop the first provably resolution-exact algorithms for motion-planning problems in SE(2)=R2×S1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms.
AB - We propose to design new algorithms for motion planning problems using the well-known Domain Subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K > 1, and takes an arbitrary input "resolution" parameter ε > 0 such that: if there is a path with clearance Kε, it will output a path with clearance ε/K; if there are no paths with clearance ε/K, it reports "NO PATH". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A∗ search and probabilistic search. Our algorithms are theoretically sound, practical, easy to implement, without implementation gaps, and have adaptive complexity. Our deterministic and probabilistic strategies avoid the Halting Problem of current probabilistically complete algorithms. We develop the first provably resolution-exact algorithms for motion-planning problems in SE(2)=R2×S1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms.
KW - Exact algorithms
KW - Motion planning
KW - Resolution-exact algorithms
KW - Soft predicates
KW - Subdivision algorithms
UR - http://www.scopus.com/inward/record.url?scp=84930379067&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84930379067&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2015.04.002
DO - 10.1016/j.comgeo.2015.04.002
M3 - Article
AN - SCOPUS:84930379067
VL - 48
SP - 589
EP - 605
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
SN - 0925-7721
IS - 8
ER -