Research Blog

Swarm Task Allocation with Embodied Evolution

In our recently accepted paper, we seek to achieve task allocation in swarm intelligence using an embodied evolutionary framework, which aims to generate divergent and specialized behaviors among a swarm of agents in an online and self-organized manner. In our considered scenario, specialization is encouraged through a bi-objective composite fitness function for the genomes, which is the weighted sum of a local and a global fitness function. The former depends only on the behavior of an agent itself, while the latter depends on the effectiveness of cooperation among all nearby agents. We have tested two existing variants of embodied evolution on this scenario and compared their performances against those of an individual random walk baseline algorithm. We have found out that those two embodied evolutionary algorithms have good performances at the extreme cases of weight configurations, but are not adequate when the two objective functions interact. We thus propose a novel bi-objective embodied evolutionary algorithm, which handles the aforementioned scenario by controlling the proportion of specialized behaviors via a dynamic reproductive isolation mechanism. 

Screen Shot 2021-06-23 at 16.36.43

More details can be found here:

  • Qihao Shan and Sanaz Mostaghim
  • Achieving Task Allocation in Swarm Intelligence with Bi-Objective Embodied Evolution
  • Accepted. Springer Journal on Swarm Intelligence, 2021

 

more ...

Multi-Objective Optimization and Decision-Making in Context Steering

Decision-making for autonomous movement of agents is one of our research topics. In one our recent works, we have developed algorithms for such agents to simultaneously optimize several objectives occuring in their local environments. Such behaviorcan be achieved with steering algorithms, which have originally been designed for moving numerous agents simultaneously where occasional uncertainties are not noticeable by players. Nevertheless, concentrating on single individuals can reveal major flaws in their movement patterns such as oscillatory movement. For avoiding such problems, computer-game makers are forced to develop higher-level abstractions for handling game-relevant special cases. Thus, eliminating the initial benefit of steering behaviors to be highly modular, lightweight, and controllable. This work enhances the context steering approach by Fray, which introduced discretized contextual information in the aggregation of a steering behavior's components. We combine this method with multi-criteria decision-making for controlling the agent's velocity direction and magnitude.

ContextSteering

More information here: 

  • Alexander Dockhorn, Sanaz Mostaghim, Martin Kirst and Martin Zettwitz
  • Multi-Objective Optimization and Decision-Making in Context Steering
  • Accepted at IEEE Conference on Games, 2021

 

 

more ...

Multi-Objective Pathfinding and Navigation

Navigation is an essential aspect in the mobility. We all know this from our daily life experiences. Going from point A to point B. The modern navigation systems usually offer us the best route according to time of travel. However, there are certain cases that we need the best route in terms of other criteria like the distance (related to CO2 emission), Slope of the route or the curvature (in animal transportation). With our newly proposed benchmark, we define 5 criteria for navigation: 

Screen Shot 2021-05-31 at 12.54.53

 

 More details: 

  • Jens Weise and Sanaz Mostaghim
  • Scalable Many-Objective Pathfinding Benchmark Suite
  • Accepted. IEEE Transactions on Evolutionary Computation, 2021 --> Link

 

more ...

Collective Decision-Making

Collective perception allows sparsely distributed agents to form a global view on a common spatially-distributed problem without any direct access to global knowledge and only based on a combination of locally perceived information. However, the evidence gathered from the environment is often subject to spatial correlations and depends on the movements of the agents. The latter is not always easy to control and the main question is how to share and to combine the estimated information to achieve the most precise global estimate in the least possible time. In our recently accepted paper, we aim to answer this question with the help of evidence theory, also known as Dempster-Shafertheory, applied to the collective perception scenario as a collective decision-making problem: 

 Fig1a

The above figure shows several agents moving in an environment with three colors. The agents do not have any knowledge about the fact which color is the presented by the majority of the units. Only through a local communication, they have to collectively figure it out. 

More information:  

  • Palina Bartashevich and Sanaz Mostaghim 
  • Multi-Featured Collective Perception with Evidence Theory: Tackling Spatial Correlations
  • Accepted. Journal on Swarm Intelligence, 2021

 

more ...

Optimal Control Policies and Strategies for Critical Situations

How can we make better decisions in critical situations like during the corona pandemic? We optimize the strategies given two policies for the current pandemic situation. We simply take the SIER model, extend it by adding economical models besides the health issues. We study just two simple policies "Lock down" and "Social distancing" and try to optimize their trigger time (when we start applying them). Since the economy and health can (or in this case "are") conflicting objectives, we identify the Pareto-Optimal strategies. In our simple case, a strategy is simply  the start point of applying these policies: 

