Robot Motion Planning in Time-varying Environments

Abstract

Motion planning is one of the principal tasks of autonomous robot systems. As a consequence, robot motion planning is one of the most active research areas in robotics and in the past decades great effort has been put into the development of flexible motion planning algorithms. The problems that needed to be tackled turned out to be demanding and most of the solutions found so far are restricted in the sense that they either find a collision free geometric path ignoring robot dynamics or they compute a time or energy optimal trajectory but they ignore collisions. The obvious goal, however, is to find a planning approach that respects both obstacles and robot dynamics. By including the time in the planning process it becomes possible to handle trajectories that are collision free and that also respect the dynamic limits of the robot. In addition, such a planning approach will be capable of dealing with time-varying obstacles. The position of such obstacles changes over time (but is known in advance for each point in time). Examples can be found in industrial manufacturing processes. Consider a robot in front of a production line with moving workpieces. In this thesis we present such a planning approach. Our motion planning algorithm considers robot dynamics (i.e. force and torque limits) and is able to deal with time-varying obstacles. Another characteristic of our approach is that the planning process and the process of generating trajectories are decoupled. This bears the advantage that our planner can handle different types of trajectories without modification. For example, point-to-point motions, path motions, or even special types of trajectories for non-holonomic robots. The planning process itself only handles base points, which define allowed areas for the actual trajectory. By modifying the position and the number of base points, the allowed trajectory area and consequently the trajectory itself is modified. To guide the planning process, we introduce several criteria upon which the evaluation of generated trajectories is based. Our main focus is on freedom from collision and robot dynamics, since these criteria have precedence over all other criteria, such as time or energy consumption. One of the main ingredients of motion planning in time-varying environments is a reliable algorithm for collision detection. We present an extension of an existing algorithm for static environments that enables us not only to detect collisions with moving obstacles but also gives us a precise rating of the depth of a collision. To demonstrate the usefulness of our approach, we have implemented our motion planning algorithm within the scope of a robot simulation system and we have tested it in various scenarios.