Robotvoetbal / vector algorithme

zaterdag 24 juli 2004 10:08

Wat je wilt is denk ik Hermite Splines. Hier een tekeningetje:

Afbeeldingslocatie: http://www.pandemic.nl/~greyfox/hermite_splines_voetbalrobot.jpg

Afbeeldingslocatie: http://www.pandemic.nl/~greyfox/hermite_splines_voetbalrobot.jpg

De vector van de bal naar het doel is straightforward. De vector vanuit de robot kun je enigszins randomizen om een 'echter' effect te creeren. Ik zou hem tussen de 5 en de 25 graden 'achter' de bal leggen, dat moet lukken.

Verder is de interpolatie van het pad dan te doen met de hermite spline. Eventjes googlen op die term en wat lezen erover, zou ik zeggen.

[ Voor 3% gewijzigd door Grijze Vos op 24-07-2004 03:33 ]

Op zoek naar een nieuwe collega, .NET webdev, voornamelijk productontwikkeling. DM voor meer info

Acties:

Verwijderd

Topicstarter

Grijze Vos schreef op 24 juli 2004 @ 03:32:
Wat je wilt is denk ik Hermite Splines. Hier een tekeningetje:

[afbeelding]

De vector van de bal naar het doel is straightforward. De vector vanuit de robot kun je enigszins randomizen om een 'echter' effect te creeren. Ik zou hem tussen de 5 en de 25 graden 'achter' de bal leggen, dat moet lukken.

Verder is de interpolatie van het pad dan te doen met de hermite spline. Eventjes googlen op die term en wat lezen erover, zou ik zeggen.

Je plaatje doet het niet meer, maar Hermite Splines ziet er veelbelovend uit $_/-\o_$ $_/-\o_$ . Ik zal er dadelijk eens het een en ander mee proberen.

http://www.dannywartnaby....hments/hermiteSplines.jpg $_/-\o_$

zaterdag 24 juli 2004 10:28

Acties:

zaterdag 24 juli 2004 12:09

ja, webserver is dood gegaan.

Afbeeldingslocatie: http://www.stack.nl/~greyfox/hermite_splines_voetbalrobot.jpg

_{ff op een andere server gezet}

Het handige aan Hermite splines is dat hij gecontroleerd wordt door de raaklijnen van de spline aan begin en uiteinde.

[ Voor 94% gewijzigd door Grijze Vos op 24-07-2004 10:35 ]

Op zoek naar een nieuwe collega, .NET webdev, voornamelijk productontwikkeling. DM voor meer info

Acties:

Verwijderd

Topicstarter

Op http://www.cubic.org/~submissive/sourcerer/hermite.htm heb ik goede uitleg gevonden, maar ik snap het volgende (basisprincipe van vectors

) niet:

(pseudocode)

code:

moveto (P1);                            // move pen to startpoint
for (int t=0; t < steps; t++)
{
  float s = (float)t / (float)steps;    // scale s to go from 0 to 1
  float h1 =  2s^3 - 3s^2 + 1;          // calculate basis function 1
  float h2 = -2s^3 + 3s^2;              // calculate basis function 2
  float h3 =   s^3 - 2*s^2 + s;         // calculate basis function 3
  float h4 =   s^3 -  s^2;              // calculate basis function 4
  vector p = h1*P1 +                    // multiply and sum all funtions
             h2*P2 +                    // together to build the interpolated
             h3*T1 +                    // point along the curve.
             h4*T2;
  lineto (p)                            // draw to calculated point on the curve
}

Hoe kan ik float's en coordinaten / richtingen optellen tot een vector?

[ Voor 6% gewijzigd door Verwijderd op 24-07-2004 12:14 ]

zaterdag 24 juli 2004 12:19

Acties:

zaterdag 24 juli 2004 12:20

de formule werkt niet met vectoren, maar met punten. Je moet dus de uiteindes van de twee vectoren zien als de punten 2 en 4 (dacht ik) van je spline.

Verder raad ik je aan de matrix vermenigvuldiging te gebruiken die er ook staat.

edit:
dit begint btw steeds meer een P&W topic te worden

