Konklusion

Session: Onsdag 23/01-08 kl. 12-16

Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1: Konklusion.

1: Konklusion.
I vores arbejde med lejos har vi igennem vores forsøg fundet frem til visse fordele og ulemper med tacho counteren. I projektet var det oprindeligt planen at forsøge at løse nogle af opgaver fra first lego league i Mars eksperimentet, men da det viste sig at være meget besværligt blot at navigerer på pladen, blev vi da enige om at koncentrere projektet omkring navigering på mars plade, for at se om vi kunne komme frem til en fornuftig løsning, eller i det mindste prøve forskellige metoder, og se hvad resultatet blev.

Vi besluttede at bruge tacho counteren til at navigere på Mars pladen. Vi ville se om det var muligt at komme frem til en fornuftig løsning, som kunne navigere rundt på Mars pladen uden alt for stor afvigelse. Dette viste sig igennem nogle indledende forsøg at være ret besværligt. For det første fandt vi frem til at robotten skulle være perfekt afbalanceret for at opnå de bedste resultater, og dette betød blandt andet at vi var nødt til at afmontere den robot arm vi havde bygget, som vi egentlig skulle have brugt til, at løse opgaverne med. Og det var så der vi besluttede os for helt at udelade løsning af opgaverne på selve pladen.

Vores løsning til navigering bestod af at bruge den naturlige inddeling af grids på spillepladen (Se tidligere billede). Vi registrerede vi de tykke sorte streger til at finde ud af positionen i henhold til X-aksen. Dette virkede rimelig præcist og vi kunne successfuldt holde styr på vores position i den retning.
Der opstod dog problemer når vi prøvede at registrere de tyndere streger der går på tværs af spillepladen. Dette kunne simpelthen ikke lade sig gøre, da spillepladen også består af sorte kratere, der gør det umuligt at skelne. Derfor blev vi tvunget til at bruge tachocounteren til at holde styr på vores position i Y-aksen.

Da vi hurtigt kunne konkludere at den var ekstremt upræcis i den forstand at hvis man fortæller den at den skal dreje 90grader, kan det betyde alt fra 80-100 i praksis. En ting som bl.a. bla blba bla også fortæller om i sin bog: Maximum Lego NXT: Building robots with Java brains. En af de ting vi indførte for at modvirke dette, var vores referencepunkter på pladen. Disse virkede ved at robotten kunne korrigere sin vinkel ved at køre ind imod en mur, og derefter resette tachocounter værdier.
Dette virkede rent faktisk nogenlunde, men da robotten allerede drejede skævt på vej væk fra referencepunktet igen, blev det ekstremt svært at koordinere over længere kørsler.

Det skal også nævnes at vi fandt en fejl i både TachoNavigator klassen og i forbindelse med brug af ArrayList som nævnt tidligere. Det er vigtigt at have i mente at Lejos stadig ikke er færdigudviklet, og vi spildte meget udviklingstid på at debugge selve frameworket.

Alt i alt kan vi konkludere at navigation med tachocounteren må frarådes, hvis der skal bare en smule præcision ind over. Dog er det ikke helt ubrugeligt. Tachocounteren er nemlig ekstremt anvendelig til at drive ting som vores arm på robotten. Når faktorer som vægtfordeling, friktion osv tages væk og den tilkobles direkte til fx en arm der skal køre op og ned, viser vores eksperimentere at den er meget præcis.

Hvis vi fra start af, havde besluttet os for ikke at følge de officielle regler mht. antal og typer af sensorer, er vi overbeviste om at vi kunne have nået et bedre resultat. Havde vi fx. haft en kompas sensor, ville det være muligt at korrigere tachocounterens fejl meget hyppigt, og derved opnå en større præcision. Det ville muligvis også kunne lade sig gøre at navigere kun via denne.

En anden der kunne være interessant at teste, kunne være brugen af ultralyds sensorer eller andre afstandsmåldende sensorer, ligesom fx i Maja beskriver i Integration of representation into goal-driven behaviour-based robots. Hvis man placerede en på hver side af robotten ville det måske være muligt at måle afstanden til væggen på pladen i hver retning og derved altid have et meget præcist x,y koordinat for ens position. Dette kunne evt kobles med en kompassensor til at holde styr på den vinkel man har. Kunne dette lade sige gøre ville det gøre det meget nemmere at navigere på pladen.

