In this paper, we propose a new algorithm, named JACC-G, for large scale optimization problems. The motivation is to improve our previous work on grouping and adaptive weighting based cooperative coevolution algorithm, DECC-G [1], which uses random grouping strategy to divide the objective vector into subcomponents, and solve each of them in a cyclical fashion. The adaptive weighting mechanism is used to adjust all the subcomponents together at the end of each cycle. In the new JACC-G algorithm: (1) A most recent and efficient Differential Evolution (DE) variant, JADE [2], is employed as the subcomponent optimizer to seek for a better performance; (2) The adaptive weighting is time-consuming and expected to work only in the first few cycles, so a detection module is added to prevent applying it arbitrarily; (3) JADE is also used to optimize the weight vector in adaptive weighting process instead of using a basic DE in previous DECC-G. The efficacy of the proposed JACC-G algorithm is evaluated on two sets of widely used benchmark functions up to 1000 dimensions.

This work focuses on the observation of environmental phenomena that occur as spatial distributions in two and three dimensions, using sensor-enabled mobile vehicle (ground,air or undersea). Algorithms to guide an adaptive exploration of a given region through systematic choice of sampling locations under the constraints imposed by vehicles are presented. Variation sensitive multiresolution sample distributions are achieved through an iterative variation sensitive estimation of the unknown process.

A new differential evolution (DE) algorithm, JADE, is proposed to improve optimization performance by implementing a new mutation strategy ldquoDE/current-to-pbestrdquo with optional external archive and updating control parameters in an adaptive manner. The DE/current-to-pbest is a generalization of the classic ldquoDE/current-to-best,rdquo while the optional archive operation utilizes historical data to provide information of progress direction. Both operations diversify the population and improve the convergence performance. The parameter adaptation automatically updates the control parameters to appropriate values and avoids a user's prior knowledge of the relationship between the parameter settings and the characteristics of optimization problems. It is thus helpful to improve the robustness of the algorithm. Simulation results show that JADE is better than, or at least comparable to, other classic or adaptive DE algorithms, the canonical particle swarm optimization, and other evolutionary algorithms from the literature in terms of convergence performance for a set of 20 benchmark problems. JADE with an external archive shows promising results for relatively high dimensional problems. In addition, it clearly shows that there is no fixed control parameter setting suitable for various problems or even at different optimization stages of a single problem.

Product development in modern enterprises usually involves collaboration among designers, suppliers, contract manufacturers to achieve efficiency and rapid response to changing markets. Product-development cost, lead time, and reliability are very critical elements in addition to functional features. However, it becomes increasingly challenging to obtain an optimal decision with respect to these multiple criteria as the number of involved entities increases in modern product developments. There is a clear need for planning tools to support effective decision making in this domain. The availability of efficient and accurate multiobjective optimization (MOO) algorithms becomes critical in such a decision support tool. This paper poses the product development as a multiobjective assignment problem in the context of printed circuit board assembly (PCBA) industry. We describe a new class of MOO algorithm based on the principles of differential evolution (DE). The multiobjective DE (MODE) algorithm is shown to approach Pareto-optimal solutions in a wide class of problems with better performance than the nondominated sorting genetic algorithm II from the literature, providing a practical tool for product-development decision support. A decision support system based on the object-oriented design methodology is described in this paper with the MODE as the core search engine. Experimental study of this decision support system is conducted using two real-world PCBA designs. We demonstrate the effectiveness of this proposed MODE algorithm and some use cases of such decision support system on facilitating decision makers' tradeoff analysis.

Differential evolution (DE) mutates solution vectors by the weighted difference of other vectors using arithmetic operations. As these operations cannot be directly extended to discrete combinatorial space, DE algorithms have been traditionally applied to optimization problems where the search space is continuous. In this paper, we use JADE, a self-adaptive DE algorithm, for winner determination in Combinatorial Auctions (CAs) where users place bids on combina tions of items. To adapt JADE to discrete optimization, we use a rank-based representation schema that produces only feasible solu tions and a regeneration operation that constricts the problem search space. It is shown that JADE compares favorably to a local stochastic search algorithm, Casanova, and a genetic algorithm based approach, SGA.

We propose a new self-adaptive differential evolution algorithm for multi-objective optimization problems. To address the challenges in multi-objective optimization, we introduce an archive to store recently explored inferior solutions whose difference with the current population is utilized as direction information about the optimum, and also consider a fairness measure in calculating crowding distances to prefer the solutions whose distances to nearest neighbors are large and close to be uniform. As a result, the obtained solutions can spread well over the computed non-dominated front and the front can be moved fast toward the Pareto-optimal front. In addition, the control parameters of the algorithm are adjusted in a self-adaptive manner, avoiding parameter tuning for prob lems of different characteristics. The proposed algorithm, named JADE2, achieves better or at least competitive results compared to NSGA-II and GDE3 for a set of twenty-two benchmark problems.

An analytical method is proposed to study the evo lutionary stochastic properties of the population in Differential Evolution (DE) for a spherical function model. Properties of mutation and selection are developed, based on which a Gaussian approximate model of DE is introduced to facilitate mathematical derivations. The evolutionary dynamics and the convergence behavior of DE are investigated based on the derived analytical formulae and their appropriateness is verified by experimental results. It is shown that the lower limit of mutation factor should be as high as 0.68 to avoid premature convergence if the initial population is isotropically normally distributed and infinitely far from the optimum (i.e., the function landscape becomes a by per-plane). The lower limit, however, may be decreased if the population becomes closer to the optimum and an accordingly smaller mutation factor is beneficial to speed up the convergence. This motivates future research to improve DE by dynamically adapting control parameters as evolution search proceeds.

A new differential evolution algorithm, JADE, is proposed to improve the rate and the reliability of convergence performance by implementing a new mutation strategy ‘DE/current-top-best’ and controlling the parameters in a self-adaptive manner. The °DE/current-top-best’ is a generaliza tion of ‘DE/current-to-best’. It diversifies the population but still inherits the fast convergence property. Self-adaptation is benefi cial for performance improvement. Also, it avoids the require ment of prior knowledge about parameter settings and thus works well without user interaction. Compared to other self-adaptive DE algorithms, JADE converges faster and reliably in at least 10 out of a set of 13 benchmark problems and shows competitive results in other cases as well. Simulations results also clearly show that there is no single parameter value suitable for various problems or even at different optimization stages of a single problem.

A new differential evolution algorithm, DE-AEC, is proposed based on adaptive evolution control utilizing the information provided by a surrogate model. The algorithm is useful for optimization problems with expensive function evaluations, because it can significantly reduce the number of true function evaluations. Specifically, DE-AEC generates multiple offspring for each parent and chooses the promising one based on the accuracy and the predicted function value of the current surrogate model. The model’s accuracy is also used as an indicator of potential false convergence and special measures are taken to improve the convergence reliability. Simulation results on a set of fifteen test functions show that, compared to an already improved DE algorithm, DE-AEC reduces the number of true function evaluations by 30% - 80% for fourteen functions in the achievement of either low-level (10-2) or high-level (10-8) accuracy.

Efficient adaptive strategies are required to facilitate the role of robotic vehicles as mobile platforms supporting sensing, monitoring, and tracking capabilities. Such strategies utilize a representation of sensor variable fields as a basis for the selection of sample points. In this paper a curvature based criterion for sample selection is presented. The curvature-sensitive sampling algorithm (CSS) utilizes the estimated second-derivative of an intermediate variable field to select sample points of interest for complex process models, such as used in oceanographic sampling with AUVs. For processes for which little or no prior knowledge base exists, an iterative curvature-based adaptive sampling algorithm (ICASA) is presented. The ICASA algorithm iteratively selects sets of sample locations based on non-parametric field representations. These algorithms are evaluated with respect to simulated data, experimental data, and data from oceanographic models. The performance is shown to be significantly better than the conventional uniform grid methodology. The selected iterative samples are used to create a path plan for a robotic vehicle sampling in the region of interest

