This article introduces a human-in-the-loop (HITL) algorithm designed to address a real-world individual animal identification problem: identifying distinct animals from a set of unlabeled camera-trap images when the total number of individuals is unknown. A key contribution of this article is its explicit balance of two critical factors in evaluating identification algorithms: identification accuracy and the cost of expert human annotation, i.e., the number of manual decisions required to determine whether an image pair belongs to the same individual. Our HITL strategy uses human involvement only in the most difficult cases, employing autonomous identification for easily distinguishable cases, to obtain high overall identification accuracy with minimal human effort. The proposed framework consists of three components: HITL-based core clustering generation, HITL-based clustering verification, and HITL-based clustering growth. Experimental validation was performed on an African leopard dataset provided byPanthera, with the algorithm achieving identification accuracy comparable to a human baseline method, where each image is manually compared to its top-2 most similar images. The proposed approach reduces human involvement by 77.3%, requiring only 0.05% of all pairs to be manually labeled as belonging to the same or different individuals.

This article describes an algorithm to solve the real-world animal identification problem, i.e., determine the unknown number of$K$individual animals in a dataset of$N$unlabeled camera-trap images of African leopards, provided by Panthera. To determine the leopards’ IDs, we propose an effective automated algorithm, that consists of segmenting leopard bodies from images, scoring similarity between image pairs, and clustering followed by verification. To perform clustering, we employ a modified ternary search that uses a novel adaptive$k$-medoids$++$clustering algorithm. The best clustering is determined using an expanded definition of the silhouette score. A new post-clustering verification procedure is used to further improve the quality of a clustering. The algorithm was evaluated using the Panthera dataset that consists of 677 individual leopards taken from 1555 images, and resulted in a clustering with an adjusted mutual information score of 0.958 as compared to 0.864 using a baseline$k$-medoids$++$clustering algorithm.Note to Practitioners—We proposed an effective automated algorithm to solve the real-world animal identification problem: identifying$K$unknown individual animals in$N$images of a given species, with most animals only represented by a single image. This algorithm is different from other methods that assume all images in a dataset are from known individuals and thus regard the animal ID problem as a retrieval identification task. Our approach consists of a new adaptive$k$-medoids$++$clustering algorithm and a novel post-clustering verification procedure. The clustering is performed based on the degree of similarity between all image pairs in the dataset with the result validated using an expanded definition of the silhouette score. The accuracy of our algorithm was demonstrated on a real-world image dataset of African leopards, a small dataset with a relatively large ratio of$K/N$, provided by Panthera. Code has been made available at: https://github.com/obaiga/Automatic-individual-animal-identification.

In this session, a panel of members of the current Fellows Committee of the IEEE Education Society will share advice on preparing nominations for Fellow of the IEEE and Fellow of the American Society for Engineering Education. The panelists will also provide advice on applications for competitive national and international awards. The panelists will explain how to enhance career planning to become eligible for awards and honors.

This article considers the problem of planning a trajectory that maximizes the probability that a robot will be able to complete a set of point-to-point tasks, after experiencing locked joint failures. The proposed approach first develops a method to calculate the probability of task failure for an arbitrary trajectory based on its failure scenarios, which are efficiently computed by identifying the ranges of task point self-motion manifolds. Then, a novel trajectory planning algorithm is proposed to find the optimal trajectory with maximum probability of task completion. The planning algorithm exploits the overlap of self-motion manifold bounding boxes, as opposed to always using the shortest distance, to determine an optimal trajectory. The proposed trajectory planning algorithm is demonstrated on planar positioning 3R, spatial positioning 4R, and spatial positioning/orienting 7R redundant robots, resulting in average improvement of 17%, 22%, and 30%, respectively, compared to the best shortest distance trajectory.

This paper presents a technique to identify singularities of any rank for a robot of any kinematic structure. The technique is based on computing the gradient of singular values of the robot Jacobian. The algorithm deals with the situations when two or more singular values become nearly equal and their corresponding singular vectors are ill-defined. Also, an algorithm is developed to identify the physically meaningful singular directions from the high dimensional singular subspaces of high-rank singularities. The suggested technique is applied to a 4-DoF and a 7-DoF robot to show its efficacy at identifying robot singularities of all ranks and dealing with the ill-defined singular directions.

Cloud computing has enabled entirely new business models for high-performance computing. Having a dedicated local high-performance computer is still an option for some, but more are turning to cloud computing resources to fulfill their high-performance computing needs. With cloud computing it is possible to tailor your computing infrastructure to perform best for your particular type of workload by selecting the correct number of machines of each type. This paper presents an efficient algorithm to find the best set of computing resources to allocate to the workload. This research is applicable to users provisioning cloud computing resources and to data center owners making purchasing decisions about physical hardware. Studies have shown that cloud computing machines have measurable variability in their performance. Some of the causes of performance variability include small changes in architecture, location within the datacenter, and neighboring applications consuming shared network resources. The proposed algorithm models the uncertainty in the computing resources and the variability in the tasks in a many-task computing environment to find a robust number of machines of each type necessary to process the workload. In addition, reward rate, cost, failure rate, and power consumption can be optimized, as desired, to compute Pareto fronts.

With the increases in complexity and number of nodes in large-scale high performance computing (HPC) systems over time, the probability of applications experiencing runtime failures has increased significantly. Projections indicate that exascale-sized systems are likely to operate with mean time between failures (MTBF) of as little as a few minutes. Several strategies have been proposed in recent years for enabling systems of these extreme sizes to be resilient against failures. This work provides a comparison of four state-of-the-art HPC resilience protocols that are being considered for use in exascale systems. We explore the behavior of each resilience protocol operating under the simulated execution of a diverse set of applications and study the performance degradation that a large-scale system experiences from the overhead associated with each resilience protocol as well as the re-computation needed to recover when a failure occurs. Using the results from these analyses, we examine how resource management on exascale systems can be improved by allowing the system to select the optimal resilience protocol depending upon each application's execution characteristics, as well as providing the system resource manager the ability to make scheduling decisions that are “resilience aware” through the use of more accurate execution time predictions.

The recent proliferation and associated high electricity costs of distributed data centers have motivated researchers to study energy-cost minimization at the geo-distributed level. The development of time-of-use (TOU) electricity pricing models and renewable energy source models has provided the means for researchers to reduce these high energy costs through intelligent geographical workload distribution. However, neglecting important considerations such as data center cooling power, interference effects from task co-location in servers, net-metering, and peak demand pricing of electricity has led to sub-optimal results in prior work because these factors have a significant impact on energy costs and performance. We propose a set of workload management techniques that take a holistic approach to the energy minimization problem for geo-distributed data centers. Our approach considers detailed data center cooling power, co-location interference, TOU electricity pricing, renewable energy, net metering, and peak demand pricing distribution models. We demonstrate the value of utilizing such information by comparing against geo-distributed workload management techniques that possess varying amounts of system information. Our simulation results indicate that our best proposed technique is able to achieve a 61 percent (on average) cost reduction compared to state-of-the-art prior work.

Resource management for large-scale high performance computing systems pose difficult challenges to system administrators. The extreme scale of these modern systems require task scheduling algorithms that are capable of handling at least millions of tasks and thousands of machines. These large computing systems consume vast amounts of electricity leading to high operating costs. System administrators try to simultaneously reduce operating costs and offer state-of-the-art performance; however, these are often conflicting objectives. Highly scalable algorithms are necessary to schedule tasks efficiently and to help system administrators gain insight into energy/performance trade-offs of the system. System administrators can examine this trade-off space to quantify how much a difference in the performance level will cost in electricity, or analyze how much performance can be expected within an energy budget. In this study, we design a novel linear programming based resource allocation algorithm for a heterogeneous computing system to efficiently compute high quality solutions for simultaneously minimizing energy and makespan. These solutions are used to bound the Pareto front to easily trade-off energy and performance. The new algorithms are highly scalable in both solution quality and computation time compared to existing algorithms, especially as the problem size increases.

A local definition of fault tolerance, based on properties of the manipulator Jacobian, is used to generate the kinematics of seven degree-of-freedom (DOF) revolute joint manipulators. The measure of fault tolerance used is the smallest singular value over all possible Jacobians resulting from single locked joint failures. The canonical form for an optimal fault-tolerant Jacobian that maximizes this measure has been previously identified. It has also been known that it is not possible to generate a seven DOF revolute manipulator that corresponds to this theoretically optimal Jacobian. However, in this paper, it is shown how to generate physically realizable Jacobians that are very close to being optimal. It is further shown that there exist 7! different manipulators, from a single Jacobian, that have the same local fault tolerance properties. To evaluate the global properties of these different manipulators, a technique for computing six-dimensional fault-tolerant workspaces is presented. The size of these workspaces vary significantly among these 7! manipulators.