[ Voor 13% gewijzigd door Grijze Vos op 24-07-2004 12:20 ]

Op zoek naar een nieuwe collega, .NET webdev, voornamelijk productontwikkeling. DM voor meer info

Acties:

Confusion

Fallen from grace

Ik voorzie eerst andere problemen: hoe weet de robot voldoende nauwkeurig waar de bal is? Oftewel: waarmee ga je detecteren waar de bal is en hoe bepaal je waar de robots zijn, met voldoende nauwkeurigheid?

Ik zou zeggen: neem eens contact op met http://www.ph.tn.tudelft.nl/~phrobosoc/index.html ; die kunnen je vast wel helpen

Wie trösten wir uns, die Mörder aller Mörder?

zaterdag 24 juli 2004 12:28

Acties:

Verwijderd

Topicstarter

Confusion schreef op 24 juli 2004 @ 12:20:
Ik voorzie eerst andere problemen: hoe weet de robot voldoende nauwkeurig waar de bal is? Oftewel: waarmee ga je detecteren waar de bal is en hoe bepaal je waar de robots zijn, met voldoende nauwkeurigheid?

Ik zou zeggen: neem eens contact op met http://www.ph.tn.tudelft.nl/~phrobosoc/index.html ; die kunnen je vast wel helpen

Verwijderd schreef op 24 juli 2004 @ 01:59:
[...]

Vergeten te vertellen . Het is de bedoeling dat er een videocamera boven het veld komt te hangen,

Ietsje uitgebreider: we zijn van plan een felblauw golfballetje te gebruiken als bal en de robots te voorzien van deze kleurtjes aan de bovenkant:
Afbeeldingslocatie: http://emiel.dezeserver.nl/public/robot_bovenkant.jpg

Afbeeldingslocatie: http://emiel.dezeserver.nl/public/robot_bovenkant.jpg

Daarna met beeldherkenning (dit wordt ook nog een uitdaging

) de positie, richting en snelheid van de 2 robots en het balletje bepalen.

zaterdag 24 juli 2004 13:42

Acties:

Verwijderd

Topicstarter

Goed, het werkt hoor. Iedereen bedankt voor zijn input (met name greyfox natuurlijk $_/-\o_$ ).

Probleempje was dat ik gebruik maakte van PHP (en php-gtk)

en dat deze geen matrices ondersteunt. Om het topic toch even compleet te maken hier de gebruikte code:

PHP:

      /* Hermite Splines
         array[0] is the x coordinate, array[1] the y coordinate */
   
      $P1 = array(10, 10);
      $P2 = array(80, 80);

      $T1 = array(0, 100);
      $T2 = array(0, 100);
  
      $steps = 200;
  
      $prevp = $P1;

      for ($t = 0; $t < $steps; $t++) {
        $s = $t / $steps; /* Scale s to go from 0 to 1 */
        $h1 =  2 * pow($s, 3) - 3 * pow($s, 2) + 1;
        $h2 = -2 * pow($s, 3) + 3 * pow($s, 2);
        $h3 = pow($s, 3) - 2 * pow($s, 2) + $s;
        $h4 = pow($s, 3) - pow($s, 2);
    
        $p[0] = $h1 * $P1[0] + $h2 * $P2[0] + $h3 * $T1[0] + $h4 * $T2[0];
        $p[1] = $h1 * $P1[1] + $h2 * $P2[1] + $h3 * $T1[1] + $h4 * $T2[1];
    
        gdk::draw_line($gdkwindow, $black, $prevp[0], $prevp[1], $p[0], $p[1]);
        
        $prevp = $p;
      }

En het resultaat

Afbeeldingslocatie: http://emiel.dezeserver.nl/public/hermitesplines_got.jpg

Uiteraard zal er nog het eea moeten gebeuren om het goed te laten werken (breedte robot meerekenen bijvoorbeeld), maar dit gaat mij zelf ook wel lukken.

[ Voor 7% gewijzigd door Verwijderd op 24-07-2004 13:46 ]

zaterdag 24 juli 2004 13:46

Acties:

Confusion

Fallen from grace

