[Previous] [Home] [Next]

2. Design

We have used fuzzy techniques to (i) implement robust, uncertainty tolerating basic behaviors; (ii) coordinate the execution of multiple behaviors to achieve an overall goal; and (iii) maintain the robot self-localized with respect to an approximate map.

2.1. Basic behaviors

We describe each behavior B in terms of a desirability function (Ruspini 1991)

Des : State x Control --> [0,1]

that measures, for each state s (i.e., configuration of the LPS) and for each control vector c, the desirability Des(s,c) of applying the control c when the state is s from the point of view of B. The task of the controller is to compute, in state s, the value of Des(s,c) for each control c, and to use these values to choose one control c* for actual execution. In Flakey, this choice is made using centroid defuzzification:

In practice, we approximate the desirability function associated with each behavior B by a set of fuzzy rules of the form

IF A THEN C

where A is a fuzzy logic formula built from fuzzy predicates over state variables using the fuzzy connectives AND (min), OR (max) and NOT (complement to 1); and C is a fuzzy set of controls. For example, the rules in Figure 2 implement the Reach behavior, intended to bring the robot to a given target position at a fixed speed. Rule consequents are triangular fuzzy sets centered on the value given as a parameter. The predicates in the antecedents depend on the current position of the target with respect to the robot, stored in LPS variables. ``Out-of-Reach'' says that the target is too close on one side to be directly reached at the desired speed given Flakey's turning velocity. In this case, the robot must first move away from the target, and then turn towards it.

IF Target-Left AND NOT Out-of-Reach THEN Turn-Left(8)
IF Target-Right AND NOT Out-of-Reach THEN Turn-Right(8)
IF Target-Left AND Out-of-Reach THEN Turn-Right(4)
IF Target-Right AND Out-of-Reach THEN Turn-Left(4)
IF Target-Ahead THEN Go-Straight
Figure 2: Fuzzy rules for the Reach behavior.

Given a rule-set R = {R1,... ,Rn} for a behavior B, the fuzzy controller first computes

in the current LPS state s, and then chooses a preferred control value C using (2). This computation corresponds to the one performed by a classical (Mamdani type) fuzzy controller; note, however, that we allow each antecedent A to be an arbitrarily complex fuzzy logic formula, and not just a conjunction. As an illustration, Figure 3 shows the control surface obtained from the Reach ruleset using (2) and (1). (Theta, rho) is the target's position in robot polar coordinates. The effect of the ``Out-of-Reach'' predicate on the shape of the surface is clearly visible.

Figure 3: Control surface of the Reach behavior.

It should be noted that centroid defuzzification can produce undesired results when the output desirability is not unimodal; for example, the robot, having the option of avoiding an obstacle from the right or from the left, may decide to go straight. Our empirical strategy is to design the rule sets so as to avoid production of multi-modal desirabilities -- roughly, we insist that rules that propose opposite controls have mutually exclusive antecedents. Other authors (Baxter and Bumby 1993; Yen and Pfluger 1995) have relied on alternative defuzzification schemes. (See (Goodridge et al 1997) for a more cognitive approach.)

2.2. Behavior coordination

Consider now the case where several behaviors are simultaneously active. Ideally, we would like the robot to select the controls that best satisfy all the active behaviors. This may not be possible, though, if some behaviors prefer opposite actions. The key observation is that behaviors are not equally applicable to all situations: for instance, corridor following is most applicable when we are in a corridor and the path is clear, while obstacle avoidance is more applicable when there is an obstacle on the way. Correspondingly, we associate to each behavior B a context of applicability, expressed by a fuzzy logic formula Cxt. Given a set B = {B1,... , Bk} of behaviors, we define their context-dependent blending (CDB) to be the composite behavior described by the following desirability function

The controller computes all the needed Des[i](s,c) using (1), blend them according to (3), and finally choses one control value c* by (2).

We represent CDB of behaviors syntactically by using fuzzy meta-rules, or context rules. For instance, the following context rules can be used to blend the target reaching behavior Reach and the obstacle avoidance behavior KeepOff.