It is well known that anthropomorphic manipulators, such as the PA-10, are intolerant to a single locked joint failure of the elbow. This is because the elbow is the only joint that can change the distance between the spherical shoulder joint and the spherical wrist. In this work, it is shown how such arms can be made significantly more fault tolerant by a minor modification to the kinematic structure of the arm. We quantify the degree of fault tolerance to locked joint failures as the minimum of the smallest singular value of the resulting seven Jacobians over all possible single failures. The DH parameters for the modified arm are designed so that the corresponding fault tolerant properties are close to those of a robot with an optimally failure tolerant Jacobian. The fault tolerance of the designed robot is evaluated for two different classes of applications, i.e., point-to-point motions and specified end-effector trajectories.

Kinematically redundant manipulators are inherently more robust to locked joint failures than non-redundant manipulators. However, if poorly designed, performance degradation may still occur in the presence of a single locked joint. This paper presents a technique for designing a desired operating workspace for a kinematically redundant manipulator that can be guaranteed after the occurrence of an arbitrary single locked joint failure. The existence of such a workspace, called a failure-tolerant workspace, will be guaranteed by imposing a suitable set of artificial joint limits prior to a failure. Conditions are presented that characterize end-effector locations within the failure-tolerant region. Based on these conditions, an algorithm for computing the failure-tolerant workspace is presented. The algorithm is based upon identifying the boundaries of the failure-tolerant workspace. Examples are presented to illustrate the application of the proposed algorithm to various manipulator design problems.

Many of today’s data centers experience physical limitations on the power needed to run the data center. The first problem that we study is maximizing the performance (quantified by the reward collected for completing tasks by their individual deadlines) of a data center that is subject to total power consumption (of compute nodes and CRAC units) and thermal constraints. The second problem that we study is how to minimize the power consumption in a data center while guaranteeing that the overall performance does not drop below a specified threshold. For both problems, we develop novel optimization techniques for assigning the performance states of cores at the data center level to optimize the operation of the data center. The resource allocation (assignment) techniques in this paper are thermal aware as they consider effects of performance state assignments on temperature and power consumption by the CRAC units. Our simulation studies show that in some cases our assignment technique achieves about 17% average improvement in the reward collected, and about 9% reduction in power consumption compared to an assignment technique that only considers putting a core in the performance state with the highest performance or turning the core off.

We model an oversubscribed heterogeneous computing system where tasks arrive dynamically and a scheduler maps the tasks to machines for execution. The environment and workloads are based on those being investigated by the Extreme Scale Systems Center at Oak Ridge National Laboratory. Utility functions that are designed based on specifications from the system owner and users are used to create a metric for the performance of resource allocation heuristics. Each task has a time-varying utility (importance) that the enterprise will earn based on when the task successfully completes execution. We design multiple heuristics, which include a technique to drop low utility-earning tasks, to maximize the total utility that can be earned by completing tasks. The heuristics are evaluated using simulation experiments with two levels of oversubscription. The results show the benefit of having fast heuristics that account for the importance of a task and the heterogeneity of the environment when making allocation decisions in an oversubscribed environment. The ability to drop low utility-earning tasks allow the heuristics to tolerate the high oversubscription as well as earn significant utility.

Today’s data centers face the issue of balancing electricity use and completion times of their workloads. Rising electricity costs are forcing data center operators to either operate within an electricity budget or to reduce electricity use as much as possible while still maintaining service agreements. Energy-aware resource allocation is one technique a system administrator can employ to address both problems: optimizing the workload completion time (makespan) when given an energy budget, or to minimize energy consumption subject to service guarantees (such as adhering to deadlines). In this paper, we study the problem of energy-aware static resource allocation in an environment where a collection of independent (non-communicating) tasks (“bag-of-tasks”) is assigned to a heterogeneous computing system. Computing systems often operate in environments where task execution times vary (e.g., due to cache misses or data dependent execution times). We model these execution times stochastically, using probability density functions. We want our resource allocations to be robust against these variations, where we defineenergy-robustnessas the probability that the energy budget is not violated, andmakespan-robustnessas the probability a makespan deadline is not violated. We develop and analyze several heuristics for energy-aware resource allocation for both energy-constrained and deadline-constrained problems.

With the advent of energy-aware scheduling algorithms, it is now possible to find solutions that trade-off performance for decreased energy usage. There are now efficient algorithms to find high quality Pareto fronts that can be used to select the desired balance between make span and energy consumption. One drawback of this approach is that it still requires a system administrator to select the desired operating point. In this paper, a market-oriented technique for scheduling is presented where the high performance computing system administrator is trying to maximize the return on investment. A model is developed where the users pay a given price to have a bag-of-tasks processed. The cost to the system administrator for processing this bag-of-tasks is strongly related to the energy consumption for executing these tasks. A novel algorithm is designed that efficiently finds the maximum profit resource allocation and tightly bounds the optimal solution. In addition, this algorithm has very desirable runtime and solution quality properties as the number of tasks and machines become large.

It is common practice to design a robot's kinematics from the desired properties that are locally specified by a manipulator Jacobian. For the case of local optimality with respect to fault tolerance, one common definition is that the post-failure Jacobian possesses the largest possible minimum singular value over all possible locked-joint failures. This work considers the global analysis of seven-joint manipulators that have been designed to be locally optimal in terms of fault tolerance when used for six-dimensional tasks. An algorithm for calculating a six-dimensional volume that is composed of a three-dimensional positioning component and a three-dimensional orientation component is presented. Two example manipulators are then analyzed and compared, illustrating a wide degree of variability between their global fault tolerant properties. It is further shown that there are 7! = 5040 different such manipulator designs due to the number of permutations of the Jacobian matrix.

The creation of a Massive Multi-Player On-line Game (MMOG) has significant costs, such as maintenance of server rooms, server administration, and customer service. The capacity of servers in a client/server MMOG is hard to scale and cannot adjust quickly to peaks in demand while maintaining the required response time. To handle these peaks in demand, we propose to employ users’ computers as secondary servers. The introduction of users’ computers as secondary servers allows the performance of the MMOG to support an increase in users. Here, we consider two cases: first, for the minimization of the response times from the server, we develop and implement five static heuristics to implement a secondary server scheme that reduces the time taken to compute the state of the MMOG. Second, for our study on fairness, the goal of the heuristics is to provide a “fair” environment for all the users (in terms of similar response times), and to be “robust” against the uncertainty of the number of new players that may join a given system configuration. The number of heterogeneous secondary servers, conversion of a player to a secondary server, and assignment of players to secondary servers are determined by the heuristics implemented in this study.

It is common practice to design a robot's kinematics from the desired properties that are locally specified by a manipulator Jacobian. In this work, the desired property is fault tolerance, defined as the post-failure Jacobian possessing the largest possible minimum singular value over all possible locked-joint failures. A mathematical analysis based on the Gram matrix that describes the number of possible planar robot designs for optimally fault-tolerant Jacobians is presented. It is shown that rearranging the columns of the Jacobian or multiplying one or more of the columns of the Jacobian by ±1 will not affect local fault tolerance; however, this will typically result in a very different manipulator. Two examples, one that is optimal to a single joint failure and the second that is optimal to two joint failures, are analyzed. This analysis shows that there is a large variability in the global kinematic properties of these designs, despite being generated from the same Jacobian. It is especially surprising that major differences in global behavior occurs for manipulators that are identical in the working area.

Fault tolerance is critical for various situations where robotic manipulators are applied, such as for hazardous waste disposal, exploring remote environments, or medical procedures. Metrics that are frequently applied to measure the degree of fault tolerance that a manipulator possesses have been focused on local kinematic properties of the Jacobian matrix, e.g., the worst-case manipulability (or relative manipulability) following a locked joint failure. These measures are useful for characterizing the manipulator's dexterity at a given configuration, however, they do not provide a measure for completion of a task within a specified workspace. This paper extends the use of local fault tolerance measures by using them to compute a global measure using a probabilistic analysis. Specifically, we compute cumulative density functions (CDF) that can be used to specify a desired fault tolerance threshold for completion of a task within a specified workspace region. We further show how this CDF can be improved by utilizing redundancy to optimize manipulator configurations throughout this region, using a modified nine degree of freedom Mitsubishi PA10-7C.

This work presents a method for identifying all the kinematic designs of spatial positioning manipulators that are optimally fault tolerant in a local sense. We use a common definition of fault tolerance, i.e., the post-failure Jacobian possesses the largest possible minimum singular value over all possible single locked-joint failures. The large family of physical manipulators that can achieve this optimally failure tolerant configuration is then parameterized and categorized. We develop a general computational technique to evaluate the resulting manipulators in terms of their global kinematic properties, with an emphasis on failure tolerance. Several manipulators with a range of desirable kinematic properties are presented and analyzed, with a specific example of optimizing over a given class of manipulators that possess a specified kinematic constraint.

In a heterogeneous environment, uncertainty in system parameters may cause performance features to degrade considerably. It then becomes necessary to design a system that is robust. Robustness can be defined as the degree to which a system can function in the presence of inputs different from those assumed. In this research, we focus on the design of robust static resource allocation heuristics suitable for a heterogeneous compute cluster that minimize the energy required to complete a given workload. In this study, we mathematically model and simulate a heterogeneous computing system that is assumed part of a larger warehouse scale computing environment. Task execution times/energy consumption may vary significantly across different data sets in our heterogeneous cluster; therefore, the execution time of each task on each node is modeled as a random variable. A resource allocation is considered robust if the probability that all tasks complete by a system deadline is at least 90%. To minimize the energy consumption of a specific resource allocation, dynamic voltage frequency scaling (DVFS) is employed. However, other factors, such as system overhead (spent on fans, disks, memory, etc.) must also be mathematically modeled when considering minimization of energy consumption. In this research, we propose three different heuristics that employ DVFS to minimize energy consumed by a set of tasks in our heterogeneous computing system. Finally, a lower bound on energy consumption is provided to gauge the performance of our heuristics.