This paper reports a mathematical modeling and convergence analysis of a continuous multi-objective differential evolution (C-MODE) algorithm that is proposed very recently. This C-MODE is studied in the context of global random search. The convergence of the population to the Pareto optimal solutions with probability one is developed. In order to facilitate the understanding of the C-MODE operators in a continuous space, a mathematical analysis of the operators is conducted based upon a Gaussian distributed initial population. A set of guidelines is derived for the parameter setting of the C-MODE based on the theoretical results from the mathematical analysis. A simulation analysis on a specific numerical example is conducted to validate the mathematical analytical results and parameter-setting guidelines. The performance comparison based on a suite of complex benchmark functions also demonstrates the merits of such parameter-setting guidelines

The revival of multi-objective optimization (MOO) is mostly due to the recent development of evolutionary multi-objective optimization that allows the generation of the whole Pareto optimal front. Several evolutionary algorithms have been developed for this purpose. This paper focuses on the recent development of differential evolution (DE) algorithms for the multi-objective optimization purposes. Although there are a few other papers on the extension of DE concept to the MOO domain, this paper is intended to provide an overall picture of one specific multi-objective differential evolution (MODE) algorithm. In the MODE, the DE concept for the continuous single-objective optimization is extended to MOO for both continuous and discrete problems (C-MODE and D-MODE, respectively). The MODE is modeled in the context of Markov framework and global random search. Convergence properties are developed for both C-MODE and D-MODE. In particular, a set of parameter-setting guidelines for the C-MODE is derived based on the mathematical analysis. An application of the D-MODE to the planning of design, supply, and manufacturing resources in product development is also reported in this paper

In recent years, multi-objective evolutionary algorithms (MOEA) have generated a large research interest. MOEA's attraction stems from their ability to find a set of Pareto solutions rather than any single, aggregated optimal solution for a multi-objective problem. As for single-objective evolutionary algorithms (SOEA), multi-objective evolutionary algorithms also require parameter tuning to achieve desirable performance. In the literature we can find fuzzy logic controllers (FLC's) applied to online parameter control for SOEA. In this paper, we propose to use a FLC to dynamically adjust the parameters of a particular multi-objective differential evolution (MODE) algorithm. The fuzzy logic controlled multi-objective differential evolution (FLC-MODE) is applied to a suite of benchmark functions. Its results are compared to those obtained by using MODE with constant parameter settings. We show that the FLC-MODE obtains better results in 80% of the testing examples. Given that the benchmarks were synthetic test functions, we designed the FLC using only our understanding of the working mechanism of the MODE, without incorporating any additional problem-specific knowledge. When addressing real-world applications, we expect the FLC to be an excellent way for representing and leveraging their associated heuristic knowledge

The integration of mobile robotic vehicles with distributed sensor networks requires the development of methods for vehicle navigation to achieve sample selection and effectively estimate distributed task variables. In this paper, singular value decomposition (SVD) of the parameter variance space is introduced as a basis for optimal sample selection. Simulation results are used to evaluate the algorithm performance, and significant reduction in field prediction variance are achieved over more conventional incremental rectangular measurement grids. An example of field estimation sensors on an autonomous underwater vehicle (AUV) is described.

Deploying large numbers of sensors has been receiving a lot of attention for detection of hazardous biological or chemical substances in public buildings, airports, shallow water harbors, etc. The sensor-carrying robots are in fact agents that facilitate the repositioning of network nodes in order to increase their coverage and accuracy. Wireless network communication is an essential technology in transmitting the sensed and telemetry information between robots, but it has traditionally been addressed separately from mobile robot navigation. In this work we propose to use a potential field framework to control the behavior of the mobile sensor nodes by combining classical robotic team concepts (obstacle avoidance, goal attainment, flight formation, environment mapping and coverage) with traditional sensor network concepts (node energy minimization, optimal data rate and congestion control, routing in ad-hoc networks). Simulation results are used to illustrate the proposed concepts, and an experimental mobile sensor fleet is built at the author's institution.

A theoretical foundation is presented for modeling and convergence analysis of a class of distributed coevolutionary algorithms applied to optimization problems in which the variables are partitioned among p nodes. An evolutionary algorithm at each of the p nodes performs a local evolutionary search based on its own set of primary variables, and the secondary variable set at each node is clamped during this phase. An infrequent intercommunication between the nodes updates the secondary variables at each node. The local search and intercommunication phases alternate, resulting in a cooperative search by the p nodes. First, we specify a theoretical basis for a class of centralized evolutionary algorithms in terms of construction and evolution of sampling distributions over the feasible space. Next, this foundation is extended to develop a model for a class of distributed coevolutionary algorithms. Convergence and convergence rate analyzes are pursued for basic classes of objective functions. Our theoretical investigation reveals that for certain unimodal and multimodal objectives, we can expect these algorithms to converge at a geometrical rate. The distributed coevolutionary algorithms are of most interest from the perspective of their performance advantage compared to centralized algorithms, when they execute in a network environment with significant local access and internode communication delays. The relative performance of these algorithms is therefore evaluated in a distributed environment with realistic parameters of network behavior.

A novel evolutionary planning framework (coevolutionary virtual design environment) particularly suited to distributed network-enabled design and manufacturing organizations is presented. The approach utilizes distributed evolutionary agents and mobile agents as principal object-oriented software entities that support a network-efficient evolutionary exploration of planning alternatives in which successive populations systematically select planning alternatives that reduce cost and increase throughput. This paper presents the architecture of the coevolutionary virtual design environment, and examines the network-based performance of the coevolutionary algorithms that execute in this environment. Simulation analysis examines the percentage convergence error and percentage computational advantage comparing the distributed network-based implementation to a centralized network-based implementation. The algorithms and architectures are evaluated in a realistic network setting and analyzed using models of network delays and processing times.

Evolutionary multiobjective optimization (EMOO) finds a set of Pareto solutions rather than any single aggregated optimal solution for a multiobjective problem. The purpose is to describe a newly developed evolutionary approach-Pareto-based multiobjective differential evolution (MODE). The concept of differential evolution, which is well-known in the continuous single-objective domain for its fast convergence and adaptive parameter setting, is extended to the multiobjective problem domain. A Pareto-based approach is proposed to implement the differential vectors. A set of benchmark test functions is used to validate this new approach. We compare the computational results with those obtained in the literature, specifically by strength Pareto evolutionary algorithm (SPEA). It is shown that this new approach tends to be more effective in finding the Pareto front in the sense of accuracy and approximate representation of the real Pareto front with comparable efficiency.

This paper presents analytical, simulation and experimental results from a study of compliant insertion tasks in microassembly. Gripper compliance is desirable to compensate for positional errors and to prevent the breakage of a gripper during assembly tasks. An analytical model is derived to study the motion and force profiles during compliant insertion. Thermal bimorph microgrippers with a compliant tip are designed and fabricated using a silicon DRIE process, and are mounted on a precision motion stage. A series of micropeg manipulation tasks such as pick up, rotation, and insertion are successfully performed. Finally, a comb structure is integrated in the gripper to calculate insertion force by measuring the deflection of a gripper, which is essential for automated microassembly.

Agility is important to modern enterprises. The effective coordination of large numbers of potential suppliers and manufacturer, demands a scientific methodology rather than just practical experience to make decisions on supply manufacturing planning problems. Particularly in cases where multiple decision objectives are important to process planning, empirical decisions are insufficient. This paper introduces formal methods to solve such multi-objective decision problems involved in general supply manufacturing planning, and specifically describes the extension of differential evolution methods to discrete problem domains. An enterprise planning problem with two objectives-cycle time and cost is used as a principal example. Such multi-objective optimization problems usually are very large and nonlinear. In this paper, the concept of differential evolution, which is well-known in single-objective continuous domain for its fast convergence and adaptive parameter setting, is extended to the discrete domain by introducing greedy probability, mutation probability, and crossover probability. Moreover, this concept is extended to discrete multi-objective optimization problem. The proposed discrete multi-objective differential evolution, or D-MODE algorithm is applied to obtain Pareto solutions of this general planning problem. A practical example in the electronics industry is used as an illustrative example to demonstrate the effectiveness of the proposed D-MODE.

