The path and location planning of workpieces by genetic algorithms

This paper presents the planning of a near-optimum path and location of a workpiece by genetic algorithms. The purpose of this planning is to minimize the processing time required for a robot to complete its work on a workpiece. The location of the workpiece can be anywhere by translating it along any direction and by rotating it about the fixedz-axis of the robot coordinate system. Owing to the changeable location of the workpiece and the alterable motion time required for a robot to move between two workpoints, the path and location planning problem is much more complicated than the travelling salesman problem. It is definitely impossible to obtain an optimum path and location within an acceptable time. In this paper, genetic algorithms are applied to solve this problem. The location of the workpiece is defined by three position parameters and one angular parameter, and the path is determined based on the values of the parameters for all workpoints. All the path and location parameters are encoded into a binary string. They are modified simultaneously by genetic algorithms to search for a global solution. As the workpiece can be anywhere, a penalty function is used to prevent the selection of illegal paths. Two experiments are given to show the performance of genetic algorithms: one has 30 workpoints and the other has 50 workpoints. Compared with four human-generated plannings, planning by genetic algorithms has much better performance in minimizing the processing time.     

Simultaneous localization of multiple unknown CSMA-based wireless sensor network nodes using a mobile robot with a directional antenna

We use a single mobile robot equipped with a directional antenna to simultaneously localize unknown carrier sensing multiple access (CSMA)-based wireless sensor network nodes. We assume the robot can only sense radio transmissions at the physical layer. The robot does not know network configuration such as size and protocol. We formulate this new localization problem and propose a particle filter-based localization approach. We combine a CSMA model and a directional antenna model using multiple particle filters. The CSMA model provides network configuration data while the directional antenna model provides inputs for particle filters to update. Based on the particle distribution, we propose a robot motion planning algorithm that assists the robot to efficiently traverse the field to search radio source. The final localization scheme consists of two algorithms: a sensing algorithms that runs in O(n) time for n particles and a motion planning algorithm that runs in O(nl) time for l radio sources. We have implemented the algorithm, and the results show that the algorithms are capable of localizing unknown networked radio sources effectively and robustly.     

Optimal switch location in mobile communication networks using hybrid genetic algorithms

The optimal positioning of switches in a mobile communication network is an important task, which can save costs and improve the performance of the network. In this paper we propose a model for establishing which are the best nodes of the network for allocating the available switches, and several hybrid genetic algorithms to solve the problem. The proposed model is based on the so-called capacitated p-median problem, which have been previously tackled in the literature. This problem can be split in two subproblems: the selection of the best set of switches, and a terminal assignment problem to evaluate each selection of switches. The hybrid genetic algorithms for solving the problem are formed by a conventional genetic algorithm, with a restricted search, and several local search heuristics. In this work we also develop novel heuristics for solving the terminal assignment problem in a fast and accurate way. Finally, we show that our novel approaches, hybridized with the genetic algorithm, outperform existing algorithms in the literature for the p-median problem.     

Near-Optimum Folding for a Reconfigurable Snake-Like Robot

To improve reachability of a snake-like robot depending on the problem, the links of the robot need to be resizable. In such a case folding links of the robot help to better plan obstacle avoidance. Optimum folding of the robot is the aim of our paper. We introduce a practical idea to construct reconfigurable and resizable snake robots which can be folded and an approximation algorithm to find near-optimum folding for the robot. Since an open chain is an abstract model of a snake-like robot, folding algorithms for the proposed robot are given in terms of an open chain. Ruler folding is a well-known NP-Complete problem. It considers folding of an n-link open chain linkage to the minimum length. The best previously known approximation algorithm for this problem has been developed by Hopcroft et al. They achieved the upper bound of 2m ₁ for the length of the folded chain in all cases, where m ₁ is the length of the longest link of the given chain. Already there are no any algorithms for open chain folding which guarante that the folded length of the open chain is less than 2m ₁. In this paper, we introduce an approximation algorithm which runs in O (n log n) using O (n) space. We introduce a function for the upper bound of the folded chain which depends to the lengths of all links in the given chain. Our experimental results show that for more than 95% of the problem instances we can achieve the same results in O (n) time. Using our folding algorithm, we can design the length of each link in an open chain to get x · m ₁ folded length where 1 < x < 2 is given and m ₁ is the length of the longest link of the chain. We introduce how to design a snake-like robot for which it can be folded in the given interval.     

