Tentakel-Steuerung (ja, ok, könnte auch ein Roboterarm sein)

[Schrompf]

Moin Leute,

ich mal wieder. Ich bin auf der Suche nach einer iterativen und vor allem *bequemen* Lösung für das Ausrichten eines Tentakels nach der Position der Spitze. Das Tentakel besteht aus x Segmenten, wobei jedes Segment jeweils mit dem Vorgänger verbunden ist und sich gegenüber diesem Vorgänger um +- Phi Grad drehen kann.

Nach meinem Verständnis sieht das Problem so aus:

- jedes Segment für sich kann einen Punkt auf einem Kreisbogen-Abschnitt rund um sein Gelenk einnehmen.
- die Position auf dem Kreisbogen-Abschnitt ist linear abhängig vom Winkel zum Vorgänger
- aber jede Rotation bewegt auch rekursiv alle Nachfolger-Segmente mit

Da kommt also schlimmstenfalls ein Gleichungssystem x. Grades raus, mit x-fach ineinander geschachtelten Sinüssen. Da hab ich keine Lust drauf. Ich möchte am liebsten eine Bastellösung, die ich ohne nennenswerte Framerate-Einbußen knapp 1000 mal pro Sekunde ausführen kann, und die gern auch mal irren darf. Die Lösung muss also nicht perfekt funktionieren.

Während des Tippens kam mir der Gedanke, wie das aussehen könnte. Der erreichbare Bereich der Tentakelspitze relativ zum Fußpunkt müsste wie folgt aussehen:

Die Maximalreichweite der Tentakelspitze ist klar: alle Segmente mit dem gleichen Winkel relativ zum Vorgänger. Die Minimal-Reichweite ist dagegen nur meinem Bauchgefühl entsprungen: wenn das Tentakel sich zur Hälfte vom Zielpunkt wegkrümmt, um dann die andere Hälfte maximal in Richtung Zielpunkt zu krümmen. Und "Hälfte" ist in dem Fall wahrscheinlich auch falsch - je näher der Zielpunkt, desto eher muss das Tentakel das Wegkrümmen seinlassen und sich in Zielrichtung krümmen. Evtl. gibt's da auch noch einen toten Bereich genau auf der Mittellinie... urg. Nuja, ihr versteht jetzt evtl. meine Zweifel.

Hat jemand eine nette Idee, wie man eine Tentakelsteuerung schreiben könnte, um sich quasi "spielerisch" einem Wunsch-Kriterium anzunähern? Die Grenzbedingungen der Tentakelsegmente kann ich ja dann passend abändern, so dass sich das Tierchen notfalls auch selbst am Panzer kratzen kann.

[dot]

Ich bin kein IK Experte, aber ich werf einfach mal das Stichwort Jacobian Transpose Method in den Raum, ohne mich jemals näher damit beschäftigt zu haben. Vielleicht hilft das ja schon etwas weiter... ;)

[gdsWizard]

Hört sich für mich wie eine Kombination aus inverser Kinematik und Constraints an. Beides lässt sich kombinieren. Aber ich denke mal das das für dich nicht unbedingt was Neues ist.

[Schrompf]

Danke für die Stichworte. Ich wollte aber eigentlich die exakte Lösung der Inversen Kinematik komplett vermeiden. Unter anderem deswegen, weil mir die Mathematik zu hoch wird.

[dot]

Für dein Problem wär wohl Cyclic Coordinate Descent auch brauchbar und evtl. einfacher.

Edit: Auch ein guter Link: http://thewanderingtech.blogspot.co.at/ ... on-on.html und http://thewanderingtech.50webs.com/Flas ... mpare.html

[Schrompf]

Uiuiui, es gibt da anscheinend ne Menge Lesestoff dazu. Danke nochmal für die Stichworte! Ich möchte unbedingt vermeiden, undankbar zu erscheinen - ihr habt mir schon zu oft geholfen, als dass ich es mir mit euch verscherzen wöllte :-) Aktuell fühle ich mich aber unter mächtigem Zeitdruck und werde mir wohl eher was Heuristisches zusammenstümpern, als jetzt die verschiedenen mathematischen Lösungsmöglichkeiten zu studieren und durchzuformeln, um herauszukriegen, welche davon glaubwürdige Ergebnisse erbringt, die in den meisten Fällen funktionieren.