Innovations in software, networks, and database systems are enabling widely distributed organizations to integrate activities, share information, collaborate on decisions, and execute transactions. However, successful enterprise-wide collaboration is increasingly dependent on the availability of generalized decision-support tools that can efficiently access and utilize distributed information. This paper presents a basic theory and network-based performance evaluation of a class of coevolutionary algorithms that supports efficient planning in a distributed environment. Performance of these coevolutionary algorithms is evaluated in a distributed information architecture (coevolutionary virtual design environment) that supports integrated design-supplier-manufacturing planning. In this architecture, distributed evolutionary agents and mobile agents are principal entities that support a network-efficient exploration of planning alternatives in which successive populations systematically select superior planning alternatives.

Describes a framework to support enterprise-level decision-making in network-based scalable systems. The fundamental principle of this approach asserts that decision tasks over a set of multiple, distributed, logically interrelated databases may be cast in the semantics of the underlying distributed database management system (DBMS). In this form, the augmented relational decision framework takes advantage of the principles of normalization and decomposition that are inherent to the relational DBMS model. The decision process is viewed as an instantiation of the relational schema, and the resulting representation of normal form hierarchies and data dependencies structures the process. Definition of a value function (or rule set) over the augmented relational decision space guides the search for desirable instances of the decision relations that constitute the suggested outcomes.

Highly redundant modular robots may undergo large shape changes which significantly affect the geometry and dynamics of the robot. In these motions, the shape change may induce a tipping or rolling behavior of the robot. The paper describes the dynamic modeling, locomotion planning, control and simulation of such rolling motions for the Tetrobot modular robots. The motion is described by the path profiles of controlled nodes, the tipping criteria and dynamic tipping motion and an impact-reaction model of contact with the ground. These phases of motion are described using Newton-Euler dynamic equations and the principle of conservation of angular momentum. In the paper, a two-phase planning and switching control sequence is introduced to achieve stable and reliable motion of a Tetrobot modular robot. Simulation results illustrate the tipping behavior of a tetrahedron, the dynamic contact and rolling of an icosahedral Tetrobot and dynamic control of the rolling Tetrobot. The resulting models are useful to analyze and control both intentional rolling as a new mode of mobility as well as the avoidance of unintentional tipping and rolling during task execution.

In an increasingly networked global marketplace, products and services are seldom created in isolation and are instead being realized through strategic and dynamic partnerships between suppliers, contract manufacturers, and customers. Superior design-supplier-manufacturing decisions are critical to the survival of enterprises that seek to compete in this environment. A novel evolutionary decision support framework (coevolutionary virtual design environment) particularly suited to distributed network-enabled organizations is introduced. In this framework an electronic interchange of design, supplier, and manufacturing information facilitates concurrent, network distributed decision-making based on evolutionary computation. The approach utilizes distributed evolutionary agents and mobile agents as principal entities that support a network-efficient exploration of planning alternatives in which successive populations systematically select planning alternatives that reduce cost and increase throughput.

This paper demonstrates a new approach to multidimensional path planning that is based on multiresolution path representation, where explicit configuration space computation is not required, and incorporates an evolutionary algorithm for solving the multimodal optimization problem, generating multiple alternative paths simultaneously. The multiresolution path representation reduces the expected search length for the path-planning problem and accordingly reduces the overall computational complexity. Resolution independent constraints due to obstacle proximity and path length are introduced into the evaluation function. The system can be applied for planning paths for mobile robots, assembly, and articulated manipulators. The resulting path-planning system has been evaluated on problems of two, three, four, and six degrees of freedom. The resulting paths are practical, consistent, and have acceptable execution times. The multipath algorithm is demonstrated on a number of 2D path-planning problems.

A theoretical foundation is presented for modeling and convergence analysis of distributed co-evolutionary algorithms applied to optimization problems in which the variables are partitioned among p nodes. An evolutionary algorithm at each of the p nodes performs a local evolutionary search based on its own set of primary variables, and the secondary variable set at each node is clamped during this phase. An infrequent intercommunication between the nodes updates the secondary variables at each node. The local search and intercommunication phases alternate, resulting in a cooperative search by the p nodes. First, we specify a theoretical basis for centralized evolutionary algorithms in terms of construction and evolution of sampling distributions over the feasible space. Next, this foundation is extended to develop a general model of distributed co-evolutionary algorithms. Convergence and convergence rate analyses are pursued for certain basic classes of objective functions. Also considered are relative computational delays of the centralized and distributed algorithms when they are implemented in a network environment.

Highly redundant modular robots may undergo large shape changes which significantly affect the geometry and dynamics of the robot. In these motions, the shape change may induce a tipping or rolling behavior of the robot itself. The paper describes the dynamic modeling, control, and simulation of such rolling motions for the Tetrobot modular robots. The motion is described by the path profiles of controlled nodes, the tipping criteria and dynamic tipping motion, and an impact-reaction model of contact with the ground. These phases of motion are described using Newton-Euler dynamic equations and the principle of conservation of angular momentum. Simulation results illustrate the tipping behavior of a tetrahedron, the dynamic contact and rolling of an icosahedral Tetrobot, and dynamic control of the rolling Tetrobot. The resulting models are useful to analyze and control both intentional rolling as a new mode of mobility as well as the avoidance of unintentional tipping and rolling during task execution.

In a recent study of modular robots (2000), the authors demonstrated the feasibility of dynamic rolling motions as a novel means of locomotion. In such a system the capability of large shape change is used to induce tipping and rolling behaviors of the robot itself. However, the dynamics of the tipping motion and the contact forces that occur on impact with the ground are complex. In this paper, a two-phase planning and switching control sequence is introduced to achieve stable and reliable motion of an icosahedral Tetrobot modular robot. Simulation of the resulting rolling motions suggests that speed and direction of the rolling can be controlled, and both sustained uphill and downhill rolling motions are feasible.

This paper proposes a distributed control scheme for a highly redundant parallel Tetrobot mechanism. The architecture of the proposed distributed control is composed of processors dedicated to each module and a network used to communicate the information between the modules. Each processor computes the kinematics, dynamics and control input for the dedicated module using the subsystem dynamic model and the information communicated only from adjacent modules. The simulation results of set-point and tracking control are provided to demonstrate the feasibility of the proposed scheme and compared to centralized control. The results show that the controlled node reaches the desired position without a steady state error even though the convergence rate is slower than for the centralized scheme. To improve the problem caused by a local optimization technique, an iteration scheme of local optimization was also applied to obtain a global solution to generate the paths of uncontrolled nodes.

A distributed computation algorithm based on the virtual force method supports the computation of dynamic redundancy resolution for modular reconfigurable robotic systems. Such systems have many redundant degrees of freedom in order to meet the combined demands of strength, rigidity, workspace kinematics, reconfigurability, and fault tolerance. An efficient distributed computational scheme computes the kinematics, dynamics, and redundancy resolution for real-time application to the control of these systems. A potential function which depends only on the local information of adjacent nodes of the structure is introduced and applied to the Tetrobot modular reconfigurable system. Simulation results are provided to demonstrate the feasibility of the proposed distributed algorithms, and these results are compared to the centralized Jacobian method which requires global information.

An assembly is defined by a configuration of parts of known geometries subject to tolerances in the pose, dimensions, and mating relations among part features. Using a tolerance model based on matrix transforms and Gaussian models of geometric variations, the pose and dimensional tolerance models are considered as a priori models of the assembly with nominal and variational components for both position and orientation. The mating relations are regarded as linear relational constraints, also with nominal and variational components. With this formulation, estimation of the configuration of parts may be posed as a maximum likelihood problem and solved by a Kalman filter algorithm. The resulting maximum likelihood configuration of the assembly may be used to evaluate the required deviation from nominal and the assemblability as defined by the maximum likelihood clearance from constraints. In addition, application of the technique to intermediate subassemblies may be used to evaluate assemblability of specific steps and discriminate among alternative assembly sequence plans.

