Recently, the behavior tree is gaining popularity as a robotic task-level knowledge representation. Manual design of behavior trees from scratch is tedious and cumbersome. Motivated by the need for an efficient way to reuse or transfer robot task-level knowledge, we propose a vector-space embedding approach that encodes a symbolic task into a numerical form. This approach, called behavior-tree embedding, takes a behavior tree that produces a single task as input and generates a corresponding vector. By exploiting the pretrained language-embedding model and the node-aggregation mechanism, the produced embedding is capable of preserving both semantic information of task description and structural information of the hierarchical task organization. We evaluated the effectiveness and versatility of our proposed vector-space embedding approach in three different tasks.

In this paper, we address the Online Unsupervised Domain Adaptation (OUDA) problem and propose a novel multi-stage framework to solve real-world situations when the target data are unlabeled and arriving online sequentially in batches. Most of the traditional manifold-based methods on the OUDA problem focus on transforming each arriving target data to the source domain without sufficiently considering the temporal coherency and accumulative statistics among the arriving target data. In order to project the data from the source and the target domains to a common subspace and manipulate the projected data in real-time, our proposed framework institutes a novel method, called an Incremental Computation of Mean-Subspace (ICMS) technique, which computes an approximation of mean-target subspace on a Grassmann manifold and is proven to be a close approximate to the Karcher mean. Furthermore, the transformation matrix computed from the mean-target subspace is applied to the next target data in the recursive-feedback stage, aligning the target data closer to the source domain. The computation of transformation matrix and the prediction of next-target subspace leverage the performance of the recursive-feedback stage by considering the cumulative temporal dependency among the flow of the target subspace on the Grassmann manifold. The labels of the transformed target data are predicted by the pre-trained source classifier, then the classifier is updated by the transformed data and predicted labels. Extensive experiments on six datasets were conducted to investigate in depth the effect and contribution of each stage in our proposed framework and its performance over previous approaches in terms of classification accuracy and computational speed. In addition, the experiments on traditional manifold-based learning models and neural-network-based learning models demonstrated the applicability of our proposed framework for various types of learning models.

Generative adversarial network (GAN)-based methods for zero-shot learning (ZSL) use the base category data as output and the semantic descriptors as conditional input for training so that the network can synthesize data for the novel classes. Using these generated data, the ZSL problem is converted into a supervised learning problem. Since the GAN is trained on only the base categories, the model prediction is biased towards the base categories. Also, the generated data for the novel categories might not accurately represent the ground truth. To address these problems, we propose a three-way solution. Firstly, we constrain the generation process such that the generated data from the novel classes can be highly discriminated from that of the base classes. This constraint tries to get rid of the biasness problem. Secondly, we enforce semantic consistency by reconstructing the semantic attributes from the generated data. Finally, we selectively adapt and transform the generated data from the novel classes to be close to the ground-truth unlabeled test data. We evaluated our framework on five standard datasets for ZSL and found our method to be highly competitive when compared with previous work. We also carried out additional studies to better understand our framework.

In this paper, we address the Online Unsupervised Domain Adaptation (OUDA) problem, where the target data are unlabelled and arriving sequentially. The traditional methods on the OUDA problem mainly focus on transforming each arriving target data to the source domain, and they do not sufficiently consider the temporal coherency and accumulative statistics among the arriving target data. We propose a multi-step framework for the OUDA problem, which institutes a novel method to compute the mean-target subspace inspired by the geometrical interpretation on the Euclidean space. This mean-target subspace contains accumulative temporal information among the arrived target data. Moreover, the transformation matrix computed from the mean-target subspace is applied to the next target data as a preprocessing step, aligning the target data closer to the source domain. Experiments on four datasets demonstrated the contribution of each step in our proposed multi-step OUDA framework and its performance over previous approaches.

This paper proposes a multi-layer neural network structure for few-shot image recognition of novel categories. The proposed multi-layer neural network architecture encodes transferable knowledge extracted from a large annotated dataset of base categories. This architecture is then applied to novel categories containing only a few samples. The transfer of knowledge is carried out at the feature-extraction and the classification levels distributed across the two training stages. In the first-training stage, we introduce the relative feature to capture the structure of the data as well as obtain a low-dimensional discriminative space. Secondly, we account for the variable variance of different categories by using a network to predict the variance of each class. Classification is then performed by computing the Mahalanobis distance to the mean-class representation in contrast to previous approaches that used the Euclidean distance. In the second-training stage, a category-agnostic mapping is learned from the mean-sample representation to its corresponding class-prototype representation. This is because the mean-sample representation may not accurately represent the novel category prototype. Finally, we evaluate the proposed network structure on four standard few-shot image recognition datasets, where our proposed few-shot learning system produces competitive performance compared to previous work. We also extensively studied and analyzed the contribution of each component of our proposed framework.

Zero-shot learning (ZSL) for image classification focuses on recognizing novel categories that have no labeled data available for training. The learning is generally carried out with the help of mid-level semantic descriptors associated with each class. This semantic-descriptor space is generally shared by both seen and unseen categories. However, ZSL suffers from hubness, domain discrepancy and biased-ness towards seen classes. To tackle these problems, we propose a three-step approach to zero-shot learning. Firstly, a mapping is learned from the semantic-descriptor space to the image-feature space. This mapping learns to minimize both one-to-one and pairwise distances between semantic embeddings and the image features of the corresponding classes. Secondly, we propose test-time domain adaptation to adapt the semantic embedding of the unseen classes to the test data. This is achieved by finding correspondences between the semantic descriptors and the image features. Thirdly, we propose scaled calibration on the classification scores of the seen classes. This is necessary because the ZSL model is biased towards seen classes as the unseen classes are not used in the training. Finally, to validate the proposed three-step approach, we performed experiments on four benchmark datasets where the proposed method outperformed previous results. We also studied and analyzed the performance of each component of our proposed ZSL framework.

Domain adaptation (DA) addresses the real-world image classification problem of discrepancy between training (source) and testing (target) data distributions. We propose an unsupervised DA method that considers the presence of only unlabelled data in the target domain. Our approach centers on finding matches between samples of the source and target domains. The matches are obtained by treating the source and target domains as hyper-graphs and carrying out a class-regularized hyper-graph matching using first-, second-and third-order similarities between the graphs. We have also developed a computationally efficient algorithm by initially selecting a subset of the samples to construct a graph and then developing a customized optimization routine for graph-matching based on Conditional Gradient and Alternating Direction Multiplier Method. This allows the proposed method to be used widely. We also performed a set of experiments on standard object recognition datasets to validate the effectiveness of our framework over previous approaches.

In this paper, we propose to achieve exponentially stable periodic bipedal walking based on recharacterization of bipedal gait and generalization of walking encoding. To conveniently define an asymmetric walking pattern, a gait is characterized here in terms of the left and the right legs instead of the support and the swing legs. Another benefit of this characterization is that the joint positions become well-defined and continuous throughout a walking process even under impulse effects caused by impacts. A more general walking encoding method is then introduced, which not only includes walking pattern encoding but also enables upper-level task planning and control. Walking dynamics is then rewritten with the roles of the left and the right legs differentiated and with the biped's global position included. The desired walking pattern, as well as the desired global motion, is tracked exponentially fast through a controller designed using the output feedback linearization method. Stability of the hybrid dynamical control system is analyzed based on the construction of multiple Lyapunov functions. Finally, a fully actuated compass-gait biped is simulated to show that the proposed framework can realize exponentially stable walking, both symmetric and asymmetric, while satisfactorily tracking the desired walking pattern and the planned global motion.

Performing manipulation tasks in human environments often requires coordinated motions. The Extended-Cooperative-Task Space (ECTS) presents a unified representation describing any type of coordinated motions of two end-effectors. This paper focuses on the specification of dual-arm motion tasks based on the ECTS representation and the evaluation of the performance of the specified tasks. We first examine how the ECTS motion variables can be used effectively to specify coordinated motions to manipulate different types of objects. Then we derive new performance indices that can be used to evaluate and optimize the configurations of dual-arm robot systems performing any type of coordinated-motion tasks. The experimental results of coordinated-motion tasks performed by a Baxter robot demonstrate intuitiveness and efficiency of ECTS-based task specifications. We also show that the proposed ECTS performance indices can enable redundancies in a dual-arm system to be effectively utilized for a larger range of workspace as well as desired control objectives.

Previous studies on human-pose estimation (HPE) rely on the design of factors to represent underlying probability distributions that model human poses. However, designing those factors manually is laborious. Moreover, manually designed factors might not represent underlying probability distributions properly. In this paper, we utilize feedforward neural networks (NNs) to design factors of our previous work on HPE and build an NN-based HPE system. We first propose a mapping that converts a Bayesian network to a feedforward NN. Then, the system is built based on the proposed mapping that consists of two steps: 1) structure identification and 2) parameter learning. In the structure identification, we develop a bottom-up approach to build a feedforward NN while preserving a Bayesian-network structure. In the parameter learning, we create a part-based approach to learn synaptic weights by decomposing a feedforward NN into parts. Using the proposed mapping, our previous work of an action-mixture model (AMM) for HPE is converted to a feedforward NN called NN-AMM. Based on the concept of distributed representation, NN-AMM is further modified to a scalable feedforward NN called NND-AMM. The NN-based HPE system is then built by using viewpoint-and-shape-feature-histogram features extracted from 3-D-point-cloud input and NND-AMM to estimate 3-D human poses. The results showed that the proposed mapping could design AMM factors automatically. NND-AMM could provide more accurate human-pose estimates with fewer hidden neurons than both AMM and NN-AMM could. Both NN-AMM and NND-AMM could adapt to different types of input, showing the adaptability of using feedforward NNs to design factors.

Locomotion stability of a humanoid robot is closely related to the capacity to regulate its Center of Mass (CoM) motion. In this paper, the Feasible Center of Mass Dynamic Manipulability (FCDM) is introduced and analyzed as a measure of this capacity. The effects of posture, joint velocities and gravity on the torque-bounded dynamic manipulability ellipsoid are first analyzed on an n-DOF planar humanoid robot with single-foot support. The ellipse orientation has a linear relationship with the ankle angle, and its shape is independent on the ankle angle. Furthermore, three common and important ground-contact constraints - the unilateral contact-force constraint, the friction constraint, and the Center of Pressure constraint - are incorporated in the derivation of FCDM. It shows geometrically how each of the three constraints shrinks the original torque-bounded manipulability polytope and affects the maximum achievable CoM acceleration in different directions. Finally, a push recovery task was simulated to show that a robot's posture affects the feasible range of the CoM acceleration in a specific direction.

A humanoid robot can be viewed as a constrained dynamic system with constraints imposed by manipulation tasks, locomotion tasks, and the environment. This paper focuses on dealing with constraints in the upper-body of humanoid robots for manipulation tasks that involve coordinated motion of two arms. Inspired by research on human bimanual actions in the biomechanics area, we have developed the Extended-Cooperative-Task-Space (ECTS) representation that efficiently describes various coordinated motion tasks performed by a humanoid robot. Furthermore, we present a general whole-body control framework as an optimal controller based on Gauss's principle of least constraint. We show that all the constraints imposed on a humanoid system can be handled in a unified manner. The proposed framework is verified by numerical simulations on a Hubo II+ humanoid robot model.

Previous studies on human-pose estimation rely on the design of factors to represent underlying probability distributions. However, designing factors is laborious and yet, the designed factors may not represent the underlying probability distributions. In this paper, we propose to use a neural network to automatically design factors in one of the existing models called the action-mixture model (AMM). Factors that are designed automatically by neural networks can be adapted to different situations. The semantic meaning of random variables in AMM can be transferred to a neural network, rendering the semantic meaning of hidden neurons transparent to users. The design process consists of two stages: structure identification and parameter learning. In the structure identification, we propose a bottom-up approach to build a neural network while preserving the structure of AMM. In the parameter learning, we propose a part-based approach to learn synaptic weights by decomposing a neural network into parts. Synaptic weights that have been learnt in one part can be used as initial weights for learning synaptic weights in another part. Based on the concept of distributed representation, the proposed two-stage, neural-network-based design process is used to design a scalable neural network to realize an AMM. Experimental results showed that the scalable neural network outperformed AMM and some existing works.

