Robot path planning in dynamic environments using a simulated annealing based approach

Mobile robots are widely used in many industrial fields. Research on path planning for mobile robots is one of the most important aspects in mobile robots research. Path planning for a mobile robot is to find a collision-free route, through the robot’s environment with obstacles, from a specified start location to a desired goal destination while satisfying certain optimization criteria. Most of the existing path planning methods, such as the visibility graph, the cell decomposition, and the potential field are designed with the focus on static environments, in which there are only stationary obstacles. However, in practical systems such as Marine Science Research, Robots in Mining Industry, and RoboCup games, robots usually face dynamic environments, in which both moving and stationary obstacles exist. Because of the complexity of the dynamic environments, research on path planning in the environments with dynamic obstacles is limited. Limited numbers of papers have been published in this area in comparison with hundreds of reports on path planning in stationary environments in the open literature. Recently, a genetic algorithm based approach has been introduced to plan the optimal path for a mobile robot in a dynamic environment with moving obstacles. However, with the increase of the number of the obstacles in the environment, and the changes of the moving speed and direction of the robot and obstacles, the size of the problem to be solved increases sharply. Consequently, the performance of the genetic algorithm based approach deteriorates significantly. This motivates the research of this work. This research develops and implements a simulated annealing algorithm based approach to find the optimal path for a mobile robot in a dynamic environment with moving obstacles. The simulated annealing algorithm is an optimization algorithm similar to the genetic algorithm in principle. However, our investigation and simulations have indicated that the simulated annealing algorithm based approach is simpler and easier to implement. Its performance is also shown to be superior to that of the genetic algorithm based approach in both online and offline processing times as well as in obtaining the optimal solution for path planning of the robot in the dynamic environment. The first step of many path planning methods is to search an initial feasible path for the robot. A commonly used method for searching the initial path is to randomly pick up some vertices of the obstacles in the search space. This is time consuming in both static and dynamic path planning, and has an important impact on the efficiency of the dynamic path planning. This research proposes a heuristic method to search the feasible initial path efficiently. Then, the heuristic method is incorporated into the proposed simulated annealing algorithm based approach for dynamic robot path planning. Simulation experiments have shown that with the incorporation of the heuristic method, the developed simulated annealing algorithm based approach requires much shorter processing time to get the optimal solutions in the dynamic path planning problem. Furthermore, the quality of the solution, as characterized by the length of the planned path, is also improved with the incorporated heuristic method in the simulated annealing based approach for both online and offline path planning.

A simulated annealing algorithm for energy efficient virtual machine placement

Improving energy efficiency has become increasingly important in data centers in recent years to reduce the rapidly growing tremendous amounts of electricity consumption. The power dissipation of the physical servers is the root cause of power usage of other systems, such as cooling systems. Many efforts have been made to make data centers more energy efficient. One of them is to minimize the total power consumption of these servers in a data center through virtual machine consolidation, which is implemented by virtual machine placement. The placement problem is often modeled as a bin packing problem. Due to the NP-hard nature of the problem, heuristic solutions such as First Fit and Best Fit algorithms have been often used and have generally good results. However, their performance leaves room for further improvement. In this paper we propose a Simulated Annealing based algorithm, which aims at further improvement from any feasible placement. This is the first published attempt of using SA to solve the VM placement problem to optimize the power consumption. Experimental results show that this SA algorithm can generate better results, saving up to 25 percentage more energy than First Fit Decreasing in an acceptable time frame.

Fabrication of SiGe rings and holes on Si(001) by flash annealing

We show that SiGe islands are transformed into nanoholes and rings by annealing treatments only and without Si capping. Rings are produced by a rapid flash heating at temperatures higher than the melting point of Ge, whereas nanoholes are produced by several minute annealing. The rings are markedly rich in Si with respect to the pristine islands, suggesting that the evolution path from islands to rings is driven by the selective dissolution of Ge occurring at high temperature.

The effect of hydroxyl groups and surface area of hematite derived from annealing goethite for phosphate removal

Synthetic goethite and thermally treated goethite at different temperatures were used to remove phosphate from sewage. The effect of annealing temperature on phosphate removal over time was investigated. X-ray diffraction(XRD), transmission electron microscopy (TEM), N2 adsorption and desorption (BET), and infrared emission spectrum (FT-IES) were utilized to characterize the phase, morphology, specific surface area, pore distribution, and the surface groups of samples. The results show that annealed products of goethite at temperatures over 250 °C are hematite with the similar morphology as the original goethite with different hydroxyl groups and surface area. Increasing temperature causes the decrease in hydroxyl groups, consequential increase in surface area at first and then experiences a decrease (14.8–110.4–12.6 m2/g) and the subsequent formation of nanoscale pores. The variation rate of hydroxyl groups and surface area based on FT-IES and BET, respectively, are used to evaluate the effect of annealing temperature on phosphate removal. By using all of the characterization techniques, it is concluded that the changes of phosphate removal basically result from the total variation rate between hydroxyl groups and surface area.

