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, New Jersey, Prentice Hall, Artificial Intelligence A Modern Approach, pag 414.

 

Het Labboek.

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.