[dot]

Schau dir den Cyclic Coordinate Descend an. Einfacher als das geht's ja wohl kaum noch... ;)

Und einen schönen Vergleich verschiedener Methoden findest du dort auch: http://thewanderingtech.50webs.com/Flas ... mpare.html

[Alexander Kornrumpf]

Wir hatten in der Uni die Cora



die mit IK sehr gut funktioniert hat, ich hab aber nur das Ergebnis bestaunt, nicht die Implementierung.

Meine eigenen Versuche eine IK zu implementieren (an sich kein Hexenwerk) waren leider numerisch nicht besonders stabil und auch nicht sehr schnell. Aber möglich ist es halt schon, wie oben gesehen.

Die Jacobi-Matrix zu transponieren statt richtig zu invertieren (wie dot schon sagte), ist auf jeden Fall eine beliebte Abkürzung.

Soweit ich mich erinnere, sagt die die IK wie du die Gelenkwinkel verändern musst um von da wo du bist zu da wo du willst zu kommen (Endeffektorposition ist das Wort). Ich hatte es, wenn ich mich richtig erinnere einfach so gemacht, dass ich nur die Änderungen durchgeführt hatte welche innerhalb der Constraints lagen, somit war die neue Position dann nicht die erwartete, von dort habe ich dann die IK erneut ausgerechnet. Dein Kriterium Bastellösung erfüllt es auf jeden Fall, numerisch war es wie gesagt die Hölle :)

Was ich auch noch weiß: Du brauchst im 3D Raum eigentlich 6 Freiheitsgrade (3 für Position + 3 Winkel). Wenn dein Tentakel mehr Freiheitsgrade hat, dann ist die Lösung nicht mehr eindeutig. Die Cora ist z.B. Anthromorph, und hat 7 Freiheitgrade im Arm. Wenn du deinen Arm gebeugt vor dich hälst, und das Handgelenk festhälst, kannst du den Ellbogen um die Achse Schultergelenk-Handgelenk kippen ohne die Endeffektorposition (Hand) zu verändern. Sie haben es also so gelöst, dass der "überzählige" Freiheitsgrad ist, der genutzt wird um z.B. um Hindernisse herumzugreifen.

Das ist alles sehr interessantes Zeug, und auch wenn ich leider nur über Halbwissen verfüge freue ich mich auf die Diskussion dazu :)

P.S. Während ich schrieb, schriebst du es sei dir zu hoch... dies ist nicht der Fall. Bis zur transponierten Jakobi Matrix kommst du mit "Hausmitteln" ganz sicher ich hatte auch damals gute Tutorials gefunden. Ist maximal ein Nachmittag lesen. Das ist an sich schon eine Heuristik (wie gesagt transponiert statt invertiert) und pfuschen kannst du ab da noch genug um die Numerik und die Constraints in den Griff zu bekommen. So zumindest meine Meinung.

[Schrompf]

Das Paper http://math.ucsd.edu/~sbuss/ResearchWeb ... survey.pdf empfiehlt Damped Least Squares - ich schau mir wohl mal beide an. Und ja, Hexenwerk ist das wohl alles nicht, ein paar Matrizen zu invertieren ist jetzt kein Zauberwerk. Ich muss mich wohl mal von meiner "Problemlösung JETZT und in fünf Worten"-Geisteshaltung trennen und mal etwas Grundlagen anlesen.

[dot]

Ja, Damped Least Squares sieht auch in dem Flash Vergleichs App mit Abstand am besten aus.

[Schrompf]

Anfass-Mensch, der ich bin, habe ich mir das mal plotten lassen. Nach meinem Verständnis ist erreichbare Raum des Zielpunkts nur linear abhängig von der Länge der Segmente, vorausgesetzt die Segmente sind alle gleich lang und unterliegen den selben Begrenzungen. Ich kann die Länge der Einzel-Segmente also ignorieren, der erreichbare Zielbereich hängt nur vom Winkel-Limit ab.