The above figure shows the two variables t1 and t2 as the start time of the two policies and the figure below shows their impact on health and economy in the HED model. 

 The points A, B, C, D and E are different strategies and we study three of them below. 

The above figures show the stratgies A, E and C respectively. More information can be found in our recent paper in our blog post: here

 

 

more ...

Traceability in Evolutionary Learning

Evolutionary optimization and learning algorithms help to find an optimal solution for complex problems. In a nutshell, they work like this: We start with a random set of solutions to the problem and by recombining the good ones, try to iteratively get closer to the optimal solution. This process is very complex and similar to the natural evolution is not easily tracable. However, we are interested to trace the impact of the initial random set of solutions on the outcome. In one of our recent papers which will be presented at IEEE Congress on Evolutionary Computation 2021, we are getting one step closer to this traceablity.

 

 Screen Shot 2021-04-19 at 16.09.45

  • Tobias Benecke and Sanaz Mostaghim 
  • Tracking the Heritage of Genes in Evolutionary Algorithms
  • Accepted at the IEEE CEC 2021

 

more ...

Genetic Programming as an explainable AI Framework

Explainability of the results of AI algorithms is an important feature especially once it comes to the applications with strong physical laws. We have developed a Genetic Programming (GP) framework for the context of fluid dynamics. The first results look very promising and the results are explainable. 

GP-compact

Figure: Main loop of GP, we evolve symbolic functions which fit data from simulations. 

More detilas to be presented at EUROGEN 2021 and can be found in this paper: 

  • Heiner Zille, Fabien Evrard, Julia Reuter, Sanaz Mostaghim and Berend van Wachem
  • Assessment of Multi-objective and Coevolutionary Genetic Programming for predicting the Stokes Flow around a Sphere
  • Accepted at International Conference on Evolutionary and Deterministic Methods for Design, Optimization and Control (EUROGEN 2021), ECCOMAS, June 2021

more ...

Health and Economy Dilemma: A Multi-Objective Problem

We are working for more than a year on finding optimal policies for pandemic situations. This work is done based on a cooperation within our project funded by Volkswagen-Foundation:

Social-distancing and lockdown policies – so-called non-pharmaceutical interventions (NPIs) – are potent measures to contain the spreading of a novel pathogen like the SARS-CoV-2. While NPIs reduce the stress on the health care system, businesses suffer from the restrictions, and little is known about how to balance NPIs to contain the pandemic while preserving the economy. We model this health economy dilemma (HED) as a multi-objective optimization problem and deal with the problem to find optimal policies. 

 

 SEIR

  • Rohit Salgotra, Amiram Moshaiov, Thomas Seidelmann, Dominik Fischer and Sanaz Mostaghim 
  • Optimal Control Policies to Address the Pandemic Health-Economy Dilemma
  • Accepted at the IEEE CEC 2021

 

more ...

Computational Intelligence Methodologies for Multi-Objective Optimization and Decision-Making in Autonomous Systems

In one of our recent papers, we provide an overview about the methodologies and challenges of multi-criteria decision-making algorithms for autonomous systems.

CI-Blog

Decision- making is usually required when we are confronted with conflicting objectives and is in fact a very challenging task even for human decision-makers. This is due to the fact that we first need to find all the possible optimal alternatives and then select the right choice using a decision policy. Replacing the human decision-maker with an autonomous system in highly dynamic environments is even more challenging. We need to enable such autonomous systems to change their (pre-defined) decision policy according to unpredictable circumstances. This ability can contribute to the applicability of such autonomous systems in critical missions, such as rescue robotics where the intervention of a human-controller is not always possible. The challenge is not only in finding and selecting the best optimal alternative, but also in acting in a limited timeframe during the mission. This chapter contains an overview about the challenges and methodologies for two different time scales. Our major focus is on navigation and exploration tasks.

Sanaz Mostaghim, Computational Intelligence Methodologies for Multi-Objective Optimization and Decision-Making in Autonomous Systems, Springer, Special Edition on Women in Computational Intelligence, Alice Smith (Editor). To be published in 2021.

 

more ...

Multi-Criteria Decision-Making

Multi-Objective Optimization using evolutionary algorithms have many advantages. One is that they are anytime algorithms and can be stopped anytime. Even if the exact optimal solutions have not been found. In such cases we probably end up with a better solution than any other earlier explored ones. The second advantage concerns the fact that it gives the ability to the user to choose his desired optimal solution.  This is because we usually obtain a set of optimal solutions for the problem and in this way the user (decision maker) has several options and can select her/his preferred solution. Having a set of optimal alternatives gives a good amount of knowledge to the decision maker. The decision maker can compare them with each other and choose his preferred solution with more confidence. One major challenge is, however, taking the right choice. What is a smart choice and how can we evaluate that? How to consider these aspects from decision making in the optimization process? We have been working on these ideas for a while. 