En sidste ting der skal nævnes er vores success med at lave dynamisk pathfinding på robotten. Givet den begrænsede hukommelse er det muligt at lave dette gentagne gange uden at lække hukommelse. Dog kræver det at vores fieldmap repræsentation ikke bliver meget stor.


Vores endelige kode kan findes her:
http://daimi.au.dk/~elvar/lego/code.zip

Bluetooth kommunikation (fortsat)

..fortsat fra forrige blog indlæg

3. Teste stien som vi får tilbage fra pc.
Det viste sig at stien vi fik tilbage fra bluetooth var korrekt. Fejlen vi beskrev tidligere viste sig at være en synkroniserings fejl imellem klient og server, som var hurtigt løst.
Herefter fik vi altid udregnet de korrekte stier og overført dem korrekt tilbage til NXT'en.


4. Opdagelse af mystisk fejl
Inden vi besluttede os for at benytte bluetooth kommunikation for at undgå hukommelsesproblemer, omskrev vi pathfinding algoritmen til at genbruge de lister der er nødvendige når man laver dybde-først søgninger (dette var inden vi eksperimenterede med bredde først). Hver Node gemmer nu fast sine 4 faste naober, samt en ArrayList for hver af disse naboer, som bliver genbrugt når findpath kaldes på hver nabo node. Dermed er algoritmen heller ikke rekursiv mere og der skulle ikke leake noget memory.
Efter at have implementeret denne algoritme kunne vi dog konstatere at vo stadigvæk løb ind i en fejl i andet kald af findPath. Denne gang ikke en hukommelses fejl, men en IndexOutOfBounds. Derfor implementerede vi Bluethooth til sidst da vi ikke kunne finde årsagen.
Nu viser det sig dog at vi får præcist samme fejl - IndexOutOfBoundsException.
Efter intensiv debugging breder mystikken sig endnu mere. Vi formår at kalde PC'en over bluetooth. Vi ved at PC'en returnerer den korrekte sti og at NXT'en modtager den. Men når så findpath metoden returnerer får vi fejlen - og det er på trods af at det første vi gør efter at metoden returnerer, er at kalde Button.LEFT.waitForPressAndRelease(); og ikke andet (af debugging årsager selvfølgelig).

Til sidst fandt vi ud af at det var kun i det tilfælde hvor vi finder en sti fra grid 3,0 til grid 8,0 (vores to referencepunkter) at fejlen opstår. Selv hvis vi lavede en sti fra 3,0 til 7,0 som går igennem 8,0 virker det som det skal.
Vi har endnu ikke kunne finde årsagen til dette problem - vi ved at dette grid er initialiseret korrekt, vi ved at vores sti bliver bygget korrekt, vi ved at vi ikke bruger stien eller noget andet til noget som helst efter at vi får returneret stien (i vores debug setup). Vores mistanke falder på en fejl i Lejos' håndtering af hukommelse, men det er umuligt at vide med sikkerhed.


4. Løsning
Vi fandt dog en måde at omgå problemet på - mere eller mindre tilfældigt. I går havde vi overvejet at sætte et af felterne til ikke at være optaget af en forhindring. Nærmere betegnet et af de felter der kun havde en boulder forhindring på sig.
Da vi gjorde dette, åbnede der sig en anden sti fra 3,0 til 8,0 og vores robot kunne åbenbart godt tolerere denne. Det skal siges at dette felt ikke havde noget at gøre med den anden sti, så det har ikke været dette der har været den oprindelig fejlårsag.

Efter at have konstateret dette er vi gået tilbage til at finde stierne på NXT'en i stedet for over bluetooth. Dette er via den ikke-rekursive dybde-først algoritme som beskrevet ovenover her. Det kom som en overraskelse at det kunne lade sig gøre uden at løbe tør for hukommelse, men det er godt nyt for vores projekt.

I morgen vil vi så endelig have mulighed for at fintune navigeringen yderligere, så vi forhåbentligt kan navigere stabilt rundt på vores spilleplade. Hele denne debugging session med vores mystiske fejl har dog nok kostet os så lang tid, at der ikke bliver tid til at løse alle de opgaver der er på spillepladen.
Som beskrevet tidligere er dette dog heller ikke hovedefokus, da det vigtigste er at kunne komme fra forhindring til forhindring på en konsistent og sikker måde.

