Assignment 3 (kiltera)

Deadline: Friday 16th of April

Question 1: simplified robots

The goal of this question is to develop minimal model of a a simplified robot that moves over the real plane while being directed by a controller.

At any point in time, the robot has a position (x,y), but this can change, as the robot can move around. However this is not an autonomous robot. It receives commands from the outside. It can receive four commands:

where d is some positive real number.

Let us assume that the robot moves at a constant speed of v meters per second. Then moving on a straight line by d meters will take the robot d/v seconds. While the robot is moving, it does not accept commands.

A controller is a process that interacts with the robot and tells it what to do by sending commands to it.

Let us assume that the robot starts at position (0.0, 0.0), its constant speed is 1 meter per second, and that we have a fixed controller has the following behaviour:

  1. wait 10 seconds
  2. tell the robot to move north 3 meters
  3. wait 10 seconds
  4. tell the robot to move east 7 meters
  5. wait 5 seconds
  6. tell the robot to move north 2 meter
  7. wait 5 seconds
  8. tell the robot to move west 4 meters
  9. wait 25 seconds
  10. tell the robot to move south 3 meters

Write a kiltera model representing the robot and the controller described above. Submit both the kiltera code (in a file robot1.klt and a text file trace1.txt containing the trace or the simulation (in tabular format; invoke the simulator as klt -et -f trace1.txt robot1.klt).

To know where the robot is at any point while you run the simulation, you can use a print statement as follows

print (x,y)

where (x,y) is the pair representing the current state of the robot (i.e. its position).

Question 2: robot exploration

Now we extend our robots model. Suppose that the robot is exploring Mars in search for interesting features like signs of water or life, or special geological formations. As before, the controller tells the robot where to go, but now, once the robot arrives, it looks around for interesting objects or features. If it sees something interesting, it sends back that information to the controller, which records all data submitted by the robot.

In order to model this, we create an abstraction of the world where the robot is. This abstraction is a process World which contains a collection of objects located at different positions, and expects queries from other processes. These queries ask the world to give a list of all objects located within a certain distance d of a position (x,y). Hence a query to the world must provide a triple (position, distance, answer), where position is some pair (x,y), distance is a number, and answer is the channel where the response will be sent. The following is the (partially completed) model for the World process, initialized with some selection of objects. 

process World[query]:

  process AnswerQueries[]:
    ...
  
  process Initialize[]:
    let object_list = [((2,6),"purple rock"), \
                       ((8,4),"water"), \
                       ((5,8),"martian"), \
                       ((3,6),"green rock")]
    in
      let dummy = initialize_world_database(object_list) 
      in
        done

  in
    seq
      Initialize[]
      AnswerQueries[]
This model of the world uses external Python code to encode a database of objects in their respective positions. Such Python code is implemented in world_database.py. It provides two functions used by this model: initialize_world_database and query_world_database. The first one adds all objects to the world database, and the second one expects two parameters, a position and a distance, and returns a list of all objects within the given distance of the given position.

Your task is to write a model of the robot and the controller such that when the robot reaches its current destination, it queries the world for objects in its current position and within a distance d representing how far away the robot can see. The robot must then forward whatever information was found to the controller, which records it. Furthermore, you must complete the AnswerQueries subprocess of the World so that whenever asked, it answers with a list of objects within a given distance of a given location (by querying the external world database). Naturally, it must be able to answer more than just once.

In order for the controller to record information, it must use an exteral Python module controller_database.py, which provides two functions: add_data_controller_database and print_contents_controller_database. The first one has a single parameter which is the data returned by the world, and should be invoked whenever the controller receives new data from the robot. The second one should be invoked at the end, when the controller has finished sending all commands, and the robot has completed them.

Write a kiltera model representing the robot and the controller described above. Submit both the kiltera code (in a file robot2.klt and a text file trace2.txt containing the trace or the simulation (in tabular format; invoke the simulator as klt -et -f trace2.txt robot2.klt).

Notes on kiltera

Downloading and installing

You can obtain the kiltera simulator from http://www.kiltera.org. You'll find links to the prerequisites and installation instructions there.

Basically you'll need three things, which you should install in order:

  1. Python 2.5 or 2.6 (don't install Python 3.0, as there are some compatibilitiy issues): http://www.python.org
  2. aperiot 0.1.7 (available in kiltera's website http://www.kiltera.org)
  3. kiltera 1.0b11 (available in kiltera's website http://www.kiltera.org)

Note that you must have administrative access to install them. On Linux-like systems this means that you should run the installation scripts using sudo, for example: 

tar zxvf aperiot-0.1.7.tar.gz
cd aperiot-0.1.7
sudo python setup.py install
cd ..
and 
tar zxvf kiltera-1.0b9.tar.gz
cd kiltera-1.0b9
sudo python setup.py install
cd ..

The command for the simulator is 

klt [flags] mymodel.klt
However, on Windows you might have to run it as 
python C:\Python25\Scripts\klt [flags] mymodel.klt
where C:\Python25 is the directory there you installed Python.

A syntax highlighting mode is available for the gedit editor. This editor is standard with GNOME based Linux distributions such as Ubuntu, but it is available for other platforms as well (including Windows and Mac OS/X). The required files are klt.lang and klt.xml.

To install these files under Linux:

For a Windows distribution, you can copy klt.lang to the gtksourceview-2.0 subdirectory of the folder where you installed gedit (typically under C:\Program Files\gedit\share\gtksourceview-2.0\language-specs)

On gedit, syntax highlighting will be automatically activated when you save the a file with a .klt extension, or if you select the menu option View -> Highlighting mode -> Others -> kiltera.

Comments

Be sure to comment your code: document what processes represent and do, as well as their interfaces (ports/events).

Comments in kiltera code begin with # and end with the end of line.

Relevant kiltera features needed to solve this assignment

You'll need the following features:

You will not need

An example

The kiltera model banking.klt provides a useful example of the modelling style in kiltera, and most of the basic features in the language.

Comments about the syntax

kiltera's syntax is indentation sensitive, hence 

when a ->
    P
is not the same as 
when a ->
P
In fact the last one will yield a syntax error.

If the when construct has more than one alternative, then the first event must be listed in the line after the one, not the same line: 

when
  a ->
    P
| b ->
    Q
is correct, while 
when a ->
    P
| b ->
    Q
is incorrect.

The continuation of a when (e.g. P or Q in the previous example) must be indented in the line after the arrow ->.

The trigger, wait, schedule and print constructs allow the continuation to be on the same column (not indented) if there is no arrow. For example: 

  wait t
  trigger x
  print y
  done
is equivalent to 
  wait t ->
    trigger x ->
      print y ->
        done
Furthermore, if the continuation is done, it can be replaced by a period: 
  trigger x
  done
is the same as 
  trigger x.

Process definitions

A process definitions has the form: 

process A[x1,x2,...,xn]:
  body
in
  term
where A is the name, each xi is a port to be linked to some event/channel from the outside, body is a process term, describing the behaviour of any instance of A in term, which is some other term that can instantiate (i.e. invoke) A.

To create an instance of A in term you use the syntax 

A[u1,u2,...,un]
where each ui is an event or channel which becomes linked to the corresponding port xi.

Note that a process can be recursive, this is it can invoke itself. This is useful to model loops.

You can define several process definitions valid within the same scope: 

process A[x1,x2,...,xn]:
  body1
process B[x1,x2,...,xm]:
  body2
in
  term
Furthermore, you can have process definitions inside process definitions: 
process A[x]:
  process B[y]:
    ...x...y...
  process C[x]:
    ...x...
  in
    ...
    B[z]
    ...
    C[u]
    ...

Nested definitions have lexical scoping, so they can directly refer to event/channel names in their enclosing scope (e.g. B can refer to the x in its enclosing scope A).

Using nested definitions is recommended to yield cleaner designs. Typically nested definitions can bu used to represent either subcomponents of a process, or to represent modes of operation within a process.

Keeping track of state variables

The simplest way to represent state variables of a process is by giving the corresponding process definition additional parameters, declared after its ports: 

process A[x1,x2,...,xn](v1,v2,...,vm):
  ...

Here, the additional parameters (v1,v2,...,vm) represent the state variables. This variables must be given values whenever the process is invoked, hence, using recursion with new values is the most natural way to update these variables: 

process A[x1,x2,...,xn](v1,v2,...,vm):
  ...
  A[x1,x2,...,xn](new_v1,new_v2,...,new_vm)
  ...

Importing Python modules

In order to access the external Python code, your kiltera code must begin with the following lines: 

module Robots:

python world_database, controller_database
and the files world_database.py and controller_database.py must be saved in the same directory as your kiltera source file.

Calling Python functions

In kiltera, external Python functions can be invoked only within expressions, and not as independent statements. Hence, the most common way of calling such functions looks like this: 

    let return_value = some_python_function(arguments)
    in
        ...use return_value ...
In the case where the Python function does not return anything, from the point of view of kiltera a null value is returned, and therefore the "let" is still necessary. In such case, the return_value variable is a dummy variable which is not used afterwards.


Author: Ernesto Posse
Last modified: Wed Nov 4 11:02:47 EDT 2009