wordcloud-2

Look at her Keynote talk at IEEE World Congress on Evolutionary Computation 2020:

Sanaz Mostaghim: "Evolutionary Multi-Objective Optimization and Decision-Making in Timely Critical Scenarios", World Congress on Computational Intelligence, July 2020, Glasgow, UK

Here is a recent paper giving an overview about the topic: 

Sanaz Mostaghim, Computational Intelligence Methodologies for Multi-Objective Optimization and Decision-Making in Autonomous Systems, Springer, Special Edition on Women in Computational Intelligence, Alice Smith (Editor). To be published in 2021.

Sanaz is very proud to publish this paper in the very special book together with leading women researchers in the field of AI. 

 

more ...

Multi-Objective Learning

We claim that most of the existing learning and optimization problems are multi-objective. In our research, we work on various such problems and develop multi-objective algorithms. One of the applications concerns multi-agent path finding: many robots moving in an environment (imagine autonomous driving cars) and there are many objectives which have to considered such as collision avoidance (no accidents), but efficiency in terms of traveling cost and time for all the involved agents. In one of our recent works, we study the problem: 

  • Sebastian Mai and Sanaz Mostaghim 
  • Modelling Pathfinding for Swarm Robotics
  • In: Dorigo M. et al. (eds) Swarm Intelligence. ANTS 2020. Lecture Notes in Computer Science, vol 12421. Springer, Cham. 2020. https://doi.org/10.1007/978-3-030-60376-2_15 

 The very good accept about multi-objective learning is that we have several optimal solutions. The picture below shows two behaviors for each setting (various number of agents and various environments): best behavior in terms of length (bottom) and best behavior in terms of collisions (top). 

Blog-MOMAPF

more ...

Communication Toplogies in Swarms

In one of our recent research works, we study the role of communication topologies in swarms performing the search under strong negative influence coming from the unknown external environment affecting the individuals’ movements. We introduce four dynamic topologies, Payoff, Prob, PayoffProb, and Switch, based on the game theoretical concepts. All these communication topologies are based on the Payoff topology:

It is based on the N-Player Iterated Prisoner Dilemma, where the particle A needs to decide between cooperation or defection with a group of other players. If it cooperates, it will exchange information with this group, otherwise there is no communication. 

SwarmNetworkTopology

Our results on a range of experiment confirm our hypothesis and indicate that dynamic neighborhoods lead to a better approximation of the optimal solution than static ones despite the unknown external forces.

More information can be found here: 

  • Palina Bartashevich, Doreen Koerte and Sanaz Mostaghim
  • Impact of Communication Topology on PSO-based Swarms in Vector Fields
  • In the proceedings of 2020 IEEE Symposium Series on Computational Intelligence (SSCI), Canberra, Australia, 2020, pp. 497-504, doi: 10.1109/SSCI47803.2020.9308526 --> Link

 

 

 

more ...

Multi-Objective Learning

Since many years, our research group is working on research about multi-objective learning. Multi-Objective Learning is about learning tasks which involve multiple conflicting objecticves. For instance imagine a group of agents (a swarm) who is supposed to move in a small area. Each agent gets a positive reward, if its passes through a very narrow gate, but gets a negative reward after each collision with others or obstacles (walls etc). One way of dealing with this problem is to perform an on-board learning. In an early work in 2009, we worked on finite state machines and evolutionary robotics and let the agents to learn the task in a collective way: 

  • Lukas König, Sanaz Mostaghim, Hartmut Schmeck
  • Decentralized Evolution of Robotic Behavior Using Finite State Machines
  • International Journal of Intelligent Computing and Cybernetics, 2, (4), pages 695-723, December, 2009

In 2019, we repeated the same work, but this time we used hidden Markov models and more features:

  • Dominik Fischer, Larissa Albantakis and Sanaz Mostaghim
  • How cognitive and environmental constraints influence the reliability of simulated animats in groups
  • PLoS ONE 15(2): e0228879, February 2020. https://doi.org/10.1371/journal.pone.0228879 Open access --> Link

The interesting result from all these studies, is that the collective is able to learn to solve the multi-objective task in a very efficient way than if we would use a multi-agent path planning. They evolve the so called wall-following behavior: 

wallfollowing 

 

 

 

 

more ...

Harmonic Average Distant Metric for MMOPs

Talking about distance metrics in our last post, today we present the Harmonic Average Distance (HAD) metric which we use to deal with multi-modal multi-objective optimization Problems (MMOPs). One major challenge in MMOPs is that we need to measure the distances between the solutions in the decision space with large dimensionalities while considering the qualities in the objective space. The example below shows a 2D decision variable space. While the traditional crowding distance metric gives a higher priority to C than E, the HAD metric does the vice versa and E gets selected. 