The design of locally optimal fault-tolerant manipulators has been previously addressed via adding constraints on the bases of a desired null space to the design constraints of the manipulators. Then by algebraic or numeric solution of the design equations, the optimal Jacobian matrix is obtained. In this study, an optimal fault-tolerant Jacobian matrix generator is introduced from geometric properties instead of the null space properties. The proposed generator provides equally fault-tolerant Jacobian matrices in R3that are optimally fault tolerant for one or two locked joint failures. It is shown that the proposed optimal Jacobian matrices are directly obtained via regular pyramids. The geometric approach and zonotopes are used as a novel tool for determining relative manipulability in the context of fault-tolerant robotics and for bringing geometric insight into the design of optimal fault-tolerant manipulators.

It is common practice to design a robot's kinematics from the desired properties that are locally specified by a manipulator Jacobian. It has been recently shown that multiple different physical robot kinematic designs can be obtained from (essentially) a single Jacobian that has desirable fault tolerant properties. Fault tolerance in this case is defined as the post-failure Jacobian possessing the largest possible minimum singular value over all possible locked-joint failures. In this work, a mathematical analysis that describes the number of possible planar robot designs for optimally fault-tolerant Jacobians is presented. Two examples, one that is optimal to a single joint failure and the second that is optimal to two joint failures, are discussed. The paper concludes by illustrating some of the large variability in the global kinematic properties of these designs, despite being generated from the same Jacobian.

It is common practice to design a robot's kinematics from the desired properties that are locally specified by a manipulator Jacobian. For the case of optimality with respect to fault tolerance, one common definition is that the post-failure Jacobian possesses the largest possible minimum singular value over all possible locked-joint failures. This work considers a Jacobian that has been designed to be optimally fault tolerant for a simple spatial positioning manipulator. It is shown that despite the fact that the Jacobian is “unique”, up to column permutations and multiplications by ±1, there are a large family of physical manipulators that correspond to the optimal Jacobian. Two example manipulators are presented and analyzed. It is shown that there is a large degree of variability in the global kinematic properties of these designs, despite being generated from the same Jacobian.

This work considers the satellite data processing portion of a space-based weather monitoring system. It uses a heterogeneous distributed processing platform. There is uncertainty in the arrival time of new data sets to be processed, and resource allocation must be robust with respect to this uncertainty. The tasks to be executed by the platform are classified into two broad categories: high priority (e.g., telemetry, tracking, and control), and revenue generating (e.g., data processing and data research). In this environment, the resource allocation of the high-priority tasks must be done before the resource allocation of the revenue generating tasks. A two-part allocation scheme is presented in this research. The goal of first part is to find a resource allocation that minimizes makespan of the high-priority tasks. The robustness for the first part of the mapping is defined as the difference between this time and the expected arrival of the next data set. For the second part, the robustness of the mapping is the difference between the expected arrival time and the time at which the revenue earned is equal to the operating cost. Thus, the heuristics for the second part find a mapping that minimizes the time for the revenue (gained by completing revenue generating tasks) to be equal to the cost. Different resource allocation heuristics are designed and evaluated using simulations, and their performance is compared to a mathematical bound.

Many appearance-based classification problems such as principal component analysis, linear discriminant analysis, and locally preserving projections involve computing the principal components (eigenspace) of a large set of images. Although the online expense associated with appearance-based techniques is small, the offline computational burden becomes prohibitive for practical applications. This paper presents a method to reduce the expense of computing the eigenspace decomposition of a set of images when variations in both illumination and pose are present. In particular, it is shown that the set of images of an object under a wide range of illumination conditions and a fixed pose can be significantly reduced by projecting these data onto a few low-frequency spherical harmonics, producing a set of "harmonic images." It is then shown that the dimensionality of the set of harmonic images at different poses can be further reduced by utilizing the fast Fourier transform. An eigenspace decomposition is then applied in the spectral domain at a much lower dimension, thereby significantly reducing the computational expense. An analysis is also provided, showing that the principal eigenimages computed assuming a single illumination source are capable of recovering a significant amount of information from images of objects when multiple illumination sources exist.

We study the problem of efficiently allocating incoming independent tasks onto the resources of a Grid system. Typically, it is assumed that the estimated time to compute each task on every machine is known. We are making the same assumption in this work, but we allow the existence of inaccuracies in these values. Our schedule will be robust versus such inaccuracies, ensuring that even when the estimated time to compute all the tasks is increased by a given percentage, the makespan of the schedule (i.e., the time when the last machine finishes its tasks) will not grow behind that percentage. We propose a new multi-objective definition of the problem, optimizing at the same time the makespan of the schedule and its robustness. Four well-known multi-objective evolutionary algorithms are used to find competitive results to the new problem. Finally, a new population initialization method for scheduling problems is proposed, leading to more efficient and accurate algorithms.

The environment considered in this research is a massive multiplayer online gaming (MMOG) environment. Each user controls an avatar (an image that represents and is manipulated by a user) in a virtual world and interacts with other users. An important aspect of MMOG is maintaining a fair environment among users (i.e., not give an unfair advantage to users with faster connections or more powerful computers). The experience (either positive or negative) the user has with the MMOG environment is dependent on how quickly the game world responds to the user's actions. This study focuses on scaling the system based on demand, while maintaining an environment that guarantees fairness. Consider an environment where there is a main server (MS) that controls the state of the virtual world. If the performance falls below acceptable standards, the MS can off-load calculations to secondary servers (SSs). An SS is a user's computer that is converted into a server. Four heuristics are proposed for determining the number of SSs, which users are converted to SSs, and how users are assigned to the SSs and the MS. The goal of the heuristics is to provide a "fair" environment for all the users, and to be "robust" against the uncertainty of the number of new players that may join a given system configuration. The heuristics are evaluated and compared by simulation.

This research investigates the problem of robust dynamic resource allocation for heterogeneous distributed computing systems operating under imposed constraints. Often, such systems are expected to function in an environment where uncertainty in system parameters is common. In such an environment, the amount of processing required to complete an application may fluctuate substantially. Determining a resource allocation that accounts for this uncertainty-in a way that can provide a probability that a given level of service is achieved-is an important area of research. We define a mathematical model of stochastic robustness appropriate for a dynamic environment that can be used during resource allocation to aid heuristic decision making. In addition, we design a novel technique for maximizing stochastic robustness in this environment. Our performance results for this technique are compared with several well known resource allocation techniques in a simulated environment that models a heterogeneous distributed computing system.

Creating replicas of frequently accessed data objects across a read-intensive content delivery network (CDN) can result in reduced user response time. Because CDNs often operate under volatile conditions, it is of the utmost importance to study replica placement techniques that can cope with uncertainties in the system parameters. We propose four CDN replica placement heuristics that guarantee a robust performance under the uncertainty of arbitrary CDN server failures. By robust performance we mean the solution quality that a heuristic guarantees given the uncertainties in system parameters. The simulation results reveal interesting characteristics of the studied heuristics. We report these characteristics with a detailed discussion on which heuristics to utilize for robust CDN data replication given a specific scenario.

The problem of finding efficient workload distribution techniques is becoming increasingly important today for heterogeneous distributed systems where the availability of compute nodes may change spontaneously over time. Therefore, the resource-allocation policy must be designed to be robust with respect to absence and re-emergence of compute nodes so that the performance of the system is maximized. Such a policy is developed in this work, and its performance is evaluated on a model of a dedicated system composed of a limited set of heterogeneous Web servers. Assuming that each HTML request results in a rdquorewardrdquo if completed before its hard deadline, the goal is to maximize a cumulative reward obtained in the system. A failure rate for each server is set relatively high to simulate its operation under harsh conditions. The results demonstrate that the proposed approach based on the concepts of the Derman-Lieberman-Ross theorem outperforms other policies compared in our experiments for inconsistent, processor-consistent, and task-processor-consistent types of heterogeneity.

Eigendecomposition has been used to classify three-dimensional objects from two-dimensional images in a variety of computer vision and robotics applications. The biggest on-line computational expense associated with using eigendecomposition is the determination of the closest point on an image manifold embedded in a high-dimensional space. The dimensionality and complexity of the space is a result of the p principal eigenimages that are selected. Unfortunately, for some real-time applications, this search may be prohibitively expensive. This work presents a method to reduce the on-line expense associated with using eigendecomposition for pose estimation. The approach is based on selecting a linear combination of the principal eigenimages to design an eigenspace manifold having a desirable geometric structure that reduces the cost associated with classification.

