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.

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

@inproceedings{umlauft:swarmfabsim:22,
  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

Call for Papers Fifteenth International Conference on the Synthesis and Simulation of Living Systems (ALIFEXV)

The Fifteenth International Conference on the Synthesis and Simulation of Living Systems (ALIFEXV) will be held in Cancun, Mexico on July 4th-8th. 2016.

http://xva.life

Paper/ abstract submission deadline: February 14th, 2016
Notification to authors: March 25th, 2016
Camera ready due: April 24th, 2016

We cordially invite you to submit your work in either full paper (8 pages) or extended abstract (2 pages) format. Accepted papers and abstracts will be published by MIT Press as open-access electronic proceedings.

Topics of interest include, but are not limited to, the following aspects of Artificial Life:

– Computational humanities/anthropology/archeology
– Evolution of language, computational linguistics
– Bio-inspired, cognitive and evolutionary robotics
– Self-replication, self-repair and morphogenesis
– Artificial chemistry, origins of life
– Cellular automata and discrete dynamical systems
– Perception, cognition and behavior
– Embodied, interactive systems
– Collective dynamics of swarms
– Complex dynamical networks
– Evolutionary dynamics
– Ecological and social dynamics
– Economy/society/social media as living systems
– Methodologies and tools for artificial life
– Living technology
– Applications to nanotechnology, biology or medicine
– Applications to business and finance
– Applications to games and entertainment
– Artificial life-based art
– Philosophical and ethical issues
– Artificial life and education
Paper/abstract formatting instructions:
To properly format their contributions, participants should download and use the following formatting instructions and template files:

Please download DOC template and LaTeX template.

Note that color figures are possible, since the proceedings will be published online in electronic format.

Papers and abstracts should be uploaded in a single file, in PDF format, to the EasyChair paper submission system. No other format is accepted.

NOTE: Even if you are submitting only an abstract, please prepare it in a formatted PDF and upload it to EasyChair just like a full paper submission. Don’t use the “Abstract Only” check box.

Workshop papers are managed separately from the main conference. To submit a paper to a workshop, go to its own website, which will be listed in the Workshops page.

Camera-ready requirements for MIT Press:

All the authors must follow the following instructions carefully:

All pages sized consistently at 8.5 x 11 inches (US letter size).
No visible crop marks.
Images at no greater than 300 dpi, scaled at 100%.
Embedded open type fonts only.
All layers flattened.
No attachments.
All desired links active in the files.

Note that individual articles (PDFs) must not exceed 5 MB if they are to be indexed by Google Scholar. Additional information about Google Scholar can be found here: http://www.google.com/intl/en/scholar/inclusion.html.

Authors of selected papers will be invited to publish an extended version of their work in a special issue of the Artificial Life journal published by MIT Press.

NOTE: At least one author of every accepted paper or poster must be registered 30 days prior to the conference, or the paper/poster will be withdrawn.

Simulating Swarm Behavior with Scratch

My young audience

Today I was giving a lecture to kids at age 8 to 12 at our University. The lecture was part of an initiative called “Kinderuni” (Children’s University) which aims at increasing awareness of our academic business already at young age.
In my lecture I approached the general topic of computer software by the example of the programming language Scratch. Scratch is a graphical programming language designed by the Lifelong Kindergarten Group at the MIT media lab. The language aims to be simple, colorful and fun in order to enable and motivate children at a young age to create programs with their own ideas.
I explained how Scratch works and together the kids and I coded a simple computer game in 25 minutes, which was definitely a challenge to do this in this short time. Another challenge was to create the connection between making a simple game with scratch and doing research at a university. However, this might be easier than you think. While Scratch is in general a programming language for kids, it can be actually useful to explore and demonstrate multi-agent behavior with comparably little effort. Especially with the introduction of cloned objects in Scratch 2.0, the implementation of swarm behavior with a variable number of interacting agents became easy.

Some projects from swarm behavior studio

The Scratch Studio Swarm Behavior gathers online simulations and games related to swarm behavior, multi-agent systems, clone interactions, self-organizing systems, and artificial life. The simulations show how Scratch can be used to demonstrate swarm behavior and how such a simulation can be implemented. Scratch is of course of low value regarding functionalty and performance - so you might have to drop the idea of having kindergarten kids coding the simulations for your next journal paper ;-).

