The trap of local optima is one of the main challenges of stochastic optimization methods from machine learning. The aim of this thesis is to develop an optimization algorithm that is inspired by users interacting with Picbreeder, which is an online service that allows users to collaboratively evolve images via an artificial evolution. The idea is that their behaviours depict creative processes. We propose a general framework on the top of a common optimization technique called inspiration-triggered search, which mimics these processes. Instead of a fixed objective function the search algorithm is free to change the objective within certain constraints. The overall optimization task is to generate complex artefacts that cannot be generated by a greedy and direct optimization approach. The proposed method is tested in the domain of images, that is to find complex and aesthetically pleasant images for humans, and compared with the direct optimization. Powered by TCPDF (www.tcpdf.org)

While autonomous robot systems are becoming increasingly common, their usage is still mostly limited to rather simple tasks. This primarily results from the need for manually programming the execution plans of the robots. Instead, as shown in this thesis, their behavior can be automatically generated from a given goal specification. This forms the basis for providing formal guarantees regarding optimality and satisfaction of the mission goal specification and creates the opportunity to deploy these robots in increasingly sophisticated scenarios. Well-defined robot capabilities of comparably low complexity can be developed independently from a specific high-level goal and then, using a behavior planner, be automatically composed to achieve complex goals in a verifiably correct way. Considering multiple robots introduces significant additional planning complexity. Not only actions need to be planned, but also allocation of parts of the mission to the individual robots needs to be considered. Classically, either are planning and allocation seen as two independent problems which requires to solve an exponential number of planning problems, or the formulation of a joint team model leads to a product state space between the robots. The resulting exponential complexity prevents most existing approaches from being practically useful in more complex and realistic scenarios. In this thesis, an approach is presented to utilize the interplay of allocation and planning, which avoids the exponential complexity for independently executable parts of the mission specification. Furthermore, an approach is presented to identify these independent parts automatically when only being given a single goal specification for the team. This bears the potential of improving the efficiency to find an optimal solution and is a significant step towards the application of formal multi-robot behavior planning to real-world problems. The effectiveness of the proposed methods is therefore illustrated in experiments based on an existing office environment and in realistic scenarios. / Även om autonoma robotsystem blir allt vanligare är deras användning fortfarande mestadels begränsad till ganska enkla uppgifter. Detta beror främst på att manuell programmering av robotarnas exekveringsplaner behövs. Istället, som det visas i denna avhandling, kan deras beteende genereras automatiskt från en given målspecifikation. Detta utgör fundamentet för att ge en formell garanti att det resulterande beteendet är optimalt och uppdragsmålspecifikationen är uppfylld. Därför skapar det möjlighet att använda dessa robotar i alltmer sofistikerade scenarier. Väldefinierade robotkompetenser med relativt låg komplexitet kan utvecklas oberoende av ett specifikt mål på hög nivå och sedan sammansättas automatiskt med hjälp av en beteendeplanerare för att uppnå komplexa mål på ett verifierbar korrekt sätt. Om det handlar om flera robotar så introduceras ytterligare planeringskomplexitet som är betydande. Inte bara åtgärder behöver planeras, men även fördelning av uppdragets olika delar till de enskilda robotarna måste hanteras. Traditionellt anses planering och allokering som två oberoende problem som kräver att man löser ett exponentiellt antal planeringsproblem, eller så leder formuleringen av en gemensam modell för hela gruppen till ett produkttillståndsutrymme mellan robotarna. Den resulterande exponentiella komplexiteten förhindrar att de flesta befintliga metoderna är praktiskt användbara i mer komplexa och realistiska scenarier. I denna avhandling presenteras ett tillvägagångssätt för att utnyttja samspelet mellan allokering och planering, som undviker exponentiell komplexitet för oberoende exekverbara delar av uppdragsspecifikationen. Dessutom presenteras ett tillvägagångssätt för att automatiskt identifiera dessa oberoende delar när endast en enda målspecifikation ges för arbetslaget. Detta har potential att förbättra effektiviteten för att hitta en optimal lösning och är ett viktigt steg mot tillämpningen av formell multi-robot-beteendeplanering för realistiska problem. Effektiviteten av de föreslagna metoderna illustreras därför i experiment baserade på en befintlig kontorsmiljö och i realistiska scenarier. / <p>QC 20170928</p>

CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / Em diversas situações, o volume de tarefas a serem cumpridas não pode ser realizado por um único robô. Assim, um campo que tem despertado crescente interesse é a investigação do comportamento de enxame de robôs de busca. Estratégias de cooperação e controle desse enxame devem ser consideradas para um desempenho eficiente do time de robôs. Existem várias técnicas clássicas em inteligência artificial que são capazes de resolver este problema. Neste trabalho um conjunto de técnicas bio-inspiradas, que engloba um modelo baseado em autômatos celulares com memória e feromônio invertido, foi considerado inicialmente para coordenar um time de robôs na tarefa de forrageamento para ambientes previamente conhecidos. Os robôs do time compartilham o mesmo ambiente, comunicando-se através do feromônio invertido, que é depositado por todos os agentes a cada passo de tempo, resultando em forças de repulsão e maior cobertura do ambiente. Por outro lado, o processo de retorno para o ninho é baseado no comportamento social observado no processo de evacuação de pedestres, resultando em forças de atração. Todos os movimentos deste processo são de primeira escolha e a resolução de conflitos proporciona uma característica não-determinista ao modelo. Posteriormente, o modelo base foi adaptado para a aplicação nas tarefas de coleta seletiva e busca e resgate. Os resultados das simulações foram apresentados em diferentes condições de ambiente. Além disso, parâmetros como quantidade e disposição da comida, posição dos ninhos e largura, constantes relacionadas ao feromônio, e tamanho da memória foram analisados nos experimentos. Em seguida, o modelo base proposto neste trabalho para tarefa de forrageamento, foi implementado usando os robôs e-Puck no ambiente de simulação Webots, com as devidas adaptações. Por fim, uma análise teórica do modelo investigado foi analisado através da teoria dos grafos e das filas. O método proposto neste trabalho mostrou-se eficiente e passível de ser implementado num alto nível de paralelismo e distribuição. Assim, o modelo torna-se interessante para a aplicação em outras tarefas robóticas, especialmente em problemas que envolvam busca multi-objetiva paralela. / In several situations, the volume of tasks to be accomplished can not be performed by a single robot. Thus, a field that has attracted growing interest is the behavior investigation of the search swarm robots. Cooperation and control strategies of this swarm should be considered for an efficient performance of the robot team. There are several classic techniques in artificial intelligence that are able to solve this problem. In this work a set of bio-inspired techniques, which includes a model based on cellular automata with memory and inverted pheromone, was initially considered to coordinate a team of robots in the task of foraging to previously known environments. The team's robots share the same environment, communicating through the inverted pheromone, which is deposited by all agents at each step of time, resulting in repulsive forces and increasing environmental coverage. On the other hand, the return process to the nest is based on the social behavior observed in the process of pedestrian evacuation, resulting in forces of attraction. All movements in this process are first choice and conflict resolution provides a non-deterministic characteristic to the model. Subsequently, the base model was adapted for the application in the tasks of selective collection and search and rescue. The results of the simulations were presented under different environment conditions. In addition, parameters such as amount and arrangement of food, nest position and width, pheromone-related constants, and memory size were analyzed in the experiments. Then, the base model proposed in this work for foraging task, was implemented using the e-Puck robots in the simulation environment Webots, with the appropriate adaptations. Finally, a theoretical analysis of the investigated model was analyzed through the graphs and queuing theory. The method proposed in this work proved to be efficient and capable of being implemented at a high level of parallelism and distribution. Thus, the model becomes interesting for the application in other robotic tasks, especially in problems that involve parallel multi-objective search. / Tese (Doutorado)

The field of evolutionary computation is inspired by the achievements of natural evolution, in which there is no final objective. Yet the pursuit of objectives is ubiquitous in simulated evolution because evolutionary algorithms that can consistently achieve established benchmarks are lauded as successful, thus reinforcing this paradigm. A significant problem is that such objective approaches assume that intermediate stepping stones will increasingly resemble the final objective when in fact they often do not. The consequence is that while solutions may exist, searching for such objectives may not discover them. This problem with objectives is demonstrated through an experiment in this dissertation that compares how images discovered serendipitously during interactive evolution in an online system called Picbreeder cannot be rediscovered when they become the final objective of the very same algorithm that originally evolved them. This negative result demonstrates that pursuing an objective limits evolution by selecting offspring only based on the final objective. Furthermore, even when high fitness is achieved, the experimental results suggest that the resulting solutions are typically brittle, piecewise representations that only perform well by exploiting idiosyncratic features in the target. In response to this problem, the dissertation next highlights the importance of leveraging human insight during search as an alternative to articulating explicit objectives. In particular, a new approach called novelty-assisted interactive evolutionary computation (NA-IEC) combines human intuition with a method called novelty search for the first time to facilitate the serendipitous discovery of agent behaviors. iii In this approach, the human user directs evolution by selecting what is interesting from the on-screen population of behaviors. However, unlike in typical IEC, the user can then request that the next generation be filled with novel descendants, as opposed to only the direct descendants of typical IEC. The result of such an approach, unconstrained by a priori objectives, is that it traverses key stepping stones that ultimately accumulate meaningful domain knowledge. To establishes this new evolutionary approach based on the serendipitous discovery of key stepping stones during evolution, this dissertation consists of four key contributions: (1) The first contribution establishes the deleterious effects of a priori objectives on evolution. The second (2) introduces the NA-IEC approach as an alternative to traditional objective-based approaches. The third (3) is a proof-of-concept that demonstrates how combining human insight with novelty search finds solutions significantly faster and at lower genomic complexities than fully-automated processes, including pure novelty search, suggesting an important role for human users in the search for solutions. Finally, (4) the NA-IEC approach is applied in a challenge domain wherein leveraging human intuition and domain knowledge accelerates the evolution of solutions for the nontrivial octopus-arm control task. The culmination of these contributions demonstrates the importance of incorporating human insights into simulated evolution as a means to discovering better solutions more rapidly than traditional approaches.