Fuzzy State Machine Based Vehicle Navigation Defined in FBDL

Fuzzy State Machine Based Vehicle Navigation Defined in FBDL

Abuobeida Mohammed Elhassan Department of Communication Engineering Al-Neelain University (Sudan)

Awad Eisa G. Mohamed Mechanical Engineering Department Omdurman Islamic University- Sudan

Abstract:- Fuzzy Behavior Description Language (FBDL) is a suitable tool for defining Fuzzy State Machine based strategies. The goal of this paper to introduce the application of the FBDL for describing a vehicle navigation strategy in a Fuzzy Rule Interpolation (FRI) rule-base format. The FBDL is a declarative language supports the navigation strategy description which can be directly run on an FRI Behavior Engine. The main benefits of the FBDL application are the clear, verbose, and self-explanatory human readable knowledge base representation. Beyond the introduction of the FBDL application area, the paper also discusses the details of the navigation strategy definition, its implementation with its performance evaluation in a simulated environment.

Keywords: Fuzzy Behavior Description Language (FBDL); Fuzzy Rule Interpolation; Rule-based vehicle navigation

1. INTRODUCTION

   Automated Guided Vehicles (AGV) are increasingly present in industrial and services field, particularly when flexible motion capabilities are required on reasonably smooth grounds and. One of the most important issues in the field of (AGV) and autonomous navigation is to build physical systems that can move purposefully and without human intervention in real world environments and the design of control algorithms for path tracking, the main objective of such algorithms is to assure that the (AGV) will follow a predetermined path, the problem of path tracking by a (AGV) has been gaining in popularity over recent decades and has been extensively studied in Automated Guided Vehicles literature; various control strategies have been proposed to drive these vehicles efficiently to execute a given trajectory.

   One of these strategies is fuzzy reasoning method, its ability to represent linguistic terms and reliable decision making in spite of uncertainty and imprecise information makes it a useful tool in control systems.

   The main drawback of the classical fuzzy reasoning methods are demanding complete rule bases, construction of these rules claims a special care of filling all the possible rules. If there are some rules missing observation may result to no hit of the rule base and therefor no conclusion is obtained [1].

   One of solution of this problem is the application of the fussy rule interpolation (FRI) method, where the derivable rules are deliberately missing, since FRI methods can provide reasonable (interpolated) conclusions even if none of the existing rules fires under the current observation.

   The rule base of a FRI controller is not necessarily complete but it must contain the most significant fuzzy rules only without risking the chance of having no conclusion for some of the observations