Comparison of Metaheuristic Algorithms for Evolving a Neural Controller for an Autonomous Robot

Robots are a good way to test things. Hope our robot overlords of the future will not take this to personal…

The task

We used a simulation of a robot that is searching for a light source as a testbed to compare how well a solution can be created by evolving an artificial neural network (ANN). While ANNs are often programmed using example input-output pairs which are learned by a backpropagation algorithm (supervised learning), in our case we left the how up to the system and only required the what – the robot should be able to find the light source by operating its wheels and using its sensors – that is called learning with belated rewards or reinforcement learning. We compared different evolutionary algorithms (EA), namely simple EA, two dimensional cellular EA, and random search, according to their performance in evolving a successful algorithm for the light-searching robot. In our experiments we studied the effects of EA parameters on performance, such as population size and number of generation. The simulations have been done using the open-source tool Framework for Evolutionary Design (FREVO).

The results explain how the choice of the neural network (three-layered or fully-connected) may inf

Possible implementation in hardware

luence the quality of a final solution. The results indicate that cEA and simple EA are the most applicable for evolving a neural controller. A fully-connected ANN outperforms three-layered ANN in all conducted experiments. Based on our findings, we recommend to use cEA and fully-connected ANN for problems that require short evaluation phase. For a large number of generations and population size the efficiency of both algorithms are approximately the same. In the experiments we measured an influence of population size and number of generations on performance of metaheuristic algorithms. The dependencies on these parameters are negligible. This information is important for the conduction of experiments. To accelerate a simulation, the population size should be the same as the number of cores on the server, where these experiments will be performed.

• Sergii Zhevzhyk, Wilfried Elmenreich, Comparison of Metaheuristic Algorithms for Evolving a Neural Controller for an Autonomous Robot, Transactions on Machine Learning and Artificial Intelligence, pp. 62-76, 15, 2014.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.

Boxplots grouped by categories

Simulating self-organizing systems often requires a compact representation of numerical data. One way to achieve this is via Boxplots,which indicate statisical distributions of data series through their quartiles. Usually, a box shows the median, the lower and the upper quartile values of a data series. The whiskers depict the lowest datum still withing 1.5 IQR (interquartile range) of the lower quartile and the highest datum still within 1.5 IQR of the upper quartile. Boxplots depict a good deal of information for statistical interpretation of data. Most of the tools for statistical computing and graphics can easily build boxplots, e.g., the boxplot function in R, the boxplot function in MATLAB, and the boxplot function in Python. As you can see, there are many affordable tools to display boxplots, but things get tricky if there is a need to group in categories. To achieve this, Sergii Zhevzhyk wrote a Python program using the matplotlib library which supports customization and adaptation of graphs. Data are loaded from the given csv files. One boxplot sample is shown below. The source code of our implementation can be found at GitHub.         

The image above shows the results of two measurements for different type of the candies. The comparison of two measurements can be done without problem, because they placed close to each other and have different colors. Two files (first file, second file) contain the data for this boxplot.

Links:

• GroupedBoxplots – the project on GitHub containing source code and samples.
• a paper using grouped box plots:
  Sergii Zhevzhyk, Wilfried Elmenreich, Comparison of Metaheuristic Algorithms for Evolving a Neural Controller for an Autonomous Robot, Transactions on Machine Learning and Artificial Intelligence, pp. 62-76, 15, 2014.

Scalability in Self-Organizing Systems

One of the properties of self-organizing systems is scalability. It means that system keeps its working capabilities even if we remove some of its components or add more of them. In our reseach, we employ different evolutionary algorithms (EAs) to create a self-organizing system. In particular, algorithms like a simple evolutionary algorithm or a two dimensional cellular EA are used  for adjusting the synaptic weights of an neural controller. The best solutions are identified based on simulations of the target application. Typically, the simulation parameters limit the applicability of the solution - there is no guarantee that an evolved solution is adaptable or scalable to situations not specified in the simulation parameters. On the other hand, there are many examples in nature where solutions could be successfully employed in other contexts. We decided to check how our soccer teams, which consist of evolved neural controllers, can scale.