Blog-MMOP-HAD

 More information can be found in our recently accepted paper which we will present at EMO 2021: 

  • Mahrokh Javadi and Sanaz Mostaghim
  • A Neighborhood-based Density Measure for Multimodal Multi-Objective Optimization
  • Accepted at the 11th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2021), Shenzhen, China, 2021

 

more ...

Fréchet Similarity Metric in Multi-Objective Optimization

In one of our research directions in multi-objective optimization, we work on navigation algorithms. The challenge in such algorithms is to keep a diverse set of solutions in both objective and decision spaces. The diversity of solutions in the decision space is a challenging task, since the similarity of solutions should be measured along a list of waypoints. As shown in Figures below. 

51DD52F3-F565-4556-A388-3D26BD730A18

In one of our recent works, we have proposed to use the Fréchet distance measure, and we found out that we can significantly increase the diversity of solutions in the decision space. The concept of Fréchet distance measure is similar to the picture below (a man and a dog on the leash). The two data sets are considered to be the points visited by the man (set one) and the dog (set two). 

08590D0A-5ECE-449F-AE99-C513E55297B0

More details can be found in our paper: 

  • Jens Weise and Sanaz Mostaghim
  • Many-Objective Pathfinding based on Fréchet Similarity Metric
  • Accepted at the 11th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2021), Shenzhen, China, 2021

 

more ...

Genetic Programming

Genetic Programming (GP) has been used in a variety of fields to learn the relationships between physical measurements in real-world problems. In our recent research, we combine different techniques from the area of evolutionary optimization and particularly GP to solve a fluid-dynamics problem: The Stokes Flow around a Sphere.

Take a closer look at our recent work: 

  • Heiner Zille, Fabien Evrard, Julia Reuter, Sanaz Mostaghim and Berend van Wachem
  • Assessment of Multi-objective and Coevolutionary Genetic Programming for predicting the Stokes Flow around a Sphere
  • Accepted Abstarct, EUROGEN conference, June 2021

 

more ...

SYnENZ

Digitalization is imposing lots of open questions regarding our lives as humans in cooperation with machines. What synergies result from the now possible interaction of humans, animals and plants on the one hand and machines on the other?  in other words what are the consequences and challenges of the interaction between natural and artificial intelligence? This extended interaction will change our lives to a considerable extent. These changes are associated with great opportunities, but also risks. In order to deal with this important topic in an interdisciplinary manner, the Braunschweigische Wissenschaftliche Gesellschaft (BWG) set up a commission on Synergy and Intelligence: Technical, Ethical and Legal Challenges of the Interaction of Living and Non-Living Entities in the Age of Digitization (SYnENZ) in 2017. Sanaz is a member of this committee and has written a paper about “Cooperation using Swarm Intelligence” in the newly published book. Take a closer look at the technical, ethical and legal challenges which are published in this book.  

https://link.springer.com/book/10.1007/978-3-658-30882-7

https://link.springer.com/chapter/10.1007/978-3-658-30882-7_5

more ...

Large-scale multi-objective optimization

The improvement in computing power in the last decade has made it possible to develop computational intelligence and AI methodologies for complex problems in various applications in science and industry. Additionally, large available data sets from simulations can contribute to unlock the power of these methodologies such as artificial neural networks and evolutionary algorithms. One of the advantages of working on evolutionary algorithms in comparison to neural networks (such as deep learning) is the explainability of the developed solutions and additionally the capability to deal with problems with large search spaces. In the recent years, there is a growing interest in so-called large-scale multi-objective optimization that deal with problems with a large number of decision variables. The performance of classic metaheuristic algorithms often deteriorates when the dimensionality of the decision space increases. We have published several works on this topic. Our proposed WOF framework can find very good solutions in a relatively short time in comparison to existing approaches:

