Advent Programming Contest 2015

An Advent calendar is a special calendar used to count or celebrate the days in anticipation of Christmas. Advent calendars typically begin on December 1 and provide a window to open until December 24. Usually they have windows, which you can open each day containing some chocolate or other stuff. But what is better to kill some time until Christmas, Hanukkah, Yule, Kwanzaa, Diwali, Boxing Day, etc. than an Advent calendar giving you a programming problem every day?

The Advent Programming Contest, being organized by the IEEE Student Branch Klagenfurt will provide a new problem every day from December 1st to December 24th. You can submit solutions any day until the contest ends on December 26. You can choose to use C, C++, C#, Java, Perl, Python 2.x or Python 3.x as programming language. The programming tasks can be solved with short programs (typically less than 100 lines of code). Until a solution is correct you can submit your program as often as you want (but please don't spam our server). The number of tries will not be a criterion for determining your score. The idea is to do it just for fun, but we will try to announce a winner after the contest is closed. The event is open to everyone. There are separate categories for pupils, university students and others. If you want to participate, please register at http://mooshak.nes.aau.at/ (Registration is also possible after 1st December)

Random Numbers in Java: Comparison of java.util.random, Xorshift, and PCG

In a previous post, we have shown how to replace the Java random number generator with a faster Xorshift algorithm, which also has nicer properties than the Java random number generator which was implemented in 1995.

Melissa E. O’Neill from Harvey Mudd College suggests a new class of random number generators called PCG. For a detailed description, see her paper "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation".

Like the Xorshift algorithm, PCG is using a couple of shift and bitwise logical operators to generate random integers. Typically this is faster that Java's linear congruential generator. We have implemented a simple version of the PCG algorithm in order to compare its performance to java.util.random and our Xorshift implementation.

The best way to replace the Java random generator in our opinion is to make a subclass of java.util.random and to overwrite the next() method. For Xorshift, the algorithm is as follows:

import java.util.Random;

/**
 * A subclass of java.util.random that implements the 
 * Xorshift random number generator
 */

public class XSRandom extends Random {
 private long seed;

 public XSRandom(long seed) {
  this.seed = seed;
 }

 protected int next(int nbits) {
  long x = seed;
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  seed = x;
  x &= ((1L << nbits) - 1);
  return (int) x;
 }
}

We implemented the PCG algorithm in Java based on the minimal C code example by M.E. O'Neill at pcg-random.org:

import java.util.Random;

/**
 * A subclass of java.util.random that implements the 
 * PCG32 random number generator
 * Based on the minimal code example by M.E. O'Neill / pcg-random.org
 * Licensed under Apache License 2.0
 */

public class PCGRandom extends Random {
 private long inc;
 private long state;
 
 public PCGRandom(long seed) {
  this.state = seed;
  inc=1;
 }

 public PCGRandom(long seed, long initseq) {
  // initseq selects the output sequence for the RNG
  this.state = seed;
  this.inc=initseq;
 }

 protected int next(int nbits) {
  long oldstate=state;
  // Advance internal state
  state=oldstate * 6364136223846793005L + (inc | 1);
  // Calculate output function (XSH RR), uses old state for max ILP
  long xorshifted = ((oldstate >> 18) ^ oldstate) >> 27;
  long rot = oldstate >> 59;
  return (int) ((xorshifted >> rot) | (xorshifted << ((-rot) & 31)));
 }
}

To use the class in legacy code, you may also instantiate an XSRandom object and assign it to a java.util.Random variable:

  java.util.Random rand = new XSRandom(); // or new PCGRandom

All method calls to rand are then using the new implementation.

The PCG algorithm comes with better properties regarding its period. But what about the performance?
We tested the performance by calculating 10⁷ random numbers subsequently, repeating this 10 times with different starting seeds. Then we compared the average execution time for a program compiled under Java 8 running single threaded on an core i7 notebook computer. Results show that for our implementation, the PCG algorithm has a very similar execution time to the original Java random generator, while the Xorshift is significantly faster.

Execution time of java.util.random, Xorshift, and PCG. Please note that y axis starts at 10 ns.

So if you mainly care about speed, go for Xorshift. If statistical quality is important, go for PCG. If you want a bad random number generator and have a lot of time, stick with java.util.random.

Five postdoctoral fellowships in complex systems, Mexico

The Center for Complexity Science of the National Autonomous University of Mexico is seeking outstanding candidates for five one year postdoctoral positions beginning in August, 2015. Research plans from all areas related to complex systems are encouraged.

Please send CV and research plan to cgg [at] unam.mx before June 10th.

Original post: Complexes: Five postdoctoral fellowships in complex systems, UNAM

Hardware for Swarm Robotics