For the FIFA World Cup in Brazil we organized our own tournament between evolved self-organized soccer teams. This is an exciting show - to see how simple agents having only partial information about the environment around them are reaching its goal (score a goal) as a team. Will they be able to play in the same manner if we take the contoller, trained in the simulation with 10 players per team, and increase or decrease the number of players? This question has remained open until today.

In our first scenario, we assume that we invited two soccer teams to show us a fantastic game, but due to some circumstances, only 4 players per teamshow up.
Thus our first experiment can be seen in the video below.
Despite the players being evolved in a context of 11 players on each side, reducing the number of players did not affect the ability of players to show good game.

To check the other extreme, we settled a very dangerous experiment - each team consisting of 40 players! The results were stunning (see video below). These soccer heroes could play as a team even with significantly increased number of players. Unfortunately, they could not play for a long time in this mode: Marco Materazzi headbutted Zinadine Zidane in the chest and shouted "Revenge!"; Luis Suarez bit two players in order to show his perfect teeth; Diego Maradona scored the goal by striking the ball with his hand and this time he was disqualified for this trick. We didn't care about these incidents since we got the results of our experiment:

Links:

• I. Fehervari and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
• I. Fehervari and W. Elmenreich. Evolution as a tool to design self-organizing systems. In Self-Organizing Systems, volume LNCS 8221, pages 139–144. Springer Verlag, 2014.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.
• More simulated matches at Lakeside Labs WM Orakel http://www.robotoracle.at/

Simulating the Soccer World Cup 2014

You cannot wait for the soccer World Cup to start? We proudly present a peek preview of the World Cup 2014 - played by teams created with evolutionary algorithms. Using our evolutionary tool FREVO for designing self-organizing systems we have evolved neural networks that make robots playing soccer. During the evolution phase, a fitness function combines different aspects of gameplay like zone defense, man-marking, passing, shots, and goals. By tweaking the weights for these parameters we can influence the playing style of a team while the overall gameplay is still generated automatically by the evolutionary process. Thus we can simulate playing styles of different national teams and then match them against each other.

The following video shows a simulation of Brazil versus Croatia, the opening game of the world cup. The commentary is from Toni Polster, a legendary Austrian soccer player.

While the result is credible, we have not done this to exactly predict the outcome of the games - this would spoil the whole tournament! Furthermore, our approach is not meant for prediction but a system to train a distributed agent-based system to achieve an emergent cooperative behavior in a self-organized way. Setting up this work helped us in improving our understanding how we can create and guide self-organizing systems. We have chosen the soccer simulation as a demonstration because in soccer the global goal (no pun intended) can be achieved in so many different ways , for example with a defensive, offensive, kick-and-rush, pass-intensive, etc. style. And it is nice to watch - who said good science can't be fun!

Further readings:

• I. Fehervari and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
• I. Fehervari and W. Elmenreich. Evolution as a tool to design self-organizing systems. In Self-Organizing Systems, volume LNCS 8221, pages 139–144. Springer Verlag, 2014.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.
• More simulated matches at Lakeside Labs WM Orakel http://www.robotoracle.at/

Prof. A. E. Eiben at Lakeside Labs: The Next Big Thing in Artificial Evolution

Professor Àgoston E. Eiben will give an interesting talk at the Lakeside Labs / Alpen-Adria-Universität Klagenfurt on April 10th 2014, 15:00 CET, Room L4.1.114  

Abstract:
This talk presents a vision about the upcoming breakthrough in artificial evolution: animate artefacts that (self-)reproduce in physical spaces. In other words, we witness the “Evolution of Things”, rather than just the evolution of digital objects, leading to a new field of Embodied Artificial Evolution. After presenting this vision some of the technical challenges are elaborated and related to the main algorithmic/technical requirements to the current know-how in evolutionary computing. Finally, Prof. Eiben will speculate about possible applications, their societal impacts, and argue that these developments will radically change our lives.

