Toto’s Mapping Behaviour’s

In order to store those landmarks, Toto constructed a map, as shown in figure. Here we come upon the really interesting fact about Toto: its distributed map representation. Each of the landmarks that Toto discovered was stored in its own behaviour. When Toto’s landmark detection layer discovered a corridor (C) going north (0) for 6.5 feet, it created a behaviour that looked something like this:

What you see above is pseudo-code, not really Toto’s code but something close to it and easier to read. The code above simply says that the behaviour represents a corridor (C) going north (0), so that whenever the input into that behaviour matches that description (i.e., when the input is C and 0, and the

An example of an indoor environment Toto navigated in, and a map it constructed of that environment.

approximate length and location are right), the landmark matches and the robot is in fact in that particular corridor.

Toto’s landmarks were clever: they worked regardless of which way Toto was going down a corridor or along a wall. A C0 shown above would also match C8 (because that corridor goes north-south, so Toto might be heading down the same corridor in the opposite direction), and C4 would also match C12 (because that corridor goes east-west). The same rule applied to walls as well: a left wall going north (LW0) matched a right wall going South (RW8), and so on.

Whenever the landmark-detecting layer detected a landmark, its description (type and compass direction) was sent to all map behaviours at the same time (in parallel). If any behaviour in the map matched the input, as described above, then that behaviour would become active, meaning Toto knew where it was in its map; this is called localization and is a very important part of the navigation problem.

 Ok, so far we have Toto moving around safely, detecting landmarks, and reporting those to the behaviour map. Whenever one matches, Toto recognizes that it is in a place where it has been before.

What happens if no behaviour in the map matches the landmark Toto is detecting?

That means Toto has discovered a new place/landmark, which needs to be added to the map. Suppose Toto is seeing a corridor (C) going east (4) that is approximately 5 feet long. Here is how it adds that new landmarks/behaviour to its map: it takes a brand new, empty behaviour “shell” and assigns it to the newly found landmark information, so it becomes:

It then connects the previous behaviour (suppose it is the C0 we just saw earlier) to the new one by putting a communication link between them. This means that when Toto is going north on C0, the next landmark it will see is C4.

To take advantage of knowing where it is (being localized), Toto’s map did another clever thing: the behaviour that was active sent messages to its neighbour in the direction in which Toto was traveling (for example, in the map shown in figure 16.5, C0 sent messages to C4 if Toto was going north, but to C12 if Toto was going south), to warn it that it should be next to be active. If the neighbour was next to be recognized, then Toto was even more confident about the accuracy of its map and its localization. On the other hand, if the expecting neighbour was not recognized next, that usually meant  that Toto had branched off on a new path it had not tried before, and would soon discover new landmarks to be added to the map.

Besides sending messages to its neighbours to tell them who is coming next, Toto’s map behaviours sent inhibitory messages to one another. Specifically, when a behaviour matches the incoming landmark, it sends messages to all of its neighbours to inhibit them, so that only one map behaviour can be active at one time, since Toto can really be only in one place at one time. That’s another part of Toto’s localization. (If this seems like a lot of machinery to assure Toto where it is, you’ll see in Chapter 19 how hard it is for any robot to know where it is.)

To summarize, Toto’s mapping layer performed the following behaviours:

1. Matched the received landmark against all landmark behaviours in the map

2. Activated the map behaviour that matched the current landmark

3. Inhibited the previous landmark

4. Reported if no landmark matched, and created a new landmark behaviour in response, storing the new landmark and connecting it to the previous landmark.

Path Planning in Toto’s Behaviour Map

As we have seen, while Toto roamed around its environment, it built up a landmark map of its world. This is an illustration of how you can build a distributed map with a behaviour-based system. Now let’s see how such a map is used to find/plan paths.

Let’s suppose that Toto’s watering can was empty, and it needed to go to the corridor with the water supply, so this landmark became Toto’s goal. If the goal landmark and Toto’s current position were the same behaviour in the map, then Toto was already at the goal and did not need to go anywhere. That’s too lucky to have been the case most of the time. Instead, Toto had to plan a path between its current location and the goal. Here is how it did that.

The behaviour that corresponded to the goal sent messages saying, “Come this way!” to all of its neighbours. The neighbours, in turn, sent the messages on to their own neighbours (but not back the way the message came; that would be a waste and create some problems). Each map behaviour, when passing a message along, also added to it its landmark length, so that as the path went

                                                     Toto’s way of path planning

through the network, its length grew based on the number and lengths of map behaviours it passed through.

Rather quickly, these messages all reached the currently active behaviour which represented wherever Toto was at the time. When they arrived, the messages contained the total length of the path taken to get there, in terms of physical landmark length. The current landmark paid attention only to the message with the minimum summed landmark length, since that indicated the direction toward the shortest path to the goal.

Besides going to a particular landmark, such as a specific corridor, Toto could also find the nearest landmark with a particular property. For example, suppose that Toto needed to find the nearest right wall. To make this happen, all right wall landmarks in the map would start sending messages. Toto followed the shortest path, and reached the nearest right wall in the map.