Verwijderd schreef op 24 juli 2004 @ 12:28:
Daarna met beeldherkenning (dit wordt ook nog een uitdaging ) de positie, richting en snelheid van de 2 robots en het balletje bepalen.

Een uitdaging is nogal een understatement. Als je bovenstaande voor elkaar krijgt, heb je al een profielwerkstuk op zich, zo niet meer. Sowieso moet je precies weten waar de robots zijn. Als je vervolgens vanaf een camera op één van de robots de plaats van een stilstaande bal weet te bepalen vanaf een stilstaande robot, dan heb je volgens mij al wel aan de eisen van een profielwerkstuk voldaan. Het is verre van triviaal. Als je iets werkends wilt hebben straks, zou ik met dit soort basisproblemen beginnen en van de rest slechts een schets van de oplossing geven. Misschien dat mensen in jaren na je het project voort kunnen zetten.

Wie trösten wir uns, die Mörder aller Mörder?

zaterdag 24 juli 2004 13:57

Acties:

Verwijderd

Topicstarter

Confusion schreef op 24 juli 2004 @ 13:46:
[...]

Een uitdaging is nogal een understatement. Als je bovenstaande voor elkaar krijgt, heb je al een profielwerkstuk op zich, zo niet meer. Sowieso moet je precies weten waar de robots zijn. Als je vervolgens vanaf een camera op één van de robots de plaats van een stilstaande bal weet te bepalen vanaf een stilstaande robot, dan heb je volgens mij al wel aan de eisen van een profielwerkstuk voldaan. Het is verre van triviaal. Als je iets werkends wilt hebben straks, zou ik met dit soort basisproblemen beginnen en van de rest slechts een schets van de oplossing geven. Misschien dat mensen in jaren na je het project voort kunnen zetten.

Uhm, het is dus de bedoeling dat er een camera boven het speelveld komt te hangen

zaterdag 24 juli 2004 14:21

Acties:

zaterdag 24 juli 2004 15:12

Verwijderd schreef op 24 juli 2004 @ 13:57:
[...]

Uhm, het is dus de bedoeling dat er een camera boven het speelveld komt te hangen

Dat maakt het idd wel een stuk eenvoudiger, maar onderschat het probleem niet.

edit:
graag gedaan, overigens.

[ Voor 8% gewijzigd door Grijze Vos op 24-07-2004 14:22 ]

Op zoek naar een nieuwe collega, .NET webdev, voornamelijk productontwikkeling. DM voor meer info

Acties:

Confusion

Fallen from grace

Grijze Vos schreef op 24 juli 2004 @ 14:21:
Dat maakt het idd wel een stuk eenvoudiger, maar onderschat het probleem niet.

I second that: onderschat de moeilijkheden niet om gegevens uit beelden te halen. Als je beeldherkenningsprogrammatuur hebt is het waarschijnlijk wel te doen, maar als je dat zelf wilt schrijven, dan betwijfel ik dat je er genoeg tijd voor hebt.

Wie trösten wir uns, die Mörder aller Mörder?

zondag 25 juli 2004 01:03

Acties:

Apollo_Futurae

>>>

Verwijderd schreef op 24 juli 2004 @ 00:22:
Om het allemaal niet te moeilijk te maken heb ik de mogelijke acties van de AI engine gelimiteerd tot deze 4:
- Linksom draaien
- Rechtsom draaien
- Vooruit bewegen
- Stilstaan

Bij linksom en rechtsom draaien blijft de robot op dezelfde plek staan.

Bij deze vorm van voortbewegen probeer je zo veel mogelijk in rechte lijnen te bewegen, lijkt me. Een vloeiend gekromde curve kun je op deze manier alleen met veel moeite en vertraging benaderen (je moet steeds stoppen om een klein stukje te draaien).

Allereerst heb ik een plaatje gemaakt van de mogelijke "arrivaltimes" voor de robot in de posities om hem heen (robot_angle = 0, hij staat met zijn voorkant naar boven gericht)

Hangt de 'arrival time' niet af van de momentane (draai)snelheid van de robot?

Het probleem is echter dat het robotje met een mooie boog precies goed naar de bal toe moet gaan rijden.

Die mooie boog lijkt me dus niet zo handig.

