Based on evolutionary computation (EC) concepts, we developed an adaptive evolutionary planner/navigator (EP/N) as a novel approach to path planning and navigation. The EP/N is characterized by generality, flexibility, and adaptability. It unifies off-line planning and online planning/navigation processes in the same evolutionary algorithm which 1) accommodates different optimization criteria and changes in these criteria, 2) incorporates various types of problem-specific domain knowledge, and 3) enables good tradeoffs among near-optimality of paths, high planning efficiency, and effective handling of unknown obstacles. More importantly, the EP/N can self-tune its performance for different task environments and changes in such environments, mostly through adapting probabilities of its operators and adjusting paths constantly, even during a robot's motion toward the goal.

A complete, precise, and systematic analysis on the geometrical nature of contacts between two arbitrary polygons and derivation of the geometric contact constraints between two such polygons are provided. Based on the results, a general algorithm is presented to identify the geometrically valid contact formations (CFs) from a given set S/sub pc/ of possible principal contacts (PCs) between two polygonal objects with location uncertainties. For any (nonempty) subset of S/sub pc/, the algorithm tests if the PCs in the set form a possible CF by verifying the geometrical contact constraints. The obtained set of geometrically valid CFs can serve as input to an additional verifier based on force sensing which can extract the actual CF from the set. The notion of equivalent CFs is introduced to describe those contact situations constraining the relative location between two objects to the same region. This concept proves to be extremely useful to the completeness of the analysis and efficiency of the algorithm. Of the many discoveries, a particularly significant one is that despite uncertainties in object locations, in many cases, if two or more PCs are formed between two objects, their relative location is fixed or can take up to only four solutions.

Distance computation is essential for collision prediction and/or detection in real-world robotic tasks, computer simulation and animation, and CAD/CAM. This paper addresses distance computation to deal with a rarely researched type of collision prediction/detection problem: Given two objects in certain contact, determine if and when a relative rotation constrained by contact will cause a collision (which results in a new contact state) between the two objects. The authors use the positive angle of rotation as the measure of rotation distance and present a method to compute, given two contacting convex polyhedra G and H and a rotation axis containing contact point(s) between them, the shortest rotation distance (SRD) of G which will cause new collision between G and H. The method is fully implemented and used in a computer simulation system for a contact-based fine motion planning scheme. The algorithm is also efficient. If each vertex of G or H is the intersection of n/sub e//spl nu// edges, the worst-case time complexity of the algorithm is O(n/sup 2//sub e//spl nu//). This means that for two arbitrary trihedral polyhedra, the algorithm has a constant worst-time complexity.

A large number of robotic tasks require precision and thus the dealing with uncertainties. The effects of various uncertainties often manifest to location (i.e., position and orientation) uncertainties of objects. Thus, an important problem that often arises is how to assess the region that an object may occupy in the presence of uncertainties. This paper addresses the problem by describing how to grow exactly an arbitrary polyhedral object in the three-dimensional Cartesian space by its position and/or orientation uncertainties. Three types of related regions for the object are described: (1) the grown regions, regions possibly occupied by the object due to uncertainties in its position, orientation, or both, (2) the grown shell regions, regions possibly occupied by the boundary (surfaces) of the object due to uncertainties in its position, orientation or both, and (3) the core regions, regions (which could be empty) definitely occupied by the object in spite of uncertainty. The exact representations introduced in this paper can serve as benchmarks against which efficient but approximate algorithms may be evaluated. A particularly important application of the grown shell regions is in obtaining the set of all possible topological contacts among polyhedral objects due to location uncertainties. Such a set can serve as a basis from which more precise contact information can be extracted by additional sensing means, such as vision and force/moment sensing. The approach for this application and its implementation is introduced and discussed.

An implemented algorithm is presented for finding all principal contacts possibly established between two surface features (i.e. faces, edges, or vertices) of two polyhedral objects due to location (i.e. position and orientation) uncertainties. The algorithm FAPRIC (finding all principal contacts) requires as inputs: the estimated locations of the two objects, the geometric models of the objects, and the bounds on position and orientation uncertainties. The algorithm is based on checking intersections between the grown regions of the objects by location uncertainties with the S-tope model. It is very efficient and apt for real-time processing. The information obtained can serve as a guide for more accurate extraction and further reasoning of the contact data, possibly with additional sensors. As the surface of an arbitrary object can be approximated by planar patches, the algorithm can also be applied to general objects. The work is motivated by the need for automatically recognizing contacts in spite of uncertainties in robotic tasks.

A general strategy is presented to determine the geometrically valid contact formations (CFs) from a given set S/sub pc/ of possible principal contacts (PCs) between two arbitrary polygonal objects in the presence of location uncertainties. For any (non-empty) subset of S/sub pc/, the strategy tests if the PCs in the set form a possible CB by analyzing the geometrical contact constraints. The obtained set of geometrically valid CFs can serve as input to a verifier based on force sensing which will identify the actual CF occurred. Our analyses of contact constraints are complete and general. The results demonstrate that despite uncertainties in object locations, if two or more PCs are formed between two objects, their relative location in many cases is fixed or can take up to only 4 solutions. In such cases, we can accurately identify a valid CF. From a different perspective, these results could also be useful in grasp planning. Our future work includes taking into account modeling uncertainties of objects and extending this method to three-dimensional objects.