University of Illinois Urbana-Champaign

Proving Path Non-Existence Using Sampling and Alpha Shapes

McCarthy, Zoe

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/46495

Description

Title
Proving Path Non-Existence Using Sampling and Alpha Shapes
Author(s)
McCarthy, Zoe
Contributor(s)
Bretl, Timothy
Issue Date
2012-05
Keyword(s)
  • robotics
  • robotic control
  • robot motion planning
  • alpha shapes
  • configuration space
Abstract
In this thesis, we address the problem of determining the connectivity of a robot's free configuration space. Our method iteratively builds a constructive proof that two configurations lie in disjoint components of the free configuration space. Our algorithm first generates samples that correspond to configurations for which the robot is in collision with an obstacle. These samples are then weighted by their generalized penetration distance and used to construct alpha shapes. The alpha shape defines a collection of simplices that are fully contained within the configuration space obstacle region. These simplices can be used to quickly solve connectivity queries, which in turn can be used to define termination conditions for sampling-based planners. Such planners, while typically either resolution complete or probabilistically complete, are not able to determine when a path does not exist, and therefore would otherwise rely on heuristics to determine when the search for a free path should be abandoned. An implementation of the algorithm is provided for the case of a 3D Euclidean configuration space, and a proof of correctness is provided.
Type of Resource
text
Language
en
Permalink
http://hdl.handle.net/2142/46495
Sponsor(s)/Grant Number(s)
NSF

Owning Collections

Senior Theses - Electrical and Computer Engineering PRIMARY
The best of ECE undergraduate research