Sampling-based motion planners are an effective means for generating collision-free motion paths. However, the quality of these motion paths (with respect to quality measures such as path length, clearance, smoothness or energy) is often notoriously low, especially in high-dimensional configuration spaces. We introduce a simple algorithm for merging an arbitrary number of input motion paths into a hybrid output path of superior quality, for a broad and general formulation of path quality. Our approach is based on the observation that the quality of certain sub-paths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed for comparing and clustering multiple motion paths, reduces the running time of the merging algorithm significantly. We tested our algorithm in motion-planning problems with up to 12 degrees of freedom. We show that our algorithm is able to merge a handful of input paths produced by several different motion planners to produce output paths of much higher quality.
Two paths are said to be homotopy equivalent if one path can be continuously deformed into the other, without introducing any collisions along the way. Often the output path of a roadmap is homotopy equivalent to another higher-quality path. In this case, post-processing procedures ignore the roadmap that originally created the path, and focus on small perturbations that improve the path within its homotopy class. Path pruning and shortcut heuristics are common post-processing techniques for creating shorter and smoother paths, with little chance of switching between homotopy classes. Geraerts @cite_23 locally improved path clearance using a retraction schemes that resembles the approach taken by Wilmarth @cite_1 , and more recently @cite_20 , improved both path length and path clearance simultaneously (but not other criteria of path quality). Geraerts @cite_27 locally improved path quality within a corridor (an inflated path) by applying a force-field to the moving body within that corridor. In this case, the output path is restricted by construction to the selected corridor. In the Appendix, we discuss some more related work that deals with the very formulation of path-quality measures.
@cite_27 @cite_20 @cite_1 @cite_23
2037034267 2563402379 2085512211 1961231572
We address the fundamental problem of goal-directed path planning in an uncertain environment represented as a probability (of occupancy) map. Most methods generally use a threshold to reduce the grayscale map to a binary map before applying off-the-shelf techniques to find the best path. This raises the somewhat ill-posed question, what is the right (optimal) value to threshold the map? We instead suggest a persistent homology approach to the problem-a topological approach in which we seek the homology class of trajectories that is most persistent for the given probability map. In other words, we want the class of trajectories that is free of obstacles over the largest range of threshold values. In order to make this problem tractable, we use homology in ℤ 2 coefficients (instead of the standard ℤ coefficients), and describe how graph search-based algorithms can be used to find trajectories in different homology classes. Our simulation results demonstrate the efficiency and practical applicability of the algorithm proposed in this paper.paper. Allowing a human to express topological requirements to a robot in language enables untrained users to guide robot movement without requiring the human to understand sophisticated robot algorithms. By using a homotopy class or classes to represent one or more topological requirements, we build a framework that helps a robot understand a human's intent. This paper reviews a homotopic decomposition method that is used to convert any path into a string, which allows homotopic path equivalence to be performed by comparing strings. We then integrate the Homotopic Distributed Correspondence Graph (HoDCG) to infer the homotopic constraint in the format of strings from a language instruction. Finally, we use a homotopic path-planning algorithm that finds the optimal paths for a given objective and homotopic constraint. Experiment results show how a language instruction is converted into a path driven by an implicit topological requirement. The motion-planning problem, involving the computation of a collision-free path for a moving entity amidst obstacles, is a central problem in fields such robotics and game design. In this paper we study the problem of planning high-quality paths. A high-quality path should have some desirable properties: it should be short, avoiding long detours, and at the same time it should stay at a safe distance from the obstacles, namely it should have clearance. We suggest a quality measure for paths, which balances between the above criteria of minimizing the path length while maximizing its clearance. We analyze the properties of optimal paths according to our measure, and devise an approximation algorithm to compute near-optimal paths amidst polygonal obstacles in the plane. We also apply our quality measure to corridors. Instead of planning a one-dimensional motion path for a moving entity, it is often more convenient to let the entity move in a corridor, where the exact motion path is determined by a local pla... We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovasz relaxation. The Local Distribution LP is generally stronger than the Lovasz relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovasz relaxation gives a (2--2 k)-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2--2 k -- e)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2--2 k -- e)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence.