The file qulog/examples/towers/twoArmCoopTowerBuildersMod1.qlg contains a tower buider that has two “home tables” where the towers are to be built with each task having a home table and with a shared table that sits between the two home tables. There are two arms with each associated with a home table and where each arm can reach both its home table and the shared table.
Now we have an additional problem we need to avoid and that is the two arms conflicting on the shared table. We avoid this by making both the tables and the arms as resources with the following type declaration.
If the user does not declare this type then the system uses a default declaration that is equivalent to the user making the declaration
Typically the atomic procedures will take one or more resources as arguments as in the following declaration.
In any case, if resources have been declared the TeleoR compiler looks at all possible call stacks of atomic procedures and determines the set of resources that might be used. If the atomic procedures have resource arguments they will be variables in the program and so the actual resources that are required are determined at runtime.
If a task needs to move a needed block from the other home table to a tower on its home table then it will first require the other arm, the other table and the shared table as resources and then the home arm, home table and the shared table.
On the other hand if the task only needs to move a block locally then it only needs the home arm and the home table leaving a task to build a tower on the other table using its home arm. We therefore get tasks running in parallel when they have non-overlapping resource needs.
We can further improve parallelism if we consider the case where one task is moving a block from the shared table to table2 using resources arm2, shared, table2 and another task wants to move arm1 to the shared table. As soon as the first task starts moving towards table2 - i.e. tracking(arm2) becomes true then the second task can safely use the shared table. We can accomplish this by defining the system declared, user defined relation overlapping_resources as follows
If the user does not define this relation the system uses a default definition that is the same as if the user had made the following definition.
The evaluator uses this relation to determine if resources overlap and, if not, allows the tasks to run in parallel.
In the above we define overlapping_resources purely to improve paralellism. In qulog/examples/towers/twoArmSlotTowerBuilders.qlg, however, we can't use the default definition because each running task requires access to a range of slots and so overlapping resources is not based on equality but on intersection.
These programs use the system declared, user defined hook for accessing resources. In this case we have
This is so that our simulator can colour the arms and tables with the task colours to visualize which tasks are using the resources. Typically this will want to access the relations that retrieve the current active and waiting resources as above. This hook is called by the evaluator each time it has completed its task re-evaluations.
It's up to the programmer to decide how to use this. For example, another process might be used to monitor task resource use over time.
Because this program sometimes requires transferring blocks across tables using both arms and because we wanted to increase efficiency by having tasks cooperate more when moving unwanted blocks we have made several modifications to the basic structure of the one arm tower builder.
The first modification is using the procedure coop_move to move unwanted blocks. Sometimes such a block is (eventually) needed by another task and so this task can help the other task by, for example, moving the block to the shared table so that the other task then only needs to do a single move.
The second modifications arises because of the more complex move sequences - instead of using an iterative unpile we have moved unpiling rules into makeTower and made them iterative.
The makeTower procedure is given below. Note that we have used commit_while in the rules involving coop_move rather than or_while as in unpile in the previous program. This is because we want each of these rules to commit to completing a cooperative move. As discussed in the next section there are some cases where the cooperative move is not completed by the task. We therefore also present two more variants of this program that avoid the problem.
This iterative approach turns out to simplify the overall code quite a bit but a consequence is that it does not exactly follow standard regression. For example, when the third rule fires the action does not necessarily lead directly to the guard of the first or second rule becoming true. Instead it might refire and remove another block. Eventually, however, by repeated use of this rule an earlier guard will become true (unless the environment interferes). This is a simple but useful extension of the regression property.
The problem with the above program (as discussed in the next section) is to do with a case when a recursive call on makeTower is made. That case is when Blocks is not a stack (but its tail is). This case also arises in the original Nilsson program but it's not an issue there because it isn't multi-tasking.
In the program
qulog/examples/towers/twoArmCoopTowerBuildersMod2.qlg
we make the recursive call only when the tail of Blocks is not a stack (or tower) and so we do not “return from recursion” until Blocks is a tower. This fixes the problem.
Another solution is to make makeTower iterative as well. We do this in
qulog/examples/towers/iterTowerBuilder.qlg
and
qulog/examples/towers/iterTwoArmCoopTowerBuilders.qlg
The downside of this approach is that we move even further away from standard regression and so we extend the idea of regression in a similar way to a standard approach used to prove program termination. We define an integer valued “regression cost function” on the state that is bounded below (typically by the value for the goal state) and where the action of each rule strictly decreases this function. These programs contains comments describing the function and how each action reduces this function.
