python - tsp - Algoritmo evolutivo para el mecanismo de caminar Theo Jansen

libreria deap python

Question

Hay un artista / ingeniero holandés que creó un mecanismo para caminar muy elaborado. El principio de funcionamiento se puede ver aquí:

http://www.strandbeest.com/beests_leg.php

Lo curioso es que utilizó un algoritmo evolutivo hecho por sí mismo para calcular las longitudes de enlace ideales, que se describen en la parte inferior de la página.

Creé una secuencia de comandos de Python para analizar visualmente la parte del ciclo de contacto con el suelo, que debe cumplir con dos requisitos:

1. Sea lo más recto posible, para no tambalearse hacia arriba y hacia abajo;
2. Tenga una velocidad lo más constante posible, para no arrastrar un pie contra el otro;

Estos dos criterios darían lugar a un efecto de "rueda", con la máquina avanzando linealmente sin desperdiciar energía cinética.

La pregunta es:

"¿Tiene alguna sugerencia de una fórmula iterativa evolutiva simple para optimizar las longitudes de las piernas (insertando las mutaciones correctas en el código a continuación) para mejorar la trayectoria para caminar teniendo en cuenta los dos criterios anteriores?"

EDITAR: algunas sugerencias sobre la "regla de ajuste" para los candidatos del genoma:

• Tome la "parte inferior" (contacto con el suelo) del ciclo, dado que corresponde a un tercio de la revolución del cigüeñal (tenga en cuenta que la parte inferior puede tener una pendiente no horizontal y aún ser lineal);
• Aplicar regresión lineal en las posiciones de puntos de esta parte de "contacto con el suelo";
• Calcular la variación vertical a partir de la regresión lineal (¿mínimos cuadrados?)
• Calcule la variación de velocidad por la diferencia entre un punto y el anterior, paralela a la línea de regresión;
• (opcional) traza gráficas de estas "funciones de error", posiblemente permitiendo seleccionar mutantes visualmente (boooring ...; o).

Aquí está mi código, en Python + GTK, que ofrece una visión visual del problema: (EDITAR: ahora con números mágicos parametrizados sujetos a mutación por los valores de mut )