For those who cannot attend or want to warm up on the topic, we recommend Eiben's TED talk "Evolution at Work":

Bio:
A.E. Eiben is a professor of Computational Intelligence on the VU University Amsterdam and Visiting Professor in the Department of Electronics of the University of York, UK. He is one of the European early birds of Evolutionary Computing; his first EC paper dates back to 1989 and he co-authored the first comprehensive book on the subject. He has been organizing committee member of practically all major international evolutionary computing conferences and editorial board member of related international journals. He have also coordinated or participated in several EU research projects. Prominent themes in his work include multi-parent recombination methods, evolutionary constraint handling, evolutionary art, artificial life, and evolutionary robotics. Furthermore, he is concerned with methodological issues, especially the design and calibration of evolutionary algorithms (parameter tuning off-line as well as parameter control on-line). Lately he became interested in artificial evolutionary systems that are physically embodied in real time and real space. This goes far beyond conventional evolutionary computing in digital spaces and implies great new opportunities and challenges – see his TEDx talk and a journal paper on the vision, and the The Triangle of Life framework for a possible implementation in robotic systems that can self-reproduce. On the long term, a broad range of possible “incarnations” can emerge and form a radically new way of engineering. Furthermore, they can serve as an apparatus to investigate deep scientific questions about evolution in a new substrate, different from carbon-based life as we know it.

Solving the „Tracking Game“

Guest article from Doris A. Behrens


Games taking place in a shared environment are characterized by the fact that the effectiveness of individual decisions heavily depends on the decisions of other players. Our algorithm OPTGAME is able to approximate the evolution of choices to be made if a number of independent decision makers seek to reach individually desirable states. The evolution of states subject to control is described by a system of nonlinear difference equations. We call this a „tracking game“, since is an extension of the linear regulator problem (also known as „tracking problem“) that is well known from LQ optimal control theory.
OPTGAME is a tool that steers the control and state paths towards desired outcomes. It is novel in a way that it works for game theoretic systems with nonlinear constraints. It searches for equilibrium solutions by iteratively applying a sequence of local linearization and optimization over the entire planning horizon. The tool yields three types of non-cooperative equilibrium solutions (open-loop Nash equilibrium, feedback Nash equilibrium, feedback Stackelberg equilibrium) plus one cooperative solution (Pareto-optimal strategy).
An example for such a game could be the decision-making within a monetary union such as the European Monetary Union (EMU). In this game all but one player represent countries with intentions for economic growth, employment and limited budget deficit and one player represents the European Central Bank, aiming solely at price stability. Besides trade-offs between state variables, for example the well-known trade-off between unemployment and price stability (see Phillips curve), there are strong economic interdependencies due to international trade.

European Monetary Union

For instance, if a single country aims at economic growth, one option could be to increase the demand for goods and services from the public sector. This increases production in response to demand, which in turn increases incomes. However, within an open economy the future success strongly depends on the situation and behavior of the other member countries. In order to find a solution for this problem it is necessary to estimate the countries’ individual parameters as well as the degree of economic interdependencies (like trade) between countries.
Such models, in order to be accurate are inherently nonlinear, which cannot be solved analytically by a linear model such as the LQ game. In our work we apply OPTGAME to a monetary union macroeconomic model based on the nonlinear MUMOD1 model. In this model, there are basically two groups of countries, one economically stronger than the other, all experiencing a brief period of recession.

Doris A. Behrens is a senior re-
searcher working on optimization
in techno-socio-economic systems
at the Alpen-Adria-Universität
Klagenfurt

Without policy intervention all countries would experience a deep recession and an enormous increase in public debt. By applying OPTGAME for different solution concepts we learn that macroeconomic properties like public debt, economic growth, inflation, etc. can be significantly improved with system-aware control actions of players.

The OPTGAME tool is available as MATLAB implementation upon request (Contact Doris A. Behrens).

