Эволюционный алгоритм для механизма ходьбы Тео Янсена - PullRequest
19 голосов
/ 04 июля 2011

Есть голландский художник / инженер, который создал очень сложный механизм ходьбы.Принцип работы можно увидеть здесь:

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

Любопытно, что он использовал самодельный Эволюционный алгоритм для вычисления идеальных длин звеньев, которые описаны в нижней частистраницы.

Я создал скрипт Python для визуального анализа части цикла, касающейся земли, для которой должны быть выполнены два условия:

  1. Будьте максимально прямыми, чтобыне качаться вверх и вниз;
  2. иметь как можно более постоянную скорость, чтобы не тянуть одну ногу против другой;

Эти два критерия привели бы к "колесу"как «эффект», когда машина движется линейно вперед без потери кинетической энергии.

Вопрос:

«Есть ли у вас какие-либо предположения о простой эволюционной итеративной формуле для оптимизации длины ног (вставивправильные мутации в приведенном ниже коде), чтобы улучшить пешеходную дорожку с учетом двух критериев, указанных выше?для кандидатов в геном:

  • Возьмите «нижнюю часть» (контакт с землей) цикла, учитывая, что он соответствует одной трети оборота коленчатого вала (учтите, что нижняя часть может иметь не горизонтальный наклон ивсе еще быть линейным);
  • Применить линейную регрессию к точечным позициям этой детали "контакта с землей";
  • Вычислить вертикальное отклонение от линейной регрессии (наименьших квадратов?)
  • Рассчитайте изменение скорости по разнице между одной точкой и предыдущей, параллельно линии регрессии;
  • (необязательно) построите графики этих «функций ошибок», возможно, позволяя визуально выбирать мутантов (boooring ...;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 голосов
/ 05 июля 2011

Попробуйте демо!

enter image description here

Это увлекательный вопрос, хотя я думаю, что он выходит за рамки Stack Overflow: это не то, что будет решено через несколько минут, поэтому я добавлю схему и обновлю ее, если добьюсь прогресса. В любом подходе будет три части:

  1. Оценка посадочного места: разрыв связи? имеет ли след правильную форму? насколько плоско это? Насколько плавное движение? он проводит достаточно времени в плоской части?

  2. Поиск хороших значений магических чисел. Не ясно, что это должен быть эволюционный алгоритм (хотя я могу понять, почему идея такого алгоритма понравится Тео Янсену, так как он вписывается в метафору животных в его искусстве); возможно, другие подходы, такие как локальный поиск (восхождение на гору) или моделируемый отжиг, будут продуктивными.

  3. Поиск хороших конфигураций оружия. Вот где эволюционный подход кажется наиболее целесообразным.

Вы можете опробовать различные магические числа в моей демонстрации Javascript / canvas, чтобы увидеть, какие виды движения вы можете получить (например, CD = 55.4 довольно интересный). Между прочим, существует целая математическая теория связей , которая связывает конфигурационные пространства связей с топологическими многообразиями.


Я добавил несколько простых оценок в демо. наземный балл - это доля цикла, которую нога проводит на земле, и я считаю, что это все точки, у-координата которых находится в пределах некоторого допуска от самой низкой точки. показатель сопротивления - это наибольшая разница между любыми двумя горизонтальными скоростями, когда ступня находится на земле. (Это всегда отрицательно, поэтому более высокие значения = небольшие различия в скоростях = лучше.)

Но вот тут-то и возникают трудности. Чтобы запрограммировать любой вид поиска, мне нужно объединить эти оценки. Но как мне сбалансировать их друг с другом? Волшебные числа Янсена дают мне GroundScore: 0,520; dragScore: -0.285. Если я установлю AC = 10, GH = 65, EH = 50, я получу GroundScore: 0,688; dragScore: -0,661. Почти 70% времени ноги находятся на земле. Но взлет тяжелый. Это лучше или хуже, чем у Янсена?

Я думаю, что получение реальной инженерной обратной связи для определения хорошего результата будет большой проблемой, а не фактическим поиском.

...