Blue tooth kommunikation

Session: Torsdag 10/01-08 kl. 9-16

Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1. Blue tooth kommunikation.
2. Testing a kommunikation.
3. Teste stien som vi får tilbage fra pc.

1. Blue tooth kommunikation.
I dag implementerede vi blue tooth kommunikationen mellem pc og nxt enhed. Vi udregner stadig hvordan koordinat systemet ser ud på nxt enheden, og vi gør det samme på pc'en. Grunden til at vi gør det samme begge steder er, at vi blot skal sende x og y koordinater fra pc til computer, så kan nxt enheden slå centimeter tallet op for en koordinats centrum baseret på x, y koordinaterne.

2. Testing a kommunikation.
Da vi gik igang med at teste komminukationen mellem nxt og pc, da stødte vi ind i en uventet fejl. Det viste sig at den fint kunne kommunikerer en sti den første gang, men når den prøvede at kommunikere en sti mere, så var det som om at enten nxt enheden eller pc'en låste. Vi observerede at begge enheder stod stille, som om at de afventede hinanden.

3. Teste stien som vi får tilbage fra pc.

Hukommelses problem

Session: Onsdag 09/01-08 kl. 9-16

Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1: Løse hukommelses problemet.
2: Prøve en anderledes algoritme.
3: Blue tooth.

1: Løse hukommelses problemet.
Som beskrevet i går, havde vi store problemer med nxt enhedens meget begrænsede hukommelse på 64kb. I går fandt vi ud af at der var varslet en ny udgivelse af lejos, og at denne udgivelse ville indeholde garbage collection. I dag var denne udgivelse så kommet.
Udgivelsen indbefattede en række nyttige ændringer, for det første var der som sagt garbage collection, det var dog ikke real-time garbage collection, så hver gang vi skal rydde op i hukommelsen skal vi kalde System.gc(). Dette viste sig dog midlertidigt hurtigt ikke at have nogen indflydelse på vores hukommelses problem, så enten er garbage collection implementeret forkert, ellers også ligger problemet andetsteds i vores kode, vi vil i løbet af idag arbejde videre med dette problem og forhåbentlig have en løsning senere idag.
Det første vi vil prøve er at ændre algoritmen til path finding fundamentalt, sådan at den genbruger hukommelse, og hvis dette viser sig ikke at virke, så har vi snakket om at kigge nærmere på, hvordan man får blue tooth til at virke. Vi vil så bruge en bærbar computer til at lave de hukommelses tunge beregninger på, for derefter at kommunikerer resultatet til nxt enheden via blue tooth.

2: Prøve en anderledes algoritme.
For at løse vores hukommelses problem prøvede vi idag en ny indgangs vinkel. Tanken var at prøve at søge efter målet i en bredde først søgning af felterne, det vil sige vi starter fra det felt hvor robotten står, og søger efter vores destinationen i ved først at spørge alle naboer, og derefter spørger alle naboer deres naboer. Hver knude gemmer så informationer om hvem der har spurgt dem om vej, for på den måde kan man backtracke ruten tilbage til start.
Dette viste sig dog at være umuligt at implementere, da bredde først søgning næsten er umuligt at implementerer, hvis man ikke skal gemme en eller anden form for tilstand undervejs for at se hvor langt man er nået i søgningen, og det var præcist dette vi gerne vil undgå for at spare hukommelse.

3: Blue tooth.
Vi besluttede, før vi forlod sessionen i dag, at imorgen vil vi implementerer blue tooth kommunikation med en bærbar computer. Resultatet af flere dages kæmpen med at få en fornuftig pathfinding algoritme til at virke, har gjort at vi delvist kan konkludere at dette stort set vil være umuligt for børn i den alder first lego league kræver, at lave en robot der fornuftigt kan finde rundt, ihvertfald ved hjælp af tacho counteren og en lys sensor, der skal helt andre hjælpe midler i brug, men dette vil vi kigge nærmere på i følgende dage. Vi vil ikke afprøve disse metoder da det indvolverer sensorer som vi ikke har.
Men vi vil imorgen gøre at path finding bliver beregnet på en pc og resultatet bliver sent til nxt enheden.

