Theo Jansen行走机制的进化算法
有一位荷兰的艺术家兼工程师，他创造了一个非常复杂的行走机制。这个机制的工作原理可以在这里看到：
http://www.strandbeest.com/beests_leg.php
有趣的是，他使用了一种自己制作的进化算法来计算理想的连杆长度，这些内容在页面底部有描述。
我写了一个Python脚本，用来可视化分析这个行走周期中与地面接触的部分，这部分需要满足两个条件：
- 尽量保持直线，这样就不会上下晃动；
- 速度尽量保持恒定，这样就不会让一只脚拖着另一只脚。
这两个条件会让机器像轮子一样，直线前进而不浪费动能。
问题是：
“你有没有什么简单的进化迭代公式建议，用来优化腿的长度（通过在下面的代码中插入正确的变异），以改善行走路径，满足上述两个条件？”
补充说明：关于基因候选者的“适应规则”的一些建议：
- 取周期的“下半部分”（与地面接触），因为它对应于曲柄旋转的三分之一（注意下半部分可能有非水平的坡度，但仍然是线性的）；
- 对这个“地面接触”部分的点位置应用线性回归；
- 计算线性回归的垂直变化（最小二乘法？）；
- 通过一个点与前一个点之间的差异计算速度变化，这个差异要与回归线平行；
- （可选）绘制这些“误差函数”的图表，可能可以让人直观地选择变异体（无聊... ;o）。
这是我的代码，使用Python和GTK，能对这个问题提供一些可视化的见解：
（补充说明：现在有参数化的魔法数字，可以通过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()
1 个回答
17
这是个很有趣的问题，不过我觉得有点超出Stack Overflow的范围：这不是几分钟就能解决的事情，所以我先简单列个大纲，如果有进展我会更新。任何方法都会有三个部分：
评估脚印：连接部分会断吗？脚印的形状对吗？有多平坦？运动流畅吗？在平坦部分待的时间够吗？
寻找合适的魔法数字。现在还不清楚这是否必须用进化算法（不过我能理解为什么Theo Jansen会喜欢这个想法，因为这和他艺术中的动物隐喻相符）；也许其他方法，比如局部搜索（爬山算法）或模拟退火，也会有成效。
寻找手臂的好配置。这部分似乎用进化方法会比较有价值。
你可以在我的Javascript/canvas演示中尝试不同的魔法数字，看看能得到什么样的运动（比如CD = 55.4就挺有趣的）。顺便提一下，还有一整套关于连接的数学理论，将连接的配置空间和拓扑流形联系起来。
我在演示中添加了一些简单的评分。地面评分是脚在地面上循环的时间占比，我认为所有y坐标在最低点附近的点都算在内。阻力评分是脚在地面时，任意两个水平速度之间的最大差值。（这个值总是负的，所以值越高，速度差越小，效果越好。）
但问题在于，这里有个难点。为了编写任何搜索程序，我需要能够将这些评分结合起来。但是我该如何平衡它们呢？Jansen的魔法数字给我的地面评分是0.520；阻力评分是-0.285。如果我设置AC=10，GH=65，EH=50，我得到的地面评分是0.688；阻力评分是-0.661。脚在地面上的时间接近70%。但起飞时阻力很大。这比Jansen的结果好还是坏呢？
我认为，获取实际工程反馈以确定一个好的评分将是这里最大的难题，而不是实际的搜索过程。