Optimal path planning of multiple nanoparticles in continuous environment using a novel Adaptive Genetic Algorithm

Highlights

• Presenting an efficient method for precise path planning in nanomanipulation.

• Obtaining optimal curved path for several nanoparticles in continuous environment.

• Objective function consists of manipulation effort, smoothness, and roughness.

• Multiple particle path planning by an intelligent co-evolutionary algorithm.

• Evaluation of method’s performance for complex nanomanipulation assembly tasks.

Abstract

This paper presents a novel Adaptive Genetic Algorithm for optimal path planning of multiple nanoparticles during the nanomanipulation process. The proposed approach determines the optimal manipulation path in the presence of surface roughness and environment obstacles by considering constraints imposed on the nanomanipulation process. In this research, first by discretizing the environment, an initial set of feasible paths were generated, and then, path optimization was continued in the original continuous environment (and not in the discrete environment). The presented novel approach for path planning in continuous environment (1) makes the algorithm independent of grid size, which is the main limitation in conventional path planning methods, and (2) creates a curve path, instead of piecewise linear one, which increases the accuracy and smoothness of the path considerably. Every path is evaluated based on three factors: the displacement effort (the area under critical force-time diagram during nanomanipulation), surface roughness along the path, and smoothness of the path. Using the weighted linear sum of the mentioned three factors as the objective function provides the opportunity to (1) find a path with optimal value for all factors, (2) increase/decrease the effect of a factor based on process considerations. While the former can be obtained by a simple weight tuning procedure introduced in this paper, the latter can be obtained by increasing/decreasing the weight value associated with a factor. In the case of multiple nanoparticles, a co-evolutionary adaptive algorithm is introduced to find the best destination for each nanoparticle, the best sequence of movement, and optimal path for each nanoparticle. By introducing two new operators, it was shown that the performance of the presented co-evolutionary mechanism outperforms the similar previous works. Finally, the proposed approach was also developed based on a modified Particle Swarm Optimization algorithm, and its performance was compared with the proposed Adaptive Genetic Algorithm.

Introduction

In recent years many nanorobotic systems have emerged [1,2] and the atomic force microscope is widely used for nanoparticle research [[3], [4], [5]]. The nanomanipulation technique using AFM-based nanorobotic system was developed to manufacture nanoscale patterns by pushing nanoparticles. In this approach, relative movement of the cantilever with respect to particles is used for nano-assembly. Nanomanipulation operation traditionally has been performed using haptic devices [6], computer-aided design methods [[7], [8], [9]], or cooperative parallel imaging/manipulation [10]. As this process is complicated and time-consuming, finding the optimal nanomanipulation path is of crucial importance. Some of the recent works determined the manipulation path by the aid of atomic force microscopy (AFM) [11] or manually [12] which are neither accurate nor efficient. Potential field approach has been adopted to build a virtual reality environment to compensate the lack of real-time visual feedback in AFM [13]. However, the path planning problem might get stuck in local minima of the potential field, and fail to find a solution. Automated manipulation of nanoparticles based on successive pushes along piecewise linear paths was presented in [14,15]. Path planning in the presence of obstacles, parts of environment where cannot be passed, has been shown in [16]. In this research, first linear paths were determined between particles and destinations, and then, piecewise linear paths were built for other nanoparticles which cannot move in straight line. The presented method in [17] extracts the set of paths between particles and destinations using Voronoi diagram and graph theory and finds the optimal path among them by the aid of A^* algorithm. In addition to spherical nanoparticles, a virtual reality toolkit which benefits from haptic guides for obstacle avoidance path planning also developed for carbon nanotubes in [18].

Evolutionary optimization approaches like Genetic Algorithm, Particle Swarm Optimization, and Ant Colony Optimization have also been used for path planning of nanoparticles [19,20]. A hybrid co-evolutionary genetic algorithm for intelligent path planning of multiple nanoparticles has been presented in [20,21]. The presented method is able to (1) find optimal linear or piecewise linear obstacle-free paths in complex environments, and (2) determine the best destination for each nanoparticle and the optimal sequence of movement for particles using the co-evolutionary mechanism in multiple particle path planning problems. However, the main limitations of this research can be stated as follows. First, the quality of the path planning method is limited by the grid size, or discretization resolution, in a discrete environment. Second, while it is shown in [20] that choosing an appropriate destination for each particle (assignment problem: AP) and movement sequence of particles (sequence problem: SP) is highly correlated with the efficiency of the multiple particles path planning, the efficiency of the proposed method can be affected negatively by (1) producing and evaluating several identical solutions during the optimization process, which is highly time-consuming, and (2) using random initial solution for the co-evolutionary mechanism, which decreased the quality of the initial solutions considerably.

In this research, a continuous path planning (CPP) method has been proposed to determine the optimal path for moving nanoparticles during nanomanipulation process. In contrast to conventional path planning methods which provide a piecewise linear path between start and destination points, the presented method is able to find the optimal curve path in every complex environment filled with obstacles and surface roughness. Conventional path planning methods determine the piecewise linear path in a discrete gridded environment. In this situation, the connection between two linear segments usually associates with a sharp direction change. In addition, the path is limited to pass through the edges (or centers) of the grids. Though creating smaller grids makes the path smoother and more accurate, however, it increases the computation load considerably as well. In this research, an efficient approach was presented to determine the curve path with the highest degree of smoothness and avoid sharp direction changes along the path.

In this paper, a novel Adaptive Genetic Algorithm is introduced for optimal path planning of several nanoparticles in the continuous environment. First, an innovative approach to path planning in the continuous environment has been presented. Considering the importance of initial solutions on the performance of evolutionary optimization, a hybrid mechanism is adopted to create a feasible path in any complex environment. By discretizing the continuous environment, a set of near-optimal feasible piecewise linear paths can be obtained using Dijkstra or A^* method. Second, the Genetic Algorithm has been customized with an adaptive mechanism to reduce the dependency of the optimal path to the initial feasible paths and increase its accuracy. Third, the objective function has been designed to find the optimal path during nanomanipulation process. For this purpose, a weighted linear combination of the (1) nanoparticle displacement effort, (2) path smoothness, and (3) surface roughness along the path were evaluated as the path cost. In addition, a practical method for fine tuning the objective function weights was presented. Finally, a co-evolutionary mechanism is presented to deal with multiple particles path planning problem. The presented method is modified such that it can find the best destination for each particle, find the optimal movement sequence of particles, and the optimal path between all particles and destinations in a highly efficient manner. To do so, the co-evolutionary mechanism was modified with two new operators: memory and neighborhood. Saving all unique solutions of the co-evolutionary mechanism enables us to avoid producing and evaluating repeated solutions. Additionally, only the particles in the neighborhood of each destination were used to produce the initial solutions of the co-evolutionary mechanism.