Determining the pose of a three-dimensional object under unknown lighting conditions is a challenging problem. Eigenspace methods represent one computationally efficient method for doing illumination invariant pose estimation, and have been applied in a variety of application domains. Unfortunately, determining the appropriate eigenspace dimension, as well as the eigenspace itself, is computationally prohibitive for real-world applications. This paper presents a method to reduce this expense by using results from spectral theory. In particular, this paper shows that a set of images of an object under a wide range of illumination conditions and a fixed pose can be significantly reduced by projecting this data on to a few low-frequency spherical harmonics, producing a set of ¿harmonic images¿. It is then shown that the dimensionality of the set of harmonic images can be further reduced by utilizing the fast Fourier transform. An eigendecomposition is then applied in the spectral domain thus relieving the computational burden. Experimental results are presented to compare the proposed algorithm to the true eigendecomposition, as well as assess the computational savings.

Eigendecomposition represents one computationally efficient approach for dealing with object detection and pose estimation, as well as other vision-based problems, and has been applied to sets of correlated images for this purpose. The major drawback in using eigendecomposition is the off line computational expense incurred by computing the desired subspace. This off line expense increases drastically as the number of correlated images becomes large (which is the case when doing fully general 3-D pose estimation). Previous work has shown that for data correlated on S(1), Fourier analysis can help reduce the computational burden of this off line expense. This paper presents a method for extending this technique to data correlated on S(2) as well as SO3 by sampling the sphere appropriately. An algorithm is then developed for reducing the off line computational burden associated with computing the eigenspace by exploiting the spectral information of this spherical data set using spherical harmonics and Wigner-D functions. Experimental results are presented to compare the proposed algorithm to the true eigendecomposition, as well as assess the computational savings.

The pose detection of three-dimensional (3-D) objects from two-dimensional (2-D) images is an important issue in computer vision and robotics applications. Specific examples include automated assembly, automated part inspection, robotic welding, and human robot interaction, as well as a host of others. Eigendecomposition is a common technique for dealing with this issue and has been applied to sets of correlated images for this purpose. Unfortunately, for the pose detection of 3-D objects, a very large number of correlated images must be captured from many different orientations. As a result, the eigendecomposition of this large set of images is very computationally expensive. In this work, we present a method for capturing images of objects from many locations by sampling S2appropriately. Using this spherical sampling pattern, the computational burden of computing the eigendecomposition can be reduced by using the spherical harmonic transform to "condense" information due to the correlation in S2. We propose a computationally efficient algorithm for approximating the eigendecomposition based on the spherical harmonic transform analysis. Experimental results are presented to compare and contrast the algorithm against the true eigendecomposition, as well as quantify the computational savings.

The creation of a virtual world environment (VWE) has significant costs, such as maintenance of server rooms, server administration, and customer service. The initial development cost is not the only factor that needs to be considered; factors such as the popularity of a VWE and unexpected technical problems during and after the launch can affect the final cost and success of a VWE. The capacity of servers in a client/server VWE is hard to scale and cannot adjust quickly to peaks in demand while maintaining the required response time. To handle these peaks in demand, we propose to employ users' computers as secondary servers. The introduction of users' computers as secondary servers allows the performance of the VWE to support an increase in users. In this study, we develop and implement five static heuristics to implement a secondary server scheme that reduces the time taken to compute the state of the VWE. The number of heterogeneous secondary servers, conversion of a player to a secondary server, and assignment of players to secondary servers are determined by the heuristics implemented in this study. A lower bound of the performance is derived to evaluate the results of the heuristics.

Adaptive replication of data items on servers of a mobile ad hoc network can alleviate access delays. The selection of data items and servers requires solving a constrained optimization problem, that is in general NP-complete. The problem is further complicated by frequent partitions of the ad hoc network. In this paper, a mathematical model for data replication in ad hoc networks is formulated. We treat the mobile servers in the ad hoc network as self-interested entities, hence they have the capability to manipulate the outcome of a resource allocation mechanism by misrepresenting their valuations. We design a game theoretic "truthful" mechanism in which replicas are allocated to mobile servers based on reported valuations. We sketch the exact properties of the truthful mechanism and derive a payment scheme that suppresses the selfish behavior of the mobile servers. The proposed technique is extensively evaluated against three ad hoc network replica allocation methods: (a) extended static access frequency, (b) extended dynamic access frequency and neighborhood, and (c) extended dynamic connectivity grouping. The experimental results reveal that the proposed approach outperforms the three techniques in solution quality and has competitive execution times.

We present a decentralized market-based approach to resource allocation in a heterogeneous overlay network. The presented resource allocation strategy assigns overlay network resources to traffic dynamically based on current utilization, thus, enabling the system to accommodate fluctuating demand for its resources. We present a mathematical model of our resource allocation environment that treats the allocation of system resources as a constrained optimization problem. Our presented resource allocation strategy is based on solving the dual of this centralized optimization problem. The solution to the dual of our centralized optimization problem suggests a simple decentralized algorithm for resource allocation that is extremely efficient. Our results demonstrate the near optimality of the proposed approach through extensive simulation of a real-world environment. That is, the conducted simulation study utilizes components taken from a real-world middleware application environment and clearly demonstrates the practicality of the approach in a realistic setting.

This paper summarizes some of our research in the area of robust static resource allocation for distributed computing systems operating under imposed quality of service (QoS) constraints. Often, these systems are expected to function in a physical environment replete with uncertainty, which causes the amount of processing required over time to fluctuate substantially. Determining a resource allocation that accounts for this uncertainty in a way that can provide a probabilistic guarantee that a given level of QoS is achieved is an important research problem. The stochastic robustness metric described in this research is based on a mathematical model where the relationship between uncertainty in system parameters and its impact on system performance are described stochastically.

An ad hoc grid is a wireless heterogeneous computing environment without a fixed infrastructure. This study considers wireless devices that have different capabilities, have limited battery capacity, support dynamic voltage scaling, and are expected to be used for eight hours at a time and then recharged. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule) in a manner that exploits the heterogeneity of the resources and tasks while considering the energy constraints of the devices. In the single-hop ad hoc grid heterogeneous environment considered in this study, tasks arrive unpredictably, are independent (i.e., no precedent constraints for tasks), and have priorities and deadlines. The problem is to map (match and schedule) tasks onto devices such that the number of highest priority tasks completed by their deadlines during eight hours is maximized while efficiently utilizing the overall system energy. A model for dynamically mapping tasks onto wireless devices is introduced. Seven dynamic mapping heuristics for this environment are designed and compared to each other and to a mathematical bound.

In this paper, the authors examine the problem of designing nominal manipulator Jacobians that are optimally fault tolerant to one or more joint failures. Optimality is defined here in terms of the worst-case relative manipulability index. While this approach is applicable to both serial and parallel mechanisms, it is especially applicable to parallel mechanisms with a limited workspace. It is shown that a previously derived inequality for the worst-case relative manipulability index is generally not achieved for fully spatial manipulators and that the concept of optimal fault tolerance to multiple failures is more subtle than previously indicated. Lastly, the authors identify the class of 8-DOF Gough--Stewart platforms that are optimally fault tolerant for up to two joint failures. Examples of optimally fault-tolerant 7- and 8-DOF mechanisms are presented.

In addition to possessing a number of other important properties, kinematically redundant manipulators are inherently more tolerant to locked-joint failures than non-redundant manipulators. However, a joint failure can still render a kinematically redundant manipulator useless if the manipulator is poorly designed or controlled. This paper presents a method for identifying a region of the workspace of a redundant manipulator for which task completion is guaranteed in the event of a locked-joint failure. The existence of such a region, called a failure-tolerant workspace, will be guaranteed by imposing a suitable set of artificial joint limits prior to a failure. Conditions are presented that characterize end-effector locations in this region. Based on these conditions, a method is presented that identifies the boundaries of the failure-tolerant workspace. Optimized failure-tolerant workspaces for a three degree-of-freedom planar robot are presented.

Heterogeneous computing (HC) is the coordinated use of different types of machines, networks, and interfaces to maximize the combined performance and/or cost effectiveness of the system. Heuristics for allocating resources in an HC system have different optimization criteria. A common optimization criterion is to minimize the completion time of the last to finish machine (makespan). In some environments, it is useful to minimize the finishing times of the other machines in the system, i.e., those machines that are not the last to finish. Consider a production environment where a set of known tasks are to be mapped to resources off-line before execution begins. Minimizing the finishing times of all the machines will provide the earliest available ready time for these machines to execute tasks that were not initially considered. In this study, we examine an iterative approach that decreases machine finishing times by repeatedly running a resource allocation heuristic. The goal of this study is to investigate whether this iterative procedure can reduce the finishing time of some machines compared to the mapping initially generated by the heuristic. We show that the effectiveness of the iterative approach is heuristic dependent and study the behavior of the iterative approach for each of the chosen heuristics. This work which identifies heuristics can and cannot attain improvements in the completion time of non-make span machines using this iterative approach.

