Thinking about TeleoR programming

When thinking about writing a TeleoR procedure the first step is to divide states up into sets distinguished by some properties. The next step is to order these states from the most desirable to the least desirable with the most desirable being the goal of the TeleoR procedure. Then for each set of states (other than the first) we determine an action that, under normal conditions, will achieve a state that is more desirable. This is the regression property.

This action might be a collection of primitive actions but when the situation is more complex it might be another TeleoR procedure whose goal is the more desirable state.

In doing this initial design, based on available percepts and primitive robotic actions, some rethinking of what constitutes the sets of interesting states might make designing the TeleoR procedure simpler. This might mean changing what constitutes the percepts and maybe even the robotic actions.

As a running example lets consider a simple block stacking problem similar to earlier examples.

We have a table that contains a collection of numbered blocks some of which might be on the table and some might be stacked on other blocks. We have an arm that has three robotic actions: pickup(Block) that will pick up Block provided it is uncovered, put_on_block(Block) that puts the held block on Block provided it is uncovered, and put_on_table() that puts the held block on the table. We will assume the arm will do nothing if called when the action conditions are not satisfied - e.g. no block is being held or the required block is covered.

Our task is to build a tower [1,2,3] where 1, 2 and 3 are the block numbers. 3 needs to be on the table, 2 on 3 and 1 on 2 (and nothing on 1). We assume percepts on(Block1, Block2), onTable(Block) and holding(Block).

Now lets consider dividing states up into sets with properties related to our problem. So the most desirable set of states is the one that has the property tower([1,2,3]) where we can define the property (relation) in terms of the percepts on and onTable. Note that we don't care where on the table this tower is or where any other blocks are - the tower property only cares about the arrangement of these 3 blocks.

A slightly less desirable state would be tower([2,3]) & holding(1). Applying the action put_on_block(2) will normally achieve the most desirable state (in which tower([1,2,3]) is true).

A slightly less desirable state than this would be tower([2,3]) & clear(1) where clear(1) means 1 is uncovered. The action pickup(1) will normally achieve the state above.

Note that we say "normally". By this we mean that the environment does not itself modify the state.

For example say tower([2,3]) & clear(1) is true and we invoke the action pickup(1) but before the arm reaches block 1 the environment puts another block on top of 1. In this case the action will do nothing and we won't achieve a more desirable state.

Even less desirable states consist of variations where needed blocks are covered.

Now lets consider a first attempt at a makeTower TeleoR procedure. For moving a block from one place to another we can think of solving this by having two rules in the top-level TeleoR procedure - one whose action picks up the block and the other whose action is to put the block down. Since we will need to do this in several scenarios it might be better to hand off the problem to a sub-procedure as we have done below.

where

• relation block_needed_for_tower(Block, TopBlock, Blocks) is true if there is an uncovered partial tower of Blocks with TopBlock the top block of the partial tower and Block is the next block needed to extend the tower.
• partial_tower_covered_by(Blocks, Block) is true if a partial (or full) tower is covered by blocks and Block is the top covering block
• top_block_above(Block, TopBlock) is true if TopBlock is the top block above Block
• tower_base(Blocks, Block) is true if Block is the last element of Blocks

The auxliary TeleoR procedure are then

To determine if these TeleoR procedure will solve the problem we first consider if the tower will correctly be built from any initial state in the absence of interference from the environement.

Consider a very simple case: there is only one block needed to complete the tower and it's clear. In this case rule 2 of makeTower fires causing rule 3 of move_block_to_block to fire and the block will be picked up. As soon as its picked up the guard of rule 2 of makeTower becomes false and no other guard is true. There are a few ideas we might consider to solve this problem:

1. Don't use auxilary predicates and inline the rules for move_block_to_block in makeTower
2. Inject a new second rule to deal with this situation
3. Change the guard to a disjunct
4. Use an or_while in the guard.

1. will work but has the disadvantage of miminizing code reuse and is going against a design principle that suggests breaking down a problem into a subproblem and solving that - i.e. writing a sub-procedure

For 2. we would need a rule like

We might also need to follow this with a rule like to deal with unwanted blocks being held.

This is not completely satisfactory as it adds complexity and reduces efficiency as there will be more reevaluating of guards.

The third idea looks promising. Lets say we also have a relation
clear_or_holding(Block) and change the rule to

In this case this disjunction works quite well but in more complex cases it can be difficult to produce a suitable disjunction that has a reasonable intuition.

The last idea is to use the or_while construct as below.

The semantics of the or_while is that when this rule is fired (because the guard is true but no earlier guard is true) then this rule will continue to be the active rule provided no earlier guard is true and or_while is true with the same binding of variables as when the rule was (re)fired.

In this case as soon as we pick Block up clear(Block) is no longer true but holding(Block) is and so this rule continues as the active rule.

We argue that the use of or_while is simpler and more intuitive than using a disjunction.

Now lets reconsider this modified TeleoR procedure:

Provided the environment does not intefere with the execution of this procedure will the goal be achieved gived an arbitrary initial state?

First note that this procedure does not satisfy the regression property as stated earlier. In an initial state where some or all needed blocks are covered we will find we will typically repeatedly fire rule 3 to remove blocks above a needed block then, once it becomes clear, fire rule 2 and then fire rule 3 again.

However this procedure does satisfy a more sophisticated regression property in that the action associated with any fired rule will normally achieve a state that is "closer" to the desired goal state as discussed earlier.