Motion planning algorithms of an omni-directional mobile robot with active caster wheels

This work deals with motion planning algorithms of an omni-directional mobile robot with active caster wheels. A typical problem occurred in the motion control of such omni-directional mobile robot, which has been identified through experimental experiences, is skidding of the mobile wheel. It sometimes results in uncertain rotation of the steering wheel. To cope with this problem, a motion planning algorithm which resolves the skidding problem and uncertain motions of the steering wheel is mainly investigated. For navigation of the mobile robot, the posture of the omni-directional mobile robot is initially calculated using the odometry information. Then, the accuracy of the mobile robot’s odometry is measured through comparison of the odometry information and the external sensor measurement. Finally, for successful navigation of the mobile robot, a motion planning algorithm that employs kinematic redundancy resolution method is proposed. Through simulations and experimentation, the feasibility of proposed algorithms was verified.     

Obstacle Collision Detection Using Best Ellipsoid Fit

This paper describes a method for estimating the distance between a robot and its surrounding environment using best ellipsoid fit. The method consists of the following two stages. First we approximate the detailed geometry of the robot and its environment by minimum-volume enclosing ellipsoids. The computation of these ellipsoids is a convex optimization problem, for which efficient algorithms are known. Then we compute a conservative distance estimate using an important but little known formula for the distance of a point from and n-dimensional ellipse. The computation of the distance estimate (and its gradient vector) is shown to be an eigenvalue problem, whose solution can be rapidly found using standard techniques. We also present an incremental version of the distance computation, which takes place along a continuous trajectory taken by the robot. We have implemented the proposed approach and present some preliminary results.     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

Particle Filter for Collaborative Multi-Robot Localization Tolerant to Recognition Error

Statistical algorithms using particle filters have been proposed previously for collaborative multi-robot localization. In these algorithms, by synchronizing each robot's belief or exchanging the particles of the robots, fast and accurate localization is attained. However, there algorithms assume correct recognition of other robots and the effects of recognition error are not considered. If the recognition of other robots is incorrect, a large amount of error in localization can occur. This paper describes this problem. Furthermore, in order to cope with the problem, an algorithm for collaborative multi-robot localization is proposed. In the proposed algorithm, the particles of a robot are exchanged with those of other robots according to measurement results obtained by the sending robot. At the same time, some particles remain in the sending robot. Received particles from other robots are evaluated using measurement results obtained by the receiving robot. The proposed method copes with recognition error by using the remaining particles, and increases the accuracy of estimation by twice evaluating the exchanged particles of the sending and receiving robots. These properties of the proposed method are argued mathematically. Simulation results show that incorrect recognition of other robots does not cause serious problems in the proposed method.     

Generating gaits for snake robots: annealed chain fitting and keyframe wave extraction

Snake robots have many degrees of freedom, which makes them both extremely versatile and complex to control. They are often controlled with gaits, coordinated cyclic patterns of joint motion. Using gaits simplifies the design of high-level controllers, but shifts the complexity burden to designing the gaits. In this paper, we address the gait design problem by introducing two algorithms: Annealed chain fitting and Keyframe wave extraction. Annealed chain fitting efficiently maps a continuous backbone curve describing the three-dimensional shape of the robot to a set of joint angles for a snake robot. Keyframe wave extraction takes joint angles fit to a sequence of backbone curves and identifies parameterized periodic functions that produce those sequences. Together, they allow a gait designer to conceive a motion in terms three-dimensional shapes and translate them into easily manipulated wave functions, and so unify two previously disparate gait design approaches. We validate the algorithms by using them to produce rolling and sidewinding gaits for crawling and climbing, with results that match previous empirical investigations.     

A collaborative localization tolerant to recognition error by double-check particle exchange

