Today, robots can be found helping humans with their daily tasks. Some tasks require the robot to visit a set of locations in the environment efficiently, like in the Traveling Salesman Problem. As indoor environments are maze-like areas, feasible paths connecting locations must be computed beforehand, so they can be combined during the scheduling, which can be impracticable for real-time applications. This work presents an on-line Route Scheduling supported by a Fast Path Planning Method able to adjust pre-built paths. Experiments were carried out with virtual and real robots to evaluate time and quality of tours.

This paper presents research in the development of heuristic evolutionary algorithms (EAs) for generating and exploring differentiated force-based structures. The algorithm is weighted toward design exploration of topological differentiation while including specific structural and material constraints. An embryological EA model is employed to “grow” networks of mass-spring elements achieving desired mesh densities that resolve themselves in tensile force (form-active) equilibrium. The primal quadrilateral quadrisection method serves as the foundation for a range of extensible subdivision methods. Unique to this research, the quad is addressed as a “cell” rather than a topological or geometric construct, allowing for the contents of the cell to vary in number of mass-spring elements and orientation. In this research, this approach has been termed the quadrilateral quadrisection with n variable topological transformation method. This research culminates with the introduction of a method for grafting meshes where emergent features from the evolved meshes can be transposed and replicated in an explicit yet informed manner. The EA and grafting methods function within a Java-based software called springFORM, developed in previous research, which utilizes a mass-spring based library for solving force equilibrium and allows for both active (manual) and algorithmic topology manipulation. In application to a specific complex tensile mesh, the design framework, which combines the generative EA and mesh grafting method, is shown to produce emergent and highly differentiated topological arrangements that negotiate the specific relationships among a desired maximal mesh density, geometric patterning, and equalized force distribution.

We present and compare two evolutionary algorithm based methods for rectangular architectural layout generation: dense packing and subdivision algorithms. We analyze the characteristics of the two methods on the basis of three floor plan scenarios. Our analyses include the speed with which solutions are generated, the reliability with which optimal solutions can be found, and the number of different solutions that can be found overall. In a following step, we discuss the methods with respect to their different user interaction capabilities. In addition, we show that each method has the capability to generate more complex L-shaped layouts. Finally, we conclude that neither of the methods is superior but that each of them is suitable for use in distinct application scenarios because of its different properties.

The tool switching problem (ToSP) is well known in the domain of flexible manufacturing systems. Given a reconfigurable machine, the ToSP amounts to scheduling a collection of jobs on this machine (each of them requiring a different set of tools to be completed), as well as the tools to be loaded/unloaded at each step to process these jobs, such that the total number of tool switches is minimized. Different exact and heuristic methods have been defined to deal with this problem. In this work, we focus on memetic approaches to this problem. To this end, we have considered a number of variants of three different local search techniques (hill climbing, tabu search, and simulated annealing), and embedded them in a permutational evolutionary algorithm. It is shown that the memetic algorithm endowed with steepest ascent hill climbing search yields the best results, performing synergistically better than its stand-alone constituents, and providing better results than the rest of the algorithms (including those returned by an effective ad hoc beam search heuristic defined in the literature for this problem).

In this paper we prove that the stationary distribution of populations in genetic algorithms focuses on the uniform population with the highest fitness value as the selective pressure goes to ∞ and the mutation probability goes to 0. The obtained sufficient condition is based on the work of Albuquerque and Mazza (2000), who, following Cerf (1998), applied the large deviation principle approach (Freidlin-Wentzell theory) to the Markov chain of genetic algorithms. The sufficient condition is more general than that of Albuquerque and Mazza, and covers a set of parameters which were not found by Cerf.

In this paper we propose a new genetic algorithm specifically based on mutation and selection in order to maximize a fitness function. This mutation-selection algorithm behaves as a gradient algorithm which converges to local maxima. In order to obtain convergence to global maxima we propose a new algorithm which is built by randomly perturbing the selection operator of the gradient-like algorithm. The perturbation is controlled by only one parameter: that which allows the selection pressure to be governed. We use the Markov model of the perturbed algorithm to prove its convergence to global maxima. The arguments used in the proofs are based on Freidlin and Wentzell's (1984) theory and large deviation techniques also applied in simulated annealing. Our main results are that (i) when the population size is greater than a critical value, the control of the selection pressure ensures the convergence to the global maxima of the fitness function, and (ii) the convergence also occurs when the population is the smallest possible, i.e. 1.

We consider two versions of a simple evolutionary algorithm (EA) model for protein folding at zero temperature, namely the (1 + 1)-EA on the LeadingOnes problem. In this schematic model, the structure of the protein, which is encoded as a bit-string of length n, is evolved to its native conformation through a stochastic pathway of sequential contact bindings. We study the asymptotic behavior of the hitting time, in the mean case scenario, under two different mutations: the one-flip, which flips a unique bit chosen uniformly at random in the bit-string, and the Bernoulli-flip, which flips each bit in the bit-string independently with probability c/n, for some c ∈ ℝ+ (0 ≤ c ≤ n). For each algorithm, we prove a law of large numbers, a central limit theorem, and compare the performance of the two models.