Files in this item

FilesDescriptionFormat

application/pdf

application/pdfECE499-Sp2012-mccarthy.pdf (517kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Proving Path Non-Existence Using Sampling and Alpha Shapes
Author(s):McCarthy, Zoe
Contributor(s):Bretl, Timothy
Subject(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.
Issue Date:2012-05
Genre:Other
Type:Text
Language:English
URI:http://hdl.handle.net/2142/46495
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Sponsor:NSF
Date Available in IDEALS:2014-01-09


This item appears in the following Collection(s)

Item Statistics