Collective behavior that emerges from the interactions between agents and with the environment are one of the most prominent examples of self-organizing systems. The field of swarm robotics allows to research and engineer such collective behavior. However to do this, there is the need for small cost-effective swarmbots. 

The table below lists a number of robots used in real experiments in the field of swarm robotics. It shows the most important parameters and information about the robots simplifying comparison between them. For more detailed description there are links (right after the robots' names) to websites or articles exhibiting specifications or conducted experiments.

Robot	Cost	Locomotion	Speed (cm/s)	Size (cm)	Battery life (hours)	Communication
Alice[1]	N/A	wheels	4	2.1x2.1x2.1	10	RF
Jasmine[1,2]	$118	wheels	N/A	2.6x2.6x2.6	1-2	RF, IR
Elisa[1]	$390	wheels	60	∅5	3	RF,IR
Colias[1,2]	$37	wheels	35	∅4	1-3	IR
Kilobot[1,2]	$111	vibration	1	∅3.3	3-24	IR
Flockbots[1]	$500	wheels	N/A	∅18	3	Wi-Fi
E-puck[1,2]	$850	wheels	13	∅7	1-10	Bluetooth, ZigBee
Kobot[1,2]	$1174	wheels	N/A	∅12	10	ZigBee
R-one[1,2]	$322	wheels	30 cm/s	∅10	6	RF, IR
ZeeRO[1]	N/A	wheels	N/A	∅25	N/A	Bluetooth
MinDART[1]	N/A	tracks	17	29x24x37	N/A	None
marXbot[1,2]	N/A	treels	50	∅17	4-7	Wi-Fi
JL-2[1]	N/A	tracks	20	35x25x15	2	Wi-Fi
Khepera IV[1, 2]	$2700	wheels	100	∅14	4-7	Wi-Fi, Bluetooth

One of the first questions, coming up in the beginning of a project concerning swarm robotics, is money. Conducting real experiments with dozens of robots require high investments to buy all needed hardware and software. The price of the robots varies greatly that depends on a number of sensors and actuators, quality of a robot's frame, and demand for a particular robot. Unfortunately, the price of some robots is not specified. The most of these robots have an open-source design and code so they can be built from scratch in case there is such a need.

The table shows that the majority of the robots are differential drive robots whose movement is based on two wheels placed on either side of the robot. It allows achieving higher speed and precisely controlling the direction of movement. However, there are also some disadvantages, such as a need for a prepared surface without pits and bumps. Robots using the tracks usually can move on the unprepared surface, which facilitates a preparation for experiments and demonstrations. A unique type of locomotion is vibration (check the Kilobot robot) which tends to be slow and imprecise way of movement. It also requires a special smooth surface.

Size matters in the field of swarm robotics. A swarm consists of a large number of individuals which are quite effective in performing of important tasks for surviving of the colony. A significant number of robots is important in order to reproduce the swarm behavior or to check a hypothesis.

Unlike individuals in the real swarms, robots cannot generate energy from organics and still require a source of energy such as a battery. The working time of a robot depends on the capacity of battery and the amount of sensor and actuators using by a robot in experiments. Some of the robots have charging stations (e.g. Elisa, Jasmine) which may be useful in conducting of long-term experiments. The marXbot goes even further supporting exchange of the battery in less than 10 seconds without shutting down the power.

Communication in swarm robotics can play a crucial role while the effectiveness of the whole colony depends on how well the robots can send and receive messages. There are two types of communication: abstract (e.g. Wi-Fi, Bluetooth, ZigBee, RF) and situated (e.g. IR). Both of them work well for messages exchange, but situated communication provides additional information about the sender and the message, e.g. strength of the signal and its direction.

The choice of the robot depends on experiments where it will be used. Select the most important features of the future research and pick a robot that fits best.

Call for Papers Ninth IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2015)

 The Ninth IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2015)

Boston Massachusetts; 21-25 September 2015

https://saso2015.mit.edu/

Part of FAS* - Foundation and Applications of Self* Computing Conferences

Colocated with:

The International Conference on Cloud and Autonomic Computing (CAC 2015)

The 15th IEEE Peer-to-Peer Computing Conference (P2P 2015)

Aims and Scope

The aim of the Self-Adaptive and Self-Organizing systems conference series (SASO) is to provide a forum for the foundations of a principled approach to engineering systems, networks and services based on self-adaptation and self-organization. The complexity of current and emerging networks, software and services, especially in dealing with dynamics in the environment and problem domain, has led the software engineering, distributed systems and management communities to look for inspiration in diverse fields (e.g., complex systems, control theory, artificial intelligence, sociology, and biology) to find new ways of designing and managing such computing systems. In this endeavor, self-organization and self-adaptation have emerged as two promising interrelated approaches. They form the basis for many other self-* properties, such as self-configuration, self-healing, or self-optimization. Systems exhibiting such properties are often referred to as self-* systems.