Fusion of information from multiple sensors is required for planning and control of robotic systems in complex environments. The minimal representation approach is based on an information measure as a universal yardstick for fusion and provides a framework for integrating information from a variety of sources. In this paper, we describe the principles of minimal representation multisensor fusion and evaluate a differential evolution approach to the search for solutions. Experiments in robot manipulation using both tactile and visual sensing demonstrate that this algorithm is effective in finding useful and practical solutions to this problem for real systems. Comparison of this differential evolution algorithm with more traditional genetic algorithms shows distinct advantages in both accuracy and efficiency.

A multiresolution representation of robot paths is introduced as a basis for path planning where explicit configuration-space computation is not feasible. This multiresolution representation is computationally efficient since the path representation depends on the complexity of the problem space-therefore, a simple path will be found quickly if one exists. An evolutionary algorithm uses a variable-length string to encode the path, and this length is systematically varied as the evolutionary search proceeds. Resolution independent constraints due to obstacle proximity, and path length are introduced into the evolutionary evaluation function. The resulting algorithm has been evaluated on problems of 2, 3, 4, and 6 degrees of freedom, including mobile articulated robots and six degree-of-freedom assembly trajectory problems. The resulting paths are practical and consistent with acceptable execution times.

The virtual design environment is an information architecture to support design-manufacturing-supplier planning decisions in a distributed, heterogeneous environment. The approach utilizes evolutionary intelligent agents as program entities which generate and execute queries among distributed computing applications and databases. The evolutionary agents support a global evolutionary optimization process in which successive populations systematically select planning alternatives which reduce cost and increase throughput. A prototype of the virtual design environment has been implemented using CORBA as a principal distributed systems programming tool. The prototype has been used to examine design-manufacturing-supplier decisions for a real commercial electronic circuit board product (Pitney Bowes Inc.) and to explore plans in controlled experiments with alternative manufacturing facilities.

Highly redundant parallel manipulators are gaining increased attention due to their capability to meet demands of strength, rigidity, kinematic structure, dexterity, reconfigurability, and fault tolerance. Most previous research has considered the kinematic resolution of highly redundant parallel manipulators, and the dynamic resolution of redundancy has not yet been studied for these systems. This paper presents the dynamic simulation of a highly redundant parallel manipulator called Tetrobot, a class of modular reconfigurable robotic systems. The modular concept is applied to formulate the kinematic and dynamic equations of motion. In this modular approach, kinematic and dynamic solutions are obtained for Tetrobot mechanisms by propagation through the structures. Results show that the pseudoinverse solution which minimizes the norm of acceleration may introduce stability problems, and the null space vector which avoids joint limits is required to ensure stability.

The paper describes a framework for task sequence planning for a generalized robotic work cell. The AND/OR net provides a compact, distributed, domain-specific representation of geometric configurations of parts and devices in the work cell. The approach maintains a correspondence from geometric state information to task and motion plans and on-line discrete-event control that is not available in traditional action-based planners. The feasibility criteria for each AND/OR net transition guide the geometric reasoning required in the planning of feasible sequences. The resulting search space for plans is often much smaller (due to explicit representation of geometric constraints) than the state space of an action-based task planner. For purposes of analysis, the AND/OR net is mapped into a Petri net and the resulting Petri net is shown to be bounded and have guaranteed properties of liveness, safeness, and reversibility. In this form, the AND/OR net may be viewed as a Petri net synthesis tool in which the resulting Petri net representation may be used for on-line scheduling and control of the system.

Multisensor fusion has emerged as a central problem in the development of robotic systems where interaction with the environment is critical to the achievement of a given task. The Anthrobot five-fingered hand grasps an object, and senses the contact points with the surface of the object using tactile sensors. The tactile sensors extract touch position and approximate surface normal in the kinematic reference frame of the hand. In addition, a CCD camera views the position of the same object and extracts vertex/edge features of the object image. Both the tactile features and the visual features are related to the position and orientation of the object, and in practice we wish to combine these two sources of information to improve robot's ability to accurately manipulate the object. The fusion of the tactile and image feature data is used to derive an improved estimate of the object pose which guides the manipulation.

A novel genetic algorithm (GA) using minimal representation size cluster (MRSC) analysis is designed and implemented for solving multimodal function optimization problems. The problem of multimodal function optimization is framed within a hypothesize-and-test paradigm using minimal representation size (minimal complexity) for species formation and a GA. A multiple-population GA is developed to identify different species. The number of populations, thus the number of different species, is determined by the minimal representation size criterion. Therefore, the proposed algorithm reveals the unknown structure of the multimodal function when a priori knowledge about the function is unknown. The effectiveness of the algorithm is demonstrated on a number of multimodal test functions. The proposed scheme results in a highly parallel algorithm for finding multiple local minima. In this paper, a path-planning algorithm is also developed based on the MRSC_GA algorithm. The algorithm utilizes MRSC_GA for planning paths for mobile robots, piano-mover problems, and N-link manipulators. The MRSC_GA is used for generating multipaths to provide alternative solutions to the path-planning problem. The generation of alternative solutions is especially important for planning paths in dynamic environments. A novel iterative multiresolution path representation is used as a basis for the GA coding. The effectiveness of the algorithm is demonstrated on a number of two-dimensional path-planning problems.

This paper presents an application of feature-based visual servoing to achieve accurate and robust 3D filament alignment. Two orthogonal cameras are used to localize the five degrees of freedom of an axi-symmetric filament. An algorithm for precisely estimating the center and orientation features of a filament in a camera view is described. The use of feature-based servoing overcomes the difficulty of 3D camera calibration in a factory environment. These features drive a PID control loop for each view. The two views are coupled in one degree of freedom, and the multiple-view controller switches between two single-view controllers to achieve 3D servoing. The overall accuracy achieved is in thousandths of an inch. Experimental results on the performance of the control algorithm are discussed. Models explaining the system behavior are presented. The use of visual servoing in this application far exceeds the positioning accuracy and the repeatability of human operators.

TETROBOT is a modular system for the design, implementation, and control of a class of highly redundant parallel robotic mechanisms. This paper describes new experimental results based on evaluation of prototype configurations with up to 18 nodes, 48 links and 15 actuators. TETROBOT is an actuated robotic structure which may be reassembled into many different configurations while still being controlled by the same hardware and software architecture. Implementations of a double octahedral platform, a tetrahedral arm and a six-legged walker, constructed from the same set of parts, are described. The TETROBOT system addresses the needs of application domains, such as space, undersea, mining, and construction, where adaptation to unstructured and changing environments and custom design for rapid implementation are required.

Parallel robots can be built by linking together unit cells in configurations which retain the static determinacy of the overall structure. In the Tetrobot system, the kinematics of these concatenated structures can be solved by propagation of solutions through connected graphs of linked modules. In this paper, we examine the synthesis of unit cells which could be used in creating these structures and retain the ability to compute the kinematics for control of the actuated system. Admissible unit cells are shown to form families in two- and three-dimensions, and a set of synthesis rules is described which generates the members of these families recursively for each generations. The resulting set of modules comprises a broad set of useful cells which can be used to design parallel robots and guarantee the computability of their kinematics on a cell-by-cell basis.

A modular system for the design, implementation, and control of a class of highly redundant parallel robotic mechanisms is described. The Tetrobot system features a novel concentric multilink spherical (CMS) joint which allows an arbitrary number of links to share a common center of rotation. The CMS joint facilitates the construction of a wide variety of variable geometry truss mechanisms using an integrated control and computational framework. A distributed control algorithm is based on an iterative virtual force based solution which propagates the goal positions of target nodes to determine systematic adjustments of actuators. Capabilities of the Tetrobot system have been demonstrated by the construction of several configurations of up to 18 nodes, 48 links, and 15 actuators. Implementations of a double Stewart platform and a six-legged walker, constructed from the same set of parts, are described in this paper.

