An Equivalence Relation for Local Path Sets

Abstract

We propose a novel enhancement to the task of collision-testing a set of local paths. Our approach circumvents expensive collision-tests, yet it declares a continuum of paths collision-free by exploiting both the structure of paths and the outcome of previous tests. We define a homotopy-like equivalence relation among local paths and provide algorithms to (1) classify paths based on equivalence, and (2) implicitly collision-test up to 90% of them. We then prove both correctness and completeness of these algorithms before providing experimental results showing a performance increase up to 300%.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2010
Accession Number
ADA532831

Entities

People

  • Matthew T. Mason
  • Ross A. Knepper
  • Siddhartha Srinivasa

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Collision Avoidance
  • Collisions
  • Curvature
  • Diameters
  • Dispersions
  • Electronic Mail
  • Environment
  • Geometry
  • Intervals
  • Line Of Sight
  • Motion Planning
  • Navigation
  • Robots
  • Sequences
  • Shape

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Vision.
  • Mathematical Modeling and Probability Theory.