The ninth edition of the SASO conference embraces the inter-disciplinarity and the scientific, empirical, and application dimensions of self-* systems and welcomes novel results on both self-adaptive and self-organizing systems research. The topics of interest include, but are not limited to:

• Self-* systems theory: theoretical frameworks and models; biologically- and socially-inspired paradigms; inter-operation of self-* mechanisms;
• Self-* systems engineering: reusable mechanisms, design patterns, architectures, methodologies; software and middleware development frameworks and methods, platforms and toolkits; hardware; self-* materials;
• Self-* system properties: robustness, resilience and stability; emergence; computational awareness and self-awareness; reflection;
• Self-* cyber-physical and socio-technical systems: human factors and visualization; self-* social computers; crowdsourcing and collective awareness; human-in-the-loop;
• Applications and experiences of self-* systems: cyber security, transportation, computational sustainability, big data and creative commons, power systems; swarm systems and robotics.
• Self-* in education: experience reports; curricula; innovative course concepts; methodological aspects of self-* systems education

Contributions must present novel theoretical or experimental results; novel design patterns, mechanisms, system architectures, frameworks or tools; or practical approaches and experiences in building or deploying real-world systems and applications. Contributions contrasting different approaches for engineering a given family of systems, or demonstrating the applicability of a certain approach for different systems, are equally encouraged. Likewise, papers describing substantial innovation or insights in the use and communication of self-* systems in the classroom are welcome.

Where relevant and appropriate, accepted papers will also be encouraged to participate in the Demo or Poster Sessions.

Important Dates

Abstract submission: May 8, 2015
Paper submission: May 22, 2015 (There will be no extensions of this deadline)
Notification: June 30, 2015
Camera ready copy due: July 17, 2015
Conference: September 21-25, 2015

Submission Instructions

All submissions should be 10 pages and formatted according to the IEEE Computer Society Press proceedings style guide and submitted electronically in PDF format.
Please register as authors and submit your papers using the SASO 2015 conference management system, which is located at:

https://www.easychair.org/conferences/?conf=saso2015

The proceedings will be published by IEEE Computer Society Press, and made available as a part of the IEEE digital library. Note that a separate call for poster submissions has also been issued.
Review Criteria

Papers should present novel ideas in the cross-disciplinary research context described in this call, clearly motivated by problems from current practice or applied research.

We expect both theoretical and empirical contributions to be clearly stated, substantiated by formal analysis, simulation, experimental evaluations, comparative studies, and so on. Appropriate reference must be made to related work. Because SASO is a cross-disciplinary conference, papers must be intelligible and relevant to researchers who are not members of the same specialized sub-field. Authors are also encouraged to submit papers describing applications. Application papers are expected to provide an indication of the real world relevance of the problem that is solved, including a description of the deployment domain, and some form of evaluation of performance, usability, or comparison to alternative approaches. Experience papers are also welcome, but they must clearly state the insight into any aspect of design, implementation or management of self-* systems which is of benefit to practitioners and the SASO community

Conference General Chairs

• Howard E. Shrobe, MIT CSAIL, Cambridge, MA, USA
• Julie A. McCann, Imperial College London, UK

Program Chairs

• Emma Hart, Edinburgh Napier University
• Gregory Sullivan, BAE Systems AIT
• Jan-Philipp Steghöfer, University of Gothenburg, Sweden

SEAHORSE: A Middleware for Search and Delivery of Information Units based on an Artificial Hormone System Algorithm

SEAHORSE structure

With the rise of networked smart devices and the so called Internet of Things, services require more scalability and robustness to handle the complexity of the underlying ecosystem. In some situations (e.g., disaster areas, large-area sports events, battle fields, etc.), a traditional network infrastructure does not exist, or is expensive to set up. In this context content is also consumed in a more dynamic way than in traditional environments. By looking at principles found in nature we can see that it is possible to handle complexity and dynamics by relying exclusively on simple, local decisions (bio-inspired self-organizing systems). As an example, ants are exploring the surrounding area to find food, and if found they go back to their home base leaving pheromones to guide other ants.
We introduce SEAHORSE, a middleware showing by example how an existing self-organizing algorithm can be generalized. SEAHORSE is a first step for bringing self-organizing algorithms towards real-world applications.
By specifying interfaces to the application the middleware transparently handles the distribution of content. We show two use cases from different technical fields and performed a parameter analysis to reduce the configuration effort.

A. Sobe, W. Elmenreich, T. Skalicky, and L. Böszörmenyi. SEAHORSE: Generalizing an artificial hormone system algorithm to a middleware for search and delivery of information units. Elsevier Journal of Computer Networks, 2015.