2. A BRIEF OVERVIEW OF FRI TECHNIQUES

   .

   One of the first FRI techniques was published by Kocsy, and Hirota [2]. It is usually referred as KH method. It is applicable to convex and normal fuzzy (CNF) sets. It determines the conclusion by its a-cuts in such a way that the ratio of distances between the conclusion and the consequents should be identical with the ones between the observation and the antecedents for all important a-cuts. The applied formula:

   d (A*, A1) : d(A*, A1) =d(B*, B1) : d(B*, B2),

   can be solved for B*for relevant a-cuts after decomposition. It is shown in, e.g. in [3], [4] that the conclusion of the KH method is not always directly interpretable as fuzzy set. This drawback motivated many alternative solutions. A modification was proposed by Vass, Kalmar and Kocsy [5] (VKK method), where the conclusion is computed based on the distance of the center points and the widths of the a-cuts, instead of lower and upper distances. VKK method decreases the applicability limit of KH method, but does not eliminate it completely. The technique cannot be applied if any of the antecedent sets is singleton (the width of the antecedents support must be nonzero). In spite of the disadvantages, KH is popular because its simplicity that infers its advantageous complexity properties. It was generalized in several ways.

   Among them the stabilized KH interpolator is emerged, as it is proved to hold the universal approximation property [6], [7].This method takes into account all flaking rules of an observation in the calculation of the conclusion in extent to the inverse of the distance of antecedents and observation.

   The universal approximation property holds if the distance function is raised to the power of the inputs dimension.

   Another modification of KH is the modified alpha-cut based interpolation (MACI) method [8], which alleviates completely the abnormality problem. MACIs main idea is the following: it transforms fuzzy sets of the input and output universes to such a space where abnormality is excluded, then computes the conclusion there, which is finally transformed back to the original space. MACI uses vector representation of fuzzy sets and originally applicable to CNF sets [9].

   These latter conditions (CNF sets) can be relaxed, but it increases the computational need of the method considerably

   [10]. MACI is one of the most applied FRI methods [11], since it preserves advantageous computational and approximate nature of KH, while it excludes its abnormality. Another fuzzy interpolation technique was proposed by Kocsy, Hirota, and Gideon. [12]. It is called conservation of relative fuzziness (CRF) method, which notion means that the left (right) fuzziness of the approximated conclusion in proportion to the flanking fuzziness of the neighboring consequent should be the same as the (left) right fuzziness of the observation in proportion to the flanking fuzziness of the neighboring antecedent. The technique is applicable to CNF sets.

   An improved fuzzy interpolation technique for multidimensional input spaces (IMUL) was proposed in [13], and described in details in [11]. IMUL applies a combination of CRF and MACI methods, and mixes advantages of both.

   The core of the conclusion is determined by MACI method, while its flanks by CRF. The main advantages of this method are its applicability for multi-dimensional problems and its relative simplicity.

   Conceptually different approaches were proposed by Baranyi et al [14] based on the relation and on the semantic and inter- relational features of the fuzzy sets. The family of- 257 – these methods applies General Methodology (GM); this notation also reflects to the feature that these methods are able to process arbitrary shaped fuzzy sets. The basic concept is to calculate the reference point of the conclusion based on the ratio of the distances between the reference points of the observation and the antecedents. Then, single rule reasoning method (revision function) is applied to determine the final fuzzy conclusion based on the similarity of the fuzzy observation and an interpolated observation.

3. A DECLARATIVE LANGUAGE FOR BEHAVIOUR DESCRIPTION

   The task of the suggested declarative language is to provide a simple way for dening the state-transition rule-base size in a human readable form close to the original verbal form as the ethological models are given [15]. The proposed model is built from various rule-bases. According to the common decomposed FRI models, the rule-bases can have an arbitrary number of input values (antecedents) and a single output value (consequent). The state of te system is determined by the values of the edges. This enables the description of the structure of the system without restrictions on the inner implementation of the rule-bases.

   All the rule bases must possess a unique name, also the name of a rule-base needs to be the same as the name of its consequent. Therefore connections between the rule-bases can be dened by these unique names of the antecedents and the consequent.

   The presented language is a structured language consisting of various blocks.

   A block can be opened simply by using any valid keyword, which at the same time denes the type of the block. Blocks should be closed with the end keyword. Some types of blocks have a name in quotes after the type of block keyword. All types of blocks can optionally contain a description keyword which is followed by a documentation

   comment. Depending on the type, the contents of the blocks are slightly different. Considering the block denitions presented in the followings, our goal was to make them verbose and human readable.

   For formal description of the proposed behavior description language we present syntax diagrams. The text element marks a quoted string, which can contain arbitrary characters except the quote character itself. In the followings the language will be introduced in a top-down manner.

   The most important type of block is the rule-base type (Figure 1a).the scroll down window on the left of the MS Word Formatting toolbar. At the start of the rule base denition a method block (Figure 1b) denes which one of the supported consequent calculation methods should be used, with its corresponding parameters

   1. Rule base definition

   2. Term block definition

      Fig. 1: Syntax diagrams of the description language