Blog-largeScale

 

  • Heiner Zille, Hisao Ishibuchi, Sanaz Mostaghim and Yusuke Nojima
  • A Framework for Large-scale Multi-objective Optimization based on Problem Transformation (Download) (Supplement Material) (Sourcecode
  • IEEE Transactions on Evolutionary Computation, Vol. 22, Issue 2, pp. 260-275, April 2018. --> Link

 

  • Heiner Zille and Sanaz Mostaghim
  • Comparison Study of Large-scale Optimisation Techniques on the LSMOP Benchmark Functions (Download) (Sourcecode)
  • IEEE Symposium Series on Computational Intelligence (SSCI), IEEE SSCI 2017, Honolulu, Hawaii, November 2017 --> Link

 

more ...

Ising Model for Collective Decision Making

In our research about Collective Decision-Making, we work on the collective perception problem: A group of agents move in an unknown environment which is composed of units with two colors (like a chess board). The agents have to collectively estimate, which color is in majority. The agents can only perceive their local neighborhood and only communicate with their neighbors. 

In the following paper, we investigate the influence of the preferences of individuals on the process of collective perception using the Ising model from the context of Social Impact Theory. We have a dynamic network of agents within the unknown environment. The results show that assigning preferences to the agents allows a designer to take control over the outcome of the collective decision-making process. In addition, the agents with a right conjecture can faster reach the correct conclusion even if only 20% of the initial population holds the target opinion.

CDM-1

Dissemination of opinions: (a) in multi-agent simulation; (b) on static lattice. Colors represent agents opinions (red for black, blue for white). Lines indicate possible connections at the current time step. Bold lines (magenta) show agents in communication with each other. The agents in (a), while moving, perceive the environment consisting of black and white cells. (Color figure online)

More details can be found here: 

  • Palina Bartashevich and Sanaz Mostaghim
  • Ising Model as a Switch Voting Mechanism in Collective Perception (Download)
  • EPIA Conference on Artificial Intelligence 2019. Lecture Notes in Computer Science, vol 11805. Springer, pp. 617-629, September 2019 --> Link

 

more ...

Traceable Evolutionary Algorithms (T-EA)

Tracing the evolution is almost impossible. This is due to the complexity of the operations (cross-over and mutation) over several generations. However, when it comes to evolutionary algorithms, it is of great interest to trace the impact of the solution candidates. For instance, when we use evolutionary algorithms to find the best optimal strategy to take a decision, we are very much interested to see which individual impacted the optimization process the most. In one of our recent works, Traceable Evolutionary Algorithms (T-EA), we developed new ideas for this purpose. The figure shows 20 individuals of T-EA. Left figure illustrates the fitness values of the first generation (the larger the better) and the right figure shows the influence of the individuals over 20 generations. We can trace back that only 4 individuals 2, 3, 6 and 11 (shown also with arrows) and the mutation operator had an impact:

T-EA

More information can be found here:

 

 

 

more ...

Multi-Objective Tak Allocation for Wireless Sensor Networks

The Internet-of-Things (IoT) and especially Wireless Sensor Networks (WSNs) are comprised of multiple potentially low-power nodes distributed throughout the environment to monitor and manipulate. Nowadays this technologyis already used in many application fields like air quality monitoring, traffic control and environmental monitoring. However, especially for WSN, the major limiting factor remains the limited battery lifetime of the nodes especially in environments and use-cases where recharging or replacing the individual nodes or their batteries is infeasible. Consequently, energy efficiency is the key factor in nearly all applications of WSN technologies if they are to beadopted by real world users. Another important aspect is the generic dynamic nature of these networks. Nodes may fail because of mobility, environmental changes or simply because their battery is drained. Consequently, WSN need additional mechanisms to enforce reliability and reaction to these dynamic changes but still keep a specific level of performance regarding various metrics like bandwidth, latency and data quality.

In our research, we proposed a new multi-objective optimization algorithm enabling WSNs to optimize network metrics and mitigate changes in network topology through node failures by providing re-allocation of tasks based on continuous optimization of the task allocation. This allows the network to sustain task execution throughout node failures while simultaneously improving network metrics. The following figure shows a Single-Sink setup consisting of 10 non-constrained sensing tasks connected to a single actuating (sink) task, which is constrained to the two central tasks, which we used in our experiments: 

MO-TA-IOT

More details can be found here: 

  • Dominik Weikert, Christoph Steup and Sanaz Mostaghim
  • Multi-Objective Task Allocation for Wireless Sensor Networks
  • In: Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI), Symposium on Computational Intelligence in IoT and Smart Cities (CIIoT), Australia, 2020

 

more ...

Human Swarm Experiment

Did you know that we performed several human-swarm experiments in 2015, 2016, and 2017? With the goal to understand, what kind and how much communications self-organized systems require, we asked 200 people to be part of the human swarm experiment. We gave them T-Shirts (and Balloons) in different colors (blue, orange, green and Bordeaux red) with various printed shapes (circles, triangles, squares and pentagon), numbers (1 to 200), alphabets (from German Scrabble) and asked then to sort themselves. Experiment 1: Sorting the colors, Experiment 2: Sorting in terms of shapes, Experiments 3: Sorting the numbers and Experiment 4: Playing scrabble 

