Case Study

Instead of continuing to study obstacle avoidance , this time we attempt wall following . These problems are very similar in nature, and most of our existing work still applies to wall following. Notably, the targeted environments remain the same, as do the rest of the requirements and interface specification.

Only the behavioral outcome differs . This requires a new case study. Essentially, the animat must first find a wall, and then follow outward and inward corners:

If no wall is present and the animat is not already following one, a random move forward should be made.
If there is a wall in front, the animat should turn away from it, regardless of the presence of a wall on the side.
If there is a wall to the side and not in front, it should be followed by moving forward.
If no wall is present and one was being followed, the animat should turn toward the side where the wall last was.

Conceptually, the main difference with obstacle avoidance is the need for context-sensitive action. Indeed, the lack of obstacles means two different things, depending on whether a wall was previously being followed (cases 1 and 4). The mapping from senses to actions is thereby ambiguous, so a reactive system would have to pick the same rule in both these cases. If the animat deterministically selects the "turn" action, it will spin around in uncluttered areas; whereas always selecting the "move forward" action will make the animat lose contact with walls that turn away.

Luckily, nondeterminism is not a problem for RBSs, because we can add an internal symbol to distinguish the context. This "already following wall" symbol allows the system to be aware of the necessary behavior -which makes wall following possible (see Figure 12.1).

Figure 12.1. The four different cases that arise in wall following, and what actions are required.

graphics/12fig01.gif

Rationale

Before diving straight down into the low-level details of the implementation, we need to consider the previous research or design decisions to determine how it all fits together.

Rule-Based System or Not?

The main concern during development is a trade-off between work and results. How much time are we willing to invest in developing an RBS? A fully fledged system might take weeks to develop and may be overkill for this relatively simple problem. On the other hand, a simpler alternative (such as steering behaviors) will be much quicker to implement but might not be suited to other problems.

In this chapter, we will actually design a modular RBS. However, efficiency remains of prime importance because of the nature of the application; when targeting other problems than fundamental behaviors (such as motion), flexibility and extensibility are often the main requirements.

Type of Chaining

As far as the type of RBS is concerned , we'll stick to a forward-chaining system (explained in Chapter 11, "Rule-Based Systems") for two main reasons:

Behavioral simulation - Because we're simulating reactive control behaviors rather than problem solving, backward chaining is not a feasible option.
Procedural actions - With forward chaining, the body of each rule does not need to be in declarative form; the RBS executes it without knowing about it. This enables us to hard-code some of the actions. The major benefits lie in expressive power and efficiency (thanks to C++).

The intention is to allow direct support for hard-coded effectors (which perform actions in the environment), but also allow declarative conditions (loaded from a file). We'll support sensor indirectly by using preprocessing to gather information from the surroundings.

Precautions to Simplify Rules

Even though rules are conceptually simple, ideally we want to keep their complexity down to a minimum (both head and body). We also want to reduce the number of rules as much as possible. This will undoubtedly simplify the knowledge acquisition greatly.

Each of the rules is implicitly ranked, which hints to the interpreter which rules to pick first. When the processing starts with the higher priorities, latter rules can assume that the conditions of previous rules are true. This simplifies the conditions of rules lower down the ranks.

In addition, symbols are often set to the same values in the body of rules. For example, all but one rule may set symbol A to true. Explicitly including this action in every rule is highly redundant. Instead, we can use default values to set A to true unless it's overridden.

To reduce the number of rules, we'll allow for multiple actions in the rule body. This avoids the duplication of rules, and supports atomic operation; in some cases, we must set two symbols at the same time, instead of waiting for the next cycle of the interpreter to do so.