PROBABILISTIC ROADMAPS FOR PATH PLANNING IN HIGH-DIMENSIONAL CONFIGURATION-SPACES

A new motion planning method for robots in static workspaces is presen ted, This method proceeds in two phases: a learning phase and a query phase, In the learning phase, a probabilistic roadmap is constructed a nd stored as a graph whose nodes correspond to collision-free configur ations and whose edges correspond to feasible paths between these conf igurations, These paths are computed using a simple and fast local pla nner, In the query phase, any given start and goal configurations of t he robot are connected to two nodes of the roadmap; the roadmap is the n searched for a path joining these two nodes, The method is general a nd easy to implement, It can be applied to virtually any type of holon omic robot, It requires selecting certain parameters (e.g., the durati on of the learning phase) whose values depend on the scene, that is th e robot and its workspace, But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the consid ered robots, In this paper the method is applied to planar articulated robots with many degrees of freedom, Experimental results show that p ath planning can be done in a fraction of a second on a contemporary w orkstation (approximate to 150 MIPS), after learning for relatively sh ort periods of time (a few dozen seconds).