Transcript pes.h - METU

Parallelized Evolution
System
Onur Soysal, Erkin Bahçeci
Erol Şahin
Dept. of Computer Engineering
Middle East Technical University
http://www.kovan.ceng.metu.edu.tr
ISCIS’03
04/11/2003
www.kovan.ceng.metu.edu.tr
Evolutionary Methods
Simulation of Natural Evolution
Using evolution mechanisms to solve
optimization problems
Survival of the fittest
...........
Chrom.1: 1010001110...
Generation n
Select
Reproduce
Mutate
Generation n+1
...........
ISCIS’03
Chrom.2: 0011110101...
Population n
.........
Chrom.1: 0101011001...
Chrom.2: 1100110111...
Population n+1
.........
www.kovan.ceng.metu.edu.tr
Genetic Algorithms
Encoding
Binary representation
Stochastic search
Guided by measure of
fitness
Problem-specific
fitness function
Genetic operators
Mutation
Crossover
ISCIS’03
www.kovan.ceng.metu.edu.tr
Evolutionary Robotics
Sensors
Controller
???
Actuators
Motivation
Controller: Sensor-actuator relationship
Difficult to design manually in nontrivial
tasks
To be in the shoes of a robot?
Solutions of evolutionary robotics
Evolving controllers
ISCIS’03
www.kovan.ceng.metu.edu.tr
Genotype  Phenotype:
Generic Controller
Sensor data
Chromosome
010101 100111...
Controller
Controller
Convert to controller
parameters
Use the controller
in robots
Actuator outputs
ISCIS’03
www.kovan.ceng.metu.edu.tr
Genotype  Phenotype:
Neural Network Controller
Sensor data
Chromosome
010101 100111...
Convert to neural
network weights
Use the neural network
to control robots
Actuator outputs
ISCIS’03
www.kovan.ceng.metu.edu.tr
Fitness Evaluation
Use controller
on physical robots
on simulated robots
Observe behavior
Calculate fitness value
Repeat
for each generation
• for each chromosome
ISCIS’03
www.kovan.ceng.metu.edu.tr
Physics Based Simulation
Importance of realistic simulations
Pros
Much faster runtime
compared to physical
implementation
Behavioral similarity
to physical robots
Realistic interactions
Cons
High processing demand!
Example libraries: ODE, Vortex, Havok
ISCIS’03
www.kovan.ceng.metu.edu.tr
Single Machine Limitations
Computation required
Solving Ordinary Differential Equations
Increasing complexity with more collisions
Time estimates for single computer
Order of minutes for a single evaluation
For 100 chromosomes and 100 generations
• Total time > a week on a single machine
ISCIS’03
www.kovan.ceng.metu.edu.tr
Cluster Computing
Cheap alternative to supercomputers
Large-grained problems
Example application
SETI@home: Search for Extraterrestrial
Intelligence at home
ISCIS’03
www.kovan.ceng.metu.edu.tr
Cluster Computing Solution to
Evolutionary Robotics
Fitness evaluations dominate
computation time
Fitness evaluations are independent
Master-Slave model
Master: GA
Slaves: Fitness evaluations
ISCIS’03
www.kovan.ceng.metu.edu.tr
Parallel Evolution System (PES)
Parallel Genetic Algorithm library
Distributed fitness evaluation
Central genetic algorithm
Supports interoperability of multiple
platforms
ISCIS’03
www.kovan.ceng.metu.edu.tr
PES Architecture
Server: GA
Clients: Fitness evaluation
Server
Application
ISCIS’03
PES-S
PES-C
Client Application
PES-C
Client Application
PES-C
Client Application
www.kovan.ceng.metu.edu.tr
PES Communication Model
Ping mechanism
Task and result packets
PES-S
ping
PES-C
ping reply
PES Network Adapter
PES Network Adapter
task
result
ISCIS’03
www.kovan.ceng.metu.edu.tr
PES-S Architecture
PES-S
Server
Application
Task generator
Best solutions
Network
Adapter
Task Manager
GA Engine
ISCIS’03
www.kovan.ceng.metu.edu.tr
PES-C Architecture
PES-C
Network Adapter
ISCIS’03
Task
Fitness
Client
Application
www.kovan.ceng.metu.edu.tr
PES Usage: Server
Server Code
#include <pes.h>
int main()
{
PES_INIT();
for each generation
{
PES_EVAL_INDIVIDUALS();
PES_NEXT_GENERATION();
}
}
ISCIS’03
www.kovan.ceng.metu.edu.tr
PES Usage: Client
Client Code
#include <pes.h>
int main()
{
PES_INIT();
while true
{
RECEIVE_TASK();
EVAL_TASK();
SEND_RESULT();
}
}
ISCIS’03
www.kovan.ceng.metu.edu.tr
PES Features
Multi-platform support
Linux and Windows via PVM
Improved fault tolerance
Ping mechanism to detect non-responding clients
Supplies GA facilities
Built-in crossover, mutation and selection functions
Simplified usage
Automatic task distribution / fitness collection
Single line for evaluating fitness of whole
population
Basic load balancing
ISCIS’03
www.kovan.ceng.metu.edu.tr
Our Application
Task: Aggregation
Getting 10 robots as close as possible
Minimal sensors and communication
1
Modified single layer NN for control
No memory/learning
No world knowledge
Probabilistic inputs
Fitness evaluation
2
3
3
1
2
3
1
2
3
R
2000 steps of simulation
Total distance as fitness measure
ISCIS’03
www.kovan.ceng.metu.edu.tr
Sample Application Results
ISCIS’03
www.kovan.ceng.metu.edu.tr
Processor Load Balancing
Dynamic
simulation
Varying number
of collisions
Varying task
complexity
Varying
processor load
Diamonds: tasks
Solid lines: Start of new generation
ISCIS’03
www.kovan.ceng.metu.edu.tr
Fault Tolerance
Processor 2
fails
Detected at
ping at 15th sec
Task restart at
19th sec
ISCIS’03
Red lines: Ping
Blue lines: Generation
Numbers: Task index
www.kovan.ceng.metu.edu.tr
Efficiency &
Speedup
ISCIS’03
www.kovan.ceng.metu.edu.tr
Discussions & Future Work
Generation gap
Asynchronous reproduction
Dynamic host list
Progress monitor
Extension to the Internet
ISCIS’03
www.kovan.ceng.metu.edu.tr
PES Sources & Documentation
Source distribution under Gnu Public
License (GPL)
User manual
Functional reference
Sample applications
http://www.kovan.ceng.metu.edu.tr/software/PES
ISCIS’03
www.kovan.ceng.metu.edu.tr