Tuesday, May 9, 2023

Bottom-Up Bio-Inspired Algorithms for Optimizing Industrial Plants

Scheduling in a production plant with a high product diversity is an NP-hard problem. In large plants, traditional optimization methods reach their limits regarding computational time. In this paper, we use inspiration from two bio-inspired optimization algorithms, namely, the artificial bee colony (ABC) algorithm and the bat algorithm, and apply them to the job shop scheduling problem. Unlike previous work using these algorithms for global optimization, we do not apply them to solutions in the solution space, though, but rather choose a bottom-up approach and apply them as literal swarm intelligence algorithms. We use the example of a semiconductor production plant and map the bees and bats to actual entities in the plant (lots, machines) using agent-based modeling using the NetLogo simulation platform. These agents then interact with each other and the environment using local rules from which the global behavior – the optimization of the industrial plant – emerges. We measure performance compared to a baseline algorithm using engineered heuristics (FIFO, fill fullest batches first). Our results show that these types of algorithms, employed bottom-up, show promise of performance improvements using only low-effort local calculations.

Our newest research paper builds upon the simulation framework presented in http://demesos.blogspot.com/2022/08/swarmfabsim-simulation-framework-for.html

Asking Question at ICAART Panel Session
As in this earlier paper, algorithm performance was compared against a reference baseline algorithm using the key performance indicators of makespan, flow factor, delay, and machine utilization. Results show that using these swarm intelligence algorithms in a bottom-up manner with only low-effort local calculations can lead to performance improvements. The paper details the application of two algorithms to factory optimization, an artificial bee algorithm (ABC) and a bat-inspired algorithm. Both algorithms are used in a bottom-up approach, not as a global optimizer. In this type of approach, the swarm members do not represent solutions in the solution space of the problem but actual lots and/or machines in the factory. In conclusion, swarm intelligence algorithms can be a powerful tool for production plant scheduling optimization. Although the case study is based on a semiconductor production plant, the same approach applies well to other production plants as well.

Paper presentation at ICAART'23
Further information can be found in the paper

M. Umlauft, M. Gojkovic, K. Harshina and M. Schranz: Bottom-Up Bio-Inspired Algorithms for Optimizing Industrial Plants, Proceedings of ICAART 2023, ISBN: 978-989-758-623-1, doi:10.5220/0011693400003393

Wednesday, April 5, 2023

They say the best way to learn is by doing, but sometimes the best way is to automate!

Ah, the version control system git. We've all been there, typing out commands to push a new commit to the server, trying to remember which is which. For example to update the remote repository with your local changes, I use the git pull, add, commit and push commands in sequence. This will ensure that the remote repository is up-to-date with the local repository. Well, I had enough of it. I decided to take matters into my own hands and wrote a script that I named 'gits'. It's just a one-liner that does the steps of git pull, git add, git commit and git push for me, without all the hassle of having to type each paticular command. The commit message is given as argument to gits, if I forget about it, the script puts the number of changed files there as a placeholder.

@echo off
:: Batch script to commit and push your git changes
:: and quickly resolve conflicts
:: by Wil
:: March 2023 V0.21
:: The script has the decency to ask before adding new files
:: If an argument is given, this is used as the commit message
:: otherwise a generic commit message is generated


for /F "delims=#" %%E in ('"prompt #$E# & for %%E in (1) do rem "') do set "ESCchar=%%E"
set "red=%ESCchar%[91m"
set "green=%ESCchar%[92m"
set "yellow=%ESCchar%[93m"
set "magenta=%ESCchar%[95m"
set "cyan=%ESCchar%[96m"
set "white=%ESCchar%[97m"
set "black=%ESCchar%[30m"
set "nocolor=%ESCchar%[0m"
set "bold=%ESCchar%[1m"

::stage modifications and deletions
set countmodified=0
for /f %%C in ('git ls-files -m') do set /A countmodified=!countmodified!+1