The results show that leadership (not predefined leadership, but a leadership which comes from the swarm) and communication (from the participants) play an essential role in people's swarm behavior. 

 Analysis of the video recording of the experiments shows:

  • Less intensive communication was required for the first experiment, as the participants could easily see the different colors over a greater distance.
  • In comparison, the second experiment required more communication and additional leadership from the swarm members. The experiment showed that more than 20 percent of the people had taken role of a leader, but only for a very short period of time.
  • In the third experiment, the individuals had to interact more in order to be able to place themselves in the queue and sort the numbers. Here leadership (out of the swarm) was indispensable in organizing the swarm. During this task there were fewer participants in the leadership role, but this role was retained for much longer.
  • The solution to the experiment four took much longer. The words formed by the participants are often only short. In addition, there was more interaction with this task, as the participants had to agree on a goal (word) within groups, which is reflected in the long time to solve the task.

The results are published in this paper (in German): 

  • Sanaz Mostaghim and Sebastian Mai
  • Kooperation mittels Schwarmintelligenz
  • In Haux R, Gahl K, Jipp M, Kruse R, Richter O, Herausgeber. Zusammenwirken von natürlicher und künstlicher Intelligenz. Wiesbaden: Springer VS; 2020. --> https://www.springer.com/de/book/9783658308810

Here are some videos from 2015:

Experiment 1: Sorting in terms of colors

Experiment 3: Sorting in terms of numbers

more ...

Self-organized Manufacturing

In one our projects, called MOSAIK, which is funded by BMBF, we work on self-organization algorithms in modern manufacturing systems. We aim to develop algorithms which can easily and autonomously adapt to changing circumstances given a set of workers, machines, products, etc. Imagine a shopfloor which is producing a certain item using several collaborating robots. An item like this could be all kinds of things, for example a sewing machine. Now the interesting part is what happens when we want to change some specifications of the sewing machine, or maybe we even want to produce a completely different item at some point. Maybe we want to produce sewing machines for one month, then masks for COVID-regulations for one month, then both in parallel. Can we achieve this by using the same robots as before? Changing the products implies changing the whole task sequence and many aspects of the shopfloor itself. Which robot moves to which location and performs which task? How do the robots communicate their individual goals and how can they coordinate their actions? How do they detect good strategies and can avoid bad ones? All of these questions and many more are at the heart of the MOSAIK project. In the following four videos you observe very abstarct simulations of the 2 to 20 robots moving in an environment performing several tasks without any collisions:

 

2 and 5 robots

 

10 and 20 robots

Together with our project partners, we just published a paper about this: 

  • Victor Charpenay, Daniel Schraudner, Thomas Seidelmann, Torsten Spieldenner, Jens Weise, Rene Schubotz,Sanaz Mostaghim, Andreas Harth
  • MOSAIK: A Formal Model for Self-Organizing Manufacturing Systems
  • Accepted at IEEE Transactions on Pervasive Computing, Special Issue on Pervasive Manufacturing, 2020

 

 

 

more ...

Multi-Objective Multi-Modal Optimization

Multi-objective Optimization Problems (MOPs) have typically several conflicting objectives which are supposed to be optimized at the same time. The solution of such problems is a set of so-called Pareto-optimal solutions. In our research in the area of Multi-Modal Multi-Objective Optimization we work on a particular sort of MOPs, namely Multi-Modal problems, which are present in many real-world problems. In such Multi-Modal problems, multiple equivalent solutions map to the same Pareto-optimal solution. The major challenge for the optimization algorithms is to discover these several equivalent solutions in the decision space. In our research we work on a variety of approaches to address this issue. In one of our recent works, we propose a new algorithm NxEMMO which enforces the diversity of the solutions in decision-space: 

  • Mahrokh Javadi and Sanaz Mostaghim
  • Using neighborhood-based Density Measures for Multimodal Multi-Objective Optimization
  • Accepted at the 11th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2021), Shenzhen, China, 2021

In the following videos, the evolution of the population is shown in the search space for NxEMMO (left videos) and NSGA-II (right videos) as a baseline algorithms. The obtained solutions are shown as red stars, and the blue lines indicate the true Pareto-optimal solutions.

NxEMMO-MMF1 NSGAII-MMF1  

NxEMMO (left), NSGA-II (right)

Decision space for MMF1 test problem

NxEMMO-MMF6 NSGAII-MMF6  

NxEMMO (left), NSGA-II (right)

Decision space for MMF6 test problem

NxEMMO-SYM_PART_rotated NSGAII-SYM_PART_rotated 

NxEMMO (left), NSGA-II (right)   

Decision space for SYM-PART-Rotated test problem

more ...

Reliability of simulated swarms

