Configuration spaces in robotic manipulation and motion planning.

摘要

The study of configuration spaces plays an important role space $C$ whose points are identified with distinct states of the system. This thesis considers three problems in robotics which can be solved by working in three very different configuration spaces.; The first problem, planning the motion of a robot in an obstacle filled room, uses a configuration space $C$ with one dimension for each degree of freedom of the robot. A solution corresponds to a free path in $C$, one where the robot intersects no obstacles. The Probabilistic Roadmap Method (PRM) approximates the free portion of $C$ with a one-dimensional roadmap by randomly sampling $C$ and connecting free configurations when appropriate. This is an effective approach in high dimensions, provided that $C$ contains no narrow corridors. Accordingly, this thesis introduces a Hierarchical PRM variant (HPRM), whose initially sparse sampling is refined in problem areas only when necessary, and is probabilistically complete in the sense that it generates a path when one exists with high probability. Implementation details are given for a planar articulated arm.; The remaining two problems concern the design of sensorless part feeders for automated assembly. The feeders considered move a part along a track which has been equipped with a series of either reorienting fences or rejecting traps designed so that any part which successfully runs the gauntlet is in the desired orientation. For fences, bars suspended across the track that reorient a part as it moves by, $C$ is a discrete graph whose nodes correspond to collections of orientations of the part. Successful fence designs correspond to certain paths in this graph, and can be computed in near-quadratic time. For traps, polygonal holes in the track which reject misaligned parts, $C$ is the infinite-dimensional space of all polygons. By considering only minimal traps, the problem is reduced to a finite number of one-dimensional searches, and a trap is designed in polynomial time. Both algorithms are complete, in the sense that a feeder is found whenever one exists.