czech english


Simulation and Automated Synthesis for Robotics

Darwin2K is a free, open-source toolkit for robot simulation and automated design. It features numerous simulation capabilities and an evolutionary algorithm capable of automatically synthesizing and optimizing robot designs to meet task-specific performance objectives. Darwin2K uses Parameterized Module Configuration Graph (PMCG) to represent the robots. As the name implies, robots are composed of modules, each of which may contain parameters describing properties of the module. You can build your own robot or let Darwin2k design one for you from the modules of your choosing for the task at hand.


Darwin2K is written in C++ and the author claims it contains around 60 000 lines of code (something around 4MB). This is a lot of work for a one man . You can freely download it from sourceforge, it is distributed under the GPL. In order to play with it you'll need some *nix (Linux and Irix 6.x tested) with X windows, OpenGL/MesaGL/OpenInventor, xforms and also perl >= 5 is strongly recommended.
The system consists of several parts:
  • dyno — the dynamics engine
  • rapid — collision detection package (TODO link)
  • rtc — real time communication package (not included in the distribution)
  • d2k — synthetizer and evaluator and everything related
There is a nice documentation consisting of tutorial (not very complete), a PhD. thesis of the author and reference manual generated from the source code by Doc++. I recommend reading them in the order listed above.

What's Interesting

So you might ask: “What makes the project worth looking at?” There are a lot of things actually…


Parameterized Module Configuration Graph is a little bit awkward name for a very natural looking representation of the genome. The graph is a DAG (directed acyclic graph) where nodes are parametrized modules and edges represent the relative position of the nodes. There are about 40 different types of modules prepared for direct use and database of different parametrizations corresponding to some Maxon and HD System equipment. The PMCG allows representation of a wide range of robots, including modular and monolithic robots, mobile robots, and robots with multiple or bifurcated manipulators.

Multiple Metrics Optimization

Usually the weighted sum approach is used in the case were there are multiple objectives to be optimized. However, there are cases where this approach is not appropriate. Let's say the objective is to design robot to fulfil a certain task while conserving little energy and having small mass. Using the weighted sum all criteria are taken into account. But is it right to say that robot having no mass and cosuming no energy is better than robot fulfiling part of the task? That is where Requirement Prioritization (RP) comes. The RP allows the designer to assign priorities to the different metrics and the engine optimizes the population in waves starting with the topmost priority moving to the next only after a certain threshold has been reached (ie. only when the robot is able to fulfil the task, the energy consumption and mass can be optimized). The thesis explains the motivation more thoroughly including the way the RP has evolved from other approaches.

Dynamic Simulation for Fitness Evaluation

Darwin2K supports two modes of simulation: kinematic and dynamic. Kinematic simulation considers only positions, velocities, and accelerations. There is no inclusion of force, torque, mass, or angular inertia when computing the motion of the robot. In contrast, dynamic simulation is based on the forces and torques applied to the robot’s links and computes the accelerations caused by those forces and torques. Depending on the task at hand the appropriate simulation type can be chosen (kinematic is computationaly easier while dynamics accounts for more factors). There is a limitation in the dynamic simulator since it does not model forces arising from contact or friction.

Distributed Fitness Computation

A pool of clients running the evaluator can be used to calculate fitness of the individuals. In order to compensate for different performances of the clients a steady-state evolution is used as opposed to generational evolution. When using generational evolution each step a whole new generation of individuals is created. These individuals are then evaluated and a new generation is created by applying the genetic operators. With this approach the performace of the system would be limited by the slowest evaluator. Using the steady-state evolution a new individuals are continuously created and sent for evaluation. When a new evaluated individual comes in, one from the original set is deleted to make a room for it.

Elitism and Diversity Preservation

In a generational Evolution Algorithm (EA), elitism means always duplicating the best few solutions when the next generation is created. In a steady-state algorithm, elitism always preserves the best few solutions. Elitism prevents an EA from losing the best solutions found to date and can improve convergence toward good solutions by giving them more opportunities for reproduction.
However, explicit measures must be taken to prevent a single configuration from dominating the population. Otherwise, due to the way steady-state EA works the population will contain many identical copies of a single individual, which clearly do not contribute any additional information about the search space. Because individuals can potentially persist in the population indefinitely, every time an individual is duplicated its probability of selection is effectively increased further. This creates a positive feedback loop, frequently resulting in a population that consists mostly of identical configurations.
In a generational EA (as opposed to Darwin2K’s steady-state EA), this is not a problem: a duplication does not immediately affect the probability of a configuration being reproduced, since the duplicate is added to the next generation instead of to the current population. Darwin2K prevents duplicate configurations from being introduced into the population by searching the population for existing configurations that are identical to each new configuration. If the new configuration is a copy, then mutation operators are applied until a novel configuration is generated (or until a time-out is reached). [section 3.3.1 of the thesis]

Commonality Preservation

While the crossover operators used in fixed-length genetic algorithms inherently preserve commonality, those for trees and graphs do not. When doing crossover with bitstrings the possitions with 0 or 1 in both parents will have the same value in the offsprings as well. This behavior is beneficial since the properties shared by the parents probably most contribute to their good performace. Crossover for graphs do not have this property implicitly so some measures must be taken in order to get it. Darwin2K achieves this by finding the larges common subgraph in the parents and preserving it for the offsprings.


Darwin2K’s synthesis algorithm is independent of the task and the type of robot, allowing the system to be extended to address a wide range of synthesis tasks even without recompilation of the core system.


The experiments presented in the thesis demonstrate synthesis of fixed-base and mobile manipulators, multiple manipulators, and a walking robot, and include generation of robot kinematics, dynamics, structural properties, actuator selection, and control and task parameters. The breadth of experiments and the detail of synthesized results demonstrate a substantial improvement over previous systems for automated robot configuration synthesis.


Darwin2K is a very nice system definitely worth cheking out if you are interested in a simulation of robot dynamics and/or automated design. There are some limitation in the current system that might limit its usability beyond the goals set by its author. As a standalone robotic simulator one would miss simulation of contact with objects and terrain and also simulation (and encoding in genom) of closed chains (thus far the graphs of modules need to be trees). As a robot design tool one could miss an interactive tool with a direct visual feedback. Anyway, the thesis is something worth reading, even though it sometimes sounds little bit like a bussiness report repeating throught the text that the software is the best (it could be true, it'd just be nice if author left more room for the reader to make his/her own opinion ).