Dynamic robot path planning using an enhanced simulated annealing approach

Evolutionary computation is an effective tool for solving optimization problems. However, its significant computational demand has limited its real-time and on-line applications, especially in embedded systems with limited computing resources, e.g., mobile robots. Heuristic methods such as the genetic algorithm (GA) based approaches have been investigated for robot path planning in dynamic environments. However, research on the simulated annealing (SA) algorithm, another popular evolutionary computation algorithm, for dynamic path planning is still limited mainly due to its high computational demand. An enhanced SA approach, which integrates two additional mathematical operators and initial path selection heuristics into the standard SA, is developed in this work for robot path planning in dynamic environments with both static and dynamic obstacles. It improves the computing performance of the standard SA significantly while giving an optimal or near-optimal robot path solution, making its real-time and on-line applications possible. Using the classic and deterministic Dijkstra algorithm as a benchmark, comprehensive case studies are carried out to demonstrate the performance of the enhanced SA and other SA algorithms in various dynamic path planning scenarios.

Evolution of epitaxial graphene layers on 3C SiC/Si (111) as a function of annealing temperature in UHV

The growth of graphene on SiC/Si substrates is an appealing alternative to the growth on bulk SiC for cost reduction and to better integrate the material with Si based electronic devices. In this paper, we present a complete in-situ study of the growth of epitaxial graphene on 3C SiC (111)/Si (111) substrates via high temperature annealing (ranging from 1125˚C to 1375˚C) in ultra high vacuum (UHV). The quality and number of graphene layers have been thoroughly investigated by using x-ray photoelectron spectroscopy (XPS), while the surface characterization have been studied by scanning tunnelling microscopy (STM). Ex-situ Raman spectroscopy measurements confirm our findings, which demonstrate the exponential dependence of the number of graphene layer from the annealing temperature.

A hybrid constructive heuristic and simulated annealing for railway crew scheduling

Railway crew scheduling problem is the process of allocating train services to the crew duties based on the published train timetable while satisfying operational and contractual requirements. The problem is restricted by many constraints and it belongs to the class of NP-hard. In this paper, we develop a mathematical model for railway crew scheduling with the aim of minimising the number of crew duties by reducing idle transition times. Duties are generated by arranging scheduled trips over a set of duties and sequentially ordering the set of trips within each of duties. The optimisation model includes the time period of relief opportunities within which a train crew can be relieved at any relief point. Existing models and algorithms usually only consider relieving a crew at the beginning of the interval of relief opportunities which may be impractical. This model involves a large number of decision variables and constraints, and therefore a hybrid constructive heuristic with the simulated annealing search algorithm is applied to yield an optimal or near-optimal schedule. The performance of the proposed algorithms is evaluated by applying computational experiments on randomly generated test instances. The results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time for large-sized problems.

Visible photoluminescence from plasma-synthesized SiO 2-buffered SiN x films : effect of film thickness and annealing temperature

The effect of the film thickness and postannealing temperature on visible photoluminescence (PL) from Si Nx films synthesized by plasma-assisted radio frequency magnetron sputtering on Si O2 buffer layers is investigated. It is shown that strong visible PL is achieved at annealing temperatures above 650 °C. The optimum annealing temperature for the maximum PL yield strongly depends on the film thickness and varies from 800 to 1200°C. A comparative composition-structure-property analysis reveals that the PL intensity is directly related to the content of the Si-O and Si-N bonds in the Si Nx films. Therefore, sufficient oxidation and moderate nitridation of Si Nx Si O2 films during the plasma-based growth process are crucial for a strong PL yield. Excessively high annealing temperatures lead to weakened Si-N bonds in thinner Si Nx films, which eventually results in a lower PL intensity.

Annealing-free high-mobility diketopyrrolopyrrole-quaterthiophene copolymer for solution-processed organic thin film transistors

A donor-acceptor polymer semiconductor, PDQT, comprising diketopyrrolopyrrole (DPP) and β-unsubstituted quaterthiophene (QT) for organic thin film transistors (OTFTs) is reported. This polymer forms ordered layer-by-layer lamellar packing with an edge-on orientation in thin films even without thermal annealing. The strong intermolecular interactions arising from the fused aromatic DPP moiety and the DPP-QT donor-acceptor interaction facilitate the spontaneous self-assembly of the polymer chains into close proximity and form a large π-π overlap, which are favorable for intermolecular charge hopping. The well-interconnected crystalline grains form efficient intergranular charge transport pathways. The desirable chemical, electronic, and morphological structures of PDQT bring about high hole mobility of up to 0.97 cm2/(V·s) in OTFTs with polymer thin films annealed at a mild temperature of 100 °C and similarly high mobility of 0.89 cm2/(V·s) for polymer thin films even without thermal annealing.