Information regarding vehicles in neighboring lanes is essential to an autonomous vehicle for decision-making during lane-change maneuvers. Complete autonomy requires effective velocity estimation of the neighboring vehicles under different road scenarios. A two-stage Interactive-Multiple-Model-based (IMM) estimator has been proposed to perform multiple target-tracking with application to vehicles in a lane-changing scenario. The first stage deals with an adaptive-window-based turn-rate estimation for tracking maneuvering targets. The estimator can detect abrupt changes in turnrates and function independently, and avoids the problem of non-linear vehicle dynamics, thereby facilitating the use of standard Kalman filter. Variable-structure models with updated estimated turn-rate are utilized in the second stage to perform data association followed by IMM-based velocity estimation. The proposed algorithm results in root-mean-squared error of position and velocity to 5–6 cm and 0.25–0.3 m/s, respectively, and the turn-rate converges up to 10% accuracy within 3–4 s. The algorithm has been validated using simulations and experimentation using mobile robots in a simulated lane environment.

Estimating human poses is an important step towards developing robots that can understand human motion. Since a human is highly articulated, changing viewpoints of sensors on robots can improve the accuracy of human-pose estimation. We propose a two-phase approach that determines the best viewpoint of a depth sensor for human-pose estimation. The proposed approach measures the quality of potential viewpoints and selects one of them as the best viewpoint for each human pose. Based on the quality of viewpoints, human poses can be directly mapped to the best viewpoint without reconstructing the human body. Thus, the proposed approach provides a discriminative mapping to determine the best viewpoint for estimating different human poses. To measure the quality of a potential viewpoint, the viewpoint is first instantiated by representing the depth sensor of the viewpoint using the finite projective camera model. The quality of the viewpoint is expressed in terms of the error of humanpose estimates. A mapping is derived by minimizing the error in a human-pose estimate among different viewpoints. The proposed two-phase approach has been evaluated on a benchmark database. Experimental results showed that the best viewpoint for a human pose could be determined by evaluating the quality of potential viewpoints. The mean error and standard deviation of human-pose estimates were reduced by using the best viewpoint determined by the proposed two-phase approach.

This paper presents an autonomous planning and control framework for humanoid robots to climb general ladder- and stair-like structures. The approach consists of two major components: 1) a multi-limbed locomotion planner that takes as input a ladder model and automatically generates a whole-body climbing trajectory that satisfies contact, collision, and torque limit constraints; 2) a compliance controller which allows the robot to tolerate errors from sensing, calibration, and execution. Simulations demonstrate that the robot is capable of climbing a wide range of ladders and tolerating disturbances and errors. Physical experiments demonstrate the DRC-Hubo humanoid robot successfully mounting, climbing, and dismounting an industrial ladder similar to the one intended to be used in the DARPA Robotics Challenge Trials.

This video presents our preliminary work towards addressing the ladder climbing event in DARPA Robotics Challenge (DRC) using DRC-Hubo robot. A ladder-climbing motion planner is developed which generates a collision-free, stable quasi-static trajectory for execution. Compliance control is enabled on arm joints to compensate for the calibration error, modeling error and control error. We have demonstrated that DRC-Hubo can robustly climb a variety of ladders in simulation and successfully climb a ship ladder on the hardware.

A mobile visual sensor network has a potential to create impacts in many applications in the society; however, it remains a challenge to keep the network lifetime as long as possible with limited onboard energy. Based on our previous work, mobility can be exploited to improve network lifetime significantly for data-intensive mobile sensor networks. In a visual sensor network, besides heavy data transmission, the video encoding process consumes a considerable portion of the energy. With the quality of visual sensing in mind, this paper investigates a joint design method to simultaneously design mobility, source data rate, routing, and video encoding strategies for robotic visual sensor nodes to improve the lifetime of a mobile visual sensor network. We formulate the network lifetime problem as a nonlinear, non-convex, optimization problem, and we propose to solve it distributively by a series of convex approximations and a proposed novel algorithm. Computer simulations were conducted to verify its quick convergence to the solution and the improvement of the lifetime of the network using mobility.

This paper focuses on human-pose estimation using a stationary depth sensor. The main challenge concerns reducing the feature ambiguity and modeling human poses in high-dimensional human-pose space because of the curse of dimensionality. We propose a 3-D-point-cloud system that captures the geometric properties (orientation and shape) of the 3-D point cloud of a human to reduce the feature ambiguity, and use the result from action classification to discover low-dimensional manifolds in human-pose space in estimating the underlying probability distribution of human poses. In the proposed system, a 3-D-point-cloud feature called viewpoint and shape feature histogram (VISH) is proposed to extract the 3-D points from a human and arrange them into a tree structure that preserves the global and local properties of the 3-D points. A nonparametric action-mixture model (AMM) is then proposed to model human poses using low-dimensional manifolds based on the concept of distributed representation. Since human poses estimated using the proposed AMM are in discrete space, a kinematic model is added in the last stage of the proposed system to model the spatial relationship of body parts in continuous space to reduce the quantization error in the AMM. The proposed system has been trained and evaluated on a benchmark dataset. Computer-simulation results showed that the overall error and standard deviation of the proposed 3-D-point-cloud system were reduced compared with some existing approaches without action classification.

Estimating human poses is an important step towards developing robots that can understand human motions and improving their cognitive capabilities. This paper presents a geometric feature for estimating human poses from a 3D point cloud input. The proposed feature can be considered as an extension of the idea of visual features, such as color/edge, of color/grayscale images, and it contains the geometric structure of the point cloud. It is derived by arranging the 3D points into a tree structure, which preserves the global and local properties of the 3D points. Shown experimentally, the tree structure (spatial ordering) is particularly important for estimating human poses (i.e., articulated objects). The 3D orientation (pan, tilt and yaw angles) and shape features are then extracted from each node in the tree to describe the geometric distribution of the 3D points. The proposed feature has been evaluated on a benchmark dataset and compared with two existing geometric features. Experimental results show that the proposed feature has the lowest overall error in human-pose estimation.

This paper studies the use of Cooperative Dual-Task Space (CDTS) as an efficient approach for the whole-body motion balancing problem for humanoid robots. The CDTS variables have been used efficiently to describe and control coordinated motions of dual-arms. Similarly, the concept of CDTS variables can be extended to describe the constraints and the control of humanoid legs. When the leg motion is described and controlled by CDTS variables, the variables regarding the feet constraints and the control variables in the leg motion regarding the waist movement can be nicely decoupled. One of the CDTS variables can be used to describe the constraints on the feet, and the constraints can be expressed independently of the support-foot changes. The proposed CDTS-based method provides an efficient way to stabilize the merged whole-body motion by modifying the horizontal waist position by a coordinated motion of both legs while satisfying the changing constraints on both feet in the lower-body motion. Thus, the proposed CDTS-based method provides the possibility of generating a large library of whole-body motions for a humanoid robot by combining an upper-body motion captured from humans and lower-body motions generated by an existing biped walking pattern planner. The performance of the proposed CDTS-based approach was validated through extensive simulations including cases that showed a HOAP-2 robot walking on a flat terrain and climbing up the stairs with a rapid upper-body movement.

This paper presents a 3D-point-cloud system that extracts a 3D-point-cloud feature (VISH) from the observation of a depth sensor to reduce feature/depth ambiguity and estimates human poses using the result of action classification and a kinematic model. Based on the concept of distributed representation, a non-parametric action-mixture model is proposed in the system to represent high-dimensional human-pose space using low-dimensional manifolds in searching human poses. In each manifold, the probability distribution is estimated by the similarity of features. The distributions in the manifolds are then redistributed according to the stationary distribution of a Markov chain that models the frequency of actions. After the redistribution, the manifolds are combined according to the distribution determined by the action classification. In addition, the spatial relationship between human-body parts is explicitly modeled by a kinematic chain. Computer-simulation results showed that multiple low-dimensional manifolds can represent human-pose space. The 3D-point-cloud system showed reduction of the overall error and standard deviation compared with other approaches without using action classification.

This paper presents a hierarchal, two-layer, connectionist-based human-action recognition system (CHARS) as a first step towards developing socially intelligent robots. The first layer is a K-nearest neighbor (K-NN) classifier that categorizes human actions into two classes based on the existence of locomotion, and the second layer consists of two multi-layer recurrent neural networks that distinguish between subclasses within each class. A pyramid of histograms of oriented gradients (PHOG) descriptor is proposed for extracting local and spatial features. The PHOG descriptor reduces the dimensionality of input space drastically, which results in better convergence for the learning and classification processes. Computer simulations were conducted to illustrate the performance of the proposed CHARS and the role of temporal factor in solving this problem. A widely used KTH human-action database and the human-action dataset from our lab were utilized for performance evaluation. The proposed CHARS was found to perform better than other existing human-action recognition methods and achieved a 95.55% recognition rate.

This paper presents a real-time emotion recognition system (RTERS) as a first step towards developing a socially intelligent robot. The RTERS first localizes faces in a sequence of images, then features are extracted and passed to a recognition engine that codes facial expressions into one of seven different emotional states: happiness, sadness, fear, disgust, anger, surprise, and neutrality.We propose and develop a distance-based classifier, called Distance-Ratio Classifier, for emotion identification from the feature vectors. The performance of the proposed distance-ratio classifier was compared with support-vector-machine-based classifiers, using different feature extraction and dimensionality reduction approaches, including principal component analysis, linear discriminant analysis, kernel principal component analysis, greedy kernel principal component analysis, and generalized discriminant analysis. Extensive computer simulations were conducted to illustrate the performance of the proposed RTERS. Using two widely used databases for performance evaluation, the best performance of the proposed RTERS was 95.8% using the generalized discriminant analysis for dimensionality reduction and the proposed distance-ratio classifier.

This paper presents a Nonlinear AutoRegressive with eXogenous input (NARX)-based approach for human-emotion recognition from an input video. The dynamics of facial expressions are first captured by performing a temporal-spatial analysis by extracting local and spatial features using a pyramid of histograms of oriented gradients (PHOG) descriptor. Then the temporal phases of facial expressions are identified using our proposed Mutual-Information-based Delay Identification Algorithm. Finally, the emotion recognition problem is formulated into a parametric regression context using a recurrent NARX network. This approach enhances the cognitive skills of humanoid robots by adding the ability to recognize and understand affective emotional states of a human. Computer simulations were conducted to illustrate the performance of the proposed NARX-based approach with recurrent neural network realization. The proposed recurrent NARX network performed better than other existing human-emotion recognition systems and achieved a 91.5% recognition rate when tested using the Cohn-Kanade database.

This paper investigates mobility strategies of mobile robots to improve the lifetime of a mobile sensor network with energy harvesting capability. The network lifetime problem is formulated as a nonlinear non-convex optimization problem, which is solved distributively by a series of convex approximations and a novel saddle-point computation algorithm. The convergence of the proposed method is guaranteed. Computer simulations showed quick convergence to the optimal solution in most cases, and verified the use of mobility for energy efficiency by showing its significant improvement to the network lifetime and relatively low cost in mobility.

The positions of mobile sensor nodes and the routing of sensing data to a base station for processing have major impact on the lifetime of a mobile sensor network. Based on our previous work on mobility for lifetime maximization, this paper investigates simultaneously designing mobility and routing strategies of robotic sensor nodes to improve the lifetime of a mobile sensor network. The network lifetime problem was formulated as a nonlinear non-convex optimization problem and is solved distributedly by a series of convex approximations and a proposed novel algorithm. Computer simulations illustrated quick convergence to the solution, and the lifetime of the network was improved tremendously. By comparison, the proposed joint design method has an edge over other methods, which further justifies the use of mobility for energy efficiency in robotic sensor networks.