Traditional data interpretation methods do not prescribe a well-defined methodology for sensors which are difficult to characterize by well-defined statistical uncertainty models. We describe a minimal representation approach that characterizes the "information" in observed data by its coding complexity; this "information" is well-defined for sensors with known and unknown statistics. For statistical data, this information-based approach subsumes classical approaches, while for sensors with unknown statistics it provides a new paradigm for uncertainty modeling based on accuracy and precision (AP), and allows fusion with statistical data. An abstract multisensor data interpretation problem is described and formulated using the minimal representation approach. Monte-Carlo simulations comparing the use of an AP-coding uncertainty model with a Gaussian uncertainty model for a two-dimensional pose estimation problem are presented.

This paper describes a new representation for sensing and control uncertainties in sensor-based robot control, and presents motion planning algorithms that use this representation. The planning algorithms employ a robot's sensing capabilities as needed to accomplish a task, by activating sensors at points or intervals during motion. A sensor is represented by three quantities: a domain, which is the set of robot configurations at which a valid measurement can be taken; an absolute sensing uncertainty held, which describes the sensor's absolute (global) accuracy; and an incremental motion uncertainty, which describes the sensor's relative (pertaining to displacements) accuracy. Control uncertainty represents the ability of a controller to drive the measured error near zero. These descriptions of sensing and control capability determine the evolution of uncertainty in a sensor-based motion plan. Two complementary algorithms for motion planning with the new representation are presented. One is a backprojection algorithm which searches globally (in configuration space and the available sensors) for ways to achieve a particular subgoal. The other searches locally (in path space) to satisfy all the constraints in a planning problem. Examples of uncertainty evaluation and motion planning in two degrees of freedom are presented.

This paper discusses the problem of representation and planning of operations sequences in a robotic system using fuzzy Petri nets. In the fuzzy Petri net representation, objects whose internal states are altered during a process are termed soft objects, and the process steps where alterations may occur are labeled key transitions. A correct sequence is defined as a sequence which is feasible, complete, and satisfies precedence relations. In this formulation, the internal state of an object is represented by a global fuzzy variable attached to the token related to the degree of completion of the process. All correct operations sequences must satisfy process sequence constraints imposed by transition reasoning rules. The correct precedence relationships and the characteristics of completeness for operations in all feasible sequences are guaranteed by the prime number marking algorithm which marks the fuzzy Petri net. The use of transition reasoning rules in this application simplifies the representation and search problems for task planning where correct sequences do not depend on exact knowledge of internal states, but only their precedence relations.>

A new spherical joint mechanism which is well suited to parallel robotics is presented. The concentric multilink spherical (CMS) joint allows two or more struts to be connected together such that they rotate about a single point. This joint can replace the traditional ball or universal (Hooke) joints in Stewart platforms, variable geometry truss manipulators, and other parallel robots. The TETRA2 robot consists of five nodes and six actuated struts. It provides a range of motion of 1m/spl times/0.5m/spl times/0.5m and has lifted a payload of 10 kg at full lateral extension. Simulation of a 48 struct walking robot illustrates the use of CMS joints to design more complex structures. The simulation also demonstrates new algorithms for parallel robot control.>

A general approach to model-based multisensor data fusion using a minimal representation size criterion is described. Each sensor is modeled by a general constraint equation which defines a data constraint manifold (DCM), and observed sensor data populate the measurement space according to these constraints. The choice of multisensor interpretations is based on a minimal representation size criterion which evaluates the complexity through correspondence and encoded errors weighted by relative sensor accuracy and precision. This general framework automatically selects subsets of data features called constraining data feature sets (CDFS) and chooses the CDFS corresponding to a minimal representation interpretation of the observed data. The resulting procedure fuses heterogeneous sensor readings into a single estimation method. The method is illustrated for a visual and tactile data fusion example. The approach generalizes to problems with non-geometric models, and can be used for multisensor system identification in other domains such as process control.>

Previous work in representing transformational uncertainty used a linearized perturbed-transform method which assumes small angle errors. This paper presents an alternative representation using random unit quaternions that makes no strict small angle error assumption. The approach uses a novel family of probability density functions derived by placing a unit-length constraint upon some or all of the degrees of freedom of a Gaussian in Euclidean space. An important property of this representation is that it does not directly interrelate angles with spatial components. This paper discusses the properties of radially constrained Gaussians, presents specific cases of uncertain rotations, directions, orientations, 2D transformations, and 3D transformations, and then indicates their applications to robotics.>

This paper describes a hybrid genetic algorithm (HGA) for model-based matching of observed scenes that are noisy, where only a small fraction of the scene features are expected to correspond to the model features. The problem of finding the match is framed within a hypothesize-and-test paradigm and the HGA, with a representation size minimum description length evaluation function, is formulated as the method to search for the match. Unlike most genetic algorithms, the HGA introduced is based on an integer representation with a position based recombination operator. An assignment operator, also used as a reproduction operator, introduces domain-specific constraints and defines the hybrid nature of the algorithm. Results for models and scenes derived from images of occluded and cluttered environments are described. The results show the HGA to be an efficient search technique and the related matching technique to be robust in a variety of cases.>

The authors address the problem of representing and automatically invoking error recovery sequences in response to sensed error during execution. The approach is based on the use of a fuzzy Petri net model in which sensory verification operations determine fuzzy values of tokens in the net. The outcome of a sensory verification operation changes the fuzzy values of tokens and leads to an altered firing sequence and resulting error recovery. An algorithm is described for adding sensory verification transitions and associated fuzzy transition rules which implement error recovery through retry or alternative sequence mechanisms.>

The feasible path problem is solved for planning a collision-free path to translate an arbitrary polyhedral robot from an initial position to some goal position in a polyhedral environment. The shortest path problem entails finding the shortest feasible path. The authors present two versions of the window corner (WC) algorithm, which is a novel solution to the problems for the case of single and multistep translational paths for two dimensions, and then summarize the extension to the three-dimensional WC algorithm, for feasible paths. The concept of window corners in the polyhedral cone representation (PCR) is introduced, which reduces the search space. The PCR cones store constraints between boundary elements. The PCO representation has O(m) vertices compared to O(m/sup 2/) in a C-space representation. The WC algorithm was tested and an example from assembly path planning is presented.>

In this paper, we present a complete and ex- act algorithm for planning a geometrically feasible path for a polyhedral subassembly (robot) translating amongst poly- hedral obstacles. Our algorithm can be used to determine whether a pair of non-convex subassemblies can be separated by a sequence of fine-motions and, possibly, contact-motions, when the amount of free space tends to be severly limited. We present the three-dimensional Window Corner algorithm to plan feasible paths. The algorithm solves the FeosiblePath problem, in worst-case time O(m5) where m is the product of the number of vertices describing the robot and obstacles respectively. A Feasiblepath solution hierarchy, for assembly sequence planning, is described for incremental, straight-line and multi-step paths. The Polyhedral Cone Representation (PCR) is introduced to efficiently represent the geometrical constraints on trans- lation and as a basis for fast collision avoidance checks. We introduce the concept of Window Corners in the PCR and this results in a finite search space. The Polyhedral Cone Obstacle Representation (PCUR), which is a constructive representation of all boundary contact configurations, trans- forms the problem into that of a point moving amongst a col- lection, O(m), of convex obstacles. In comparison, the worst- case space complexity of the C-space boundary is O(m3). Certain contact-constrained, feasible motions, which lie on surfaces without interior points can be inaccessible in a typ id C-space representation.

An approach to geometric reasoning about the feasibility of translation motion of parts of assembly operations is demonstrated. The feasibility problem has been broken down hierarchically such that necessary conditions for less complex motions may be evaluated early, and the problem of planning arbitrarily complex part trajectories is not treated unless required for the specific design implementation. The determination of local motion feasibility using the polyhedral convex cone representation of contact constraints has been extended to the analysis of global transition feasibility using a polyhedral cone algebra. This representation has further been used for the formulation of the multistage translation problem where a simulated annealing optimization strategy and a reachability wave algorithm was used to efficiently search for feasible solutions.>