Application of simulated annealing to data distribution for all-to-all comparison problems in homogeneous systems

Distributed systems are widely used for solving large-scale and data-intensive computing problems, including all-to-all comparison (ATAC) problems. However, when used for ATAC problems, existing computational frameworks such as Hadoop focus on load balancing for allocating comparison tasks, without careful consideration of data distribution and storage usage. While Hadoop-based solutions provide users with simplicity of implementation, their inherent MapReduce computing pattern does not match the ATAC pattern. This leads to load imbalances and poor data locality when Hadoop's data distribution strategy is used for ATAC problems. Here we present a data distribution strategy which considers data locality, load balancing and storage savings for ATAC computing problems in homogeneous distributed systems. A simulated annealing algorithm is developed for data distribution and task scheduling. Experimental results show a significant performance improvement for our approach over Hadoop-based solutions.

Time evolution of graphene growth on SiC as a function of annealing temperature

We followed by X-ray Photoelectron Spectroscopy (XPS) the time evolution of graphene layers obtained by annealing 3C SiC(111)/Si(111) crystals at different temperatures. The intensity of the carbon signal provides a quantification of the graphene thickness as a function of the annealing time, which follows a power law with exponent 0.5. We show that a kinetic model, based on a bottom-up growth mechanism, provides a full explanation to the evolution of the graphene thickness as a function of time, allowing to calculate the effective activation energy of the process and the energy barriers, in excellent agreement with previous theoretical results. Our study provides a complete and exhaustive picture of Si diffusion into the SiC matrix, establishing the conditions for a perfect control of the graphene growth by Si sublimation.

A sequencing approach for creating new train timetables

Train scheduling is a complex and time consuming task of vital importance. To schedule trains more accurately and efficiently than permitted by current techniques a novel hybrid job shop approach has been proposed and implemented. Unique characteristics of train scheduling are first incorporated into a disjunctive graph model of train operations. A constructive algorithm that utilises this model is then developed. The constructive algorithm is a general procedure that constructs a schedule using insertion, backtracking and dynamic route selection mechanisms. It provides a significant search capability and is valid for any objective criteria. Simulated Annealing and Local Search meta-heuristic improvement algorithms are also adapted and extended. An important feature of these approaches is a new compound perturbation operator that consists of many unitary moves that allows trains to be shifted feasibly and more easily within the solution. A numerical investigation and case study is provided and demonstrates that high quality solutions are obtainable on real sized applications.

Microstructural characterization of electron beam evaporated tungsten oxide films for gas sensing applications

Tungsten trioxide is one of the potential semiconducting materials used for sensing NH3, CO, CH4 and acetaldehyde gases. The current research aims at development, microstructural characterization and gas sensing properties of thin films of Tungsten trioxide (WO3). In this paper, we intend to present the microstructural characterization of these films as a function of post annealing heat treatment. Microstructural and elemental analysis of electron beam evaporated WO3 thin films and iron doped WO3 films (WO3:Fe) have been carried out using analytical techniques such as Transmission electron microscopy, Rutherford Backscattered Spectroscopy and XPS analysis. TEM analysis revealed that annealing at 300oC for 1 hour improves cyrstallinity of WO3 film. Both WO3 and WO3:Fe films had uniform thickness and the values corresponded to those measured during deposition. RBS results show a fairly high concentration of oxygen at the film surface as well as in the bulk for both films, which might be due to adsorption of oxygen from atmosphere or lattice oxygen vacancy inherent in WO3 structure. XPS results indicate that tungsten exists in 4d electronic state on the surface but at a depth of 10 nm, both 4d and 4f electronic states were observed. Atomic force microscopy reveals nanosize particles and porous structure of the film. This study shows e-beam evaporation technique produces nanoaparticles and porous WO3 films suitable for gas sensing applications and doping with iron decreases the porosity and particle size which can help improve the gas selectivity.

Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion

In the paper, the flow-shop scheduling problem with parallel machines at each stage (machine center) is studied. For each job its release and due date as well as a processing time for its each operation are given. The scheduling criterion consists of three parts: the total weighted earliness, the total weighted tardiness and the total weighted waiting time. The criterion takes into account the costs of storing semi-manufactured products in the course of production and ready-made products as well as penalties for not meeting the deadlines stated in the conditions of the contract with customer. To solve the problem, three constructive algorithms and three metaheuristics (based one Tabu Search and Simulated Annealing techniques) are developed and experimentally analyzed. All the proposed algorithms operate on the notion of so-called operation processing order, i.e. the order of operations on each machine. We show that the problem of schedule construction on the base of a given operation processing order can be reduced to the linear programming task. We also propose some approximation algorithm for schedule construction and show the conditions of its optimality.