4. FRI RULE BASE DESIGN EXAMPLE

   The application example introduced in this paper for demonstrating the benefits of the interpolation-based fuzzy reasoning as systematic approach, is the fuzzy rule base construction of an automated guided vehicle (AGV) steering control [16], [17]. In the example, the steering control has two goals, the path tracking (to follow a guide path) and the collision avoidance. The guide path is usually a painted marking or an active guide-wire on the floor. The guiding system senses the position of the guide path by special sensors (guide zone) tuned for the guide path. The goal of the steering control is to follow the guide path by the guide zone with minimal path tracking error on the whole path (fig. 2).

   . Fig. 2: Different steered AGV with guide zone, is path tracking error, ev is the distance of the guide path and the guide point, Pv, is guide point, K is the drining center, Rl, RR, RM are the distance measured by the left, right and middle ultrasonic sesors (UL, UR, UM)

   1. Path tracking, complete rule base

      The design of the steering control rule base can be divided into two main steps. First the path tracking rule base needed to be elaborated and then it can be extended by the rules of collision avoidance. The simplest way of defining the fuzzy rules is based on studying the operators control actions in relevant situations. These control actions could form the later rule base. The basic idea of the path tracking strategy is very simple: keep the driving centre K of the AGV as close as it is possible to the guide path, and than simply turn the AGV into the new direction. This strategy needs two observations, the measured distance between the guide path and the guide point (e), and the estimated distance between the guide path and the driving centre () (see fig. 3 for the notation). Based on V these observations, as a conclusion, the level of steering ( ) needed to be calculated. Collecting the operators control actions, the path tracking strategy can be

      Fig. 3: Relevant control actions (Vd: steering) characterizing the path tracking strategy

      Having the relevant control actions and the linguistic term fuzzy sets (fuzzy partitions) of the two antecedent and one consequent universes, the fuzzy rule base can be simply constructed. The ith rule of the rule base has the form:

      RVd : If ev =A1,I And d=A2,I Then Vd=Bi.

      Let us have the linguistic term fuzzy partitions built up five fuzzy sets, namely: negative large (NL), negative middle (NM), zero (Z), positive middle (PM), positive large (PL) for, d), and negative large (NL), negative small (NS), zero (Z), positive small (PS), positive large (PL) for the consequent universe (Vd). Building a complete fuzzy rule base first, according to the antecedent terms, we have to set up an antecedent grid of all possible fuzzy rules, and then fill it with the corresponding rule consequents (see Table I). First we can fill the rule consequents already known as relevant situations from the knowledge acquisition phase (noted by underline on Table I.), than to make the rule base complete, the filling rules too.

      In most cases, the filling rules have the only task to get smooth transient between the relevant rules. Selecting a fuzzy reasoning method, e.g. the max-min composition, and center of gravity defuzzification, the control surface of the steering can be directly calculated as shown in figure; 4.

      TABLE I

      PATH TRACKING, COMLETE RULE BASE

      v

      RVd: e

      NL: NM: Z: PM: PL:	PL PS Z NS NL PL PS PS Z NL PL PL Z NL NL PL Z NS NS NL PL PS Z NS NL
      Fig. 4: Control surface of the path tracking steering strategy, max-min CRI, center of gravity defuzzification, 25 rules, complete rule base (Table I.)

      = NL: NM: Z: PM: PL:

   2. Path tracking, sparse rule base

      The design of the path tracking steering control rule base for FRI is very similar to the complete rule base situation. The main difference is the lack of the filling rules. The rule base contains the rules of the relevant situations, known from the knowledge acquisition phase, only (see Table II).

      Introducing single antecedent rules, rules which have the same conclusion independently from some of the antecedents can be merged to single rules i.e. according to our example the rule base of Table II can be simplified to Table III. Selecting a fuzzy reasoning method suitable for sparse rule bases, i.e. in our case the FIVE FRI, introduced in Section III, after constructing the scaling functions of the antecedent and consequent universes based on their fuzzy partitions (see fig. 5, fig. 6, and fig. 7).

      Fig. 5: The ev antecedent fuzzy partition and its scaling function sev

      TABLE II

      PATH TRACKING, SPARSE RULE BASE

      v

      RVd: e

      = NL: NM: Z: PM: PL:

      NL: NM: Z: PM: PL:

      PL NL PL PS Z NL PL PL NL NL PL Z NS NL PL NL

      TABLE III

      RVd	ev		Vd
      Rule 1:	NL		PL
      Rule 2:	PL		NL
      Rule 3:	NM	Z	PL
      Rule 4:	PM	Z	NL
      Rule 5:	NM	PM	Z
      Rule6:	PM	NM	Z
      Rule 7:	Z	PM	NS
      Rule8:	Z	NM	PS

      PATH TRACKING, SPARSE RULE BASE

      Fig.6: The antecedent fuzzy partition and its scaling function s

      Fig. 7: The Vd consequent fuzzy partition and its scaling function sVd

   3. FBDL application example

   As an application a simple behavior set consisting of eight rule-bases is presented. Th inputs and outputs of the system are simulated by a small application developed for this purpose. The simulation environment employs an agent, which is able to explore its environment

   universe "Vd" "NL" -1 -1

   "NS" -0.3 -0.3

   "Z" 0 0

   "PS" 0.3 0.3

   "PL" 1 1

   end

   universe "ev" "NL" -1 -1

   "NM" -0.5 -0.5

   "Z" 0 0

   "PM" 0.5 0.5

   "PL" 1 1

   end

   universe "delta" "NL" -1 -1

   "NM" -0.5 -0.5

   "Z" 0 0

   "PM" 0.5 0.5

   "PL" 1 1

   end

   rule base "Vd" rule

   "PL" when ev" is "NL"

   end rule

   "NL" when ev" is "PL" end

   rule

   "PL" when "ev" is "Z" and "delta" is "NM"

   end rule

   "NL" when "ev" is "Z" and "delta" is "PM"

   end rule

   "Z" when "ev" is "PM" and "delta" is "NM"

   end rule

   "Z" when "ev" is "NM" and "delta" is "PM"

   end rule

   "NS" when "ev" is "PM" and "delta" is "Z"

   end rule

   "PS" when "ev" is "NM" and "delta" is "Z"

   end end

   The simulation of the above presented example with graphical user interface was created, and control surface of the steering can be directly calculated as shown in figure: 8.

   1

   0.5

   Vd

   0

   -0.5

   -1

   30

   20 25

   20

   15

   10 10

   5

   ev 0 0

   Fig. 8: Control surface of the path tracking steering strategy, rules, sparse rule base, according to (FBDL)