Literature:

Doris A. Behrens, Reinhard Neck, Approximating Solutions for Nonlinear Dynamic Tracking Games, Computational Economics, Springer, February 2014. DOI: 10.1007/s10614-014-9420-4

Reinhard Neck, Doris A. Behrens, A macroeconomic policy game for a monetary union with adaptive expectations. Atlantic Economic Journal, 37(4), 335–349, 2009. DOI: 10.1007/s11293-009-9186-6f

Evolution as a Tool to Design Self-Organizing Systems

Self-organizing Systems exhibit numerous advantages such as robustness, adaptivity and scalability, and thus provide a solution for the increasing complexity we face within technical systems. While they are attractive solutions, due to their nature, designing self-organizing systems is not a straightforward task. Artificial evolution has been proposed as a possible way to build self-organizing systems, but there are still many open questions on how an engineer should apply this method for this purpose.

Evolutionary design process

We propose a system architecture for evolving self-organizing systems that marks the major cornerstones and decisions the designer has to face:

In particular, the following aspects need to be considered:

Simulation setup:

• Accuracy/granularity of the simulation?
• Physical capabilities of the agent + environment
• How many agents, homogeneous/heterogeneous configuration?

Interaction interface:

• How should the agent interact with the environment/other agents
• Number/type of sensors
• Ability to change the environment (enable stygmergy)

Evolvable decision unit

• Must be evolvable
• Smooth search space, not too large
• Genotype-to-phenotype mapping

Search algorithm

• There exists literally a zoo on metaheuristic optimization algorihtms (Cuckoo search, Honeybee, Frog leap, Firefly, ...)
• Ability to find global optimum
• Number of tweaking parameters?

Objective function

• Should contribute to a smooth search space
• Avoid modeling the solution instead of the problem
• Mapping of multiple objectives (or weighted sum?)

Framework for Evolutionary Design (FREVO)

• Is a way to implement an evolutionary design task for multi-agent system
• Needs a simulation of the problem
• Interface for sensor/actuator connections to the agents
• Feedback from a simulation run -> objective function
• Written in Java, runs on multiple platforms including Linux, Mac OS, Windows
• FREVO is available as open soure at http://frevo.sourceforge.net/
• FREVO introduction video including installation, setting up a simulation and running it (length 6 minutes)

Literature

• I. Fehérvári and W. Elmenreich. Evolution as a tool to design self-organizing systems. In Proceedings of the 7th International Workshop on Self-Organizing Systems. Springer Verlag, May 2013.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.

JGridMap - Fast and Easy Visualization of Objects in a Grid

Conway's Game of Life implemented
with JGridMap

Many models for complex systems start with some markings on a piece of squared paper. This is probably the most straightforward approach to depict agents in their environment. However, in order to model a complex system, the cells need to interact, which is hard to implement on paper but easily done with a computer. However, if you, like me, have a favor for Java, then there was no quick way for implementing a cellular automata with graphical visualization. In the end, programmer have spent 90% of the time getting the graphics right and at most 10% remained for the actual model of interest.

After reviewing several frameworks for displaying nice grid structures, we decided there is a need for an easy to use and fast Java library. Our project JGridMap is now about two years old and mature to support you for fast and easy visualization of objects in a grid. With JGridMap you can quickly implement a visualization for cellular automata including proper routines for zooming. Cells can be painted with a selected color or with a picture of your choice, which makes it easy to create attractive visualizations.

JGridMap is available as open source project at http://sourceforge.net/projects/jgridmap/ under GPLv3.

Examples of projects done with JGridMap:

Langton's Ant simulation:

Vampires vs. Werewolves simulation:

Integrated in the Framework for Evolutionary Design (FREVO):

Graphical engine for a Smart Grid simulator:

Call for Papers 6th Complex Systems Modelling and Simulation Workshop (CoSMoS 2013)

Università degli Studi di Milano-Bicocca, Italy
1 day workshop held between 1 - 5 July 2013

http://www.cs.york.ac.uk/nature/cosmos/cosmos2013.html
cosmos2013-group@york.ac.uk