Five types of representations for assembly sequences are reviewed: the directed graph of feasible assembly sequences; the AND/OR graph of feasible assembly sequences; the set of establishment conditions, and two types of precedence relationships namely those between the establishment of one connection between parts and the establishment of another connection, and those between the establishment of one connection and states of the assembly process. The mappings of one representation into the others are established. The correctness and completeness of these representations are established. The results presented are needed in the proof of correctness and completeness of algorithms for the generation of mechanical assembly sequences.>

An algorithm for the generation of all mechanical assembly sequences for a given product is presented. It uses a relational model of assemblies. In addition to the geometry of the assembly, this model includes a representation of the attachments that bind parts together. The problem of generating the assembly sequences is transformed into the problem of generating disassembly sequences in which the disassembly tasks are the inverse of feasible assembly tasks. The problem of disassembling one assembly is decomposed into distinct disassembly subproblems. The algorithm returns the AND/OR graph representation of assembly sequences. The correctness of the algorithm is based on the assumption that it is always possible to decide correctly whether two subassemblies can be joined, based on geometrical and physical criteria. An approach to computing this decision is presented. An experimental implementation for the class of products made up of polyhedral and cylindrical parts with planar or cylindrical contacts among themselves is described. Bounds for the amount of computation involved are presented.>

The authors introduce two criteria for the evaluation and selection of assembly plans. The first criterion is to maximize the number of different sequences in which the assembly tasks can be executed. The second criterion is to minimize the total assembly time through simultaneous execution of assembly tasks. An algorithm that performs a heuristic search for the best assembly plan over the AND/OR graph representation of assembly plans is discussed. Admissible heuristics for each of the two criteria introduced are presented. Some implementation issues that affect the computational efficiency are addressed.>

Two criteria are introduced for the evaluation and selection of assembly plans. The first criterion is to maximize the number of different sequences encompassed by the assembly plan. The second criterion is to maximize the amount of parallelism (i.e., simultaneity) that is possible in the execution of the assembly tasks. While the metrics corresponding to the criteria used in previous work can be expressed as a sum of terms, each being a function of a task or a state, the metrics corresponding to the criteria introduced are more complex functions of the whole assembly plan. An algorithm that performs a heuristic search for the best assembly plan over an AND/OR graph representation of assembly plans is presented. Admissible heuristics for each of the two criteria are presented.>

Strategies used and parameter selection problems encountered in developing robot programs are addressed by describing an approach to self-tuning of robot program parameters. In this approach, the robot program incorporates control primitives with adjustable parameters and an associated cost function. A hybrid gradient-based and direct-search algorithm uses experimentally measured performance data to adjust the parameters to seek optimal performance and track system variations. Alternative control strategies which have first been optimized with the same cost function are then assessed in terms of their optimized behavior. It is demonstrated that the optimal control strategy for a particular task is a function not only of task geometry, but also of the desired performance.>

The authors describe and analyze two algorithms for maintaining cache coherence in multiprocessor systems with parallel communication channels and many processors. A distributed link-list relates all cache frames representing the same main memory block. Messages traverse the list to maintain list integrity, exclusive ownership, and consistent values. Memory access semantics are equivalent to a shared memory system without caches. Reference latency, efficiency of memory use, and hardware complexity are moderate and well-bounded. A brief comparison with the Scalable Coherent Interface illustrates some of the design tradeoffs associated with distributed directory algorithms.>

A compact representation of all possible assembly plans of a given product using AND/OR graphs is presented. Such a representation forms the basis for efficient planning algorithms that make possible an increase in assembly system flexibility by allowing an intelligent robot to pick a course of action according to instantaneous conditions. The AND/OR graph is equivalent to a state transition graph but requires fewer nodes and simplifies the search for feasible plans. Three applications are discussed: the preselection of the best assembly plan, the recovery from execution errors, and the opportunistic scheduling of tasks. A hypothetical error situation in the assembly of the four-part assembly is discussed to show how a bottom-up search of the AND/OR graph leads to an efficient recovery. The scheduling efficiency using this representation is compared with fixed sequence and precedence graph representations.>

The structured highlight inspection method uses an array of point sources to illuminate a specular object surface. The point sources are scanned, and highlights on the object surface resulting from each source are used to derive local surface orientation information. The extended Gaussian image (EGI) is obtained by placing at each point on a Gaussian sphere a mass proportional to the area of elements on the object surface that have a specific orientation. The EGI summarizes shape properties of the object surface and can be efficiently calculated from structured highlight data without surface reconstruction. Features of the estimated EGI including areas, moments, principal axes, homogeneity measures, and polygonality can be used as the basis for classification and inspection. The structured highlight inspection system (SHINY) has been implemented using a hemisphere of 127 point sources. The SHINY system uses a binary coding scheme to make the scanning of point sources efficient. Experiments have used the SHINY system and EGI features for the inspection and classification of surface-mounted-solder joints.>

The authors present an algorithm for the generation of mechanical assembly sequences and a proof of its correctness and completeness. The algorithm uses a relational model which describes the geometry of the assembly and the attachments that bind one part to another. The problem of generating the assembly sequences is transformed into the problem of generating disassembly sequences, in which the disassembly tasks are the reverse of feasible assembly tasks. This transformation leads to a decomposition approach in which the problem of disassembling one assembly is decomposed into distinct subproblems, each involving the disassembly of one subassembly. It is assumed that at each assembly task exactly two subassemblies are mated and that all contacts between the parts in the two subassemblies are established. The algorithm yields an AND/OR graph representation of assembly sequences. The correctness of the algorithm is based on the assumption that it is always possible to decide correctly whether two subassemblies can be joined based on geometrical and physical criteria. An approach to compute this decision is given, and bounds for the amount of computation required are presented.>

The authors describe a novel approach to image matching which utilizes the minimal representation criterion as a means to obtain robust matching performance, even when image data are extremely noisy. They describe the application of this approach to the problem of matching noisy gray-level images to attributed models. Using the minimum representation criterion, the match between gray-level image features and an attributed graph model incorporates a representation size measure for the modeled points, the data residuals, and the unmodeled points. This structural representation identifies correspondence between a subset of data points and a subset of model points in a manner which minimizes the complexity of the resulting model. The proposed minimum representation matching algorithm is polynomial in complexity, and exhibits robust matching performance on examples where less than 30% of the features are reliable. The minimum representation principle is extensible to related problems using three-dimensional models and multisensor data matching.>

Energetic formulations of Newton's laws are valuable for mechanics problems involving multiple constraints. The following energic principle for quasistatic systems is discussed: a quasistatic system chooses that motion, from among all motions satisfying the constraints, which minimizes the instantaneous power. This minimum power principle states that a system chooses at every instant the lowest energy, or 'easiest', motion in conformity with the constraints. It is shown that the principle is in general false. For example, if viscous forces act, the motion predicted by the minimum power principle will be incorrect. The authors proved that the principle is correct if there are no forces with velocity-dependent magnitude. This allows its application to many systems with Coulomb friction.>

A simple modification is shown in the set of goal nodes of the AND/OR graph that allows its use in planning repairs such as the replacement of a part or a subassembly. An algorithm for the generation of all feasible sequences for disassembly and reassembly of parts that will achieve a repair is shown. This approach has been demonstrated for the example of the repair of space-based satellite equipment.>

Quasistatic mechanical systems, in which mass or acceleration is sufficiently small for the inertial term ma in F=ma to be negligible compared to dissipative forces, are discussed. It is pointed out that many instances of robotic manipulation can be well approximated as quasistatic systems, with the dissipative force being dry friction. Energetic formulations of Newton's laws have often been found useful in the solution of mechanics problems involving multiple constraints. An intuitive minimum power principle is outlined which states that a system chooses at every instant the lowest-energy, or 'easiest', motion in conformity with the constraints. Surprisingly, the principle is in general false; but it is proved that the principle is correct in the useful special case that Coulomb friction is the only dissipative or velocity-dependent force acting in the system.>

