Research Blog
CI in Sport Games
We have been developing Algorithms, Simulations, and HW for Sport Games in the past years. Our newest research is on the Tennis Game:
- Carlo Nübel
- Match Point AI: A Novel Reinforcement Learning Framework for Evaluating Data-Driven Tennis Strategies
- Master Thesis, OVGU
- Supervision: Sanaz Mostaghim
- April 2024
Other projects were for Dart Games and Football Table (CIcker) on Hardware:
- Ruben Ortlam,
- Developing and Evaluating Smart Agents for a Football Table Game
- Master Thesis, OVGU
- Supervision: Sanaz Mostaghim
- Advisor: Christoph Steup
- October 2022
- Thomas Hennig
- Variability Analysis based on Multi-Objective Performance and Throw Acceleration in Dart-Game
- Master Thesis, OVGU
- Supervision: Sanaz Mostaghim (OvGU), Frank Ohl (Leibniz Institute for Neurobiology)
- Advisors: Heiner Zille and Lars Boenke
- November 2018
Unfolding the Variability of Clinical Data in Parkinson Treatment using Multi-objective Analysis
The typical way to analyze clinical data is to use one performance metric and extract the most important features by performing dimensionality reduction mechanisms. In this paper, we identify several performance metrics describing data of patients with Parkinson’s disease and observe a large variability of their performance when we consider these metrics separately. None of the patients has the same performance in all parameters, some are better in one and worse in others. This feature is well-known in the context of multi-objective optimization. In this paper, we propose a clustering of data based on multi-objective analysis and perform a correlation-based feature selection with statistical testing to quantify and understand the variability in the clinical data.
More Information:
- Sanaz Mostaghim, Qihao Shan, Christiane Desel, Alexander Duscha, Aiden Haghikia, Tobias Hegelmeier
- Unfolding the Variability of Clinical Data in Parkinson Treatment using Multi-objective Analysis
- 2023 IEEE Conference on Artificial Intelligence (CAI), Santa Clara, CA, USA, 2023, pp. 120-121, doi: 10.1109/CAI54212.2023.00058
Medical and Behavioral Knowledge Discovery using Multi-Objective Analysis
Objective ranking and clustering of behavioral data that utilized different metrics is an important foundation for understanding the relationship between behavior and physiological as well as neurological processes in medicine and neuroscience. Fortunately, similar problems have been extensively studied in multi-objective optimization, where a population of solutions needs to be ranked in terms of performance within a high dimensional objective space. In this paper, we take advantage of the ordinal nature of behavioral metrics, and propose a non-dominated ranking-based approach to perform Pareto dominance-based partial ranking on the test subjects of behavioral studies regarding their performances with respect to multiple metrics. We have also proposed two indicators, interfront hypervolume and intrafront spread, to measure the separation between and diversity within non-dominated fronts. They serve to gauge the validity of the produced fronts as a basis for clustering analysis. Our approach is then applied to two different datasets and its functionalities and potentials are demonstrated.
More Information:
- Sanaz Mostaghim, Qihao Shan, Christiane Desel, Alexander Duscha, Aiden Haghikia, Tobias Hegelmeier, Felix Kuhn, Stefan Remy
- Medical and Behavioral Knowledge Discovery using Multi-Objective Analysis
-
Accepted at IEEE CIBCB 2023: Conference on Computational Intelligence in Bioinformatics and Computational Biology, 29-31 August, 2023 – Eindhoven, The Netherlands
Towards Benchmarking of Pathfinding Algorithms in Path-Influenced Environments
Pathfinding Algorithms are used in many research areas in different combinations and settings. In most cases, they are used for path planning, while another interesting problem class is path paving. This class represents road or railway construction, needle injection, mining, or metro planning. Finding the shortest or quickest path or minimizing energy consumption are often the objectives of current pathfinding problems. However, the influence on the environment which is induced when paving a path is not regarded in those problems so far. The proposed problem is an epistasis problem.
In this work, we introduce the concept of path-influenced environments (PIEs), outline various paving strategies and give a detailed outlook on future research.
More details can be found here:
- Julia Heise and Sanaz Mostaghim
- Towards Benchmarking of Pathfinding Algorithms in Path-Influenced Environments
Online Learning Hyper-Heuristics in Multi-Objective Evolutionary Algorithms
In a world of rising complexities, optimization problems become more diverse, dynamic and sophisticated. To find solutions for those problems, more algorithms and algorithm components are developed. A new challenge emerges, which is the selection of the best algorithm. An approach to this are the so called “Hyper-Heuristics”, top-level optimization algorithms, that select the best bottom level optimization algorithm for one problem from a selection pool. Hyper-Heuristics can be categorized in a system with axes from “Construction” to “Selection” and “Offline” to “Online”. We apply a Hyper-Heuristic to NSGA-II to select the crossover operator. Our approach is therefore in the middle of "Selection" and “Construction”. We employ an online rewarding system to score the different operators during the optimization procedure.
Those scores are applied in two different selection mechanisms:
- Hyper-Heuristic Crossover Selector: one operator per generation, with probability depending on scores
- Hyper-Heuristic Crossover Distributor: all operators, but with a partition according to the scores
From our experiments with those selection mechanisms, we developed a new version that combines those approaches and achieved promising results and terms of generalizability of the crossover operator selection. Have a look at our full paper for more details.
More details can be found here:
- Julia Heise and Sanaz Mostaghim
- Online Learning Hyper-Heuristics in Multi-Objective Evolutionary Algorithms
- EMO 2023: Evolutionary Multi-Criterion Optimization pp 162–175, March 2023, https://doi.org/10.1007/978-3-031-27250-9_12
Surrogate Models for IoT Task Allocation Optimization
The Internet of Things (IoT) is a rapidly growing field with various applications. Efficient task allocation in IoT networks is crucial for network performance. Existing optimization algorithms rely on simulation, which can be computationally expensive for low-power devices. Our published paper proposes two surrogate models, an analytical model and a Graph Neural Network (GNN) model, to evaluate task allocation in IoT networks. These models replace costly simulations and improve reactivity to network changes. The models are evaluated using different network and task topologies, demonstrating promising results. Future improvements will include augmenting the training data to better deal with node outages and applying the surrogate models to simulations including network dynamics.
Task (blue) and network (orange) Graphs used for the evaluation of the surrogate models.
- Dominik Weikert, Christoph Steup and Sanaz Mostaghim
- Surrogate Models for IoT Task Allocation Optimization
- GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion,July 2022, https://doi.org/10.1145/3520304.3528943
Graph Networks as Inductive Bias for Genetic Programming: Symbolic Models for Particle-Laden Flows
One of our DFG-funded projects addresses Genetic Programming (GP) for a problem from fluid mechanics: We develop algorithms to identify symbolic models for the complex particle-particle and particle-fluid interactions in particle-laden flows. Such flows occur in many real-world applications, such as the fluidization of biomass particles in furnaces, or the flow of blood cells in blood plasma. One challenge is the huge number of interactions considered when billions of particles are involved. Recent studies indicate that machine learning models do not improve further when more than 30 neighboring particles are considered in the prediction of the force exerted on a particle. In other words, to predict the force on a particle, we solely need to consider the locations of its 30 closest neighbors.
In our current work, we created benchmark datasets for the force on a center particle, given the locations of its 30 closest neighbors. The interactions between particles are modeled as a directed graph, which has one outgoing edge from all neighbors towards the center particle. We induce a bias by approximating the underlying relations with a Graph Network (GN), where the influences of neighboring particles are aggregated by a sum in order to compute the force on the center particle. In the next step, the network blocks of the GN are replaced by symbolic models.
Have a look at our results and learnings from this experiment.
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.
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
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.
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
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:
More details:
- Jens Weise and Sanaz Mostaghim
- Scalable Many-Objective Pathfinding Benchmark Suite
- Accepted. IEEE Transactions on Evolutionary Computation, 2021 --> Link
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:
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
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
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.
- Tobias Benecke and Sanaz Mostaghim
- Tracking the Heritage of Genes in Evolutionary Algorithms
- Accepted at the IEEE CEC 2021
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.
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
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.
- 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
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.
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.
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.
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.
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).
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.
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
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:
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.
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
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.
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).
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
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
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
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:
- 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
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.
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
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:
More information can be found here:
- Cristian Ramirez-Atencia, Tobias Benecke and Sanaz Mostaghim
- T-EA: A Traceable Evolutionary Algorithm
- In the Proceedings of IEEE Congress on Evolutionary Computation (CEC), World Congress on Computational Intelligence, Glasgow, UK, 2020 DOI: 10.1109/CEC48606.2020.9185615 --> Link to video presentation, Link to IEEE Xplore
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:
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
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
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