Linear-time path and motion planning algorithm for a tree climbing robot — TreeBot

Abstract

This paper proposes a path and motion planning algorithm for a tree climbing problem. This problem is challenging as the shape of tree is complex and irregular. To our best knowledge, this is the first paper dealing with the path planning problem on natural tree environment. Different from conventional motion planning approach that requires constructing a complex configuration space, this paper divides the planning problem into two parts, i.e., path and motion planning problem so as to reduce the dimension of the problem. An intuitive method to represent a climbing space is proposed that highly simplifies the path planning problem. With the use of a dynamic programming algorithm, an optimal path to reach a target position can be acquired in linear time. In addition, an efficient motion planning algorithm for a tree climbing robot named TreeBot is developed to make TreeBot follow the planned path.