Friday, December 5, 2003

Cat & Mouse Project Report

See also: Cat & Mouse Software

The “cat and mouse maze” problem is a matter of controlling the behaviour of a cat and mouse in a maze, only by opening and closing various doors in the maze. New software for the purpose of modeling variants of the problem is discussed. The new software is extremely user friendly and automated. It also makes use of some related existing programs. The package is shown to successfully model the classic cat and mouse problem, and extends to arbitrary mazes with doors that may or may not be controllable, observable, unidirectional or restricted to a particular animal.

I have developed several software modules (in Visual Basic 6.0 and Visual C++) and interfaced them with some existing software tools (namely CTCT and GraphViz) for the purpose of providing a complete package for the design, simulation and analysis of variants on the classic cat and mouse problem.

Main Simulation Interface

The main simulation interface is a program I developed in Visual Basic 6.0. It is intended as the control center for all modules. In a complete version of this package, all desirable actions would be made through this interface. Currently each application stands alone.

Simulation Interface

The blank area in the centre of the window is the drawing palette. The user can select a brush from the top left and draw in the palette. Walls are drawn as black lines and are forced to an orthogonal grid. Doors are drawn as thick white lines and are likewise forced to a grid. Doors are also forced to a fixed size. The cat and mouse icons are unique, so after initial creation, these brushes only serve to reposition the icons. The cat and mouse icons are also forced to a grid, such that they lie in the centre of the smallest drawable squares.

A Simple Maze

Once created, walls and doors can be easily edited. The only edit option given to the walls is deletion. This is achieved by right-clicking near the wall and selecting the popup delete option. The user is not prevented from drawing walls or doors on top of each other. In such cases, the doors are always displayed on top and nearby right-clicks give preference to doors.

Delete A Wall

Doors are more important and have more options. Doors can be specified as unidirectional, bidirectional, for a specific animal, for both animals, as controllable or uncontrollable, and as observable or unobservable. Their properties are displayed in a popup when the cursor hovers over them. The properties are editable via a popup menu reachable by right-click.

View Door Properties

The maze displayed is the classic configuration. Each door has been given the appropriate properties although this is not obvious without hovering over each to read it’s parameter list. An improvement on the GUI could alter the size, colour or shape of the doors based on their properties.

Edit Door Properties

At any point the user can save their maze. The data structures are dumped to a text file specified via the standard “Save As” dialogue box. The user can also load a saved maze via a similar “Open” dialogue box. This process trashes the current maze and replaces it with the structure specified in the input file.

The compile feature is currently the only link between the main interface and the other modules. It processes the maze and dumps data to various files; these include, an input file for the animation program, input files for CTCT that represent the FSM for the mouse’s behaviour and the FSM for the cat’s behaviour, and input files for GraphViz that represent the FSM for the mouse’s behaviour, the FSM for the cat’s behaviour and the FSM for their combined behaviour. The last is achieved by a shuffle algorithm that I wrote. This algorithm is not general and requires some of the constraints inherent to the cat and mouse problem.

Animation Interface

The Animation Interface is written in C++ and implements OpenGL for graphics. This application is an extension of maze game I developed for use in a previous project.

Animation Interface

The animation interface requires an input file as a command line argument. The input file specifies the geometry of the maze and the locations of the cat and mouse. The cat is displayed as a blue wire-frame rotating sphere. The mouse is displayed as a red wire-frame rotating cube. Movement routines have been written which allow the user to click on the cat icon and drag it through the maze. It will not pass through walls, but disregards the door rules (ie: it will pass through mouse doors, etc.).

Further development of this package would fully interface it with the main simulation application. This would be called as a popup window and would animate a specified sequence. For example if the user were interested in a string such as “αβγδ” which might represent “cat moves to room 0, mouse moves to room 3, cat moves to room 1, mouse moves to room 0” then they could use this module to view an automatic animation of the events.

GraphViz Output

In analysis of variants of the cat and mouse problem, the user will require FSM models of the various parts. The main simulation package was designed to represent a cat and a mouse in an arbitrary maze with arbitrary doors varying in controllability, observability, direction, and animal. The compile feature of the simulation program creates three dump files for GraphViz input. Each faithfully represents states and transitions, but do not contain information about controllability of observability. Furthermore, the do now identify the start state. Fortunately in these FSMs there is only one marked state and it is always the start state, so this information is implicit. Nevertheless, several improvements could be made to this component.

Mouse Behaviour

Mouse Behaviour

The FSM representing mouse behaviour was generated almost automatically. Once a maze has been specified and compiled, all that is necessary is to open the auto-generated GraphViz “.dot” file and convert it to a gif. This process requires only a few mouse click and could easily be fully automated.

It is important to note, that the properties on the doors are adhered to, meaning that if the mouse started in a room that had all one-way doors pointing in, then the result would be a single state with no transitions. Another important note is the room numbers. These are automatically generated by the simulation program and do not correlate to the number given in the classic problem. Once a maze has been compiled, hovering over the doors shows the door number as well as the other properties. Before compiling, this property does not appear because no numbers have yet been assigned. Again advancement in the GUI could be made by showing the numbers nearby, all the time, and displaying room numbers as well.

An example event sequence of mouse behaviour is given by events [Door_2, Door_5, Door_12]. Visualizing the occurrence is best achieved by the animation interface, but I will give a description in words. The mouse moves from room #3, up through door #2, into room #1, then down through door #5, into room #4, then left through door #12, back into room #3.

Mouse Movement

Cat Behaviour

The FSM representing cat behaviour was also automatically generated by the simulation system and various other models for arbitrary mazes can be easily produced. Unfortunately, the GraphViz tools do not allowing editing of the graphic output; however, the project is open source and there is great potential for future development

FSM of Combined Behaviour

The simulation system also generates the shuffle of the two animals, thereby displaying all possible maze behaiour. The result has 25 states and 70 transitions.

States are labeled by which room the cat and mouse are in, and transitions are labeled by which animal goes through which door. Hence state c_R_3_m_R_5 reads “the cat is in room three and the mouse is in room 5”, and transition c_Door_3 reads “the cat goes through door three”. Using this model, it would be straight forward to write a translation module that automatically describes any input sequence in simple English.

Interaction With CTCT

The simulation system also creates input files for use with CTCT. “.ads” representations of the FSMs for the individual movement of the cat and mouse are automatically generated. It is then easy to perform CTCT functions on the model. MAZE = Mutex(CAT,MOUSE,[]) for example generates the shuffle as previously displayed in the GraphViz output.

Unfortunately, CTCT does not preserve naming relationships in the output, so translation from CTCT to GrahpViz is not as useful as it might be. Nevertheless, careful examination of CTCT output of MAZE finds it identical to the previous FSM displayed via GraphViz.

des
{ "loggedin": false, "owner": false, "avatar": "", "render": "nothing", "trackingID": "UA-36983794-1", "description": "", "page": { "blogIds": [ 235 ] }, "domain": "holtstrom.com", "base": "\/michael", "url": "https:\/\/holtstrom.com\/michael\/", "frameworkFiles": "https:\/\/holtstrom.com\/michael\/_framework\/_files.4\/", "commonFiles": "https:\/\/holtstrom.com\/michael\/_common\/_files.3\/", "mediaFiles": "https:\/\/holtstrom.com\/michael\/media\/_files.3\/", "tmdbUrl": "http:\/\/www.themoviedb.org\/", "tmdbPoster": "http:\/\/image.tmdb.org\/t\/p\/w342" }