Wenn ich mein Tentakel also 10 Segmente zu je +-X Radian Winkelbeschränkung baue, erreiche ich damit verschiedene Gebiete. In Bildern:

testakel_0.4.jpg (11.63 KiB) 2723 mal betrachtet

Von oben nach unten: 0.4 Radian Winkelgrenze, dann 0.5 Radian, dann 0.6 und schlussendlich 0.7 Radian. Der weiße Punkt in der Mitte ist die Startposition des Roboterarms mit Startrichtung hoch, Blau ist der vom Arm-Endpunkt erreichbare Bereich, die Rotabstufungen sind die Positionen der Zwischensegmente. Bei 0.4 Radian habe ich fast keinen Bewegungsspielraum, bei 0.6 Radian kann sich das Tierchen zumindest schon selbst auf die Schulter klopfen, ab 0.7 Radian kann es sich außerdem am eigenen Tentakel kratzen. Mein Bauchgefühl meint, ich komme der Lösung langsam näher.

Und Danke nochmal für die Links! Die Flash-Veranschaulichung hat mir sehr geholfen. CCD sieht wirklich *sehr* schlicht aus, ist für meine Bedürfnisse aber wegen der schrittweisen Bearbeitung der Einzelsegmente wohl ungeeignet. Jeder Punkt nahe am Ursprung führt dazu, dass sich der Arm zusammenfaltet - unter Winkelbegrenzungen wird das ein Foul mit Ansage. Ich probiere mich mal an Damped Least Squares.

Randnotiz: am liebsten würde ich gern mit einem Tentakel auch mal nach was schlagen oder so. Ich könnte ja auch einfach eine zweite Jakobi-Matrix für die Geschwindigkeiten aufstellen und so eine Wunsch-Geschwindigkeit des Endpunkts anpeilen. Nur leider sind die beiden Systeme ja voneinander abhängig - das eine ist die Ableitung des anderen. Differentialgleichungen erster Ordnung mit Matrizen... jetzt hab ich richtig Angst.

[Matthias Gubisch]

Naja so tragisch ist das nicht :)

Erinner mich mal Abends dran dann kram ich mal in meinen Robotikunterlagen. Da müsste ich sogar eine mehr oder weniger fertige Lösung für diese Problemstellung haben.

Was hast du eigentlich genau vor damit?

[Schrompf]

Das wird ein neues Splatter-Monster. Bzw. mehrere, wenn ich das Verhalten gut genug hinbekomme.

[Jonathan]

Ja, Damped Least Squares sieht auch in dem Flash Vergleichs App mit Abstand am besten aus.

Moment, egal wo ich klicke, bei mir ist der schwarze Arm immer mit Abstand am schnellsten da, und das ist "CCD Conventional", der Rots (also DLS) ist eigentlich immer eher in der Mitte bis Hinten. Oder versteh ich da was falsch? Es geht doch darum, mit möglichst wenig Iterationsschritten, möglichst schnell möglichst nahe ans Ziel zu kommen.

[dot]

CCD Conventional ist wesentlich schneller, aber die resultierenden Bewegungen sind imo bei weitem nicht so natürlich, insbesondere wenn es eine Tentakel sein soll... ;)

[joeydee]

bei 0.6 Radian kann sich das Tierchen zumindest schon selbst auf die Schulter klopfen, ab 0.7 Radian kann es sich außerdem am eigenen Tentakel kratzen. Mein Bauchgefühl meint, ich komme der Lösung langsam näher.

Und mein Bauchgefühl sagt mir, bei ca. 0.62832 rad kann er sein Stammgelenk berühren... ;-)

[Schrompf]

Woher hast Du diese Zahl? Ich wollte es ehrlich gesagt nicht durchformeln, aber ich vermute, es gibt für "Identische Gelenke, identische Grenzwinkel" auch eine mathematische Lösung.

