We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d, the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d \\Gamma 1 for pairs of robots, and d \\Gamma 2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the st...

Many algorithms developed in computationid geometry are needlessly complicated and slow because they have to be prepared for very complicated, hypathetical inputs.To avoid this, realistic models are needed that describe the properties that realistic inputs have, so that algorithms can de designed that take advantage of these properties.This can lead to algorithms that are provably efficient in realktic situations.We obtain some fundamental results in this research direction.In particular, we have the following results.. We show the relations between various models that have been proposed in the literature.q For several of these models, we give algorithms to compute the model parameter(s) for a given scene; these algorithms can be used to verify whether a model is appropriate for typical scenesin some application area.q As a case study, we give some experimental results on the appropriateness of some of the models for one particular type of scenes often encountered in GIS, namely certain triangulated irregular networks.

The motion planning problem requires that a collision-free path be determined for a robot moving amidst a fixed set of obstacles. Most neural network approaches to this problem are for the situation in which only local knowledge about the configuration space is available. The main goal of the paper is to show that neural networks are also suitable tools in situations with complete knowledge of the configuration space. In this paper we present an approach that combines a neural network and deterministic techniques. We define a colored version of Kohonen's self-organizing map that consists of two different classes of nodes. The network is presented with random configurations of the robot and, from this information, it constructs a road map of possible motions in the work space. The map is a growing network, and different nodes are used to approximate boundaries of obstacles and the Voronoi diagram of the obstacles, respectively. In a second phase, the positions of the two kinds of nodes are combined to obtain the road map. In this way a number of typical problems with small obstacles and passages are avoided, and the required number of nodes for a given accuracy is within reasonable limits. This road map is searched to find a motion connecting the given source and goal configurations of the robot. The algorithm is simple and general; the only specific computation that is required is a check for intersection of two polygons. We implemented the algorithm for planar robots allowing both translation and rotation and experiments show that compared to conventional techniques it performs well, even for difficult motion planning scenes.

A tractor-trailer robot consists of a car-like tractor towing a passive trailer. Due to its highly nonholonomic nature, the kinematics of this type of robot are complicated and difficult to compute. We present exact closed-form solutions for the kinematic parameters of a tractor-trailer robot and use them to construct an exact and efficient motion planner in the absence of obstacles. This local planner can be employed in a probabilistic global planner, which allows us to plan motions in the presence of obstacles.