Practicum: De Wolf, de Geit en de Kool

Een man heeft een wolf, een geit en een kool. Hij moet een rivier oversteken met de twee dieren en de kool. Er is een kleine roeiboot waarin hij slechts één ding tegelijk kan meenemen. Echter, als de wolf en de geit alleen gelaten worden, eet de wolf de geit op. Als de geit en de kool alleen gelaten worden, eet de geit de kool op. Hoe kan de man de rivier oversteken met de twee dieren en de kool zonder dat er ongelukken gebeuren?

Los deze puzzel op door er een Uppaal-model voor te maken en Uppaal de oplossing te laten uitrekenen. Vervolgens kun je testen of je oplossing werkt bij de interactieve versie van het spel op Plastelina.

Hint: Maak aparte automaten voor de man, de wolf, de geit en de kool. Er zijn diverse manieren om het probleem te modeleren. Een manier is om gebruik te maken van de volgende declaraties:


int v;

chan heen,weer,verscheurhier,verscheurdaar,knabbelhier,knabbeldaar;

chan priority default < verscheurhier,verscheurdaar,knabbelhier,knabbeldaar;

Met variabele v kun je bijhouden aan welke kant van de rivier de veerman is: als de waarde 0 is dan is de veerman hier en als de waarde 1 is dan is hij daar. Wanneer de man en de wolf samen oversteken van hier naar daar, dan laat je de man een transitie heen! doen en tegelijk de wolf een transitie heen?. Op dezelfde manier modelleer je het oversteken van de man samen met geit of kool. Een heen!-transitie van de man kan alleen plaatsvinden als er tegelijk een heen?-transitie gedaan wordt door wolf, geit of kool. Zo kun je ervoor zorgen dat de man precies één ding kan meenemen. Je hebt aparte transities nodig om te beschrijven dat de man ook alleen kan oversteken. Het kanaal weer gebruik je om de man weer terug de rivier te laten oversteken samen met de wolf, geit of kool. Wanneer de wolf de geit verslindt aan deze kant van de rivier gebruik je daarvoor kanaal verscheurhier, en als het drama zich aan de andere kant van de rivier afspeelt dan gebruik je kanaal verscheurdaar. Op vergelijkbare manier synchroniseren geit en kool met knabbelhier en knabbeldaar. In de laatste regel van de declaraties wordt aangegeven dat de verscheur- en knabbelacties prioriteit hebben boven alle andere acties: als de wolf of de geit hun buikje kunnen voleten dan zullen ze dat altijd direct doen.

Het onderstaande diagram geeft de architectuur van het model weer:

Bonusopdracht

Probeer nog een andere rivier-oversteek-puzzel op te lossen met Uppaal, bijvoorbeeld het probleem van de jaloerse echtgenoten of het gerelateerde probleem van de missionarissen en de kannibalen. In de Uppaal demo directory zit een model bridge.xml dat je wellicht helpt om het familiecrisisprobleem op te lossen.