Om het niet echt eenvoudiger te maken, deze hele beweging zal ook gebruikt moeten om te voorspellen waar de bal geraakt moet worden, omdat in een boog rijden natuurlijk langer duurt dan in een rechte lijn.

Enfin, mijn vraag dus: bestaat er een mooi algorithme die de goede boog om de bal heen beschrijft?

Mijn eerste idee hierbij is het volgende.
Breid de 'arrival time' uit door rekening te houden met de omgeving: kun je in een rechte lijn naar het betreffende punt toe, of moet je tussentijds draaien om de bal of misschien zelfs je tegenstander je ontwijken? (Het ontwijken van de tegenstander is lastig wegens de onvoorspelbaarheid van zijn baan, dus daar kun je misschien beter mee wachten.)
Laat de 'arrival time' niet alleen afhangen van de plaats in kwestie, maar ook van de verlangde oriëntatie van de robot ('uitgebreide arrival time').
Reken uit waar de bal is op een variabel moment in de toekomst en bereken de 'uitgebreide arrival time' voor die plaats (de verlangde oriëntatie kies je in overeenstemming met de positie van het doel van de tegenstander.). Als je bij de verwachte positie van de bal kunt komen voor de bal daar aankomt, ben je klaar: de te nemen route is in feite al bepaald bij het berekenen van de 'arrival time'.

Pas de replâtrage, la structure est pourrie.

zondag 25 juli 2004 13:47

Acties:

zondag 25 juli 2004 21:25

In eerste instantie, is het inderdaad zo dat je de complexiteit van dit probleem absoluut niet moet onderschatten. Maar ja daar ben je nu wel genoeg voor gewaarschuwd.

Kun je in de robotje niet iets maken dat de bal kan vasthouden (Een halve circel in de voorkant). Dan hoef je namelijk niet in een boog te rijden. Je rijd dan tegen de bal aan (En hebt hem dan in je halve circel). Vervolgens draai je de richting van het doel, en schiet je.

en als je dan toch in een boog wilt rijden is het niet eenvoudig om dat te doen met je huidige besturing (zonder teveel hotten en stoten). Wat je misschien zou kunnen gebruiken is een PID regeling.
Je berekend de fout die je robotje heeft ten opzichte van je gewenste spline die hij moet rijden. Door deze fout te integreren, differentieren of te vermenigvuldigen (Of een combinatie hiervan) kun je bepalen hoe sterk je robot moet bijsturen om de ideale lijn weer terug te krijgen.

Bij een PID regeling gebruik je de volgende formule: Afbeeldingslocatie: http://claymore.engineer.gvsu.edu/~jackh/books/plcs/labguide/egr450-12.gif

Afbeeldingslocatie: http://claymore.engineer.gvsu.edu/~jackh/books/plcs/labguide/egr450-12.gif

u = De mate van bijsturing
Kp = afstel factor voor het proportionele deel
Ki = " " " " Integrerende "
Kd = " " " " Differentierende "
e = de fout van de robot ten opzichte van de ideale lijn.
t = de tijd

Het Proportionele deel stuurt de fout van de robot evenredig bij
Het Integrerende deel stuurt de fout van de robot bij als deze langere tijd hetzelfde is.
Het Differentierende deel stuurt de fout van de robot bij als deze in een kort tijdsbestek snel veranderd.
Met deze regeling in combinatie met de spline formules kun je de robots in mooie vloeiende lijnen laten rijden.

Je kan er ook voor kiezen om bepaalde termen van de formule weg te laten zodat je op bepaalde bovenstaande effecten niet regelt.

offtopic:
Ik vermoed wel dat bij het langskomen van een modje dit topic verhuisd naar P&W

[ Voor 5% gewijzigd door mrClass op 25-07-2004 13:55 . Reden: t = tijd vergeten ;) een offtopicje toegevoegd ]

Acties:

Zoijar

Because he doesn't row...

In mijn groep doet iemand hier (academisch) onderzoek naar, en dat ging geloof ik niet zo heel erg goed. Daar waren het wel autonome robots met cameras, dus dat maakt het wel een stuk moeilijker...maar toch, ik denk dat het wel erg lastig is voor een profiel werkstuk.