Ich bin, wie dot schon korrekt vermutet hat, an einer natürlich aussehenden Lösung interessiert, die dann gern in vielen Einzelschritten laufen darf. Daher ist mir schnelle Konvergenz schnuppe. Ich habe allerdings gestern festgestellt, dass ich zusätzlich noch das Problem habe, dass ich ja neben Zielposition bisweilen auch Zielgeschwindigkeit steuern will. Es ist mir manchmal, aber nicht immer wurscht, mit welchem Tempo die Tentakelspitze am Zielpunkt ankommt. Und steuern kann ich ja nur die Drehmoment-Motoren an den Box2D-Gelenken, also genau genommen die Beschleunigung. Ich bin gestern dann heldenhaft gescheitert bei dem Versuch, die Differentialgleichungen dafür aufzustellen, aber evtl. kann ich mir auch eine Bastellösung zusammenstümpern. Ich bin jedenfalls gespannt, wie das wird.

[joeydee]

Achtung, gleich rufst du das Wald-Bäume-Problem aus ;-)
Ein Kreis durch 10 Segmente mach 2Pi/10.
Um sich genau bis zum 1. Gelenk zu kratzen sind 9 Segmente übrig, macht ca. 0.698 rad.

Ich würde da auch eher live eine Trial-and-Error-Lösung probieren statt exakte Lösungen vorzuberechnen. Also den Endpunkt ein Stückchen dem Ziel näherbringen und dann in Richtung Wurzel alle Längen und Winkel auf die Grenzbedingungen korrigieren. Da die Wurzel dann ja in der Regel auch ein Stückchen bewegt werden muss, den ganzen Tentakel am Ende wieder zurückschieben. Damit läuft die erste Bewegung nicht exakt in Richtung Ziel, wird sich aber vermutlich auf einer leichten Kurve nähern, da sie das Ziel ja immer neu anpeilt. Was dann evtl. sogar natürlicher aussieht.
Als weitere Bedingung würde ich noch aufnehmen, dass die Winkelunterschiede von Segment zu Segment möglichst gering sein sollen, zudem in Richtung Wurzel steifer und in Richtung Ende flexibler.

[dot]

Mit anderen Worten: Du würdest das ganze als Optimierungsproblem formulieren und iterativ lösen. Also z.B. so wie die Damped Least Squares Methode!? ;)

[joeydee]

Ja, iterativ, so konnte ich bisher meine Ki-Bewegungsprobleme immer recht intuitiv und gleichzeitig natürlich aussehend lösen.
Habe mir die Papers nicht durchgelesen, daher kann ich nicht sagen was dem am nächsten kommt, aber allein dem Namen nach hört sich das in der Richtung an.

[Schrompf]

Ja, Damped Least Squares wird es werden. Ich muss aber etwas basteln, weil ich nichts gefunden habe, wie ich die Position und die erste Ableitung davon, also die Geschwindigkeit, gleichzeitig behandeln kann.

[joeydee]

tentacle.swf

(8.47 KiB) 2430-mal heruntergeladen

Sowas meinte ich. Einfachste Vektorarithmetik. Der Tentakel ist lediglich durch ein Array von Punkten mit fest definiertem Abstand (len) definiert. Die Winkellimits sind noch nicht drin, sollte aber auch kein Problem sein, denn man ist ja auch hier nicht auf eine sofortige exakte Lösung angewiesen. Also würde es sogar reichen, nach der ersten Schleife eine weitere einzufügen, die die Winkel korrigiert und die Ergebnisse der ersten Schleife etwas verfälscht, so wie es auch die letzte Korrektur macht.
Natürlich kann man den Tentakel dann sprichwörtlich "an der Nase herumführen" und in eine Sackgasse lotsen, obwohl es eine Lösung gäbe. Hier ist ein klein wenig KI gefragt, wo bei Nichterreichen des Ziels eine andere Richtung eingeschlagen wird (Zwischenziele wie Waypoints festlegen).

Die Demo ist bewusst langsam gehalten; mit entsprechend hohem Speed-Faktor "klebt" die Spitze direkt am Ziel. Be- und Entschleunigung sollte natürlich auch noch ergänzt werden; allgemein denke ich, solche Anpassungen, auch das "Schlagen", sind hier sehr leicht zu implementieren.
Interessant finde ich hier übrigens auch das "Nachfedern", wenn man außer Reichweite ist.