Statistical algorithms using particle filters for collaborative multi-robot localization have been proposed. In these algorithms, by synchronizing every robot’s belief or exchanging particles of the robots with each other, fast and accurate localization is attained. These algorithms assume correct recognition of other robots, and the effects of recognition errors are not discussed. However, if the recognition of other robots is incorrect, a large amount of error in localization can occur. This article describes this problem. Furthermore, an algorithm for collaborative multi-robot localization is proposed in order to cope with this problem. In the proposed algorithm, the particles of a robot are sent to other robots according to measurement results obtained by the sending robot. At the same time, some particles remain in the sending robot. Particles received from other robots are evaluated using measurement results obtained by the receiving robot. The proposed method is tolerant to recognition error by the remaining particles and evaluating the exchanged particles in the sending and receiving robots twice, and if there is no recognition error, the proposed method increases the accuracy of the estimation by these two evaluations. These properties of the proposed method are argued mathematically. Simulation results show that incorrect recognition of other robots does not cause serious problems in the proposed method.     

机器人运动规划方法的研究

针对路径规划以及碰撞检测这一研究的重点问题,提出了G-空间法、人工势力场法、遗传算法等。序列规划问题一般转化为旅行商问题来求解。在综合现有序列规划和路径规划方法的基础上,提出两种机器人运动规划算法：基于任意路径的运动规划算法和基于直线路径的运动规划算法,思路简单,能对各种机器人工程任务进行运动规划。     

Robot calibration by mobile camera systems

A measurement technique for kinematic calibration of robot manipulators, which uses a stereo hand-eye system with moving camera coordinates, is presented in this article. The calibration system consists of a pair of cameras rigidly mounted on the robot end-effector, a camera calibration board, and a robot calibration fixture. The stereo cameras are precalibrated using the camera calibration board so that the 3D coordinates of any object point seen by the stereo cameras can be computed with respect to the camera coordinate frame [C] defined by the calibration board. Because [C] is fixed with respect to the tool frame [T] of the robot, it moves with the robot hand from one calibration measurement configuration to another. On each face of the robot calibration fixture that defines the world coordinate frame [W], there are evenly spaced dot patterns of uniform shape. Each pattern defines a coordinate frame [E_i], whose pose is known in [W]. The dot pattern is designed in such a way that from a pair of images of the pattern, the pose of [E_i] can be estimated with respect to [C] in each robot calibration measurement. By that means the pose of [C] becomes known in [W] at each robot measurement configuration. For a sufficient number of measurement configurations, the homogeneous transformation from [W] to [C] (or equivalently to [T]), and thus the link parameters of the robot, can be identified using the least-squares techniques. Because the cameras perform local measurements only, the field-of-view of the camera system can be as small as 50 × 50 mm², resulting in an overall accuracy of the measurement system as high as 0.05 mm. This is at least 20 times better than the accuracy provided by vision-based measurement systems with a fixed camera coordinate frame using common off-the-shelf cameras. © 1994 John Wiley & Sons, Inc.     

Evolutionary Path Planning Algorithm for Industrial Robots

This paper proposed a new methodology to solve collision free path planning problem for industrial robot using genetic algorithms. The method poses an optimization problem that aims to minimize the significant points traveling distance of the robot. The behavior of more two operational parameters – the end effector traveling distance and computational time – are analyzed. This algorithm is able to obtain the solution for any industrial robot working in the complex environments, just it needs to choose a suitable significant points for that robot. An application example has been illustrated using robot Puma 560.     

Multi-objective path planning in discrete space

Finding a path for a robot which is near to natural looking paths is a challenging problem in motion planning. This paper suggests two single and multi-objective optimization models focusing on length and clearance of the path in discrete space. Considering the complexity of the models and potency of evolutionary algorithms we apply a genetic algorithm with NSGA-II framework for solving the problems addressed in the models. The proposed algorithm uses an innovative family of path refiner operators, in addition to the standard genetic operators. The new operators intensify explorative power of the algorithm in finding Pareto-optimal fronts in the complicated path planning problems such as narrow passages and clutter spaces. Finally, we compare efficiency of the refiner operators and the algorithm with PSO and A* algorithms in several path planning problems.     