# coding: utf-8
import pygtk
pygtk.require(''2.0'')
import gtk, cairo
from math import *
class Mechanism():
def __init__(s):
pass
def assemble(s, angle):
# magic numbers (unmutated)
mu = [38, 7.8, 15, 50, 41.5, 39.3, 61.9, 55.8, 40.1, 39.4, 36.7, 65.7, 49]
# mutations
mut = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
# mutated
mn = [mu[n]+mut[n] for n in range(13)]
s.A = Point(0,0)
s.B = Point(-mn[0], -mn[1])
s.C = fromPoint(s.A, mn[2], angle)
s.ac = Line(s.A, s.C)
s.D = linkage(s.C, mn[3], s.B, mn[4])
s.cd = Line(s.C, s.D)
s.bd = Line(s.B, s.D)
s.E = linkage(s.B, mn[5], s.C, mn[6])
s.be = Line(s.B, s.E)
s.ce = Line(s.C, s.E)
s.F = linkage(s.D, mn[7], s.B, mn[8])
s.df = Line(s.D, s.F)
s.bf = Line(s.B, s.F)
s.G = linkage(s.F, mn[9], s.E, mn[10])
s.fg = Line(s.F, s.G)
s.eg = Line(s.E, s.G)
s.H = linkage(s.G, mn[11], s.E, mn[12])
s.gh = Line(s.G, s.H)
s.EH = Line(s.E, s.H)
return s.H
class Point:
def __init__(self, x, y):
self.x, self.y = float(x), float(y)
def __str__(self):
return "(%.2f, %.2f)" % (self.x, self.y)
class Line:
def __init__(self, p1, p2):
self.p1, self.p2 = p1, p2
def length(self):
return sqrt((p1.x-p2.x)**2 + (p1.y-p2.y)**2)
def fromPoint(point, distance, angle):
angle = radians(angle)
return Point(point.x + distance * cos(angle),
point.y + distance * sin(angle))
def distance(p1, p2):
return sqrt( (p1.x - p2.x)**2 + (p1.y - p2.y)**2 )
def ccw(p1, p2, px):
""" Test if px is at the right side of the line p1p2 """
ax, ay, bx, by = p1.x, p1.y, p2.x, p2.y
cx, cy = px.x, px.y
return (bx-ax)*(cy-ay)-(by-ay)*(cx-ax) < 0
def linkage(p1, l1, p2, l2):
l1 = float(l1)
l2 = float(l2)
dx,dy = p2.x-p1.x, p2.y-p1.y
d = sqrt(dx**2 + dy**2) # distance between the centers
a = (l1**2 - l2**2 + d**2) / (2*d) # distance from first center to the radical line
M = Point(p1.x + (dx * a/d), p1.y + (dy * a/d)) # intersection of centerline with radical line
h = sqrt(l1**2 - a**2) # distance from the midline to any of the points
rx,ry = -dy*(h/d), dx*(h/d)
# There are two results, but only one (the correct side of the line) must be chosen
R1 = Point(M.x + rx, M.y + ry)
R2 = Point(M.x - rx, M.y - ry)
test1 = ccw(p1, p2, R1)
test2 = ccw(p1, p2, R2)
if test1:
return R1
else:
return R2
###############################33
mec = Mechanism()
stepcurve = [mec.assemble(p) for p in xrange(360)]
window=gtk.Window()
panel = gtk.VBox()
window.add(panel)
toppanel = gtk.HBox()
panel.pack_start(toppanel)
class Canvas(gtk.DrawingArea):
def __init__(self):
gtk.DrawingArea.__init__(self)
self.connect("expose_event", self.expose)
def expose(self, widget, event):
cr = widget.window.cairo_create()
rect = self.get_allocation()
w = rect.width
h = rect.height
cr.translate(w*0.85, h*0.3)
scale = 1
cr.scale(scale, -scale)
cr.set_line_width(1)
def paintpoint(p):
cr.arc(p.x, p.y, 1.2, 0, 2*pi)
cr.set_source_rgb(1,1,1)
cr.fill_preserve()
cr.set_source_rgb(0,0,0)
cr.stroke()
def paintline(l):
cr.move_to(l.p1.x, l.p1.y)
cr.line_to(l.p2.x, l.p2.y)
cr.stroke()
for i in mec.__dict__:
if mec.__dict__[i].__class__.__name__ == ''Line'':
paintline(mec.__dict__[i])
for i in mec.__dict__:
if mec.__dict__[i].__class__.__name__ == ''Point'':
paintpoint(mec.__dict__[i])
cr.move_to(stepcurve[0].x, stepcurve[0].y)
for p in stepcurve[1:]:
cr.line_to(p.x, p.y)
cr.close_path()
cr.set_source_rgb(1,0,0)
cr.set_line_join(cairo.LINE_JOIN_ROUND)
cr.stroke()
class FootPath(gtk.DrawingArea):
def __init__(self):
gtk.DrawingArea.__init__(self)
self.connect("expose_event", self.expose)
def expose(self, widget, event):
cr = widget.window.cairo_create()
rect = self.get_allocation()
w = rect.width
h = rect.height
cr.save()
cr.translate(w/2, h/2)
scale = 20
cr.scale(scale, -scale)
cr.translate(40,92)
twocurves = stepcurve.extend(stepcurve)
cstart = 305
cr.set_source_rgb(0,0.5,0)
for p in stepcurve[cstart:cstart+121]:
cr.arc(p.x, p.y, 0.1, 0, 2*pi)
cr.fill()
cr.move_to(stepcurve[cstart].x, stepcurve[cstart].y)
for p in stepcurve[cstart+1:cstart+121]:
cr.line_to(p.x, p.y)
cr.set_line_join(cairo.LINE_JOIN_ROUND)
cr.restore()
cr.set_source_rgb(1,0,0)
cr.set_line_width(1)
cr.stroke()
cr.save()
cr.translate(w/2, h/2)
scale = 20
cr.scale(scale, -scale)
cr.translate(40,92)
cr.move_to(stepcurve[cstart+120].x, stepcurve[cstart+120].y)
for p in stepcurve[cstart+120+1:cstart+360+1]:
cr.line_to(p.x, p.y)
cr.restore()
cr.set_source_rgb(0,0,1)
cr.set_line_width(1)
cr.stroke()
canvas = Canvas()
canvas.set_size_request(140,150)
toppanel.pack_start(canvas, False, False)
toppanel.pack_start(gtk.VSeparator(), False, False)
footpath = FootPath()
footpath.set_size_request(1000,-1)
toppanel.pack_start(footpath, True, True)
def changeangle(par):
mec.assemble(par.get_value()-60)
canvas.queue_draw()
angleadjust = gtk.Adjustment(value=0, lower=0, upper=360, step_incr=1)
angleScale = gtk.HScale(adjustment=angleadjust)
angleScale.set_value_pos(gtk.POS_LEFT)
angleScale.connect("value-changed", changeangle)
panel.pack_start(angleScale, False, False)
window.set_position(gtk.WIN_POS_CENTER)
window.show_all()
gtk.main()