Code: Alles auswählen

function moveTo(target:Vector3D,speed:Number=1):void{
	var dir:Vector3D=target.subtract(pts[9]);//current vector from end point to target
	for(var i:int=9;i>0;i--){
		var l:Number=dir.normalize()/speed;//constant speed
		if(l>1)l=1;
		dir.scaleBy(l*speed);
		pts[i].incrementBy(dir);//move this point
		//calculate correction move for next point
		dir=pts[i-1].subtract(pts[i]);//segment vector
		var ldiff:Number=len-dir.normalize();//difference to original segment length
		dir.scaleBy(ldiff);//next move is correcting this segment's length
		//TODO: correct limited angles, too
	}
	//instead of moving root, subtract its correction move from all points above root
	for(i=1;i<10;i++)pts[i].decrementBy(dir);
}

[Schrompf]

Auch ein interessanter Ansatz. Du bewegst quasi das Spitzensegment ein Stück Richtung Zielpunkt, dann das Vorgängerstück, so dass es den Abstand zu seinem Nachfolger einhält, usw. Und an der Wurzel stehst Du dann mit einem Rest-Offset dar, welches die Segmentreihe nicht ausgleichen konnte, und bewegst deswegen alle Segmente um dieses Offset zurück. Damit bleibt der Ansatz, wo er ist, und die Spitze tut ihr Bestes, dem Ziel hinterher zu angeln.

Theoretisch könnte ich den Ansatz auch auf die Drehmoment-Motoren von Box2D anwenden, indem ich auf die Art erstmal einen fiktiven Versatz pro Segment ausrechne und dann wiederrum von der Spitze zur Wurzel jeden Motor so einrichte, dass er sein Bestes probiert, den Versatz einzuhalten. Und den Restversatz, den das Gelenk nicht leisten kann, könnte man einfach auf den Wunsch-Versatz des Vorgängers addieren, so dass der Kram zur Wurzel propagiert, wo andere Segmente durch andere Ausrichtung evtl. besser korrigieren können.

Und das ist dann übrigens quasi schon die Jacobian Transpose Methode, die dot im ersten Beitrag vorgeschlagen hat :-) Allerdings mit einer interessanten Priorisierung der Spitzensegmente gegenüber der Wurzel, wodurch man die Mehrdeutigkeit der Lösungen angenehm auflösen kann. Mein Gott, so langsam steige ich doch hinter den ganzen Mathe-Kram.

[Alexander Kornrumpf]

Theoretisch könnte ich den Ansatz auch auf die Drehmoment-Motoren von Box2D anwenden

Richtig. In der Cora oben sind das natürlich auch Motoren in den Gelenken.

Und das ist dann übrigens quasi schon die Jacobian Transpose Methode, die dot im ersten Beitrag vorgeschlagen hat :-) Allerdings mit einer interessanten Priorisierung der Spitzensegmente gegenüber der Wurzel, wodurch man die Mehrdeutigkeit der Lösungen angenehm auflösen kann. Mein Gott, so langsam steige ich doch hinter den ganzen Mathe-Kram.

Nice.

[Schrompf]

Um das Thema mal zu einem Vorerst-Abschluss zu bringen: ich habe die Tentakelsteuerung durchaus hinbekommen. Nach einer Freistil-Variante der Jakobian Transpose-Methode, wenn ich das richtig betrachte: ich berechne die Bewegungsrichtungen der Gelenk-Motoren nach dem Punktprodukt zwischen Bewegungsänderungsvektor der Tentakelspitze in Abhängigkeit von der Motorrichtung und dem Wunschbewegungsvektor der Tentakelspitze. Das ist aus den ganzen IK-Methoden eigentlich die banalste, aber an den IK-Fehlern ist das Thema definitiv nicht gestorben. Der Teil klappt ganz gut, wenn man genügend Bla- und Blubbfaktoren einführt, um ein wenig Übersteuerung für schnellere Ziel-Annäherung reinzubekommen und gleichzeitig die Schwingungen zu dämpfen.