This is an overview of the robust resource allocation research efforts that have been and continue to be conducted by the CSU robustness in computer systems group. Parallel and distributed computing systems, consisting of a (usually heterogeneous) set of machines and networks, frequently operate in environments where delivered performance degrades due to unpredictable circumstances. Such unpredictability can be the result of sudden machine failures, increases in system load, or errors caused by inaccurate initial estimation. The research into developing models and heuristics for parallel and distributed computing systems that create robust resource allocations is presented.

Heterogeneous distributed computing systems often must operate in an environment where system parameters are subject to uncertainty. Robustness can be defined as the degree to which a system can function correctly in the presence of parameter values different from those assumed. We present a methodology for quantifying the robustness of resource allocations in a dynamic environment where task execution times are stochastic. The methodology is evaluated through measuring the robustness of three different resource allocation heuristics within the context of a stochastic dynamic environment. A Bayesian regression model is fit to the combined results of the three heuristics to demonstrate the correlation between the stochastic robustness metric and the presented performance metric. The correlation results demonstrated the significant potential of the stochastic robustness metric to predict the relative performance of the three heuristics given a common objective function.

In addition to possessing a number of other important properties, kinematically redundant manipulators are inherently more tolerant to locked-joint failures than non- redundant manipulators. However, a joint failure can still render a kinematically redundant manipulator useless if the manipulator is poorly designed or controlled. This paper focuses on the implementation issues involved in identifying a region of the workspace for which task completion is guaranteed in the event of a locked-joint failure for a general class of planar 3R manipulators. The existence of such a region, called a failure-tolerant workspace, will be guaranteed by imposing a suitable set of artificial joint limits prior to a failure. The authors have developed a graphical user interface (GUI) that computes all workspace boundaries of interest for the planar 3R manipulators. This GUI allows the user to explore different robot geometries, and adjust the artificial joint limits, in an attempt to gain further understanding of a manipulator's failure-tolerant workspace.

In this article, the authors examine the problem of designing nominal manipulator Jacobians that are optimally fault tolerant to one or more joint failures. In this work, optimality is defined in terms of the worst case relative manipulability index. While this approach is applicable to both serial and parallel mechanisms, it is especially applicable to parallel mechanisms with a limited workspace. It is shown that a previously derived inequality for the worst case relative manipulability index is generally not achieved for fully spatial manipulators and that the concept of optimal fault tolerance to multiple failures is more subtle than previously indicated. Lastly, the authors identify the class of eight degree-of-freedom Gough-Stewart platforms that are optimally fault tolerant for up to two locked joint failures. Examples of optimally fault tolerant seven and eight degree-of-freedom mechanisms are presented.

Often, parallel and distributed computing systems must operate in an environment replete with uncertainty. Determining a resource allocation that accounts for this uncertainty in a way that can provide a probabilistic guarantee that a given level of quality of service (QoS) is achieved is an important research problem. This paper defines a stochastic methodology for quantifiably determining a resource allocation's ability to satisfy QoS constraints in the midst of uncertainty in system parameters. Uncertainty in system parameters and its impact on system performance are modeled stochastically. This stochastic model is then used to derive a quantitative expression for the robustness of a resource allocation. The paper investigates the utility of the proposed stochastic robustness metric by applying the metric to resource allocations in a simulated distributed system. The simulation results are then compared with deterministically defined metrics from the literature

Minimization of the execution time of an iterative application in a heterogeneous parallel computing environment requires an appropriate mapping scheme for matching and scheduling the subtasks of a given application onto the processors. Often, some of the characteristics of the application subtasks are unknown a priori or change from iteration to iteration during execution-time based on the inputs being processed. In such a scenario, it may not be feasible to use the same off-line-derived mapping for each iteration of the application. One possibility is to employ a semi-static methodology that starts with an initial mapping but dynamically performs remapping between application iterations by observing the effects of the changing characteristics of the application's input data, called dynamic parameters, on the application's execution time. A contribution in this paper is to implement and evaluate a semi-static methodology involving the on-line use of off-line-derived mappings. The off-line phase is based on a genetic algorithm (GA) to generate high-quality mappings for a range of values for the dynamic parameters. A dynamic parameter space partitioning and sampling scheme is proposed that partitions the parameter space into a number of hyper-rectangles, within which the “best” mapping for each hyper-rectangle is stored in a mapping table. During the on-line phase, the actual dynamic parameters are observed and the off-line-derived mapping table is referenced to choose the most suitable mapping. Experimental results indicate that the semi-static approach outperforms a dynamic on-line approach and performs reasonably close to an infeasible on-line GA approach. Furthermore, the semi-static approach considerably outperforms the method of using the same mapping for all iterations.

Eigendecomposition is a common technique that is performed on sets of correlated images in a number of computer vision and robotics applications. Unfortunately, the computation of an eigendecomposition can become prohibitively expensive when dealing with very high-resolution images. While reducing the resolution of the images will reduce the computational expense, it is not known a priori how this will affect the quality of the resulting eigendecomposition. The work presented here provides an analysis of how different resolution reduction techniques affect the eigendecomposition. A computationally efficient algorithm for calculating the eigendecomposition based on this analysis is proposed. Examples show that this algorithm performs well on arbitrary video sequences.

This work considers kinematic failure tolerance when obstacles are present in the environment. It addresses the issue of finding a collision-free path such that a redundant robot can successfully move from a start to a goal position and/or orientation in the workspace despite any single locked-joint failure at any time. An algorithm is presented that searches for a simply-connected, obstacle-free surface with no internal local minimum or maximum in the configuration space that guarantees the existence of a solution. The method discussed is based on the following assumptions: a robot is redundant relative to its task, only a single locked-joint failure occurs at any given time, the robot is capable of detecting a joint failure and immediately locks the failed joint, and the environment is static and known. The technique is illustrated on a seven degree-of-freedom commercially available redundant robot. Although developed and illustrated for a single degree of redundancy, it is possible to extend the algorithm to higher degrees of redundancy

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. Different classes of machines used in such systems typically vary in dollar cost based on their computing efficiencies. Makespan (defined as the completion time for an entire set of tasks) is often the performance feature that is optimized. Resource allocation is often done based on estimates of the computation time of each task on each class of machines. Hence, it is important that makespan be robust against errors in computation time estimates. The dollar cost to purchase the machines for use can be a constraint such that only a subset of the machines available can be purchased. The goal of this study is to: (1) select a subset of all the machines available so that the cost constraint for the machines is satisfied, and (2) find a static mapping of tasks so that the robustness of the desired system feature, makespan, is maximized against the errors in task execution time estimates. Six heuristic techniques to this problem are presented and evaluated

Singular value decomposition (SVD) is a common technique that is performed on video sequences in a number of computer vision and robotics applications. The left singular vectors represent the eigenimages, while the right singular vectors represent the temporal properties of the video sequence. It is obvious that spatial reduction techniques affect the left singular vectors; however, the extent of their effect on the right singular vectors is not clear. Understanding how the right singular vectors are affected is important because many SVD algorithms rely on computing them as an intermediate step to computing the eigenimages. The work presented here quantifies the effects of different spatial resolution reduction techniques on the right singular vectors that are computed from those video sequences. Examples show that using random sampling for spatial resolution reduction rather than a low-pass filtering technique results in less perturbation of the temporal properties.

This paper expands on previous research on the effect of introducing social robots into crowded situations in order to improve pedestrian flow. In this case, a genetic algorithm is applied to find the optimal parameters for the interaction model between the robots and the people. Preliminary results indicate that adding social robots to a crowded situation can result in significant improvement in pedestrian flow. Using the optimized values of the model parameters as a guide, these robots can be designed to be more effective at improving the pedestrian flow. While this work only applies to one situation, the technique presented can be applied to a wide variety of scenarios.

This research investigates two distinct issues related to a resource allocation: its robustness and the failure rate of the heuristic used to determine the allocation. The target system consists of a number of sensors feeding a set of heterogeneous applications continuously executing on a set of heterogeneous machines connected together by high-speed heterogeneous links. There are number of quality of service (QoS) constraints that must be satisfied. A heuristic failure occurs if the heuristic cannot find an allocation that allows the system to meet its QoS constraints. The system is expected to operate in an uncertain environment where the workload, i.e., the load presented by the set of sensors, is likely to change unpredictably, possibly invalidating a resource allocation that was based on the initial workload estimate. The focus of this paper is the design of a static heuristic that: (a) determines a robust resource allocation, i.e., a resource allocation that maximizes the allowable increase in workload until a run-time reallocation of resources is required to avoid a QoS violation, and (b) has a very low failure rate. This study proposes a heuristic that performs well with respect to the failure rates and robustness to unpredictable workload increases. This heuristic is, therefore, very desirable for systems where low failure rates can be a critical requirement and where unpredictable circumstances can lead to unknown increases in the system workload.

This work considers kinematic failure tolerance when obstacles are present hi the environment. An example is given using a fully spatial redundant robot, the seven degree-of-freedom Mitsubishi PA-10. This article addresses the issue of finding a collision-free path such that a redundant robot can successfully move from a start to a goal position and/or orientation in the workspace despite any single locked-joint failure at any time. An algorithm is presented that searches for a continuous obstacle-free monotonic surface in the configuration space that guarantees the existence of a solution. The method discussed is based on the following assumptions: a robot is redundant relative to its task, only a single locked-joint failure occurs at any given time, the robot is capable of detecting a joint failure and immediately locks the failed joint, and the environment is static and known.

Eigendecomposition is a common technique that is performed on sets of correlated images in a number of computer vision and robotics applications. Unfortunately, the computation of an eigendecomposition becomes prohibitively expensive when dealing with very high resolution images. Reducing the resolution of the images reduces the computational expense, it is not known how this affects the quality of the resulting eigendecomposition. The work presented here gives the theoretical background for quantifying the effects of varying the resolution of images on the eigendecomposition that is computed from those images. A computationally efficient algorithm for this eigendecomposition is proposed using derived analytical expressions. Examples show that this algorithm performs very well on arbitrary video sequences.

Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six static heuristics.

Eigendecomposition is a common technique that is performed on sets of correlated images in a number of computer vision and robotics applications. Unfortunately, the computation of an eigendecomposition can become prohibitively expensive when dealing with very high resolution images. While reducing the resolution of the images will reduce the computational expense, it is not known a priori how this will affect the quality of the resulting eigendecomposition. The work presented here provides an analysis of how different resolution reduction techniques affect the eigendecomposition. A computationally efficient algorithm for calculating the eigendecomposition based on this analysis is proposed. Examples show that this algorithm performs very well on arbitrary video sequences.

Parallel and distributed systems may operate in an environment that undergoes unpredictable changes causing certain system performance features to degrade. Such systems need robustness to guarantee limited degradation despite fluctuations in the behavior of its component parts or environment. This research investigates the robustness of an allocation of resources to tasks in parallel and distributed systems. The main contributions are 1) a mathematical description of a metric for the robustness of a resource allocation with respect to desired system performance features against multiple perturbations in multiple system and environmental conditions, and 2) a procedure for deriving a robustness metric for an arbitrary system. For illustration, this procedure is employed to derive robustness metrics for three example distributed systems. Such a metric can help researchers evaluate a given resource allocation for robustness against uncertainties in specified perturbation parameters.

This work considers the failure tolerant operation of a kinematically redundant manipulator in an environment containing obstacles. In particular, the article addresses the problem of planning a collision-free path for a manipulator operating in a static environment such that the manipulator can reach its desired goal despite a single locked-joint failure and the presence of obstacles in the environment. A method is presented that searches for a continuous obstacle-free space between the starting configuration and the desired final end-effector position, which is characterized in the joint space by the goal self-motion manifold. This method guarantees completion of critical tasks in the event of a single locked-joint failure in the presence of obstacles.

Eigendecomposition is a common technique that is performed on sets of correlated images in a number of computer vision and robotics applications. Unfortunately, the computation of an eigendecomposition can become prohibitively expensive when dealing with very high resolution images. While reducing the resolution of the images will reduce the computational expense, it is not known how this affects the quality of the resulting eigendecomposition. The work presented here proposes a framework for quantifying the effects of varying the resolution of images on the eigendecomposition that is computed from those images. Preliminary results show that an eigendecomposition from low-resolution images may be nearly as effective in some applications as those from high-resolution images.

An understanding of how to alter crowd dynamics would have a significant impact in a number of scenarios, e.g., during riots or evacuations. The social force model, where individuals are self-driven particles interacting through social and physical forces, is one approach that has been used to describe crowd dynamics. This work uses the framework of the social force model to study the effects of introducing autonomous robots into crowds. Two simple pedestrian flow problems are used as illustrative examples, namely flow in varying width hallways and lane formation in bi-directional pedestrian flow. Preliminary results indicate that robots capable of inducing an attractive social force are effective at improving pedestrian flow in both of these scenarios.

Teleoperated robots in harsh environments have a significant likelihood of failures. It has been shown in previous work that a common type of failure such as that of a joint "locking up," when unidentified by the robot controller, can cause considerable performance degradation in the local behavior of the manipulator even for simple point-to-point motion tasks. The effects of a failure become more critical for a system with a human in the loop, where unpredictable behavior of the robotic arm can completely disorient the operator. In this experimental study involving teleoperation of a graphically simulated kinematically redundant manipulator, two control schemes, the pseudoinverse and a proposed failure-tolerant inverse, were randomly presented under both nonfailure and failure scenarios to a group of operators. Based on performance measures derived from the recorded trajectory data and operator ratings of task difficulty, it is seen that the failure-tolerant inverse kinematic control scheme improved the performance of the human/robot system.

Eigendecomposition-based techniques are popular for a number of computer vision problems, e.g., object and pose detection, because they are purely appearance-based and they require few on-line computations. Unfortunately, they also typically require an unobstructed view of the object whose pose is being detected. The presence of occlusion precludes the use of the normalizations that are typically applied and significantly alters the appearance of the object under detection. This work presents an algorithm that is based on applying eigendecomposition to a quadtree representation of the image dataset used to describe the appearance of an object. This allows decisions concerning the pose of an object to be based on only those portions of the image in which the algorithm has determined that the object is not occluded. The accuracy and computational efficiency of the proposed approach is evaluated on sixteen different objects with up to 50% of the object being occluded.

We present a computationally efficient algorithm for the eigenspace decomposition of correlated images. Our approach is motivated by the fact that for a planar rotation of a two-dimensional (2-D) image, analytical expressions can be given for the eigendecomposition, based on the theory of circulant matrices. These analytical expressions turn out to be good first approximations of the eigendecomposition, even for three-dimensional (3-D) objects rotated about a single axis. In addition, the theory of circulant matrices yields good approximations to the eigendecomposition for images that result when objects are translated and scaled. We use these observations to automatically determine the dimension of the subspace required to represent an image with a guaranteed user-specified accuracy, as well as to quickly compute a basis for the subspace. Examples show that the algorithm performs very well on a number of test cases ranging from images of 3-D objects rotated about a single axis to arbitrary video sequences.

Robotic joint failures are directly characterized and measured in joint space. A locking failure, for example, is one for which a joint cannot move, and it gives an error equal to the desired value minus the locked value. This article extends the joint-space characterization to Euclidean space by measuring the failure effect. The approach is based on a rudimentary measure of point error that can be defined to be distance or path length. It is used to form comprehensive measures through weighted integration over Euclidean-space regions. For kinematically redundant manipulators, minimizing the measures using the redundancy is a method to induce failure tolerance. This can be applied both before a failure to reduce the likelihood of collision-induced damage and after a failure to reduce end-effector error. Examples for both cases are given.

The velocity control of kinematically redundant manipulators has been addressed through a variety of approaches. Though they differ widely in their purpose and method of implementation, most are optimizations that can be characterized by Liegeois's (1977) method. This characterization is used in this article to develop a single framework for implementing different methods by simply selecting a scalar, a function of configuration, and a joint-rate weighting matrix. These quantities are used to form a fully constrained linear system by row augmenting the manipulator Jacobian with a weighted basis of its nullspace and augmenting the desired hand motion with a vector function of the nullspace basis. The framework is shown to be flexible, computationally efficient, and accurate.

The use of robots in hostile environments significantly increases the likelihood of failures in the robot's subsystems. Existing techniques for developing failure tolerant robots rely on effective failure detection and identification. Since failure identification is itself a difficult process that may not always be successful, it is important to consider the behavior of the robot prior to identification of a fault, or even the possibility of failures remaining unidentified. This work proposes control strategies that improve local measures of failure tolerance for kinematically redundant robots experiencing unidentified locked-joint failures. Measures to evaluate the fault tolerance capability of the various schemes are presented and the performance of the proposed schemes are demonstrated with an example.

Teleoperated robots in harsh environments have a significant likelihood of failures. A common type of failure such as that of a joint "locking up", when unidentified by the robot controller, can cause considerable performance degradation in the local behavior of the manipulator even for simple point-to-point motion tasks. The effects of a failure become more critical for a system with a human in the loop, where unpredictable behavior of the robotic arm can completely disorient the operator. In this experimental study involving teleoperation of a graphically simulated kinematically redundant manipulator, two control schemes, the pseudo-inverse and a proposed failure-tolerant inverse, were randomly presented under both non-failure and failure scenarios to a group of operators. Based on the performance measures derived from the recorded trajectory data and operator responses, it is seen that the failure-tolerant inverse kinematic control scheme improved the performance of the human/robot system.

Considers real-time fault-tolerant control of kinematically redundant manipulators to single locked-joint failures. The fault-tolerance measure used is a worst-case quantity, given by the minimum, over all single joint failures, of the minimum singular value of the post-failure Jacobians. Given any end-effector trajectory, the goal is to continuously follow this trajectory with the manipulator in configurations that maximize the fault-tolerance measure. The computation required to track these optimal configurations with brute-force methods is prohibitive for real-time implementation. We address this issue by presenting algorithms that quickly compute estimates of the worst-case fault-tolerance measure and its gradient. Comparisons show that the performance of the best method is indistinguishable from that of brute-force implementations. An example demonstrating the real-time performance of the algorithm on a commercially available seven degree-of-freedom manipulator is presented.