if NOT "!countmodified!"=="0" (
  git add -u

set /A total=!countmodified!

for /f %%C in ('git diff --cached --numstat') do set /A total=!total!+1

::check if there are untracked (new) files
set countnew=0
for /f %%C in ('git ls-files . --exclude-standard --others') do set /A countnew=!countnew!+1

if NOT "!countnew!"=="0" (
  git ls-files . --exclude-standard --others
  echo There are !countnew! files, should they be added?
  CHOICE /C asx /M "Press [A] for adding the files, [S] for skipping without and [X] for exiting this script."
    exit /b
    git add .
    set /A total=!total!+!countnew!

if "!total!"=="0" (
  echo Nothing to do!
) else (
  if "%1"=="" (
    git commit -m "updated !total! files"
  ) else (
    git commit -m "%*"
  git pull
  git push

  set conflicts=0
  set unsolved=0
  for /f %%C in ('git ls-files -u  ^| cut -f 2  ^| sort ^|uniq') do (
    set cff=%%C
    call :SUBCHOICE
      git checkout --theirs !cff!
      git add !cff!
      git checkout --ours !cff!
      git add !cff!
      set /A unsolved=!unsolved!+1
      exit /b
    set /A conflicts=!conflicts!+1

  if !unsolved! GTR 0 (
    echo There are still %red%!conflicts! files%nocolor% in conflict.
    exit /b
  if !conflicts! GTR 0 (
    git commit -m "merged conflicted files"
    git push

exit /b

echo|set /p="File %red%!cff!%nocolor% is in conflict "
CHOICE /C dtosx /M "(show [D]iff, use [T]heirs, use [O]urs, [S]kip file, e[X]it script)"
      git diff !cff!
      goto SUBCHOICE
   exit /B !ERRORLEVEL!

The Windows .bat code is a script for committing and pushing git changes, with the ability to quickly resolve conflicts. It sets up some color codes for the text output and checks for modifications, deletions, and untracked (new) files. It then adds the files to be committed and either uses an argument given to the script as the commit message, or a generic commit message. It then pulls, pushes, and checks for conflicts. If conflicts are present, it provides the user with the option to view a diff, select a version of the file, skip the file, or exit the script. If conflicts are resolved, the script commits the merged files and pushes them.

gits in action. Here it found files not added to the repo yet and proposes to add them, to do the commit without adding them or to stop the script


Thursday, March 9, 2023

Discovering New Ways to Navigate: A Swarm Intelligence-Based Robotic Search Algorithm Integrated with Game Theory

Robotics has come a long way in the last few decades, and we continue to see innovations in the field as researchers seek to improve robotic search algorithms. Recently, researchers have proposed a decentralize and asynchronous swarm robotic search algorithm integrated with game theory to better disperse robots in the environment while crossing obstacles and solving mazes. This prevents early convergence and improves the efficiency of the searches.

In the proposed algorithm, individual robots, while searching, play a sequential game at each iteration, and based on that, choose their velocity update rule. This strategic game works well in search environments with different levels of complexity and especially improves search efficiency further in complex environments. In the target problem, since the environment is unknown, it is not possible to preplan a path to the target. And there is no difference between static and dynamic obstacles, as the robots cannot distinguish them. Thus, in the proposed method, passing and avoiding obstacles are synchronized with the target searching.

Example of a maze-like complex environment and its mapping to a fitness function

The simulation results showed that, following the proposed algorithm, robots disperse well in search environments, and therefore search speed increases by up to 24% and attended path length to target lessens by up to 23.5% in complex search environments. Also, the proposed algorithm has a success rate equal to the state-of-the-art, which is 100% in all of the tested environments.

For more details check out the paper:

Khalil Alrahman Youssefi Darmian, Modjtaba Rouhani, Habib Rajabi Mashhadi, and Wilfried Elmenreich. A swarm intelligence-based robotic search algorithm integrated with game theory. Applied Soft Computing, 122, 4 2022. (doi:10.1016/j.asoc.2022.108873)

Robotics is an exciting and ever-evolving field, and this new algorithm shows us the potential of swarm intelligence-based robotic search algorithms. We look forward to seeing more innovations in this area as researchers continue to explore new ways to navigate.

Tuesday, August 2, 2022

SwarmFabSim: A simulation framework for bottom-up optimization in flexible job-shop scheduling using Netlogo

It was great to be in presence at a conference again. At the 12th International Conference on Simulation and Modeling Methodologies, Technologies and Applications, aka SIMULTECH, we presented our paper 

Martina Umlauft, Melanie Schranz, and Wilfried Elmenreich. SwarmFabSim: A simulation framework for bottom-up optimization in flexible job-shop scheduling using Netlogo. In Proceedings of the 12th International Conference on Simulation and Modeling Methodologies, Technologies and Applications - SIMULTECH. SciTePress, July 2022. (doi:10.5220/0011274700003274

Click triangle for Bibtex entry
  author = {Umlauft, Martina and Schranz, Melanie and Elmenreich, Wilfried},
  title = {{SwarmFabSim}: {A} Simulation Framework for Bottom-up Optimization
in Flexible Job-Shop Scheduling Using {N}etLogo},
  booktitle = {Proceedings of the 12th International Conference on Simulation and Modeling Methodologies, Technologies and Applications - SIMULTECH},
  year = {2022},
  month = jul,
  publisher = {SciTePress},
  doi = {10.5220/0011274700003274},

The paper shows how to the programming language NetLogo to model and simulate a factory producing according to the job-shop manufacturing principle. The main contribution is a modular simulation framework that can apply various algorithms to optimize a make-to-order manufacturing system and supports multiple configurable scenarios. The evaluation framework was used to assess the effectiveness of an artificial hormone algorithm compared to a naïve basic implementation and a reference baseline algorithm. The evaluation was based on three key performance indicators: Flow factor, delay, and utilization. The simulations show promising results of the artificial hormone algorithm in three reference scenarios with significant improvements over the reference algorithms. The implementation of the simulation environment is published as open source in the Git repository https://swarmfabsim.github.io. Readers are welcome to contribute with their ideas and developments.

Screenshot of the SwarmFabSim application

Tuesday, February 9, 2021

An Artificial Hormone-based Algorithm for Production Scheduling

Artificial hormone systems are inspired by the natural endocrine system that adjusts the metabolism of tissue cells in our body. By connecting decisions and actions in a system to the production and evaporation of artificial hormones, it is possible to create a bio-inspired self-organizing algorithm.

Application areas for such algorithms are problems with many agents to be coordinated, where existing optimization approaches come to their limit. An example of such a problem is the production of logic and power integrated circuits (ICs) in the semiconductor industry. Unlike the high-volume production of memory ICs, wafer production in the logic and power sector has a large product mix. This involves many processing steps and dynamic changes of involved machines.

Weekly workloads can involve around 100 000 operations on thousands of machines. Optimizing such a system for work in progress and flow factor is an NP-hard problem. At this size, existing dispatching rules and linear optimization methods cannot cope with the NP-hard search space, thus not optimize the entire system.

To address this issue, we have modeled a production plant as a self-organizing system of agents that interact with each other in a non-linear way. As it is common in the semiconductor industry, wafers are combined in groups of 25 pieces forming a so-called lot. In our approach, an artificial hormone systems is used to express a lot's urgency and the need for new lots at a machine type, thus providing a system using local information for optimization. The algorithm builds upon five principles, which are 

  • (i) machines produce hormone to attract lots, 
  • (ii) hormone diffuses process-upstream, 
  • (iii) incoming lots diffuse hormone, 
  • (iv) lots are prioritized by their timing, and 
  • (v) lots are attracted by hormone. 

Via these mechanisms, machines can balance their workload by pulling required lots towards them. The algorithm has been implemented and evaluated in a NetLogo simulation model. Simulation results indicate that the artificial hormone system improves around 5% for overall production time and flow factor compared to a baseline algorithm. Future work will investigate if the hormone algorithm can be used on top of existing production systems. In a productive system an improvement of 5% would be highly notable.

More information can be found on the SWILT project webpage and in the paper

Wilfried Elmenreich, Alexander Schnabl, and Melanie Schranz. An artificial hormone-based algorithm for productionscheduling from the bottom-up. In Proceedings of the 13th International Conference on Agents and Artificial Intelligence. SciTePress, February 2021.

Click triangle for Bibtex entry
  author = {Elmenreich, Wilfried and Schnabl, 
    Alexander and Schranz, Melanie},
  title = {An artificial hormone-based algorithm
    for production scheduling from the bottom-up},
  booktitle = {Proceedings of the 13th International 
    Conference on Agents and Artificial Intelligence},
  year = {2021},
  month = feb,
  publisher = {SciTePress}

Wednesday, November 11, 2020

Benford’s Law and the US 2020 Presidential Election Votes

Benford’s law states that if you get a big range of data from the real world and you look at the lead digit of each of the values you get significantly more 1s than other digits if the numbers span multiple magnitudes.

As one application, Benford’s law is used to detect fraud in accounting. There typically, the pairs of the two first digits are analyzed and plotted according to their frequency in order to detect anomalies. An anomaly can have different explanations though.

For example, in the US 2020 presidential elections, the proportion of digits 1 and 2 on first digits for votes for Mr. Biden is lower than expected, while for votes for Mr. Trump the proportion of digits 1 and 2 on first digits is slightly higher.

In the video below, Matt Parker analyzes the situation and shows that the more densely populated areas in the US, where a majority of Mr. Biden's votes are coming from, have precincts with mostly the same size. Thus here the condition of having data spanning multiple magnitudes is not fulfilled, hence we get a distribution of first digits that deviates from the prediction by Benford’s law.

When looking at the frequency of the last digits, there is an anomaly in the voter data for Mr. Trump. Instead of having a roughly equal distribution of frequency of last digits, the lower digits are much higher. This is due to the fact that a majority of votes for Mr. Trump come from smaller precincts thus favoring the smaller numbers.


Thus, the deviation of voting counts (from precincts with a standardized size) from Benford’s Law is not an indicaton of voter fraud but rather a phenomenon to be expected.

Further reading:
Deckert, J., Myagkov, M., & Ordeshook, P. (2011). Benford's Law and the Detection of Election Fraud. Political Analysis, 19(3), 245-268. doi:10.1093/pan/mpr014

Wednesday, September 9, 2020

Swarm Intelligence and Cyber-Physical Systems

Swarm Intelligence (SI) is a popular multi-agent framework that has been originally inspired by swarm behaviors observed in natural systems, such as ant and bee colonies. In a system designed after swarm intelligence, each agent acts autonomously, reacts on dynamic inputs, and, implicitly or explicitly, works collaboratively with other swarm members without a central control. The system as a whole is expected to exhibit global patterns and behaviors.

When is it advantageous to use a Swarm approach?
The scaling principle depicts a range where a swarm
outperforms a linear system of the same size

Although well-designed swarms can show advantages in adaptability, robustness, and scalability, it must be noted that SI system have not really found their way from lab demonstrations to real-world applications, so far. This is particularly true for embodied SI, where the agents are physical entities, such as in swarm robotics scenarios.

In the paper 

Melanie Schranz, Gianni di Caro, Thomas Schmickl, Wilfried Elmenreich, Farshad Arvin, Ahmet Sekercioglu, and Micha Sende. Swarm Intelligence and Cyber-Physical Systems: Concepts, challenges and future trends. Swarm and Evolutionary Computation, 60, 2020. (doi:10.1016/j.swevo.2020.100762)

we start from these observations, outline different definitions and characterizations, and then discuss present challenges in the perspective of future use of swarm intelligence. These include application ideas, research topics, and new sources of inspiration from biology, physics, and human cognition. To motivate future applications of swarms, we make use of the notion of cyber-physical systems (CPS). CPSs are a way to encompass the large spectrum of technologies including robotics, internet of things (IoT), Systems on Chip (SoC), embedded systems, and so on. Thereby, we give concrete examples for visionary applications and their challenges representing the physical embodiment of swarm intelligence in

  • autonomous driving and smart traffic,
  • emergency response,
  • environmental monitoring,
  • electric energy grids,
  • space missions,
  • medical applications,
  • and human networks.

In the future, swarm-based applications will play an important role when there is not enough information to solve the problem in a centralized way, when there are time constraints which do not allow to find an analytical solution, and when the operation needs to be performed in a dynamically changing environment. With an increasing complexity in upcoming applications this will mean that SI will be applied to solve a significant part of ubiquitous complex problems.