Woran es jetzt eigentlich gescheitert ist: wenn mein Seestern einige Tentakel auf dem Boden aufgesetzt hat und sich damit abstoßen will, heben sich die Kräfte in der Mitte genau auf. Ich kriege meinen Seestern nicht dazu, dass er sich sinnvoll dreht. Stattdessen verkrampft er mit allen Armen auf dem Boden. Ich müsste hier entweder dehn- und stauchbare Tentakel einsetzen, um über diesen Totpunkt hinwegzukommen, oder ich müsste 3D-Tentakel simulieren, um die Stauchung über die dritte Achse abzufangen. Stauchen und Dehnen habe ich mit den Gelenken von Box2D allerdings nicht hinbekommen. Ich hatte dann Box2D wieder rausgeworfen und eine Eigenbau-Tentakelphysik angelehnt an joydees Vorschlag gebastelt, aber ich habe das Thema jetzt seinlassen müssen, weil es in der aktuellen Entwicklungsphase einfach unerhört viel Zeit gefressen hat. Sehr schade.

Evtl. treten die Tentakel nochmal auf, entweder nur als Deko-Tentakel an Monstern hintendran, oder in einem späteren Update als vollwertiges Monster. Bis dahin muss ich aber erstmal mit dem eigentlichen Spiel weitermachen.

[Alexander Kornrumpf]

"Vom Boden abstoßen", wäre in deiner Perspektive aus dem Bildschirm raus, oder? Also wenn deine Box2D welt die Bildschirmebene ist dann in eine Dimension die es "gar nicht gibt". Oder?

[Schrompf]

Nein, das war so gemeint: das Tierchen besteht aus einem zentralen Körper und fünf Armen. Es einer Wunsch-Richtung und einer Wunsch-Rotation wird für jedes Tentakel ein Kraftvektor ausgerechnet, den es umsetzen soll. Jedes Tentakel heftet sich an der Spitze an den Boden (mittels eines neuen Gelenks) und versucht dann die Spitze in einer Richtung zu bewegen, was wegen der festgetackerten Spitze für eine gegensätzliche Kraft am Zentralkörper sorgen müsste. Das klappt so aber nur mit einem einzigen Tentakel. Sobald mehr als ein Tentakel beteiligt ist, müssten sich die Tentakel prinzipiell ein bisschen stauchen oder dehnen, damit sich noch irgendwas bewegt. Die Box2D-Gelenke sorgen aber für eine mathematisch perfekte Einhaltung der Distanzen, weswegen das Gesamtkonstrukt wie im Krampf erstarrt.

[Alexander Kornrumpf]

Ahaaaa :)

Naja Alternative wäre dass die Verbindung von Tentakel und Boden nicht überall gleich viel Reibung erzeugt.

Ich weiß nicht wie sich echte Seesterne bewegen (können die das überhaupt steuern?) Aber als Alternative zu etwas wie richtigem Laufen würde mir einfallen, dass es sich mit einem Tentakel abstößt oder hinzieht, und die anderen nur so über den Boden "schleifen".

[Chromanoid]

Seesterne haben kleine Tentakel mit denen sie sich vorwärts schieben:

http://www.youtube.com/watch?v=HG17TsgV_qI (sehr hübsch auf 1080p)

Ich würde die Tentakel IK für die Waffenarme und die Optik benutzen. Den Laufenden Teil des Krakenmonsters kann man bestimmt besser animieren oder zumindest einfach die Zielpunkte der IK animieren.

edit: Das sieht auch ganz interessant aus:
[youtube]Lom5kM4ytaI[/youtube]

[Schrompf]

Jaja, jetzt macht mich noch wuschig mit all den Manövern, die eigentlich mit so einem Setup funktionieren sollten. Mit einem reinen 2D-Skelett ging es jedenfalls nicht, aber ob das jetzt an meiner eigenen Subcleverness oder am Prinzip liegt, kann ich nur mit weiterem Zeiteinsatz herausfinden. Das Thema ruht also bis irgendwann später.