We present a computationally efficient algorithm for the eigenspace decomposition of correlated images. Our approach is motivated by the fact that for a planar rotation of a two-dimensional image, analytical expressions can be given for the eigendecomposition, based on the theory of circulant matrices. These analytical expressions turn out to be good first approximations of the eigendecomposition, even for three-dimensional objects rotated about a single axis. We use this observation to automatically determine the dimension of the subspace required to represent an image with a guaranteed user-specified accuracy, as well as to quickly compute a basis for the subspace. Examples show that the algorithm performs very well on a range of test images composed of three-dimensional objects rotated about a single axis.

Robots are frequently used for operations in hostile environments. The very nature of these environments, however, increases the likelihood of robot failures. Common failure tolerance techniques rely on effective failure detection. Since a failure may not always be successfully detected, or even if detected, may not be detected soon enough, it becomes important to consider the behavior of manipulators with undetected failures. This work focuses on developing techniques to analyse a manipulator's workspace and identify regions in which tasks, characterized by sequences of point-to-point moves, can be completed even with such failures. Measures of fault tolerance are formulated to allow for the evaluation of the workspace.

Fault tolerance is an important design criterion for robotic systems operating in hazardous or remote environments. This article addresses the issue of tolerating a free-swinging joint failure by focusing on how to best configure a slow-moving manipulator before a failure. Three scalar measures of fault susceptibility are defined using joint torques/forces, accelerations, and swing angles. Minimizing these measures is an approach to achieving fault tolerance, and for this, algorithms to calculate their gradients are also given. The formulas are valid for general n-link manipulators.

Robotic joint failures are directly characterized and measured in joint space. A locking failure, for example, is one for which a joint cannot move, and it gives an error equal to the desired value minus the locked value. This article extends the joint-space characterization to Euclidean space by measuring a failure's effect there. The approach is based on a primitive measure of point error that can be defined to be distance or path length. It is used to form comprehensive measures through weighted integration over Euclidean-space regions. For kinematically redundant manipulators, minimizing the measures can be used to induce failure tolerance by either reducing the likelihood of collision-induced damage before a failure or reducing end-effector error after a failure. Examples for both cases are given.

Operations in hazardous or remote environments are invariably performed by robots. The hostile nature of the environments, however, increase the likelihood of failures for robots used in such applications. The difficulty and delay in the detection and consequent correction of these faults makes the post-fault performance of the robots particularly important. This work investigates the behavior of robots experiencing undetected locked-joint failures in a general class of tasks characterized by point-to-point motion. The robot is considered to have "converged" to a task position and orientation if all its joints come to rest when the end-effector is at that position. It is seen that the post-fault behavior may be classified into three categories: (1) the robot converges to the task position; (2) the robot converges to a position other than the task position; or (3) the robot does not converge, but keeps moving forever. The specific conditions for convergence are identified, and the different behaviors illustrated with examples of simple planar manipulators.

This work considers real-time fault-tolerant control of kinematically redundant manipulators with single locked-joint failures. The fault-tolerance measure used is a worst-case quantity, given by the minimum, over all single joint failures, of the minimum singular value of the post-failure Jacobians. Given any end-effector trajectory, the goal is to continuously follow this trajectory with the manipulator in configurations that maximize the fault-tolerance measure. The computation required to track these optimal configurations with brute-force methods is prohibitive for real-time implementation. We address this issue by presenting algorithms that quickly compute estimates of the worst-case fault-tolerance measure and its gradient. Real-time implementations are presented for all these techniques, and comparisons show that the performance of the best is indistinguishable from that of brute-force implementations.

This paper studies the degree to which the kinematic redundancy of a manipulator may be utilized for failure tolerance. A redundant manipulator is considered to be fault tolerant with respect to a given task if it is guaranteed to be capable of performing the task after any one of its joints has failed and is locked in place. A method is developed for determining the necessary constraints which insure the failure tolerance of a kinematically redundant manipulator with respect to a given critical task. This method is based on estimating the bounding boxes enclosing the self-motion manifolds for a given set of critical task points. The intersection of these bounding boxes provides a set of artificial joint limits that may guarantee the reachability of the task points after a joint failure. An algorithm for dealing with the special case of 2-D self-motion surfaces is presented, These techniques are illustrated on a PUMA 560 that is used for a 3-D Cartesian positioning task.

We are developing a new graduate program at Purdue in Video and Image Systems Engineering (VISE). The project is comprised of three parts: a new curriculum centered around a degree option in VISE to be earned as part of the Masters or Ph.D. degrees; a state-of-the-art lecture/laboratory facility for instruction, laboratory experiments, and project and homework activities in VISE courses; and enhancement of existing courses and development of new courses in the VISE area.

Fault tolerance is an important design criterion for robotic systems operating in hazardous or remote environments. This article addresses the issue of tolerating a free-swinging joint failure by focusing on how to best configure a slow-moving manipulator before a failure. Three scalar measures of fault susceptibility are defined using joint torques/forces, acceleration, and swing angles. Minimizing these measures is an approach to achieving fault tolerance, and for this, algorithms to calculate their gradients are given. The formulas are valid for general n-link manipulators.

Visual assembly inspection can provide a low cost, accurate, and efficient solution to the automated assembly inspection problem, which is a crucial component of any automated assembly manufacturing process. The performance of such an inspection system is heavily dependent on the placement of the camera and light source. This article presents new algorithms that use the CAD model of a finished assembly for placing the camera and light source to optimize the performance of an automated assembly inspection algorithm. This general-purpose algorithm utilizes the component material properties and the contact information from the CAD model of the assembly, along with standard computer graphics hardware and physically accurate lighting models, to determine the effects of camera and light source placement on the performance of an inspection algorithm. The effectiveness of the algorithms is illustrated on a typical mechanical assembly.

When a manipulator suffers a joint failure, its performance can be significantly affected. If the failed joint is locked, the resulting manipulator Jacobian is given by the original Jacobian, except that the column associated with the failed joint is removed. The rank of the resulting Jacobian then determines if the manipulator still has the ability to perform arbitrary end-effector motions. Unfortunately, even at an operating configuration that has a relatively high manipulability index, a joint failure may still result in a singular Jacobian. This work examines the problem of determining the reduced manipulability of a manipulator after one or more joint failures. Configurations that result in a minimal reduction of the manipulability index for any set of joint failures are determined.

In this paper, we develop a novel multiscale stochastic image model to describe the appearance of a complex threedimensional object in a two-dimensional monochrome image.This formal image model is used in conjunction with Bayesian estimation techniques to perform automated inspection.The model is based on a stochastic tree structure in which each node is an important subassembly of the three-dimensional object.The data associated with each node or subassembly is modeled in a wavelet domain.We use a fast multiscale search technique to compute the sequential MAP (SMAP) estimate of the unknown position, scale factor, and 2-D rotation for each subassembly.The search is carried out in a manner similar to a sequential likelihood ratio test, where the process advances in scale rather than time.The results of this search determine whether or not the object passes inspection.A similar search is used in conjunction with the EM algorithm to estimate the model parameters for a given object from a set of training images.The performance of the algorithm is demonstrated on two different real assemblies. I. INTRODUCTIONF ORMAL mathematical image models have long been used in the design of image processing algorithms for applications such as compression, restoration, and enhancement [1].Such models are traditionally low level stochastic models of limited complexity.In recent years, however, important theoretical advances and increasingly powerful computers have led to more complex and sophisticated image models.Depending on the application, researchers have proposed both low-level and high-level models.Low-level image models describe the behavior of individual image pixels relative to one another.Markov random fields and other spatial interaction models have proven useful for a variety of applications, including image segmentation and restoration [2]; [3].Bouman and Shapiro [4], along with Willsky, Benveniste, and their associates [5], [6], have developed multiscale stochastic models for image data.High-level models are generally used to describe a more restrictive class of images.These models describe larger struc-

In this paper we develop a general multiscale stochastic object detection algorithm for use in an automated inspection application. Information from a CAD model is used to initialize the object model and guide the training phase of the algorithm. An object is represented as a stochastic tree, where each node of the tree is associated with one of the various object components used to locate and identify the part. During the training phase a number of model parameters are estimated from a set of training images, some of which are generated from the CAD model. The algorithm then uses a fast multiscale search strategy to locate and identify the subassemblies making up the object tree. We demonstrate the performance of the algorithm on a typical mechanical assembly.>

We present a global motion planner for tracing curves in three dimensions with robot manipulator tool frames. This planner generates an efficient motion satisfying three types of constraints: constraints on the tool tip for curve tracing, robot kinematic constraints and robot link collision constraints. Motions are planned using a global search algorithm and a local planner based on a potential-field approach. This planner can be used with any robots including redundant manipulators and can control the trade-offs between its algorithmic completeness and computation time. It can be applied in many robotic tasks such as seam welding, caulking, edge deburring and chamfering, and is expected to reduce motion programming times from days to minutes.>