This paper studies mobility strategies to control positions of mobile robots in a mobile sensor network in order to maximize lifetime of the network. With communication and mobility energy costs modeled, the problem is formulated into a nonlinear non-convex optimization problem, then reformulated into a convex optimization problem. The separable property of the system is then exploited by Lagrangian duality, and the solution is obtained by distributed saddle-point computations. Computer simulations showed that the proposed distributed algorithm can quickly converge to the optimal solution, and it also justifies the use of mobility for energy efficiency by showing its significant improvement to the network lifetime and relatively low cost in mobility. Furthermore, the proposed energy optimization framework can accommodate different mobile sensor network models.

This paper studies optimal control in a sensor network system consisting of mobile robots to minimize the overall energy consumption of the whole network. With communication energy cost and mobility energy cost taken into consideration, the problem is formulated as an optimal control of a hybrid system, which is solved by switched Linear Quadratic Regulator (LQR). Though switched LQR obtains globally optimal solution, the computational complexity is too high to implement the algorithm when the control horizon expands. For this reason, we resort to a switched system version of Receding Horizon Control (RHC), which is stable and provides a solution close to the optimal one. Finally, in order to attenuate the complexity due to the large networked system, the centralized RHC is modified into a distributed algorithm, which converges to a solution that can approximate the optimizer quite well as verified by simulations.

This paper focuses on developing a consistent methodology for deriving a closed-form inverse kinematic joint solution of a general humanoid robot. Most humanoid-robot researchers resort to iterative methods for inverse kinematics using the Jacobian matrix to avoid the difficulty of finding a closed-form joint solution. Since a closed-form joint solution, if available, has many advantages over iterative methods, we have developed a novel reverse decoupling mechanism method by viewing the kinematic chain of a limb of a humanoid robot in reverse order and then decoupling it into the positioning and orientation mechanisms, and finally utilizing the inverse transform technique in deriving a consistent joint solution for the humanoid robot. The proposed method presents a simple and efficient procedure for finding the joint solution for most of the existing humanoid robots. Extensive computer simulations of the proposed approach on a Hubo KHR-4 humanoid robot show that it can be applied easily to most humanoid robots with slight modifications.

Mobile robots are widely used for computation-intensive tasks such as surveillance, moving object recognition and tracking. Existing studies perform the computation entirely on robot processors or on dedicated servers. The robot processors are limited by their computation capability; real-time performance may not be achieved. Even though servers can perform tasks faster, the communication time between robots and servers is affected by variations in wireless bandwidths. In this paper, we present a system for realtime moving object recognition and tracking using computation offloading. Offloading migrates computation to servers to reduce the computation time on the robots. However, the migration consumes additional time, referred as communication time in this paper. The communication time is dependent on data size exchanged and the available wireless bandwidth. We estimate the computation and communication needed for the tasks and choose to execute them on robot processors or servers to minimize the total execution time, in order to satisfy real-time constraints.

Robot motor capability is crucial for skill learning because it determines how accurately and rapidly a robot can perform a skill to accomplish a task constrained by the spatial and temporal conditions. Due to the capability of robot motor, a robot may not be able to perform skills to satisfy both task spatial and temporal constraints. To determine the robot motor capability, this paper formulates the skill for accomplishing a task as an optimization problem subject to the spatial and temporal conditions of the task, and proposes to develop a speed-accuracy constraint suitable for the optimization problem. The proposed speed-accuracy constraint is derived from the kinematics, dynamics, and control of a robot motor system. By solving the optimization problem, a robot can perform the skill to achieve a task by its fastest speed without violating the spatial and temporal conditions of the task. Computer simulations were performed on a PUMA 560 robot to demonstrate a skill on a typical task to validate the proposed speed-accuracy optimization.

Robot skills are usually learned from the so-called learning-from-human-demonstration methods. However, with the limitation of robot motor capability, a robot may not be able to duplicate human motor skills with the same motor performance. To alleviate the problem, one of the possible solutions is to know robot motor capability in advance. Thus, we develop a quantitative measure of a robot motor system, called a pseudo index of motor performance (pIp), and utilize it to compare with the index of performance (Ip) of a human motor system. To investigate the Ip, we propose an information-theory-based method to characterize a robot motor system. Computer simulations and experiments with a PUMA 560 robot will be conducted to validate the proposed information-theory-based method.

Endowing robots with the ability of skill learning enables them to be versatile and skillful in performing various tasks. This paper proposes a skill-decomposition framework, which differs from previous work in its capability of decomposing a skill by self-categorizing it into significant stimulusresponse units (SRU). The proposed skill-decomposition framework can be realized by stages with a 5-layer neuro-fuzzy network with supervised learning, resolution control and reinforcement learning, to enable robots to identify a sufficient number of significant SRUs for accomplishing a given task. Computer simulations and experiments with a Pioneer DX-3 mobile robot were conducted to validate the self-categorization capability of the proposed skill-decomposition framework in learning and identifying significant SRUs from task examples.

Endowing robots with the ability of self-organizing learned skills enables them to learn a new skill from learned skills. This paper proposes a skill-synthesis framework to enable robots to self-organize learned skills for facilitating learning a new skill for accomplishing a new task. The proposed skill-synthesis framework differs from previous work in its capability of self-organizing learned skills into stimulus-response units (SRU), from which new skills can be quickly learned and synthesized. The proposed skill-synthesis framework can be realized by stages, which establish common SRUs between two similar skills and self-organize a new skill from these common SRUs and additional new SRUs with reinforcement learning. Computer simulations and experiments with a Pioneer 3-DX mobile robot were conducted to validate the self-organizing capability of the proposed skill-synthesis framework in identifying common SRUs between similar skills and learning new skills from learned skills.

In recent years, the success of single-robot SLAM has led to more multi-robot SLAM (MR-SLAM) research. A team of robots with MR-SLAM can explore an environment more efficiently and reliably; however, MR-SLAM also raises many challenging problems, including map fusion, unknown robot poses and scalability issues. The first two problems can be considered as an optimization problem of finding a consistent joint map based on robots’ relative poses and sensory data. This optimization problem exhibits a similar property of a singlerobot topological/metric mapping. To exploit this property, we propose a multi-robot SLAM (MR-SLAM) algorithm, which builds a graph-like topological map with vertices representing local metric maps and edges describing relative positions of adjacent local maps. In this MR-SLAM algorithm, the map fusion between two robots can be naturally done by adding an edge that connects two topological maps, and the estimation of relative robot pose is simply performed by optimizing this edge. For the third scalable problem, the proposed algorithm is also scalable to the number of robots and the size of an environment. Computer simulations with a public data set and experimental work on Pioneer 3-DX robots have been conducted to validate the performance of the proposed MR-SLAM algorithm.

Traditionally, simultaneous localization and mapping (SLAM) algorithms solve the localization and mapping problem in explored regions. This paper presents a prediction-based SLAM algorithm (called P-SLAM), which has an environmental-structure predictor to predict the structure inside an unexplored region (i.e., look-ahead mapping). The prediction process is based on the observation of the surroundings of an unexplored region and comparing it with the built map of explored regions. If a similar environment/structure is matched in the map of explored regions, a hypothesis is generated to indicate that a similar structure has been explored before. If the environment has repeated structures, the mobile robot can use the predicted structure as a virtual mapping, and decide whether or not to explore the unexplored region to save the exploration time. If the mobile robot decides to explore the unexplored region, a correct prediction can be used to speed up the SLAM process and build a more accurate map. We have also derived the Bayesian formulation of P-SLAM to show its compact recursive form for real-time operation. We have experimentally implemented the proposed P-SLAM on a Pioneer 3-DX mobile robot using a Rao-Blackwellized particle filter in real time. Computer simulations and experimental results validated the performance of the proposed P-SLAM and its effectiveness in indoor environments

Traditionally, the SLAM problem solves the localization and mapping problem in explored and sensed regions. This paper presents a prediction-based SLAM algorithm (called P-SLAM), which has an environmental structure predictor to predict the structure inside an unexplored region (i.e., look-ahead mapping). The prediction process is based on the observation of the surroundings of an unexplored region and comparing it with the built map of explored regions. If a similar structure is matched in the map of explored regions, a hypothesis is generated to indicate that a similar structure has been explored before. If the environment has repeated structures, the mobile robot can utilize the predicted structure as a virtual mapping, and decide whether or not to explore the unexplored region to save exploration time. If the mobile robot decides to explore the unexplored region, a correct prediction can be utilized to localize the robot and speed up the SLAM process. We also derive the Bayesian formulation of P-SLAM to show its compact recursive form for real-time operation. We have experimentally implemented the proposed P-SLAM in a Pioneer 3-DX mobile robot using a Rao-Blackwellized particle filter in real-time. Computer simulations and experimental results validated the performance of the proposed P-SLAM and its effectiveness in an indoor environment

Mobile robots can be used in many applications, including exploration in an unknown area. Robots usually carry limited energy so energy conservation is vital. This paper presents an approach for energy-efficient robot exploration. Our approach determines the next target for the robot to visit based upon orientation information. The robot plans the path between the current position to the next target in an energy-efficient way. Our method reduces repeated coverage, a common problem for most existing utility-based target selecting methods. We conduct simulations for both random and structured environments, and compare our method with a utility-based method that chooses the middle cell from the widest opening. Results show that our method can reduce energy consumption by 42% and traveling distance by 41%

In this paper, we propose zero moment point (ZMP) manipulability ellipsoid as an extension to the existing ZMP balance criterion. The ZMP manipulability ellipsoid was developed by combining the ZMP balance criterion, the humanoid robot dynamics and the manipulability of robotic manipulators. The ZMP manipulability ellipsoid represents the ability of a humanoid robot to instantly move the ZMP from its current ZMP location within the balance criterion. The size and shape of the ZMP manipulability ellipsoid are a function of the joint-torque limitation of a humanoid robot. Thus, the ellipsoid forms an area in which the ZMP can be manipulated instantly, and the larger the ellipsoid, the better the propensity of a humanoid robot will be to recover from an unbalanced situation. We also show that the gravity force of a humanoid robot affects neither the shape nor the translation of the ellipsoid. Furthermore, we show that the ZMP manipulability ellipsoid can aid the humanoid-robot design process by choosing appropriate actuators. Finally, a four degree-of-freedom walking robot was used to illustrate the proposed ZMP manipulability ellipsoid

Mobile robots can be used in many applications, such as carpet cleaning, search and rescue, and exploration. Many studies have been devoted to the control, sensing, and communication of robots. However, the deployment of robots has not been fully addressed. The deployment problem is to determine the number of groups unloaded by a carrier, the number of robots in each group, and the initial locations of those robots. This paper investigates robot deployment for coverage tasks. Both timing and energy constraints are considered; the robots carry limited energy and need to finish the tasks before deadlines. We build power models for mobile robots and calculate the robots' power consumption at different speeds. A speed-management method is proposed to decide the traveling speeds to maximize the traveling distance under both energy and timing constraints. Our method uses rectangle scanlines as the coverage routes, and solves the deployment problem using fewer robots. Finally, we provide an approach to consider areas with random obstacles. Compared with two simple heuristics, our solution uses 36% fewer robots for open areas and 32% fewer robots for areas with obstacles.

In recent years, the rapid growth of peer-to-peer (P2P) networks has provided a new paradigm for content distribution. To improve the efficiency of a P2P system, it is important to provide incentives for the peers to participate and contribute their resources. Various attempts have been made to reward/penalize peers by providing service differentiation based on a requesting peer's history or reputation. However, in a truly distributed, non-cooperative environment, maintaining and preventing the untruthful revealing of such information within the community impose larger computation and communication overheads to the system. These problems are further magnified when large-volume contents are being distributed because of the length distribution processes and the update of history or reputation has to keep up with the distribution process. In this paper, we address the incentive provisioning problem for distribution of large-volume content in P2P networks, and present a "seeing-is-believing" incentive-compatible mechanism (protocol) in which a peer will decide how much resources will be assigned to which neighbors based on what it has experienced. The protocol applies a utility-based resource-trading concept where peers will maximize their contributions for a fair or better return, and we show that by adopting this protocol, the system will achieve Cournot Equilibrium. Furthermore, our protocol is light-weight, completely decentralized, and cheat-proof. Experimental results illustrate significant improvements on the distribution efficiency of our protocol over other adopted alternatives.