SPECIAL ISSUE OF NATURAL COMPUTING JOURNAL: we will be organising a special issue of the Natural Computing journal (http://www.springer.com/computer/theoretical+computer+science/journal/11047) based on the themes raised in the workshop. Suitable workshop submissions will be invited to submit to this special journal issue.

The 6th workshop on Complex Systems Modelling and Simulation (CoSMoS 2013) will take place as a 1-day satellite workshop of the Unconventional Computation and Natural Computation conference (http://ucnc2013.disco.unimib.it/) held between 1st and 5th July at the Università degli Studi di Milano-Bicocca, Italy. The CoSMoS workshops series provides a forum for research examining all aspects of the modelling and simulation of complex systems. This year, we will place a special focus on how complex systems simulations can be used to simulate unconventional and natural computation.

Constructing models and simulations of complex systems is a challenging and interdisciplinary task. Elements might include choice of modelling tools and techniques, simulation infrastructures, concurrency, the process of moving from models to simulations, arguing validity of simulations, and the identification of reusable engineering techniques such as patterns. The CoSMoS workshop series continues an initiative, based at the Universities of York and Kent, UK, to develop a framework and infrastructure for the construction of complex systems simulations.

Submitted papers will undergo a rigorous peer-review process and accepted papers will appear in the workshop proceedings published by Luniver Press. Proceedings of the previous CoSMoS workshop are available: http://www-users.cs.york.ac.uk/psa/cosmos2013/proceedings.html


AREAS OF INTEREST

We are seeking submissions that explore aspects of complex systems modelling and simulation, with a special focus on how complex systems simulations can be used to simulate unconventional and natural computation. Areas of interest include, but are not limited to:

* Complex systems simulation case-studies
* Modelling tools and techniques
* Simulation infrastructures
* Arguing validity of simulations
* Concurrency and distribution techniques
* Identification of reusable engineering techniques
* Working across scientific disciplines


SUBMISSIONS

We are accepting both full papers (to be presented orally) and abstracts (to be presented via a poster). Both full papers and abstracts will appear in the workshop proceedings.

For submission via abstract, please submit an abstract not longer than 2 pages of LNCS format that summarises the content of the poster you wish to present. Full papers can be of any length up to a maximum of 25 pages of LNCS format. If you wish to exceed the page limit, or have any other queries, then please email cosmos2013-group@york.ac.uk in advance of submission.

LNCS formatting details can be found here: http://www.springer.com/computer/lncs?SGWID=0-164-7-72376-0

Papers should be submitted via EasyChair here: https://www.easychair.org/conferences/?conf=cosmos2013


IMPORTANT DATES

* Paper Submission: 22 March 2013
* Notification of acceptance: 22 April 2013
* Camera ready copies: 6 May 2013
* CoSMoS Workshop: 1 day between 1 - 5 July 2013


WORKSHOP CHAIRS

* Paul Andrews, Department of Computer Science and York Centre for Complex Systems Analysis, University of York, UK
* Susan Stepney, Department of Computer Science and York Centre for Complex Systems Analysis, University of York, UK

Vampires vs. Werewolves

Tonight is Halloween! Typical Halloween activities include telling scary stories, so I am going to tell you a story about vampires and werewolves.
Once upon a time in a valley in Complexania, there were Werewolves and Vampires. They could live from the magic field in the valley, as long as they did not grow too large. The valley is also magically rolled up to a torus surface, so have no fear kids, the creatures cannot escape. Their size is genetically given, but when they reproduce, the target size might mutate by plus/minus 10 percent. If one of this creatures could gather enough magic (which is easier when they are small), an offspring was created in a free field beside it. So far it is clear that being smaller is advantageous because you can save more energy and reproduce faster. However, a werewolf is also able to kill a smaller vampire and steal its energy. Vice versa, large vampires are able to kill and consume werewolves which are smaller than them. This triggered an arms race of larger and larger creatures in the valley. At one time they grew so large that they had to constantly feed on their foes, since the magic field alone was not able to support their hunger for energy any more. So they grew and fought each other, numbers went up and down on both sides, until one species was left. Or both died.

Do you want to know who won the battle? Find out for yourself and use the simulation below:

In case you cannot see the simulation, your browser does not support applets. I made a video of the simulation for this case:

Small vampires and werewolves, which can feed sufficiently from the magic field, are characterized by light red and gray color, respectively. The red and black squares indicate larger vampires and werewolves.

Have fun and happy Halloween!

Sixth IEEE Xtreme Programming Contest: Bunnies in the Forest

At the annual IEEE Xtreme Programming Contest teams of three programmers are given a set approximately 20 problems, for which they have to write a program that solves the task. Choice of programming language is mostly free; the contest system supports Java, C, C++, C#, PHP, Python, Ruby. The contest goes on for exactly 24 hours, therefore the "Xtreme" in its name. In the 2012 issue, there had been 1900 teams worldwide. To be successful, it is necessary to work concentrated under pressure for hours and have excellent programming skills. In fact it is rather software engineering skills, since a sloppy or ad-hoc programming style does not lead to successful solutions. Watching a good team one can observe the classic stages of software engineering like specification of operational and performance qualification, design specification, implementation, black box/white box testing, and validation in a fast-forward manner within a few hours.


One important aspect of software engineering is also the proper specification of the intended project by the customer. A mistake in the initial specification is crucial, so it is important to state a task in a clear unambiguous manner. In practice, unfortunately, a software engineering team often has to guess what the customer really wants. This was the case for problem AA at IEEE Xtreme 2012:

In a forest, there were 'x' bunnies, 50% male, and 50% female, all adults. Bunnies doubles every 15 days, 10% of the baby rabbits dies at birth. They mature after 30 days, 30% leave the forest, and rest becomes rabbits. In every 30 days , 25% dies off due to flu. If every bunny dies off, the bunny world ends. Calculate the final number of bunnies alive after 1 year for any number of initial bunnies, x.

The problem is very interesting since it defines a simulation of an ecologic system. See for comparison the description of the Lotka Volterra system featuring rabbits and foxes. However, the problem specification is unclear in many aspects. What is the essential difference between an "adult bunny", a bunny, a "baby bunny" and a rabbit? It is not mentioned how to handle rounding, if the leaving of the forest happens once for a group that just matured or if an adult rabbit is tempted to leave the forest every time.

The problem had been complemented by these two test cases:

Test Case 1
444 (input)
0 (output)
Test Case 2
30000 (input)
56854 (output)

So a group of 444 dies out after one year, while a group of 30000 almost doubles. Given that the described effects are all linearly superimposable (except for possible rounding errors), it seems odd how the two groups yield so different results. 30000 is around 68 times as much as 444, so the results just also differ by that factor. The following python program implements one possible interpretation of this problem:

b0=0            #newborn bunnies  
b15=0           #15 day old bunnies 
b30=input()     #30 day old, read from stdin
for i in range(25): #one year
    print "t:",(i*15)," bunnies:",(b0+b15+b30)
    oldb0=b0
    b0=int(b30*0.9) # babies, 10% die
    b30=int(b30+b15*0.7) # maturing, 30% leave forest
    b15=int(oldb0)
    b0=int(b0*0.75)      # 25% die off by the flue
    b15=int(b15*0.75)    # 25% die off by the flue
    b30=int(b30*0.75)    # 25% die off by the flue

Running the program gives us 772 bunnies after one year with a starting population of 444 and 54816 for a starting population of 30000, both in contradiction to the test cases. Obviously the specification is unclear or wrong. Among all 1900 participating teams, not a single one was able to find the correct solution. Poor bunnies :-)

• Experiences from a previous IEEE Xtreme Programming Contest

On rabbits and foxes, see also section 2 of

• W. Elmenreich, R. D'Souza, C. Bettstetter, and H. de Meer. A survey of models and design methods for self-organizing networked systems. In Proceedings of the Fourth International Workshop on Self-Organizing Systems. Springer Verlag, pages 37-49, 2009.