An important part of a robust automated assembly process is an accurate and efficient method for the inspection of finished assemblies. This paper presents a novel multiscale assembly inspection algorithm that is used to detect errors in an assembled product. The algorithm is trained on synthetic images generated using the CAD model of the different components of the assembly. The CAD model guides the inspection algorithm through its training stage by addressing the different types of variations that occur during manufacturing and assembly. Those variations are classified into those that can affect the functionality of the assembled product and those that are unrelated to its functionality. Using synthetic images in the training process adds to the versatility of the technique by removing the need to manufacture multiple prototypes and control the lighting conditions. Once trained on synthetic images, the algorithm can detect assembly errors by examining real images of the assembled product. The effectiveness of the system is illustrated on a typical mechanical assembly.>

The high cost involved in the retrieval and repair of robotic manipulators used for remediating nuclear waste, processing hazardous chemicals, or for exploring space or the deep sea, places a premium on the reliability of the system as a whole. For such applications, kinematically redundant manipulators are inherently more reliable since the additional degrees of freedom (DOF) may compensate for a failed joint. In this work, a redundant manipulator is considered to be fault tolerant with respect to a given task if it is guaranteed to be capable of performing the task after any one of its joints has failed and is locked in place. A method is developed for insuring the failure tolerance of kinematically redundant manipulators with respect to a given critical task. Techniques are developed for analyzing the manipulator's workspace to find regions which are inherently suitable for critical tasks due to their relatively high level of failure tolerance. Then, constraints are imposed on the range of motion of the manipulator to guarantee that a given task is completable regardless of which joint fails. These concepts are illustrated for a PUMA 560 that is used for a three-dimensional positioning task.>

This paper provides a set of algorithms which allow qualitative information regarding the connectivity of configuration space to be quickly established. A mechanism is presented which utilizes these results to determine the effects of the motions of one manipulator on the configuration space of the other. These algorithms are then used as a basis for a simple planner which is capable of rapidly computing collision-free paths for multiple SCARA manipulators operating within overlapping workspaces.>

Kinematically redundant manipulators are inherently capable of more dextrous manipulation due to their additional degrees of freedom. To achieve this dexterity, however, one must be able to efficiently calculate the most desirable configuration from the infinite number of possible configurations that satisfy the end-effector constraint. It has been previously shown that the singular value decomposition (SVD) plays a crucial role in doing such calculations. In this work, a parallel algorithm for calculating the SVD is incorporated into a computational scheme for solving the equations of motion for kinematically redundant systems. This algorithm, which generalizes the damped least squares formulation to include solutions that utilize null-space projections and task prioritization as well as augmented or extended Jacobians, is then implemented on a simple linear array of processing elements. By taking advantage of the error bounds on the perturbation of the SVD, it is shown that an array of only four AT&T DSP chips can result in control cycle times of less than 3 ms for a seven degree-of-freedom manipulator.>

This work describes the development of a student model that is used in a Japanese language intelligent tutoring system to assess a pupil's proficiency at reading one of the distinct orthographies of Japanese, known as katakana. While the effort required to memorize the relatively few katakana symbols and their associated pronunciations is not prohibitive, a major difficulty in reading katakana is associated with the phonetic modifications which occur when English words which are transliterated into katakana are made to conform to the more restrictive rules of Japanese phonology. The algorithms described here are able to automatically acquire a knowledge base of these phonological transformation rules, use them to assess a student's proficiency, and then appropriately individualize the student's instruction.>

This work considers the path planning problem for planar revolute manipulators operating in a workspace of polygonal obstacles. This problem is solved by determining the topological characteristics of obstacles in configuration space, thereby determining where feasible paths can be found. A collision-free path is then calculated by using the mathematical description of the boundaries of only those configuration space obstacles with which collisions are possible. The key to this technique is a simple test for determining whether two disjoint obstacles are connected in configuration space. This test allows the path planner to restrict its calculations to regions in which collision-free paths are guaranteed a priori, thus avoiding unnecessary computations and resulting in an efficient implementation. Typical timing results for environments consisting of four polyhedral obstacles comprising a total of 27 vertices are of the order of 22 ms on a SPARC-IPC workstation.>

The problem of path planning for two planar robot manipulators that cooperate in carrying a rectangular object from an initial position and orientation to a destination position and orientation in a 2-D environment is investigated. The two robot arms, the carried object, and the straight line connecting the two robot bases are modeled as a 6-link closed chain. The problem of path planning for the chain is solved by two major algorithms: a collision-free feasible-configuration-finding algorithm and a collision-free path-finding algorithm. The former maps the free space in the Cartesian world space to the robot's joint space in which all the collision-free feasible configuratiions (CFFCs) for the 6-link closed chain are found. The latter builds a connection graph representing the CFFCs and the transitions between any two groups of CFFCs at adjacent joint intervals. A graph search method is employed to find a collision-free path for each joint of both manipulators.>

The authors present a parallel algorithm for solving the equations of motion for kinematically redundant robotic systems. This algorithm, which relies on the calculation of the singular value decomposition (SVD), is implemented on a simple linear array of processing elements. By taking advantage of the error bounds on the perturbation of the SVD, it is shown that an array of only four AT&T DSP (digital signal processor) chips can result in control cycle times of less than 3 ms for a seven degree-of-freedom manipulator.>

A kinematically redundant manipulator is a robotic system that has more than the minimum number of degrees of freedom that are required for a specified task. Due to this additional freedom, control strategies may yield solutions which are not repeatable in the sense that the manipulator may not return to its initial joint configuration for closed end effector paths. The authors present two methods for choosing repeatable control strategies which minimize their distance from a non-repeatable inverse with desirable properties. The first method minimizes the integral norm of the difference of the desired inverse and a repeatable inverse. While this is the more appropriate criterion, it results in a difficult optimization. The second method, which minimizes the distance of the null vectors associated with the desired and the repeatable inverses, is somewhat easier to implement. As an illustrative example the pseudoinverse is approximated in a region of the joint space using both techniques.>

Kinematically redundant manipulators, by definition, possess an infinite number of generalized inverse control strategies for solving the Jacobian equation. These control strategies are not, in general, repeatable in the sense that closed trajectories for the end-reflector do not result in closed trajectories in the joint space. The Lie bracket condition (LBC) can be used to check for the possibility of integral surfaces, also called stable surfaces, which define regions of repeatable behavior. However, the LBC is only a necessary condition. A necessary and sufficient condition for the existence of stable surfaces is used to illustrate that such surfaces are much rarer than previously thought. A technique for designing a repeatable control that is nearest, in an integral norm sense, to a desired optimal control is presented. The desired optimal control is allowed to take the form of any generalized inverse. An example is presented that illustrates the capability of designing repeatable controls that approximate the behavior of desired optimal inverses in selected regions of the workspace.>

The kinematic specification of motion for redundant manipulators has relied primarily on a formulation that treats the redundant degrees of freedom as independent of those required to maintain a desired end effector trajectory. While such a formulation is conceptually appealing, it has been shown to be physically inaccurate when applied to the kinetic behavior of redundant manipulators. The kinetic effects of homogeneous solutions are analyzed with emphasis on placing realistic limitations on how redundancy can be utilized without adversely affecting the primary goal of a desired end effector trajectory. It is shown that it is possible to identify manipulator configurations that possess the desirable characteristic of being able either to remove or to impart a homogeneous velocity while simultaneously reducing the torque requirements on the manipulator. The conditions that govern these configurations are shown to be directly related to the conditions for guaranteeing global stability for the local torque minimization formulation.>

A measure of fault tolerances for redundant manipulators is derived based on the remaining dexterity following the loss of degree of freedom. Using this measure as a criterion, a technique for calculating optimal fault tolerant configurations for redundant manipulators is presented. The properties of these configurations are analyzed in order to assist designers in determining the number of degrees of freedom required to maintain a minimum level of dexterity under a worst-case scenario.>

The kinematic specification of motion for redundant manipulators has relied primarily on a formulation which treats the redundant degrees of freedom as independent from those required to maintain a desired end-effector trajectory. While such a formulation is conceptually appealing, it has been shown to be physically inaccurate when applied to the kinetic behavior of redundant manipulators. Here, the kinetic effects of homogeneous solutions are analyzed with emphasis on placing realistic limitations on how redundancy can be utilized without adversely affecting the primary goal of a desired end-effector trajectory. It is shown that it is possible to identify manipulator configurations which possess the desirable characteristic of being able to either remove or impart a homogeneous velocity while simultaneously reducing the torque requirements on the manipulator. The conditions which govern these configurations are shown to be directly related to the conditions for guaranteeing global stability for the local torque minimization formulation.>

The author describes the human-computer interaction of an intelligent tutoring system designed to mediate some of the difficulties faced by an English-speaking person trying to acquire proficiency in reading technical Japanese material. A brief summary of some of the unique characteristics of the Japanese language is included.>

Modeling techniques for animating legged figures are described which are used in the PODA animation system. PODA utilizes pseudoinverse control in order to solve the problems associated with manipulating kinematically redundant limbs. PODA builds on this capability to synthesize a kinematic model of legged locomotion which allows animators to control the complex relationships between the motion of the body of a figure and the coordination of its legs. Finally, PODA provides for the integration of a simple model of legged locomotion dynamics which insures that the accelerations of a figure's body are synchronized with the timing of the forces applied by its legs.