maandag 26 juli 2004 00:19

Acties:

Verwijderd

Confusion schreef op 24 juli 2004 @ 15:12:
I second that: onderschat de moeilijkheden niet om gegevens uit beelden te halen. Als je beeldherkenningsprogrammatuur hebt is het waarschijnlijk wel te doen, maar als je dat zelf wilt schrijven, dan betwijfel ik dat je er genoeg tijd voor hebt.

Mwoah, als je de bal en beide robots een unieke kleur geeft die voldoende van elkaar en van de ondergrond afwijken, is het natuurlijk vrij simpel om uit een beeld de drie posities te halen.

maandag 26 juli 2004 17:23

Acties:

dinsdag 27 juli 2004 12:00

mrClass schreef op 25 juli 2004 @ 13:47:
en als je dan toch in een boog wilt rijden is het niet eenvoudig om dat te doen met je huidige besturing (zonder teveel hotten en stoten). Wat je misschien zou kunnen gebruiken is een PID regeling.
Je berekend de fout die je robotje heeft ten opzichte van je gewenste spline die hij moet rijden. Door deze fout te integreren, differentieren of te vermenigvuldigen (Of een combinatie hiervan) kun je bepalen hoe sterk je robot moet bijsturen om de ideale lijn weer terug te krijgen.
[/offtopic]

Een PID-regelaar lijkt mij hier iets te veel van het goede. Vooral omdat het model van de robot (nog) niet bekend is. Ik denk dat het volstaat om een gedetailleerd grid te maken en dat vervolgens in een 'dynamic programming'-algorithme te gooien (curse the curse of dimensionallity

).

In hoeverre beeldverwerking een probleem wordt weet ik niet. Je gebruikt een camera van bovenaf, dus je hoeft geen plaatsidentificatie toe te passen. Tevens denk ik ook dat je geen last hebt van andere schaduwen en dergelijke zodat je alleen de 'goals', de robots en de bal hoeft te identificeren.

Buiten dat wil ik even opmerken dat je jezelf echt belachelijk veel op de hals haalt, maar ik zou graag op de hoogte gehouden willen worden.

Succes iig!

Acties:

dinsdag 27 juli 2004 15:12

Ik denk toch persoonlijk. Dat als je voor zo'n besturing een algoritme moet bedenken, dat je veel exacter te werk moet gaan, dan als je regelsysteem gebruikt.
Wij hebben ook eens een robotje laten rijden, maar een programmeer algortime bleek te excact te zijn, en kon moeilijk in de praktijk gebruikt worden. (Door allerlei analoge factoren). Achteraf gezien leek een regelsysteem makkelijker de praktijk aan te kunnen. En een regelsysteem is sowizo minder werk dan een programmeer algoritme (Als je het tunen een beetje uit de losse pols doet).

Acties:

donderdag 29 juli 2004 13:27

mrClass schreef op 27 juli 2004 @ 12:00:
Ik denk toch persoonlijk. Dat als je voor zo'n besturing een algoritme moet bedenken, dat je veel exacter te werk moet gaan, dan als je regelsysteem gebruikt.
Wij hebben ook eens een robotje laten rijden, maar een programmeer algortime bleek te excact te zijn, en kon moeilijk in de praktijk gebruikt worden. (Door allerlei analoge factoren). Achteraf gezien leek een regelsysteem makkelijker de praktijk aan te kunnen. En een regelsysteem is sowizo minder werk dan een programmeer algoritme (Als je het tunen een beetje uit de losse pols doet).

Hoe heb je destijds dat regelsysteem dan ontworpen? Ik kan me namelijk voorstellen dat een robuust programmeer algorithme redelijk goed zou kunnen werken.

Acties:

donderdag 29 juli 2004 15:05