Mobile robot teams have many useful applications such as search and rescue, exploration and hazard detection and analysis. Communication between the robots of a team as well as between the robots and a human operator or controller are useful for many applications. Many applications of mobile robots involve scenarios in which no communication infrastructure such as base stations exist (e.g. demining in battlefields) or the existing infrastructure is damaged (e.g. search and rescue after an earthquake). In such scenarios, it is necessary for mobile robots to form an ad hoc network to enable communication by forwarding each other’s packets. In many applications, group communication can be used for flexible control, organization, and management of the mobile robots. Multicast provides a bandwidth efficient communication method between a source and a group of robots. In this paper, we propose an efficient multicast protocol MRMM (Mobile Robot Mesh Multicast) for deployment in mobile robot networks. MRMM exploits the fact that mobile robots know what velocity they are instructed to move at and for what distance in building a long lifetime sparse mesh for group communication that is more efficient. Our results show that MRMM provides an efficient group communication mechanism that can potentially be used in many mobile robot application scenarios.

Mobile multi-robot teams are useful in many critical applications such as search and rescue. Explicit communication among robots in such mobile multi-robot teams is useful for the coordination of such teams as well as exchanging data. Since many applications for mobile robots involve scenarios in which communication infrastructure may be damaged or unavailable, mobile robot teams frequently need to communicate with each other by using ad hoc networking. In such scenarios, energy efficient routing protocols to deliver messages among robots are a key requirement. In this paper, we propose and evaluate two routing protocols tailored for use in ad hoc networks formed by mobile multi-robot teams: Mobile Robot Distance Vector (MRDV) and Mobile Robot Source Routing (MRSR). Both protocols exploit the unique mobility characteristics of mobile robot networks to perform efficient routing. Our simulation study show that both MRDV and MRSR incur lower overhead while operating in mobile robot networks when compared to traditional mobile ad hoc network routing protocols such as DSR and AODV.

Mobile robots usually carry limited energy and have to accomplish their tasks before deadlines. Examples of these tasks include search and rescue, landmine detection, and carpet cleaning. Many researchers have been studying control, sensing, and coordination for these tasks. However, one major problem has not been fully addressed: the initial deployment of mobile robots. The deployment problem considers the number of robots needed and their initial locations. In this paper, we present a solution for the deployment problem when robots have limited energy and time to collectively accomplish coverage tasks. Simulation results show that our method uses 26% fewer robots comparing with two heuristics for covering the same size of area.

This paper addresses the problem of whole-body trajectory generation in humanoid robot performing a manipulation task. The approach utilizes coordination of prioritized movements of the Center of Mass (CM), foot and hand. A Center of Mass trajectory is computed from the desired Zero Moment Point (ZMP) trajectory while stepping. The ability to maneuver horizontal CM is related to the ability to maintain balance. Generally, the vertical CM movement is left unspecified. In this paper, the horizontal CM manipulability is associated with the CM height through the shape of the CM manipulability ellipsoid. A posture with a larger horizontal CM manipulability ellipsoid is more stable in the sense that its CM can be easily maneuvered as required by the desired ZMP with less joint effort. Computer simulation was conducted to verify the performance and consistency of the proposed approach for generating balance stepping motion with a manipulation task.

Mobile robots provide new opportunities for research in environment sensing. By combining sensors and robots, we can develop applications to enhance security, search and rescue, and detect hazardous materials. One important problem is to use fewer mobile sensors to cover an area. This paper focuses on two problems in robot sensor deployment: speed management and detouring distance under energy and timing constraints. We determine the robots' traveling speed based on the remaining energy and remaining time before deadline. We use probabilistic models for environments with obstacles and propose an empirical analysis to estimate the extra traveling distance due to detouring. We compute the number of robots (fleet size) needed for cover an area and our approach reduces the fleet size. Compared with two simple heuristics, our method uses 21% fewer robots.

In recent years, the rapid growth of peer-to-peer (P2P) networks has provided a new paradigm for content distribution. To improve the efficiency of a P2P system, it is important to provide incentives for the peers to participate and contribute their resources. In this work, we address the incentive provisioning problem for distribution of large-volume content in P2P networks, and present a "seeing-is-believing" incentive-compatible mechanism in which a peer will decide how much resources will be assigned to which neighbors based on what it has experienced. The protocol applies a utility-based resource-trading concept where peers will maximize their contributions for a fair or better return, and we show that by adopting this protocol, the system will achieve Cournot Equlibrium. Our protocol is light-weight, completely decentralized, and cheat-proof.

BitTorrent is a popular, open-source, hybrid peer-to-peer content distribution system that is conducive for distribution of large-volume contents. In this paper, we propose a genetic-algorithm-based neighbor-selection strategy for hybrid peer-to-peer networks, which enhances the decision process performed at the tracker for transfer coordination. We also investigate how the strategy affects system throughput and distribution efficiency as well as peer contributions. We show through computer simulations that by increasing content availability to the clients from their immediate neighbors, it can significantly improve the system performance without trading off users' satisfaction. The proposed strategy can significantly improve the efficiency of distribution, especially for low-connectivity peers, and it is suitable to deploy for online decisions

In this paper, we investigate energy-time-efficient dispatching methods for ant-like robots to cover an unmapped region effectively. These ant-like robots have very limited energy and sensor ability, making them practical and inexpensive to build. Our dispatching model was based on bio-inspired algorithms from an ant colony system. We assumed that all the ant-like robots start from their home starting point, the nest, and the region is composed of floor tiles that can be modelled as vertices in a graph. In this dispatching system, the ant-like robots leave pheromone on the tiles and use this information to cover the region. We developed and analyzed two different adaptive dispatching algorithms with different communication methods to the nest. We further compared these two adaptive dispatching algorithms with two non-adaptive methods. Extensive computer simulations validated the proposed adaptive algorithms, showing that they can dispatch ant-like mobile robots to cover an unmapped region with energy-time efficiency.

We study the problem of supporting communication in mobile sensor networks formed by teams of mobile robots equipped with sensors. We assume that in addition to communicating with each other by implicit or environmental means, the robots are equipped with wireless communication capability and effectively form a mobile ad hoc network (MANET). However, unlike typical MANETs where the primary communication pattern is any-to-any, such mobile multi-robot sensing networks need to support sensing applications which exhibit a many-to-one communication pattern. We evaluate the ability of current ad hoc network routing protocols to support communication in such sensing networks using detailed simulations of 50 robots. We consider typical communication patterns that arise in sensing applications and their impact on success rates, routing overhead, and energy costs of the mobile sensor network.

This paper presents a new approach to find energy-efficient motion plans for mobile robots. Motion planning has two goals: finding the routes and determining the velocities. We model the relationship of motors' speed and their power consumption with polynomials. The velocity of the robot is related to its wheels' velocities by performing a linear transformation. We compare the energy consumption of different routes at different velocities and consider the energy consumed for acceleration and turns. We use experiment-validated simulation to demonstrate up to 51% energy savings for searching an open area.

