On soft predicates in subdivision motion planning

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 x S1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms.

• Publication year

  2013

• Venue

  International Symposium on Computational Geometry

• Publication date

  2013-06-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2462356.2462386
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram

  2018cited by this paper
• Robotics

  2018cited by this paper
• Generalized Voronoi Diagrams for Moving a Ladder: I. Topological Analysis

  2015cited by this paper
• Soft subdivision search in motion planning

  2013cited by this paper
• Near optimal tree size bounds on a simple real root isolation algorithm

  2012cited by this paper
• Theory of Soft Subdivision Search and Motion Planning

  2012cited by this paper
• Towards exact numerical Voronoi diagrams

  2012cited by this paper
• ROBUST GEOMETRIC COMPUTATION

  2012cited by this paper
• Coordinating the Motion of Several Discs

  2011cited by this paper
• A simple but exact and efficient algorithm for complex root isolation

  2011cited by this paper
• When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial

  2011cited by this paper
• SqFreeEVAL: An (almost) optimal real-root isolation algorithm

  2011cited by this paper
• Motion Planning via Manifold Samples

  2011cited by this paper
• Motion Planning

  2011influential reference
• In Praise of Numerical Computation

  2010cited by this paper
• Constructing the Exact Voronoi Diagram of Arbitrary Lines in Space

  2010cited by this paper
• Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique

  2009cited by this paper
• The Voronoi diagram of three arbitrary lines in R3

  2009cited by this paper
• Theory of Real Computation According to EGC

  2008cited by this paper
• Motion planning for legged and humanoid robots

  2008cited by this paper
• Efficient Cell Labelling and Path Non-existence Computation using C-obstacle Query

  2008cited by this paper
• The Voronoi Diagram of Three Lines

  2007cited by this paper
• Principles of Robot Motion: Theory, Algorithms and Implementations by Howie Choset, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia E. Kavraki and Sebastian Thrun, 603 pp., $60.00, ISBN 0-262-033275

  2007cited by this paper
• OOPS for Motion Planning: An Online, Open-source, Programming System

  2007cited by this paper
• The predicates of the Apollonius diagram: Algorithmic analysis and implementation

  2006cited by this paper
• On the Probabilistic Foundations of Probabilistic Roadmap Planning

  2006cited by this paper
• Robot Motion Planning

  2006cited by this paper
• Shortest path amidst disc obstacles is computable

  2005cited by this paper
• Star-shaped Roadmaps - A Deterministic Sampling Approach for Complete Motion Planning

  2005cited by this paper
• Principles of Robot Motion: Theory, Algorithms, and Implementations [Book Review]

  2005influential reference
• Accurate Minkowski sum approximation of polyhedral models

  2004cited by this paper
• Topology preserving surface extraction using adaptive subdivision

  2004cited by this paper
• Classroom Examples of Robustness Problems in Geometric Computations

  2004cited by this paper
• Algorithmic motion planning

  2004cited by this paper
• Resolution complete rapidly-exploring random trees

  2002cited by this paper
• Nonuniform Discretization for Kinodynamic Motion Planning and its Applications

  2000cited by this paper
• Robot Motion Planning and Control

  1998cited by this paper
• Handbook of Discrete and Computational Geometry, Second Edition

  1997cited by this paper
• Probabilistic Roadmaps for Path Planning in High-Dimensional Con(cid:12)guration Spaces

  1996cited by this paper
• Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest paths trees

  1995cited by this paper
• An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere

  1995cited by this paper
• Toward an exact incremental geometric robot motion planner

  1995cited by this paper
• Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds

  1995cited by this paper
• New heuristic algorithms for efficient hierarchical path planning

  1991influential reference
• Computing Roadmaps of General Semi-Algebraic Sets

  1991cited by this paper
• AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

  1987cited by this paper
• A sweepline algorithm for Voronoi diagrams

  1986cited by this paper
• Planning, geometry, and complexity of robot motion

  1986cited by this paper
• A "Piano Movers" Problem.

  1986cited by this paper
• A "Retraction" Method for Planning the Motion of a Disc

  1985cited by this paper
• On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers

  1983influential reference
• On the Piano Movers' Problem : III

  1983cited by this paper
• On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds

  1983cited by this paper
• A subdivision algorithm in configuration space for findpath with rotation

  1983influential reference
• On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriers

  1983cited by this paper

• A Note on the Time Complexity of Using Subdivision Methods for the Approximation of Fibers

  2025cites this paper
• Distortion Bounds of Subdivision Models for SO(3)

  2025cites this paper
• Theory and Explicit Design of a Path Planner for an SE(3) Robot

  2024influential citation
• Proceedings of the 1 st Workshop on Robotics Challenges and Vision (RCV2013)

  2021influential citation
• Certified Approximation Algorithms for the Fermat Point and n-Ellipses

  2021cites this paper
• Certified Approximation Algorithms for the Fermat Point

  2020cites this paper
• Rods and Rings: Soft Subdivision Planner for R^3 x S^2

  2019influential citation
• Towards Soft Exact Computation (Invited Talk)

  2019cites this paper
• Towards Soft Exact Computation

  2019influential citation
• New Challenges in Parallelism

  2018cites this paper
• The Complexity of Subdivision for Diameter-Distance Tests

  2018cites this paper
• Finding Intersections of Algebraic curves in a Convex Region using Encasement

  2018cites this paper
• Soft Subdivision Motion Planning for Complex Planar Robots

  2018cites this paper
• The Complexity of an Adaptive Subdivision Method for Approximating Real Curves

  2017cites this paper
• Robust free space construction for a polyhedron with planar motion

  2017cites this paper
• Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots

  2017cites this paper
• Implications of Motion Planning: Optimality and k-survivability

  2016cites this paper
• Path Planning for Simple Robots using Soft Subdivision Search

  2016cites this paper
• 51 Robotics

  2016cites this paper
• Robust Geometric Computation

  2016cites this paper
• Soft Subdivision Planner for a Rod ∗

  2016cites this paper
• Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams

  2016cites this paper
• Metric cells: Towards complete search for optimal trajectories

  2015cites this paper
• Semi-dynamic Connectivity in the Plane

  2015influential citation
• Soft Subdivision Search in Motion Planning, II: Axiomatics

  2015cites this paper
• Resolution-Exact Algorithms for Link Robots

  2014influential citation
• Amortized analysis of smooth quadtrees in all dimensions

  2014cites this paper
• Resolution-Exact Planner for a 2-link Planar Robot using Soft Predicates

  2014influential citation
• Resolution-Exact Planner for Non-Crossing 2-Link Robot

  2014influential citation
• Proceedings of the 1st Workshop on Robotics Challenges and Vision (RCV2013)

  2014influential citation
• The 24 th Annual Fall Workshop on Computational Geometry at The University of Connecticut Friday October 31 , 2014

  2014cites this paper
• A subdivision approach to weighted voronoi diagrams

  2014cites this paper
• Soft subdivision search in motion planning

  2013influential citation
• Towards exact numerical Voronoi diagrams

  2012cites this paper
• Towards Exact Numerical Voronoi Diagrams ( Invited Talk )

  2012cites this paper
• Optimal Path Planning on a Semi-Dynamic Subdivision Graph ∗

  year unknowncites this paper