Bevægelse

Session: Tirsdag 08/01-08 kl. 9-16

Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1. Designe en bevægelses metode.
2. Test bevægelse på Mars pladen.
3. Garbage collection i nxt enheden.

1:Designe en bevægelses metode.
Vi besluttede os for, som vi havde beskrevet igår, at benytte metoden i tacho counteren, som kunne flytte robotten baseret på centimeter. Det vil sige at vi skulle tilføje et centimeter tal til vores koordinater, som beskriver hvor centrum af firkanten (koordinaten) befinder sig på Mars pladen. Vi besluttede os for at koordinat systemets (0,0) punkt skulle befinde sig nederst i venstre hjørne af Mars pladen. Nederste venstre hjørne er i forhold til billede 2 fra blog indlæg den 5. januar.

Vi konstaterede igår at vores path finding algoritme virker som den skal både på windows, men også på nxt enheden. Dermed er det eneste vi skal sørge for idag, at robotten bevæger sig det korrekte antal centimeter for at komme fra koordinat til koordinat.
De tests vi foretog i denne sammenhæng var først at lave en simpel sti bestående af et start og et slut punkt, som var naboer i koordinat systemet. Denne simple test lykkedes, men som sagt er den simpel.

Vi målte os frem til at der var 21, 3cm fra midten til midten af en koordinat i Y-aksen og 21,8cm i X-aksen. Derudover skulle vi ligge et lille offset til X-aksen da vi gerne ville have vore lys sensor til, at være over de tykke sorte linie, da vi her bruger ly sensoren.
Lys sensoren bruges til at korrigerer for eventuelle småfejl i tacho counteren. Hver gang vi regner med at støde ind i en tyk sort linie, så stopper vi lidt før, hvorefter vi aktiverer lys sensoren og rykker 1 centimeter af gangen indtil lys sensoren har fundet sort. Vi resetter nu tacho counteren til den koordinat vi står i.

2. Test bevægelse på Mars pladen.
De mere komplicerede tests vi lavede her var, at bygge og følge en længere sti fra start til slut. Vi valgte at lave en sti af længde 8, det vil sige at robotten skulle besøge 7 koordinater før den nåede sit mål. Dertil prøvede vi en sti af længde 4 i den modsatte retning (robotten skulle i begge tilfælde dreje en eller flere gange før den nåede sit mål. Stierne er illustreret i de følgende to billeder.

I denne figur ses den første sti som sort linie.

I denne figur ses den anden sti som sort linie

Grunden til at vi skulle bevæge os i begge retninger er at der er forskel på hvor langt vi skal bevæge os i den negative X- og den positive X retninger før vi begynder at lede efter den tykt optrukne sorte linie. Grunden til dette er at robottens center er lokaliseret i kanten af en sort linie, det vil sige ikke i centrum af en koordinat. Vi observerede visse afvigelser, men i bund og grund kom robotten fra start punktet til slut punktet uden alt for stor afvigelse fra den planlagte rute.
Vi blev enige om at i reelle omgivelser, det vil sige ikke simulerede omgivelser på en computer, så er det umuligt at lave noget som altid er 100% præcist. I begge tilfælde var resultatet acceptabelt, men med små og varierende afvigelser.

3. Garbage collection i nxt enheden.
Vi løb i dag ind i store problemer da vi skulle teste path finderen med flere forskellige ruter, det vil sige at vi brugte path finder algoritmen mere end en enkelt gang på nxt enheden. Problemet var simpelthen at nxt enheden løb tør for hukommelse Nxt enheden har ialt 64kb RAM, så det er ikke meget vi har at arbejde med.
Grunden til at vi løber tør for hukommelse stammer fra den måde vi udregner stier i koordinat systemet op. I udregnelsen opbygger flere arrays vi bruger til mellemregninger, og det hukkomelse, som bliver brugt til disse arrays bliver ikke frigivet når algoritmen er færdig.
Vi forsøgte først at løse problemet ved at genbruge hukommelse, men da dette gav os yderligere problemer med null pointer exception, valgte vi istedet at kigge på en meget ny udgivelse at nxt softwaren, som indbefatter garbage collection. Dette var imidlertidigt ikke noget vi nåede at blive færdig med idag, da vi først fandt problemet meget sent. Vi vil arbejde videre med dette problem imorgen.

Navigering på spillepladen

Session: Mandag 07/01-08 kl. 9-16

Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1. Redesigne robotten endnu en gang.
2. Eksperimenter med tacho units i forhold til centimeter.
3. Navigering på Mars pladen.
4. Tilrette vores pathfinding algoritme til NXT enheden.

1.Redesigne robotten endnu en gang.
Endnu en gang fandt vi det nødvendigt at redesigne vores robot. Den have stadig et par problemer, som gjorde at den havde svært ved at køre lige. Vi fandt ud af at robotten var meget uligevægtig. Motoren som trækker vores løftemekaniske, og selve løftemekanismen, sad i den ene side af robotten, og var dermed med til at trække robotten ned i denne side. Det vi gjorde var at finde noget modvægt, og sætte det i den anden side af robotten. Dette resulterede i at den kørte en smule mere lige, men det var stadig ikke perfekt. Vi ændrede derudover hvor langt der var imellem hver hjul da vi kunne observere at hjulene skrånede en smule ind mod selve bilen. Til sidst observerede vi at hjulene skrabede en smule imod selve robottens konstruktion, og dette kunne yderligere gøre at en motor blev en smule bremset i forhold til den anden, og dermed gøre at robotten kørte skævt.
Vi foretog, i forbindelse med at robotten kørte skævt, nogle eksperimenter for at sikre os at de ting vi ændrede rent faktisk hjalp. Vi fik robotten til at køre det der ca svarer til 100cm på en lige linie, hvorefter vi målte hvor meget den afveg fra denne linie efter afsluttet eksperiment. Vi foretog fem tests før vores ændringer på robotten og observerede i gennemsnit en afvigelse på fem centimeter fra robotten centrum til liniens centrum over en afstand på 100cm. Efter ændringer kunne vi observere at robotten nu kun afveg i gennemsnit 2cm over fem forsøg på en 100cm strækning. Vi fandt at dette var en tilstrækkelig forbedring, men vi kan eventuelt lave flere forsøg senere hvis vi finder at afvigelsen er for stor.
Vi fandt ud af at andre havde haft problemer med tacho counteren, da vi søgte på nettet. Deres problemer er ikke nødvendigvis de samme som vores, men problemerne er dog taget i betragtning og udviklerne erkender at der er visse fejle, som skal rettes i næste udgave af nxt. References til dette er her.
Vores nye design af robotten kan ses på følgende billede:



2. Eksperimenter med tacho units i forhold til centimeter.
Disse simple forsøg gik blot ud på at finde ud af hvor mange tacho units der var per centimeter, sådan at når vi bevæger os på Y-aksen på Mars pladen, så ville vi kunne navigere i centimeter ved hjælp af tacho units. Vi kan nemlig ikke på Y-aksen navigere ved hjælp af de sorte streger da disse er meget tynde i forhold til stregerne, som adskille X-koorinaterne.
Det er dog ikke sikkert at vi i sidste ende bruger tacho units til at navigere med, måske bruger vi centimeter, hvis vi kan få dette til at blive præcist nok. Men lige nu bruger vi tacho units, så derfor skal vi finde ud af hvor mange units der er per centimeter.
Vi opstillede forsøget ved at ligge et centimetermål ud på Mars pladen og starte robotten i den ene ende, og måle hvor langt robotten egentlig kørte når man bedte den om at køre 100cm. Vi udførte igen dette forsøg fem gange og fandt en afvigelse på i gennemsnit fem centimeter, det vil sige robotten kørte i gennemsnit fem centimeter for langt. Vi justerede parametrene, som man skal give tacho counteren, altså målet mellem hver hjul, og hjulets radius. Da disse ændringer var lavet kom vi i fem forsøg ned på en afvigelse på en centimeter i gennemsnit, hvorefter forsøget blev meget svært forbedre, og vi besluttede at resultatet var tilstrækkeligt.
Forsøgets opstilling kan ses på følgende billede:



3. Navigering på Mars pladen.
Efter vi fik lavet algoritmen til at navigere på Mars pladen, stod vi nu overfor det problem der var i rent faktisk, at bevæge robotten fra start positionen til slut positionen. Det skal først siges at vi, i dag, ikke blev færdige med dette, men arbejdet med dette skulle gerne færdiggøres i morgen. Vi har dog overvejet to løsninger til dette problem, men ingen er i dag blevet implementeret. Begge løsninger har selvfølgelig det til fælles, at vi tager det første element vi får tilbage fra den ArrayListe fra path finding algoritmen, og derefter går alle elementerne igennem en efter en, for til sidst at komme til destinationen. Måden vi kommer fra punkt til punkt i denne ArrayListe på, varierer i vore to løsninger.
I den første løsning var planen, at holde styr på vinklen robotten står i, og hvor meget den præcist skal bevæge sig for at komme fra punkt til punkt. Denne løsning giver mange varibler, som der er nødvendigt at vedligeholde, og komplicerer også selve bevægelsen af robotten fra punkt til punkt, da dette er noget vi selv skal implementerer.
I den anden løsning giver vi centret i hvert punkt(hver firkant på Mars pladen), i koordinat systemet, en koordinat i centimeter. Vi fandt ud af at tacho counteren selv kan roterer og navigerer fra punkt til punkt i et koordinat system, hvor enhederne er centimeter. Dette vil simplificerer vores navigering meget, da vi ikke selv skal holde styr på at roterer og køre vores robot, det vil tacho counteren selv klare. Vi hælder til sidst forklarede løsning, og denne vil vi fortsætte med i morgen.

4. Tilrette vores pathfinding algoritme til NXT enheden.
Da vi testede vores path finding algoritme på nxt enheden havde vi nogle problemer. Den virtuelle maskine, som ligger på nxt enheden, er en begrænset udgave af den virtuelle maskine, som ligger i windows. Det første vi løb ind i, var at vores repræsentation af koordinat systemet ikke var gyldig på nxt enheden. Vi havde repræsenteret koordinat systemet som et multi dimensionelt array, men da dette dig imidlertidigt er muligt på en nxt enhed, så havde vi dog stadig problemer, og vi fik fejl, som vi ikke rigtigt forstod, men vi forstod dog så meget af dem, at vi kunne identificerer fejlens oprindelsen, dog ikke problemet. Vi valgte istedet at løse problemer ved at lave et ArrayListe med Arrylister. Dette er i bund og grund det samme som et flerdimensionelt array, men det er åbenbart arrangeret på en måde i hukkommelse, som nxt enheden kan håndterer. Derudover kørte vores algoritmen som den skulle, vi lavede selvfølgelig forsøg med path finding på enheden, og resultatet af disse forsøg blev som forventet en korrekt rute fra punkt A til punkt B.

Imorgen er den primære plan, at få robotten til at bevæge sig efter en rute fundet med vores path finding algoritme, og hvis der er tid til det, så vil vi starte med at implementerer løsningen til de første opgaver.

Systemarkitektur og pathfinding

Session: Søndag 06/01-08 kl. 9-16
Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1. Færdiggøre redesign af robot.
2. Implementere systemarkitektur.
3. Implementere repræsentation spillepladen.
4. Implementere pathfinding algoritme.

1. Redesign af robot
Vores redesign af vores robot er færdigt, og den står nu som det ses på nedenstående billede:



Det har skabt større stabilitet at ligge NXT enheden ned. Dette har gjort at vores kran sidder bedre fast, og er nemmere at drive. Samtidigt er vores lyssensor kommet helt ind imellem hjulene, således at den nu kan køre over alle forhindringer.

2. Systemarkitektur
hele vores systemarkitektur er nu på plads, inkl vores main event loop. Vi har implementeret vores egen MarsNavigator, som extender TachoNavigator med metoder til at køre imellem grid-celler, og derved abstrahere tacho-counters osv. væk. Navigatoren bruger PathFinder klassen til at finde ruter igennem vores miljø. Vi beskriver PathFinder senere.
Det eneste vi mangler at implementere er sådan set metoden der pålideligt kan bringe robotten fra en celle (kvadrat man får når longitude og lattitude stregerne skærer hinanden) til en anden celle.
Vi planlægger, som beskrevet tidligere, at bruge de brede sorte længedegrads streger til at finde ud af i hvilken 'kolonne' vi befinder os i henad x-aksen. Dette betyder at vi ikke bruger tacho-counteren til dette, hvilket skule give os større præcision. Vi har så 2 referencepunkter på pladen i y=0 rækken (se tidligere tegning af spillepladen) hvor vi kan resette vores tachocouner. Vi håber at dette kan give os en rimelig præcision i både x og y aksens retning.
Til at finde ud af hvornår vi kører hen over en af de bredde sorte streger, har vi lavet en MarsSensor klasse, der har metoder specifikt til dette.

Vi løb ind i en teknisk begrænsning da vi implementerede vores MarsNavigator. Det viser sig at Runnable interfacet fra Java, ikke er tilgængeligt i Lejos. Derfor kan vi ikke lave denne som en tråd, som vi egentlig kunne have tænkt os. Vi har derfor måtte arbejde udenom dette problem.
Den komplette kode for vores robot er her.



3. Repræsentation af spillepladen
Vi har valgt at repræsentere spillepladen som et 2-dimensionelt array af Node's. En Node er indtil videre bare en x,y koordinat, men på denne måde har vi mulighed for at tilføre mere funktionalitet til disse senere. De kvadrater hvor der er forhindringer på, og hvor vi derfor ikke kan køre hen, bliver sat til null.



4. Implementere pathfinding algoritme.
Vores pathfinding algoritme finder den korteste sti fra en grid-cell til en anden og returnerer denne sti i form af en list af Node's. Grundet den relativt lille spilleplade har det været muligt at implementere denne algoritme som en rekursiv dybde-først-søgning. Denne er delvist inspireret af Djikstra, der dog bruger en bredde-først-søgning. Vi beregner derved alle mulige stier til vores destination, men ved hver returning fra et rekusrsivt kald, bliver de længste ruter sorteret fra.
Vi har lavet et simpelt PathTest program, der tester denne pathfinder. Dette kan også findes blandt vores anden kode.

Arkitektur beskrivelse. Initiel ideudvikling.

Session: Lørdag 05/01-08 kl. 9-15
Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1. Beskrivelse af initielle løsningsidéer.
2. Eksperimentere med de forskellige løsningsforslag.


1. Initielle idéer.
Vores første løsningsforslag er som følger:
Vores spilleplade bliver opdelt i 12x6 kvadrater, svarende til inddelingen der fremstår af højde og breddegrads stregerne. (Se forrige indlæg for billede af spillepladen). Hvert kvadrat kan enten beskrives som værende frit, eller at have en specifik forhindring på sig. Vi repræsenterer dette via et byte array.
Til at navigere rundt på spilledepladen vil vi så anvende en pathfinding algoritme. Mulige forslag vil være A* eller Djikstra. For at spare tid vil vi forsøge at finde en færdig implementeret version.

Opbygningen af vores program bliver som følger:

• Til navigering, laver vi en seperat klasse, der kan holde styr på hvor vi er, og bringe os fra A til B. Denne klasse vil højst sandsynligt anvende TachoNavigator klassen.
• Vi implementerer hver opgave der skal løses som en tråd. En sådan opgavetråd ved hvor den skal bevæge sig hen for at påbegynde opgaven, og hvor den slutter hvis alt går efter planen. Den ved også hvor lang tid opgaven forventes at tage. En opgavetråd vil returnere true hvis alt går som det skal.
• Vores main tråd vil implentere en kø af opgaver og sørge for at starte dem i en givet rækkefølge. Den vedligeholder en timer hver gang en opgave startes der svarer til den forventede opgavetid. Hvis enten denne timer udløber, eller hvis tråden returnerer false, vil main tråden tage kontrollen og prøve at navigere hen til et af vores referencepunkter. Herfra ved vi præcist hvor vi står på pladen og vi kan derefter forsøge den samme opgave igen.

Vores referencepunkter bliver valgt som 2-3 steder på spillepladen som er let tilgængelige og genkendelige. Dette vil højst sandsynligt være enten ved en væg eller et hjørne, hvor vi ved med sikkerhed hvor vi er i enten x eller y retningen. Se nedenstående billede.

Det vil være muligt for os at holde styr på hvor vi er i x-retningen ved at registrere hver gang vi kører over en af de brede sorte linjer. Dette håber vi på at kunne gøre pålideligt.
Planen er så at bruge tachocounteren til at holde styr på hvor vi er i y-retningen. Da den kun bruges til dette, vil det give større pålidelighed. Men da vi ved fra tidligere øvelser at denne er betragteligt upræcist, gør vi brug af vores referencepunkter til at resette vores position efter hver opgave.

Dette er indtil videre den overordnede plan, der dog kan nå at ændre sig mange gange efterhånden som vi udfører eksperimenter.

2. Eksperimenter

Eksperiment A:
Formål: At fastlægge afstanden mellem vores breddegrader målt i tacocounter enheder.
Resultater:
Under vores eksperiment opdagede vi et par kritiske fejl i vores design. Vores lyssensor sidder for langt fremme, således at den rammer på nogle forhindringer og derved forhindrer at robotten kan komme over disse. Vi gik derfor i stå da vi blev nød til at redesigne robotten helt forfra. Et kedeligt tilbageskridt, men hellere nu end senere hvor vi har fået kalibreret alle vores variable efter det forkerte design.

Vores redesign bliver klar til i morgen igen hvor vi mødes næste gang.
Vores systemarkitektur bliver samtidigt også klar i morgen og vi skulle kunne begynde at arbejde på navigationsdelen og problemløsningsdelen i parallel.

Næste møde:

06/01-2008 kl 09:00 i Zuse

Endelig en endelig projektbeskrivelse

Session: Fredag 04/01-08 kl. 9-15
Deltagere: Elvar, Ebbe, Henrik

Sessionens formål:
1. Formulere den endelige projektbeskrivelse
2. Bygge de sidste lego modeller til vores opstilling.
3. Færdiggøre design af vores robot og bygge den.

1. Endelig projektbeskrivelse
Vores projekt tager udgangspunkt i First Lego League projektet fra 2003 - Mission Mars.
Vi vil i denne opgave dog ikke ligge vægt på den hastighed hvormed vi kan løse opgaverne, eller hvor mange point vi kan indsamle. Vi ønsker dog stadig at lave en robot der kan løse opgaverne som foreskrevet i regelsættet.

Vores kerneproblem baserer sig derimod på den observation, at størstedelen af de grupper der er med i First Lego League projekter, ikke har nogen fejlkorrektions mekanisme indbygget i deres robots adfærd. Det vil sige at hvis en robot kommer galt afsted eller farer vild på en eller anden måde, løfter gruppedeltagerne simpelthen robotten af bordet tilbage til startstedet og prøver igen. Set fra et pointmæssigt synspunkt i konkurrencen er dette en effektiv løsning. Men set fra et rent teknisk synspunkt er dette hverken ikke en særlig køn eller interessant måde at gribe tingene an på.

Vores fokus vil derfor primært være på at implementere en navigerings algoritme, således at vores robot altid kan finde tilbage til et af flere specifikke referencepunkter. Dermed kan vi bruge dette som basis for fejlkorrektion ved simpelthen at prøve forfra hvis vi finder ud af at noget går galt under udførelsen af en opgave.

Mission Mars spillepladen er specielt velegnet til netop dette formål pga. dens indtegnede højde og breddegrader. Vores endelige mål er at få en robot der løser alle opgaverne uden nogen menneskelig indgriben. Dog vil fokus være på den algoritme der finder tilbage til basen, da vi arbejder indenfor en givet tidsramme.


2. Færdiggørelse af legomodeller
Vores spilleplade står nu klar, med alle legomodeller bygget efter specifikation. Et billede kan ses her:

En beskrivelse af alle elementerne på spillepladen og de opgaver der skal løses kan ses her:
http://80.89.35.72/challenge2003/dansk/oppdrag.html


3. Design og færdiggørelse af robot.
Vores initielle design for vores robot kan ses på nedenstående billeder:


Opbygningen følger den standard NXT opbygning som vi kender det. Vi har tilføjet en 3. motor der styrer en arm der kan løftes og sænkes. Lidt ligesom en gaffeltruck. På denne måde håber vi på, at vi kan bruge den til både at løfte, feje, skubbe og trække.