The authors apply Monte Carlo simulation techniques to gain further insight into the relationship between manufacturing errors and the performance of a robot using either the design model or arm signature model for control. In conventional design-model robot control, manufacturing errors contribute most to robot positioning errors. The authors relate the statistical parameters which characterize the manufacturing error probability distribution functions. In arm signature-based robot control (S-model), the correct arm signature model eliminates kinematic errors due to manufacturing. In this case, robot performance is limited by sensor errors which contribute to inaccuracy of the identified arm signature model. The relationship between the statistical parameters which characterize a robot's positioning accuracy to the statistical parameters which characterize the sensor performance is presented. The authors analyze and quantify the requirements of an arm signature identification system in terms of the underlying sensor performance.>

An approach to illumination and imaging of specular surfaces that yields three-dimensional shape information is described. The structured highlight approach uses a scanned array of point sources and images of the resulting reflected highlights to compute local surface height and orientation. A prototype structured highlight inspection system, called SHINY, has been implemented. SHINY demonstrates the determination of surface shape for several test objects including solder joints. The current SHINY system makes the distant-source assumption and requires only one camera. A stereo structured highlight system using two cameras is proposed to determine surface-element orientation for objects in a much larger field of view. Analysis and description of the algorithms are included. The proposed structured highlight techniques are promising for many industrial tasks.>

The authors consider the automated planning of manipulation strategies for workpieces able to slide on their work surface. The aim is to generate open-loop (i.e. sensorless) strategies which succeed in aligning or grasping a workpiece, in the face of two kinds of uncertainty: (1) the initial configuration of the workpiece may have some bounded error, and (2) the details of the contact between workpiece and work surface may be unknown, precluding deterministic solution for the motion of the workpiece even were its initial configuration exactly known. Configuration maps are defined which map all configurations of a workpiece before elementary manipulative operation to all possible outcomes. Using elementary manipulative operations (represented by configuration maps) as primitives, appropriate search techniques are applied to find operations sequences which are guaranteed to succeed despite uncertainty. As a concrete example, the authors demonstrate the automated design of a class of passive parts-feeder consisting of multiple sequential fences across a conveyor belt.>

It occurs frequently in robotic applications that a robot manipulates a workpiece which is free to slide on a work surface. Because the pressure distribution supporting the workpiece on the work surface cannot in general be known, the motion of the workpiece cannot be calculated uniquely. The authors find the locus of centers of rotation of a workpiece for all possible pressure distributions. The results allow a quantitative understanding of open-loop robot motions which guarantee the alignment of a workpiece. Several sample problems are solved using the results, including the distance that a flat fence, or robot finger, must push a polygonal workpiece to assure that a facet of the workpiece comes into alignment with the fence.>

A configuration map is defined and computed, mapping all configurations of a part before an elementary manipulative operation to all possible outcomes. Configuration maps provide a basis for planning the operation sequences which occur in parts-feeder designs or in more general sensorless manipulation strategies for robots. Sequences of elementary operations are represented as matrix-products of configuration maps for the individual operations. Efficient methods for searching the space of all operations sequences are described. As an example we consider a class of parts feeders based on a conveyor belt. Parts arrive on the belt in random initial orientations. By interacting with a series of stationary fences angled across the belt, the parts are aligned into a unique final orientation independent of their initial orientation. The planning problem is to create (given the shape of a part) a sequence of fences which will align that part. We demonstrate the automated design of such parts feeders.

The S-Model identification algorithm described in [6,7] is a technique which can be used to accurately identify the actual kinematic parameters of serial link robotic manipulators. The actual kinematic parameters of a manipulator differ from the design parameters due to the presence of random manufacturing errors. The set of identified kinematic parameters is called the arm signature. Accurate arm signatures are needed to control and improve the end-effector positioning accuracy of robotic manipulators for a variety of important tasks. This paper describes the hardware and software implementation of a prototype arm signature identification system. This system uses an external ultrasonic range sensor to measure the Cartesian position of target points placed on the links of the robot. Algorithms to compensate the primary range measurements for spatial variations in air temperature and humidity are also incorporated. The relative Cartesian positioning accuracy of the sensor system is ± .02cm. The general characteristics of our sensor design and the overall system design which exploits averaging over many sensor readings offer numerous advantages for arm signature identification. The prototype system has been applied in [6] to improve the kinematic performance of seven Puma 560 robots. For these robots relative positioning accuracy was improved by a factor of 10 on straight'line positioning tasks. Analysis and simulation of systematic errors confirms that the resolution of our sensor system should provide kinematic performance close to the limitations of the joint encoders. Our experimental studies show that sensor bias ultimately limits kinematic performance using this arm signature system. Experience with this prototype system has demonstrated that the S-Model identification algorithm is a practical and viable method for improving the kinematic performance of robotic manipulators.

One approach to pattern classification is to match a structural description of a pattern to models which describe the structural properties of pattern classes. The central problem in structural pattern matching is to determine the correspondence between the symbols which comprise a model and symbols which describe a pattern. The difficulty of determining this correspondence depends critically on the representation that is used to describe patterns. This correspondence presents a probabilistic representation for structural models of pattern classes. Both pattern descriptions and models for pattern classes are based on symbols which represent grayscale information at multiple resolutions. A pattern description is given by a tree of symbols with attribute values. Structural models are represented by a tree of symbols with probabilistic attributes. The position and scale (resolution) of the symbols, as well as other ``features,'' are represented by these attributes. An algorithm is presented for determining the correspondence between symbols in a description of a pattern and symbols in a model of a pattern class. This algorithm uses the connectivity between symbols at different scales to constrain the search for correspondence. An interactive training program for learning models of pattern classes is described, and some conclusions from the work are presented.

Sensor-based robot control may be viewed as a hierarchical structure with multiple observers. Actuator, feature-based, and recognition observers provide the basis for multilevel feedback control at the actuator, sensor, and world coordinate frame levels, respectively. The analysis and design of feature-based control strategies to achieve consistent dynamic performance is addressed. For vision sensors, such an image-based visual servo control is shown to provide stable and consistent dynamic control within local regimes of the recognition observer. Simulation studies of two- and three-degree-of-freedom systems show the application of an adaptive control algorithm to overcome unknown and nonlinear relations in the feature to world space mapping.

Planning manipulation of an object free to slide on a surface is an important problem in many robotic applications. Physical analysis of the object's motion is made difficult by the absence of information about the distribution of support of the object on the surface, and of the resulting frictional forces. Here we describe a new approach to the analysis of sliding motion. We present results for the locus of centers of rotation for all possibie distributions of support. In one application to robotic manipulation, bounds on the distance an object must be pushed to come into alignment with a robot finger or a fence are determined.

The positioning accuracy of commercially-available industrial robotic manipulators depends upon a kinematic model which describes the robot geometry in a parametric form. Manufacturing errors in machining and assembly of manipulators lead to discrepancies between the design parameters and the physical structure. Improving the kinematic performance thus requires identification of the actual kinematic parameters of each individual robot. This identification of the individual kinematic parameters is called the arm signature which is then incorporated into the manipulator's controller to improve positional accuracy. In this paper, an approach, based on a new parametric model of the kinematics, is introduced for arm signature identification. The S-Model utilizes 6.n parameters to describe the robot geometry and offers advantages for identification by decomposing the parameters into individually identified subsets. The S-Model parameters are then mapped into the equivalent Denavit-Hartenberg parameters for implementation into the controller. The S-Model arm signature identification algorithm can be implemented with relatively simple sensors and improves accuracy through statistical averaging. This algorithm has been implemented with an external ultrasonic range sensor to measure robot end-effector positions. Experimental results of arm signature identification of seven Unimation/Westinghouse Puma 560 robots demonstrated an average reduction in positioning error by a factor of 5-10 for a spectrum of representative test tasks.