Answer 1

garethrees.org/2011/07/04/strandbeest/strandbeest.html

Esta es una pregunta fascinante, aunque creo que va más allá del alcance de : no es algo que vaya a resolverse en unos minutos, así que pegaré un esquema aquí y lo actualizaré si hago algún progreso. Habrá tres partes en cualquier enfoque:

1. Puntuación de la huella: ¿se rompe el vínculo? ¿La huella tiene la forma correcta? que tan plano es ¿Qué tan suave es el movimiento? ¿Pasa suficiente tiempo en la porción plana?

2. Buscando buenos valores de los números mágicos. No está claro si este tiene que ser un algoritmo evolutivo (aunque puedo ver por qué la idea de tal algoritmo atraería a Theo Jansen, ya que encaja con la metáfora animal en su arte); quizás otros enfoques como la búsqueda local (escalada de colinas) o el recocido simulado serían productivos.

3. Buscando buenas configuraciones de los brazos. Aquí es donde parece que un enfoque evolutivo podría valer la pena.

Puedes probar diferentes números mágicos en mi demostración de Javascript / canvas para ver qué tipos de movimiento puedes obtener (CD = 55.4 es bastante entretenido, por ejemplo). Hay toda una teoría matemática de los enlaces , por cierto, que conecta los espacios de configuración de los enlaces con las variedades topológicas.

Agregué un puntaje simple a la demo. El puntaje del terreno es la fracción del ciclo que el pie pasa en el suelo, que considero que es todos los puntos cuya coordenada y está dentro de la tolerancia del punto más bajo. La puntuación de arrastre es la mayor diferencia entre dos velocidades horizontales mientras el pie está en el suelo. (Siempre es negativo, por lo que los valores más altos = pequeñas diferencias en las velocidades = mejor).

Pero aquí es donde entra la dificultad. Para programar cualquier tipo de búsqueda, necesito poder combinar estos puntajes. Pero, ¿cómo los balanceo unos contra otros? Los números mágicos de Jansen me dan groundScore: 0.520; dragScore: -0.285. Si configuro AC = 10, GH = 65, EH = 50, obtengo groundScore: 0.688; dragScore: -0.661. Casi el 70% del tiempo el pie está en el suelo. Pero el despegue es arrastrado. ¿Es mejor o peor que el de Jansen?

Creo que obtener el feedback de ingeniería real para determinar una buena puntuación será el gran problema aquí, no la búsqueda real.