We offer two studies covering findings about a simulation of reliability in organized animats. Animats are simple agents with cognitive abilities similar to organisms, e.g., ants or bees. We simulate the evolution of organized animal swarms navigating between two rooms without colliding against each other. These studies help to advance knowledge about the optimal size of organizations and how the organization's performance depends on the abilities of the individual members.

Animat

A sample animat configuration with basic cognitive abilites

Simulating agents acting in an organized group is already a common practice. Not only to study swarm behavior but also to solve optimization problems. Still, little is known about how the size of the group, the cognitive abilities of the agent, or uncertain environmental conditions influence behavior. Consequently, depending on the internal and external constraints, the behavior of agents and their ability to cooperate varies. 

Animat Brain

A sample Markov Brain using Hidden Markov Gates

In the simulation experiments, we are wondering about the specific size of the organization in terms of the number of individual members. As a second dimension, we manipulate the individual's potential skills in terms of memory, sensory capacity, or motoric abilities during evolution. After evolving the animats, we expose them with uncertain conditions like changing the group size or changing the static environment. Since the environment has constant space, changing the group size varies the environment's density, and the animats are less or more likely to meet group members. Changing the static environment makes it easier or harder to navigate between the rooms, e.g., by adding or removing walls. We argue that those post-evolutionary tests provide data to assess the reliability of animats under uncertain conditions. The abstract nature of our study can be useful to theorize about the dynamics between the organizational and individual levels. Further, it sheds light on the high complexity of studies investigating multiple levels of analysis.

https://www.youtube.com/embed/OEFxX9uoZjw

The simulation of a winner generation, visualizing the wall-following strategy.

The findings are divided into the results for the evolution of the animats and the results of the reliability assessment: First, we find that it is dependent on the group size for animats to evolve flexible behavior, reasonable task fitness, and higher brain complexity. For our experiment design, the group size must be neither too small or too large. Second, we find that there can be a relationship between the group size an animat evolves in and the corresponding reliability. In our design, an animat who evolves in a balanced group size shows the best reliability under uncertain conditions. Further, we can show a correlation between high brain complexity, the group size, and optimized sensor capacity. 

The evolutionary simulation experiments using a Genetic Algorithm to generate collective behavior. This method visualizes a way to study reliability in organized groups while being able to control conditions and collect data on multiple levels. In general, the studies show that the group size can have an effect on reliability in uncertain conditions and that rather general cognitive abilities, which relate to heuristics, can avoid over-specialization. 

More details about this work can be found in:

  • Fischer, D., Mostaghim, S., & Albantakis, L. (2020). How cognitive and environmental constraints influence the reliability of simulated animats in groups. PLOS ONE, 15(2), e0228879. https://doi.org/10.1371/journal.pone.0228879
  • Fischer, D., Mostaghim, S., & Albantakis, L. (2018). How swarm size during evolution impacts the behavior, generalizability, and brain complexity of animats performing a spatial navigation task. GECCO 2018https://doi.org/10.1145/3205455.3205646

more ...

Multi-Objective Pathfinding

Route planning, also known as pathfinding is one of the key elements in logistics, mobile robotics and other applications, where engineers face many conflicting objectives. However, most of the current route planning algorithms consider only up to three objectives. In our research, we work on many-objective pathfinding. In the following papers, we propose a scalable many-objective benchmark problem covering most of the essential features for routing applications based on real-world data. We define five objective functions representing distance, travelling time, delays caused by accidents, and two route-specific features such as curvature and elevation. Since this test benchmark can be easily transferred to real-world routing problems, we construct a routing problem from OpenStreetMap data (right video). More details can be found in our papers: 

  • Jens Weise and Sanaz Mostaghim
  • Many-Objective Pathfinding based on Fréchet Similarity Metric
  • Accepted at the 11th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2021), Shenzhen, China, 2021

  

  

The first video shows one of our benchmark instances with a Lake-obstacle in the middle. During the video, the search of the paths is shown. The second video shows the same process on real-world data, the Berlin map.

 

And we just submitted the folowing paper: 

  • Jens Weise and Sanaz Mostaghim
  • Scalable Many-Objective Pathfinding Benchmark Suite
  • Submitted to IEEE Transactions on Evolutionary Computation.--> Link

 

 

more ...

Contour Search

Finding the contour of an object, known as contour search, has a large variety of applications. Beside the conventional applications in image processing, there are other applications in robotics. Imagine a scenario of identifying the contour of wildfire or oil spill on the ocean. The major challenges concern searching for an object and then identifying the corresponding contour. The existing algorithms typically rely on image processing technologies, which typically require knowledge about the entire search space. In our research, we work on a new algorithm for contour search which is based on Particle Swarm Optimization (PSO). We unify both of the search processes for the object and the contour identification in one algorithm. We consider the contour search of an object with an unknown shape which is located in an unknown position in a two-dimensional search space. Similar to optimization scenarios, the goal is to find and identify the contour (border) of any encountered part of the object. This research is being published in the following paper: 

