Features
In onderstaande
opgave staan de doelstellingen die bereikt zijn in het vet aangegeven.
Dit project
bestaat uit het ontwerp en
implementatie van een algemeen robotbesturings-programma. Het programma
moet
een willekeurige robot kunnen besturen die opgebouwd is uit volgende
componenten :
Vaste arm van willekeurige lengte
Uitschuifbare arm met minimum- en
maximumlengte
Rotatie-scharnier dat tussen twee armen
wordt geplaatst, met minimum en maximum rotatie-hoek.
Verplaatsbaar voetstuk
Verscheidene armuiteinden: boor, grijparm, trekijzer, pen
Om redenen
van eenvoud beperken we ons tot
twee-dimensionale bewegingen. Als output wordt een grafische weergave
in een
vlak verwacht. Verschillende grijparmen kunnen andere output genereren. Een
boor bijvoorbeeld genereert een puntje op de plaats waar hij boort.
Bijkomende
aspecten:
Ontdekken dat de robot zichzelf snijdt
Met meer dan één robot tegelijkertijd
werken (met ontdekken van snijden onderling)
Enkele voorgedefiniëerde
constructies voorzien die bestaan uit een compositie van de bestaande
componenten. Bijvoorbeeld een "kootjes-arm" bestaande uit vele kleine
dezelfde armpjes en dezelfde scharnieren die een boog (of andere
ingewikkelde
bewegingen) benaderen.
Demonstreer
het robotbesturingsprogramma door
enkele robots te configureren en iets te laten uitvoeren (bijvoorbeeld
een
vierkant tekenen en in het midden een gat boren).
Interface
Hoe een robot
creëren ?
Een robot wordt
opgebouwd als een boom, waarbij elke knoop zelf zorgt dat hij zijn
opvolgers
kent. Het is dus geen boom die als structuur over componenten wordt
gemapt. Het
zijn de componenten die een boomstructuur krijgen. Robots worden
gecreëerd door
een scheme-expressie in te typen. Bijvoorbeeld de robot
wordt informeel
als volgt gecreëerd.
robot-root:=
(make-robot
(make-arm1 ...
(make-arm2 ...
(make-arm3 ...
(make-arm4 ...
null-component)))))
Wat er in de
plaats van de "..." komt hangt van component tot component af.
Meestal zit hier een voethoek tussen
die aanduidt welke hoek de volgende component (child)altijd
moet vormen met de huidige component. Zo is het
mogelijk twee armen direct aan mekaar te sluiten onder een willekeurige
vaste
hoek zonder een scharnier te moeten gebruiken.
|
Componenten |
|
|
How to make ? |
Visualization |
|
make-normal-arm lengte voethoek child |
|
|
make-arm minimum maximum lengte voethoek child |
|
|
make-scharnier minimum maximum rotation voethoek child |
|
|
make-robot position voethoek child |
|
Interface tot
de componenten.
|
Actions available |
|
|
name & parameters |
action |
|
boor boor-component |
Boort een gat op de
huidige plaats. Het gat wordt voorgesteld door een rondje op de plaats
waar geboord werd. |
|
pen-color pen-component |
Verandert de kleur
van de meegegeven pen. De volgende keer dat een lijn moet getekend
worden zal dit in de nieuwe kleur gebeuren. |
|
pen-down pen-component |
Zet de pen op
papier. De eerst volgende keer dat de pen wordt verplaatst.
Bijvoorbeeld door een armbeweging of door het verplaatsen van de robot
zal er een lijn in kleur color getekend worden. (color is gedefinieerd bij het creëeren van de pen) |
|
pen-up pen-component |
Heft de pen op van
het papier zodat, als de robot in het vervolg beweegt, geen lijnen meer
worden getekend. |
|
arm-length who angle |
Verandert de lengte
van de meegegeven arm. Who mag ofwel een vaste arm
zijn, ofwel een variabele arm. Bij het veranderen van de armlengte
wordt gecontroleerd of de robot zichzelf niet snijdt, nadien wordt
gecontroleerd of de globale wereld niet om zeep wordt geholpen. |
|
rotate who angle |
Verandert de hoek
van who, indien hiermee niet gezondigd wordt tegen de
minimum/maximum hoeken. Bij deze operatie worden geen[1] interne, noch externe snijdingen gecontroleerd. |
|
rel-move who speedx speedy |
Deze routine zorgt
dat de robot over (x,y) verplaatst. Hierbij worden
botsingen met andere robot's gecontroleerd. De meegegeven paramater who moet een robot-root zijn. Indien niet zal er een
error optreden. |
Programma's
Het is normaal
dat een robot aangestuurd wordt door programma's. In deze implementatie
heb ik
gekozen voor scheme-programma's omdat die zeer expressief zijn,
recursie
aankunnen en voldoende abstractie toelaten. Een programma wordt
voorgesteld
door een lijst van commando's en instructies. Op het ogenblik dat een
error
ontstaat wordt het programma onderbroken om de error te laten zien,
nadien kan
verder gewerkt/gespeeld worden. Indien het programma de error
onderschept en
zelf oplost is hier natuurlijk geen enkel probleem en zal de loop van
het
programma niet onderbroken worden. Onderstaand voorbeeld is één van de
demo's.
(define
program2 '(
(define ralf-arm4 (make-arm 10 200 50
PI/2 null-component))
(define ralf-arm3 (make-arm 10 200 20
PI/2 ralf-arm4))
(define ralf-arm2 (make-arm 10 200 80
PI/2 ralf-arm3))
(define ralf-arm1 (make-arm 10 200 70
PI/2 ralf-arm2))
(define ralf-voet (make-robot
(make-point 150 30) PI/2 ralf-arm1))
(arm-length ralf-arm4 70)
(arm-length ralf-arm4 90)
(arm-length ralf-arm4 110)
(arm-length ralf-arm3 100)
(arm-length ralf-arm2 200)
(arm-length ralf-arm3 100)
(arm-length ralf-arm2 80)
(arm-length ralf-arm4 100)
(arm-length ralf-arm1 100)
))
(loop-program
program2)
Error-meldingen
Een error-melding
bestaat uit 2 delen, een numerieke representatie en een
string-representatie.
Dit is een beetje zoals de BGI waarbij je voor elke error een
bijpassende
string kan opvragen. Om te controleren of het resultaat een error is
kan je de
procedure error? gebruiken, om de
getal-waarde dan op te vragen gebruik je error-info
en om de textuele representatie te bemachtigen smeek je om error-text.
Mogelijke error-meldingen zijn :
|
Error-meldingen |
||
|
value |
textueel |
meaning |
|
'glue |
"robot-lussen" |
Je probeert één
component in 2 robot's te gebruiken. Of 1 component 2 vaders te geven. |
|
'sub |
"intersecting sub-world" |
De gevraagde actie
kan niet worden uitgevoerd omdat de robot's sub-world anders gestoord
wordt. M.a.w de robot zal zichzelf snijden. |
|
'glob |
"intersecting global world" |
De gevraagde actie
zal aanleiding geven tot snijdingen met andere robots. |
|
'arminit |
"impossible arm-value" |
Je wil een arm
initialiseren met akelig foute waarden. Bijvoorbeeld een
minimum-armlengte die groter is dan de maximumlengte. Of een
init-lengte die niet in [min,max] ligt |
|
'length |
"invalid length" |
Je hebt arm-length
opgeroepen en getracht een nieuwe waarde in te stellen die
groter is dan de maximumlengte (of keiner dan de minimumlengte) |
|
'rotinit |
"impossible rot-value" |
Het scharnier moet
een hoek meekrijgen tussen minangle en maxangle.
Ook moet minangle<maxangle. |
|
'rot |
"invalid angle" |
Rotate geeft deze error weer indien de gevraagde hoek
buiten het interval [minangle,maxangle]
valt. |
De implementatie
Basis adt's
Het programma
maakt gebruik van een heel stel basis-adts. Meestal zijn dit abstracte
definities van grafische objecten met een verzameling operatoren op
gedefinieerd. Hieronder staan deze adt's snel bij elkaar geraapt.
|
Altijd weerkerend operaties |
|
|
name & parameters |
action |
|
x-int; y-int |
Geeft het
x/y-interval weer waarop het grafische object gedefinieerd is. |
|
type-number |
Elk grafisch object
heeft zijn eigen type-number zodat het berekenen van intersecties zeer
eenvoudig kan verlopen. |
|
display |
Deze functie vraagt
aan het object zichzelf af te printen in het trace venster door gebruik
te maken van de functie message. |
|
show-point color |
Vraagt het object
zichzelf zichtbaar te maken op een grafische wijze, waarbij gebruik
wordt gemaakt van de standaard PCS-BGI routines. Color bepaalt
de kleur waarin het object moet getekend worden. Als hier 'ownstyle
wordt meegegeven duidt dit aan dat er een zekere "standaardkleur"
gebruikt moet worden. |
|
translate vct |
Copieert self en verplaatst het resultaat over een afstand vct. |
|
translate-sleep vct |
Verplaatst self over een afstand vct. Hierbij wordt
een nieuw object gecreëerd, dat niet noodzakelijk van hetzelfde type
is. Een punt verslepen geeft bijvoorbeeld een lijn. |
|
rotate around angle |
Roteert self
over een hoek angle waarbij het centrum in around
gelegen is. Hierbij wordt een nieuw object gecreëerd. |
|
rotate-sleep around angle |
Roteert en sleept self. Hierbij wordt een nieuw object weergegeven dat niet
noodzakelijk van hetzelfde type is. Een punt rotate-sleep-en
bijvoorbeeld zal aanleiding geven tot een cirkelboog. |
|
punt-op? p |
Geeft weer of p op het grafische object ligt. Het is duidelijk
dat dit voor een open grafische verzameling anders is dan voor een
gesloten grafische verzameling. |
|
nulpunten@horizon horizon |
Geeft als resultaat
een gesorteerde lijst naar buiten van nulpunten. Deze operatie is nodig
om nadien te kunnen controleren of een punt in een gesloten kromme valt. |
Points
hebben niet veel speciaals voor de rest. Je kan hun x,y coordinaat
opvragen en
op het ogenblik dat ze aangemaakt worden, worden ze geconverteerd naar
een
grid.
Lines tussen twee verschillende punten. Operaties hierop zijn from-p; to-p, from-x; from-y; to-x; to-y; dx; dy; dx/dy; dy/dx; horizontal?; vertikal?; fast-poin-op?; point-in-range?; x@y; y@x.
Circles bestaande uit een middelpunt, straal, een from-angle en een to-angle. Operaties hierop zijn : radius; center; from-angle; to-angle; center-x; center-y; angle-of; point@angle; fast-point-op?
Een open grafische verzameling, graphset genaamd. Operaties zijn punt-in?; empty?; singleton; %replace; recalc-bounds; info; set-info!; foreach; copy; add!
Een
gesloten grafische verzameling is exactly een open grafische
verzameling met
het enige verschil dat de punt-op?
herschreven is.
Subworld
De
subworld/subwereld is de omgeving waarin één robot leeft. Een subwereld
bestaat
uit een verzameling tekeningen geassocieerd met de bijhorende
componenten. De
subwereld kan zelf controleren of er ongewenste snijdingen optreden.
Dit is
enigzins normaal omdat men zo een mooi symmetrische oplossing
verkrijgt. Ik kon
evengoed de subwereld gewoon de verzameling van tekeningen/robots laten
zijn
zonder meer. Een soort dictionary without brains, maar de vraag is dan
:
"wie moet de snijdingen controleren ?". Moet de component die iets
wil doen zijn eigen snijdingen controleren. Nee want dit is net een
iets te
laag niveau. Met de oplossing die ik heb gekozen heb je een soort
supervisie
vanuit de subwereld over de robot. Al hetgeen nodig is om snijdingen te
controleren
is aanwezig. Terwijl je met een implementatie in de robots veel
rompslomp zou
krijgen van "dikmakende" data-members.
World
De world/wereld
is de verzameling van
robot-werelden, subworlds die in evenwicht zijn. Met in evenwicht zijn
bedoel
ik dat er geen interne snijdingen voorkomen. De wereld is in staat om
een
gegeven grafisch object te snijden met al de subwerelden (bijvoorbeeld
: een
sleeppad). Zo kan naderhand gecontroleerd worden of er geen globale
snijdingen
voorkomen.
Untouchable
world
The untouchable
world is de wereld waarbij
gewoon grafische objecten worden onthouden zonder dat deze enige
invloed hebben
op het gedrag van de robots. Hier worden lijnen/cirkels samen met hun
kleur
onthouden. Een robot kan dus "door" de tekeningen lopen zonder daar
enige
hinder van te ondervinden.
Componenten
Een component kan
zijn : Vaste arm, Beweegbare arm, Robot-voet, Scharnier, Terminals
Waarbij de terminals de armuiteinde vormen, ttz : Pen, Boor, Null
Van een component
wordt verwacht dat hij in staat is te zeggen met wie hij altijd
verbonden is zodat de subworld kan opzoeken welke snijdingen relevant
zijn en
welke niet. Een arm bijvoorbeeld zal altijd snijden met zijn child-arm, daarom is deze snijding
verwaarloosbaar.
Componenten
moeten ook in staat zijn een sleeppad weer te geven van wat er gaat
gebeuren.
Op onderstaande tekening staat gedemonstreerd wat met een sleeppad
bedoelt
wordt.
Voor de rest
controleert de component nog of hetgeen hem gevraagd wordt wel een
uitvoerbare
eis is. Bijvoorbeeld een negatieve armlengte zal meestal niet goed
gekeurd
worden.
|
Berichten voor alle componenten |
|
|
name & parameters |
action |
|
set-sub-world! to |
Wordt opgeroepen
als de sub-world van de robot verandert. |
|
set-drawing! to |
Wordt opgeroepen
als de tekening van de component veranderd is. |
|
glue father |
Lijmt componenten
aaneen zodat ze een tree vormen. Indien father reeds gekend was wordt
#f weergegeven. (dit wil dus zeggen dat de component reeds in gebruik
was). De glue message wordt doorgegeven aan de
kinderen. |
|
unglue |
Zorgt dat de vader
niet meer gekend is. Deze routine dient opgeroepen te worden als de
creatie van de robot mislukt is, zodat de componenten in een nieuwe
robot gebruikt kunnen worden |
|
sign-in-world sw pos angle |
Na het aaneen glue-en van de componenten moet ook een subwereld
gecreëerd worden. Dit wordt met deze message gedaan. Sw
is de subworld waarin het resultaat moet komen, pos is
de positie van de component, angle is de hoek die de
component zal vormen. |
|
change-translate-world! result-in howmuch |
Vraagt de component
of hij zichzelf eens denkbeeldig wil verplaatsen over afstand howmuch. Hierbij wordt verwacht dat in result-in de oude tekening van de component wordt
vervangen door een nieuwe. |
|
add-translate-sleeppad! result-in howmuch |
Vraagt de component
of hij het sleeppad ten gevolge van een translate over howmuch
wil vervolledigen in result-in |
|
translate-action naar |
Vertelt de
component dat al de checks voor een translatie positief waren en dat de
translatie over naar uitgevoerd mag worden. Hierbij
wordt niet verwacht dat de tekeningen en de subworlds ge-update worden.
Deze zijn reeds veranderd. Deze routine zorgt gewoon dat een component
zijn nieuwe positie kan bijhouden |
|
change-rotate-world! result-in around howmuch |
Vraagt aan de
component of hij zichzelf eens denkbeeldig wil roteren rond around
bij een hoek van howmuch. Hierbij dient de oude
tekening van de component die aanwezig is in result-in
vervangen worden door een nieuwe tekening. |
|
rotate-action around angle |
Net zoals bij translate-action laat dit bericht toe dat de component
zijn posities en hoeken up to date blijven. |
|
Always-connected-to |
Dit bericht vraagt
de component of hij eens een lijst wil naar buiten geven met wie hij
altijd verbonden zal zijn. Dit is om vanzelfsprekende snijdingen op
voorhand weg te filteren en zelf niet meer te controleren. |
Waarom er voor
een translatie 3 berichten nodig zijn (change-translate-world!,
add-translate-sleeppad!, translate-action) zal duidelijk worden in
het
volgende kapittel :
Hoe beweegt
een component/robot nu ?
De component weet
wat hij wil doen, maar vraagt aan een andere routine om deze taak tot
uitvoering te brengen. Deze routine heeft de, toch wel
vanzelfsprekende, naam want-to-act en zorgt voor een
zeer grote
leesbaarheid van de geïmplementeerde acties.
In : function get-sub-world,
function get-sleep-pad, function act
Out : error-melding/#t
Comments : Met de functie get-sub-world
mag de component een voorstel doen om een nieuwe subwereld te creëren
voor de
robot. Als de voorstel-subwereld intact is moet de caller een sleep-pad
opdissen zodat gecontroleerd kan worden of dit sleeppad tegen niets
onaangenaams knalt. Indien wel wordt een error naar buiten geworpen.
Indien ook
hier geen problemen waren mag de robot in actie treden door act
op te roepen.
Van act wordt niet verwacht
dat hij de oude componenten gaat verplaatsen in de nieuwe wereld. Deze
berekening is al eens gedaan en moet niet herdaan worden. Gewoon de
component-positions/angles moeten hierbij aangepast worden. Als act ten uitvoer wordt gebracht is de
nieuwe wereld reeds actief.
Ik heb het algoritme hieronder laten staan omdat het een zeer
representatief
stuk code is voor het gehele programma.
(define
(want-to-act get-sub-world get-sleep-pad act)
(let
((new-sub-world
(get-sub-world)))
(if
(new-sub-world 'disturbed?)
(begin
((new-sub-world 'redraw)
'red)
(make-error 'sub
"intersecting sub-world"))
(begin
(if sub-world ((world
'unregister) sub-world))
(let* ((sleeppad
(get-sleep-pad new-sub-world)))
(if ((world
'disturbs-with?) sleeppad (fast-set))
(begin
(if sub-world
((world 'register) sub-world))
((sleeppad
'show) 'red)
((new-sub-world
'redraw) 'light-red)
(make-error 'glob
"intersecting global world"))
(begin
(new-sub-world
'wring-er-tussen)
(act))))))))
Mogelijke verbeteringen
Ik had de
intentie om de rotatie-operator in volle glorie te implementeren zodat
het
draaien van een scharnier tot geen onmogelijke situaties meer zou
leiden. Maar
bij gebrek aan PCS-cell-geheugen heb ik dit niet tot uitvoering kunnen
brengen.
Om mezelf toch een beetje te verdedigen en aan te tonen dat ik de
nodige
funderingen al had aangebracht beschrijf ik nu even wat er aan het
programma
zou moeten veranderen.
Voornamelijk
zorgen dat de Nulpunten@horizon
gedefinieerd wordt voor een cirkel. Dit is niet moeilijk maar nog niet
gedaan.
De
huidige rotatie-actie vervangen door de want-to-act
function (zonder aan want-to-act iets
te moeten aanpassen !)
Een ander
spaaklopend element van dit programma is ongetwijfeld zijn snelheid. Ik
heb
hier en daar al kleine optimisaties in gestoken omdat ik het anders
helemaal
niet meer kon testen, maar een paar
-altijd van gedroomd, maar nooit geïmplementeerde- optimisaties
staan
hieronder vermeld :
Om
grafische objecten te snijden wordt eerst rap uitgezocht of de
omvattende
vierhoeken niet snijden (xint/yint).
Als deze rechthoeken echt groot worden, wordt hier geen winst meer aan
gedaan
en zou ik beter op 6-hoeken gaan controleren. Dit zou zeker een
optimisatie
zijn daar waar een robot een grote move wil uitvoeren. (het sleeppad
zorgt dat
de rechthoek absurd groot word)
Ik
gebruik nog steeds list-dispatchers in plaats van vector-dispatchers.
Als ik
deze zou veranderen zou er een zeer grote snelheidswinst geboekt
worden. Maar
aangezien dit het werk van een compiler is heb ik me met deze
tijdverspilling
niet bezig gehouden.
En
dan natuurlijk nog de optimisaties afhankelijk van de omgeving waarin
ik werk :
Ik zou bijvoorbeeld al de variable-namen kunnen vervangen door 3
letters in
plaats van betekenisvolle woorden. Dit is natuurlijk één van de
lelijkste
(desalniettemin, wel performante) optimisaties die ik me kan inbeelden.
Vooral
het gebrek aan leesbaarheid zal nadien verschrikkelijk zijn.
Al
de verzamelingen die in het programma voorkomen zijn geïmplementeerd
met
lijsten. Dit zou veel sneller gaan als ik dubbelgelinkte lijsten zou
gebruiken.
Waarom ik het niet gedaan heb ? Natuurlijk omdat de code dan helemaal
niet meer
mooi/proper is. Als ik een dubbelgelinkte lijst gebruik moet elk object
dat ik
in de lijst bijhoud een fieldje bezitten dat vermeld in welke lijst hij
zit.
Dit fieldje zou dan de prev en next-pointer bevatten. Deze strategie
heb ik
vorig jaar in mijn project GMC toegepast (met veel succes) maar dit
jaar heb ik
geopteerd voor leesbare code waar geen extra -ik weet niet van waar-
fields in
voorkomen. Merk op dat de voorzieningen voor zo'n dubbel gelinkte lijst
al
aanwezig zijn. Graph-set's bevatten reeds een info-field. De
implementatie van
een dubbelgelinkte lijst verandert/verwijdert/voegt toe in O(1).
Het
hertekenen van het scherm op een slimme manier laten gebeuren. Als nu
een robot
verplaatst wordt, wordt het scherm volledig leeg gemaakt en dan alles
hertekend. Het is ook mogelijk de oude subwereld weg te tekenen en dan
de
nieuwe subwereld te tekenen.
Met nog iets meer verstand wordt eerst de oude subwereld verwijderd,
dan de
nieuwe getekend en uiteindelijk al de subwerelden die sneden met oude
ook nog
eens hertekend zodat 'domme zwarte' puntjes niet meer voorkomen.
Toegegeven :
deze laatste gaat veel code in beslag nemen en weinig zin hebben, des
te meer
omdat over de robot's gewaakt wordt zodat ze niet meer snijden.
De interface tot
de robot zou ik liever uitgebreider zien. Mogelijkheden hiertoe zijn
Als
een snijdings-error optreedt ook terug geven tegen wie gelopen wordt.
De
interface tot de wereld algemenere toegankelijker maken zodat
standaardobjecten
toegevoegd kunnen worden. (bijvoorbeeld een tafel die steeds aanwezig
is).
Hetgeen daarvoor nu gedaan moet worden is de init-world
aanroepen en nadien ((global-world
'register) my-table)
Een
meer layer-achtig scherm gebruiken waarbij je objecten op de voorgrond
hebt en
objecten op de achtergrond. Bijvoorbeeld een untouchable-world die voor
de
touchable world ligt en een untouchable world die achter de robots ligt.
Het
zou ook mogelijk zijn dit project om te vormen tot 3D. Het enige
dat
daarvoor aangepast moet worden is de definitie van de grafische
objecten en de
definitie van de snijdingen. Dit zal natuurlijk niet zo gemakkelijk
zijn.
Ook
een toffe mogelijkheid zou het toevoegen van eigen componenten zijn.
Dit is nu
mogelijk met goede kennis van zaken, maar anders ook niet. Je moet
weten op
welke berichten een component allemaal moet reageren. Maar aangezien
dit een
algoritmische bezigheid is kan het in een procedure create-component-maker
gestoken worden. Om een voorbeeld te hebben
wat ik bedoel kan je eens kijken naar de functie create-terminal.
Tijdschema
17-03-95
Final
version afgeprint. (Met speciale dank aan Marc Van Limberghen die deze
tekst
grondig onderzocht heeft)
23-02-95
Afwerking
verslag en documenteren source.
17-02-95
Gauw
oude source door nieuwe source gemixt om verse source te krijgen die de
rotatie
kan uitvoeren. De opdracht nagelezen en de laatste hand gelegd aan het
programma.
10-02-95
De
pen samen met de untouchable world toegevoegd.
09-02-95
De
arm kan resizen met het testen van snijdingen
08-02-95
Een
optimisatie toevoegen zodat ik weer verder kan testen (x-int/y-int)
03-02-95
De
robot kan zichzelf volledig verplaatsen.
08-01-95
De
robot kan al gedefinieerd worden, alleen worden nog geen snijdingen
gecontroleerd.
Voor de rest werken de abstracte grafische objecten l volledig.
24-12-95
Gestart
met implementeren.