For this discussion, we informally argue that the goal of the procedure will eventually be achieved as long as the environment does not interfere. One very undesirable state is one in which the base of the tower is not on the table and is covered by blocks. In this case the last rule fires removing a block above the tower base block. This achieves a slightly more desirable state. Repeated use of this rule will eventually give us a state in which the tower base block is clear and so the second last rule will fire moving this block to the table again producing a more desirable state. Now, as discussed above, we will typically oscillate between rules 2 and 3 with each application improving the state either by building more of the tower or by removing blocks covering needed blocks. Eventually we will fire rule 2 to move the last block on to the tower, achieving the goal (rule 1 fires).

Above we did not discuss the need for rule 4. This rule is needed when the initial state has a covered (partial) tower. Once these covering blocks are removed this rule would not normally fire again.

The other concept we should check is completness. Recall that a TeleoR procedure is complete if, for any state, some rule is true. For top-level TeleoR procedure this is a very important property as without it we get undefined behaviour. In the implementation of teleor we raise an exception in this case. For sub-procedures like the one above we talk about completeness relative to the calling context. Typically sub-procedures are only called for states that satisfy some property and so we can assume that property to be true when deciding on the completeness of sub-procedures.

With a bit of thought we see that these procedures are complete.

So completeness tells us that some rule will fire for any given state and the regression property tells we will normally make progress towards the goal. This in turns tells us that, without inteference, we will achieve the goal from any initial state.

What about when the environment itself changes the state? This could happen in two ways:

1. The environment could help, for example, by putting a needed block on the tower; or
2. The environment could hinder, for example, by shuffling around the blocks in a partially built tower.

The beauty of TeleoR programming is that it (mostly) naturally deals with both cases. For 1. the environment has itself produced a more desirable state and the TeleoR procedure will flip to firing a rule that takes advantage of this state. For 2, the environment produces a less desirable state but the TeleoR procedure will flip to firing a rule to cope with this less desirable state.

So this block building robot will efficiently cope with inteference by the environment.

Later we discuss a situation where, without more careful thought in the design of TeleoR rules, we can get inefficiency or even wrong behaviour when the environment interferes.

We now discuss when commit_while might be useful to consider. The above example does not need to use commit_while so we now introduce another very simple example, similar to an eariler one, where commit_while is useful.

We have a bottle collector robot, part of whose job is to get next to a bottle so it can pick it up and take it to a depot. For this example we consider just the get_next_to_bottle TeleoR procedure. For this procedure the only percept required is see_bottle(Distance, Direction) where distance is far, near and close and the direction is left, right, centre_left, centre_right, dead_centre. At any time there will be at most one see_bottle belief - being a belief about the closest bottle. The primitive actions are to move forward at a given speed and to turn in a direction at a given speed with the turn speed being zero when the direction is a centre direction. If both actions are active the robot moves is a curved path.

As a first pass consider

where is_centered(Direction) is true if Direction is
centre_left, centre_right or dead_centre

The idea is when the robot is a long way from the bottle it can afford to move fast without loosing sight of the bottle but it slows down as it gets closer.

Note that the last rule is required for completeness. Now lets consider regression. What happens if there is no bottle on the table? In this case the last rule will fire and we won't make any progress. So we have to relax the idea of regression and say provided there is at least one bottle on the table then normally eventually we will achieve the goal.

This procedure is both complete and satisfies the simple regression property, well almost. Take the sceanrio when the robot does not see a bottle on the table (but there is one). In this case the last rule fires and starts turning. Eventually it will see a bottle on the left and rule 6 will fire and will start moving (and continue turning). Now rule 5 will fire as soon as we move from seeing the bottle on the left to seeing a bottle centre_left and it will stop turning but continue moving. Note that because we flip rules exactly when we cross the boundry from left to centre_left then, even if the robot tracks perfectly without any wheel slipage, we will shortly get the percept that we see the bottle on the left rather than centre_left and we will flip back to tuning. Shortly after that we will get the percept that we see the bottle centre_left. This will lead to a rapid fluttering of the robot. This is not desirable.

What we would like to do is once we start turning to centre we should commit to turning until we see the bottle dead centre. We can think of this as over achieving an earlier guard. This is where commit_while comes in. Consider the following variant using commit_while.

The semantics of commit_while is that, once the rule is fired, we commit to the action of this rule while the commit_while test is true. This means it prevents the firing of any other rule in this procedure while the commit_while test is true. So, in the above scenario, when rule 6 fires we commit to the actions until we see the bottle dead centre. This avoid the fluttering discussed above.

So, without inteference, adding the commit_while improves the efficiency of the program. However, given the dramatic effect commit_while has on rule firing we have to be careful about environment inteference in the presence of commit_while. For example, consider the situation where rule 4 fires and after it fires the environment removes the bottle. The robot will continue moving and turning. Similarly, if the bottle is moved to the other side (e.g. moved from being seen on the left to being seen on the right) then the robot will continue to turn but now in the wrong direction.

The problem is the commit_while test it overly strong. We can fix this by defining the relation

where, for example, op_dirs(left) = [right, centre_right] and changing rule 4 (and rule 6 similarly) to This example shows that we need to be careful when using commit_while and need to consider how we can "escape" from this commit when the environment has a negative effect. Here are three ways we can mitigate against this.

The first approach is similar to the above. Often we want to write something like

where the rule trigger G contains a part we want to be initially true and another part that we want to remain true. In other words G is rewritten as G1 & G2 where G1 is the triggering part and G2 is the continuing part. In that case we can write and so we won't stay committed to this rule if G2 becomes false.

The second approach that works sometimes, for example, where the bottle collector needs to detect and avoid another robot is to put the collision detection/avoidance rules in the parent TeleoR procedure. Since the effect of commit_while is local to the procedure in which it is used then it will not block the detection/avoidance of the other robot.

The third approach is to make the action a TeleoR procedure and add rules to it that will allow recovery from environmental interference.

---

Subsections

• Robot Side