Here are two videos on a sample test problem with both convex and concave contours: 

 

 

 

more ...

Energy Model for Small-scale Flying Robots

Unmanned Aerial Vehicles (UAVs) are used in more and more applications in the real world. These applications range from inspection tasks, e.g., bridges and wind turbines to agriculture applications like protection of deer from harvesters. However, most of these applications are still done using remotely piloted UAVs, even though the usage of autonomous quadcopters as replacements promises additional benefits like tighter surveillance and less cost. Especially, swarms of UAVs promise high efficiency with low-cost UAVs. UAVs, in general, promise efficient deployment and manoeuvrability even in hardly accessible areas, for example, in natural disaster management. The benefit in manoeuvrability comes at the cost of high energy consumption of the robots. To create an optimal mission plan and take appropriate decisions during the mission, a reliable, accurate and adaptive energy model is of utmost importance. However, most existing approaches either use very generic models or ones that are especially tailored towards a specific UAV. We present a generic energy model that is based on decomposing a robotic system into multiple observable components. More details can be found here: 

  • Christoph Steup, Simon Parlow, Sebastian Mai and Sanaz Mostaghim
  • Generic Component-based Mission-centric Energy Model for Micro-scale Unmanned Aerial Vehicles
  • Drones, 4(4), 63, September 2020. https://doi.org/10.3390/drones4040063 Open Access --> Link

And here you see a video of our flying robot during the energy test: 

 

more ...

Multi-Agent Path Finding

Robot swarms and multi-robot systems are very popular and are used in various applications. In most of such applications, navigation to certain positions and path planning for several robots within an environment pose a challenge for algorithm design. Currently robots rely on purely reactive behavior resulting in sub-optimal paths. The long term goal of our research is to extend the capabilities of the agents to plan future actions, taking into account the intend of their neighbors, to obtain more efficient behaviors. In order to optimally navigate within a moving robotic swarm, we need a framework for planning, evaluating and executing trajectories in a very dynamic environment. In the following paper, we propose a model to represent trajectories for multiple robots within a swarm, respecting the kinematic constraints of the robots given by a specific vehicle model.

  • Sebastian Mai and Sanaz Mostaghim 
  • Modelling Pathfinding for Swarm Robotics
  • In: Dorigo M. et al. (eds) Swarm Intelligence. ANTS 2020. Lecture Notes in Computer Science, vol 12421. Springer, Cham. 2020. https://doi.org/10.1007/978-3-030-60376-2_15

 

  

 

 

more ...

Swarm of Robots in Dynamic Environments

Since several years, we study the impact of dynamic environments (e.g., flow, wind) on robot swarms. This is actually a very important aspect, if we consider small scale (so called micro scale) robots which we have in our SwarmLab. Our flying robots are as large as an A4 paper and they are easily influenced by the wind in the back yard (where we do the outdoor experiments) or by themselves (since they fly in a swarm, they produce a lot of flow).

We have several works on this topic. The recent paper from 2020 is about various communication topologies. Here is the abstract of the paper and some interesting videos: 

  • Palina Bartashevich, Doreen Koerte and Sanaz Mostaghim
  • Impact of Communication Topology on PSO-based Swarms in Vector Fields
  • Accepted at the IEEE Symposium on Swarm Intelligence (SIS), SSCI, Australia, 2020

Abstract:

This paper studies the role of communication topologies in swarms performing the search under strong negative influence coming from the unknown external environment af- fecting the individuals’ movements. The experiments are carried out on two modified versions of PSO, namely Power- and Zigzag-PSO, which act without any preliminary information about external forces modeled by vector fields. We propose four dynamic topologies inspired by the game-theoretic concepts and investigate their performance relative to the ordinarily static ones with regard to convergence and “energy expenses”, reflecting the amount of collective effort needed to eliminate the produced drift. The results reveal that the topology of social connections on its own is not an effective way to cope with the unknown disturbance during the search. However, within the predefined coping mechanism against the disturbance as in the case of Zigzag-PSO, the considered dynamic topologies show the advantage before static ones for a limited communication radius, indicating its potential in swarm robotics applications.

Note in all of the videos, the swarm is performing a collective search to find a Point of Interest located at (-10,10). The Vector Fields (VF) show the different profiles. Radius refers to the communication radius.  

 

 

 


 

 

 

 

more ...

[1] | 2 vor

Last Modification: 27.11.2020 - Contact Person:

Sie können eine Nachricht versenden an: Webmaster
Sicherheitsabfrage:
Captcha
 
Lösung: