Effectively planning the motion of objects in geometrically complex situations is of great practical importance for many tasks and domains. In robotics, it is necessary to maneuver robots through cluttered environments, such as a room full of chairs. In engineering design, it is necessary to detect undesired part interferences and establish assembly tolerances. In manufacturing, it is necessary to determine manipulation and assembly operations of parts into tight spaces, such as mounting the oil filter in a car engine. In computer graphics, it is necessary to realistically navigate, animate, and manipulate complex scenes without having to manually specify many keyframes. A practical planner for these realistically complex situations will have significant industrial impact: it will provide a rapid prototyping tool that allows the exploration of more scenarios, reduce design errors, and shorten the design and manufacturing cycle.
We propose to develop practical algorithms for approximate fine motion planning in geometrically complex situations. These situations are characterized by complex 3D robot and environment geometry, and complex motions with many degrees of freedom. The robot -- which can be any set of objects -- and the obstacles, are typically described by many thousands of facets and form a crowded environment requiring fine, coupled robot motions to navigate through tight openings and narrow passages. We will research the practical and theoretical aspects of the problem, develop useful problem-specific complexity metrics, empirically compare existing approaches, identify the main computational roadblocks, and develop effective strategies for fine motion planning.
Our technical approach will be based on incremental computation of approximate configuration space cells defined by local, linearized contact constraints [Joskowicz and Taylor 96] and geometrically coherent search strategies that will identify and effectively navigate very narrow and tight configuration space channels [Benchetrit 96]. The idea is to replace the inherently expensive collision detection computation with local incremental, approximate configuration space cell computation. We will evaluate the planner on practical examples from biomedicine and manufacturing.
![[Back]](arrow2.gif)