Darwin2K
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.
http://darwin2k.sourceforge.net/
Overview
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…
PMGC
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.
Extensibility
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.
Experiments
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.
Conclusion
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 ).