Local roadmap adaptation for mobile manipulators in incrementally changing environments

Abstract

Mobile manipulators will be deployed in supermarkets for a large variety of tasks, for instance, for restocking products. The operation time of mobile manipulators can be reduced by generating coupled trajectories for the base and the robot's arm. When planning for high Degree of Freedom (DOF) robots, such as a mobile manipulator, in an obstacle-cluttered environment, the graph construction for sampling-based planners is time-consuming. If changes in the environment occur, most sampling-based algorithms reconstruct the entire graph. In some dynamic environments, planning can be simplified by the assumption of an incrementally changing environment; this is a mostly static environment where slight changes occur that do not violate the connectivity of the free configuration space, indicating that a significant part of the graph remains valid.

The main contribution of this thesis is a new motion planning algorithm: the adaptive roadmap algorithm (ARM). ARM is a multi-query sampling-based motion planning algorithm that can locally adapt vertices and edges of the graph to account for incremental changes in the environment to allow faster planning than algorithms that reconstruct the entire graph. ARM generates a 3D grid to represent the workspace. The grid cells are marked as occupied or free based on the presence of obstacles in the environment. To determine what vertices and edges of the roadmap need to be updated due to a change in the occupancy of the 3D grid by an incremental change, ARM assigns the vertices and edges to the 3D grid cells. ARM performs this assignment based on the workspace representations of the vertices and edges of the roadmap by 3D bounding boxes surrounding robot configurations. If the occupancy of one or multiple grid cells is changed due to an obstacle, the algorithm resamples the vertices associated with the occupied grid cells and removes the edges associated with the occupied grid cells. Then, the updated roadmap is used for motion planning, and if additional changes occur, this roadmap update is repeated.

We carried out different experiments in simulation performing coupled motion planning for mobile manipulators. A simplified implementation of ARM, which enables the implementation in the Robot Operating System, reported a 35-40% speedup of the planning time compared to the single-query algorithm rapidly-exploring random tree, which reconstructs the entire graph for every new query or change in the environment. The speedup the simplified implementation gained compared to existing planners will be magnified for the non-simplified ARM as the roadmap adaptation by ARM is 10% faster than by the simplified ARM. Further experiments demonstrated that the algorithm successfully adapted the roadmap for a real-world system, not merely in simulation. We conclude that local roadmap adaptation by our proposed algorithm allows faster planning than algorithms that reconstruct the entire graph for mobile manipulators in incrementally changing environments.