Advent Programming Contest 2014 Awarding

At the awarding ceremony

In December 2014, the Advent Programming Contest (APC) was held for the third time. The joint event between the Faculty of Technical Sciences and the IEEE Student Branch Klagenfurt enjoys increasing popularity every year. This time there were 345 enthusiastic participants who accepted the challenge and tryed to solve a daily programming task from December 1st to December 24th. I hope everybody who participated enjoyed the problems, even though nobody was able to solve all the tasks. While every problem was solved at least once, the maximum number of solved tasks by any participant was 23 out of 24 – given the hardness of several of the problems this is an excellent result.
The winners of the three categories of "student", "university staff" and "other" were announced at a formal ceremony organized by the IEEE Student Branch Klagenfurt. The best student adventcoder was Philip Gasteiger, student of computer science at Alpen-Adria-Universität Klagenfurt.
The best pupil adventcoder, Simon Dörrer, came from HTL Mössingerstraße Klagenfurt. Ben Wright, a recent graduate of the University of Tennessee, Martin, now working as a software engineer won the third category “other” and attended the ceremony via webcast.

FREVO 1.2 release

We proudly announce the new release 1.2 of FREVO (FRamework for EVOlutionary design). FREVO helps to reduce the time to implement, set up and run an evolutionary algorithm to evolve an agent's behavior as a solution to a particular control problem. FREVO supports decomposing the task into problem definition, solution representation and the optimization method. The componentwise separation allows to experiment with different combinations of algorithms and neural networks for different tasks.

The following components were added to FREVO:

• HEMS – a simulation for modeling trading behavior of loads and local energy generators.
• SinglePong – a simulation of the one player pong game where several paddles can cooperate in order to achieve better performance.
• Pong – a simulation of the pong game where two teams can play against each other.

Quick start:

• download the newest version at frevo.sourceforge.net 
• unpack the ZIP file
• unless you have it already on your system, install Java 
• execute the createscrips.jar ("java -jar createscrips.jar") 
• you can now run FREVO using the script named launch_Frevo 

...or have a look at the following video explaining the basic steps to get started with FREVO:

For more information see the following sources:

• A. Sobe, I. Fehérvári, and W. Elmenreich. Frevo: A tool for evolving and evaluating self-organizing systems. InProceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.
• A. Monacchi, S. Zhevzhyk, and W. Elmenreich. HEMS: A home energy market simulator. Computer Science - Research and Development, 2014. 
• I. Fehérvári and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
• FREVO - software used for the evolutionary algorithm.
• WMOrakel - the championship between self-organized soccer teams which were evolved using FREVO.

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.

Call for Papers 10th International Conference on Soft Computing Models in Industrial and Environmental Applications (SOCO 2015)

10th International Conference on
Soft Computing Models in Industrial
and Environmental Applications
SOCO 2015

Burgos, Spain
15th-17th June, 2015
http://soco.usal.es

In conjunction with:

8thComputational Intelligence in Security for Information Systems

CISIS 2015

and

 6th International Conference on EUropean Transnational Education

ICEUTE 2015

The 10th International Conference on Soft Computing Models in Industrial and Environmental Applications will take place in Burgos, Spain. Soft computing represents a collection or set of computational techniques in machine learning, computer science and some engineering disciplines, which investigate, simulate, and analyze very complex issues and phenomena. This conference is mainly focus on its industrial and environmental applications.

Topics of interest include, but are not limited to:
• Green Computing
• Evolutionary Computing
• Neuro Computing
• Probabilistic Computing
• Immunological Computing
• Hybrid Methods
• Causal Models
• Case-based Reasoning
• Chaos Theory Fuzzy Computing
• Intelligent Agents and Agent Theory
• Interactive Computational Models

The application fields of interest cover, but are not limited to:
• Decision Support
• Process and System Control
• System Identification and Modelling
• Optimization
• Signal or Image Processing
• Vision or Pattern Recognition
• Condition Monitoring
• Fault Diagnosis
• Systems Integration
• Internet Tools
• Human Machine Interface
• Time Series Prediction
• Robotics
• Motion Control & Power Electronics
• Biomedical Engineering
• Virtual Reality
• Reactive Distributed AI
• Telecommunications
• Consumer Electronics
• Industrial Electronics
• Manufacturing Systems
• Power and Energy
• Data Mining
• Data Visualisation
• Intelligent Information Retrieval
• Bio-inspired Systems
• Autonomous Reasoning
• Intelligent Agents

Important Dates

Paper submission deadline: 24th January, 2015
Acceptance notification: 13th February, 2015
Submission of final papers: 3rd March, 2015
Final version submission: 13th March, 2015
Conference dates: 15th-17th June, 2015