Motion planning for industrial robots

Abstract

Autonomous motion planning addresses the problem of nding collision-free paths for moving objects robots among obstacles. In this report we consider robots operating in workspaces occupied by stationary, completely known obstacles. We describe a new approach to probabilistic roadmap planners (PRMs). The overall theme of the algorithm, called Lazy PRM, is to minimise the number of collision checks performed during planning. Our algorithm builds a roadmap in the con- guration space, whose nodes are the user-dened initial and goal congurations and a number of randomly generated nodes. Neighbouring nodes are connected by edges representing the straight line path between the nodes. In contrast with PRMs, our planner initially assumes that all nodes and edges in the roadmap are collision-free, and searches the roadmap at hand for a shortest path between the initial and the goal node. The nodes and edges along the path are then checked for collision. If a collision with the obstacles occurs, the corresponding nodes and edges are removed from the roadmap. Our planner either nds a new shortest path, or rst updates the roadmap with new nodes and edges, and then searches for a shortest path. The above process is repeated until a collision-free path is returned.