IF obstacle-close THEN KeepOff
IF NOT obstacle-close AND NOT at-target THEN Follow(Corr1)

Intuitively, the robot's actions are biased by the desirability functions of Reach and of KeepOff, in a combination that depends on the distance from a detected obstacle.

We have implemented CDB in Flakey using the hierarchical structure shown in Figure 4 , inspired by (Berenji et al 1990). A few observations should be made. First, it is essential that defuzzification be performed after combination. Second, we could include each context rule inside the corresponding behavior; this solution would be more amenable to a distributed implementation. Third, CDB can be iterated: we can use the structure in Figure 4 to implement each individual behavior, and combine several such (complex) behaviors using a second layer of context rules; and so on. Some of Flakey's behaviors have been built in this fashion.

Figure 4: The hierarchical fuzzy controller used in Flakey.

CDB can be used to execute a full navigation plan, represented by a set of context rules telling which behaviors should be used in which situation. The rules shown (in a simplified form) in Figure 5 constitute a navigation plan; each behavior is parameterized by the object it should be applied to. If executed in an environment with the right topological relations, like the one shown in Figure 9 below, this plan will get Flakey into Room4 by first following corridors Corr1 and Corr2, and then crossing door Door4. The plan also incorporates an avoidance behavior to go around possible obstacles. Section 4 will show an actual execution of this plan.

IF obstacle THEN KeepOff
IF NOT obstacle AND at(Corr1) AND NOT at(Corr2) THEN Follow(Corr1)
IF NOT obstacle AND at(Corr2) AND NOT near(Door4) THEN Follow(Corr2)
IF NOT obstacle AND near(Door4) AND NOT ar(Room4) THEN Cross(Door4)
IF at(Room4) THEN Stop
Figure 5 A plan for reaching Room4 in the environment in Figure 9 below.

Thanks to the logical format, context rules can be easily generated by a symbolic planner. When Flakey is given a new navigation goal, it uses a simple goal-regression planner to synthesize a set of context rules that achieves it, and uses CDB to execute these rules. The plan in Figure 5 has been generated in this way.

2.3. Using map information

In order to build plans that involve objects beyond what can be immediately perceived, Flakey uses a topological map that includes the stable features of the environment, like doors and walls, and their approximate locations. We represent approximate locations by fuzzy subsets of a given metric space, read under a possibilistic interpretation: if P is a fuzzy set representing the approximate location of an object, we read P(x) as the degree of possibility that that object be located at x. Approximate locations can model different aspects of locational uncertainty. Figure 6 shows four approximate locations in one dimension: in (a), the object is located at approximately 5 (``vagueness''); in (b), it can possibly be anywhere between 5 and 10 (``imprecision''); in (c), it can be either at 5 or at 10 (``ambiguity''); in (d), we are told that the object is at 5, but the source may be wrong, and there is a small possibility that it be located just anywhere (``unreliability'').

Figure 6: Representing different types of approximate locations by fuzzy sets.

To use the metric information in the map, the robot needs to know its own position with respect to this map. We have developed a recursive self-localization algorithm for Flakey based on fuzzy locations. The outline of the algorithm is as follows. At each time-step t the robot has an approximate hypothesis of its own location in the map, represented by a fuzzy set H[t] of the map frame. During navigation, the perceptual apparatus recognizes relevant features, and the map is searched for matching objects using a fuzzy measure of similarity. Each matching pair is used to build a fuzzy localizer: a fuzzy set representing the approximate location in the map where the robot should be in order to see the object where the feature has been observed. The shape of this set depends on the characteristics of perceptual recognition and is decided by the designer. Each localizer is seen as a source of information about the actual position of the robot. All the localizers so built at time t, plus odometric information, are combined by fuzzy intersection to produce the new hypothesis H[t+1], and the cycle repeats. More details can be found in (Saffiotti and Wesley 1996).

[Previous] [Home] [Next]

Last updated: August 7, 1997, by A. Saffiotti