Algorithms for optimal design of robots in complex environments

Abstract

The goal of our work is to find the optimal design of a robot that can reach everywhere in an environment with obstacles without collisions. 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 environment? and what is the best placement for the robot? We describe some algorithms for finding the set of points in the environment that can reach all other points with a minimum number of links. Initially the obstacles are modeled as convex polygons and subsequently we discuss extensively the modifications that those algorithms require to cover curvilinear, non-convex and threedimensional obstacles. We derive several theorems that establish upper and lower bounds on the number of links for both planar and spatial cases. We describe some algorithms for minimizing the upper bounds to the optimal number of links for the environment. We generalize the basic prob...