Simultaneous localization and map building (SLAM) is a fundamental and complex problem in mobile robot research. In SLAM, Kalman-filter-like implementations are widely adopted to localize a mobile robot and build a map simultaneously and incrementally. However, this approach requires extensive computations of order O(N/sup 2/), where N is the total number of landmarks. To make the computations more manageable, we propose a logarithmic map partitioning algorithm that partitions the global map into one local region and several sub-maps. The size of each sub-map is based on its distance from the mobile robot, and in each sub-map, a centroid landmark is selected to represent all the landmarks in the sub-map for SLAM computations. With this logarithmic-map partitioning, it maintains correlation updates with each sub-map and provides an efficient suboptimal solution to the SLAM problem. The number of landmarks reduces from N to a logarithm-based function of N, and the computational requirement reduces from O(N/sup 3/) to O(N/sup 2/), where N/sub L/ is the number of local landmarks. Furthermore, utilizing the compressed extended Kalman filter, the real-time computational complexity reduces to O(N/sub L//sup 2/). Computer simulation results showed that the proposed algorithm is consistent and efficient for a large number of landmarks.

As robotics technologies improve, mobile robots can be used in many applications. A fundamental question is to decide the number of robots needed (i.e., the "fleet-size problem") to accomplish tasks. Previous studies did not consider the energy constraints of the fleet size problem. In this paper, we present a probabilistic method to decide the fleet size for serving random requests. A simplification method is provided for fast computation. Our method is computationally efficient, with an average of 4% errors validated by an event-driven simulator.

This paper presents the utilization of a self-adaptive recurrent neuro-fuzzy control as a feedforward controller and a proportional-plus-derivative (PD) control as a feedback controller for controlling an autonomous underwater vehicle (AUV) in an unstructured environment. Without a priori knowledge, the recurrent neuro-fuzzy system is first trained to model the inverse dynamics of the AUV and then utilized as a feedforward controller to compute the nominal torque of the AUV along a desired trajectory. The PD feedback controller computes the error torque to minimize the system error along the desired trajectory. This error torque also provides an error signal for online updating the parameters in the recurrent neuro-fuzzy control to adapt in a changing environment. A systematic self-adaptive learning algorithm, consisting of a mapping-constrained agglomerative clustering algorithm for the structure learning and a recursive recurrent learning algorithm for the parameter learning, has been developed to construct the recurrent neuro-fuzzy system to model the inverse dynamics of an AUV with fast learning convergence. Computer simulations of the proposed recurrent neuro-fuzzy control scheme and its performance comparison with some existing controllers have been conducted to validate the effectiveness of the proposed approach.

This paper presents the utilization of a self-adaptive recurrent neuro-fuzzy control as a feedforward controller and a proportional-plus-derivative (PD) control as a feedback controller for controlling an autonomous underwater vehicle (AUV) in an unstructured environment. Without a priori knowledge, the recurrent neuro-fuzzy system is first trained to model the inverse dynamics of the AUV and then it utilized as a feedforward controller to compute the nominal torque of the AUV along a desired trajectory. The PD feedback controller computes the error torque to minimize the system error along the desired trajectory. This error torque also provides an error signal for online updating the parameters in the recurrent neuro fuzzy control to adapt in a changing environment. A systematic self-adaptive learning algorithm, consisting of a mapping-constrained agglomerative clustering algorithm for the structure learning and a recursive recurrent learning algorithm for the parameter learning, was developed to construct the recurrent neuro-fuzzy system to model the inverse dynamics of an AUV with fast learning convergence. Computer simulations of the proposed recurrent neuro-fuzzy control scheme and its performance comparison with an adaptive controller were conducted to validate the effectiveness of the proposed approach.

This paper presents a self-adaptive neuro-fuzzy inference system (SANFIS) that is capable of self-adapting and self-organizing its internal structure to acquire a parsimonious rule-base for interpreting the embedded knowledge of a system from the given training data set. A connectionist topology of fuzzy basis functions with their universal approximation capability is served as a fundamental SANFIS architecture that provides an elasticity to be extended to all existing fuzzy models whose consequent could be fuzzy term sets, fuzzy singletons, or functions of linear combination of input variables. Without a priori knowledge of the distribution of the training data set, a novel mapping-constrained agglomerative clustering algorithm is devised to reveal the true cluster configuration in a single pass for an initial SANFIS construction, estimating the location and variance of each cluster. Subsequently, a fast recursive linear/nonlinear least-squares algorithm is performed to further accelerate the learning convergence and improve the system performance. Good generalization capability, fast learning convergence and compact comprehensible knowledge representation summarize the strength of SANFIS. Computer simulations for the Iris, Wisconsin breast cancer, and wine classifications show that SANFIS achieves significant improvements in terms of learning convergence, higher accuracy in recognition, and a parsimonious architecture.

Examines several clustering methods for structure learning in constructing efficient neuro-fuzzy systems. The structure learning establishes the internal structure (i.e., the number of term sets and fuzzy-rule base generation) of a given neuro-fuzzy architecture. The fundamental ideas of existing rule generation algorithms are addressed and discussed. Performance of the neuro-fuzzy systems established from these clustering methods is validated through computer simulations of the classification problem of IRIS and the control example of an autonomous underwater vehicle.

In this paper, we propose a neuro-fuzzy scheduler (NFS) for a multimedia Web server to ensures synchronized delivery of multimedia documents. The problem of scheduling multimedia information to ensure media synchronization in a Web environment is identified as a multicriteria scheduling problem which is NP-hard. The proposed NFS makes an intelligent compromise among multicriteria by properly combining some scheduling heuristics. Performance of the NFS is compared with several known heuristics and a branch and bound algorithm. The results show that the proposed neuro-fuzzy scheduler can dynamically adjust to the varying work-load quite well.

Presents a systematic approach for developing a concise self-adaptive neuro-fuzzy inference system (SANFIS) with a fast hybrid parameter learning algorithm for online learning the control knowledge for autonomous underwater vehicles (AUV). The multi-layered structure of SANFIS incorporates fuzzy basis functions for better function approximations. Based on the need of different applications, we investigate three SANFIS structures with three different types of fuzzy IF-THEN-rule-based models and cast the rule formation problem as a clustering problem. A recursive least squares algorithm and a modified Levenberg-Marquardt algorithm with limited memory are exploited to accelerate the learning process. Thus, incorporating an online clustering technique, a fast hybrid learning procedure and rule examination, the SANFIS is capable of self-organizing and self-adapting its internal structure for learning the required control knowledge for an AUV to follow desired trajectories. Computer simulations for modeling a control system for an AUV have been conducted to validate the effectiveness of the proposed SANFIS.

This paper presents a systematic and fast learning algorithm for developing a parsimonious internal structure for self-adaptive neuro-fuzzy inference system (SANFIS). The rule extraction problem is cast as a clustering problem so that the number of rules and the number of term sets for input and output variables can be determined in an efficient and systematic way. The consequent of SANFIS could be fuzzy term sets, fuzzy singleton values, or functions of linear combination of input variables. Without a prior knowledge of the distribution of the training data set, the proposed mapping-constrained agglomerative clustering algorithm is able to reveal the true number of clusters and simultaneously estimate the centers and variances of the clusters for constructing an initial SANFIS structure in a single pass. Next, a fast linear/nonlinear parameter optimization algorithm is performed to further accelerate the learning convergence and improve the system performance.

We consider the problem of multimedia synchronization in a Web environment. The workload generated by the multimedia server during a Web session exhibits variations that are quite different from the traffic fluctuation offered by a single media stream, e.g., a variable bit rate (VBR) video. We propose a set of parameters that can be used to characterize the workload generated by the multimedia server in a Web-type browsing environment. The workload characterization scheme is subsequently used in designing a server-based synchronization scheme. The problem of scheduling multimedia information to ensure media synchronization in a Web environment is identified as a multicriteria scheduling problem, which is NP-hard. The ability of fuzzy control to deal with multivariables makes it a good alternative for the multicriteria scheduling problem considered. Consequently, we propose a neuro-fuzzy scheduler (NFS) that makes an intelligent compromise among multicriteria by properly combining some scheduling heuristics. Performance of the NFS is compared with several known heuristics and a branch and bound algorithm. The results show that the proposed NFS ran dynamically adjust to the varying workload quite well.

Controlling autonomous underwater vehicles (AUVs) in an uncertain and unstructured environment presents many challenging control problems. Model-based control strategies have been used with limited success. The paper presents an online self-organizing neuro-fuzzy control that serves as a better alternative control scheme in controlling AUVs. The proposed self-organizing neuro-fuzzy controller is a six-layer feedforward neural network that is capable of self-constructing and self-restructuring its internal node connectivity and learning the parameters of each node based on incoming training data. Computer simulations have been conducted to validate the performance of the proposed neuro-fuzzy controller and an experimental verification has been scheduled to verify if on ODIN, an autonomous underwater vehicle developed at the University of Hawaii.

The control of underwater robots presents a number of unique and formidable challenges. Underwater robot dynamics are highly nonlinear, coupled, and time-varying, and subject to hydrodynamic uncertainties and external disturbances such as current. Unlike land mobile robots, underwater robots cannot use GPS. Most popular underwater positioning sensors are sonar-based, such as long-base line. However, autonomous processing of sonar measurements is plagued by noise, drop-outs, missed detection, false reading, poor resolution, etc. The paper presents a new adaptive control of underwater robots with sonar-based position measurements. Experimental results show robustness of the control system in the presence of unmodelled dynamics and various noise.

Presents an online self-adaptive neuro-fuzzy control that serves as a better alternative control scheme in controlling autonomous underwater vehicles (AUVs) in an uncertain and unstructured environment. The proposed self-adaptive neuro-fuzzy controller is a five-layer feedforward neural network that implements fuzzy basis function (FBF) expansions and is capable of self-constructing and self-restructuring its internal node connectivity and learning the parameters of each node based on incoming training data. Computer simulations have been conducted to validate the performance of the proposed neuro-fuzzy controller and an experimental verification has been scheduled to verify it on ODIN, an autonomous underwater vehicle developed at the University of Hawaii.

Focuses on the development of a learning-based heuristic for scheduling heterogeneous machines. Although list scheduling methods have been widely used for a large class of scheduling problems, including the heterogeneous machine scheduling problem, they involve designing priority rules, which usually require a fair amount of insights on the characteristics of the problem to be solved. Instead of elaborate design of priority rules in a single step, we propose an iterative list scheduling process, which refines priority rules while generating a number of schedules. The proposed iterative list scheduling is formulated as a reinforcement learning problem, with states and actions defined in list scheduling. Due to the large number of possible states, reinforcement learning algorithms which use value functions in constructing an optimal policy may not be suitable for scheduling problems. Thus, to directly work with policies rather than the values of states, we propose genetic reinforcement learning (GRL), in which the policies of reinforcement learning are encoded into the chromosomes of genetic algorithms and a near-optimal policy is searched for by genetic algorithms. A GRL-based scheduler, called evolutionary intracell scheduler (EVIS), has been developed and applied to various scheduling problems such as the heterogeneous machine scheduling, the processor scheduling, the job-shop scheduling, the flow-shop scheduling, and the open-shop scheduling problems. The proposed model of EVIS, which has a linear order of population-fitness convergence, is verified by computer experiments. Even without fine tuning EVIS, the quality of solutions achieved by EVIS is comparable to that of problem-tailored heuristics for most of the problem instances.

Traditionally, design for assembly is done during the detailed design phase. A designer first maps a set of design requirements into a set of components or subassemblies that can satisfy the given set of requirements. The components and subassemblies are then examined individually to determine whether they conform to the principles of design for assembly. Usually, local changes are performed so that the resultant components/subassemblies are better for assembly. In this paper, we propose to bring the design for assembly analysis into an even earlier phase-that of the conceptual design phase. We argue that by incorporating the design for assembly analysis at the conceptual design phase, we can achieve a more substantial savings as compared to the savings obtained when the design for assembly analysis is only performed as late as the detailed design phase. The basic idea is to select a combination of design concepts (previously stored in a library) such that together they can achieve the stated functional requirements (in the form of state transitional graph) at the minimum cost for assembly. This problem of selecting the right combination of design concepts is reduced to the well-known set covering problem. With this reduction, many existing graph algorithms can be applied to aid in the design for assembly analysis.

Concerns the development of a learning-based heuristic for scheduling heterogeneous machines. List scheduling methods are flexible enough to be used for a large class of problems, including the heterogeneous machine problem. However, designing a priority rule requires insight into the characteristics of the problem. We propose the iterative list scheduling, which refines priority rules while generating a number of schedules. We also show that the iterative list scheduling can be formulated as a reinforcement learning problem, defining states and actions. Due to the large number of possible states, reinforcement learning algorithms which use value functions in constructing an optimal policy may not be suitable for scheduling problems. Encoding the policies of reinforcement learning into genetic algorithms leads to the genetic reinforcement learning (GRL), which directly works with the policies rather than the values of states. A GRL-based scheduler, EVIS (Evolutionary Intracell Scheduler), has been applied to problems such as the heterogeneous machine scheduling, the job-shop scheduling, the flow-shop scheduling, and the open-shop scheduling problems. The proposed model of EVIS, which has the linear order of population-fitness convergence, was verified with computer experiments. Even without fine tuning of EVIS, the quality of solutions found by EVIS was comparable to that of problem-tailored heuristics for most of the problem instances.

This paper presents a systematic procedure for generating the goal region of a mating action from a model of assemblies. The goal region of a mating action is defined as the acceptable destination of the moving object and is used to identify the successful situation of the mating action. In this paper, goal regions are constructed by using the mating features and the constraint types residing in the model of assemblies. The mating features identify the important variables between which the interdependencies are considered, and the constraint types identify the necessary constraints that mating features cannot provide. An analytical solution for C-space interior is developed to construct the goal region from 2D features. The effects of interference and fine-motion planning on success probabilities are also taken into consideration to define theoretical goal regions; goal regions are also subject to uncertainties. An approach that shrinks the nominal boundary of a goal region is also proposed to compute the expectation of success probabilities.

With the increased competition in today's world market, emphasis has been on the ability to shift from an existing paradigm to a new paradigm so as to create new opportunities and to gain new market. A successful paradigm shift is dependent on two factors: (1) the ability to pinpoint the inherent weaknesses in the existing paradigm, (2) the ability to find a paradigm that can replace the old paradigm. In this paper, we show how the integrated feedback approach is able to address these two concerns. The integrated feedback approach was proposed to integrate the design phase with the downstream activities so as to achieve a design that is better for assembly. The approach operates in two phases: an evaluation phase and a redesign suggestion generation phase. A number of objective criteria have been proposed to evaluate a given design from the functional perspective, from the assembly plan perspective, and from the tolerance perspective. Through the evaluation process, weaknesses in the design are identified and techniques for generating feasible redesign suggestions are examined. By encouraging greater participation from the designer, a systematic aid to paradigm shifting can be obtained. A prototype system implementing the integrated feedback approach has been developed on a Sun Sparcstation with graphics simulation on a Silicon Graphics Iris workstation. A real life product, the telephone, is used as an illustration.

This paper focuses on the development of a learning-based heuristic for the machine scheduling problem, which automatically captures the search control knowledge or the common features of good schedules while generating a number of schedules. Defining states and actions of the machine shop, the machine scheduling problem is transformed into a problem of reinforcement learning (RL) in which a learner or a scheduler will learn to select the right action at each state of the machine shop, using the reward from a schedule evaluator for executing the action. Implementing the proposed reinforcement learning with a genetic algorithm results in the genetic reinforcement learning (GRL) approach to the machine scheduling problem. Although the learning-based heuristic has the overhead of acquiring knowledge on the problem, it can be easily adapted for a wide variety of machine scheduling problems due to the weak dependence on the problem structures and objectives. A GRL-based scheduler, called EVIS (Evolutionary Intracell Scheduler), has been developed and applied to various classes of machine scheduling problems, such as the job-shop scheduling, the flow-shop scheduling and the open-shop scheduling problems, and even the processor scheduling problem, the performance evaluation of EVIS with a number of different problem instances has shown that the learning-based heuristic is robust and its performance is comparable with that of other problem-specific heuristics or search-oriented heuristics in the quality of solutions.

Scanlines, which are specifically processed rows or columns of a digital camera image, are used to develop a very fast visual tracking algorithm. The bottleneck of any visual robot tracking system is the large amount of data processed by the vision system in order to determine the pose (position and orientation) of an object moving in space. Scanlines provide a means of using minimal (if not the minimum) amount of information necessary for pose determination; thereby, increasing the sensor response time and the tracking speed. The scanline-based algorithm is developed to track the 6-dimensional pose of regular polygonal objects such as squares, triangles, and circles. Experimental verifications are provided for a single-camera and a dual-camera system.

The idea of a Hopfield network is based on the Ising spin glass model in which each spin has only two possible states: up and down. By introducing stochastic factors into this network and performing a simulated annealing process on it, it becomes a Boltzmann machine which can escape from local minimum states to achieve the global minimum. This paper generalizes the above ideas to multi-value case based on the XY spin glass model in which each spin can be in any direction in a plane. Simply using the gradient descent method and the analog Hopfield network, two different analog connectionist structures and their corresponding evolving rules are first designed to transform the XY spin glass model to distributed computational models. These two analog computational models are single-layered connectionist structures and multi-layered Hopfield analog networks. The latter network eases the node (neuron) computational requirement of the former at the expense of more neurons and connections. With the proposed evolving rules, the proposed models evolve according to a predefined Hamiltonian (energy function) which will decrease until it reaches a (perhaps local) minimum. Since these two structures can easily get stuck in local minima, a multi-valued Boltzmann machine is proposed which adopts the discrete planar spin glass model for the local minimum problem. Each neuron in the multi-valued Boltzmann machine can only take n discrete directions (states). The stochastic simulated annealing method is introduced to the evolving rules of the multi-valued Boltzmann machine to solve the local minimum problem. The multi-valued Boltzmann machine can be applied to the mobile robot navigation problem by defining proper artificial magnetic field on the traverse terrain. This new artificial magnetic field approach for the mobile robot navigation problem has shown to have several advantages over existing graph search and potential field techniques.>

This paper proposes a fuzzy model-reference adaptive control (Fuzzy-MRAC) to deal with controlling a plant with unknown parameters which are dependent on known variables. The proposed method uses the fuzzy basis function expansion (FBFE) to represent the unknown parameters and change the identification problem from identifying the original unknown parameters to identifying the coefficients of the FBFE. That is, the dependency property of unknown parameters is absorbed into the fuzzy basis functions and their linear combination coefficients. This data representation is substantiated by the Stone Weierstrass theorem which indicates that any continuous function can be represented by the FBFE. With the aid of the FBFE, the unknown parameters can be estimated more precisely and better performance can be expected from the fuzzy-MRAC than the traditional MRAC. Furthermore, the adaptation scheme of the proposed fuzzy-MRAC is based on both the tracking error and the prediction error. Combining these two sources of error information, the proposed fuzzy-MRAC will provide more adaptation power than a traditional adaptive control. Since the proposed fuzzy-MRAC can be considered as an extension of the traditional MRAC, its stability and convergence properties are preserved. Computer simulations were conducted to show the validity and the performance of the proposed fuzzy-MRAC and its improvements over the traditional MRAC.

Develops a new method for automatic generation of error recovery procedures in the assembly workcell. Current reactive systems have integrated planning and learning capabilities to allow them to augment their store of reactive behaviors whenever they are forced to plan. The cycle of evaluation and reaction used by these systems implicitly detects and corrects any errors made in prior behavior execution. By capitalizing on this analogy to error recovery, the authors are able to gain the benefits of a reactive system for use in error recovery while minimizing the perception and evaluation burden that is inherent in those approaches. The authors present a system that uses the new learning reactive paradigm to quickly correct known errors and autonomously learn to recover new errors without human intervention.>

This paper focuses on the heuristic hybridization and the genetic search as a methodology to develop a computationally efficient heuristic for the job-shop scheduling problem (JSP). In order to adapt the JSP to a genetic algorithm (GA), the ASGPL (Active-Schedule Generation with a Priority-List) algorithm with a hopping scheme was proposed, and using a GA, an iterative schedule improvement procedure called EVIS (Evolutionary Intracell Scheduler) was designed. The genetic search in EVIS was parallelized with a model of subpopulations and migration. Without implementing any problem-tailored heuristic for the job-shop scheduling problem, EVIS was able to find optimal solutions to a number of different problem instances in reasonable computation time.>

A dual phase robot tracking and control strategy is proposed where a global trajectory of the robot is initially estimated in phase one using absolute location information provided by fixed, "far-away" sensors and then in phase two, a fine-motion reactive tracker is invoked to compensate for the local deviations about the globally estimated trajectory from phase one. This dual phase tracking strategy reduces both the tracking error and the capture time of the target by the robot, compared to the operation of either mode of tracking (global or local) independently. The sensory information provided by the multiple sensors, disparate or redundant, is fused together to increase the reliability of the system.>

An assembly planning system that takes the CAD model description of a product as input and automatically generates executable plans not only can automate assembly processes, but also can provide assembly properties of the product through the simulation of all possible assembly plans. Yet, to achieve such automation, the necessary information required in describing the executable action must be automatically generated from the model of a product so that the effective simulation of the assembly process is possible. In this paper, the generation of the destination of a mating action in the presence of uncertainty is presented. When a mating action in an assembly process is required to be executed, the action description developed from the model of a product usually only specifies the mating properties of the action, like "peg in hole". Thus, with the purpose of effective simulation, a set of locations must be derived from the mating property to identify the acceptable region of the goal of the action such that the uncertainties occurring in the representation of object dimensions, action motions, and sensory information can be incorporated in the assembly process. In the authors' previous work, a systematic procedure has been proposed to automatically generate such a goal region. However, goal regions can only provide the information of the acceptable goals of the corresponding moving objects. In specifying a goal in a planning process or in the description of an executable action, a point is required to define the destination of a mating action in order that the system can know how to perform the action. In this paper, with the concept of reliability indices, the destination of a goal region, which is assumed to be a convex polygon, is considered to be the point from which the minimal distance to the edges of the polygon is the maximum, and then the destination can yield the maximal estimated success probability on executing the mating action. An algorithm with the time complexity of O(NlogN) is proposed to find the point from which the minimal distance to the edges of the polygon is the maximum.>

This paper proposes a reinforcement neural-network-based fuzzy logic control system (RNN-FLCS) for solving various reinforcement learning problems. The proposed RNN-FLCS is constructed by integrating two neural-network-based fuzzy logic controllers (NN-FLC's), each of which is a connectionist model with a feedforward multilayered network developed for the realization of a fuzzy logic controller. One NN-FLC performs as a fuzzy predictor, and the other as a fuzzy controller. Using the temporal difference prediction method, the fuzzy predictor can predict the external reinforcement signal and provide a more informative internal reinforcement signal to the fuzzy controller. The fuzzy controller performs a stochastic exploratory algorithm to adapt itself according to the internal reinforcement signal. During the learning process, both structure learning and parameter learning are performed simultaneously in the two NN-FLC's using the fuzzy similarity measure. The proposed RNN-FLCS can construct a fuzzy logic control and decision-making system automatically and dynamically through a reward/penalty signal or through very simple fuzzy information feedback such as "high," "too high," "low," and "too low." The proposed RNN-FLCS is best applied to the learning environment, where obtaining exact training data is expensive. It also preserves the advantages of the original NN-FLC, such as the ability to find proper network structure and parameters simultaneously and dynamically and to avoid the rule-matching time of the inference engine. Computer simulations were conducted to illustrate its performance and applicability.>

The authors examine issues involved in integrating the design level and the assembly planning level with a feedback loop. The integration is performed in two stages. The first stage focuses on the evaluation of an assembly plan. Evaluation criteria that can pinpoint areas which need redesign are defined. The second stage is to use the evaluation results to come up with the actual redesign. Algorithms are developed for performing evaluation of assembly plans. From the evaluation results, means of generating hints for redesign are discussed. The hints are then processed and calls are made to the redesign operators to perform the actual redesign of components. The integrated design-planning system has the ability to identify parts that need redesign and the ability to come up with feasible redesign options in polynomial time.>

A systematic methodology of manipulating and propagating spatial uncertainties in the form of homogeneous transforms and in a probabilistic sense is presented. Uncertainties are represented by covariance matrices and the manipulation of uncertainties focuses on the spatial uncertainty propagation and the uncertainty fusion. To integrate the uncertainty information into a task plan that consists of a sequence of primitive actions, the propagation of uncertainty before and after a primitive action such as moving action, perception action, and contact action is developed. A simple and optimal solution for maintaining the consistency in the world state is proposed for perception actions. To determine the applicability of an action, forward propagation and backward propagation are proposed to verify the success of an action in the presence of uncertainties. It is shown that the backward propagation method can be used to determine an admissible set of an action with a specified acceptable success confidence and/or to efficiently apply perception actions to reduce the uncertainty.>

A generic framework that employs a sensor-independent, feature-based relational model, called the geometric feature relation graph (GFRG), to represent information acquired by various sensors is proposed. A GFRG consists of nodes representing 3-D geometric features and arcs denoting spatial relations between features. Sensor fusion is then accomplished by integrating multiple irregular GFRGs constructed by various sensors into a regular GFRG. A procedure is presented for identifying corresponding measurements of features in the presence of sensory uncertainty with geometric and topological constraints, and a nonlinear programming formulation for maintaining consistency in a network of relations is proposed. The Dempster-Shafer theory of belief functions is applied to make topological constraints in achieving reliable identification. Optimal and heuristic solutions for maintaining consistency are presented. The heuristic solution has near-optimal performance with less computational complexity. Computer simulations verify the validity and performance of the framework.>

An approach to strategic recognition of objects using multiple sensors based on the candidate discriminating graph (CADIG) is presented. A CADIG represents the candidates of an unknown object and the complete discriminating relations between the candidates in terms of relevant discriminators (geometric features). Strategic recognition is decomposed into two interacting procedures: the information acknowledgement procedure (IAP) and the sensory acquisition procedure (SAP). The IAP identifies the critical information for recognition as a set of discriminators from the CADIG and receives sensory examinations of these discriminators to eliminate invalid candidates from the CADIG. The SAP coordinates multiple sensors to examine the critical information identified in the IAP. This coordination is formulated as a constraint satisfaction problem and solved by the backtracking algorithm. The unknown object is recognized through iterations of the IAP and SAP until there is only one candidate left in the CADIG. The IAP and SAP are further integrated to achieve the optimal strategic recognition of objects.>

A framework of knowledge-based assembly planning for the automatic generation of assembly plans from the CAD model of an assembly is presented. The knowledge about assembly structure, precedence constraints, and resource constraints is represented using predicate calculus, and it forms the static knowledge database. Production rules are used to generate assembly plans. A graph search mechanism is used to search for the optimal assembly plan. To test the proposed approach, a prototype system has been developed. It can read in the CAD data of a product and the resource information of an assembly cell and automatically generate an optimal assembly plan based on the selection criteria specified by the user of the system.>

Uncertainties are represented in the form of homogeneous transforms, and the manipulation of uncertainties is focused on the spatial uncertainty propagation and the uncertainty fusion. In order to integrate the uncertainty information into a task plan which consists of a sequence of primitive actions, the propagation of uncertainty before and after a primitive action, such as moving, perception, or contact action, has been developed. A simple and optimal solution for the consistency problem is proposed for perception actions. Using conditional probability and the evidence collecting technique, the correlation between motion parameters, when a contact occurs, can also be taken into account. To determine the applicability of an action, forward propagation and backward propagation are proposed to verify the success of the action in the presence of uncertainties. This backward uncertainty propagation method can be used to determine the admissible set of an action according to an acceptable success confidence.>

A general neural-network (connectionist) model for fuzzy logic control and decision systems is proposed. This connectionist model, in the form of feedforward multilayer net, combines the idea of fuzzy logic controller and neural-network structure and learning abilities into an integrated neural-network-based fuzzy logic control and decision system. A fuzzy logic control decision network is constructed automatically by learning the training examples itself. By combining both unsupervised (self-organized) and supervised learning schemes, the learning speed converges much faster than the original backpropagation learning algorithm. The connectionist structure avoids the rule-matching time of the inference engine in the traditional fuzzy logic system. Two examples are presented to illustrate the performance and applicability of the proposed model.>

The authors develop methodologies for the automatic selection of image features to be used to visually control the relative position and orientation (pose) between the end-effector of an eye-in-hand robot and a workpiece. A resolved motion rate control scheme is used to update the robot's pose based on the position of three features in the camera's image. The selection of these three features depends on a blend of image recognition and control criteria. The image recognition criteria include feature robustness, completeness, cost of feature extraction, and feature uniqueness. The control criteria include system observability, controllability, and sensitivity. A weighted criteria function is used to select the combination of image features that provides the best control of the end-effector of a general six-degrees-of-freedom manipulator. Both computer simulations and laboratory experiments on a PUMA robot arm were conducted to verify the performance of the feature-selection criteria.>

The commenter indicates that in the above-mentioned paper (see ibid., vol.5, no.5, p.569-82 (1989)) the proposed pipelined array architecture for the mixed-radix conversion problem is not as efficient and suitable for VLSI implementation as claimed. The commenter identifies the shortcomings of the design and then gives an efficient systolic/wavefront array that requires fewer hardware resources. The authors reply that this is another valid design for the mixed-radix conversion problem that avoids broadcasting; however, the triangular array of buffers is still required in the design for the data-format conversion, and this problem is not addressed. Since a semisystolic design was not given, the comparison between the original design and the semisystolic design in terms of buffers is premature.>

Efficient parallel algorithms for computing the kinematics, dynamics, and Jacobian of manipulators and their corresponding inverses are discussed and analyzed, and their characteristics are identified based on the type and degree of parallelism, uniformity of the operations, fundamental operations, data dependencies, and communication requirements. Most of the algorithms for robotic computations possess highly regular properties and some common structures, especially the linear recursive structure. They are well-suited to be implemented on a single-instruction-stream-multiple-data-stream (SIMD) computer with reconfigurable interconnection networks. A reconfigurable dual-network SIMD machine with internal direct feedback that best matches these characteristics has been designed. To achieve high efficiency in the computation of robotics algorithms on the proposed parallel machine, a generalized cube interconnection network is proposed. A centralized network switch control scheme is developed to support the pipeline timing of this machine. To maintain high reliability in the overall system, a fault-tolerant generalized cube network is designed to improve the original network.>

An automatic assembly planning system which takes the CAD description of a product as input and automatically generates an assembly plan subject to the resource constraint of a given assembly cell is presented. The system improves the flexibility and productivity of FMSs and is composed of five modules: world database, simulated world model, knowledge acquisition mechanism, planning knowledge base, and assembly planner. The world database contains the information from a designer which provides the information about the product and the assembly cell. The knowledge acquisition mechanism acquires knowledge necessary for assembly planning, that is, the precedence knowledge among assembly tasks, the fixture specification for the assembly, and the tool requirement for the assembly tasks. The acquired knowledge forms the planning knowledge base. The simulated world model keeps track of the current state of the assembly world. In the initial state, all the components are separated, while in the final state, all the components are assembled. The assembly planner is made up of a set of production rules which models the effects of real assembly tasks. By repeatedly applying these production rules to the simulated world state, the planner transforms the initial state into the final state. The set of rules applied forms the assembly plan. Examples are given.>

An adaptive method for visually tracking a known moving object with a single mobile camera is described. The method differs from previous methods of motion estimation in that both the camera and the object are moving. The objective is to predict the location of features of the object on the image plane based on past observations and past control inputs and then to determine an optimal control input that will move the camera so that the image features align with their desired positions. A resolved motion rate control structure is used to control the relative position and orientation between the camera and the object. A geometric model of the camera is used to determine the linear differential transformation from image features to camera position and orientation. To adjust for modeling errors and system nonlinearities, a self-tuning adaptive controller is used to update the transformation and compute the optimal control. Computer simulations were conducted to verify the performance of the adaptive feature prediction and control.>

Two efficient mapping algorithms are presented for scheduling the execution of a robot inverse dynamics computation using a p-processor multiprocessor system where p is the number of identical processors. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. A minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem is formulated as a combination of a graph partitioning and scheduling problem; both are known to be NP-complete. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms.>

The authors investigate the selection of image features to be used to control visually the position and orientation (pose) of the end-effector of an eye-in-hand robot relative to a workpiece. A resolved-motion-rate control scheme is used to update the robot's pose on the basis of the position of three features in the camera's image. The selection of these three features depends on the condition and sensitivity of the differential relationship between the image features and the control parameters. Both computer simulations and laboratory experiments on a PUMA robot arm were conducted to verify the performance of the feature selection criteria. Experimentally, the PUMA robot arm, with a CCD (charged-coupled device) camera mounted on its end effector, was able to track a randomly moving carburetor gasket with a visual feedback cycle time of 70 ms.>

The authors discuss the representation and acquisition of the precedence knowledge of an assembly, which plays an important role in the generation of assembly sequences and the planning of assembly. An efficient and complete symbolic representation has been developed to express the precedence knowledge clearly and precisely. This symbolic representation makes it possible to perform reasoning and manipulation of the precedence knowledge. Furthermore, the representation is complete in the sense that it can represent the assembly precedence knowledge as well as the disassembly precedence knowledge and these two forms of knowledge can be transformed from one to another. A geometric mating graph is developed to include all the necessary geometric and topological information for the precedence knowledge acquisition. Two algorithms are developed to obtain the precedence knowledge from the geometric mating graph systematically. The disassembly precedence knowledge thus obtained is equivalent to the assembly precedence knowledge and can be used to generate all the possible sets of assembly sequences.>

The authors present an efficient algorithm for mapping m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p homogeneous processors with processor and communication costs to achieve minimum computation time. Minimax optimization is performed on the objective function to obtain the best mapping. Experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithm. Computer simulation and experimental results are compared and discussed.>

The authors present the design of a two-level macro-pipelined VLSI array architecture for the real-time computation of the exact solution of the manipulator pseudo-inverse Jacobian using the Decell algorithm in the residue arithmetic system. The first-level arrays are asynchronous data-driven, wave-front-like arrays and perform matrix multiplication, matrix diagonal addition, and trace computations in the Decel algorithm. A pool of the first-level arrays is then configured into a second-level macro-pipeline with outputs of one array acting as inputs to another array in the pipe. The pipelined time of the proposed two-level pipelined array architecture has a computational order of 0(n+2p-1), which is the same computational complexity order as that of the evaluation of a matrix product in an ordinary wavefront array. For a 12 degree-of-freedom redundant robot, a pipelined time of 6.975 mu s is achievable with current VLSI custom design technology.>

The real-time computation of the Jacobian that relates the manipulator joint velocities to the linear and angular velocities of the manipulator end-effector is pursued. Since the Jacobian can be expressed in the form of a first-order linear recurrence, the time lower bound for computing the Jacobian can be proved to be of order O(N) on uniprocessor computers and of order O(log/sub 2/ N) on both single-instruction-stream-multiple-data-stream (SIMD) and VLSI pipelined parallel processors, where N is the number of links of the manipulator. To achieve the lower bound, the authors developed a generalized-k method for uniprocessor computers, a parallel forward and backward recursive doubling algorithm (PFABRD) for SIMD computers, and a parallel systolic architecture for VLSI pipelines. All the methods are capable of computing the Jacobian at any desired reference coordinate frame k from the base coordinate frame to the end-effector coordinate frame. The computational effort in terms of floating-point operations is minimal when k is in the range (4,N-3) for the generalized-k method, and k=(N+1)/2 for both the PFABRD algorithm and the parallel pipeline.>

The use of residue arithmetic for the exact computation of the manipulator pseudoinverse Jacobian, to obviate the roundoff errors normally associated with the computations, is considered. A two-level macropipelined residue arithmetic array architecture implementing Decell's pseudoinverse algorithm has been developed to overcome the ill-conditioned problem of the pseudoinverse computation. The Decell algorithm is suitable for VLSI array implementation to achieve the real-time computation requirement. The first-level arrays are data-driven, wavefront-like arrays and perform the matrix multiplications, matrix diagonal additions, and trace computations. A pool of the first-level arrays are configured into a second-level macro-pipeline with outputs of one array acting as inputs to another array in the pipe. The proposed architecture can calculate the pseudoinverse Jacobian with a pipelined time in the same computational complexity order as evaluating a matrix product in a wavefront array.>

The problem of scheduling an inverse dynamics computation consisting of m computational modules to be executed on a multiprocessor system consisting of p identical homogeneous processors to achieve a minimum-scheduled length is presented. To achieve the minimum computation time, the Newton-Euler equations of motion are expressed in the homogeneous linear recurrence form, which results in achieving maximum parallelism. To speed up the searching for a solution, a heuristic search algorithm called dynamical highest level first/most immediate successors first (DHLF/MISF) is proposed to find a fast but suboptimal schedule. For an optimal schedule, the minimum-scheduled-length problem can be solved by a state-space search method. An objective function is defined in terms of the task execution time, and the optimization of the objective function is based on the minimax of the execution time. The proposed optimization algorithm solves the minimum-scheduled-length problem in pseudopolynomial time and can be used to solve various large-scale problems in a reasonable time.>

To investigate real-time Jacobian computation, the authors determine an optimal reference coordinate frame k for efficient computation in uniprocessor computers, extend the concept to be computed by parallel SIMD (single-instruction, multiple-data-stream) computers, and design two VLSI systolic pipelined architectures. The first is a linear VLSI pipe, which uses the least number of modular processors; however, 3N FLOPS (floating-point operations per second) are needed to compute the Jacobian. The second one is a parallel VLSI pipe, which just takes 3 FLOPS to compute the Jacobian.>

An approach that utilizes the geometric information about the mating parts in generating and synthesizing the C-frame and the compliance-selection vector which are needed at every sampling instant for hybrid position/force control scheme in an insertion task, is presented. A geometric modeling system is used to model the mating objects involved in the insertion task. From the geometric model of the objects and the nominal position-trajectory of the task, a set of cut-planes of the mating objects perpendicular to the insertion direction can be obtained. Due to the uncertainties inherent in working with real-world objects, and the limited position accuracy of the manipulator, an uncertainty model is incorporated into the cut-planes to reflect the position and orientation uncertainties of the C-frame. This approach reduces a difficult three-dimensional problem into a set of two-dimensional problems and will successfully complete the task even in the presence of position and orientation uncertainties.>

The problem of scheduling the robot inverse dynamics computation consisting of m computational modules to be executed on a multiprocessor system consisting of p identical homogeneous processors to achieve a minimum-schedule length is examined. This scheduling problem is known to be NP-complete. To achieve the minimum computation time, the Newton-Euler equations of motion are expressed in the homogeneous linear recurrence form that results in achieving maximum parallelism. To speed up the searching for a solution, a heuristic search algorithm called dynamical highest-level-first/most-immediate-successors-first (DHLF/MISF) is proposed to find a fast but suboptimal schedule. For an optimal schedule the minimum-schedule-length problem can be solved by a state-space search method, the A* algorithm coupled with an efficient heuristic function derived from the Fernandez and Bussell bound.>

Two efficient parallel algorithms for computing the forward dynamics for real-time simulation were developed for implementation on a single-instruction multiple-data-stream (SIMD) computer with n processors, where n is the number of degrees of freedom of the manipulator. The first parallel algorithm, based on the composite rigid-body method, generates the inertia matrix using the parallel Newton-Euler algorithm, the parallel linear recurrence algorithm, and the modified row-sweep algorithm, and then inverts the inertia matrix to obtain the joint acceleration vector at time t. The time complexity of this parallel algorithm is of the order O(n/sup 2/) with O(n) processors. The second parallel algorithm, based on the conjugate gradient method, computes the joint acceleration with a time complexity of O(n) for multiplication operation and O(n log/sub 2/n) for addition operation. The interprocessor communication problem for the implementation of the proposed parallel algorithms on SIMD machines is also discussed and analyzed.>

This paper presents a graph-theoretic approach to determining an optimal task (or routing) assignment of p autonomous vehicles (AVs) among m workstations in a flexible manufacturing system (FMS) to minimize the assignment completion time, as well as to achieve load balancing among the AVs. The task assignment problem is equivalent to an optimal routing assignment of destinating the m workstations to the p autonomous vehicles. A cost function is defined in terms of job execution time and traveling time performed by the AVs. Optimization of the cost function is based on the minimax of the job execution time and the minimization of max-min of the traveling time. The optimal task assignment problem is solved by a state-space search method - the A* algorithm. If potential collisions exist on the optimal routing assignment, then dynamic collision detection must be carried out during the state-space search to guarantee an optimal collision-free routing assignment. This collision avoidance can be easily taken care of by using an ordered collision matrix to adjust the arrival time of every AV arriving at the center of the "collision zone" if a potential collision is detected. Again the A* search strategy can be utilized to obtain an optimal collision-free routing assignment with load balancing.

A non-contact, full field vision technique is presented to determine the surface roughness values. The variation of extracted texture features, roughness (Frgh), on the arithmetic average roughness (Ra) of the test surface is studied. The effects of magnification and aperture size of the imaging system on the extracted surface features are also examined. The vision system offers a fast and accurate method for the on-line automated surface roughness inspection of machined components.

Computing the robot forward dynamics is important for real-time computer simulation of robot arm motion. Two efficient parallel algorithms for computing the forward dynamics for robot arm simulation were developed to be implemented on an SIMD computer with n processors, where n is the number of degrees-of-freedom of the manipulator. The first parallel algorithm, based on the Composite Rigid-Body method, generates the inertia matrix using the parallel Newton-Euler algorithm, the parallel linear recurrence algorithm, and the row-sweep algorithm, and then inverts the inertia matrix to obtain the joint acceleration vector desired at time t. The second parallel algorithm, based on the conjugate gradient method, computes the joint accelerations with a time complexity of O(n) for multiplication operation and O(nlogn) for addition operation. The proposed parallel computation results are compared with the existing methods.

A graph-theoretic approach for determining an optimal task (or routing) assignment of p autonomous vehicles (AV's) among m workstations in a flexible manufacturing system which both minimizes the assignment completion time and balances the load among the AV's is presented. This task assignment problem is equivalent to an optimal routing assignmenl of destinating the m workstations to the p autonomous vehicles. A cost function is defined in terms of the job execution time and the traveling time performed by the AV's. Optimization of the objective function is based on the minimax of the job execution time and the minimization of max-min of the traveling time. This optimal task assignment problem is known to be NP-complete. Thus the problem is solved by a state-space search method-the A algorithm. The A algorithm is a classical minimum-cost graph search method. It is guaranteed to find an optimal solution if the evaluation function which utilizes the heuristic information about the problem for speeding up the search is properly defined. If potential collisions exist on the optimal routing assignment, then dynamic collision detection must be carried out during the state-space search to guarantee an optimal collision-free routing assignment. This collision avoidance can be taken care of by using an ordered collision matrix to adjust the arrival time of every AV arriving at the center of the "collision zone" if a potential collision is detected. Again, the A search strategy can be utilized to obtain an optimal collision-free routing assignment, and the optimal assignment obtained also achieves load balancing of the p AV's.

A cost-effective coordinate rotation digital computer (CORDIC) architecture is described for the computation of inverse kinematic position solution based on a functional decomposition of the closed-form joint equations. The functional decomposition shows a limited amount of parallelism with a large amount of sequentialism in the flow of computation and data dependencies and reveals the requirement for computing a large set of elementary operations: multiplications, additions, divisions, square roots, trigonometric functions and their inverse. However, these elementary operations, in general, cannot be efficiently computed in general-purpose uniprocessor computers. The CORDIC algorithms are the natural candidates for efficiently computing these elementary operations and the interconnection of these CORDIC processors to exploit the great potential of pipelining provides a better solution for computing the inverse kinematic position solution. The functional decomposition of the inverse kinematic position solution into a set of computational tasks can be represented as a directed task graph. The inclusion of input data modifies the task graph to an acyclic data dependency graph (ADDG). The nodes of the ADDG correspond to the computational modules, each of which can be realized by a CORDIC processor. The operands or data move along the edges, each of which connects a pair of nodes. Due to different paths and computation time for each CORDIC processor, operands may arrive at multi-input modules at different arrival time, causing a longer pipelined time. Delay buffers may be inserted at various paths to achieve a balanced ADDG. The optimal buffer assignment problem is reduced to an integer linear optimization problem which can be solved easily by computers. The realization of the balanced ADDG results in a maximum pipelined CORDIC architecture with a minimum number of delay buffer stages for the computation of inverse kinematic position solution.

An approach to collision-free motion planning of two moving robots in a common workspace is presented. Each robot is represented by a sphere containing the wrist and the manipulator hand. The results from a strictly straight line trajectory planning method are utilized for planning a path avoiding potential collisions. Due to the distinct nature of the potential collisions between the two moving robots, a new classification of path requirement situations is presented and utilized for planning a collision-free path. Notions of collision map and time scheduling are developed and applied for realizing a collision-free motion planning. A procedure is developed for the time scheduling of the straight line trajectory. An example is shown for the time scheduling of the trajectory, which shows the significance of the proposed approach in collision-free motion planning of the two moving robots.

The development of generalized d'Alembert equations of motion for application to robot manipulators with rotary joints is presented. These equations result in an efficient and explicit set of second-order nonlinear differential equations with vector cross-product terms in symbolic form. They give well-"structured" equations of motion suitable for state-space control analysis. The interaction and coupling reaction forces/torques between the neighboring joints of a manipulator can be easily identified as coming from the translational and rotational effects of the links. An empirical method for obtaining a simplified dynamic model is discussed together with the computational complexity of the dynamic coefficients in the equations of motion. The dynamic equations of the first three links of a Pumas robot are derived to illustrate the simplicity of the generalized d'Alembert equations of motion.

This paper shows that the time lower bound of computing the inverse dynamics of an n-link robot manipulator parallelly using p processors is O(k1[n/p] + k2[log2p]), where k1and k2are constants. A novel parallel algorithm for computing the inverse dynamics using the Newton-Euler equations of motion was developed to be implemented on an SIMD computer with p processors to achieve the time lower bound. When p = n, the proposed parallel algorithm achieves the Minsky's time lower bound O([log2n]) [22], which is the conjecture of parallel evaluation. The proposed p-fold parallel algorithm can be best described as consisting of p-parallel blocks with pipelined elements within each parallel block. The results from the computations in the p blocks form a new homogeneous linear recurrence of size p, which can be computed using the recursive doubling algorithm. A modified inverse perfect shuffle interconnection scheme was suggested to interconnect the p processors. Furthermore, the proposed parallel algorithm is susceptible to a systolic pipelined architecture, requiring three floating-point operations (Flops) per complete set of joint torques.

It is shown that the time lower bound of computing the inverse dynamics of an n-link robot manipulator parallelly using p processors is O(k1 [n/p] + k2 [log<2 p]), where k1 and k2 are constants. A novel parallel algorithm for computing the inverse dynamics using the Newton-Euler equations of motion was developed to be implemented on a single-instruction-stream multiple-data-stream computer with p processors to achieve the time lower bound. When p = n, the proposed parallel algorithm achieves the Minsky's time lower bound O([log2 n]), whidc is the conjecture of parallel evaluation. The proposed p-fold parallel algorithm can be best described as consisting of p-parallel blocks with pipelined elements within each parallel block The results from the computations in the p blocks form a new homogeneous linear recurrence of size p, which can be computed using the recursive doubling algorithm. A modified inverse perfect shuffle interconnection scheme was suggested to interconnect the p processors. Furthermore, the proposed parallel algorithm is susceptible to a systolic pipelined architecture, requiring three floating-point operations per complete set of joint torques.

The synthesis of position/force trajectories for compliant motion is an important task for the control of industrial robots in assembly tasks. The position and orientation of the manipulator can be specified by a set of six linear independent constraints. Some are caused by contact with other objects (natural position constraints) and the others are applied artificially (artificial position constraints). Since the uncertainties and the modeling errors make the exact natural position constraints incomputable, a set of contact forces (artificial reaction-force constraints) is servoed to implicitly reflect their effects. Two mappings, T-C and C-PF, are defined which derive the nominal position trajectory P(t) and freedom decomposition function S(t) from the attributes of a given task, and then the desired artificial position and reaction-force constraints. In the T-C mapping, for an insertion task, the convex operand shrinks to a line and the three 2-D cut-diagrams of the concave operand are derived and expanded correspondingly. The nominal position trajectory is determined from these expanded cut-diagrams. Three 2-D trapezoids are defined to model the uncertainties. The intersections between the trapezoids and the cut-diagrams are checked to determine the values of freedom decomposition function S(t). Consequently, in the C-PF mapping the time sequences of the artificial position constraints and artificial reaction-force constraints are derived from the nominal position trajectory and the freedom decomposition function.

This paper describes a cost effective architecture for the control of mechanical manipulators based on a functional decomposition of the equations of motion of a manipulator. The Lagrange-Euler formulation and the Newton-Euler formulation were considered for the decomposition. The functional decomposition separated the inertial, Coriolis, centrifugal and gravity terms of the Lagrange-Euler equations of motion. The Newton-Euler equations of motion lent themselves to being decomposed to the terms used to generate the recursive forward and backward equations. Architectures tuned to the functional flow of the two algorithms were examined. An architecture which meets our design criteria is proposed. The proposed controller architecture can best be described as a macro level pipeline with parallelism within elements of the pipeline. The pipeline is designed to take maximum benefit of the serial nature of the Newton-Euler equations of motion.

A cost-effective architecture for the control of mechanical manipulators based on a functional decomposition of the equations of motion of a manipulator are described. The Lagrange-Euler and the Newton-Euler formulations were considered for this decomposition. The functional decomposition separates the inertial, Coriolis and centrifugal, and gravity terms of the Lagrange-Euler equations of motion. The recursive nature of the Newton-Euler equations of motion lend themselves to being decomposed to the terms used to generate the recursive forward and backward equations. Architectures tuned to the functional flow of the two algorithms were examined. An architecture which meets our design criterion is proposed. The proposed controller architecture can best be described as a macro level pipeline, with parallelism within elements of the pipeline. The pipeline is designed to take maximum benefit of the serial nature of the Newton-Euler equations of motion.

This paper presents the study of an adaptive control which tracks a desired time-based trajectory as closely as possible for all times over a wide range of manipulator motion and payloads both in joint-variable coordinates and Cartesian coordinates. The proposed adaptive control is based on the linearized perturbation equations in the vicinity of a nominal trajectory. The controlled system is characterized by feedforward and feedback components which can be computed separately and simultaneously. The feedforward component computes the nominal torques from the Newton-Euler equations of motion either using the resolved joint information or the joint information from the trajectory planning program. This computation can be completed in O(n) time. The feedback component consisting of recursive least square identification and one-step optimal control algorithms for the linearized system computes the variational torques in O(n3) time. Because of the parallel structure, the computations of the adaptive control may be implemented in low-cost microprocessors. A computer simulation study was conducted to evaluate the performance of the adaptive control in joint-variable coordinates for a three-joint robot arm. The feasibility of implementing the adaptive control in Cartesian coordinates using present day low-cost microprocessors is discussed.

A theoretical procedure is developed for comparing the performance of arbitrarily selected admissible controls among themselves and with the optimal solution of a nonlinear optimal control problem. A recursive algorithm is proposed for sequential improvement of the control law which converges to the optimal. It is based on the monotonicity between the changes of the Hamiltonian and the value functions proposed by Rekasius, and may provide a procedure for selecting effective controls for nonlinear systems. The approach has been applied to the approximately optimal control of a trainable manipulator with seven degrees of freedom, where the controller is used for motion coordination and optimal execution of object-handling tasks.