5. CONCLUSION

The main objective of this paper was to present a viable, application situated perspective on Fuzzy Rule Interpolation (FRI) strategies. Applying FRI techniques and thus scanty standard bases can drastically improve the method for fuzzy rule base creation. FRI strategies can spare the master from managing logical principles and accordingly help to lessen the quantity of the fuzzy rules needed should have been taken care of extensively. In the model "Path Tracking system" presented in this paper, the steering control sparse fuzzy rule base was built upon 12 runs as it were. If there should arise an occurrence of old style fuzzy logic controller (FLC), for example max-min CRI, and complete

principle base having a similar antecedent fuzzy partitions, the directing control ought to contain 52+ 25= 57 rules.

REFERENCES

[1] Szilvester Kovacs, Fuzzy Rule Interpolation in Practice, SCIS and ISIS 2006,Tokyo, Japan, Septemoer 20-24, 2006

[2] L. T. Kóczy and K. Hirota, Rule interpolation by a-level sets in fuzzy approximate reasoning, In J. BUSEFAL, Automne, URA-CNRS. Vol. 46. Toulouse, France, 1991, pp. 115-123.

[3] L. T. Kóczy and Sz. Kovács, On the preservation of the convexity and piecewise linearity in linear fuzzy rule interpolation, Tokyo Inst. Technol., Yokohama, Japan, Tech. Rep. TR 93-94/402, LIFE Chair Fuzzy Theory, 1993.

