Motion planning is a major topic in robotics. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical ...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
Motion planning is a major topic in robotics. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical guarantees. Recently, we have proposed a subdivision approach based on soft predicates Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG'13), pp. 349-358 (2013). To appear CGTA, Special Issue for SoCG' 13 [20], but with a new notion of correctness called resolution-exactness. Unlike mos ques for planar link robots. The technical contributions of this paper are the design of soft predicates for link robots, a novel "T/R splitting method" for subdivision, and feature-based search strategies. The T/R idea is to give primacy to the translational (T) components, and perform splitting of rotational components (R) only at the leaves of a subdivision tree. We implemented our algorithm for a 2-link robot with 4 degrees of freedom (DOFs). Our implementation achieves real-time performance on a variety of nontrivial scenarios. For comparison, our method outperforms sampling-based methods significantly. We extend our 2-link planner to thick link robots with little impact on performance. Note that there are no known exactalgorithms for thick link robots.
The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detect...
详细信息
The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between their implementability and their accuracy/effectivity. In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O (m(3)) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots. We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods. (c) 2020 Elsevier B.V. All rights reserved.
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 geo...
详细信息
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 epsilon > 0 such that: if there is a path with clearance K epsilon, it will output a path with clearance epsilon/K;if there are no paths with clearance epsilon/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) = R-2 x S-1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms. (C) 2015 Elsevier B.V. All rights reserved.
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 geo...
详细信息
ISBN:
(纸本)9781450320313
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 epsilon > 0 such that: if there is a path with clearance K epsilon, it will output a path with clearance epsilon/K;if there are no paths with clearance epsilon/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) = R-2 x S-1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms. (C) 2015 Elsevier B.V. All rights reserved.
暂无评论