AI
reasoning about a blockworld
Kaspar de Geus (0426849)
Dolf Klomp (0400130)
Inleiding
In het kader van het vak Zoeken Sturen en Bewegen is er met een robotarm
(UMI RTX 173) eind schaakspellen gespeeld. Hierbij is aandacht besteed aan
zowel redeneren over schaakspellen met behulp van een advice langues als ook
het verplaatsen van de stukken. Voor het verplaatsen van de stukken was vooral
kennis van path planning en inverse kinematics van belang. Als vervolg opdracht
is geprobeerd deze dingen op een nieuw vlak te combineren buiten het schaakspel
om. Hiervoor bleek een blockworld heel geschikt. Hierbij wordt zowel het
redeneren als path planning en general robot movement gebruikt. De path
planning en general robot movements zijn daarbij herschreven om aan de eisen
van de nieuwe opdracht te voldoen. Voor het redeneren is overgestapt op ADL
omdat dit beter aansloot bij de nieuwe opdracht.
Onderzoeksstelling
De doelstelling van het onderzoek was om de oplossing van de Sussmann
analogy [1] na te bootsen. Deze nabootsing hebben wij zowel met een
geïndexeerde plaats als ook met non-geïndexeerde plaatsen proberen te creëren.
Bij non-geïndexeerde plaatsen komt dit neer op het feit dat een bouwsel gebouwd
moet worden, maar de plaats van dit bouwsel niet van belang is. Beide varianten
worden natuurlijk met geïndexeerde blokken gedaan.
De bedoeling was om het bouwen van het bouwsel met de robot te doen.
Hiervoor is gebruik gemaakt van de path planning en de kinematische algoritmes
van de reeds eerder voltooide opdrachten. Daarnaast is er een interface
geschreven om communicatie tussen de verschillende programma’s, de mens en de
robot te vergemakkelijken.
Implementatiemethode
Voor het bereiken van de doelstelling, is gebruikt gemaakt van twee
verschillende programmeertalen. Voor het redeneren over de blockworld en daarin
de juiste zetten vinden is gebruik gemaakt van prolog. Prolog is hier gekozen
omdat er voornamenlijk ADL wordt gebruikt om de blockworld te beschrijven en prolog
dit zeer goed kan verwerken. ADL is gekozen vanwege het feit dat moves van
blokken heel strict aan een aantal precondities moeten voldoen, en een of
meerder effects hebben. De verschillende moves worden daarna gepland met behulp
van ADL door een non-interleaved planner. Er wordt een non-interleaved planner
gebruikt omdat bij ADL een volgende move dan wel pre-condities van een andere
move mag opheffen, wat niet zo is in het geval dat er een interleaved planner
gebruikt wordt. In dit laatste geval is door dit feit de Sussmann analogy niet
oplosbaar.
Prolog is alleen verantwoordelijk voor de redenatie, en zal uiteindelijk
een txt-file schrijven met het geplande pad erin. Daarna is het bovenliggende
Java programma verantwoordelijk voor het updaten van de wereld. Dit gebeurt
zowel fysiek als ook in het computer geheugen (de wereld staat als txt-file in
het computer geheugen).
Het Java programma werkt in de “bereikbare” wereld van de robot. Deze
wereld is als continu veronderstelt, zodat een blokje daadwerkelijk overal kan
worden neergezet waar de robot bij kan, en niet op bepaalde hokjes of iets
dergelijks. Een bijkomend feit hiervan is wel dat er gecontroleerd moet worden
dat er geen overlap plaats vind tussen de blokjes, of dat de robot ze kan
neerzetten zonder andere blokjes aan te raken.
Discussie en Conclusie
Over een blockworld met ongeindexeerde blokken kan volledig geredeneerd
worden, en elk bouwsel wat gewenst is gemaakt worden. Bij een bouwsel moet wel
een geindexeerde plaats opgegeven om het te laten bouwen. In een zelfde
blockworld met geindexeerde blokken kan elk willekeurig bouwsel worden gemaakt
uit elke willekeurige wereld. Hierbij wordt het redelijk efficient gedaan, met
maar één soort move die onnodig is. De doelstelling om de Sussmann analogy na
te kunnen bootsen is hiermee ruimschoots behaald, op het feit na dat dit wel
alleen op een geindexeerde plaats kan.
Het feit dat hij elk willekeurig bouwsel kan bouwen levert ook problemen
op. Er wordt gecheckt of een wereld veilig of onveilig is om te bouwen, maar
niet hard op ingegrepen. Dit vanwege het feit dat de robot sommige dingen net
wel of net niet kan bereiken wat in het programma niet precies te zeggen is.
Naast deze check zijn er ook twee checks die in feite nodig zijn maar niet
uitgevoerd worden door de computer maar door de mens gedaan moeten worden. Het
is mogelijk om een onmogelijke wereld te laten bouwen, hierbij denkend aan
blokjes neer laten zetten buiten het bereik van de robot, of blokjes in de
lucht laten neerzetten. De tweede en belangrijkere check is of er geen blokjes
in de weg van de robot staan, indien er een hoge toren van blokjes vlak naast
een blokje staat wat de robot wil oppakken, kan de robot hier last van hebben.
Future outlook
Drie plannen die in dit project niet uitvoerbaar waren vanwege tijdgebrek
die wel zeer goed te realiseren zijn als voortbouwing op dit project zijn de
volgende:
1: Een
bouwsel kunnen maken met geindexeerde blokken op een ongeindexeerde plaats.
Hiervoor moeten variable in het filesysteem geschreven kunnen worden, die
prolog dan ook weer herkend als variable en daarmee werkt.
2:
Blokjes kunnen oppakken met verschillende orientaties van de gripper. In dit
project is er maar met een orientatie van de gripper gewerkt, wat als gevolg
had dat blokjes in de x richting niet tegen elkaar aangezet konden worden omdat
de gripper in de weg zat. Als de gripper op verschillende manieren een blokje
kan vast pakken moet het wel mogelijk zijn om in alle richtingen blokjes tegen
elkaar aan te zetten, tot op zekere hoogte. Hierin moet ook weer een stuk
redeneren zitten, wanneer je op welke manier een blokje moet vastpakken.
3: Het
werken met verschillende vormen van blokken. Hierbij komt zowel het probleem
van hoe je verschillende blokjes moet vastpakken kijken, als ook dat je niet
zomaar alle blokjes op elkaar kan zetten.
Literatuurlijst
[1] Russel. S., Norvig.
P., 2003, 2de druk,
De BronCode. Het prolog deel staat in blockworld. De main van de java code staat in BlockWorld.java
Verder is er gebruik gemaakt van de tio.jar. voor het lezen van bestanden.
De robotJoints worden aangestuurd met code aangeleverd door de UvA JointCode.