Optimal Motion Planning with constraints for mobile robot navigation

Abstract

Motion planning is the process of planning a sequence of motions to move an object from one configuration to another. Recently, randomized techniques known as PRMs have shown great potential for solving motion planning problems in complicated high-dimensional space. Motion Planning, or path planning for robots, becomes increasing difficult as the dimension of the planning space increases with the robot's degrees of freedom (dof). While the running time of deterministic motion planning algorithms grows exponentially with an increase in dof, PRMs can produce solutions in times that do not depend on the dof but only the difficulty of the problem. PRMs randomly generate collision free configurations in a robot's Configuration-space (Cspace), representing feasible positions and orientations for the robot. Nearby configurations are linked together by so-called local planners, and these connections are edges in a roadmap, a graph containing representative discrete paths the robot may travel. We present methods to extract optimal paths from roadmap-based motion planners. Our system uses Markov-like states and flexible goal states so that general optimization criteria including collision detection, kinematic/dynamic constraints, or minimum clearance can be used in various applications. Our algorithm is an augmented version of Dijkstra's shortest path algorithm. We present simulation results maximizing minimum path clearance, minimizing localization effort, and enforcing kinematic/ dynamic constraints.