Algorithme évolutif pour le mécanisme de marche de Theo Jansen
il y a un artiste/ingénieur hollandais qui a créé un mécanisme de marche très élaboré. Le principe de travail peut être vu ici:
http://www.strandbeest.com/beests_leg.php
ce qui est curieux, c'est qu'il a utilisé un algorithme évolutif fait par lui-même pour calculer les longueurs de liens idéales, qui sont décrites au bas de la page.
j'ai créé un script Python pour analyser visuellement la partie contact avec le sol du cycle, qui doit avoir deux conditions préalables remplies:
- soyez aussi rectilignes que possible, afin de ne pas vaciller de haut en bas;
- Avoir une vitesse aussi constante que possible, afin de ne pas glisser un pied contre l'autre;
ces deux critères se traduiraient par un effet" wheel like", La machine allant linéairement en avant sans gaspiller d'énergie cinétique.
La question est:
<!-"Avez-vous la moindre suggestion d'une simple formule évolutive itérative pour optimiser la longueur des jambes (en insérant les bonnes mutations dans le code ci-dessous) afin d'améliorer le parcours de la marche compte tenu des deux critères ci-dessus?"EDIT: quelques suggestions à propos de la "mise en place de la règle" de génome de candidats:
- prendre la "partie inférieure" (contact avec le sol) du cycle, étant donné qu'elle correspond à un tiers de la rotation de la manivelle (bien que la partie inférieure puisse avoir une pente non horizontale et être tout de même linéaire);
- appliquer une régression linéaire sur la positions des points de cette partie "contact avec le sol";
- calculer la variation verticale à partir de la régression linéaire (moindres carrés?)
- calculer la variation de vitesse par la différence entre un point et le précédent, parallèle à la droite de régression;
- (optionnel) tracer des graphiques de ces "fonctions d'erreur", permettant éventuellement de sélectionner des mutants visuellement (boooring... ;o).
Voici mon code, en Python + GTK, qui donne un aperçu visuel le problème:
(EDIT: maintenant, avec paramétrées, des numéros de magie l'objet d'une mutation par mut's valeurs)
# 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()
1 réponses
c'est une question fascinante, bien que je pense un peu au-delà de la portée du débordement de la pile: ce n'est pas quelque chose qui va être résolu dans quelques minutes, donc je vais coller un contour ici et le mettre à jour si je fais des progrès. Il y aura trois parties à toute approche:
notation de l'empreinte: la tringlerie est-elle rompue? l'empreinte avez le bon type de forme? comment plat est-il? Quelle est la douceur du mouvement? ne passez suffisamment de temps dans la partie plate?
recherche de bonnes valeurs des nombres magiques. Il n'est pas clair que cela doit être un algorithme évolutif (bien que je puisse voir pourquoi L'idée d'un tel algorithme ferait appel à Theo Jansen car il correspond à la métaphore animale dans son art); peut - être d'autres approches comme la recherche locale (escalade de colline) ou le recuit simulé serait productif.
recherche de bonnes configurations des bras. C'est là qu'une approche évolutive semble la plus utile.
vous pouvez essayer différents nombres magiques dans ma démo Javascript/canvas pour voir quels types de mouvements vous pouvez obtenir (CD = 55.4 est assez divertissant, par exemple). Il y en a un entier!--25-->mathématiques de la théorie des liens, soit dit en passant, qui connecte les espaces de configuration de linkages à variétés topologiques.
j'ai ajouté quelques points simples à la démo. score au sol est la fraction du cycle que le pied passe sur le sol, que je considère comme tous les points dont la coordonnée y est à l'intérieur d'une certaine tolérance du point le plus bas. faites glisser score est la plus grande différence entre deux vitesses horizontales alors que le pied est au sol. (Il est toujours négatif, de sorte que des valeurs plus élevées = petites différences dans les vitesses = mieux.)
mais c'est là que la difficulté entre en jeu. Afin de programmer n'importe quel type de recherche, j'ai besoin d'être en mesure de combiner ces scores. Mais comment puis-je les équilibrer les uns par rapport aux autres? Les nombres magiques DE Jansen me donnent groundScore: 0.520; dragScore: -0.285. Si je mets AC=10, GH=65, EH=50, j'obtiens groundScore: 0.688; dragScore: -0.661. Près de 70% du temps, le pied est au sol. Mais le décollage est difficile. C'est mieux ou pire que celui de Jansen?
je pense que le fait d'obtenir des commentaires techniques réels afin de déterminer une bonne note va être le gros problème ici, pas la recherche réelle.