In [1], the converging squares algorithm was introduced as a method designed to effectively and efficiently locate peaks in data of two dimensions or higher. In this correspondence, the performance of the algorithm on a signal in noise is examined, and some extensions of the algorithm-beyond peak-picking-are introduced. The minimum-area enclosing square is one extension, which locates an image region in a uniform background, and finds the smallest square which entirely encloses it. The maximum-difference enclosing square is another extension by which a global feature of the image is found which separates it into a foreground square region and background region, based on the maximum statistical difference between the two. Some applications of these extensions are shown, including object location, tracking of a moving object, and adaptive binarization.

An algorithm that finds the externally visible vertices of a polygon is described. This algorithm generates a new geometric construction, termed the convex ropes of each visible vertex. The convex ropes give the range of angles from which each vertex is visible, and they give all the pairs of vertices which are reachable by a straight robot finger. All of the convex ropes can be found in expected time order n, where n is the number of vertices of the polygon. We discuss the application of this geometric construction to automated grasp planning. The algorithm may also be useful in image interpretation and graphics where efficient computation of visible points is important. The direct application of the algorithm is restricted to two dimension since sequential ordering of vertices is required. Extension to three dimension would rely on well chosen intersecting or projective planes.

Sensory systems, such as computer vision, can be used to measure relative robot end-effector positions to derive feedback signals for control of end-effector positioning. The role of vision as the feedback transducer affects closed-loop dynamics, and a visual feedback control strategy is required. Vision-based robot control research has focused on vision processing issues, while control system design has been limited to ad-hoc strategies. We formalize an analytical approach to dynamic robot visual servo control systems by first casting position-based and image-based strategies into classical feedback control structures. The image-based structure represents a new approach to visual servo control, which uses image features (e.g., image areas, and centroids) as feedback control signals, thus eliminating a complex interpretation step (i.e., interpretation of image features to derive world-space coordinates). Image-based control presents formidable engineering problems for controller design, including coupled and nonlinear dynamics, kinematics, and feedback gains, unknown parameters, and measurement noise and delays. A model reference adaptive controller (MRAC) is designed to satisfy these requirements.

This paper describes a method for segmentation of convex shaped image regions. The wedge filter technique first employs the converging squares algorithm [1] to locate a region of interest. Then a region oriented boundary estimation technique, called the wedge filter, is applied. This wedge filter entails angular filtering and subsampling, and boundary interpolation. The technique is more capable of segmenting noncircular shapes than some earlier methods based on the Hough transform. In addition, unlike many edge-based segmentation schemes, this method is relatively tolerant to edge gaps and to blurred or thick edges. This technique is tested on a number of synthesized images over a range of convex shapes, for different algorithm parameters, and under various conditions of region size and image noise. In addition, the technique has been applied to segmentation of liver cell nuclei in light microscope images of human liver tissue.

Assembly tasks require the feeding, acquisition, orientation, and mating of parts subject to contact forces. Positional entropy provides an efficient tool for describing an assembly task and its system implementation in terms of the uncertainty in position and orientation of parts as the assembly sequence progresses. A parts entropy measure HQ(X) may be calculated from the probability distribution of parts positions and orientations at a given assembly step defined over an ensemble of repeated assembly tasks. The part entropy may be reduced mechanically by containerization, fixturing, manipulation, or product redesign. The part entropy may also be reduced using sensors (typically vision or tactile) by reducing the conditional entropy HQ(X/Y) due to the sensory measurement. The information obtained about part position may be defined in terms of the mutual information I(X;Y). In these terms, the goal of an assembly system is to reduce the joint entropy among parts by mating them in stable configurations. The positional entropy concept provides a unifying tool for assessing the relative effectiveness of systems designs which incorporate both mechanical and sensor-based techniques. The approach may also provide a useful ingredient for quantitative assessment of product designs, complexity of assembly procedures, and flexibility of assembly systems. An example of the use of positional entropy for analysis of an electronic assembly task is given.

The converging squares algorithm is a method for locating peaks in sampled data of two dimensions or higher. There are two primary advantages of this algorithm over conventional methods. First, it is robust with respect to noise and data type. There are no empirical parameters to permit adjustment of the process, so results are completely objective. Second, the method is computationally efficient. The inherent structure of the algorithm is that of a resolution pyramid. This enhances computational efficiency as well as contributing to the quality of noise immunity of the method. The algorithm is detailed for two-dimensional data, and is described for three-dimensional data. Quantitative comparisons of computation are made with two conventional peak picking methods. Applications to biomedical image analysis, and for industrial inspection tasks are discussed.

The converging squares algorithm is a method for locating peaks in sampled data of 2 dimensions or higher. There are two primary advantages of this algorithm over other conventional methods. First, it is robust with respect to noise and data type. There are no empirical parameters to allow adjustment of the process, so results are completely objective. Secondly, the method is computationally efficient. The inherent structure of the algorithm is that of a resolution pyramid. This enhances computational efficiency as well as contributing to the quality of noise immunity of the method. The algorithm is detailed for 2-dimensional data. Quantitative comparisons of computation are made with two conventional peak picking methods.

IN RECENT YEARS, experimental and theoretical progress has rekindled interest in the study of organizational and computational principles underlying neural systems. Neural systems are both complex and intriguing, and the relation of neural and sensory information processing to communications, control, and behavior in living organisms continues to pose fundamental research issues in a variety of disciplines. This Special Issue on Neural and Sensory Information Processing is intended to provide a timely sampling of current views and progress in these studies.

A method is presented which provides a criterion for detecting a change in the structure of a model generating a stochastic sequence. Models that can be represented by a sequence of predictive probability distributions are considered. The method is based on the transformation of the observed sequence\{x_{n}\}into a sequence of partial sums of the general innovations, computed for the sequence\{-\log f(x_{n}|x_{n-1},x_{n-2}, \cdots ,x_{0})\}. If no change occurs the transformed sequence behaves like a Wiener process, but its mean will exhibit a monotonic growth after the process changes. Based on the properties of this transformation, fixed sample size and sequential tests for the change are constructed. The technique is applied to test for a change in the mean vector in a sequence of (generally dependent) Gaussian random variables, a change of coefficients of an autoregressive process, and a change of distribution in a sequence of discrete independent identically distributed random variables.

Multivariate data sets with dependency between observations are described using a feature space representation. The resulting ordered set of points in feature space is termed the pattern trajectory. A set of descriptors of the pattern trajectory has been developed. Time-dependent clusters and transition segments form the basic structural description from which both lower level properties, e.g., cluster position, cluster dispersion, transition rate, and higher level properties, e.g., rebound, periodicity, finite state model, may be derived. Two algorithms have been developed for time-dependent cluster analysis. The time-weighted minimum spanning tree (TWMST) algorithm utilizes a composite space-time distance measure and creates clusters by cutting the longest tree branches. The time-dependent Isodata (TD-ISODATA) algorithm utilizes a global clustering to initiate the segmentation into timedependent cluster cores and transition segments. Examples of the applica tion of these algorithms to nonstationary neuronal spike train data and to simulated animal migration data are described. The pattern trajectory approach appears to offer advantages in the analysis of complex nonstationary data sets where conventional time series techniques are insufficient. Time-dependent clustering provides a means to identify a composite source model.

The discriminability of small changes in amplitude and frequency of a pure tone auditory stimulus is examined in terms of statistical estimators of neural coding parameters. The neural spike train encoding process is described in terms of a multimodal histogram of interspike intervals. Such a multimodal process has the important property that both stimulus amplitude and stimulus frequency can be encoded in the same spike train. Performance of the neural coding parameters is evaluated using the Cramér-Rao bound as a measure of discriminability of statistical estimators. The dependence of the Weber fraction for stimulus frequency and stimulus amplitude is derived as a function of frequency, amplitude, and observation interval. These results are compared to results of psychophysical experiments. It is concluded that while statistical estimates based on one primary auditory nerve fiber would be insufficient to account for psychophysical performance, estimates based on about 10-12 fibers sampled in parallel would be sufficient.