In this report, we present work towards a framework for modeling and checking behavior of spatially distributed component systems. Design goals of our framework are the ability to model spatial behavior in a component oriented, simple and intuitive way, the possibility to automatically analyse and verify systems and integration possibilities with other modeling and verification tools. We present examples and the verification steps necessary to prove properties such as range coverage or the absence of collisions between components and technical details.
 The Complexity of Robot Motion Planning makes original contributions both to robotics and to the analysis of algorithms. In this groundbreaking monograph John Canny resolves long-standing problems concerning the complexity of motion planning and, for the central problem of finding a collision free path for a jointed robot in the presence of obstacles, obtains exponential speedups over existing algorithms by applying high-powered new mathematical techniques.Canny's new algorithm for this "generalized movers' problem," the most-studied and basic robot motion planning problem, has a single exponential running time, and is polynomial for any given robot. The algorithm has an optimal running time exponent and is based on the notion of roadmaps - one-dimensional subsets of the robot's configuration space. In deriving the single exponential bound, Canny introduces and reveals the power of two tools that have not been previously used in geometric algorithms: the generalized (multivariable) resultant for a system of polynomials and Whitney's notion of stratified sets. He has also developed a novel representation of object orientation based on unnormalized quaternions which reduces the complexity of the algorithms and enhances their practical applicability.After dealing with the movers' problem, the book next attacks and derives several lower bounds on extensions of the problem: finding the shortest path among polyhedral obstacles, planning with velocity limits, and compliant motion planning with uncertainty. It introduces a clever technique, "path encoding," that allows a proof of NP-hardness for the first two problems and then shows that the general form of compliant motion planning, a problem that is the focus of a great deal of recent work in robotics, is non-deterministic exponential time hard. Canny proves this result using a highly original construction.John Canny received his doctorate from MIT And is an assistant professor in the Computer Science Division at the University of California, Berkeley. The Complexity of Robot Motion Planning is the winner of the 1987 ACM Doctoral Dissertation Award. Collision detection is a basic tool whose performance is of capital importancein order to achieve eciency in many robotics and computer graphics applica-tions, such as motion planning, obstacle avoidance, virtual prototyping, com-puter animation, physical-based modeling, dynamic simulation, and, in general,all those tasks involving the simulated motion of solids which cannot penetrateone another. In these applications, collision detection appears as a module orprocedure which exchanges information with other parts of the system concern-ing motion, kinematic and dynamic behaviour, etc. It is a widespread opinionto consider collision detection as the main bottleneck in these kinds of appli-cations.In fact, static interference detection, collision detection and the generationof con guration-space obstacles can be viewed as instances of the same prob-lem, where objects are tested for interference at a particular position, along atrajectory and throughout the whole workspace, respectively. The structure ofthis chapter reects this fact.Thus, the main guidelines in static interference detection are presented inSection 2. It is shown how hierarchical representations allow to focus on relevantregions where interference is most likely to occur, speeding up the whole inter-ference test procedure. Some interference tests reduce to detecting intersectionsbetween simple enclosing shapes, such as spheres or boxes aligned with the co-ordinate axes. However, in some situations, this approximate approach does notsuce, and exact basic interference tests (for polyhedral environments) are re-quired. The most widely used such test is that involving a segment (standing foran edge) and a polygon in 3D space (standing for a face of a polyhedron). In thiscontext, it has recently been proved that interference detection between non-convex polyhedra can be reduced, like many other problems in ComputationalGeometry, to checking some signs of vertex determinants, without computingnew geometric entities.Interference tests lie at the base of most collision detection algorithms,which are the subject of Section 3. These algorithms can be grouped into fourapproaches: multiple interference detection, swept volume interference, space- We present a data structure and an algorithm for efficient and exact interference detection amongst complex models undergoing rigid motion. The algorithm is applicable to all general polygonal models. It pre-computes a hierarchical representation of models using tight-fitting oriented bounding box trees (OBBTrees). At runtime, the algorithm traverses two such trees and tests for overlaps between oriented bounding boxes based on a separating axis theorem, which takes less than 200 operations in practice. It has been implemented and we compare its performance with other hierarchical data structures. In particular, it can robustly and accurately detect all the contacts between large complex geometries composed of hundreds of thousands of polygons at interactive rates. CR We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described. These algorithms have been successfully implemented and we discuss their performance in various environments. The problem of automatic collision-free path planning is central to mobile robot applications. An approach to automatic path planning based on a quadtree representation is presented. Hierarchical path-searching methods are introduced, which make use of this multiresolution representation, to speed up the path planning process considerably. The applicability of this approach to mobile robot path planning is discussed.