Slutprojekt, del 2

Deltagere: Bjarke, Mikkel, Jesper, Troels
Varighed: 4 timer

Mål

Vi skal arbejde videre med Mind arkitekturen og få bygget de tre robotter. Derudover vil vi gerne have lavet nogle baneelementer (tiles).

Plan

1. Byg tre ens robotter.

2. Få arkitekturen på plads.

3. Tegn og print nogle baneelementer.

4. Begynd på at kode.

Resultater

1. Vi konstruerede tre ‘five minute bots’ [1]. Disse blev udbygget med farvesensorer der kigger ned i jorden. Sensorerne skal bruges til at finde vej i banen. Derudover tilføjede vi ultralyds-sensorer, da de alle skal kunne håndtere blokeringer af den edge de bevæger sig ad. Vi er ikke overbevist om, at én farvesensor er tilstrækkeligt. Det er nok til at bevæge sig ned ad en sort edge, men vores robotter skal kunne identificere om edgen pludselig stopper og dette vil muligvis være lettere med to sensorer.

Derudover har vi udbygget “DemolisherBot” med en “fejearm”, der kan fjerne mure fra banen, ved at feje dem til side:

2. Sidste gang diskuterede vi hvorledes kommunikationen mellem robotterne og serveren skulle fungerer [2].
Denne gang er målet at få fastsat en arkitektur på server siden. Som vi bestemte sidst, skal vi bruge en bot-klasse der kan styrer robotterne rundt. Den er ansvarlig for al kommunikation mellem server-arkitekturen og robotterne. Denne bot klasse nedarves af mere specialiserede robot-klasser, der hver især også kan varetage specifikke opgaver.
Indledningsvist lagde vi meget arbejde i, at planlægge hvordan stier skulle kommunikeres mellem vores Hivemind (Den der er ansvarlig for, at det overordnede mål bliver mødt) og bot-klassen. Vi planlagde en simpel form, hvor robottens handlinger og ikke selve stien bliver kommunikeret. Bot-klassen ville da blot modtage en liste over kommandoer, såsom: “LEFT, FORWARD, FORWARD, LEFT...”


Dette gav dog problemer da computeren derved skulle bevare information om robotternes umiddelbare kørselsretning, for at beslutte om der skulle bruges f.eks. FORWARD eller LEFT. Derudover ønskede vi et system, hvor Hivemind'en reserverede stier som robotterne skal bevæge sig ad og i dette system vil det være fordelagtigt at hver del af stien kan ‘unlockes’ løbende, som robotten bevæger sig ad stien. Hvis vi brugte denne kommando-baserede kommunikation, ville computeren selv skulle opretholde en oversigt over de stier robotterne bevæger sig ad, så den kan åbnes løbende. Dette talte samlet set imod et design, hvor hele stier blev sendt til robotten på samme tid.

Vi besluttede at anvende et system der lægger ansvaret for retning hos robot-superklassen (NB. tidligere 'Bot', nu kaldet 'Overmind' (indsat d.25/6)). Fordi vores bane har en grid-baseret opbygning, kan Overmind-klassen også holde styr på robottens placering i banen ud fra et x,y koordinatsystem. Vores Hivemind skal derfor blot sende en liste med tiles, der udgør den vej robotten skal køre til sit mål, til robot-klasserne, hvorefter disse selv opdeler dem i enkelte trin og sørger for at robotten udfører disse ét af gangen. Hiveminden reserverer alle tiles involveret i ruten, således at andre robotter ikke kan bevæge sig over disse før de åbnes igen. Når en robot har bevæget sig fra et tile til et andet, kan det forrige tile åbnes op igen, hvorfor dette skal rapporteres til Hivemind'en.

Banen består, som beskrevet i første blogpost, af kvadratiske tiles. Disse repræsenteres internt af en Tile-klasse. Der kan potentielt være en forbindelse mellem to nabo tiles, men dette er ikke sikkert, derfor skal veje også kunne identificeres. Som beskrevet i forrige blogpost overvejede vi at gøre dette ved hjælp af en matrice, med tiles på hver akse, hvorfor hver indgang i matricen derfor skulle beskrive en potentiel forbindelse. Dette design har vi opgivet af forskellige årsager. En af dem er, at der ville være meget spildplads idet der maksimalt kan være fire forbindelser fra en tile til andre tiles. Yderligere ønskede vi at kunne beskrive om der var en vej fra til A til B og måske ikke fra B til A, idet en blind vej stadig kunne benyttes som midlertidig holdeplads for en robot. Dette blev dog opgivet, efter vi lavede prototyper af de fysiske tiles robotterne skulle færdes på. Det viste sig at de blinde veje ikke var tilstrækkeligt store til formålet, hvorfor dette 2-vejs system er overflødigt.
Vi besluttede at anvende et hashmap i java. De værdier vi mapper sammen er en unik hashværdi for to nabo tiles og en enum der beskriver stiens tilstand (er den der, er den reserveret, er den blokeret etc). Hashing algoritmen ser pt således ud: ( (tile1.x + tile2.x) ^ 37) * (tile1.y + tile2.y) baseret på [5] (NB. Ændret - beskrives i blogpost 7 (25/6)).

Følgende billede viser et uml-diagram over vores server-arkitektur samt en to-do liste. 

3.

Vi har besluttet at tage udgangspunkt i kun at have to slags tiles: et kryds og en hule med en indgang. Derudover overvejer vi at have garager for robotter.

Kryds:

Problemet med denne repræsentation er, hvordan robotterne skal finde over til de nye streger... Her har vi udtænkt følgende tile. Tanken er her, at vi kan bruge en farvesensor [3] til at opdage hvornår vi er i det grønne område og en lyssensor [4] til at følge den sorte streg:

Hule:

Tanken er her at hvis robotten vil ud af hulen, skal den finde grænsen imellem rød og hvid og derefter køre rundt indtil den finder den sorte streg.



4. Løbende med arkitektur diskussionen er der blevet implementeret enkelte interfaces og klasser der hører til på serveren. 

Efter dagens diskussioner har vi fastsat de essentielle variable på hoved-serveren, der skal håndtere verden og robotterne:

Map paths = new HashMap<String, Integer>(); //kanter mellem Tiles

Tile tiles[][] = {}; //Tiles, indgangen i array svarer til position i kartesisk koordinatsyst.

MinerMind miner; 

SeekerMind seeker; 

DemolisherMind demolisher;

Hver af de tre *Mind klasser repræsenterer en robot. Som tidligere nævnt nedarver de fra en OverMind-klasse. Denne har følgende constructor:

public Overmind(HiveMind mind, String bluetoothAddress, String bluetoothName, Tile startTile)

Som det ses af denne, tager hver implementation en forbindelse til Hivemind'en, hvilket gør dem i stand til at kommunikere med denne. Derudover tager den informationer der gør den i stand til at oprette en bluetooth forbindelse til den robot den repræsenterer. Det sidste argument den tager er et Tile, det repræsenterer det felt hvor robotten starter. Dette gør det muligt for robotten at opretholde et billede af hvor i banen den befinder sig. 

Slutteligt implementerede vi Tile klassen. Denne er blot en simpel klasse der holder et x,y koordinat og en type. 

public Tile(int xCoordinate, int yCoordinate, TileType type)

Der er, traditionen tro, getter og setter metoder til disse variable. 

Referencer

1. http://www.nxtprograms.com/five_minute_bot/index.html

2. http://robotteddy.blogspot.com/2012/05/slutprojekt-del-1.html

3. http://lejos.sourceforge.net/p_technologies/nxt/nxj/api/lejos/nxt/ColorSensor.html

4. http://lejos.sourceforge.net/p_technologies/nxt/nxj/api/lejos/nxt/LightSensor.html

5. http://www.javamex.com/tutorials/collections/hash_function_guidelines.shtml

Slutprojekt, del 1

Deltagere: Mikkel, Troels, Bjarke
Varighed: 4,5 timer

Mål

Vi skal diskutere arkitektur og definere de relevante interfaces.

Plan

1. Diskuter designet på et højere niveau for at opnå enighed om problemer og design.
2. Lav punktopstilling over hvad robotterne og “Hivemind” skal gøre.
3. Få lavet en foreløbig arkitektur for projektet og visualiser strukturen (UML).

Resultater

1.
Robotterne:
Vi arbejder pt med henblik på at anvende tre robotter. Deres opbygning vil være tæt på ens, baseret på [1], men med enkelte ændringer der tillader dem at udføre specielle opgaver.
Vi ønsker at have en ‘seeker’-robot, der skal kunne afsøge verden og rapportere alt ind til computeren, der internt opbygger en datastruktur over denne. Computeren bestemmer rækkefølgen af afsøgningen og robotten skal være i stand til at genkende de forskellige elementer verden kan være opbygget af.
Vi skal også bruge en ‘miner’-robot der, når Seekeren har afdækket en mine, kan sendes ud for at hente brikker, der symboliserer guld, i denne. Guldet skal returneres til basen, hvorefter robotten er klar til igen at blive sendt ud.
Sidste robot er en ‘demolisher’-robot, der skal kunne fjerne forhindringer på stier. Denne bliver sendt ud når en opgave er identificeret og derefter kan den enten returnere til basen eller afvente yderligere opgaver ude i banen.



Repræsentationen af verden:
Vi har snakket om en tile-baseret verden. Et tile kan som udgangspunkt enten være et kryds, hvor fire edges mødes, en mine hvor der skal hentes brikker eller en garage hvor robotterne kan holde stille og afvente opgaver.
At anvende en tile-baseret verden giver mulighed for at repræsentere verden i matrix form. Vi skal kunne repræsentere hvert tile, samt om der går en edge mellem to nabo-tiles.
Ideen er at vi vil have en matrix for tiles, hvor hver indgang indeholder et objekt (knude), der fortæller hvad der er på det pågældende tile:

	1	2	3	4	5
1	(1,1)	(2,1) tom
2
3			(3,3) - start
4
5

Derudover vil vi have en lignende matrix med alle objekterne (knuderne), der indeholder informationer for edges (hvorvidt der er en edge, og om der står en blokade på den pågældende edge):

	(1,1)	(1,2)	(1,3)	(1,4)	(1,5)
(1,1)	X	Vej	Vej	Ingen vej	Vej
(2,1)	?	X	Vej	Blokade	?
(3,1)	?	?	X	?	?
(4,1)	Vej	?	?	X	?
(5,1)	?	?	?	?	X

På denne måde kan man også beskrive halve veje imellem tiles, da man kan se at f.eks. vejen fra (4,1)->(1,1) har en vej, hvor (1,1)->(4,1) ikke indeholder en vej. Dette betyder at der er en halv vej fra (4,1) til grænsen imellem (4,1) og (1,1).



Concurrency problemer:
Da vi arbejder ud fra ideen om tre robotter, skal vi sikre os, at der ikke kan opstå deadlocks. Problemet består især i, at vi ønsker at alle robotterne skal kunne færdes i banen simultant, hvilket betyder at to robotter potentielt vil prøve at anvende en sti på samme tid, hvilket vil give problemer.
Vores umiddelbare plan er, at lade computeren der styrer robotterne, låse stier, når en robot skal bruge dem, hvorved andre robotter må finde en anden vej eller afvente at stien låses op igen. Opgaven at låse stier skal naturligvis implementeres på en sådan måde, at to robotter ikke kan ende med at låse samme sti på samme tid og derved kolliderer.
Yderligere skal vi tilføje mulighed for, at en robot kan køre ud på et sidespor, hvis to robotter skal passere hinanden og ingen alternative ruter er tilgængelige.
Vi ønsker også at håndtere et dynamisk element, der er placering af blokader på edges. Disse blokader skal alle robotter selv kunne opdage og rapportere, hvorved computeren skal håndtere de nye informationer og potentielt ændre vægtningen af opgaver. Dette giver dog mulighed for deadlocks, idet stier pludselig skal ændres og en robot kan blive fanget på en sti blokeret af en mur. Derfor skal vi tilføje mulighed for at robotter kan holde en på et sidespor (en blind vej) og afvente yderligere ordre.



Computeropsætning:
Vores computer har to opgaver. Den ene er kommunikationen med robotterne, hvor den i sidste ende skal sørge for at alle miner er opdaget og blevet tømt. Denne opgave inkluderer en intern repræsentation af verden og et system der sikrer at opgaven bliver udført, uden nedbrud.
Den anden er grafisk at repræsentere verden, således at tilskuere kan se hvad computeren ved om verden og hvilke opgaver den har identificeret og sat i gang.





2.
Vores overordnede tanke er, at på computeren vil der være en klasse for hver robot. Hver af disse kører i sin egen tråd og kan koordinere opgaver med programmets hovedtråd.
Enhver robot-klasse har en sender og modtager klasse, der står for kommunikationen med den fysiske robot. Disse sendere og modtager klasser vil alle være instanser af samme klasse, da vi som udgangspunkt vil anvende de samme kald frem og tilbage. Konkret information er tilgængelig i næste punkt.
Alle robotter skal være i stand til at rapportere hvad den ser, når den følger en sti. Der er fire muligheder:

1. En mur der blokerer stien.
2. En blind vej den ikke kan fortsætte af.
3. Et kryds der har fire indgange, hvoraf robotten befinder sig på den ene.
4. En mine, der kun har den ene udgang/indgang robotten befinder sig på.

Derudover vil to af robotterne være i stand til at udføre en speciel opgave. Mineren kan køre ud til en mine, samle en brik op og bevæge sig tilbage til indgangen og demolisheren kan fjerne en forhindring på en edge. Når disse opgaver er udført kan de rapportere dette.

At sende beskeder til robotten varetages ligeledes af en uniform sender-klasse. Denne skal være i stand til at bede robotten om at udføre dens specielle opgave og bevæge sig rundt i verden via følgende kald:

1. Robotten skal dreje til venstre.
2. Robotten skal dreje til højre.
3. Robotten skal dreje 180 grader.
4. Robotten skal køre fremad, indtil den møder en slutning på stien, hvorved den skal rapportere hvad den ser.

Det har været en længere diskussion at nå frem til denne uniforme kommunikation. Vi implementerer et interface der bestemmer metoder i både sender og modtager klassen, men denne idé stammer oprindeligt fra vores første tanke, der gik på en unik sender og modtager klasse for hver robot.
Dette design planlagde vi, da hver robot skulle udføre forskellige opgaver, hvorfor vi forventede at forskellig kommunikation ville blive nødvendig. Behovet for forskelligartet kommunikation er dog afhængig af ansvarsfordelingen mellem robotter og computeren. Vi diskuterede forskellige andre tilgange udover den valgte.


Den ene lagde op til, at hver robot har sin egen specialiserede sender og modtager klasse, som hver kommunikerer med en specialiseret klasse der står for kommunikationen mellem hovedtråden og robotterne. Dette giver dog mange ekstra klasser, med praktisk talt ens kode, hvilket undgås med vores nuværende design.


En anden fjernede mellemleddene og lod hovedtråden kommunikere direkte med sender og modtager klasserne. Dette var dog et problematisk design, da hovedtråden derfor ville blive ansvarlig for flere robot-specifikke opgaver, hvilket ville gøre dens ansvar mere uklart og give rodet kode.


En tredje tilgang indeholdte én robot-klasse, der blev lavet tre implementationer af, som hver kommunikerede med robot-specifikke sendere og modtager klasser. Dette viste sig dog helt umuligt, da en sender og modtager klasserne vil være afhængige af hinanden, hvorfor der et sted skal være en klasse der styrer dette ansvar. Medmindre de to klasser skal være opmærksomme på hinanden, hvilket dog åbner op for en hel verden af nye problematikker vi ikke har interesse i at udforske.
På følgende billede er tavlen efter lang tids diskussion.






Hovedtrådens opbygning og arkitektur blev ikke udarbejdet, men dens ansvar blev diskuteret.
Dens vigtigste opgave bliver at undgå deadlocks i systemet, samtidig med at den sikrer at opgaven udføres. Dette skal gøres ved at have en god intern repræsentation af banen og algoritmer der tillader robotterne at bevæge sig rundt uden at støde ind i hinanden.
Tråden skal også kunne bestemme og prioritere opgaver for hver robot og da vi tillader dynamiske elementer i form af blokeringer der kan placeres på edges, skal tråden også kunne ændre planer og prioriteter, selv mens en robot udfører en anden given opgave.
Da vi som udgangspunkt har tre robotter, som skal opbygges og tilpasses løbende, ønsker vi at kunne udføre opgaver med bare én eller to af robotterne, uden at systemet bryder sammen. Tråden må derfor ikke antage at en specifik robot er tilgængelig, hvorfor vi overvejer en implementation hvor tråden ikke kan kontakte en robot, medmindre kommunikationen er blevet initialiseret af denne robot. Det er naturligvis vigtigt at tråden har kendskab til alle robotter ude i banen, så den kan ændre deres handlinger, baseret på indput fra andre robotter, men i det en robot er ude i banen, har den allerede haft kontakt med tråden for at komme ud.



Udfordringen bliver at have et system der:

• Ikke antager en robot er tilgængelig.
• Kan ændre opgaven for enhver robot der er ude i banen.
• Dynamisk opdatere opgaver for robotter baseret på input fra andre robotter.
• Holde styr på banen og opdatere dens tilstand og udseende dynamisk.
• Tillade robotterne at spørge efter opgaver, og uddelegere disse, mens concurrency problemer undgås.
• Lave en arkitektur der er pæn og velfungerende, der er let at udvide og teste og der virker løbende, mens robotterne udvikles.

3.


Arkitektur
Den overordnede struktur for arkitekturen på computeren kan ses på figuren nedenfor.



Hivemind klassen (her kaldet 'Mind') indeholder en instans af hver type bot og hver af disse bots har en instans af hhv. ISender og IReceiver. Tanken er at hver klasse der nedarver fra Bot-klassen kan startes som en tråd fra ‘Mind’ og derefter selv stå for kommunikation frem og tilbage med de tre robotter via bluetooth. Alle beslutninger og al koordinering mellem de tre robotter, samt den datastruktur der repræsenterer vores verden foregår således via ‘Mind’ klassen og de hjælpeklasser der findes i ‘Mind’ pakken (som illustreret nedenfor).
De to interfaces der benyttes til kommunikation til og fra robotten ser ud som følger:
IReceiver:

og ISender:

Referencer

[1] http://www.nxtprograms.com/five_minute_bot/index.html

NXT Programming, Lesson 11

Deltagere: Mikkel, Troels, Jesper
Varighed: 4,5 timer

Mål

Find tre forslag til slutprojekter og vælg en mulighed (se http://www.legolab.daimi.au.dk/DigitalControl.dir/NXT/Lesson11.dir/Lesson.html).

Plan

1. Specificer tre forskellige projekter. Overvej og diskuter de forskellige projekter og beskriv hvad de forskellige projekter kræver for at blive løst.
2. Beslut et projekt og lav en mere detaljeret beskrivelse.
3. Lav en plan for projektet.

Resultater

1. Specificer tre projekter

Sumo

Lave flere forskellige sumobrydere med forskellige taktikker. Lad dem kæmpe og find ud af om der er en overlegen taktik.
Hardware behov: i hvert fald 3 NXTer hvis ikke flere, alt efter hvor meget tid vi har. Supersonicsensors, touchsensors, lyssensor, 2 motorer på robot.
Software behov: Flere forskellige robotter, evt med forskellige arkitekturer, fx. nogle der er behaviorbased andre der bruger subsumption eller simpel sense-plan-act.
Robotterne skal være i stand til at bestemme hvor andre robotter er, samtidig med at de altid sikrer sig at de er på det rigtige underlag.
Afsluttende præsentation: Mindst 2 sumobrydere der kæmper.

MineRobotter

Forskellige robotter skal samarbejde om at hente ressourcer ud af en mine, hvilket kræver robotternes samlede kompetencer.

Hardware behov:
3 NXTer, 2 Motorer til hver, 3 farvesensorer til at finde streger og orienterer sig i verdenen, da denne vil bestå af forskelligefarvet underlag. Kommunikation via bluetooth.
Tre ultralydssensor, der skal fungerer til at identificere objekter der blokerer en sti og ressourcer i minen.
Software behov: Robotterne får forskellige opgaver og deres sensorer skal derfor være tilpasset derefter. For at styre opgaver og opretholde et kort over verdenen, vil robotterne kommunikere med en PC, der har det centrale software til at uddelegerer arbejde. Computerens ansvar er, at alle ressourcer bliver hentet og at robotter ikke kolliderer i tunnelerne under arbejdet.
Afsluttende præsentation: Et hold af robotter der tømmer en mine for guld. Minen er grid-baseret og robotterne bliver koordineret af en fælles computer så de løser deres opgave på en effektiv måde.

Fodbold

To robotter spiller fodbold med en bold der udsender infrarød signaler.
Hardware behov: 2 NXTer, 2 Infrarøde sensorer, en infrarød fodbold, fodboldbane, 2 motorer på hver NXT, bump-sensorer (eller andre sensorer til at opdage sammenstød imellem robotter).
Software behov: En mulig software arkitektur kunne være en “behavior-based” arkitektur, hvor de forskellige opførsler “kæmper” om retten til at kontrollere robotten. I toppen kunne man have en “undgå” proces, der sikrer at robotterne undgår at køre ind i siderne af bane / hinanden.
Mulige problemer: Det kan godt blive kompliceret at finde målene. Det kan også blive problematisk at afveje vigtigheden af de forskellige processer. Hvis den er forkert kan kampen ende med at robotterne står og prøve at få fat i bolden, men ikke kan komme til da de begge skal undgå hinanden.
Hvad vi regner med at kunne vise i slutningen af projektet: En fodboldkamp imellem to robotter, der formår at score mål og kæmpe frem og tilbage om bolden.
Afsluttende præsentation: en “fodboldkamp” mellem to robotter.

2. Projektvalg

Vi vælger “Mine Robotterne”. Vi synes, at der er gode måder for at skalere projektet på alt efter, hvor godt det går. Vi kan også godt lide, at projektet er orienteret omkring samarbejdende enheder, der skal løse en opgave i stedet for enheder, der skal slå hinanden. Projektet gør brug af mange af de teknikker vi har prøvet i kurset og sætter den ind i en større sammenhæng. Målet for enhederne er lettere at opnå end de andre projektet. Det er derfor lettere, at bygge det op i dele, f.eks. kan man starte med at lave en robot, der kører af en fast sti ind i et rum, hvor den samler en guldklump up, som den så kører ud med igen. Vi vælger specielt projektet, fordi det er det projekt, der har skabt størst entusiasme af de 3.

Verden de befinder sig i, vil delvist være et ‘grid’ af sorte streger, hvor hvert kryds evt er markeret med en anden farve. Enkelte steder ender de sorte streger i et underlag af en anden farve, der markerer en mine, hvor en eller flere klodser er lokeret. Disse skal indsamles. Nogen af de sorte streger vil være blokeret af en mur af klodser, som skal brydes ned før robotterne kan fortsætte.

Der vil som udgangspunkt være tre forskellige robotter. En der er ansvarlig for at afsøge verdenen og lokaliserer huler (Seeker). En der er ansvarlig for at opsøge hulerne og finde de ressourcer der er lokaliseret i dem (Miner). Og en der kan fjerne blokerede stier, hvilket de to andre ikke er i stand til (Wrecker).
De skal alle kunne navigerer i verden, baseret på input fra en PC der fungerer som et hivemind. Computeren er ansvarlig for at opretholde en datastruktur der repræsenterer verdenen og bestemme hvordan robotterne skal bevæge sig rundt i denne. Der vil være forskellige opgaver hver robot skal udføre og computeren skal tage højde for dette.

3. Plan fremadrettet

I næste uge skal vi indsamle materialer og lægge en plan for softwarearkitekturen. Vores målsætning er at få defineret den overordnede struktur for de forskellige moduler vi skal bruge til at opbygge vores robotter. Kort opsummeret skal der laves:

• 3 Robotter
• Tiles
• Interfaces - planlægning af software
• Sammenstukket tre robotter ud fra moduler - plug-n-play.
• Lav PC Hivemind program
• Bluetooth kommunikation
• Fundet og lavet en Single Source Shortest Path.

Det er svært for os at se længere frem end en uge lige nu, men vi vil gerne have så vi kan vise alle 3 slags robotter i brug til den 14. Juni.

Konklusion

Vi har nået alt hvad vi skulle i lab idag. Vi har fået udvalgt et projekt ud fra vores tre ideer og har fået udforsket ideer og problematikker i projektet. Vores fremadrettede plan er løs, men det er alt hvad det er muligt for os at planlægge på nuværende tidspunkt.

Referencer