Kara

Kara provides an introduction to programming through finite state machines. Kara's world is a grid of squares on which a small range of objects may be placed while Kara him/herself is a ladybug that moves around the grid and acts on the program's instructions. The program does not include commands in the sense of a high level language such as C or Pascal but rather a series of instructions based on the inputs from the grid and the next state in the program.

Kara's world consists of a grid of squares with a small number of objects that can be placed in them. Kara reacts to the objects in the squares and can be programmed to take a variety of actions. Apart from Kara the world may include tree stumps, toadstools and leaves. The actions that Kara can take are: picking up a leaf, dropping a leaf, moving forward one square and turning either left or right.

When Kara is programmed the programmer can choose one or more states from a list of five supplied. To add a condition from the 'sensor library' the programmer simply double-clicks on the condition or drags it into the Used Sensor window:

The program then evaluates the combinations of conditions dragged into the Used sensors window.

When running the example programs the documentation provides trial environments and finished code:

Click on the 'Show program' bar to load the code into the 'Programming Kara' window.

Examples

1. Kara and the Clover Leaves

The simplest finite state machine is one that calls only itself. One of the first exercises provided is called 'Kara and the Cloverleaves' and features just one state in an endless loop. The possible actions in the 'walk' state are based on the conditions of Kara either coming face to face with a tree stump or Kara having a tree stump on his right side.

The 'code' is as follows:

This shows two states for the 'machine', walk and stop. The states in the machine are shown by the circles 'walk' and 'stop' while the arrows between them show the possible paths that the 'program' can take. In this case the path is either to loop back to 'walk' or to move to the 'stop' state.

The conditions defined in setup for this model are based on the idea that Kara can sense the objects in the world around him. The first condition shown in the diagram above is that Kara is facing a tree and the second is that Kara is over a leaf. The conditions that Kara evaluates are as follows:

1. Neither condition applies: Kara drops a leaf, moves forward one square and remains in state 'walk'
2. Facing tree is false, over a leaf is true: Kara picks up the leaf, moves forward one and stays in state 'walk'
3. Facing tree is true, Leaf underneath is false: Kara stops
4. Facing tree is true, Leaf underneath is true: Kara stops

The solution includes three environments labelled Clover leaf trail 1, 2 and 3. Environment 3 is the simplest:

Kara is facing the tree and there is no leaf in the square so condition 3 applies: Kara drops a leaf and stops.

The second environment is slightly more complex and allows Kara to perform both leaf-dropping and leaf-collecting actions before stopping at the tree stump:

2. Kara the Tunnel Seeker

In this example Kara is programmed to find a 'tunnel' between trees and to stop when there is tree on both left and right sides.

Here we can see that the conditions included are a tree stump to the left and a tree stump to the right. The four conditions are:

1. Stump to right is false and stump to left is false: Kara moves forward and returns to state 'entry'
2. Stump to right is false, stump to left is true: Kara moves forward and returns to state 'entry'
3. Stump to right is true, stump to left is false: Kara moves forward and returns to state 'entry'
4. Stump to right is true, stump to left is true: Kara enters state 'stop'

Once again there are three environments provided, though in this case they differ only in Kara's starting position.

Notice how the conditions in this example follow the AND truth table:

Remember that 0 is false or 'no' while 1 is true or 'yes'. When there is a tree stump to the left AND to the right Kara stops.

3. Tunnel Seeker 2

In this example there are three states, entry, exit and stop. The first state entry is defined as follows:

The same evaluation and truth table apply as before but this time the yes-yes situation leads to the 'exit' state.

The exit state is defined as follows:

So long as there is a tree on both sides Kara keeps moving forward and stops as soon as this condition is not true, when there is only one tree or none.

Notice that it is not possible to reach 'stop' from 'entry', only from 'exit'.

3. Searching For Clover Leaves in the Forest

In this example Kara has been programmed to find a clover leaf and will only stop when she finds it.

The single state 'search' evaluates three conditions and takes action depending on the sensor inputs, which are a tree stump in front and a clover leaf underneath.

1. No tree stump ahead and no clover leaf underneath: move forward, stay in state 'search'
2. Tree stump ahead but no leaf underneath: turn left, move forward, turn right, move forward, move forward, turn right, move forward, turn left
3. Tree stump ahead or not, if there is a leaf underneath pick it up and move to state 'stop'

The truth table for this is:

Here is the environment provided:

The program will fail if one of the pair of forward movements is removed because Kara will now run into a tree but have no way of turning away. Try this and see if you can find a way to make Kara continue until she finds the leaf.

Writing Your Own Examples

Single Condition Situations

We start with an empty program area by clicking on the New button.

We start with an empty environment or world by doing the same in the run-time area:

The default grid is 9x9 and though bigger grids are possible this should be enough for now. Use the Size button to set the dimensions of Kara's world.

If we think in terms of truth tables we would like to begin with a program that has just one input. The condition could be that Kara stops when she meets a tree:

The truth table is as follows:

The code:

The finite state machine has two conditions, S1 and stop. So long as Kara does not meet a tree stump she continues to move forward. When a tree stump is met Kara stops.

You should be able to think up a number of single state situations for Kara.

Two State Situations

We have met a number of these in the examples, now it is time to create your own.

Back