[4] L. T. Kóczy, and Sz. Kovács, Shape of the Fuzzy Conclusion Generated by Linear Interpolation in Trapezoidal Fuzzy Rule Bases, in Proceedings of the 2nd European Congress on Intelligent Techniques and Soft Computing, Aachen, 1994, pp. 16661670.

[5] G. Vass, L. Kalmár, and L. T. Kóczy, Extension of the fuzzy rule interpolation method, in Proc. Int. Conf. Fuzzy Sets Theory Applications (FSTA92), Liptovsky M., Czechoslovakia, 1992, pp. 1- 6.

[6] D. Tikk, I. Joó, L. T. Kóczy, P. Várlaki, B. Moser, and T. D. Gedeon, Stability of interpolative fuzzy KH-controllers, Fuzzy Sets and Systems, 125(1), January, 2002, pp. 105119.

[7] D. Tikk: Notes on the approximation rate of fuzzy KH interpolator.

Fuzzy Sets and Systems, 138(2), Sept., 2003, pp. 441453.

[8] D. Tikk and P. Baranyi, Comprehensive analysis of a new fuzzy rule interpolation method, In IEEE Trans. Fuzzy Syst., vol. 8, No. 3, June, 2000, pp. 281-296.

[9] Y. Yam, and L. T. Kóczy, Representing membership functions as points in high dimensional spaces for fuzzy interpolation and extrapolation, Dept. Mech. Automat. Eng., Chinese Univ. Hong Kong, Tech. Rep.CUHK-MAE-97-03, 1997.

[10] D. Tikk, P. Baranyi, T. D. Gedeon, and L. Muresan, Generalization of a rule interpolation method resulting always in acceptable conclusion, Tatra Mountains Math. Publ., 21, 2001, pp. 7391.

[11] K. W. Wong, D. Tikk, T. D. Gedeon, and L. T. Kóczy, Fuzzy Rule Interpolation for Multidimensional Input Spaces With Applications, IEEE Transactions on Fuzzy Systems, ISSN 1063-6706, Vol. 13, No. 6, December, 2005, pp. 809-819.

[12] L.T. Kóczy, K. Hirota, and T. D. Gedeon, Fuzzy rule interpolation by the conservation of relative fuzziness, Technical Report TR 97/2. Hirota Lab, Dept. of Comp. Int. and Sys. Sci., Tokyo Inst. of Techn., Yokohama, 1997.

[13] K. W. Wong, T. D. Gedeon, and D. Tikk: An improved multidimensional a-cut based fuzzy interpolation technique, In Proc. Int. Conf Artificial Intelligence in Science and Technology (AISAT2000), Hobart, Australia, 2000, pp. 2932.

[14] I. Perfilieva, Fuzzy function as an approximate solution to a system of fuzzy relation equations, Fuzzy Sets and Systems, 147, 2004, pp. 363383.

[15] Imre Piller, David Vincze, and Szilvester Kovacs, A Declaratve Language for Behavior Description, under publication.

[16] Sz. Kovács and L.T. Kóczy, Application of the Approximate Fuzzy Reasoning Based on Interpolation in the Vague Environment of the Fuzzy Rulebase in the Fuzzy Logic Controlled Path Tracking Strategy of Differential Steered AGVs, Lecture Notes in Computer Science, 1226, Springer, Germany, (1997), pp.456-467.

[17] Sz. Kovács and L. T. Kóczy, Application of an approximate fuzzy logic controller in an AGV steering system, path tracking and collision avoidance strategy, Fuzzy Set Theory and Applications, In Tatra Mountains Mathematical Publications, Mathematical Institute Slovak Academy of Sciences, vol.16, Bratislava, Slovakia, 1999, pp. 456-467.