University of Sofia, Sofia, Bulgaria
The problem we discuss in this thesis is: given an environment with obstacles, what is the optimal design of a robot that can reach everywhere in this environment without collision with the obstacles. The main questions we are concerned with are: what is the most appropriate type for the links of the robot; what is the minimum number of links that are needed to cover every point in the free space; and what is the best placement for the robot in the environment.
The primary joint type we employ is a one degree of freedom prismatic joint which folds into itself like a telescope to some minimal length. Our robot is formed by connecting each telescopically jointed link to a revolute joint at its other end. The revolute axes are perpendicular to the prismatic axes. We call the links thus formed "telescoping links". All links of the robots that we are considering have telescoping structure.
In the first part of the thesis we discuss some algorithms for finding the set of points in the environment (the link center), that can reach all other points with minimum number of telescoping links. We start with the description and implementation of an algorithm that finds all visibility polygons from a given point when the obstacles are modelled as convex polygons. We use this algorithm in the implementation of algorithms for finding the link center and an approximate link center in this case. We discuss extensively the modifications and the additions that those algorithms require to cover curvilinear, non-convex and three-dimensional obstacles.
In the second part of the thesis we derive several theorems that establish upper and lower bounds on the number of links needed to cover the free space in both planar and spatial cases. We describe some algorithms for minimizing the upper bounds to, hopefully, the optimal number of links for the environment.
Finally we consider several generalizations to the basic problem for the cases when we design both the robot and the environment simultaneously, when we deal with moving robots and obstacles, multiple robots or robots with variable structure.
Provided a formal proof of an interesting geometrical theorem first formulated 500 years ago by Holditch. Several interesting and important generalizations and applications of this theorem were introduced.