Provably Constant-Time Motion Planning

Abstract

In many robotic applications, including logistics and manufacturing, robots often operate in semi-structured environments and perform highly repetitive manipulation tasks. Additionally, large parts of these environments are static most of the time. Fast and reliable motion planning is one of the key elements that ensure efficient operations in such environments. A very common example scenario is of manipulators working at conveyor belts, where they have limited time to pick moving items and if the planner exceeds a certain time threshold, they would fail to pick the items up. Similar scenarios are encountered in automated assembly lines. Such time-critical applications spur the need for planners which are guaranteed to be fast. To this end we introduce and formalize the concept of Constant-Time Motion Planning (CTMP); namely, the ability to provably guarantee to generate a motion plan within a (small) constant time. We then develop several algorithms that fall into the class of CTMP algorithms.

This thesis presents constant-time motion planning algorithms for three types of semi-structured environments: (1) static environments (2) semi-static environments and (3) dynamic environments (specifically for the task of picking up moving objects off a conveyor belt). For (1) we assume that the environment occupancy remains purely static during the robot's operation. For (2) we relax the purely-static assumption by allowing a fixed number of known movable obstacles that may get displaced during operation. For (3), we assume that the overall environment is static but the goal, namely the object to be picked up, is moving and its position estimate may also improve over time as perception gets more data. In addition, we also demonstrate an application of our CTMP framework for a manipulation task of a robot protecting itself with a shield from incoming attacks. For the conveyor-pickup and the shield-manipulation tasks, the robot typically perceives a rough pose estimate viewing from a distance, but it must start moving early on (relying on that rough estimate) and then adjust its motion by continuously replanning in real time as it gets improved estimates, to be able to reach the object in time. To this end, we also show how CTMP algorithms can be extended to provide constant-time re-planning capability.

Our key insight is that for highly recurring tasks in semi-structured environments, the space in which the robot operates is a very small subset of its configuration space. This allows us to preprocess it exhaustively. The preprocessing step generates a small representative set of paths that can be used by search at query time in a way that guarantees small constant-time planning for any planning query.

For domain (1), we evaluated our approach on a mail-sorting task in simulation on PR2 and also tested it on a real truck-unloading robot. For (2), we tested our algorithm on the Franka robot in simulation and on the real robot for pick and place tasks in a kitchen environment. For (3) we performed real-robot experiments on PR2 working at a conveyor belt. Finally, for the shield-manipulation task, we ran experiments on the PR2 in simulation and on the real robot.