Nou kijk ons probleem was niet het voetballen, maar wij moesten een robot een wand laten volgen (Met bochten) en laten ringsteken.
We gebruikte een microcontroller(PIC) en een PC net BlueTooth verbinding. Voor de positiebepaling was je dus afhankelijk van je sensoren. In ons algortime keek de robot hoe hij t.o.v de muur stond (9 verschillende posities) en berekende aan de hand van de sensoren hoe hij moest bijsturen (Waar hij heen moest rijden). Ons probleem was echter dat de sensoren niet precies genoeg waren om zulke excacte conclusies te kunnen trekken. Het volgende probleem was dat de programmeercode zo groot was (Hoewel wel efficient geprogrammeerd) dat het ook nog eens lastig te debuggen was.
Dus wat we beter hadden kunnen doen is de afstand tot de muur berekenen, en deze te vergelijken met de ideale afstand om zo een fout(e) te berekenen. Vervolgens hoefden we dan alleen maar op deze fout te regelen met een PID regelaar (welke 1 formule is).
Wat het principe en regels programmeercode toch aanzienlijk gemakkelijker maakten. Als er mensen zijn die de werking van het programmeer algoritme willen nalezen, kan ik het verslag wel ff online zetten.

Acties:

zondag 1 augustus 2004 20:24

mrClass schreef op 29 juli 2004 @ 13:27:
Dus wat we beter hadden kunnen doen is de afstand tot de muur berekenen, en deze te vergelijken met de ideale afstand om zo een fout(e) te berekenen. Vervolgens hoefden we dan alleen maar op deze fout te regelen met een PID regelaar (welke 1 formule is).

Je blijf hier het probleem houden van onnauwkeurige sensoren, dus het gebruik van het D-gedeelte van de regelaar lijkt me sowieso erg vreemd, al zal je wel een lage gain gebruikt hebben. Hebben jullie robuuste regelaars beschouwd en in hoeverre hebben jullie een model geïdentificeerd van de robot?

Als er mensen zijn die de werking van het programmeer algoritme willen nalezen, kan ik het verslag wel ff online zetten.

Graag!

Acties:

maandag 2 augustus 2004 14:49

Om misverstanden te voorkomen. Hebben wij zelf de PID niet toegepast. Maar er zijn wel andere groepen die het wel successvol gedaan hebben. En die hadden minder code dan wij die een programmeer algortime hadden.

Ik zal het probleem ook een beetje exacter omschrijven.

Algoritme:
De robot reed net zolang totdat hij een te grote fout had. Vervolgens berekend hij aan de hand van de sensoren hoe hij weer terug moet komen in zijn goede baan.

PID:
Hier word direct geregeld op de fout. Dus zodra hij van de ideale lijn afgaat, dan word de hoek waaronder de robot reed aangepast. Hiermee word de robot dus verder of dichter naar de muur gestuurt.

Het probleem is dus, dat bij het bovenstaande algoritme de sensoren altijd exacte data moet geven (Ze mogen dus niet fluctueren) Indien ze dat dus doen, trekt de robot verkeerde conclusies.
Bij een PID regelaar maakt het niet uit of de sensoren fluctueren, hij stuurt toch direct, en bij fluctuatie van de sensoren stuurt hij in principe het gemiddelde van de fluctuaties.

Ik heb niet zoveel over regelsystemen gehad, dat ik ze zou kunnen tunen, of kijken welke delen er gebruikt moesten worden (P, I of D). Maar de effecten kunnen wel in de praktijk bekenen en getuned worden, als je maar kennis hebt van de effecten van de verschillende delen.
Een basis voor een regelsysteem hoeft helemaal niet zo complex te zijn. En kan prima door de TS gebruikt worden.

het verslag houd je nog van mij tegoed. Ik heb het namelijk niet meer. Moet ik even een klasgenoot vragen.

Acties:

dinsdag 3 augustus 2004 13:17

Ik kan me niet voorstellen dat het niet uitmaakt dat er een fout zit op de sensoren. Zero mean white noise zou tot wellicht op zekere hoogte nog kunnen (al probeert men bij elke systeem identificatie noise van het werkelijke model te scheid), maar als er bias op de sensoren zit kan je het naar mijn idee wel vergeten.

Een mogelijke reden waarom het bij hen gewerkt zou kunnen hebben, is, denk ik, dat zij geen model geïdentificeerd hebben en de regelaar zodoende twee dingen tegelijkertijd wegregelt.

Als iemand anders een betere verklaring heeft, zou ik dit graag willen weten.

Acties: