Deltagere: Mikkel, Troels, Bjarke
Varighed: 4,5 timer
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:
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):
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:
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:
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:
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:
Varighed: 4,5 timer
Mål
Vi skal diskutere arkitektur og definere de relevante interfaces.Plan
- Diskuter designet på et højere niveau for at opnå enighed om problemer og design.
- Lav punktopstilling over hvad robotterne og “Hivemind” skal gøre.
- 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:
- En mur der blokerer stien.
- En blind vej den ikke kan fortsætte af.
- Et kryds der har fire indgange, hvoraf robotten befinder sig på den ene.
- 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:
- Robotten skal dreje til venstre.
- Robotten skal dreje til højre.
- Robotten skal dreje 180 grader.
- 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:
Ingen kommentarer:
Send en kommentar