Simultaneous localization and mapping using the Geometric Projection Filter and correspondence graph matching

A common way of localization in robotics is using triangulation on a system composed of a sensor and some landmarks (which can be artificial or natural). First, when no identifying marks are set on the landmarks, their identification by a robust algorithm is a complex problem which may be solved using correspondence graphs. Secondly, when the localization system has no a priori information about its environment, it has to build its own map in parallel with estimating its position, a problem known as simultaneous localization and mapping (SLAM). Recent works have proposed to solve this problem based on building a map made of invariant features. This paper describes the algorithms and data structure needed to deal with landmark matching, robot localization and map building in a single efficient process, unifying the previous approaches. Experimental results are presented using an outdoor robot car equipped with a two-dimensional scanning laser sensor.     

Completion time variance minimization in single machine and multi-machine systems

In this paper we consider the problem of minimizing the completion time variance of n jobs on a single machine with deterministic processing times. We propose a new heuristic and compare the results with existing popular heuristics for the problem. We also propose a method based on genetic algorithms to solve the problem. We present the worst case performance analysis of the proposed heuristic. We also consider the problem of minimizing the completion time variance of n jobs on m identical parallel machines in both restricted and unrestricted versions. A heuristic method and a method based on genetic algorithms are presented for both the cases and results of computational testing are provided. It is concluded that the proposed methods provide better results compared to existing methods for the single machine case as well as for the multi-machine case.     

An observer-based set-point controller for robot manipulators with flexible joints

We present a globally asymptotically stable controller for point-to-point regulation of robot manipulators with flexible joints that uses only position measurement on the motor side. Existing asymptotically stable schemes for the set point regulation problem without velocity measurement address only the rigid robot case. Furthermore, these solutions ensure only local stability provided some bounds on the dynamic part of the robot model are known. Also, they require the injection of high gains into the loop to enlarge the equilibrium domain of attraction. In contrast, our solution is global, applies for robots with flexible joints and assumes only that the gravity forces are known. The underlying rationale of the design is to ‘shape’ the potential energy of the closed loop system so that it has an absolute minimum at the desired equilibrium, and add the required dampingto achieve asymptotic stability. This is attained by adding a (linear) observer that converges to the position required to compensate the gravity forces and injects the damping, and a ‘spring-like’ effect between the observer and the robot that ‘pulls’ the robot to the desired target. This approach to observer-based controller design differs from the classical certainly equivalent approach and effectively exploits the dynamic properties of the physical system.     

Parametric algorithms for 2-cyclic robot scheduling with interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, that is, schedules in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and operation durations are chosen from prescribed intervals. A strongly polynomial algorithm of time complexity O(m ⁸log m) is proposed.     

A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines

This paper presents a hybrid memetic algorithm for the problem of scheduling n jobs on m unrelated parallel machines with the objective of maximizing the weighted number of jobs that are completed exactly at their due dates. For each job, due date, weight, and the processing times on different machines are given. It has been shown that when the numbers of machines are a part of input, this problem is NP-hard in the strong sense. At first, the problem is formulated as an integer linear programming model. This model is practical to solve small-size problems. Afterward, a hybrid memetic algorithm is implemented which uses two heuristic algorithms as constructive algorithms, making initial population set. A data oriented mutation operator is implemented so as to facilitate memetic algorithm search process. Performance of all algorithms including heuristics (H1 and H2), hybrid genetic algorithm and hybrid memetic algorithm are evaluated through computational experiments which showed the capabilities of the proposed hybrid algorithm.     

基于文化算法的家庭服务机器人任务规划

通过对家庭服务机器人任务规划问题进行形式化描述,给出了问题的求解模型,提出了一种改进的文化算法,通过算法中信念空间和种群空间的相互联系和相互促进实现求解。算法采用独特的编码方式,其种群空间采用遗传算法作为进化手段,采用较为独特的信念提取方式构造算法的信念空间并促使其进化。将该算法用于家庭服务机器人大赛的仿真平台上,证明其有效性。